Algorithms for Optimally Arranging Multicore Memory Structures

  • PDF / 819,954 Bytes
  • 16 Pages / 600.05 x 792 pts Page_size
  • 101 Downloads / 198 Views

DOWNLOAD

REPORT


Research Article Algorithms for Optimally Arranging Multicore Memory Structures Wei-Che Tseng, Jingtong Hu, Qingfeng Zhuge, Yi He, and Edwin H.-M. Sha Department of Computer Science, University of Texas at Dallas, Richardson, TX 75080, USA Correspondence should be addressed to Wei-Che Tseng, [email protected] Received 31 December 2009; Accepted 6 May 2010 Academic Editor: Chun Jason Xue Copyright © 2010 Wei-Che Tseng et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. As more processing cores are added to embedded systems processors, the relationships between cores and memories have more influence on the energy consumption of the processor. In this paper, we conduct fundamental research to explore the effects of memory sharing on energy in a multicore processor. We study the Memory Arrangement (MA) Problem. We prove that the general case of MA is NP-complete. We present an optimal algorithm for solving linear MA and optimal and heuristic algorithms for solving rectangular MA. On average, we can produce arrangements that consume 49% less energy than an all shared memory arrangement and 14% less energy than an all private memory arrangement for randomly generated instances. For DSP benchmarks, we can produce arrangements that, on average, consume 20% less energy than an all shared memory arrangement and 27% less energy than an all private memory arrangement.

1. Introduction When designing embedded systems, the application of the system may be known and fixed at the time of the design. This grants the designer a wealth of information and the complex task of utilizing the information to meet stringent requirements, including power consumption and timing constraints. To meet timing constraints, designers are forced to increase the number of cores, memory, or both. However, adding more cores and memory increases the energy consumption. As more processing cores are added to a processor, the relationships between cores and memories have more influence on the energy consumption of the processor. In this paper, we conduct fundamental research to explore the effects of memory sharing on energy in a multicore processor. We consider a multi-core system where each core may either have a private memory or share a memory with other cores. The Memory Arrangement Problem (MA) decides whether cores will have a private memory or share a memory with adjacent cores to minimize the energy consumption while meeting the timing constraint. Some examples of memory arrangements are shown in Figure 1. The main contributions of this paper are as follows.

(i) We prove that MA without sharing constraints is NPcomplete. (ii) We propose an efficient optimal algorithm for solving linear cases of MA and extend it into an efficient heuristic for solving rectangular cases of MA. (iii) We propose both an optimal algorithm and an efficient heuristic for solving rectangular cases of MA whe