Exploring Task Mappings on Heterogeneous MPSoCs using a Bias-Elitist Genetic Algorithm
This addresses performance optimization in heterogeneous MPSoCs, an incremental improvement over classic genetic algorithms for faster evolution times.
The paper tackled the NP-complete problem of mapping tasks onto heterogeneous MPSoCs for maximal throughput, proposing a bias-elitist genetic algorithm that handles large-scale problems and produces high-quality solutions quickly.
Exploration of task mappings plays a crucial role in achieving high performance in heterogeneous multi-processor system-on-chip (MPSoC) platforms. The problem of optimally mapping a set of tasks onto a set of given heterogeneous processors for maximal throughput has been known, in general, to be NP-complete. The problem is further exacerbated when multiple applications (i.e., bigger task sets) and the communication between tasks are also considered. Previous research has shown that Genetic Algorithms (GA) typically are a good choice to solve this problem when the solution space is relatively small. However, when the size of the problem space increases, classic genetic algorithms still suffer from the problem of long evolution times. To address this problem, this paper proposes a novel bias-elitist genetic algorithm that is guided by domain-specific heuristics to speed up the evolution process. Experimental results reveal that our proposed algorithm is able to handle large scale task mapping problems and produces high-quality mapping solutions in only a short time period.