.png){kind=icon}
.png){kind=icon}
Return
Models and scheduling algorithms for mixed data and task parallel programs
.png){kind=icon}
PRE
AI
DOI：10.1006/jpdc.1997.1413.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
An increasing number of scientific programs exhibit two forms of parallelism, often in a nested fashion, at the outer level, the application comprises coarse-grained task parallelism, with dependencies between tasks reflected by an acyclic graph, At the inner level, each node of the graph is a data-parallel operation on arrays, Designers of languages, compilers, and runtime systems are building mechanisms to support such applications by providing processor groups and array remapping capabilities. In this paper we explore how to supplement these mechanisms with policy, What properties of an application, its data size, and the parallel machine determine the maximum potential gains from using both kinds of parallelism? It turns out that large gains can he expected only for specific task graph structures. For such applications, what are practical and effective ways to allocate processors to the modes of the task graph? In principle one could solve the NP-complete problem of finding the best possible allocation of arbitrary processor subsets to nodes ha the task graph, Instead of this, our analysis and simulations show that a simple switched scheduling paradigm, which alternates between pore task and pure data parallelism, provides nearly optimal performance for the task graphs considered here, Furthermore, our scheme is much simpler to implement, has less overhead than the optimal allocation, and would he attractive even if the optimal allocation was free to compute. To evaluate switching in real applications, we implemented a switching task scheduler in the parallel numerical library ScaLAPACK and used it in a nonsymmetric eigenvalue program, Even far fairly large input sizer;, the efficiency improves by factors of 1.5 on the Intel Paragon and 2.5 on the IBM SP-2. The remapping and scheduling overhead is negligible, between 0.5 and 5%. (C) 1997 Academic Press.
Journal
IF:
4
Papers:
3.8K
Citations:
4.8K
Organization
No organization information available