Please use this identifier to cite or link to this item:
|Title: ||On the Scalability of Constraint Programming on Hierarchical Multiprocessor Systems|
|Authors: ||Machado, Rui|
|Keywords: ||constraint solving|
|Issue Date: ||Oct-2013|
|Citation: ||Rui Machado and Vasco Pedro and Salvador Abreu, On the Scalability of Constraint Programming on Hierarchical Multiprocessor Systems, Proceedings of the The 42nd International Conference on Parallel Processing (ICPP-2013), pp 530-535, Lyon, France, October 2013. IEEE CPS.|
|Abstract: ||Recent developments in computer architecture progress towards systems with large core count, which expose more parallelism to applications, creating a hierarchical setup at the node and cluster levels. To take advantage of all this parallelism, applications must carefully exploit the different levels of the system which, if ignored, may yield surprising results. This aggravates the already difficult task of parallel programming.
Declarative approaches such as those based on constraints are attractive to parallel programming because they concentrate on the logic of the problem. They have been successfully applied to hard problems, which usually involve searching through large problem spaces, a computationally intensive task but with potential for parallelization. Tree search algorithms play an important role in research areas such as constraint satisfaction or optimisation, and artificial intelligence. Tree search lends itself naturally to parallelization by exploiting different branches of the tree but scalability may be harder to achieve due to the high dynamic load balancing requirements.
In this paper we present a high-level declarative approach based on constraints and show how it benefits from an efficient dynamic load balancing based on work stealing targeted at large-scale. We focus on the implementation of a hierarchical work stealing scheme using a different programming model, GPI. Experimentation brought encouraging results on up to 512 cores on large instances of satisfaction and optimisation problems.|
|Appears in Collections:||INF - Artigos em Livros de Actas/Proceedings|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.