N-Queens Contest
ETSI and INRIA organized the IV Grid Plugtests of the of the IV Grid@work event from the 28th of October to the 2nd of November 2007 at Beijing in China.
The IV Grid Plugtests was made of two contests:
- the N-Queens Contest ;
- the Flowshop Contest.
The Kaapi/MOAIS Team took part in the N-Queens Contest. It is made up of:
- Xavier Besseron (integration of TakTuk with ProActive),
- Vincent Danjean (karun),
- Guillaume Huard (TakTuk),
- Serge Guelton (N-Queens program),
- Frédéric Wagner (N-Queens program),
- Thierry Gautier (Kaapi, leader).
You can find all the teams who took part in this event here.
The N-Queens application
The N-Queen application that we developed for this Plugtests is composition of three grid tools :
- TakTuk is a tool for deploying parallel remote executions of commands to a potentially large set of remote nodes. It spreads itself using an adaptive algorithm and sets up an interconnection network to transport commands and perform I/Os multiplexing/demultiplexing. The TakTuk mechanics dynamically adapt to environment (machine performance and current load, network contention) by using a reactive work-stealing algorithm that mixes local parallelization and work distribution.
- Kaapi (Kernel for Adaptative, Asynchronous Parallel and Interactive programming) is a C++ library that allows to execute multithreaded computation with data flow synchronization between threads. The library is able to schedule fine/medium size grain program on distributed machine. The data flow graph is dynamic (unfold at runtime). Target architectures are clusters of multiprocessor machines.
- ProActive is a middleware (part of the ObjectWeb consortium, with Open Source code) for parallel, distributed and multithreaded computing. Its use was imposed by the rules of the contest. We used it only to reserve nodes and connect to one node on each cluster.
The 3 key points of reaching high level of performances are :
- Have a simple API to develop parallel program. The program have been developed on top of the Athapascan API of KAAPI that defines only two keywords to describe parallelism. We have mostly reused the version of that we have used during the III GRID PLUGTESTS in 2006. The first version was developed in less than half a day based on the original Takaken code. Three full-time days has been devoted to optimize the sequential code using C++ template specialization. The gain with the original Takaken code is about 34%.
- Use a proved theoretical scheduling algorithm for these kind of strict multithreaded computation (our N-Queens is a pure serie-parallel program) for both homogeneous or heterogeneous (in speed) clusters. This scheduling algorithm is basically a work-stealing algorithm that is theoretically efficient for program with small critical path with respect to the work. We have extend classical workstealing algorithm with hierarchical version in order to better take into account the hierarchy of grid. Experiments during the contest have demonstrated its very good scalability up to 3654 cores.
- Use an efficient deployment tool TakTuk. This year we have work on integrating TakTuk into proActive deployment mechanism.
Results
Run of our N-Queens application
Some timings during the plugtest:
- N-Queens N=22 solved in 3min 21s on 3654 cores of Grid5000 ;
- N-Queens N=23 solved in 35min 7s on 3654 cores of Grid5000 ;
- Deployment of all processes last less than few minutes using proActive and the Kaapi launcher karun on top of taktuk.
Ganglia output during the run on Grid'5000 :
Full Ganglia capture 1 Full Ganglia capture 2
Results of the contest
Future works
See also
N-Queens KAAPI performances at the III GRID PLUGTESTS 2006
KAAPI winner of IV GRID PLUGTESTS 2007
KAAPI winner of V GRID PLUGTESTS 2008
Related links
Contact
<xavier besseron (a) imag fr>
<kaapi-dev-info (a) lists gforge inria fr>