A Scalable and Adaptable ILP-Based Approach for Task Mapping on MPSoC Considering Load Balance and Communication Optimization

Task mapping has been a hot topic in MPSoC software design for decades. During the mapping process, load balance and communication optimization have been two important performance optimization factors. This paper studies the relations between load balance, inter-processor communications and communication pipeline technique during the mapping process, and proposes an Integer Linear Programming (ILP)-based static task mapping approach, which considers both load balance and communication optimization. The approach consists of an optimized ILP model for task mapping with fewer variables compared to previous ILP mapping works. Moreover, to enhance the scalability of the ILP task mapping, the Task-Processor-Cluster (TP-CLUSTER) algorithm is proposed to reduce the scale of the task graph and the number of processors and then solve the coarse-grained input by the ILP mapping. To increase the adaptability of the ILP task mapping, the improved augmented e-constraint (AUGMECON2) method is further integrated with the ILP formulations to select the best mapping for different applications. Experimental results on a 2/4/8/16/24-CPU platform of both synthetic and real-life benchmarks demonstrate the efficiency of the proposed approach.