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

Wing Ning Li, Zhichun Xiao, John Jenq

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

1 Citation (Scopus)

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
Volume3
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

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

Fingerprint

Scheduling algorithms
Communication
Polynomials
Specifications
Processing

Keywords

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

Cite this

Li, W. N., Xiao, Z., & Jenq, 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 (Vol. 3, pp. 1095-1101)
Li, Wing Ning ; Xiao, Zhichun ; Jenq, John. / An exact scheduling algorithm for two, linear-nonlinear clusters, with a common communication delay. Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, PDPTA'04. editor / H.R. Arabnia. Vol. 3 2004. pp. 1095-1101
@inproceedings{dc2a6f3436084bf5ac973c05d3de89d2,
title = "An exact scheduling algorithm for two, linear-nonlinear clusters, with a common communication delay",
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.",
keywords = "Clustering, Complexity, Multiprocessor, Parallel and distributed computing, Scheduling",
author = "Li, {Wing Ning} and Zhichun Xiao and John Jenq",
year = "2004",
month = "12",
day = "1",
language = "English",
isbn = "1932415262",
volume = "3",
pages = "1095--1101",
editor = "H.R. Arabnia",
booktitle = "Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, PDPTA'04",

}

Li, WN, Xiao, Z & Jenq, J 2004, An exact scheduling algorithm for two, linear-nonlinear clusters, with a common communication delay. in HR Arabnia (ed.), Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, PDPTA'04. vol. 3, pp. 1095-1101, Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, PDPTA'04, Las Vegas, NV, United States, 21/06/04.

An exact scheduling algorithm for two, linear-nonlinear clusters, with a common communication delay. / Li, Wing Ning; Xiao, Zhichun; Jenq, John.

Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, PDPTA'04. ed. / H.R. Arabnia. Vol. 3 2004. p. 1095-1101.

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

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

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

SN - 1932415262

SN - 9781932415261

VL - 3

SP - 1095

EP - 1101

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

A2 - Arabnia, H.R.

ER -

Li WN, Xiao Z, Jenq J. An exact scheduling algorithm for two, linear-nonlinear clusters, with a common communication delay. In Arabnia HR, editor, Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, PDPTA'04. Vol. 3. 2004. p. 1095-1101