Defragmentation of tasks in many-core architecture

Anuj Pathania, Vanchinathan Venkataramani, Muhammad Shafique, Tulika Mitra, Jörg Henkel

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Article number2
JournalACM Transactions on Architecture and Code Optimization
Issue number1
StatePublished - Mar 2017


  • Many-core
  • Multiagent systems
  • Task defragmentation

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture


Dive into the research topics of 'Defragmentation of tasks in many-core architecture'. Together they form a unique fingerprint.

Cite this