An efficient algorithm for static task scheduling in parallel applications

摘要

Scheduling is an important tool for optimizing the performance of parallel systems. It aims at reducing the completion time of parallel applications by properly allocating the tasks to the processors. This work proposes a novel scheduling algorithm to parallelize tasks with dependence restrictions. The communication costs between processors and computer architecture are parameters of the proposed algorithm, which explores the trade off between process execution time and communication costs between processes to optimize the system's overall performance. The paper conducts an experiment to compare the performance of the proposed algorithm against six other scheduling algorithms. The experiment considered several execution scenarios. Although our algorithm does not present the best performance in any of the execution scenarios, it produces the best average execution time for the scenarios studied.