Advertisement
Published in:
2011 | OriginalPaper | Chapter
Realistic Task Scheduling with Contention Awareness Genetic Algorithm by Fuzzy Routing in Arbitrary Heterogeneous Multiprocessor Systems
Authors : Nafiseh Sedaghat, Hamid Tabatabaee-Yazdi, Mohammad-R Akbarzadeh-T
Published in: Knowledge Engineering and Management
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.