Αλγόριθμοι Για Εξισορρόπηση Πολυδιάστατου Φορτίου

Abstract

Σε όλα τα μοντέρνα συστήματα βάσεων δεδομένων, οι πληροφορίες διαμοιράζονται σε πολλούς υπολογιστές ή επεξεργαστές, και οι υπολογισμοί γίνονται παράλληλα με την ελάχιστη δυνατή επικοινωνία μεταξύ αυτών. Για το σκοπό αυτό,έχουν αναπτυχθεί πολλά μοντέλα παράλληλου υπολογισμού, καθώς και πολλοί αλγόριθμοι διαμοιρασμού δεδομένων σε επεξεργαστές. Ο συνήθης στόχος των αλγορίθμων αυτών είναι να ελαχιστοποιήσουν το φορτίο που θα λάβει ο υπολογιστήςμε τα περισσότερα δεδομένα, καθώς ο χρόνος ανταπόκρισης του συστήματος είναι αντιστρόφως ανάλογος του φόρτου εργασίας των επεξεργαστών του.Στην εργασία αυτή βασιζόμαστε σε ένα Μαζικό και Παράλληλο Υπολογιστικό μοντέλο, MPC, με σκοπό τον υπολογισμό queries χωρίς ενδιάμεση επικοινωνία των υπολογιστών μεταξύ τους. Ενδιαφερόμαστε για τη μελέτη αλγορίθμων εξισορρόπησης πολυδιάστατων φορτίων, οι οποίοι γενικεύουν τους κλασσικούς αλγόριθμους εξισορρόπησης, αφού αντί να έχουμε βαθμωτά μεγέθη να διαμοιράσουμε, έχουμε διανυσματικά. Παρουσιάζουμε τα πρόσφατα αποτελέσματα τόσο σε deterministic όσο και σε randomized αλγορίθμους και μελετάμε την απόδοση τους σε σχέση με τη μορφή που έχουν τα δεδομένα εισόδου και το query που πρέπει να υπολογίσουν. Στη συνέχεια αποδεικνύουμε ένα νέο αποτέλεσμα για έναν από τους αλγόριθμους αυτούς, εξασφαλίζοντας τη σχεδόν βέλτιστη κατανομή των δεδομένων, σε περιπτώσεις που προηγουμένως δεν είχαν λυθεί.