Benchmarking the contention aware nature inspired metaheuristic task scheduling algorithms

摘要

In this paper, we consider the contention aware task scheduling problem on a grid topology of processors. By contention awareness, we mean that simultaneous communication on a link has to be serialized. To solve this problem, we propose several nature inspired metaheuristic algorithms:Simulated Annealing(SA),Genetic Algorithm(GA),Differential Evolution(DE),Particle Swarm Optimization(PSO),Bat Algorithm(BA),Cuckoo Search(CS), andFirefly Algorithm(FA). We perform benchmark evaluation of these algorithms for theNormalized Schedule Length(NSL) parameter. The benchmark task graphs that we consider are: random task graphs, peer set task graphs, systolic array task graphs, Gaussian elimination task graphs, divide and conquer task graphs, and fast Fourier transform task graphs.