Title page for ETD etd-08312005-130609

Type of Document Master's Thesis
Author Subramanian, Saravanan
Author's Email Address ssubra3@lsu.edu
URN etd-08312005-130609
Title Heuristics for Memory Access Optimization in Embedded Processors
Degree Master of Science in Electrical Engineering (M.S.E.E.)
Department Electrical & Computer Engineering
Advisory Committee
Advisor Name Title
Ramanujam Jagannathan Committee Chair
Seung-Jong Park Committee Member
Vaidyanathan Ramachandran Committee Member
  • ILP
  • memory access optimization
  • variable partitioning
Date of Defense 2005-07-01
Availability unrestricted
Digital signal processors (DSPs) such as the Motorola 56k are equipped with two memory banks that are accessible in parallel in order to offer high memory bandwidth, which is required for high-performance applications. In order to make efficient use of the memory bandwidth offered by two or more memory banks, compilers for such DSPs should be capable of appropriately partitioning the program variables between the two memory banks and scheduling accesses. If two variables can be accessed simultaneously, then it is essential to have these two variables assigned to two different memory banks. Also if these two variables are in different banks, then instead of using two separate instructions for accessing the variables, both the accesses can be encoded into a single instruction, thereby reducing the code size as well. An efficient heuristic for maximizing the parallel accesses in DSPs with dual memory banks is proposed and evaluated. The heuristic is shown to be very effective on several examples.

Architectures like the M3 DSP have a group memory for the single-instruction multiple-data (SIMD) architecture, for which addressing an element of the group means to access all the elements of that group in parallel, so there is no need for separately addressing each element of the group. Given a variable access sequence for a particular code, instead of separately accessing each one of the variables, if the variables are grouped then the number of memory accesses can be reduced as per SIMD paradigm. An efficient way of forming groups can significantly reduce the memory accesses. Two solutions for this problem are presented in this thesis. First, a novel integer linear programming formulation for forming the groups, thereby reducing the number of memory accesses in DSPs with SIMD architecture is presented. Second, a heuristic based on the solution for optimizing multiple memory bank accesses is presented and evaluated for this problem. Results on several graphs show the effectiveness of the heuristic.

  Filename       Size       Approximate Download Time (Hours:Minutes:Seconds) 
 28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access 
  Subramanian_thesis.pdf 361.53 Kb 00:01:40 00:00:51 00:00:45 00:00:22 00:00:01

Browse All Available ETDs by ( Author | Department )

If you have more questions or technical problems, please Contact LSU-ETD Support.