Κατά την τελευταία δεκαετία, η ανάπτυξη κεντρικών μονάδων επεξεργασίας έχει επικεντρωθεί κυρίως σε πολυπύρηνες αρχιτεκτονικές, και οι πρόσφατες τάσεις οδηγούν σε πολυπύρηνους επεξεργαστές με όλο και μεγαλύτερο αριθμό πυρήνων. Για να εκμεταλλευτεί κανείς πλήρως ένα πολυπύρηνο σύστημα, πρέπει να αναπτύξει αποδοτικές παράλληλες εφαρμογές. Ωστόσο, η συλλογιστική σχετικά με το συγχρονισμό, την σειρά εκτέλεσης και τις συγκρουόμενες προσβάσεις στην μνήμη καθιστά τον παράλληλο προγραμματισμό περίπλοκο, επιρρεπή σε λάθη και δύσκολο να δοκιμασθεί, να διοθωθεί και να διατηρηθεί. Τα μοντέλα task-based προγραμματισμού όπως τα OpenMP, Cilk, Sequoia. SVS, OoOJava και StarSs προσφέρουν έναν πιο δομημένο τρόπο έκ¬φρασης της παραλληλίας από ότι τα threads, ενώ κάποια από αυτά είναι σε θέση να εξάγουν αυτόματα παραλληλισμό και να επιλύουν εξαρτήσεις.
Παρά τα πλεονεκτήματά τους, τα task-based μοντέλα προγραμματισμού προκαλούν σημαντικές προκλήσεις για το σύστημα εκτέλεσης (runtime). Τα tasks που είναι fine¬grained απαιτούν αποτελεσματικούς βασικούς μηχανισμούς για τη διαχείριση τους. Όμως οι μηχανισμοί διαχείρισης tasks, όπως η αρχικοποίηση, η ολοκλήρωση, η τοποθέτηση σε λίστες αναμονής, και ο χρονοπρογραμματισμός, σε παραδοσιακά παράλληλα συστήματα έχουν κόστος της τάξης των δεκάδων χιλιάδων κύκλων, που οφείλεται στην επικοινωνία και τη διαχείριση μνήμης.
Στην παρούσα εργασία, παρουσιάζουμε τον SCOOP (Source-level COmpiler Optimizations for Parallelism), έναν C source-to-source μεταγλωττιστή για task-based μοντέλα προγραμματισμού που χρησιμοποιούν επισημειώσεις ροής δεδομένων (dataflow annotations). O SCOOP επεκτείνει την C με επισημειώσεις ροής δεδομένων χρησιμοποιώντας οδηγίες τύπου #pragma, όπως αυτές του StarSs. O SCOOP αναλύει αυτές τις επισημειώσεις και παράγει αποδοτικό κώδικα C για task-parallel runtimes. Ό SCOOP είναι επίσης σε θέση να συμπεράνει αν κάποιες παράμετροι των task είναι ανεξάρτητες, ώστε να βοηθήσει είτε τον προγραμματιστή ή τα ρυντιμες που εφαρμόζουν κάποιο είδος δυναμικής ανάλυσης εξαρτήσεων. Τέλος, αξιολογούμε την αποτελεσματικότητά του SCOOP σε επεξεργαστές αρχιτεκτονικών symmetric multiprocessing (SMP) και Cell Broadband Engine, χρησιμοποιώντας ένα σύνολο παράλληλων προγραμμάτων, ως ορόσημα (benchmarks).
(EL)
Over the past decade, CPU development has focused mainly on multi-core architectures,
and recent trends lead to multi-core designs with ever increasing numbers
of cores. In order to get the best out of a many-core system, one has to develop
efficient parallel applications. However, reasoning about synchronization, ordering
and conflicting memory accesses makes parallel programming difficult, error-prone
and hard to test, debug and maintain. Task-based programming models such as
OpenMP, Cilk, Sequoia. SvS, OoOJava and StarSs offer a more structured way of
expressing parallelism than threads, while some of them are able to automatically
infer parallelism and dependencies.
Despite their advantages, task-based programming models impose significant
challenges for the runtime system. Fine-grained tasks require efficient basic mechanisms
for task management. Task management operations, such as initiation,
completion, queuing, and scheduling, in traditional parallel systems cost in the order
of tens of thousands of cycles, due to communication and memory management
overheads.
In this thesis, we present SCOOP (Source-level COmpiler Optimizations for
Parallelism), a C source-to-source compiler for task-based programming models
that use dataflow annotations. SCOOP extends C with dataflow annotations using
#pragma directives, like StarSs. SCOOP parses these annotations and produces
efficient C source code for task-parallel runtimes. SCOOP is also capable to infer
independent task arguments, enabling it to hint either the programmer or runtimes
that implement some kind of dynamic dependence analysis. We evaluate SCOOP’s
effectiveness on both symmetric multiprocessing (SMP) and the Cell Broadband
Engine architectures ,using a set of parallel benchmarks.
(EN)