Realistic Task Scheduling with Contention Awareness Genetic Algorithm by Fuzzy Routing in Arbitrary Heterogeneous Multiprocessor Systems

摘要

Task scheduling is an essential aspect of parallel processing system. This problem assumes fully connected processors and ignores contention on the communication links. However, as arbitrary processor network (APN), communication contention has a strong influence on the execution time of a parallel application. In this paper, we propose genetic algorithms with fuzzy routing to face with link contention. In fuzzy routing algorithm, we consider speed of links and also busy time of intermediate links. To evaluate our method, we generate random DAGs with different Sparsity value based on Bernoulli distribution and compare our method with genetic algorithm and classic routing algorithm and also with BSA (bubble scheduling and allocation) method that is a well-known algorithm in this field. Experimental results show our method (GA with fuzzy routing) is able to find a scheduling with lower makespan than GA with classic routing and also BSA.