Multistep scheduling algorithm for parallel and distributed processing in heterogeneous systems with communication costs
type: Item
instance of: scholarly article
title: Multistep scheduling algorithm for parallel and distributed processing in heterogeneous systems with communication costs
zbMATH Open document ID: 1296.90063
DOI: 10.1155/2013/184706
author: Hitoshi Yamazaki
author: Katsumi Konishi
author: Seiichi Shin
author: Kenji Sawada
published in: Mathematical Problems in Engineering
publication date: 2014-10-13T00:00:00Z
review text: Summary: 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.
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 90C09
zbMATH DE Number: 6354488
Wikidata QID: Q59023414
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1155/2013/184706
OpenAlex ID: W1967194506
cites work: A high performance algorithm for static task scheduling in heterogeneous distributed computing systems
cites work: Reasoning within fuzzy description logics
cites work: Graph clustering
description: scientific article; zbMATH DE number 6354488