TY - JOUR
T1 - Defragmentation of tasks in many-core architecture
AU - Pathania, Anuj
AU - Venkataramani, Vanchinathan
AU - Shafique, Muhammad
AU - Mitra, Tulika
AU - Henkel, Jörg
N1 - Publisher Copyright:
© 2017 ACM.
Copyright:
Copyright 2017 Elsevier B.V., All rights reserved.
PY - 2017/3
Y1 - 2017/3
N2 - Many-cores can execute multiple multithreaded tasks in parallel. A task performs most efficiently when it is executed over a spatially connected and compact subset of cores so that performance loss due to communication overhead imposed by the task's threads spread across the allocated cores is minimal. Over a span of time, unallocated cores can get scattered all over the many-core, creating fragments in the task mapping. These fragments can prevent efficient contiguous mapping of incoming new tasks leading to loss of performance. This problem can be alleviated by using a task defragmenter, which consolidates smaller fragments into larger fragments wherein the incoming tasks can be efficiently executed. Optimal defragmentation of a many-core is an NP-hard problem in the general case. Therefore, we simplify the original problem to a problem that can be solved optimally in polynomial time. In this work, we introduce a concept of exponentially separable mapping (ESM), which defines a set of task mapping constraints on a many-core. We prove that an ESM enforcing many-core can be defragmented optimally in polynomial time.
AB - Many-cores can execute multiple multithreaded tasks in parallel. A task performs most efficiently when it is executed over a spatially connected and compact subset of cores so that performance loss due to communication overhead imposed by the task's threads spread across the allocated cores is minimal. Over a span of time, unallocated cores can get scattered all over the many-core, creating fragments in the task mapping. These fragments can prevent efficient contiguous mapping of incoming new tasks leading to loss of performance. This problem can be alleviated by using a task defragmenter, which consolidates smaller fragments into larger fragments wherein the incoming tasks can be efficiently executed. Optimal defragmentation of a many-core is an NP-hard problem in the general case. Therefore, we simplify the original problem to a problem that can be solved optimally in polynomial time. In this work, we introduce a concept of exponentially separable mapping (ESM), which defines a set of task mapping constraints on a many-core. We prove that an ESM enforcing many-core can be defragmented optimally in polynomial time.
KW - Many-core
KW - Multiagent systems
KW - Task defragmentation
UR - http://www.scopus.com/inward/record.url?scp=85017113766&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85017113766&partnerID=8YFLogxK
U2 - 10.1145/3050437
DO - 10.1145/3050437
M3 - Article
AN - SCOPUS:85017113766
VL - 14
JO - Transactions on Architecture and Code Optimization
JF - Transactions on Architecture and Code Optimization
SN - 1544-3566
IS - 1
M1 - 2
ER -