Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1145/3050437 | TACO |
Keywords | Field | DocType |
Many-core,task defragmentation,multiagent systems | Architecture,Computer science,Task mapping,Contiguity (probability theory),Defragmentation,Parallel computing,Separable space,Real-time computing,Multi-agent system,Thread (computing),Time complexity,Distributed computing | Journal |
Volume | Issue | ISSN |
14 | 1 | 1544-3566 |
Citations | PageRank | References |
2 | 0.37 | 22 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Anuj Pathania | 1 | 181 | 14.97 |
| Vanchinathan Venkataramani | 2 | 76 | 5.85 |
| Muhammad Shafique | 3 | 1945 | 157.67 |
| Tulika Mitra | 4 | 2714 | 135.99 |
| J. Henkel | 5 | 4471 | 366.50 |