Scheduling complete binary tree with constant cost task on heterogeneous processors

摘要

In the present paper, we are interested in scheduling tasks of Complete Binary Tree (CBT), whose nodes have constant costs in a heterogeneous environment involving uniform processors with different speeds. Therefore, the main objective of our work is to determinate an efficient scheduling of the described problem, then calculate the lower bound of the execution time with p processors of all the tasks forming the CBT. Besides, we propose a parallel algorithm to schedule these tasks with heterogeneous processors. In this context, some experimental results show the optimality of execution time when communication costs are neglected.