Evaluation of Offset Assignment Heuristics

• Author(s) / Creator(s)

  • Amaral, Nelson
  • Touati, Sid-Ahmed-Ali
  • Berube, Paul
  • Huynh, Johnny

• Technical report TR06-04. In digital signal processors (DSPs) variables are accessed using k address registers. The problem of finding a memory layout, for a set of variables, that minimizes the address-computation overhead is known as the General Offset Assignment (GOA) Problem. The most common approach to this problem in the literature is to partition the set of variables into k partitions and to assign each partition to an address register. Thus effectively decomposing the GOA problem into several Simple Offset Assignment (SOA) problems. The complementary problem of finding the addressing code that minimizes address-computation overhead for a fixed memory layout and a fixed instruction schedule has been solved by Gebotys. This paper implements Gebotys' solution using an integer linear programming formulation. To find the memory layouts that have the minimum address-computation overhead, the overhead for all possible memory layouts for a given sequence of instructions can be computed. Since the number of possible memory layouts grows exponentially, we can only find the memory layout with minimum overhead for access sequences with less than 12 variables. The quality of the solutions obtained with heuristic-based algorithms proposed in the literature are then compared with the set of all possible solutions. | TRID-ID TR06-04

• Date created

  2006

• Subjects / Keywords

  • Compiler optimization
  • Offset assignment

• Type of Item

  Report

• DOI

  https://doi.org/10.7939/R3TH8BM92

• License

  Attribution 3.0 International