Retour au site du LAAS-CNRS

Laboratoire d’analyse et d’architecture des systèmes
Choisir la langue : FR | EN

4documents trouvés

17017
10/01/2017

Plateforme de calcul parallèle "Design for Demise"

B.PLAZOLLES

CDA

Doctorat : Université de Toulouse III - Paul Sabatier, 10 Janvier 2017, 202p., Président: T.GAYRAUD, Rapporteurs: D.DEFOUR, R.MOLINA, Examinateurs: M.BALAT-PICHELIN, P.COCQUEREZ, Directeurs de thèse: D.EL BAZ, M.SPEL , N° 17017

Non diffusable

138893
12583
05/10/2012

Contribution à la résolution de problèmes d’optimisation combinatoire : méthodes séquentielles et parallèles

M.LALAMI

CDA

Doctorat : 5 Octobre 2012, 146p., Président: B.DAHHOU, Rapporteurs: M.HIFI, N.MELAB, Examinateur: I.KACEM, Directeurs de thèse: D.EL BAZ, M.ELKIHEL , N° 12583

Lien : http://tel.archives-ouvertes.fr/tel-00748546

Diffusable

Plus d'informations

Abstract

Combinatorial optimization problems are difficult problems whose solution by exact methods can be time consuming or not realistic. The use of heuristics permits one to obtain good quality solutions in a reasonable time. Heuristics are also very useful for the development of exact methods based on branch and bound techniques. The first part of this thesis concerns the Multiple Knapsack Problem (MKP). We propose here a heuristic called RCH which yields a good solution for the MKP problem. This approach is compared to the MTHM heuristic and CPLEX solver. The second part of this thesis concerns parallel implementation of an exact method for solving combinatorial optimization problems like knapsack problems on GPU architecture. The parallel implementation of the Branch and Bound method via CUDA for knapsack problems is proposed. Experimental results show a speedup of 51 for difficult problems using a Nvidia Tesla C2050 (448 cores). A CPU-GPU implementation of the simplex method for solving linear programming problems is also proposed. This implementation offers a speedup around 12.7 on a Tesla C2050 board. Finally, we propose a multi-GPU implementation of the simplex algorithm via CUDA. An efficiency of 96.5% is obtained when passing from one GPU to two GPUs.

Résumé

Les problèmes d'optimisation combinatoire sont souvent des problèmes très difficiles dont la résolution par des méthodes exactes peut s'avérer très longue ou peu réaliste. L'utilisation de méthodes heuristiques permet d'obtenir des solutions de bonne qualité en un temps de résolution raisonnable. Les heuristiques sont aussi très utiles pour le développement de méthodes exactes fondées sur des techniques d'évaluation et de séparation. Nous nous sommes intéressés dans un premier temps à proposer une méthode heuristique pour le problème du sac à dos multiple MKP. L'approche proposée est comparée à l'heuristique MTHM et au solveur CPLEX. Dans un deuxième temps nous présentons la mise en œuvre parallèle d'une méthode exacte de résolution de problèmes d'optimisation combinatoire de type sac à dos sur architecture GPU. La mise en œuvre CPU-GPU de la méthode de Branch and Bound pour la résolution de problèmes de sac à dos a montré une accélération de 51 sur une carte graphique Nvidia Tesla C2050. Nous présentons aussi une mise en œuvre CPU-GPU de la méthode du Simplexe pour la résolution de problèmes de programmation linéaire. Cette dernière offre une accélération de 12.7 sur une carte graphique Nvidia Tesla C2050. Enfin, nous proposons une mise en œuvre multi-GPU de l'algorithme du Simplexe, mettant à contribution plusieurs cartes graphiques présentes dans une même machine (2 cartes Nvidia Tesla C2050 dans notre cas). Outre l'accélération obtenue par rapport à la mise en œuvre séquentielle de la méthode du Simplexe, une efficacité de 96.5 % est obtenue, en passant d'une carte à deux cartes graphiques.

Mots-Clés / Keywords
Optimisation combinatoire; Sac à dos; Calcul parallèle et distribué; Logistique; Calcul sur GPU; Calcul hybride; Combinatorial optimization; Knapsack; Parallel and distributed computing; Logistics; GPU computing; Hybrid computing;

128426
11649
16/11/2011

An environment for peer-to-peer high performance computing

T.T.NGUYEN

CDA

Doctorat : Institut National Polytechnique, Toulouse, 16 Novembre 2011, 140p., Président: J.BOURGEOIS, Rapporteurs: O.BEAUMONT, F.MAGOULES, Examinateurs: M.DIAZ, T.SAADI, Directeurs de thèse: D.EL BAZ , N° 11649

Lien : http://tel.archives-ouvertes.fr/tel-00657952/fr/

Diffusable

Plus d'informations

Résumé

Le concept de pair à pair (P2P) a connu récemment de grands développements dans les domaines du partage de fichiers, du streaming vidéo et des bases de données distribuées. Le développement du concept de parallélisme dans les architectures de microprocesseurs et les avancées en matière de réseaux à haut débit permettent d'envisager de nouvelles applications telles que le calcul intensif distribué. Cependant, la mise en oeuvre de ce nouveau type d'application sur des réseaux P2P pose de nombreux défis comme l'hétérogénéité des machines, le passage à l'échelle et la robustesse. Par ailleurs, les protocoles de transport existants comme TCP et UDP ne sont pas bien adaptés à ce nouveau type d'application. Ce mémoire de thèse a pour objectif de présenter un environnement décentralisé pour la mise en oeuvre de calculs intensifs sur des réseaux pair à pair. Nous nous intéressons à des applications dans les domaines de la simulation numérique et de l'optimisation qui font appel à des modèles de type parallélisme de tâches et qui sont résolues au moyen d'algorithmes itératifs distribués or parallèles. Contrairement aux solutions existantes, notre environnement permet des communications directes et fréquentes entre les pairs. L'environnement est conçu à partir d'un protocole de communication auto-adaptatif qui peut se reconfigurer en adoptant le mode de communication le plus approprié entre les pairs en fonction de choix algorithmiques relevant de la couche application ou d'éléments de contexte comme la topologie au niveau de la couche réseau. Nous présentons et analysons des résultats expérimentaux obtenus sur diverses plateformes comme GRID'5000 et PlanetLab pour le problème de l'obstacle et des problèmes non linéaires de flots dans les réseaux.

