INRIA "Lille - Nord Europe" Research Center
Dolphin Project
A post-doctoral position is open in the DOLPHIN research group at INRIA Lille - Nord Europe on parallel hybrid metaheuristics on massively multi-processor and multi-core/GPU environments.
To apply:
Application deadline: May 4th, 2009
Starting date: from September to December 2009
Location: Parc Scientifique de la Haute Borne - 40, avenue Halley Bāt. A, Park Plaza - 59650 Villeneuve d'Ascq.
Apply one-line
Contacts:
- Prof. Nouredine MELAB, email
- Prof. El-Ghazali TALBI, email
Environnement:
In practice, combinatorial optimization problems are complex and computationally large size. Therefore, near-optimal methods such as metaheuristics are required to solve them in a reasonable time. Metaheuristics are either single-oriented (e.g. local search methods) or population-base (e.g. evolutionary algorithms). Their hybridization often provides the best known solutions. Even if metaheuristic techniques allow to significantly reduce the computation time cost of the solution exploration space this later cost remains exorbitant when very large problem instances are dealt with. As a consequence, large scale parallel computing often based these last years on computational grids. Metaheuristics are inherently parallel and three parallel models [1] are often used to solve effectively and efficiently large combinatorial problems: island/multi-start model, parallel evaluation of the population/neighbourhood, and the parallel evaluation of a single solution.
Grid infrastructures allow to harness a large number of computational resources interconnected by a wide-area and high latency network. To take benefit from the large amount of resources provided by the grid the three parallel models must be simultaneously used in a hierarchical way [2]. Moreover, these models must be adapted to take into account the characteristics of the environment: large scale, heterogeneous and volatile nature of the resources, multi-institutional aspects.
Nowadays, Petascale Computing is the present state-of-the-art in High Performance Computing that leverages the most cutting edge large-scale resources to solve challenging problems in science and engineering. One of the major issues of that emerging technology is the design of algorithms and programming techniques that allow to efficiently use the huge amount of resources at disposal. The main objective of this Post-Doctoral proposal is to deal with such scientific challenge in the context of near-optimal combinatorial optimization. More exactly, the focus is on the re-design of parallel metaheuristic models to allow solving of large scale optimization problems on massively multi-processor and multi-core/GPU architectures.
Missions:
thousands or hundreds of thousands. On the other hand, these architectures are becoming more heterogeneous and memory hierarchical and their interconnection networks are increasingly complex [3]. The major objective of this proposal is to re-visit the parallel models for metaheuristics in order to take into account the above characteristics. The issues to be focused on consist mainly in:
Finding the optimal mapping of the hierarchical parallel hybrid models on the hierarchical multi-cluster of cores, the dynamic distribution of the exploration and evaluation processes, the checkpointing mechanism in a massively hierarchical parallel environment, etc. We believe that the approaches proposed and discussed in [2] for computational grids could be re-visited and re-used for massively parallel multi-cores (grid on chip).
The proposed approaches must be then implemented in ParadisEO [5,6]. ParadisEO is a software framework for the design and implementation of metaheuristics for mono-objective and multi-objective optimization problems, and hybrid/parallel metaheuristics. A great effort in terms of programming and state-of-the-art study must be done here in order to choose the adequate programming hybrid model and language.
The designed and implemented approaches must be experimentally validated on some cryptoanalysis problems [7]. Within the Dolphin project, we currently collaborate with the artificial intelligence group from the University of Madrid. The applicant will be involved in this cooperation.
Requirements:
C++ programming, Parallel computing, Metaheuristics, Combinatorial Optimization.
Bibliographical References:
N. Melab, E-G. Talbi, S. Cahon, E. Alba and G. Luque. Parallel Metaheuristics: Algorithms and Frameworks. Chapter 6 in "Parallel Combinatorial Optimization", Wiley Series on Parallel and Distributed Computing, ISBN: 0-471-72101-8, Pages 149-161, 2006.
N. Melab, S. Cahon, E-G. Talbi. Grid computing for parallel bioinspired algorithms. Journal of Parallel and Distributed Computing (JPDC), Elsevier Science, Vol. 66(8), Pages 1052-1061, Aug. 2006.
Maurice Herlihy: The future of distributed computing: renaissance or reformation? In Proc. of ACM PODC'08, Toronto, Canada, 2008.
C. Hughes and T. Hughes. Professional multicore programming: design and implementation for C++ developers. Wrox, 2008.
S. Cahon, N. Melab and E-G. Talbi. ParadisEO: A Framework for the Reusable Design of Parallel and Distributed Metaheuristics. Journal of Heuristics, Vol.10 (3), ISSN:1381-1231, pages 357-380, May 2004.
John A Clark and Jeremy L Jacob. Protocols are Programs Too: the Meta-heuristic Search for Security Protocols. IS&T Special Issue on Metheuristics for Software Engineering (December 2001).
