Search

Well-suited to embarrassingly parallel applications, the master-worker (MW) paradigm has largely and successfully used in parallel distributed computing. Nevertheless, such a paradigm is very limited in scalability in large computational grids. A natural way to improve the scalability is to add a layer of masters between the master and the workers making a hierarchical MW (HMW). In most existing HMW frameworks and algorithms, only a single layer of masters is used, the hierarchy is statically built and the granularity of tasks is fixed. Such frameworks and algorithms are not adapted to grids which are volatile, heterogeneous and large scale environments. In this paper, we revisit the HMW paradigm to match such characteristics of grids. We propose a new dynamic adaptive multi-layer hierarchical MW (AHMW) dealing with the scalability, volatility and heterogeneity issues. The construction and deployment of the hierarchy and the task management (deployment, decomposition of work, distribution of tasks, ...) are performed in a dynamic collaborative distributed way. The framework has been applied to the parallel Branch and Bound algorithm and experimented on the Flow-Shop scheduling problem. The implementation has been performed using the ProActive grid middleware and the large experiments have been conducted using about 2000 processors from the Grid'5000 French nation-wide grid infrastructure. The results demonstrate the high scalability of the proposed approach and its efficiency in terms of deployment cost, decomposition and distribution of work and exploration time. The results show that AHMW outperforms HMW and MW in scalability and efficiency in terms of deployment and exploration time.

Cellular network design is a major issue in mobile telecommunication systems. In this paper, a model of the problem in its full practical complexity, based on multiobjective constrained combinatorial optimization, has been investigated. We adopted the Pareto approach at resolution in order to compute a set of diversified non-dominated networks, thus removing the need for the designer to rank or weight objectives a priori. We designed and implemented a ''ready-to-use'' platform for radio network optimization that is flexible regarding both the modeling of the problem (adding, removing, updating new antagonist objectives and constraints) and the solution methods. It extends the ''white-box'' ParadisEO framework for metaheuristics applied to the resolution of mono/multi-objective Combinatorial Optimization Problems requiring both the use of advanced optimization methods and the exploitation of large-scale parallel and distributed environments. Specific coding scheme and genetic and neighborhood operators have been designed and embedded. On the other side, we make use of many generic features related to advanced intensification and diversification search techniques, hybridization of metaheuristics and grid computing for the distribution of the computations. They aim at improving the quality of networks and their robustness. They also allow, to speed-up the search and obtain results in a tractable time, and so efficiently solving large instances of the problem. Using three realistic benchmarks, the computed networks and speed-ups on different parallel and/or distributed architectures show the efficiency and the scalability of hierarchical parallel hybrid models.

Numerous parallel and distributed evolutionary algorithms (PDEAs) and their implementations have been proposed and are available on the Web. A robust approach to make easier their code and design reuse is the framework approach. In this paper, we present some existing frameworks for PDEAs and their development requirements, and propose a new C++ open source framework, named Parallel and distributed Evolving Objects (ParadisEO). ParadisEO is basically devoted to the reusable and flexible design of parallel and distributed metaheuristics, but we focus here only on PDEAs. Compared to other related frameworks, ParadisEO allows more reuse flexibility, and provides more implemented parallel and distributed models. Furthermore, these models can be exploited by the user in a transparent way, and deployed as well on shared memory multi-processors as on distributed memory machines. The architecture has been experimented on two real-world applications: the radio network design and the spectroscopic data mining. The experimental results demonstrate the efficiency and robustness of the different models.

The following topics are dealt with: cloud computing interoperability; energy efficient distributed systems; multiprocessor systems; MPSoC; high performance computing systems; security systems; peer-to-peer architectures; manycore system; pattern analysis; pattern recognition; hardware accelerators; biomedical systems; bioinformatics; digital home networks; multimedia contents protection; distributed data mining; parallel data mining; cellular automata and benchmarking.

GPUs are more and more used as low cost high performance computing platforms. While new parallel computing architectures and languages such as OpenCL and CUDA, as well as some new libraries ease up their programming, it is still relatively difficult to design code for them in an efficient way and it gives us a taste of what pioneers experimented in the 50's when programming the first computers. Also most of the current implementations suppose the co-existence of CPUs and GPUs, making the communication between those a real bottleneck in the proposed architectures. However, while new generations of GPU and architectures arise, a set of open questions that the Panel will attempt to address are still pending: — GPU and energy-efficiency: friend or foe? — Can GPU accelerate applications which are not ‘embarrassingly’ parallel? — Non-proprietary alternatives to GPU? — Programming support for GPU. Are we limited to imperative languages? — GPU clusters? — Security risks related to GPU? The Panel will also discuss the current state-of-the art and the opportunities and challenges ahead.

Task scheduling algorithms are designed mostly with the sole goal of minimizing makespan (completion time). Almost all research works related to this kind of algorithms do not pay much attention to energy consumption.

