Embarrassingly Parallel Search in Constraint Programming
Authors: Arnaud Malapert, Jean-Charles Régin, Mohamed Rezgui
JAIR 2016 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | The experiments cover unsatisfiable, enumeration and optimization problems, but do not cover first solution search because it makes the results hard to analyze. The same variability can be observed for optimization problems, but at a lesser extent because the optimality proof is required. EPS offers good average performance, and matches or outperforms other available parallel implementations of Gecode as well as some solvers portfolios. |
| Researcher Affiliation | Academia | Arnaud Malapert EMAIL Jean-Charles R egin EMAIL Mohamed Rezgui EMAIL Universit e Cˆote d Azur, CNRS, I3S, France |
| Pseudocode | Yes | Algorithm 1: Top-down decomposition.Data: A CSP (X, D, C) and a number of subproblems p...Algorithm 2: Bottom-up decomposition.Data: A CSP (X, D, C), a decomposition depth d , and a subproblem limit P.Algorithm 3: Bottom-up estimation.Data: A CSP (X, D, C) and a number of subproblems p . |
| Open Source Code | No | The paper mentions using and implementing on top of existing solvers (Choco2, Gecode, OR-tools) and frameworks (Bobpp) but does not provide specific access information (e.g., a URL to a repository or an explicit statement of code release) for their own implementation of the Embarrassingly Parallel Search (EPS) method described in the paper. |
| Open Datasets | Yes | The first set called fzn is a selection of 18 instances selected from more than 5000 instances either from the repository maintained by Kjellerstrand (2014) or directly from the Minizinc 1.6 distribution written in the Flat Zinc language (NICTA Optimisation Research Group, 2012). The set xcsp is composed of instances from the categories ACAD and REAL of XCSP 2.1 (Roussel & Lecoutre, 2008). Besides, we will consider two classical problems, the n-queens and the Golomb ruler problems which have been widely used in the literature (Gent & Walsh, 1999). |
| Dataset Splits | No | The paper focuses on solving constraint programming problem instances rather than traditional machine learning datasets that are typically split into training, validation, and test sets. The concept of dataset splits in the context of this paper's problem domain (constraint programming instances) is not directly applicable, and thus no specific split information is provided. |
| Hardware Specification | Yes | Multi-core is a Dell computer with 256 GB of RAM and 4 Intel E7-4870 2.40 GHz processors running on Scientific Linux 6.0 (each processor has 10 cores). Data Center is the Centre de Calcul Interactif hosted by the Universit e Nice Sophia Antipolis which provides a cluster composed of 72 nodes (1152 cores) running on Cent OS 6.3, each node with 64 GB of RAM and 2 Intel E5-2670 2.60 GHz processors (8 cores). Cloud Computing is a cloud platform managed by the Microsoft company (Microsoft Azure) that enables to deploy applications on Windows Server technology (Li, 2009). Each node has 56 GB of RAM and Intel Xeon E5-2690E 2.6 GHz processors (8 physical cores) We were allowed to simultaneously use 3 nodes (24 cores) managed by the Microsoft HPC Cluster 2012 (Microsoft Corporation, 2015). |
| Software Dependencies | Yes | We implemented EPS method on top of three solvers: Choco2 2.1.5 written in Java, Gecode 4.2.1 and OR-tools rev. 3163 written in C++. We use two parallelism implementation technologies: Threads (Mueller et al., 1993; Kleiman, Shah, & Smaalders, 1996) and MPI (Lester, 1993; Gropp & Lusk, 1993). There are many implementations for MPI like Open MPI (Gabriel, Fagg, Bosilca, Angskun, T., Dongarra, J., Squyres, J., Sahay, V., Kambadur, P., Barrett, B., Lumsdaine, A., et al., 2004), Intel MPI (Intel Corporation, 2015), MPI-CH (MPI-CH Team, 2015) and MS-MPI (Krishna, J., Balaji, P., Lusk, E., Thakur, R., & Tiller, F., 2010; Lantz, E., 2008). In fact, Gecode will use C++ pthread on the multi-core computer, Open MPI on the data center, and MS-MPI on the cloud platform. The cluster is managed by OAR (Capit, N., Da Costa, G., Georgiou, Y., Huard, G., Martin, C., Mounie, G., Neyron, P., & Richard, O., 2005). |
| Experiment Setup | Yes | The time limit for solving each instance is set to 12 hours whatever be the solver. If the number of workers is strictly less than the number of cores (w < c), then there will always be unused cores. Usually, one chooses w = c, so that all workers can work simultaneously. On the multi-core computer, we use two workers per physical core (w = 2c) because hyperthreading is efficient as experimentally demonstrated in Appendix A. The target number p of subproblems depends linearly on the number w of workers (p = 30 w) that allows statistical balance of the workload without increasing too much the total overhead (R egin et al., 2013). In our experiments, the network and RAM memory loads are low in regards to the capacities of the computing infrastructures. Indeed, the total number of messages depends linearly of the number of workers and the number of subproblems. RAM is pre-allocated if the computing infrastructure allows it. Last, workers almost produce no input/output or disk access. In our experiments, the queuing policy is the FIFO policy that ensures that subproblems are solved in the same order so that the speedups are relevant. However, there is no guaranty that the sequential and parallel algorithms return the same solution. |