Contribution à l'algorithmique non numérique parallèle : parallélisations de méthodes de recherche arborescentes / Bernard Mans
Type 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 algorithms90C27, 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 educationNote de thèse: Thèse de doctorat, informatique, 1992, université paris VI Item type:

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.