Search

International audience

The field of life imaging spans a large spectrum of scientific study from mathematics and computer science to medical, passing by physics, biology, etc. The challenge of IDV project is to enrich a multi-parametrized, quantitative, qualitative, integrative, and correlative life imaging in health. It deals with linking the current research developments and applications of life imaging in medicine and biology to develop computational models and methods for imaging and quantitative image analysis and validate the added diagnostic and therapeutic value of new imaging methods and biomarkers.

In this paper, we introduce a new parallel and distributed algorithm for the resolution of the satisfiability problem. The proposed algorithm is based on algorithm portfolio and is intended to be used for servicing requests in a distributed cloud. The core of our contribution is the modeling of the optimal resource sharing schedule in parallel executions and the proposition of heuristics for its approximation. For this purpose, we reformulate a computational problem introduced in prior work. The main assumption is that it is possible to learn the optimal resource sharing from traces collected on past executions on a representative set of instances. We show that the learning can be formalized as a set coverage problem. Then, we propose to solve it by approximation and dynamic programming algorithms. These algorithms are based on classical greedy algorithms for the maximum coverage problem. Finally, we conduct an experimental evaluation for comparing the performance of the various proposed algorithms. The results show that some algorithms become more competitive if we intend to determine the trade-off between their quality and the runtime required for their computation.

International audience; —In this paper we investigate the general problem of controlling a scientific workflow service in terms of data management. We focus on the data management problem for the RedisDG scientific workflow engine. RedisDG is based on the Publish/Subscribe paradigm for the interaction between the different components of the system, hence new issues appear for scheduling. Indeed, the Publish/Subscribe paradigm utilization introduces different challenging problems, among them the design of effective solutions for managing data, on the fly, when tasks are published. Our contributions are twofold. First we add new functionalities to the RedisDG workflow engine with scheduling decisions related to the allocation of data intensive jobs to compute units and according to an efficient management of data and second we introduce a large set of experiments to validate our approaches. We analyze our results and we also sketch perspectives and insights. Experiments are conducted on the Grid'5000 testbed and the paper is a step forward to implement a 'Workflow engine as a Service' (WaaS).

International audience; —This article proposes a path for doing Data Science using browsers as computing and data nodes. This novel idea is motivated by the cross-fertilized fields of desktop grid computing, data management in grids and clouds, Web technologies such as Nosql tools, models of interactions and programming models in grids, cloud and Web technologies. We propose a methodology for the modeling, analyzing, implemention and simulation of a prototype able to run a MapReduce job in browsers. This work allows to better understand how to envision the big picture of Data Science in the context of the Javascript language for programming the middleware, the interactions between components and browsers as the operating system. We explain what types of applications may be impacted by this novel approach and, from a general point of view how a formal modeling of the interactions serves as a general guidelines for the implementation. Formal modeling in our methodology is a necessary condition but it is not sufficient. We also make round-trips between the modeling and the Javascript or used tools to enrich the interaction model that is the key point, or to put more details into the implementation. It is the first time to the best of our knowledge that Data Science is operating in the context of browsers that exchange codes and data for solving computational and data intensive programs. Computational and data intensive terms should be understand according to the context of applications that we think to be suitable for our system.

In this paper we propose new insights into the problem of concurrently scheduling threads through mainly the Work Stealing (WS) technique which is one of the technique, with Parallel Depth First (PDF) technique able to efficiently manage fine-grained mutithreaded programs. We investigate a nice result of Bender and Rabin about the scheduling of threads in an heterogeneous context, show the limits in terms of (theoretical) performance and we propose to enhance the efficiency of the processor use by keeping the fastest processor busy and working on the critical path of the application. Then we provide a bound on the completion time. We also investigate the problem of execution time penalies when scheduling according to WS faced to PDF and we show how to adapt our initial algorithm to behave ’like’ a PDF schedule. We hope that such frame work could help multi-threaded or multi-core architect to rely on well founded mathematical results to build appropriate hardware controling the scheduling of threads or for implementing software schedulers.

National audience; We study, in this work, the load balancing of sort algorithm executed on a two cluster grid. Our solution is based on data partitioning. We use mainly geometrical interpretations to find out the optimal partition that reduces both communication and computing times in an heterogeneous context.

