Investigando Heurísticas de Mapeamento de Tarefas sobre a Plataforma HeMPS

Abstract

An MPSoC is an integrated system on a single chip (SoC), composed of multiple processing elements, allowing the execution of multiple tasks in parallel. They are trend in circuit design since allow to minimize the project productivity crisis, represented by the gap between the silicon technology capacity and the SoCs’ current design capacity. Examples of MPSoCs are TILE-Gx72 and Kilo-Core, composed respectively by 72 and 1000 processing cores. Faced with this abundant amount of cores, efficient resource allocation strategies need to be developed. Task Mapping is responsible by assigning the MPSoC’s Processing for each task of a given application. The Static mapping is performed at design time, so it can not handle dynamic workloads. On the other hand, the dynamic mapping strategies can handle new tasks or applications inserted in MPSoC at run time. However, this strategy requires the employment of simple and fast heuristics. The purpose of this paper is to investigate the performance of heuristics for dynamic task mapping. In order to reach this objective, a research was first carried out on MPSoCs, and from there the models of systems found as well as platforms that simulate these systems were discussed. HeMPS was selected as the target platform for this work. Next, task mapping heuristics were investigated and heuristics First Free, Nearest Neighbor, Path Load and Best Neighbor were selected for implementation in the simulation platform. After this step, we performed simulations of test cases with applications running on the platform. The performance and occupation of the HeMPS communication channels were used as metrics to compare the results of the heuristics. The results of the simulations evidenced the vocation of the Path Load and Best Neighbor heuristics in controlling congestion in the communication channels, with the Best Neighbor heuristic presented the lowest average occupation of the communication channels. Regarding the performance, the Path Load and Best Neighbor heuristics obtained mapping and simulation time up to 6.24% higher than the other heuristics, because they have more complex algorithms in comparison to the First Free and Nearest Neighbor heuristics that do not consider the occupation of communication channels.