A4 Vertaisarvioitu artikkeli konferenssijulkaisussa

DBFS: Dual Best-First Search mapping algorithm for shared-cache multicore processors




TekijätThomas Canhao Xu, Ville Leppänen

ToimittajaWang, Guojun and Zomaya, Albert and Martinez Perez, Gregorio and Li, Kenli

Konferenssin vakiintunut nimiInternational Conference on Algorithms and Architectures for Parallel Processing

Julkaisuvuosi2015

Kokoomateoksen nimiAlgorithms and Architectures for Parallel Processing

Sarjan nimiLecture Notes in Computer Science

Numero sarjassa9528

Aloitussivu185

Lopetussivu198

Sivujen määrä14

ISBN978-3-319-27118-7

DOIhttps://doi.org/10.1007/978-3-319-27119-4_13


Tiivistelmä

This paper proposes a task mapping algorithm for shared-cache multicore processors. The multicore system is quantitatively analysed in terms of intra-application communication latency, inter-application congestion and delay of shared-cache access. A heuristic greedy best-first search algorithm is adapted to find a compact mapping region for an application. We develop a flexible dual best-first search strategy that evaluates the network dynamically according to the current situation. Several metrics are applied to improve the quality of the mapping result. We evaluate the proposed algorithm along with others using synthetic and real applications. Results from the synthetic workloads show that the proposed algorithm achieves nearly optimal cache access delays on 64-node network under 50 % to 100 % system utilization, while the intra-application latency and inter-application congestion metrics are improved by 13.8 % and 17.2 % in a practical system configuration, compared with the incremental algorithm. We also compare our proposal with the true optimal solutions, results reveal that the algorithm can provide near-optimal results with enough search spaces. Furthermore the computation complexity of the proposed algorithm is relatively low. The data from real applications show that the average execution time of applications is reduced 13.5 % compared to the first fit algorithm.




Last updated on 2024-26-11 at 10:32