Solving exactly Combinatorial Optimization Problems (COPs) using a Branch-and-Bound algorithm requires a huge amount of computational resources. The efficiency of such algorithm can be improved by distributing at large scale the computation required by the exploration of the search tree. In this paper, we propose ParallelBB, which is a P2P-based parallelization of the Branch-and-Bound algorithm for the computational Grid. The algorithm has been implemented using the ProActive distributed object Grid middleware. The algorithm has been applied to a mono- criterion permutation flow-shop problem and promisingly experimented on the Grid5000 computational Grid.

Cellular network design is a major issue in mobile telecommunication systems. In this paper , a model of the problem in its full practical complexity, based on multiobjective constrained combinatorial optimization, has been investigated. We adopted the Pareto approach at resolution in order to compute a set of diversified non-dominated networks, thus removing the need for the designer to rank or weight objectives. We design an asynchronous steady-state evolutionary algorithm for its resolution. Specific coding scheme and genetic and neighborhood operators have been designed for the tackled problem. On the other side, we make use of many generic features related to advanced intensification and diversification search techniques, hybridization of metaheuristics and grid computing for the distribution of the computations. They aim at improving the quality of networks and robustness, at speeding-up the search, hence efficiently solving large instances of the problem. Using realistic benchmarks, the computed networks and speed-ups on parallel/distributed architectures show the efficiency and the scalability of hierarchical models of hybridization and parallelization used in conjunction.

Knowledge discovery from DNA microarray data has become an important research area for biologists. Association rules is an important task of knowledge discovery that can be applied to the analysis of gene expression in order to identify patterns of genes and regulatory network. Association rules discovery may be modeled as an optimization problem. We propose a multicriteria model for association rules problem and present a genetic algorithm designed to deal with association rules on DNA microarray data, in order to obtain associations between genes. Hence, we expose the main features of the proposed genetic algorithm. We emphasize on specificities for the association rule problem (encoding, mutation and crossover operators) and on its multicriteria aspects. Results are given for real datasets.

This paper presents briefly the aims and challenges addressed in the GGM (Grid for Geno-Medicine) project. The idea behind the project is to offer a software infrastructure able to analyze and discover links between distributed medical and genetic data.

Hill-climbing, simulated annealing and genetic algorithms are search techniques that can be applied to most combinatorial optimization problems. The three algorithms are used to solve the mapping problem, which is the optimal static allocation of communication processes on distributed memory architectures. Each algorithm is independently evaluated and optimized according to its parameters. The parallelization of the algorithms is also considered. As an example, a massively parallel genetic algorithm is proposed for the problem, and results of its implementation on a 128-processor Supernode are given. A comparative study of the algorithms is then carried out. The criteria of performance considered are the quality of the solutions obtained and the amount of search time used for several benchmarks. A hybrid approach consisting of a combination of genetic algorithms and hill-climbing is also proposed and evaluated. >

Mining predictive models in dense databases is CPU time consuming and I/O intensive. In this paper, we propose a taxonomy of existing techniques allowing to achieve high performance. We propose a hybrid approach allowing to exploit four of them: feature selection, GA-based exploration space reduction, parallelism and concurrency. The approach is experimented on a near-infrared (NIR) spectroscopic application. It consists of predicting the concentration of a given component in a given product from its absorbances to NIR radiations. Statistical methods, like PLS, are well-suited and efficient for such data mining task. The experimental results show that preceding those methods with a feature selection allows to withdraw a significant number of irrelevant features and at the same time to enhance significantly the accuracy of the discovered predictive model. It is also shown that for the considered task the GA-based approach allows to build more accurate models than neural networks. Moreover, the parallel multithreaded implementation of the approach allows a linear speed-up.

The Branch and Bound (B&B) algorithm is one of the most used methods to solve in an exact way combinatorial optimisation problems. In a previous article, we proposed a new approach of the parallel B&B algorithm for distributed systems using the farmer-worker paradigm. However, the new farmer-worker approach has a disadvantage: some nodes of the B&B tree can be explored by several B&B processes. To prevent this redundant work and speed up, we propose a new P2P approach inspired from the strategies of existing P2P systems like Napster and JXTA. Validation is performed by experimenting the two approaches on mono-objective flow-shop problem benchmarks using 500 processors belonging to the French national grid, Grid'5000. The obtained results prove the efficiency of the proposed P2P approach. Indeed, the execution time obtained with the P2P version, even if more communicative, is better than the farmer-worker's one.

Medical images, such as Computed Axial Tomography (CAT), Magnetic Resonance Imaging (MRI), Ultrasound, and X-Ray, in standard DICOM (Digital Imaging and Communications in Medicine) formats are often stored in Picture Archiving and Communication Systems (PACS) and linked with other clinical information in clinical management systems.