Large-scale parallelism for constraint-based local search: the costas array case study

设为首页

收藏本站

网站地图 | English | 公务邮箱

About the library

Background
History
Leadership
Organization

Readers' Guide

Opening Hours
Collections
Help Via Email

Publications

Electronic Information Resources

Large-scale parallelism for constraint-based local search: the costas array case study

详细信息查看全文

作者：Yves Caniou (1) Philippe Codognet (2) Florian Richoux (3) Daniel Diaz (4) Salvador Abreu (5) 1. JFLI ; CNRS / University of Tokyo / UCBL ; Lyon ; France 2. JFLI ; CNRS / University of Tokyo / UPMC ; Tokyo ; Japan 3. JFLI ; CNRS / University of Tokyo / LINA ; UNAM ; Nantes ; France 4. Universit茅 de Paris 1-Sorbonne ; Paris ; France 5. Universidade de 脡vora / CENTRIA ; 脡vora ; Portugal
关键词：CSP ; Local search ; Metaheuristics ; Parallelism ; Implementation
刊名：Constraints
出版年：2015
出版时间：January 2015
年：2015
卷：20
期：1
页码：30-56
全文大小：888 KB
参考文献：1. Aida, K., & Osumi, T. (2005). / A case study in running a parallel branch and bound application on the grid, (pp. 164鈥?73). USA: IEEE Computer Society, Washington, DC. 2. Aiex, R., Resende, M., Ribeiro, C. (2002). Probability distribution of solution time in GRASP: An experimental investigation. / J. Heuristics, / 8(3), 343鈥?73. blank" title="It opens in new window">CrossRef 3. Aiex, R., Resende, M., Ribeiro, C. (2007). TTT plots: a Perl program to create time-to-target plots. / Optimization Letters, / 1, 355鈥?66. blank" title="It opens in new window">CrossRef 4. Alava, M., Ardelius, J., Aurell, E., Kaski, P., Orponen, P., Krishnamurthy, S., Seitz, S. (2007). Circumspect descent prevails in solving random constraint satisfaction problems. / PNAS, / 105(40)(15), 253鈥?57. 5. Alba, E. (2004). Special issue on new advances on parallel meta-heuristics for complex problems. / J. Heuristics, / 10(3), 239鈥?80. blank" title="It opens in new window">CrossRef 6. Amdahl, G. (1967). / Validity of the single processor approach to achieving large scale computing capabilities, (pp. 483鈥?85). New Jersey: ACM Press, Atlantic City. URL http://doi.acm.org/10.1145/1465482.1465560. 7. Arbelaez, A., & Codognet, P. (2012). / Massively parallel local search for SAT. 8. Arbelaez, A., & Codognet, P. (2013). In M. Middendorf, & C. Blum (Eds.), / From sequential to parallel local search for SAT. 9. Arbelaez, A., & Hamadi, Y. (2011). In Coelo, C. (Ed.), / Improving Parallel Local Search for SAT, (p. 2011). Italy: LNCS, Rome. 10. Balint, A., Fr枚hlich, A., Tompkins, D., Hoos, H. (2011). / Sparrow2011. 11. Beard, J., Russo, J., Erickson, K., Monteleone, M., Wright, M. (2007). Costas array generation and search methodology. / IEEE Trans. Aerosp. Electron. Syst., / 43(2), 522鈥?38. blank" title="It opens in new window">CrossRef 12. Beldiceanu, N., & Bourreau, E. (1999). / Simonis, H. CSPLib website: A note on perfect square placement. csplib.org/prob/prob009/helmut.pdf" class="a-plus-plus">http://www.csplib.org/prob/prob009/helmut.pdf. 13. Benoist, T., Estellon, B., Gardi, F., Megel, R., Nouioua, K. (2011). Localsolver 1.x: a black-box local-search solver for 0-1 programming. / 4OR, / 9(3), 299鈥?16. blank" title="It opens in new window">CrossRef 14. Bessiere, C., & F. Rossi. (2006). In P. van Beek, & T. Walsh (Eds.), / Constraint propagation. 15. Boettcher, S., & Percus, A. (2000). Nature鈥檚 way of optimizing. / Artificial Intelligence, / 119(1-2), 275鈥?86. blank" title="It opens in new window">CrossRef 16. Boettcher, S., & Percus, A. (2003). Extremal optimization: an evolutionary local-search algorithm. arXiv:bs/cs/0209030" class="a-plus-plus">0209030. 17. Bolze, R. (2006). al.: Grid鈥?000: A large scale and highly reconfigurable experimental grid testbed. / Int. J. High Perform. Comput. Appl, / 20(4), 481鈥?94. blank" title="It opens in new window">CrossRef 18. Bordeaux, L., Hamadi, Y., Samulowitz, H. (2009). In C. Boutilier (Ed.), / Experiments with massively parallel constraint solving. 19. Caniou, Y., Codognet, P., Diaz, D., Abreu, S. (2011). / Experiments in parallel constraint-based local search, (p. 6622). Italy: Springer Verlag, Torino. 20. Caromel, D., di Costanzo, A., Baduel, L., Matsuoka, S. (2007). / Grid鈥橞nB: a parallel branch and bound framework for grids. 21. Chang, W. (1987). A remark on the definition of Costas arrays. / Proc. IEEE, / 75(4), 522鈥?23. blank" title="It opens in new window">CrossRef 22. Chen, Y.W., Zhu, Y.J., Yang, G.K., Lu, Y.Z. (2011). Improved extremal optimization for the asymmetric traveling salesman problem. / Physica A: Statistical Mechanics and its Applications, / 390(23-24), 4459鈥?465. blank" title="It opens in new window">CrossRef 23. Chu, G., Schulte, C., Stuckey, P. (2009). In I. Gent (Ed.), / Confidence-based work stealing in parallel constraint programming. 24. Chu, G., & Stuckey, P. (2008). / A parallelization of MiniSAT 2.0. 25. Codognet, P., & Diaz, D. (2001). / Yet another local search method for constraint solving: Springer Verlag. 26. Codognet, P., & Diaz, D. (2003). In T. Ibaraki (Ed.), / An efficient library for solving CSP with local search. 27. Costas, J. (1984). A study of detection waveforms having nearly ideal range-doppler ambiguity properties. / Proc. IEEE, / 72(8), 996鈥?009. blank" title="It opens in new window">CrossRef 28. Crainic, T., Gendreau, M., Hansen, P., Mladenovic, N. (2004). Cooperative parallel variable neighborhood search for the -median. / J. Heuristics, / 10(3), 293鈥?14. blank" title="It opens in new window">CrossRef 29. Crainic, T., & Toulouse, M. (2002). Special issue on parallel meta-heuristics. / J. Heuristics, / 8(3), 247鈥?88. blank" title="It opens in new window">CrossRef 30. Diaz, D., Abreu, S., Codognet, P. (2012). Targeting the cell broadband engine for constraint-based local search. / Concurrency and Computation: Practice and Experience, / 24(6), 647鈥?60. blank" title="It opens in new window">CrossRef 31. Diaz, D., Richoux, F., Codognet, P., Caniou, Y., Abreu, S. (2012). / Constraint-based local search for the costas array problem, (p. 7219). Paris, France: Springer Verlag. 32. Drakakis, K. (2006). A review of costas arrays. / J. Appl. Math., / 2006, 1鈥?2. blank" title="It opens in new window">CrossRef 33. Drakakis, K., Gow, R., Rickard, S. (2008). / Distance vectors in costas arrays. 34. Drakakis, K., Iorio, F., Rickard, S. (2011). The enumeration of costas arrays of order 28 and its consequences. / Advances in Mathematics of Communications, / 5(1), 69鈥?6. blank" title="It opens in new window">CrossRef 35. Drakakis, K., Iorio, F., Rickard, S., Walsh, J. (2011). Results of the enumeration of costas arrays of order 29. / Advances in Mathematics of Communications, / 5(3), 547鈥?53. blank" title="It opens in new window">CrossRef 36. Galinier, P., & Hao, J.K. (2000). / A general approach for constraint solving by local search. Germany: Paderborn. 37. Gendron, B., & Crainic, T. (1994). Parallel branch-and-bound algorithms: Survey and synthesis. / Oper. Res., / 42(6), 1042鈥?066. blank" title="It opens in new window">CrossRef 38. Gent, I., & Walsh, T. (1999). / CSPLIB: A benchmark library for constraints: Springer Verlag. 39. Golomb, S. (1984). Algebraic constructions for Costas arrays. / Journal Of Combinatorial Theory Series A, / 37(1), 13鈥?1. blank" title="It opens in new window">CrossRef 40. Golomb, S., & Taylor, H. (1984). Constructions and properties of Costas arrays. / Proc. IEEE, / 72(9), 1143鈥?163. blank" title="It opens in new window">CrossRef 41. Gomes, C., & Sellmann, M. (2004). In M. Wallace (Ed.), / Streamlined constraint reasoning: Springer Verlag. 42. (2007). In Gonzalez, T. (Ed.), / Handbook of Approximation Algorithms and Metaheuristics: Chapman and Hall / CRC. 43. Hamadi, Y., Jabbour, S., Sais, L. (2009). ManySAT: a parallel SAT solver. Journal on Satisfiability. / Boolean Modeling and Computation, / 6, 245鈥?62. 44. Hoos, H., & St眉tzle, T. (1998). / Evaluating Las Vegas algorithms: Pitfalls and remedies: Morgan Kaufmann. 45. Hoos, H., & St眉tzle, T. (1999). Towards a characterisation of the behaviour of stochastic local search algorithms for sat. / Artif. Intell., / 112(1-2), 213鈥?32. blank" title="It opens in new window">CrossRef 46. Hutter, F., Hoos, H., Leyton-Brown, K. (2010). Tradeoffs in the empirical evaluation of competing algorithm designs. / Ann. Math. Artif. Intell., / 60(1-2), 65鈥?9. blank" title="It opens in new window">CrossRef 47. Ibaraki, T., Nonobe, K., Yagiura, M. (2005). / (eds.) Metaheuristics: Springer Verlag. 48. Kadioglu, S., & Sellmann, M. (2009). / Dialectic search: Springer Verlag. 49. Kautz, H., Sabharwal, A., Selman, B. (2008). In A. Biere, M. Heule, H. van Maaren, T. Walsch (Eds.), / Incomplete algorithms. 50. Chassin de Kergommeaux, & J., Codognet P. (1994). Parallel logic programming systems. / ACM Computing Surveys, / 26(3), 295鈥?36. 51. Maneva, E., & Sinclair, A. (2008). On the satisfiability threshold and clustering of solutions of random 3-SAT formulas. / Theor. Comput. Sci., / 407(1-3), 359鈥?69. blank" title="It opens in new window">CrossRef 52. Martins, R., Manquinho, V., Lynce, I. (2012). An overview of parallel SAT solving. / Constraints, / 17, 304鈥?47. blank" title="It opens in new window">CrossRef 53. Michel, L., See, A., Van Hentenryck, P. (2006). In F. Benhamou (Ed.), / Distributed constraint-based local search: Springer Verlag. 54. Michel, L., See, A., Van Hentenryck, P. (2007). In C. Bessiere (Ed.), / Parallelizing constraint programs transparently: Springer Verlag. 55. Michel, L., See, A., Van Hentenryck, P. (2009). Parallel and distributed local search in comet. / Comput. Oper. Res., / 36, 2357鈥?375. blank" title="It opens in new window">CrossRef 56. Minton, S., Johnston, M., Philips, A., Laird, P. (1992). Minimizing conflicts: A heuristic repair method for constraint satisfaction and scheduling problems. / Artif. Intell., / 58(1-3), 161鈥?05. blank" title="It opens in new window">CrossRef 57. Moisan, T., Gaudreault, J., Quimper, C.G. (2013). In C. Schulte (Ed.), / Parallel discrepancy-based search: Springer. 58. Ohmura, K. (2009). / Ueda, K.: c-SAT: A parallel SAT solver for clusters: Springer Verlag. 59. Orue, A., 脕lvarez, G., Guerra, A., Pastor, G., Romera, M., Montoya, F. (2010). Trident, a new pseudo random number generator based on coupled chaotic maps. / CoRR abs/1008, 2345. 60. Pardalos, P., Pitsoulis, L., Mavridou, T., Resende, M. (1995). / Parallel search for combinatorial optimization: Genetic algorithms, simulated annealing, tabu search and GRASP. 61. Pedro, V. (2012). / Constraint Programming on Hierarchical Multiprocessor Systems. Universidade de 脡vora: Ph.D. thesis. 62. Perron, L. (1999). / Search procedures and parallelism in constraint programming: Springer Verlag. 63. R茅gin, J.C., Rezgui, M., Malapert, A. (2013). In C. Schulte (Ed.), / Embarrassingly parallel search: Springer Verlag. 64. Ribeiro, C., Rosseti, I., Vallejos, R. (2012). Exploiting run time distributions to compare sequential and parallel stochastic local search algorithms. / Journal of Global Optimization, / 54, 405鈥?29. blank" title="It opens in new window">CrossRef 65. Rickard, S., & Healy, J. (2006). / Stochastic search for costas arrays. NJ, USA: Princeton. 66. Russo, J., Erickson, K., Beard, J. (2010). Costas array search technique that maximizes backtrack and symmetry exploitation. / CISS, 1鈥?. 67. Schubert, T., Lewis, M., Becker, B. (2009). PaMiraXT: Parallel SAT solving with threads and message passing. Journal on Satisfiability. / Boolean Modeling and Computation, / 6, 203鈥?22. 68. Simonis, H. Limits of propagation (costas array). http://4c.ucc.ie/~hsimonis/ELearning/costas/handout.pdf. 69. Truchet, C. (2004). / Constraints, local search and computer-aided music composition. France: Ph.D. thesis, University of Paris-7. 70. Truchet, C., Richoux, F., Codognet, P. (2013). In J. Dongarra, & Y. Robert (Eds.), / Prediction of Parallel Speed-ups for Las Vegas Algorithms. 71. Van Hentenryck, P. (1989). / Constraint Satisfaction in Logic Programming: The MIT Press. 72. Van Hentenryck, P., & Michel, L. (2005). / Constraint-Based Local Search: The MIT Press. 73. Van Luong, T., Melab, N., Talbi, E.G. (2010). / Local search algorithms on graphics processing units: Springer Verlag. 74. Verhoeven, M. (1996). / Parallel local search. Ph.D. thesis. Netherlands: University of Eindhoven. 75. Verhoeven, M., & Aarts, E. (1995). Parallel local search. / Journal of Heuristics, / 1(1), 43鈥?5. blank" title="It opens in new window">CrossRef 76. Xiang, T., Liao, X., Wong, K. (2007). An improved particle swarm optimization algorithm combined with piecewise linear chaotic map. / Applied Mathematics and Computation, / 190(2), 1637鈥?645. blank" title="It opens in new window">CrossRef 77. Xie, F., & Davenport, A. (2010). / Massively parallel constraint programming for supercomputers: Challenges and initial results: Springer.
刊物类别：Computer Science
刊物主题：Artificial Intelligence and Robotics Optimization Computing Methodologies Operation Research and Decision Theory
出版者：Springer Netherlands
ISSN：1572-9354

文摘

We present the parallel implementation of a constraint-based Local Search algorithm and investigate its performance on several hardware platforms with several hundreds or thousands of cores. We chose as the basis for these experiments the Adaptive Search method, an efficient sequential Local Search method for Constraint Satisfaction Problems (CSP). After preliminary experiments on some CSPLib benchmarks, we detail the modeling and solving of a hard combinatorial problem related to radar and sonar applications: the Costas Array Problem. Performance evaluation on some classical CSP benchmarks shows that speedups are very good for a few tens of cores, and good up to a few hundreds of cores. However for a hard combinatorial search problem such as the Costas Array Problem, performance evaluation of the sequential version shows results outperforming previous Local Search implementations, while the parallel version shows nearly linear speedups up to 8,192 cores. The proposed parallel scheme is simple and based on independent multi-walks with no communication between processes during search. We also investigated a cooperative multi-walk scheme where processes share simple information, but this scheme does not seem to improve performance.