Interference-free memory assignment in multi-core chips is NP-hard

We study the problem of finding a memory assignment for multi-core systems with 3D-stacked reconfiguration SRAMs. In this architecture, the SRAMs are partitioned into fixed sized tiles and are stacked on top of a layer of IP cores. The SRAM tiles are connected by a 2D mesh network, and each IP core has a vertical access port connected to the SRAM tile stacked on top of it. At run-time, the SRAM tiles can be divided into several memory areas, where each of the memory area is composed of a set of contiguous SRAM tiles and is accessed by only a single IP core. Targeting this architecture we study the problem of assigning memory tiles to processors. Given the capacity of the SRAM tiles and the memory requirement of each IP core, we want to assign memory tiles to processors. Specifically we wish to find an interference-free memory assignment. That is, a memory assignment where each processor has the block containing its access port assigned to it, and for each processor all its memory blocks are orthogonally connected on the memory grid. We show by a reduction from monotone planar 3-SAT that it is NP-complete to find an interference-free memory assignment. That is, to find a memory assignment where the memory area of each core is connected and contains its access port.