Prejsť na obsah
dizertácie

Dovoľujeme si oznámiť, že dňa

2. 10. 2007 o 11.00 hod.

sa uskutoční na Fakulte informatiky a informačných technológií STU v Bratislave
v miestnosti D 220 obhajoba dizertačnej práce

PaedDr. Vladimíra Siládiho

Názov dizertačnej práce:   Paralelný hybridný genetický algoritmus na optimalizáciu neregulárnych topológií prepojovacích sietí
Odbor:   25-21-9 Počítačové prostriedky a systémy

Školiteľ:

    prof. Ing. Ján Kolenička, PhD., Fakulta prírodných vied UMB v Banskej Bystrici

Oponenti dizertačnej práce:

    prof. Ing. Milan Kolesár, PhD., Fakulta informatiky a informačných technológií STU v Bratislave
    doc. Ing. Vlastimil Jáneš, CSc., Dopravná fakulta ČVUT v Prahe
    doc. Ing. František Zbořil, CSc., Fakulta informačných technológií VUT v Brne

Abstrakt:

    Úlohy riešené na multipočítačových systémoch majú vysoké nároky na globálnu komunikáciu medzi procesormi, ktorú určuje topológia prepojovcej siete. Komunikačný čas závisí od počtu liniek, ktoré musí správa prekonať. Z tohto hľadiska sa ukazujú byť vhodnými neregulárne statické prepojovacie siete. Optimalizácia neregulárnych topológií je spojená s optimalizáciou grafov, kde optimalizačnými kritériami sú minimálny priemer grafu a minimálna priemerná vzdialenosť vrcholov v grafe. Optimálnymi grafmi sú Moorové grafy, ktoré existujú len pre určitý stupeň vrcholov, priemer grafu a počet uzlov v grafe. Z Moorovho ohraničenia je možné odvodiť teoretické limity oboch ukazovateľov, ku ktorým sa je možné optimalizáciou priblížiť.

    V dizertačnej práci je opísaný paralelný hybridný genetický algoritmus na optimalizáciu neregulárnych topológií prepojovacích sietí multipočítačov, ktorý využíva prirodzený paralelizmus genetických algoritmov. Genetický algoritmus obsahuje PMX operátor kríženia a operátor mutácie založený na párových zámenách. Genetický algoritmus nachádza miesta blízke optimu. Na nájdenie optima slúži heuristický algoritmus párových zámen. Paralelizácia genetických operácií je urobená pomocou direktív OpenMP.

     

    Problems solved on multicomputer systems have large demands on global communication between processors, which is determined by interconnection network. The time spent on communication depends on the number of links a message has to traverse. In this respect, irregular static interconnection networks seem to be suitable. The optimisation of the irregular topologies is connected with the optimisation of graphs. The optimisation measures are the diameter and the average distance of the vertices. The optimal graphs are Moore graphs which are available only for some cases of the degree of the vertices, the diameter of the graph and the number of the vertices in the graph. From the Moore bound, theoretical limits of the both optimisation ratios which can be approximated can be derived.

    In the dissertation, we present the parallel hybrid genetic algorithm on optimisation of irregular topologies of interconnection networks that uses natural parallelism of genetic algorithms. The genetic algorithm contains the PMX crossover operator and the random swap links mutation operator. The genetic algorithm finds localities of optimal solution. The heuristic algorithm is based on the idea of the pair wise exchange. The parallelization is made with the OpenMP directives.

Dizertačná práca je k nahliadnutiu na Študijnom oddelení FIIT STU.