Evaluating address register assignment and offset assignment algorithms

Abstract : 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 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. Many heuristic-based algorithms are proposed in the literature to approximate solutions to both the variable partitioning and the SOA problems. However, the address-computation overhead of the resulting memory layouts are not accurately evaluated. This article presents an evaluation of memory layouts that uses Gebotys' optimal address-code generation technique. The use of this evaluation method leads to a new optimization problem: the Memory Layout Permutation (MLP) problem. We then use Gebotys' technique and an exhaustive solution to the MLP problem to evaluate heuristic-based offset-assignment algorithms. The memory layouts produced by each algorithm are compared against each other and against the optimal layouts. The results show that even in small access sequences with 12 variables or less, current heuristics may produce memory layouts with address-computation overheads up to two times higher than the overhead of an optimal layout.
Type de document :
Article dans une revue
ACM Transactions on Embedded Computing Systems (TECS), ACM, 2011, 10 (3), pp.37:1-37:22. 〈http://dl.acm.org/citation.cfm?id=1952530〉. 〈10.1145/1952522.1952530〉
Liste complète des métadonnées

Littérature citée [23 références]  Voir  Masquer  Télécharger

Contributeur : Sid Touati <>
Soumis le : mercredi 26 octobre 2011 - 12:01:50
Dernière modification le : jeudi 11 janvier 2018 - 06:21:30
Document(s) archivé(s) le : jeudi 15 novembre 2012 - 10:35:36


Fichiers produits par l'(les) auteur(s)




Johnny Huynh, Nelson José Amaral, Paul Berube, Sid Touati. Evaluating address register assignment and offset assignment algorithms. ACM Transactions on Embedded Computing Systems (TECS), ACM, 2011, 10 (3), pp.37:1-37:22. 〈http://dl.acm.org/citation.cfm?id=1952530〉. 〈10.1145/1952522.1952530〉. 〈inria-00635915〉



Consultations de la notice


Téléchargements de fichiers