Abstract

The concept of peer to peer (P2P) has known great developments these years in the domains of file sharing, video streaming and distributed databases. Recent advances in microprocessors architecture and networks permit one to consider new applications like distributed high performance computing. However, the implementation of this new type of application on P2P networks gives raise to numerous challenges like heterogeneity, scalability and robustness. In addition, existing transport protocols like TCP and UDP are not well suited to this new type of application. This thesis aims at designing a decentralized and robust environment for the implementation of high performance computing applications on peer to peer networks. We are interested in applications in the domains of numerical simulation and optimization that rely on tasks parallel models and that are solved via parallel or distributed iterative algorithms. Unlike existing solutions, our environment allows frequent direct communications between peers. The environment is based on a self adaptive communication protocol that can reconfigure itself dynamically by choosing the most appropriate communication mode between any peers according to decisions concerning the scheme of computation that are made at the application level or elements of context at transport level, like topology. We present and analyze computational results obtained on several testeds like GRID'5000 and PlanetLab for the obstacle problem and nonlinear network flow problems.

Mots-Clés / Keywords
Peer to peer computing; Self-adaptive protocol; High performance computing; Fault tolerance; Parallel iterative algorithms; Calcul pair à pair; Protocol auto-adaptatif; Calcul haute performance; Tolérance aux fautes; Algorithmes iteratives prallèles;

125942
07804
14/12/2007

Contribution à la programmation en nombre entier

V.BOYER

MAC, CDA

Doctorat : Institut National des Sciences Appliquées, Toulouse, 14 Décembre 2007, 117p., Président: S.HANAFI, Rapporteurs: M.HIFI, G.PLATEAU, Directeurs de thèse: J.B.LASSERRE, D.EL BAZ, M.ELKIHEL , N° 07804

Lien : http://tel.archives-ouvertes.fr/tel-00280134/fr/

Diffusable

Plus d'informations

Abstract

The Multi-Knapsack Problem is a traditional problem of optimization belonging to the class of the NP-hard problems. This problem occurs in particular as a subproblem of many combinatorial optimization problems. Traditional methods, such as dynamic programming or branch-andbound, used for the exact solution have been treated abundantly in the literature. They have nevertheless weaknesses if they are used alone. The cooperative methods permit one to benefits from their specificities and to propose powerful heuristics or efficient exact methods. Heuristics approaches are proposed and compared with other heuristics from the literature. A cooperative method is compared with a branch-and-bound algorithm. Numerical tests were carried out on various difficult problems from the literature and on randomly generated problems. At last, we consider in particular two techniques in order to generate difficult problems. They are based on problems with equality constraints and the analysis of the Z transform of the knapsack problem.

Résumé

Le problème du sac à dos à plusieurs contraintes est un problème classique de l'optimisation appartenant à la classe des problèmes NP-difficiles. On le retrouve notamment sous la forme de sous-problème de nombreux problèmes d'optimisation combinatoire. Les méthodes classiques de résolution exacte telles que la programmation dynamique ou le branch-and-bound ont été traitées abondamment dans la littérature. Elles présentent n´eanmoins des faiblesses si elles sont utilisées telles quelles, d'où l'idée de faire coopérer ces méthodes en tirant profit de leurs spécificités afin de proposer soit des méthodes heuristiques performantes, soit des méthodes exactes plus efficaces. Les approches heuristiques que nous proposons sont comparées à d'autres heuristiques de la littérature. Notre méthode coopérative est, quant à elle, comparée à un algorithme de branchand- bound. L'ensemble de ces tests numériques ont été menés pour diverses instances plus ou moins difficiles de la littérature ainsi que sur des instances engendrées aléatoirement. Enfin, nous proposons deux techniques pour engendrer des problèmes difficiles. Ces dernières sont basées sur des problèmes en contraintes égalités et sur l'analyse de la transformée en Z du sac à dos.

Mots-Clés / Keywords
Optimisation combinatoire; Problème du sac à dos multidimensionnel; Méthodes coopératives; Heuristiques; Combinatorial optimization; Multi-knapsack problem; Cooperative methods; Heuristics;

113752
Les informations recueillies font l’objet d’un traitement informatique destiné à des statistiques d'utilisation du formulaire de recherche dans la base de données des publications scientifiques. Les destinataires des données sont : le service de documentation du LAAS.Conformément à la loi « informatique et libertés » du 6 janvier 1978 modifiée en 2004, vous bénéficiez d’un droit d’accès et de rectification aux informations qui vous concernent, que vous pouvez exercer en vous adressant à
Pour recevoir une copie des documents, contacter doc@laas.fr en mentionnant le n° de rapport LAAS et votre adresse postale. Signalez tout problème de dysfonctionnement à sysadmin@laas.fr. http://www.laas.fr/pulman/pulman-isens/web/app.php/