Multistep Scheduling Algorithm for Parallel and Distributed Processing in Heterogeneous Systems with Communication Costs

Hitoshi Yamazaki, Katsumi Konishi, Seiichi Shin and Kenji Sawada

Mathematical Problems in Engineering, 2013, vol. 2013, 1-15

Abstract:

We discuss a task scheduling problem in heterogeneous systems and propose a multistep scheduling algorithm to solve it. Existing scheduling algorithms formulated as 0-1 integer linear programming can be used to consider the optimality of task scheduling. However, they cannot address complicated relations among tasks or communication costs among processors. Therefore, we propose a scheduling algorithm that formulates communication costs as 0-1 integer linear programming. On the other hand, 0-1 integer linear programming takes a long time to calculate the scheduling results because it is NP-complete. Thus, scheduling time also needs to be decreased. A solution for decreasing scheduling time is a graph clustering which decomposes a large task graph into smaller subtask graphs (clusters). Also, it is important for parallel and distributed processing to find task parallelism in a task graph. Then, we also propose a clustering algorithm based on SCAN . SCAN is an algorithm for finding clusters in a network. The clustering algorithm based on SCAN can find task parallelism in a task graph. In numerical examples, we argue the following two points. First, our multistep scheduling algorithm resolves the scheduling problem in heterogeneous systems. Second, it is superior to the existing scheduling algorithms in terms of calculation time.

Date: 2013
References: Add references at CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/MPE/2013/184706.pdf (application/pdf)
http://downloads.hindawi.com/journals/MPE/2013/184706.xml (text/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:jnlmpe:184706

DOI: 10.1155/2013/184706

Access Statistics for this article

More articles in Mathematical Problems in Engineering from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().