Μελέτη Αλγορίθμων Εκτέλεσης Και Χρονοδρομολόγησης Παράλληλων Εργασιών

Abstract

Μια διαδεδομένη τεχνική για την αξιοποίηση πολυεπεξεργαστικών συστημάτων είναι η δόμηση μιας εφαρμογής σε ανεξάρτητες εργασίες που μπορούν να εκτελούνται ταυτόχρονα, γνωστή ως multithreading. Τα περισσότερα εργαλεία παράλληλου προγραμματισμού φροντίζουν αυτές οι εργασίες να κατανέμονται και να εκτελούνται στους επεξεργαστές αυτόματα, χωρίς την παρέμβαση του προγραμματιστή. Αυτό κάνει τον παράλληλο προγραμματισμό αφενός πιο εύκολο, καθώς ο προγραμματιστής ασχολείται μόνο με τον τρόπο που θα δομήσει την εφαρμογή του σε ανεξάρτητες εργασίες, και αφετέρου πιο αποδοτικό, αφού οι εργασίες δρομολογούνται από ένα σύστημα που εγγυημένα δουλεύει σωστά και γρήγορα.Στόχος αυτής της εργασίας είναι η μελέτη του τρόπου που μπορούμε να διαχειριστούμε παράλληλες εργασίες -πώς να τις δημιουργήσουμε, να τις τερματίσουμε και να τις συγχρονίσουμε μεταξύ τους- καθώς και το πώς μπορούν να δρομολογηθούν αυτές σε ένα πλήθος επεξεργαστών. Η μελέτη γίνεται σε εργαλεία παράλληλου προγραμματισμού που παρέχουν τέτοιες δυνατότητες, κυρίως τα Posix Threads και η Cilk. Κατόπιν, αναλύουμε δυο κύριες τεχνικές χρονοδρομολόγησης παράλληλων εργασιών, το work sharing και το work stealing. Μελετούμε αλγορίθμους που βασίζονται σε αυτές τις φιλοσοφίες και την επίδοση που έχουν βάσει θεωρητικών μοντέλων.Τέλος, για εκπαιδευτικούς λόγους, εμπνεόμενοι από τα εργαλεία που εξετάστηκαν, υλοποιούμε σε γλώσσα C μια βιβλιοθήκη διαχείρισης tasks και ένα δρομολογητή. Ο δρομολογητής εκτελεί απλοποιημένες εκδοχές αλγορίθμων work sharing και work stealing.