Authors: Nancy M. Amato, Ping An

Find PDF here: PDF

Abstract:
"In this report, we describe the relationship between task scheduling and deterministic mesh sweeps that arise in particle-transport computations. In particular, we argue that the efficient parallelization of such computations is most accurately viewed as a generalization of the traditional task scheduling problem and not as an application for domain decomposition, as has been generally assumed in the past. In fact, as we show, the transport problem represents an interesting composite task-scheduling problem: given one set of tasks, and multiple dependence graphs for these tasks (one for each distinguishable sweep direction), find an assignment of tasks to processors that minimizes the time required to process all such graphs. Within this context, our goal is to study and propose scheduling algorithms that are suitable for the particular generalization of the scheduling problem that arises in the context of transport sweeps. This report documents our progress to date and describes future plans. It consists of three parts. First, we define the traditional task scheduling problem and describe relevant related work. Second, we describe our progress in building a C++ task scheduling library that will provide a testbed in which to evaluate and compare the scheduling algorithms we design, including an experimental evaluation of the (traditional) scheduling algorithms implemented to date. Third, we briefly outline our plans for future work." 

@techreport{Amato-tsapmi-2000, 
 address = {College Station, TX}, 
 author = {Nancy M. Amato, Ping An}, 
 institution = {Texas A&M University}, 
 month = {January}, 
 number = {TR00-009}, 
 title = {Task Scheduling and Parallel Mesh-Sweeps in Transport Computations}, 
 year = {2000} 
}