Distributed Processing and A Study on the Efficient Task Scheduling by the Reconstructed Task Graph


The Transactions of the Korea Information Processing Society (1994 ~ 2000), Vol. 4, No. 9, pp. 2235-2246, Sep. 1997
10.3745/KIPSTE.1997.4.9.2235,   PDF Download:

Abstract

This paper presents an effective heuristic task scheduling algorithm for multiprecessor systems. To execute task scheduling effectively which is defined as an allocation of m's tasks onto n's processors(m > n), several problems almost at NP-hard should be cleaned up. The purpose of the task scheduling obtains the minimum execution time by mapping the tasks on a system topology or reduces the total execution time to give a minimum system topology. In order to solve this problem, in this paper, the task scheduling is done by redefining a task graph to a reconstructed task graph(RTG). An RTG is obtained by merging or copying nodes to equal the number of nodes on each level of the task graph to the number of processors of the system topology and then directly scheduled to the system topology. This method obtains a fast scheduling time and a simple scheduling method, and near-optimal execution time without executing steps such as refinement step and the duplication step after the task scheduling.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
B. S. Hwan and Y. K. Jong, "Distributed Processing and A Study on the Efficient Task Scheduling by the Reconstructed Task Graph," The Transactions of the Korea Information Processing Society (1994 ~ 2000), vol. 4, no. 9, pp. 2235-2246, 1997. DOI: 10.3745/KIPSTE.1997.4.9.2235.

[ACM Style]
Byun Seung Hwan and Yoo Kwan Jong. 1997. Distributed Processing and A Study on the Efficient Task Scheduling by the Reconstructed Task Graph. The Transactions of the Korea Information Processing Society (1994 ~ 2000), 4, 9, (1997), 2235-2246. DOI: 10.3745/KIPSTE.1997.4.9.2235.