International audience; The aim of the paper is to introduce techniques in order to tune sequential in-core sorting algorithms in the frameworks of two applications. The first application is parallel sorting when the processor speeds are not identical in the parallel system. The second application is the Zeta-Data Project [M. Koskas, A hierarchical database management algorithm, in: Annales 67 du Lamsade, vol. 2, 2004, pp. 277–317. [9]] whose aim is to develop novel algorithms for databases issues. About 50% of the work done in building indexes is devoted to sorting sets of integers. We develop and compare algorithms built to sort with equal keys. Algorithms are variations of the 3Way-Quicksort of Sedgewick. In order to observe performances and to fully exploit functional units in processors, and also in order to optimize the use of the memory system and the different functional units, we use hardware performance counters that are available on most modern microprocessors. We also develop analytical results for one of our algorithms and compare expected results with the measures. For the two applications, we show, through fine experiments on an Athlon processor (a three-way superscalar x86 processor), that L1 data cache misses are not the central problem, but a subtle proportion of independent retired instructions should be advised to get performance for in-core sorting.

International audience; In this paper, we describe in detail a novel SQL service based on radix tree data structures and we show how to multithread the service in order to execute it on distributed platforms. The SQL service is currently developed in the context of SMP platforms but should be deployed in the future on grid platforms. The development of the SQL service is part of the Grid Explorer project. The project (French part) aims at building a grid emulator to study the behavior of grids. One need in the project is for a database software to store experimental conditions and to analyze traces of execution (for instance, to find in "real time" frequent episodes for the CPU load metric in order to predict the future state of the grid). We plan to use our SQL service on an SMP platform for this purpose.

International audience; The aim of the paper is to introduce general techniques in order to optimize the parallel execution time of sorting on a distributed architectures with processors of various speeds. Such an application requires a partitioning step. For uniformly related processors (processors speeds are related by a constant factor), we develop a constant time technique for mastering processor load and execution time in an heterogeneous environment and also a technique to deal with unknown cost functions. For non uniformly related processors, we use a technique based on dynamic programming. Most of the time, the solutions are in O(p) (p is the number of processors), independent of the problem size n. Consequently, there is a small overhead regarding the problem we deal with but it is inherently limited by the knowing of time complexity of the portion of code following the partitioning.

Large scale distributed computing infrastructure captures the use of high number of nodes, poor communication performance and continously varying resources that are not available at any time. In this paper, we focus on the different tools available for mining traces of the activities of such aforementioned architecture. We propose new techniques for fast management of a frequent itemset mining parallel algorithm. The technique allow us to exhibit statistical results about the activity of more that one hundred PCs connected to the web.

We derive a parallel solution to the problem of finding the longest increasing subsequence in a finite sequence of numbers. We first describe a sequential solution with time complexity O(n log n) and space complexity O(n). Secondly, we show how a parallel solution can be obtained using a partially pipelined linear modular systolic array, with time complexity O(n). >

