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.

International audience; The integration of genomics and patient related data is considered as one of the most promising investigation topic in health care research.Started in 2004, the GGM, Grid for Geno Medicine, project aims at providing a comprehensive grid software infrastructure designed to allow biologists to mine and analyze relationships between medical, genetic and genomic data stored in distributed datawarehouses. The proposed layered service oriented architecture offers a number of independent but compliant services that can be deployed in a grid environment. This paper presents these services insisting on their integration into a common software platform, the use case that is carried out. It also presents the current state of the developments and of the performance evaluations.

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. >

In this paper, we are interested in discovering genetic and environmental factors that are involved in multifactorial diseases. Experiments have been achieved by the Biological Institute of Lille and many data has been generated. To exploit these data, data mining tools are required and we propose a two-phase optimisation approach using a specific genetic algorithm. During the first step, we select significant features with a specific genetic algorithm. Then, during the second step, we cluster affected individuals according to the features selected by the first phase. The paper describes the specificities of the genetic problem that we are studying, and presents in detail the genetic algorithm that we have developed to deal with this very large size feature selection problem. Results on both artificial and real data are presented.

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.

International audience; Coprocessors are increasingly becoming key building blocks of High Performance Computing platforms. These many-core energy-efficient devices boost the performance of traditional processors. On the other hand, Branch-and-Bound (B&B) algorithms are tree-based exact methods for solving to optimality combinatorial optimization problems (COPs). Solving large COPs results in the generation of a very large pool of subproblems and the evaluation of their associated lower bounds. Generating and evaluating those subproblems on coprocessors raises several issues including processor-coprocessor data transfer optimization, vectorization, thread divergence, and so on. In this paper, we investigate the offload-based parallel design and implementation of B&B algorithms for coprocessors addressing these issues. Two major many-core architectures are considered and compared: Nvidia GPU and Intel MIC. The proposed approaches have been experimented using the Flow-Shop scheduling problem and two hardware configurations equivalent in terms of energy consumption: Nvidia Tesla K40 and Intel Xeon Phi 5110P. The reported results show that the GPU-accelerated approach outperforms the MIC offload-based one even in its vectorized version. Moreover, vectorization improves the efficiency of the MIC offload-based approach with a factor of two.

In this work a new family of image segmentation algorithms is proposed. This paper is a generalization of the model proposed, called: Power Watershed segmentation framework. Indeed, we extended it for cases: \(2< q < \inf \) and \(p \rightarrow \inf \). To do so, we explore the segmentation a new formulation of the segmentation problem based on game theory is proposed optimization energy function as a game theory problem. In this new formulation, The minimization can be, then, optimization process is seen as a search of the Nash equilibrium of a non-cooperative strategic game. Indeed, the computation of Nash equilibrium in finite game is equivalent to a non linear optimization problem afterward. As the optimization problem thus formulated the computation of the Nash equilibrium is an NP-hard problem, then, we propose the use of the Branch and Bound method is used to solve it to find it in reasonable time. In this study moreover, the uniqueness of the Nash equilibrium is demonstrated using a potential game-theoretic approach. Then we propose a new family of segmentation approach with \(2< q < \inf \)and \(p \rightarrow \inf \), named Game-based PW. The obtained results of the proposed approach, show are better than those given by the original Power Watershed \(q = 2\).

International audience; no abstract

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.

