Πρόβλεψη Κλιμάκωσης Παράλληλων Περιοχών Σε Πολυπύρηνες Αρχιτεκτονικές

Abstract

Η παρούσα διπλωματική έγκειται στο ευρύτερο πεδίο των Παράλληλων Συστημάτων και εστιάζει στη μελέτη των χαρακτηριστικών των παράλληλων περιοχών και την χρησιμότητά τους σε μια στατική ανάλυση, η οποία σε συνδυασμό με πληροφορία χρόνου εκτέλεσης, μπορεί να προσφέρει μια μικρού κόστους πρόβλεψη της κλιμάκωσης της παράλληλης περιοχής, δεδομένων περισσότερων υπολογιστικών πυρήνων, με σκοπό την αποδοτικότερη χρονοδρομολόγηση των παράλληλων προγραμμάτων, δρομολογώντας παράλληλες περιοχές ξεχωριστά, παρά ολόκληρα παράλληλα προγράμματα. Εστιάζουμε σε προγράμματα που έχουν παραλληλοποιηθεί με την προγραμματιστική διεπαφή OpenMP και σε κανονικές δομές, συγκεκριμένα σε δομές parallel-for.Αρχικά, υποστηρίζουμε την ιδέα της χρονοδρομολόγησης και κατανομής πόρων σε επίπεδο παράλληλων περιοχών κι όχι σε επίπεδο προγραμμάτων, πετυχαίνοντας έτσι επιτάχυνση (όπου αυτό είναι εφικτό) και κάνοντας καλύτερη χρήση των πόρων. Προς αυτή την κατεύθυνση, παρουσιάζουμε πειραματικά αποτελέσματα που αναδεικνύουν τις διαφορές που μπορούν να έχουν παράλληλες περιοχές του ίδιου προγράμματος.Κατόπιν, μελετούμε τα χαρακτηριστικά απλών παράλληλων περιοχών αποσκοπώντας στην εύρεση εκείνων που μπορούν να χρησιμοποιηθούν για να προβλέψουμε τη συμπεριφορά της παράλληλης περιοχής και παραθέτουμε τους περιορισμούς μιας τέτοιας ανάλυσης. Παρουσιάζουμε ένα μοντέλο, το οποίο λαμβάνει υπόψιν το λόγο των υπολογισμών προς τις προσβάσεις μνήμης, χρησιμοποιώντας μια στατική ανάλυση του πηγαίου κώδικα του προγράμματος, σε συνδυασμό με πληροφορία κατά το χρόνο εκτέλεσης του προγράμματος.Επιπλέον, παρουσιάζουμε ένα απλό μοντέλο μνήμης, που χρησιμοποιείται για να εκφράσει την επίδραση που έχει η μνήμη στην κλιμάκωση ενός παράλληλου προγράμματος, το οποίο σε συνδυασμό με την προηγούμενη στατική ανάλυση μπορεί να παράξει μια ελαφριά και συνεπή πρόβλεψη για τη δυνατότητα επιτάχυνσης της παράλληλης περιοχής, ως μια "συμβουλή" προς το χρονοδρομολογητή.Τέλος, παρουσιάζουμε μια αρχική υλοποίηση που χρησιμοποιεί το μοντέλο αυτό και επιδεικνύουμε την αποτελεσματικότητα της παρούσας ανάλυσης, εφαρμόζοντάς την σε παράλληλες περιοχές από τις σουίτες προγραμμάτων NAS Parallel Benchmark Suite (NPB) και Polyhedral Benchmark Suite (PolyBench), συγκρίνοντας την προβλεπόμενη συμπεριφορά με πειραματικά αποτελέσματα από έναν 8-πύρηνο κόμβο της οικογενείας Clovertown και έναν 24-πύρηνο κόμβο της οικογενείας Dunnington.