TY - GEN

T1 - An exact scheduling algorithm for two, linear-nonlinear clusters, with a common communication delay

AU - Li, Wing Ning

AU - Xiao, Zhichun

AU - Jenq, John Jingfu

PY - 2004/12/1

Y1 - 2004/12/1

N2 - In parallel and distributed processing, tasks are ordinarily clustered and assigned to different processors before they are scheduled. The assignment of tasks to processors is called clustering. Within each cluster, the ordering of tasks for execution, including the specification of the starting time of each task, is called clustering schedule. The set of tasks is typically modelled as a directed acyclic task graph, capturing the partial order relationship among the tasks. As a result of the clustering process, with respect to the DAG, the set of tasks in each cluster either forms a total ordering or it doesn't. A cluster is called linear if the tasks in it are totally ordered, otherwise it is called nonlinear. Due to inter-processor communication delay, when T 1 ≺ T 2 and T 1 and T 2 are processed by different processors, the execution of T 2 cannot start right away once T 1 finishes and it must wait τ steps, τ is called communication delay. It has been shown that the problem of finding an optimal schedule for two clusters with one cluster being linear and the other nonlinear with a common communication delay is strongly NP-hard. In this paper, we develop an exact, polynomial time algorithm to solve the above problem when tasks are restricted to unit tasks.

AB - In parallel and distributed processing, tasks are ordinarily clustered and assigned to different processors before they are scheduled. The assignment of tasks to processors is called clustering. Within each cluster, the ordering of tasks for execution, including the specification of the starting time of each task, is called clustering schedule. The set of tasks is typically modelled as a directed acyclic task graph, capturing the partial order relationship among the tasks. As a result of the clustering process, with respect to the DAG, the set of tasks in each cluster either forms a total ordering or it doesn't. A cluster is called linear if the tasks in it are totally ordered, otherwise it is called nonlinear. Due to inter-processor communication delay, when T 1 ≺ T 2 and T 1 and T 2 are processed by different processors, the execution of T 2 cannot start right away once T 1 finishes and it must wait τ steps, τ is called communication delay. It has been shown that the problem of finding an optimal schedule for two clusters with one cluster being linear and the other nonlinear with a common communication delay is strongly NP-hard. In this paper, we develop an exact, polynomial time algorithm to solve the above problem when tasks are restricted to unit tasks.

KW - Clustering

KW - Complexity

KW - Multiprocessor

KW - Parallel and distributed computing

KW - Scheduling

UR - http://www.scopus.com/inward/record.url?scp=12244302499&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:12244302499

SN - 1932415262

SN - 9781932415261

T3 - Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, PDPTA'04

SP - 1095

EP - 1101

BT - Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, PDPTA'04

A2 - Arabnia, H.R.

T2 - Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, PDPTA'04

Y2 - 21 June 2004 through 24 June 2004

ER -