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

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

1. Introduction

Computer simulation is useful for various calculations, for example, for developing medicine [1], analyzing the orbit of rockets [2], and developing various other products [3]. Computer simulation can reduce the time and costs required to make prototypes and tell us in advance the amount of deterioration and risk in what we do. Hence, developing computers for conducting simulations is important. Today, a single processor, which is the main calculating element in a computer, has performance limitations. Accordingly, research and development on a multicore CPU and GPU accumulated processors as cores [4] and grid computing [5] to reduce computation time has been extensive. This research is in the field of parallel and distributed processing. It is important for increasing the computation speed for assigning tasks to appropriate processors or computers. This is called task scheduling [6].

In parallel and distributed processing, a program is composed of a set of tasks, which is regarded as a graph in which tasks are bridged. The graph is called a task graph [7]. One of the most active research areas is on the task scheduling problem, which is how to assign tasks to processing elements (PEs), for example, CPU, GPU, and DSP, appropriately so that certain performance indices are optimized. There are many algorithms for task scheduling [6–10]. Focusing on the optimality of task scheduling, Beaumont et al. [9] and Shioda et al. [10] have proposed scheduling algorithms within 0-1 integer linear programming framework. Beaumont et al.’s algorithm [9] is applied to task graphs for multiround algorithms. On the other hand, Shioda et al.’s algorithm [10] is used to execute more complicated task graphs that have tasks with priority orders to be executed by...