Κατανεμημένοι αλγόριθμοι διάχυσης για το πρόβλημα της εξισορρόπησης φορτίου

Abstract

The aim of the PhD thesis is the design and the analysis of new diffusion methods for the load balancing problem in order to accelerate their rate of convergence. In particular, two new diffusion methods have been developed, the (Extrapolated) Average Diffusion method and the Generalized Diffusion method. The study of the convergence for the two methods revealed the following results: the conditions of convergence are simpler and "optimum" values for the involved diffusion parameters were determined. It is proposed a new methodology, which is based on Fourier analysis, in order to determine good approximations for the diffusion parameters. This analysis have been applied for two networks topologies, ring and 2d-torous, targeting more general networks graphs such that 2d-regular. Moreover, accelerated techniques have been applied in order to increase the rate of convergence of the diffusion method by an order of magnitude.

Σκοπός της παρούσας διδακτορικής διατριβής είναι ο σχεδιασμός και η ανάλυση νέων μεθόδων διάχυσης για το πρόβλημα της εξισορρόπησης φορτίου με στόχο την αύξηση της ταχύτητας σύγκλισής τους. Πιο συγκεκριμένα αναπτύχθηκαν δύο νέες μέθοδοι διάχυσης, η (Επιταχυντική) μέθοδος της Μέσης Διάχυσης και η Γενικευμένη μέθοδος της Διάχυσης. Η μελέτη της σύγκλισης των δύο αυτών μεθόδων είχε σαν αποτέλεσμα, την παραγωγή απλούστερων συνθηκών σύγκλισης και τον προσδιορισμό βέλτιστων τιμών των υπεισερχομένων παραμέτρων διάχυσης. Προτείνεται μία νέα μεθοδολογία, η οποία βασίζεται στην ανάλυση Fourier, προκειμένου να προσδιορισθούν καλές (πλησίον των βέλτιστων) προσεγγίσεις των τιμών των παραμέτρων διάχυσης. Η εν λόγω ανάλυση εφαρμόστηκε στις τοπολογίες δικτύου, δακτυλίου και διδιάστατους πόρους με στόχο την εφαρμογή της σε πιο γενικευμένες τοπολογίες, όπως αυτές των 2d-κανονικών γράφων δικτύου. Επιπλέον, εφαρμόστηκαν επιταχυντικές τεχνικές στην κλασική μέθοδο της διάχυσης και αυξήθηκε η ταχύτητα σύγκλισής της κατά μία τάξη μεγέθους.