Recent years have witnessed growing interest in parallelising constraint solving based on tree search. One approach is search-space splitting in which different parts of the tree are explored in parallel. Another approach is the use of algorithm portfolios. This technique exploits the significant variety in performance observed between different algorithms and combines them in a portfolio. In constraint solving, an algorithm can be a solver or a tuning of a solver. Portfolios have often been run in an interleaving fashion. Their use in a parallel context is more recent. Considering the complexity of the constraint problems and thus the computational power needed to tackle them, it is appealing to benefit from large-scale parallelism and push for a massive number of CPUs. Bordeaux et. al have investigated this. By using the portfolio and search-space splitting strategies, they have conducted experiments on constraint problems using a parallel computer with the number of processors up to 128. They reported that the parallel portfolio approach scales very well in SAT, in the sense that utilizing more processors consistently helps solving more instances in a fixed amount of time. Most of the prior work in parallel constraint solving assumes a parallel computer with multiple CPUs. This architecture is fairly reliable and has low communication overhead. However, such a computer is costly and is not always at our disposal, especially if we want to push for massive parallelism. Jaffar et al addressed this problem by using a bunch of computers in a network (called “volunteer computing” in what follows). They employed 61 computers in a search-space splitting approach and showed that such a method is effectively scalable in ILP. In this paper, we combine the benefits of previous work when solving constraint satisfaction problems (CSPs). We present an architecture in which massive number of volunteer computers can run several (tunings of) constraint solvers in parallel in a portfolio approach so as to solve many CSPs in a fixed amount of time. The architecture is implemented using the service-oriented computing paradigm and is thus modular, flexible for useful extensions and allows to utilise even the computers behind a firewall. We report experiments up until 100 computers. As the results confirm, the architecture is effectively scalable.
Z. Kiziltan, J. Mauro (2010). Service-Oriented Volunteer Computing for Massively Parallel Constraint Solving Using Portfolios. HEIDELBERG : Springer Verlag.
Service-Oriented Volunteer Computing for Massively Parallel Constraint Solving Using Portfolios
KIZILTAN, ZEYNEP;MAURO, JACOPO
2010
Abstract
Recent years have witnessed growing interest in parallelising constraint solving based on tree search. One approach is search-space splitting in which different parts of the tree are explored in parallel. Another approach is the use of algorithm portfolios. This technique exploits the significant variety in performance observed between different algorithms and combines them in a portfolio. In constraint solving, an algorithm can be a solver or a tuning of a solver. Portfolios have often been run in an interleaving fashion. Their use in a parallel context is more recent. Considering the complexity of the constraint problems and thus the computational power needed to tackle them, it is appealing to benefit from large-scale parallelism and push for a massive number of CPUs. Bordeaux et. al have investigated this. By using the portfolio and search-space splitting strategies, they have conducted experiments on constraint problems using a parallel computer with the number of processors up to 128. They reported that the parallel portfolio approach scales very well in SAT, in the sense that utilizing more processors consistently helps solving more instances in a fixed amount of time. Most of the prior work in parallel constraint solving assumes a parallel computer with multiple CPUs. This architecture is fairly reliable and has low communication overhead. However, such a computer is costly and is not always at our disposal, especially if we want to push for massive parallelism. Jaffar et al addressed this problem by using a bunch of computers in a network (called “volunteer computing” in what follows). They employed 61 computers in a search-space splitting approach and showed that such a method is effectively scalable in ILP. In this paper, we combine the benefits of previous work when solving constraint satisfaction problems (CSPs). We present an architecture in which massive number of volunteer computers can run several (tunings of) constraint solvers in parallel in a portfolio approach so as to solve many CSPs in a fixed amount of time. The architecture is implemented using the service-oriented computing paradigm and is thus modular, flexible for useful extensions and allows to utilise even the computers behind a firewall. We report experiments up until 100 computers. As the results confirm, the architecture is effectively scalable.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
