Contribution à l'algorithmique non numérique parallèle : parallélisations de méthodes de recherche arborescentes / Bernard Mans

Auteur principal : Mans, Bernard, AuteurAuteur secondaire collectivité : Université Pierre et Marie Curie - Paris 6, Etablissement de soutenanceType de document : ThèseLangue : français.Pays: France.Éditeur : [S.l.] : [s.n.], 1992Description : 1 vol. (204 p.) ; 30 cmBibliographie : Bibliogr. p. 194-196.Sujet MSC : 68W10, Algorithms in computer science, Parallel algorithms
90C27, Mathematical programming, Combinatorial optimization
65Kxx, Numerical analysis - Numerical methods for mathematical programming, optimization and variational techniques
68W15, Algorithms in computer science, Distributed algorithms
97-02, Research exposition (monographs, survey articles) pertaining to mathematics education
Note de thèse: Thèse de doctorat, informatique, 1992, université paris VI Item type: Thèse
Tags from this library: No tags from this library for this title. Log in to add tags.
Holdings
Current library Call number Status Date due Barcode
CMI
Salle S
Thèses MAN (Browse shelf(Opens below)) Available 01300-01

Bibliogr. p. 194-196

Thèse de doctorat informatique 1992 université paris VI

Le but de cette these est d'etudier la parallelisation des methodes de resolution des problemes d'optimisation combinatoire reputes np-difficiles: les problemes de recherche arborescente par separation et evaluation ou branch and bound. Elle est composee de trois parties complementaires. Dans la premiere partie, nous presentons les differentes definitions essentielles au branch and bound. Le parallelisme intrinseque a cette methode est degage et un modele d'evaluation de performances des branch and bound paralleles est introduit, (chapitre 1). Les differents phenomenes d'anomalies d'acceleration et la limite des solutions connues sont presentes dans le chapitre 2. Le chapitre 3 pose les problemes classiques souleves par l'implementation parallele. La deuxieme partie s'attache a proposer des solutions a des problemes primordiaux: 1) les anomalies d'accelerations, (chapitre 5); des bornes serrees ainsi qu'une propriete de predisposition aux anomalies sont introduites et permettent des choix precis parmi differentes regles, 2) la granularite du travail alloue aux processeurs, (chapitre 6); les gains et surcouts mis en evidence pour un procede de separation polytomique permettent de prouver son interet, 3) l'acces aux donnees partagees, (chapitre 7); des structures de donnees bien adaptees au branch and bound sont etudiees et comparees; pour resoudre la contention d'acces a la memoire, les operations de bases sur ces structures sont rendues concurrentes; leurs performances sont conservees et le surcout d'implementation reduit par une methode de marquage, 4) l'equilibrage de charge des reseaux d'interconnexion de processeurs, (chapitre 8); une nouvelle fonction de charge et une regle de decision d'equilibrage s'adaptant d'elle-meme a l'evolution de la resolution sont developpees et conduisent a la description d'un branch and bound distribue. Enfin, dans la troisieme partie, nous testons ces solutions en concevant des branch and bound paralleles efficaces pour deux problemes reputes difficiles: 1) l'affectation quadratique, chapitre 9, ou les problemes de granularite et d'acces aux donnees sont importants, 2) le sac-a-dos multidimensionnel, chapitre 10, ou l'interet d'une separation polytomique pour la granularite se confirme

There are no comments on this title.

to post a comment.