Mémoires de Fin d’Etudes
Etablissement
Université de M’Sila - Mohamed Boudiaf
Affiliation
Institut d’Informatique
Auteur
ZAKARIA, Zendaoui
Directeur de thèse
Pr. Brahim BOUDERAH (Professeur)
Filière
Informatique
Diplôme
Magister
Titre
CONCEPTION D’ALGORITHMES PARALLELES POUR CERTAINS PROBLEMES D’OPTIMISATION تصميم خوارزميات متوازية لبعض مشاكل التحسين. Design of parallel algorithms for some problems of optimization.
Mots clés
Mots clés : Optimisation combinatoire, séparation et évaluation, parallélisme, grappe. الكلمات المفتاحية: الأمثلية الاندماجية، الفصل والتقييم، المتوازي، مجموعة أجهزة كمبيوتر.
Résumé
Résumé Le but du présent travail consiste à proposer une conception d’une bibliothèque d’algorithmes parallèles. Cette bibliothèque est utilisée pour implémenter des solveurs pour des problèmes d’optimisation combinatoire sur des machines parallèles et séquentielles. Cette bibliothèque rend la puissance des ordinateurs parallèles utilisable pour l’optimisation combinatoire. Elle fournit un ensemble d’algorithme parallèle comme l’algorithme de séparation et évaluation et l’algorithme de retour-arrière, et elle est conçue pour être facilement étendu par d’autres algorithmes. Ces algorithmes offerts masquent la complexité du parallélisme au programmeur d’application. Notre conception s’est concentrée sur les algorithmes de recherche arborescente, et plus précisément sur l’algorithme de séparation et évaluation, ainsi que sur le passage de message des ordinateurs à mémoire distribuée. Enfin, pour tester notre bibliothèque et mesurer ses performances, nous avons résolu des problèmes de référence d’optimisation combinatoire. Ces références sont des instances du problème d’affectation quadratique. ملخص : الغرض من هذا العمل هو اقتراح تصميم مكتبة خوارزميات متوازية. يتم استخدام هذه المكتبة لتنفيذ حل لمشاكل الأمثلية الاندماجية على الأجهزة المتوازية والتسلسلية. هذه المكتبة تمكن من استخدام أجهزة الكمبيوتر المتوازية في مجال الأمثلية الاندماجية. أنها توفر مجموعة من الخوارزميات المتوازية مثل خوارزم Branch-and-Bound (الفصل والتقييم) و خوارزم Backtrack (التراجعي) ، و يمكن تمديدها بسهولة بزيادة خوارزميات أخرى. هذه الخوارزميات الموفرة تحجب تعقيدات التوازي لمبرمج التطبيق. ركز تصميمنا على خوارزميات البحث الشجرية، و بالتحديد على خوارزم الفصل والتقييم، وكذلك تمرير الرسالة على أجهزة الكمبيوتر ذات الذاكرة الموزعة. وأخيراً، لاختبار مكتبتنا وقياس أدائها، لقد تمكنا من حل مشاكل مرجعية تتمثل في أمثلة من مشكل التوزيع الرباعي. Abstract The aim of this work is to propose a design of a framework of parallel algorithms. This framework is used to implement solvers for combinatorial optimization problems on parallel and sequential machines. This framework renders the power of parallel computers usable for combinatorial optimization. It provides a set of parallel algorithms as Branch-and-Bound and Backtrack and it’s designed to be easily extended by other algorithms. These algorithms hide the complexity of parallelism from the application programmer. Our design was focused on the tree search algorithms, specifically on Branch-and-Bound, as well as on message passing on distributed memory computers. Finally, to test our framework and measure its performance, we have solved benchmark combinatorial optimization problems. These benchmarks are quadratic assignment instances. Key words: Combinatorial optimization, Branch-and-Bound, parallelism, cluster.
Date de soutenance
02/07/2012
Pagination
131 p
Illusatration
Relié
Format
30 cm
Notes
une copierpapier +un cdrom
Statut
Soutenue