Mémoires de Fin d’Etudes
Etablissement
Université de M’Sila - Mohamed Boudiaf
Affiliation
Institut d’Informatique
Auteur
GUERNA, Abderrahim
Directeur de thèse
GASMI Abdelkader (Maitre de conférence)
Filière
Informatique
Diplôme
Magister
Titre
APPLICATION D’UNE APPROCHE BIO-INSPIREE AU PROBLEME D’ORDONNANCEMENT DES INSTRUCTIONS
Mots clés
Mots-clés :Optimisation combinatoire discrète; Approche bio-inspirée; Algorithme de Colonies de fourmis; Métaheuristiques; Ordonnancement des instructions الكلمات المفتاحية : تحسين التركيبي المتقطع، الطرقالموجهة المستوحاة من النهج الحيوي، خوارزميات مستعمرات النمل ، جدولة التعليمات، الجدولة باستعمال القائمة ، MAX - MIN نظام النمل Keywords: Discrete combinative optimization ,Approaches bio-inspired ,Algorithm of colonies of ants,Instruction Scheduling, List Scheduling, MAX-MIN Ant System
Résumé
Résumé L’ordonnancement des instructions est une tâche importante pour affecter une application à unecollection d’unités de traitement. Un ordonnancement adéquat opérations, aide à exploiter pleinement la capacité du système.L’objectif est de réduire au minimum letemps deréponse, « latence », d’une application donnée ; en utilisant efficacement les ressources informatiques. Le problème d’ordonnancement des instructions est NP-difficile, ainsi les méthodes heuristiques efficaces sont nécessaires pour fournir une solution d’ordonnancement qualitative. Dans cette étude, nous essayons présenter un algorithme d’ordonnancement des instructions en utilisant une approche hybride, qui consiste à combiner le métaheuristique de système de fourmi Max-min avec l’ordonnancement par liste, où l’heuristique locale et globale sont dynamiquement assemblés dans l’application d’entrée d’une façon itérative. Par comparaisonde cet algorithme avec un certain nombre de différentes heuristiques d’ordonnancement, notre algorithme produit de meilleurs résultats sur tous les repères examinés avec une meilleure stabilité. En outre, par cette, le test génère, d’une façon optimale, tout en utilisant la formulation d’ILP, des résultats plus au moins rapprochés . ملخـــــــــــــص جدولة التعليمات البرمجية هي خطوة أساسية لرسم معالم تنفيذ البرامج على مستوى مجموعة وحدات المعالجة داخل الحاسوب الكومبيوتر. الجدولة العير ملائمة لتنفيذ التعليمات تودي حتما للاستغلال السيئ لوحدات المعالجة. المواصفات السلوكية وتنتج جدولا زمنيا للتعليمات على مجموعة من وحدات المعالجة. والهدف من ذلك هو تقليل وقت الانتهاء من تطبيق معين مع استخدام فعال للموارد الحاسوبية.تصنف مشكلة جدولة التعليمات البرمجية في الصنف الحاد الصعوبة ، وبالتالي اللجوء إلى الطرق التقريبية فعال بشكل جيد من أجل إعطاء حلول ذات نوعية جيدة . في هذه المذكرة، فإننا نقدم رؤية خوارزمية لجدولة التعليمات باستخدام MAX - MIN للنظام المشتق من نظام مجمعات النمل ، يستخدم نهجا هجينا عن طريق الجمع بين نظام مجمعات النمل مع نظام الجدولة باستخدام القائمة ، حيث يتم تعديلها بشكل حيوي يمزج بين المناهج التجريبية المحلية والكلية تطبيق فيها المدخلات بطريقة تكرارية. ، مقارنة هذه الخوارزمية ولد نتائج أفضل على كل المقاييس مع أفضل اختبار للاستقرار. الكلمات المفتاحية : تحسين التركيبي المتقطع، الطرقالموجهة المستوحاة من النهج الحيوي، خوارزميات مستعمرات النمل ، جدولة التعليمات، الجدولة باستعمال القائمة ، MAX - MIN نظام النمل ABSTRACT Instruction scheduling is a fundamental step for mapping an application to a computational device. It takes a behavioral application specification and produces a schedule for the instructions onto a collection of processing units. The objective is to minimize the completion time of the given application while effectively utilizing the computational resources. The instruction scheduling problem is NP-hard, thus effective heuristic methods are necessary to provide a qualitative scheduling solution. In this paper, we present a novel instruction scheduling algorithm using MAX-MIN Ant System Optimization approach. The algorithm utilizes a unique hybrid approach by combining the ant system meta-heuristic with list scheduling, where the local and global heuristics are dynamically adjusted to the input application in an iterative manner. Compared with a number of different list scheduling heuristics, our algorithm generates better results over all the tested benchmarks with better stability. Furthermore, by solving the test samples optimally using ILP formulation, we show that our algorithm consistently achieves a near optimal solution. Keywords: Discrete combinative optimization ,Approaches bio-inspired ,Algorithm of colonies of ants,Instruction Scheduling, List Scheduling, MAX-MIN Ant System
Date de soutenance
28/06/2012
Pagination
94 p
Illusatration
Relié
Format
30 cm
Notes
une copie papier + un ccdrom
Statut
Soutenue