This paper shows how to parallelize a compute intensive application in mathematics (Group Theory) for an institutional Desktop Grid platform coordinated by a meta-grid middleware named BonjourGrid. The paper is twofold: it shows how to parallelize a sequential program for a multicore CPU which participates in the computation; and it demonstrates the effort for launching multiple instances of the solutions for the mathematical problem with the BonjourGrid middleware. BonjourGrid is a fully decentralized Desktop Grid middleware. The main results of the paper are: a) an efficient multi-threaded version of a sequential program to compute Littlewood-Richardson coefficients, namely the Multi-LR program and b) a proof of concept, centered around the user needs, for the BonjourGrid middleware dedicated to coordinate multiple instances of programsfor Desktop Grids and with the help of Multi-LR. In this paper, the scientific work consists in starting from a model for the solution of a compute intensive problem in mathematics, to incorporate the concrete model into a middleware and running it on commodity PCs platform managed by an innovative meta Desktop Grid middleware.
Top1. Introduction
Desktop Grid (DG) have been successfully used to address large applications with significant computational requirements, including search for extraterrestrial intelligence -SETI@Home (Anderson, Cobb, Korpela, Lebofsky, & Werthimer, 2002), global climate predication (Climatprediction.net,Anderson, 2004), and cosmic rays study (XtremWeb, Fedak, Germain, Néri, & Cappello, 2001; Cappello, Djilali, Fedak, Herault, Magniette, Néri, & Lodygensky, 2005). While the success of these applications demonstrates the potential of Desktop Grid, existing systems are often centralized and suffer from relying always on an administrative staff who guarantees the continuous running of the master. Moreover, although, in practical, the crash of the master is not frequent and replication techniques can solve this problem when it occurs, we still believe in the need to decentralized approaches. We justify this by the fact that since all institutions have not the same financial means to guarantee high levels of equipments robustness, the community should offer solutions to institutions which have not sufficient facilities to avoid the central element crash for instance. Thus, we believe in the importance of collaborative and decentralized solutions for the setting of Desktop Grid middleware.
In this context, Abbes, Cérin and Jemni have proposed a novel approach, called BonjourGrid (Abbes, Cérin, & Jemni, 2008, 2009), which enables to establish a specific execution environment for each user. Indeed, BonjourGrid constructs, dynamically and in a decentralized way, a Computing Element (CE – a CE is a set of workers managed by one master, or an instance of a local Desktop Grid middleware) when a user needs to run an application. BonjourGrid orchestrates multiple instances of CEs in a decentralized manner. Our approach does not rely on a unique static central element in the whole system, since we dedicate a temporary central element for each running application, in a dynamic way.
Furthermore, it is important to note that BonjourGrid is not only a decentralized approach to orchestrate and coordinate local DG (Desktop Grid) but it is also a system which is able, contrarily to classical DG, to construct specific execution environment on-demand (based on any combination of XtremWeb, Boinc, Condor middleware), in a decentralized, dynamic and autonomous way. This is the originality of the BonjourGrid system. We consider that it is a novel approach, a step forward regarding Desktop Grid systems.
The application that we investigate in this paper to explain our approach is a compute intensive applicationin the field of Group Theory. To our knowledge, there has been no attempt in the past to derive a multi-threaded solution of the computation of Littlewood–Richardson coefficients for desktop grid, especially for those based on multi-core processors. We give an original and efficient solution to this difficult problem because it is hard to predict on the fly the space where the solution is located in as we will see later in the paper.
Therefore, the paper is mainly organized according to two central discussions: first of all the threading of the computation of LR coefficients and second the integration of the solution into BonjourGrid. The typical use case underlying our work is the following: a mathematician needs to guess the property of some numbers. Usually it uses the PCs in its institution to ’compute’ the properties of the objects with the sequential implementation of Schur1 while colleagues work on others problems. He requires also that it could be done with a minimal effort for him (minimum of deployment, minimum of line codes to launch the application) because he is not an expert in grid middleware. This user belongs to the community of Boinc users, so he wants to use this middleware whereas one of his colleague belongs to the Condor community and he wants to use Condor. Our solution allows any user to run the multi-threaded release of the Schur application that we introduce in this paper on its favorite middleware.
We do not fully describe the adaptation of the application on the BonjourGrid infrastructure because it is out of the scope and will require too much space. BonjourGrid is a large project consisting in coordinating, simultaneously major desktop grid middleware such as Condor, Boinc and XtremWeb instances.