International audience; Image thresholding is definitely one of themost popular segmentation approaches for extracting objects from the background, or for discriminating objects from objects that have distinct gray-levels. It is typically simple and computationally efficient. It is based on the assumption that the objects can be distinguished by their gray levels. The optimal threshold is the one that can separate different objects fromeach other or from the background to such an extent that a decision can bemadewithout further processing [8, 13]. The automatic fitting of this threshold is one of the main challenges of image segmentation. Sezgin and Sankur [18] have presented a survey of a variety of thresholding techniques. There are a lot of approaches classifying thresholdingmethods. Authors in [18] labeled the method according to the information they exploit, such as histogram shape, space measurement clustering, entropy, object attributes, spatial information and local gray-level surface. Another classification approach consists in dividing these techniques into parametric and non-parametric techniques. The parametric thresholding methods exploit the first-order statistical characterization of the image to be segmented. Weszka et al. [16] proposed a parametric method where the gray-level distribution of each class is assumed to be a Gaussian distribution. An attempt to find an estimate of the parameters of the distribution that best fit the given histogram data is made by using the least-squares estimation method. Typically, it leads to a nonlinear optimization problem, its solution is computationally expensive and time consuming. Over the years, many researchers have proposed several algorithms to solve the objective function of Gaussian curve fitting for multi-level

The goal of this paper is to introduce an efficient evidential particle filter for complex shapes tracking. The particularity of that particle filter is not only the fair use of the observation at the current time in the update step of it by performing a curve evolution but also it represents a bridge between Probability function and Evidence theory. This bridge can be illustrated by incorporating a data fusion step in the update phase. This method builds a track by selecting the best particles between the particle candidates. This re-sampling phase is based on choosing the particles possessing the higher value of the basic belief assignment function. The values of these basic belief assignment functions are resulting from the fusion process of two distinctive sources of information. The first source is the energy functional and the second one is the local sensitive histogram. The evaluation of our approach, which is made on a realistic Brain cine RM sequences, aims at tracking the motion of the walls of the third ventricle. Therefore, the latter shows its obvious and clear efficiency. In order to validate our proposal, we present a comparative study between our proposal and the state of the art methods. The obtained results are encouraging.

Recently, a new technique for obtaining brain images of cine-MR (Magnetic Resonance) type has been developed by Hodel et al., (Brain ventricular wall movement assessed by a gated cine MR true FISP sequence in patients treated with endoscopic third ventriculostomy 19(12), (2009), [8]). The principle of this technique is to synchronize the MRI signal with the ECG (Electrocardiographic) signal. The MRI signal provides three dimensional images and cuts of high anatomical precision, and the ECG signal is obtained from the heart activity.

The evolution of Mixed-Integer Linear Programming (MIP) solvers has reached a very stable and effective level in which solving real-world problems is possible. However, the computed solution is not always the optimal one also because optimality is often not of primary interest for day-by-day users. We show some structural characteristics of MIP solvers and of computation for MIP problems that reveal the heuristic nature of the solvers. Moreover, we discuss the key components of MIP solvers with special emphasis on the role of heuristic decisions within the solution process. Finally, we present MIP solvers as “open” frameworks whose flexibility can be exploited to devise sophisticated hybrid algorithms.

A greedy randomized adaptive search procedure (GRASP) is a metaheuristic for combinatorial optimization. GRASP heuristics are multistart procedures which apply local search to a set of starting solutions generated with a randomized greedy algorithm or semi-greedy method. The best local optimum found over the iterations is returned as the heuristic solution. Path-relinking is a search intensification procedure that explores paths in the neighborhood solution space connecting two good-quality solutions. A local search procedure is applied to the best solution found in the path and the local optimum found is returned as the solution of path-relinking. The hybridization of path-relinking and GRASP adds memory mechanisms to GRASP. This chapter describes basic concepts of GRASP, path-relinking, and the hybridization of GRASP with path-relinking.

In this paper, a magnetic resonance image (MRI) segmentationmethod based on two-dimensional exponential entropy (2DEE) and parameterfree particle swarm optimization (PSO) is proposed. The 2DEE technique doesnot consider only the distribution of the gray level information but also takesadvantage of the spatial information using the 2D-histogram. The problem withthis method is its time-consuming computation that is an obstacle in real timeapplications for instance. We propose to use a parameter free PSO algorithmcalled TRIBES, that was proved efficient for combinatorial and non convexoptimization. The experiments on segmentation of MRI images proved that theproposed method can achieve a satisfactory segmentation with a lowcomputation cost.