Title page for ETD etd-04152004-153146

Type of Document Dissertation
Author Pinnepalli, Sai
Author's Email Address sai@lsu.edu
URN etd-04152004-153146
Title Address Optimizations for Embedded Processors
Degree Doctor of Philosophy (Ph.D.)
Department Computer Science
Advisory Committee
Advisor Name Title
Doris L. Carver Committee Chair
J. Ramanujam Committee Co-Chair
Donald H. Kraft Committee Member
Jinpyo Hong Committee Member
S. S. Iyengar Committee Member
Thomas Shaw Dean's Representative
  • offset assignment
  • address optimization
  • GOA
  • SOA
  • commutative transformation
  • embedded processors
Date of Defense 2004-04-14
Availability unrestricted
Embedded processors that are common in electronic devices perform a limited set of tasks compared to general-purpose processor systems. They have limited resources which have to be efficiently used. Optimal utilization of program memory needs a reduction in code size which can be achieved by eliminating unnecessary address computations i.e., generate optimal offset assignment that utilizes built-in addressing modes.

Single offset assignment (SOA) solutions, used for processors with one address register; start with the access sequence of variables to determine the optimal assignment. This research uses the basic block to commutatively transform statements to alter the access sequence. Edges in the access graphs are classified into breakable and unbreakable edges. Unbreakable edges are preferred when selecting edges for the assignment. Breakable edges are used to commutatively transform statements such that the assignment cost is reduced.

The use of a modify register in some processors allows the address to be modified by a value in MR in addition to post-increment/decrement modes. Though finding the most beneficial value of MR is a common practice, this research shows that modifying the access sequence using edge fold, node swap, and path interleave techniques for an MR value of two has significant benefit.

General offset assignment requires variables in the access sequence to be partitioned to various address registers. Use of the node degree in the access graph demonstrates greater benefit than using edge weights and frequency of variables.

The Static Single Assignment (SSA) form of the basic block introduces new variables to an access graph, making it sparser. Sparser access graphs usually have lower assignment costs. The SSA form allows reuse of variable space based on variable lifetimes.

Offset assignment solutions may be improved by incrementally assignment based on uncovered edges, providing the best cost improvement. This heuristic considers improvements due to all uncovered edges.

Optimization techniques have primarily been edge-based. Node-based SOA technique has been tested for use with commutative transformations and shown to be better than edge-based heuristics.

Heuristics developed in this research perform address optimizations for embedded processors, employing new techniques that lower address computation costs.

  Filename       Size       Approximate Download Time (Hours:Minutes:Seconds) 
 28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access 
  Pinnepalli_dis.pdf 1.57 Mb 00:07:16 00:03:44 00:03:16 00:01:38 00:00:08

Browse All Available ETDs by ( Author | Department )

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