Genetic Algorithm and Integer Programming Approaches for solving Task Scheduling Optimization and NoC Performance in MPSoC Systems

Abstract

Task scheduling in the Multi-Processor System-on-Chip (MPSoC) platform is important for achieving efficiency by distributing tasks among several processors. Scheduling tasks can become a complex problem the number of processors and tasks increases as well as when functioning within a framework of Network-on-Chip (NoC) systems since communication overhead has to be optimized as well. Present existing strategies such as Integer Programming (IP), offer the best solutions but are very time-consuming and prohibitive for large scientific problems or online planning. On the contrary, heuristic methods such as Genetic Algorithm (GA) provide a balance between solution quality and computational cost. This study aims to contrast IP and GA in the scheduling of MPSoC processors’ tasks and evaluate the effects of extending these algorithms on NoC-based systems with specific reference to effectiveness, robustness, computational efficiency, and NoC performance. The performance of the task scheduling problem for the small-scale case of 6-10 jobs and the large-scale case of 40 to 200 jobs have been assessed in the study.