|
|
| Κωδικός Πόρου |
000374669 |
| Τίτλος |
Efficient and Accurate Block-Level Dependence Analysis For Task Dataflow Models |
| Άλλος τίτλος |
Αποτελεσματική και ακριβής ανάλυση εξαρτήσεων σε επίπεδο μπλόκ μνήμης για μοντέλα που στηρίζονται σε εργασίες ροής δεδομένων |
|
Συγγραφέας
|
Παπατριανταφύλλου, Άγγελος Ιωάννης
|
|
Σύμβουλος διατριβής
|
Κατεβαίνης Μανόλης
|
| Περίληψη |
Επιχειρηματολογώντας σχετικά με το συγχρονισμό, τη διάταξη και τις αντικρουόμενες προσβάσεις στη μνήμη κάνει το παράλληλο προγραμματισμό δύσκολο, επιρρεπή σε λάθη και δύσκολο για δοκιμή, αποσφαλμάτ vση και συντήρηση. Τα προγραμματιστικά μοντέλα παραλληλισμού που βασίζονται σε εργασίες όπως είναι το OpenMP, το Cilk και το Sequioa προσφέρουν έναν πιο δομημένο τρόπο σε σχέση με τα νήματα διεργασιών ώστε να εκφραστεί περισσότερος παραλληλισμός, αλλά εξακολουθούν να υποχρεώνουν τον προγραμματιστή να βρίσκει χειροκίνητα και να επιβάλει οποιαδήποτε διάταξη ή εξαρτήσεις δεδομένων μεταξύ των εργασιών. Προγραμματιστικά μοντέλα με έμμεσο παραλληλισμό όπως είναι το SvS,το OoOJava ή το StasRs άρει αυτόν τον
περιορισμό με το να συμπεραίνουν το παραλληλισμό και τις εξαρτήσεις, απαιτούν όμως από τον προγραμματιστή να δηλώσει το αποτύπωμα της μνήμης της κάθε εργασίας. Τρέχων περιορισμοί τέτοιων συστημάτων απαιτούν από τον προγραμματιστή να περιορίσει τα αποτυπώματα της εργασίας είτε σε ολόκληρα και μεμονωμένα αντικείμενα, περιοχές μιας διάστασης ή στατικές μεταγλωττισμένες περιοχές. Όλα παράγουν υπερεκτιμήσεις και ψευδείς εξαρτήσεις που μειώνουν τον διαθέσιμο παραλληλισμό στο πρόγραμμα. Αυτή η δουλειά παρουσιάζει μια τεχνική για αποτελεσματική και ακριβής ανάλυση εξαρτήσεων σε επίπεδο μπλοκ μνήμης για μοντέλα που στηρίζονται σε εργασίες ροής δεδομένων. Φτιάξαμε ένα περιβάλλον εκτέλεσης το οποίο ονομάζεται BDDT και φιλοξενεί μια τέτοια τεχνική, ένα περιβάλλον εκτέλεσης βασισμένο σε εργασίες το οποίο δυναμικά ανιχνεύει και επιλύει εξαρτήσεις μεταξύ παράλληλων εργασιών. Ξεπεράσαμε κάποιους περιορισμούς του BDDT με το να ενεργοποιήσουμε την λειτουργία των πολλαπλών εκδοτών. Η εκταταμένη έκδοση του BDDT προσφέρει περισσότερο παραλληλισμό όταν χρησιμοποιούμε εφαρμογές στις οποίες ένας μοναδικός εκδότης φτάνει σε κορεσμό. Το BDDT επιτρέπει στους προγραμματιστές να διευκρινίσουν με λεπτομέρεια τα αποτυπώματα των εργασιών σε οποιαδήποτε περιοχή από διευθύνσεις μνήμης ή σε υποπίνακες πολυδιάστατων πινάκων. Το BDDT χρησιμοποιεί μια διαδικασία εύρεσης εξαρτήσεων η οποία βασίζεται σε μπλοκ μνήμης με αυθαίρετο βαθμό, κάνοντας ευκολότερη την εφαρμογή του σε προγράμματα χωρίς να χρειάζεται να ανακατασκευαστεί κανένα αντικείμενο ή δέσμευση πινάκων και προσφέρει ευελιξία σε διάταξη πινάκων και σε διαστάσεις υποπινάκων. Αξιολογήσαμε το BDDT χρησιμοποιώντας μια συλλογή από αντιπροσωπευτικά μετροπρογράμματα, και το συγκρίναμε με το SMPSs (το ισοδύναμο περιβάλλον εκτέλεσης στο StarSs) και με το OpenMP. Διαπιστώσαμε ότι το BDDT μπορεί να εκτελεστεί συγκρίσιμα ή καλύτερα από το SMPSs και είναι σε θέση να ανταπεξέλθει με βαθμό εργασίας 100 φορές μικρότερο μέγεθος από ότι το SMPSs μπορεί. Συγκρίνοντας με το OpenMP, το BDDT εκτελείται έως και 3.9 φορές καλύτερα για μετροπρογράμματα που επωφελούνται από την δυναμική ανάλυση εξαρτήσεων. Το προσφέρει επιπρόσθετα μια λειτουργία με την οποία ορίζονται για ποια δεδομένα μπορεί να παρακάμψει την ανάλυση των εξαρτήσεων. Χρησιμοποιώντας αυτή την λειτουργία, το BDDT υπερτερεί σε σχέση με το ακόμα και σε μετροπρογράμματα όπου η ανάλυση των εξαρτήσεων δεν μπορεί να ανιχνεύσει επιπλέον παραλληλισμό, χάρη σε μια πιο αποτελεσματική υλοποίηση του περιβάλλοντος εκτέλεσης. Αξιολογήσαμε την εκτεταμένη έκδοση του BDDT χρησιμοποιώντας το Jacobi, και το BDDT παράγει καλύτερη επίδοση και περισσότερη κλιμάκωση ενεργοποιώντας ταυτόχρονα περισσότερους του ενός εκδότες.
|
| Φυσική περιγραφή |
46 σ. : εικ., πίν. ; 30 εκ. |
| Γλώσσα |
Αγγλικά |
| Θέμα |
Compilers and Runtime Systems |
|
Synchronization in Concurrency Control |
|
Task Parallel Libraries |
| Ημερομηνία έκδοσης |
2012 |
| Συλλογή
|
Σχολή/Τμήμα--Σχολή Θετικών και Τεχνολογικών Επιστημών--Τμήμα Επιστήμης Υπολογιστών--Μεταπτυχιακές εργασίες ειδίκευσης
|
|
|
Τύπος Εργασίας--Μεταπτυχιακές εργασίες ειδίκευσης
|
| Εμφανίσεις |
434 |
Efficient and Accurate Block-Level Dependence Analysis For Task Dataflow Models
