ΘΕΜΑ: Paroysiash/Eksetash Metaptyxiakhs Ergasias Papakonstantinou Nikolaos_02/06/2015_ 17:00_K206_ dept. Computer Science UoC_oral defense of MSc by Papakonstantinou Nikolaos_ 2 June_ 17:00-19:00 (GR) ΑΠΟΣΤΟΛΕΑΣ: Gramateia Metaptyxiakou CSD [mailto:pgram@xxxxxxxxxx] ΠΑΡΟΥΣΙΑΣΗ / ΕΞΕΤΑΣΗ ΜΕΤΑΠΤΥΧΙΑΚΗΣ ΕΡΓΑΣΙΑΣ Παπακωνσταντίνου Νικόλαος Mεταπτυχιακός Φοιτητής Eπόπτης Μεταπτ. Εργασίας: Καθηγητής, Α. Μπίλας Τρίτη, 2 Ιουνίου 2015, 17:00 “ Συνδυάζοντας Αναδρομικά Παράλληλα Συστήματα Χρόνου Εκτέλεσης με Ανάλυση Εξαρτήσεων βασισμένη σε blocks "
Στην εργασία αυτή συνδυάσαμε τον αναδρομικό παραλληλισμό εργασιών με την δυναμική ανάλυση εξαρτήσεων για να εξάγουμε περισσότερο παραλληλισμό από τα προγράμματά μας. Παλαιότερα συστήματα χρόνου εκτέλεσης όπως το Cilk χρησιμοποιούν τον αναδρομικό παραλληλισμό εργασιών αλλά ο συγχρονισμός των εργασιών είναι χειροκίνητος και ο προγραμματιστής είναι υπεύθυνος για των ορισμό των σημείων συγχρονισμού. Από την άλλη, συστήματα χρόνου εκτέλεσης όπως το BDDT και το SMPSs χρησιμοποιούν την ανάλυση εξαρτήσεων για να λύσουν τις εξαρτήσεις μεταξύ των εργασιών, αλλά υποφέρουν από το πρόβλημα κλιμάκωσης μοναδικού χρονοδρομολογιτή. Εμείς συνδυάζουμε αυτά τα δύο μοντέλα και παρουσιάζουμε ένα παράλληλο αλγόριθμο ανάλυσης εξαρτήσεων για να συμπεράνουμε εξαρτήσεις κατά τον χρόνο εκτέλεσης μεταξύ αναδρομικών παράλληλων εργασιών. Υλοποιήσαμε την δυναμική ανάλυση στο PARTEE , ένα κλιμακώσιμο σύστημα χρόνου εκτέλεσης το οποίο υποστηρίζει έμμεσο συγχρονισμό μεταξύ εμφωλευμένων παράλληλων εργασιών. Ερευνήσαμε τις απαιτούμενες αλλαγές για ένα σύστημα χρόνου εκτέλεσης όμοιο του Cilk που να υποστηρίζει εξαρτήσεις μεταξύ των εργασιών και αξιολογήσαμε την απόδοση του συστήματος χρόνου εκτέλεσης που προέκυψε. Παρατηρούμε ότι σε περιπτώσεις που οι εξαρτήσεις των εργασιών είναι ακανόνιστες, το PARTEE υπερισχύει του Cilk, ενός παράλληλου συστήματος χρόνου εκτέλεσης χωρίς έμμεσο συγχρονισμό εργασιών, έως και 54%. Papakonstantinou Nikolaos
Master's Thesis Supervisor: Professor Angelos Bilas Tuesday, 2/6/2015, 17:00 Room K206, Computer Science dept., University of Crete
“Combining Recursively Parallel Runtimes with Blocked-based Dependence Analysis” ABSTRACT In this work we combine recursive task-parallelism with dynamic dependence analysis to expose more parallelism from our programs. Early runtime systems as Cilk usethe recursively task-parallelism but task synchronization is manual and the programmeris rensposible defining the synchronization points. On the other hand, runtime systems such as BDDT and SMPSs also use dependence analysis which to solve the dependencies between tasks, but they suffer from the single master scaling problem. We combine these two models and we present a dependence analysis algorithm for inferring runtime dependencies between recursively parallel tasks. We implement the dependence analysis in PARTEE, a scalable runtime system that supports implicit synchronization between nested parallel tasks. We explore the changes required for a Cilk-like runtime system to support task dependencies and evaluate the performance of the resulting runtime system. We find that in cases where task dependencies are irregular, PARTEE outperforms Cilk, a task-parallel runtime without implicit task synchronization, by up to 54%.
-- Postgraduate Secretariat Computer Science Department Voutes University Campus Heraklion, Crete GR-70013, Greece tel: + 30 2810 393592, 393504 fax:+ 30 2810 393804 e-mail: pgram@xxxxxxxxxx Url: http://www.csd.uoc.gr |