| Presentation | 2014/11/13 Interference-free memory assignment in multi-core chips is NP-hard YI-JUNG CHENI, MATIAS KORMAN, MARCEL ROELOFFZEN, TAKESHI TOKUYAMA, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | |
| Paper # | Vol.2014-AL-150 No.18 |
| Date of Issue |
| Conference Information | |
| Committee | MSS |
|---|---|
| Conference Date | 2014/11/13(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Mathematical Systems Science and its applications(MSS) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Interference-free memory assignment in multi-core chips is NP-hard |
| Sub Title (in English) | |
| Keyword(1) | |
| 1st Author's Name | YI-JUNG CHENI |
| 1st Author's Affiliation | Department of Computer Science and Information Engineering, National Chi Nan University() |
| 2nd Author's Name | MATIAS KORMAN |
| 2nd Author's Affiliation | National Institute of Informatics:JST, ERATO, Kawarabayashi Large Graph Project |
| 3rd Author's Name | MARCEL ROELOFFZEN |
| 3rd Author's Affiliation | Tohoku University |
| 4th Author's Name | TAKESHI TOKUYAMA |
| 4th Author's Affiliation | Tohoku University |
| Date | 2014/11/13 |
| Paper # | Vol.2014-AL-150 No.18 |
| Volume (vol) | vol.114 |
| Number (no) | 313 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |