Genetic algorithms for scheduling in a CPU/FPGA architecture with heterogeneous communication delays. (November 2019)

• Record Type: Journal Article
• Authors: Abdallah, Fadel; Tanougast, Camel; Kacem, Imed; Diou, Camille; Singer, Daniel
• Is Part Of: Computers & industrial engineering. Volume 137(2019)
• Publication Date: 2019-11
• Subjects: Genetic algorithm -- Task scheduling problem -- Combinatorial optimization -- Metaheuristics -- Makespan (schedule length) -- Linear programming; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2019.106006
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: We consider a heterogeneous architecture scheduling problem. We consider the assumption of communication delays on a CPU/FPGA architecture. The aim is to minimize the makespan. Two genetic algorithms are proposed and compared. We identify one effective algorithm providing satisfactory solutions in short computation time. Abstract: In this paper we study a CPU/FPGA heterogeneous architecture scheduling problem (often referred as Multi-Processors System on Chip or MPSoC) with communication delays' constraints. In this context, we propose two approaches based on genetic algorithms. Their main goal is to run in the MPSoC an application, which is described by a given data flow graph. The aim is to minimize the schedule length (makespan). Computational experiments are conducted to evaluate the proposed algorithms. The obtained results show that the two approaches are often capable of finding optimal or near optimal solutions for the studied problem while improving significantly the running time compared to existing works.