Future Network-on-Chip (NoC) designs no longer map single cores to each cache slice but rather multiple cores in layouts known as hybrid architectures. Additional proposals have suggested creating reconfigurable hybrid architectures where the OS can revise core-to-cache mappings as required. However, these designs will still be measured by their ability to reduce the average L2 cache delay. Denser core placements with varying core mappings require cache policies with intelligent data placement schemes otherwise there will be no gain to overall system performance as a result of the networked architecture.
Solutions such as OS-directed page placement can reduce some of this delay by placing pages in caches local to the initial requestor. However, due to the page-level allocation granularity compared to line-level data accesses, this policy can still result in shared data existing in remote locations during highly parallelized applications. The most effective network delay reduction alternative is line-level data migration. Data migration policies are designed to take advantage of data temporal locality by assuming data recently used by a processor will be used again in the future. Several variations of migration policies have been proposed to address this demand. However, the physical costs, high computation demands and poor scalability of these methods have reduced their effectiveness in future layouts with hundreds of cores. Additionally, many proposals fail to consider migrating data to a centralized location with even latencies for multiple active cores instead they reduce latency for a single core at the expense of all others. This best average placement is also known as the nearest-neighbor search or the “Two-Dimensional Post Office Problem”.
The proposed Directional Migration solution attempts to solve these problems by providing an autonomous, line-level migration that is responsive to multiple cores with varying access patterns. This design maintains two usage sensors in the form of physical counters on a per-cache-line basis. Migrations traverse only a single network hop to reduce in-transit delays, providing finely-tuned movement and responsiveness to changes in future access patterns. This migration policy is further enhanced by the addition of the Active Neighbor Migration policy. This method is a unique implementation which proposes consideration of data spatial locality. Here each triggered migration causes analysis of logically neighboring lines for potential early migrators.
The Directional Migration solution with the Active Neighbor Migration policy provides a solution to the nearest-neighbor search with a constant physical cost in relation to the number of cores and size of the network while maintaining a linear physical cost in relation to the size of the cache. This is of enormous importance as the size of networks and volume of cores on a single device grow. The physical cost is also independent of the number of shared or migratory lines as the volume of such continues to grow exponentially due to highly parallelized applications. Finally, this solution provides an adaptive response to changes in network layout and core density as necessitated by any NoC architectures.