On runtime adaptive tile defragmentation for resource management in many-core systems

Before an application can be actually launched in a many-core system, the first thing that needs to be done is to get the application mapped to a number of tiles (cores). Such online application mapping process may unfortunately lead to a serious resource leak problem, referred as tile fragmentation, that free (uncommitted) tiles from any single contiguous region are just inadequate to accommodate the performance needs of an incoming application, although the total number of free tiles may still exceed what is required to service this application. When applications have to be mapped to noncontiguous tiles due to fragmentation, there will be obvious performance penalty due to increased communication distances. As a result, defragmentation that consolidates fragmented tiles needs to be routinely exercised, and this defragmentation process must not introduce high computation overhead that otherwise can adversely impact the system performance. In this paper, we propose a task migration-based adaptive tile defragmentation algorithm that helps consolidate running applications through online task migration. This algorithm relocates the applications' tile regions so that a contiguous free tile region is formed and maintained. By doing so, future applications can be mapped to a region with low communication distance. Both the computation overhead and quality of defragmentation result of the proposed algorithm are adaptively set in response to the system workloads. Enabled by its low overhead, the proposed defragmentation algorithm is an effective resource management enhancement to the existing runtime task-to-tile mapping methods, with as much as 3× system throughput improvement observed in some experiments.