In this thesis, we present our research work in the field of high performance computing in fluid mechanics (CFD)for cluster and cloud architectures. In general, we propose to develop an efficient solver, called ADAPT, for problemsolving of CFDs in a classic view corresponding to developments in MPI and in a view that leads us to representADAPT as a graph of tasks intended to be ordered on a cloud computing platform.As a first contribution, we propose a parallelization of the diffusion-convection equation coupled to a linear systemin 2D and 3D using MPI. A two-level parallelization is used in our implementation to take advantage of the currentdistributed multicore machines. A balanced distribution of the computational load is obtained by using the decompositionof the domain using METIS, as well as a relevant resolution of our very large linear system using the parallelsolver MUMPS (Massive Parallel MUltifrontal Solver).Our second contribution illustrates how to imagine the ADAPT framework, as depicted in the first contribution, asa Service. We transform the framework (in fact, a part of the framework) as a DAG (Direct Acyclic Graph) in orderto see it as a scientific workflow. Then we introduce new policies inside the RedisDG workflow engine, in order toschedule tasks of the DAG, opportunistically. We introduce into RedisDG the possibility to work with dynamic workers(they can leave or enter into the computing system as they want) and a multi-criteria approach to decide on the“best” worker to choose to execute a task. Experiments are conducted on, Dans cette thèse, nous présentons notre travail de recherche dans le domaine du calcul haute performance en mécaniquedes fluides (CFD) pour architectures de type cluster et cloud. De manière générale, nous nous proposonsde développer un solveur efficace, appelé ADAPT, pour la résolution de problèmes de CFD selon une vue classiquecorrespondant à des développements en MPI et selon une vue qui nous amène à représenter ADAPT comme un graphede tâches destinées à être ordonnancées sur une plateforme de type cloud computing.Comme première contribution, nous proposons une parallélisation de l’équation de diffusion-convection couplée àun système linéaire en 2D et en 3D à l’aide de MPI. Une parallélisation à deux niveaux est utilisée dans notre implémentationpour exploiter au mieux les capacités des machines multi-coeurs. Nous obtenons une distribution équilibréede la charge de calcul en utilisant la décomposition du domaine à l’aide de METIS, ainsi qu’une résolution pertinentede notre système linéaire creux de très grande taille en utilisant le solveur parallèle MUMPS (Solveur MUltifrontalMassivement Parallèle).Notre deuxième contribution illustre comment imaginer la plateforme ADAPT, telle que représentée dans la premièrecontribution, comme un service. Nous transformons le framework ADAPT (en fait, une partie du framework)en DAG (Direct Acyclic Graph) pour le voir comme un workflow scientifique. Ensuite, nous introduisons de nouvellespolitiques à l’intérieur du moteur de workflow RedisDG, afin de planifier les tâches du DAG, de manière opportuniste.Nous introduisons dans RedisDG la possibilité de travailler avec des machines dynamiques (elles peuvent quitter ouentrer dans le système de calcul comme elles veulent) et une approche multi-critères pour décider de la “meilleure”machine à choisir afin d’exécuter une tâche. Des expériences sont menées sur le workflow ADAPT pour illustrerl’efficacité de l’ordonnancement et des décisions d’ordonnancement dans le nouveau RedisDG.

International audience

International audience

GPC 2007 provided a high-profile, leading-edge forum for researchers and developers from industry and academia to report on the latest scientific and technical advances, discuss and debate the major issues, and showcase the latest systems in merging grid computing and the pervasive computing field. This year, a total of 217 high-quality papers were submitted by researchers and practitioners from about 20 countries. All the submissions were rigorously reviewed by the Program Committee members. To ensure fairness and the quality of the papers, we put a number of measures in place. For example, each paper was assigned at least one reviewer from Australia, one reviewer from America, and one reviewer from Europe. Based on the originality, significance, correctness, relevance, and clarity of presentation, 56 submissions were selected as regular papers and 12 were selected as short papers. The acceptation rate is 32%. Also, the authors of accepted papers were required to submit a read-me file along with the camera-ready version of their paper explaining how the reviewers comments were taken into account in the final version of their paper. The publication Co-chairs, Lucian Finta (Paris XIII, France) and Jemal H. Abawajy (Deakin University, Australia), painstakingly went through each read-me file and reviewers' comments to ensure that the comments were indeed incorporated into the final version of the papers. Only those papers that included reviewers' comments were finally accepted for inclusion in the proceedings. Undoubtedly, Lucian and Jemal had to work long hours to meet the tight deadline, which is greatly appreciated. The overall outcome of the revision process is a selection of papers that showcase the very best of grid and pervasive computing technology today. After the conference, the proceedings editors selected and recommended some highquality papers from the GPC 2007 conference to be published in special issues of international journals. Special thanks go to Jemal H. Abawajy for liasing with the chief editors of the journals. The GPC 2007 program included presentations by accepted paper authors, keynote speeches, and a special round table on “Pervasive Grid.” The special round table was organized by Lionel Brunie, Manish Parashar, and Jean-Marc Pierson. We thank them for this initiative. We allocated a slot of 30 minutes for each paper presentation so that the participants had plenty of time for questions and answers.We were also delighted to be able to welcome three well-known international researchers, Thierry Priol (France) representing the European CoreGrid initiative, Minyi Guo, Professor at the School of Computer Science and Engineering, University of Aizu (Japan), and Laurence T. Yang representing St. Francis Xavier University (Canada), who delivered the keynote speeches.