A Genetic Algorithm for Scheduling Directed Acyclic graphs in The Presence of Communication Contention

摘要

This paper presents an algorithm for scheduling parallel applications represented in the form of directed acyclic graphs (DAGs) onto a set of homogeneous parallel processors. The algorithm utilizes a genetic algorithm to prioritize scheduling activities for a list scheduling algorithm with the primary goal of minimizing schedule length and a secondary goal of minimizing the total number of processors used in the schedule. The genetic list scheduling (GLS) algorithm presented in this paper extends existing research by considering contention for processor-to-network links during communication operations. This requires the GLS to efficiently schedule both communication and computation operations in order to reduce schedule lengths. Furthermore, The GLS presented in this paper also strives to efficiently schedule multicast operations over a virtual point-to-point topology. Schedules produced by this GLS algorithm are shown to have shorter lengths than those produced by the HLEFT and ETF algorithms that have been modified to handle communication contention and multicast communication. A parallel implementation of the GLS algorithm using the synchronous connected island model is also investigated and is shown to produce better results than the sequential implementation.