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

Wing Ning Li, Zhichun Xiao, John Jingfu Jenq

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

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.

Original languageEnglish
Title of host publicationProceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, PDPTA'04
EditorsH.R. Arabnia
Pages1095-1101
Number of pages7
StatePublished - 1 Dec 2004
EventProceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, PDPTA'04 - Las Vegas, NV, United States
Duration: 21 Jun 200424 Jun 2004

Publication series

NameProceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, PDPTA'04
Volume3

Other

OtherProceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, PDPTA'04
CountryUnited States
CityLas Vegas, NV
Period21/06/0424/06/04

Keywords

  • Clustering
  • Complexity
  • Multiprocessor
  • Parallel and distributed computing
  • Scheduling

Fingerprint Dive into the research topics of 'An exact scheduling algorithm for two, linear-nonlinear clusters, with a common communication delay'. Together they form a unique fingerprint.

  • Cite this

    Li, W. N., Xiao, Z., & Jenq, J. J. (2004). An exact scheduling algorithm for two, linear-nonlinear clusters, with a common communication delay. In H. R. Arabnia (Ed.), Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, PDPTA'04 (pp. 1095-1101). (Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, PDPTA'04; Vol. 3).