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

作者：Huang, Kai; Zhang, Xiaomeng; Zheng, Dandan^*; Yu, Min; Jiang, Xiaowen; Yan, Xiaolang; de Brisolara, Lisane B.; Jerraya, Ahmed Amine

来源：IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2019, 38(9): 1744-1757.

DOI：10.1109/TCAD.2018.2859400

• Graph partitioning
• integer linear programming (ILP)
• multiobjective optimization
• multiprocessor system-on-chip (MPSoC)
• task mapping

Task mapping has been a hot topic in multiprocessor system-on-chip software design for decades. During the mapping process, load balance (LB) and communication optimization have been two important performance optimization factors. This paper studies the relations between LB, interprocessor communications, and communication pipeline technique during the mapping process, and proposes an integer linear programming (ILP)-based static task mapping approach, which considers both LB 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 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 epsilon-constraint 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.

• 出版日期2019-9
• 单位中国地震局; 浙江大学