Optimization Techniques For Task-based Parallel Programming Models

Abstract

Ένα από τα πιο απαιτητικά προβλήματα στα σύγχρονα παράλληλα υπολογιστικά συστήματα είναι η εκμετάλλευση του μεγάλου αριθμού των νημάτων/πυρήνων που προσφέρει το σύγχρονο υλικό, με σκοπό την βελτίωση της αποδοτικότητας εφαρμογών που εκτελούν κομμάτια κώδικα παράλληλα. Στην βιβλιογραφία και την βιομηχανία έχουν προταθεί διάφορα προγραμματιστικά μοντέλα για αυτό τον σκοπό, στα οποία περιλαμβάνεται και το μοντέλο με παράλληλες εργασίες. Στο συγκεκριμένο μοντέλο, που έχει σκοπό την απλοποίηση του παράλληλου προγραμματισμού, ο προγραμματιστής εκφράζει τον παραλληλισμό της εφαρμογής ως εργασίες που μπορούν να εκτελεστούν παράλληλα και το σύστημα εκτέλεσης αποφασίζει πως αυτές οι εργασίες θα ανατεθούν σε νήματα του λειτουργικού συστήματος προς εκτέλεση.Στόχος της παρούσας εργασίας είναι να εξερευνήσει και να βελτιστοποιήσει τους εσωτερικούς μηχανισμούς της βιβλιοθήκης Intel TBB κάτω από συγκεκριμένους αρχιτεκτονικούς περιορισμούς. Αρχικά εξετάζουμε τον scheduler εργασιών της βιβλιοθήκης, με έμφαση στον μηχανισμό «κλοπής εργασιών», ώστε να αναγνωριστούν οι βασικές λειτουργίες του και εκτελούμε profiling για να μετρήσουμε την επιβάρυνση που επιφέρει η καθεμία. Εν συνεχεία, γίνεται προσπάθεια να βελτιστοποιήσουμε τον μηχανισμό τυχαίας κλοπής προσθέτοντας πληροφορίες που αφορούν την αρχιτεκτονική, κυρίως την ιεραρχία κρυφών μνημών και την διαμόρφωση των packages. Υλοποιούμε έναν μηχανισμό κλοπής εργασιών που ακολουθεί δύο πολιτικές: 1) κλοπή από τους κοντινότερους πυρήνες (σε απόσταση ιεραρχίας μνήμης), 2) κλοπή από τον πιο φορτωμένο με εργασίες πυρήνα. Η πρώτη πολιτική έχει στόχο να μεγιστοποιήσει την επαναχρησιμοποίηση δεδομένων που μοιράζονται πυρήνες στην ιεραρχία μνήμης, μείωση της μόλυνσης της κρυφής μνήμης με μη σχετικά δεδομένα (μείωση των conflict/coherence misses), ενθαρρύνοντας την πρόσβαση δεδομένων σε τοπικό αρχιτεκτονικό επίπεδο. Η δεύτερη πολιτική έχει στόχο την βελτίωση της εξισορρόπησης φορτίου μεταξύ των πυρήνων. Για την αξιολόγηση των παραπάνω παρουσιάζουμε πειραματικά αποτελέσματα που αφορούν την βελτίωση της απόδοσης διάφορων εφαρμογών σε μία SMP πλατφόρμα 24 πυρήνων, μία NUMA πλατφόρμα 12 πυρήνων και μία NUMA πλατφόρμα 32 πυρήνων (με πολυνηματισμό).