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

• Item type: SIG Technical Reports(1)
• 公開日: 2014-11-13
• タイトル: Interference-free memory assignment in multi-core chips is NP-hard
• タイトル / 言語: en
• タイトル: Interference-free memory assignment in multi-core chips is NP-hard
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Department of Computer Science and Information Engineering, National Chi Nan University
• 著者所属: National Institute of Informatics / JST, ERATO, Kawarabayashi Large Graph Project.
• 著者所属: Tohoku University
• 著者所属: Tohoku University
• 著者所属(英): en
• 著者所属(英): Department of Computer Science and Information Engineering, National Chi Nan University
• 著者所属(英): en
• 著者所属(英): National Institute of Informatics / JST, ERATO, Kawarabayashi Large Graph Project.
• 著者所属(英): en
• 著者所属(英): Tohoku University
• 著者所属(英): en
• 著者所属(英): Tohoku University
• 著者名: Yi-jungChen; Matias, Korman; Marcel, Roeloffzen; Takeshi, Tokuyama
• 著者名(英): Yi-jung, Chen; Matias, Korman; Marcel, Roeloffzen; Takeshi, Tokuyama
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 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.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2014-AL-150, 号 18, p. 1-6, 発行日 2014-11-13
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会