Non-restricted Winter 2026 convocation theses and dissertations will be discoverable in ERA on March 16. Congratulations to all our graduates!

Evaluation of Offset Assignment Heuristics

Simple item page
dc.contributor.authorAmaral, Nelson
dc.contributor.authorTouati, Sid-Ahmed-Ali
dc.contributor.authorBerube, Paul
dc.contributor.authorHuynh, Johnny
dc.date.accessioned2025-05-01T21:12:59Z
dc.date.available2025-05-01T21:12:59Z
dc.date.issued2006
dc.descriptionTechnical 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
dc.identifier.doihttps://doi.org/10.7939/R3TH8BM92
dc.language.isoen
dc.rights.urihttp://creativecommons.org/licenses/by/3.0/
dc.subjectCompiler optimization
dc.subjectOffset assignment
dc.titleEvaluation of Offset Assignment Heuristics
dc.typehttp://purl.org/coar/resource_type/c_93fc
ual.jupiterAccesshttp://terms.library.ualberta.ca/public

Files

Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
TR06-04.pdf
Size:
1018.47 KB
Format:
Adobe Portable Document Format
Download

Collections

Technical Reports (Computing Science)