A4 Vertaisarvioitu artikkeli konferenssijulkaisussa
DBFS: Dual Best-First Search mapping algorithm for shared-cache multicore processors
Tekijät: Thomas Canhao Xu, Ville Leppänen
Toimittaja: Wang, Guojun and Zomaya, Albert and Martinez Perez, Gregorio and Li, Kenli
Konferenssin vakiintunut nimi: International Conference on Algorithms and Architectures for Parallel Processing
Julkaisuvuosi: 2015
Kokoomateoksen nimi: Algorithms and Architectures for Parallel Processing
Sarjan nimi: Lecture Notes in Computer Science
Numero sarjassa: 9528
Aloitussivu: 185
Lopetussivu: 198
Sivujen määrä: 14
ISBN: 978-3-319-27118-7
DOI: https://doi.org/10.1007/978-3-319-27119-4_13
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.