A Scheduling Algorithm to Optimize Parallel Processes

In this paper we present a scheduling algorithm that assigns tasks of medium size grain. The behavior of the proposed algorithm, called extended latency time (ELT), is compared with the dominant sequence clustering (DSC) algorithm. One of the inputs values required by the ELT algorithm is the maximum number of processors available in the architecture. This value corresponds to the number of processors used by DSC for the same DAG (directed acyclic graph), but ELT uses no more processors than necessary. Although ELT algorithm was specifically designed for assigning fine grained DAGs, results show that the number of processors used by ELT for the assignment of medium grained DAGs is, at most, the same number as used by DSC. When comparing the results for each algorithm in terms of average CPU use, the proposed ELT algorithm is superior in 100% of the cases, so that the performance in terms of CPU use is always lower for DSC.