Particionamento e mapeamento de aplicações em MPSoCs baseados em NoCs 3D

Abstract

Multiprocessor System-on-Chip (MPSoC) based on Network-on-Chip (NoC) incorporates a lot of Processing Elements (PEs) in order to perform applications with high degree of parallelism/concurrence. These applications consist of several communicating tasks that are dynamically mapped into the PEs of the target architecture. When the number of application tasks grows, the complexity of mapping also grows, possibly reducing the effectiveness and/or efficiency of the solution. An approach for the mapping optimization is the introduction of a previous step called partitioning, which allows to organize the tasks interaction through an efficient grouping, reducing the number of mapping alternatives. This paper proposes the Partition Reduce (PR) algorithm, which is a task partitioning approach inspired on MapReduce algorithm, where tasks are partitioned by a deterministic iterative clustering. The PR was analyzed according to its effectiveness and efficiency to minimize the energy consumption caused by the communication in the target architecture and to balance the processing load on the PEs. Experimental results, containing a wide range of complex tasks, show that PR is more effective in generating partitions with low power consumption and efficient load balancing at any level of tasks complexity, when compared with the simulated annealing (SA) algorithm. Moreover, the results show that the algorithm is efficient only for medium or high complexity applications.