Using genetic algorithms to schedule multiprocessor systems under LOGP model
Yu Chen · Spectrum Research Repository (Concordia University) · 2006
In recent years, with the wide-spreading usage of computer technologies in various aspects of the modern world, the demand for more powerful computers has outmatched the yet rapid advancement in hardware development. LogP model is a practical model that reflects better the practical behavior of nowaday massively parallel computers. This thesis is dedicated to the design and evaluation of algorithms for multiprocessor system scheduling under the LogP model. The objective is to obtain a feasible schedule of input task graphs and corresponding LogP model with minimum makespan . Due to the NP-hard nature of the problem, we choose the genetic algorithms (CA) to effectively explore the huge solution space. The approach consists of two main parts. The communication tasks under the LogP model are scheduled by a genetic algorithm with determined processor assignments. Another CA is used to optimize the processor assignments of computational tasks. The design issues in both CA algorithms are discussed in detail. The evaluation of both parts of the algorithm over a set of benchmark task graphs shows an overall improvement over previous works within the LogP model.