SCOOP: Language extensions and compiler optimizations for task-based programming models

This item is provided by the institution :
University of Crete
Repository :
E-Locus Institutional Repository
see the original item page
in the repository's web site and access all digital files if the item*

2012 (EN)
Scoop: Επεκτάσεις γλώσσας και βελτιώσεις από τον Compiler για Task-Based μοντέλα προγραμματισμού
SCOOP: Language extensions and compiler optimizations for task-based programming models

Ζακκάκ, Φοίβος Σάμι

Μπίλας, Άγγελος

Κατά την τελευταία δεκαετία, η ανάπτυξη κεντρικών μονάδων επεξεργασίας έχει επικεντρωθεί κυρίως σε πολυπύρηνες αρχιτεκτονικές, και οι πρόσφατες τάσεις οδηγούν σε πολυπύρηνους επεξεργαστές με όλο και μεγαλύτερο αριθμό πυρήνων. Για να εκμεταλλευτεί κανείς πλήρως ένα πολυπύρηνο σύστημα, πρέπει να αναπτύξει αποδοτικές παράλληλες εφαρμογές. Ωστόσο, η συλλογιστική σχετικά με το συγχρονισμό, την σειρά εκτέλεσης και τις συγκρουόμενες προσβάσεις στην μνήμη καθιστά τον παράλληλο προγραμματισμό περίπλοκο, επιρρεπή σε λάθη και δύσκολο να δοκιμασθεί, να διοθωθεί και να διατηρηθεί. Τα μοντέλα 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)

Τύπος Εργασίας--Μεταπτυχιακές εργασίες ειδίκευσης

Parallel Computing

Πανεπιστήμιο Κρήτης (EL)
University of Crete (EN)



Σχολή/Τμήμα--Σχολή Θετικών και Τεχνολογικών Επιστημών--Τμήμα Επιστήμης Υπολογιστών--Μεταπτυχιακές εργασίες ειδίκευσης

*Institutions are responsible for keeping their URLs functional (digital file, item page in repository site)