E-Locus - Institutional Repository of the University of Crete - Combining recursively parallel runtimes with blocked-based dependence analysis

Home Combining recursively parallel runtimes with blocked-based dependence analysis

Results - Details

[Add to Basket]

Identifier

000395041

Title

Combining recursively parallel runtimes with blocked-based dependence analysis

Alternative Title

Συνδυάζοντας αναδρομικά παράλληλα συστήματα χρόνου εκτέλεσης με ανάλυση εξαρτήσεων βασισμένη σε blocks

Author

Παπακωνσταντίνου, Νικόλαος

Thesis advisor

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

Reviewer

Πρατικάκης, Πολύβιος
Φατούρου, Παναγιώτα

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%.

Language

English, Greek

Issue date

2015-07-17

Collection

School/Department--School of Sciences and Engineering--Department of Computer Science--Post-graduate theses

Type of Work--Post-graduate theses

Views

607

Digital Documents
	Download document View document Views : 22