CPR: mixed task and data parallel scheduling for distributed systems

It is well-known that mixing task and data parallelism to solve large computational applications often yields better speedups compared to either applying pure task parallelism or pure data parallelism. Typically, the applications are modeled in terms of a dependence graph of coarse-grain data-parall...

Full description

Saved in:
Bibliographic Details
Main Authors: Radulescu, A., Nicolescu, C., van_Gemund, A.J.C., Jonker, P.P.
Format: Conference Proceeding
Language:English
Subjects:
Computer applications
Concurrent computing
Costs
Information technology
Measurement
Parallel processing
Physics computing
Processor scheduling
Scheduling algorithm
Topology
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:It is well-known that mixing task and data parallelism to solve large computational applications often yields better speedups compared to either applying pure task parallelism or pure data parallelism. Typically, the applications are modeled in terms of a dependence graph of coarse-grain data-parallel tasks, called a data-parallel task graph. In this paper we present a new compile-time heuristic, named Critical Path Reduction (CPR), for scheduling data-parallel task graphs. Experimental results based on graphs derived from real problems as well as synthetic graphs, show that CPR achieves higher speedup compared to other well-known existing scheduling algorithms, at the expense of some higher cost. These results are also confirmed by performance measurements of two real applications (i.e., complex matrix multiplication and Strassen matrix multiplication) running on a cluster of workstations.
ISSN:1530-2075
DOI:10.1109/IPDPS.2001.924977