During the three PhD research years, I have concentrated my research work on the resolution of large linear/non linear equation systems. These large problems cannot be solved using a single machine because it does not have enough computing power nor enough memory.
Therefore, we used distributed architectures to solve such large problems, such as grids and peer-to-peer environments.
These architectures are composed of heterogeneous distant volatile computing nodes interconnected via a high latency network.
In order to optimally use these architectures, adapted algorithms that take in consideration their characteristics, must be developed. Bahi and al. proved that the AIAC model (Asynchronous Iterations Asynchronous Communications)
for iterative parallel algorithms is well adapted to volatile distributed architectures.
Indeed, using this model, the computing nodes do not have to synchronize at each iteration, thus, there is no idle times between successive iterations.
Moreover, the AIAC tolerates the loss of data messages which makes it well adapted to volatile environments.
In order to execute the iterative methods, implemented based on the AIAC model, on distributed architectures, we have developed the JACEP2P-V2 platform.
It provides all the necessary functionalities to execute such algorithms, like multi-threading and asynchronous communications.
JACEP2P-V2 is also completely fault tolerant. It includes a distributed backup mechanism and a decentralized failure detection mechanism.
The efficiency of this platform have been evaluated over the Grid’5000 architecture while solving various large numerical problems, like the advection-diffusion problem or the smallest eigenvalue of a large sparse matrix,
using more than 1000 computing heterogeneous cores. The experiments showed that JACEP2P-V2 is well adapted to the distributed heterogeneous volatile environments and scalable.
We have also developed many parallel asynchronous resolution methods for solving differential equation systems. In particular, we proposed to couple the Waveform Relaxation method
with a sequential solver to solve differential systems over distributed high latency architectures. This method reduces the time costly data exchanges between computing nodes and thus reduces the total execution time.
This method was compared to the PVODE solver and the Multisplitting-Newton method and the experiments showed that over a distributed high latency architecture the Waveform Relaxation based method outperforms the PVODE solver and the Multisplitting-Newton method.
These research works were published in four international journals and three international conferences (IEEE and LNCS).
Key words : iterative asynchronous algorithms, peer to peer architectures, parallel computing, Java, threads, linear systems, EDP
Many combinatorial optimization problems are complex (usually NP difficult).
There exists two classes of methods to solve such problems : exact methods and heuristics.
Exact methods give the optimal solution for a problem but require a lot of execution time, they are well suited to solve small problems.
For large instances, heuristics are better suited. They require far less execution time than exact methods but they only give an approximation of the optimal solution. Finally, there is hybrid methods which are composed of exact methods and heuristics.
Hybrid methods use the advantages of both classes of methods to quickly find a near optimal solution to the problem.
All these optimization methods are computing intensive, especially for large problems.
Therefore, it is interesting to parallelize these methods and execute them over parallel or distributed architectures to decrease their execution times. Therefore, we have developed a parallel hybrid method well adapted to the grid environment.
This hybrid method is composed of a parallel exact B&B method coupled to a parallel genetic algorithm. The two methods exchange data to improve their search for the optimal solution. The parallelization of this hybrid method is based on the island model where the B&B islands divide the search space between them and each B&B island communicate with one genetic algorithm island to refine the search.
To execute this parallel hybrid method, we developed a framework that allows the two platforms Paradiseo and BOB++ to interact.
It is possible now to use the B&B algorithm included in BOB++ with the genetic algorithm included in Paradiseo in order to form an hybrid optimization method. The framework and the parallel hybrid method where evaluated over the Grid’5000 architecture while solving the Q3AP optimization problem. The experiments proved that the hybrid method outperforms classical methods and allowed us to solve to optimality a new large instance of order 15.
This research work was published in an international conference and was granted the best paper award.
Key words : Combinatorial problems, hybrid metaheuristics, parallel/distributed architectures.
Since September 2010, I have an assistant professor position at the university of Franche Comté and I am member of AND research team.
I have worked on parallelizing asynchronous iterative numerical resolution methods. In particular, I adapted the waveform relaxation parallel method to multi-core architectures such as GPUs. This method can easily benefit from the data parallelism paradigm.
The experiments executed on the new GPU cluster showed an 18x speed up when compared to a CPU execution.
I also am working on reducing the energy consumption of parallel iterative methods over grid and cluster architectures. I am tutoring a PhD student that is working on this subject. Our approach consists on using dynamic voltage and frequency scaling (DVFS) to reduce the energy consumed by the parallel iterative algorithm.
The optimal scaling factor is computed online after the execution of the first iteration and using the data retrieved from the execution of this first iteration,
such as computation time, executiontime and energy consumed during the first iteration.
I am also working on protein structure prediction using self avoiding walks (SAWs). This work is done in collaboration with other researchers in the AND team. I am working on parallelizing the algorithm for finding unfoldable SAWs or k time foldable walks that are not achieved by 90 degrees pivot operations from a direct line. These problems are NP complete and it’s difficult to enumerate all possible solutions for big instances. For these reasons, we are trying to use parallel heuristics or hybrid methods such as genetic algorithms to find unfoldable walks.
Key words : Green computing, DVFS, parallel/distributed architectures, SAW.