University of Limerick
Browse
2008_Shokry.pdf (119.31 kB)

A new heuristic for SOA problem based on effective tie break function

Download (119.31 kB)
conference contribution
posted on 2012-08-01, 14:13 authored by Hesham Shokry, Hatem M. El-Boghdadi, Samir I. Shaheen
Producing efficient and compact code for embedded DSP processors is very important for nowadays faster and smaller size devices. Because such processors have highly irregular data-path, conventional code generation techniques typically result in inefficient code. Embedded software compilers are expected to make use of the Address Generation Unit (AGU); a feature commonly found in modern embedded DSP processors. This helps in generating optimized offset assignments to program variables in memory, and consequently minimize the overhead instructions dedicated for addresses computations. This paper addresses one of the problems of code optimizations; namely Simple Offset Assignment (SOA) problem. In this paper, we study the tie break function introduced by Leupers and Marwedel [1] and show that this function does not represent the actual tie break that could happen in the graph. Then we introduce the notion of Effective Tie Break Function (ETBF) and use it in proposing a new algorithm for solving the SOA problem. We apply the algorithm to randomly generated graphs. Our results show improvement in offset assignment cost of up to 7% over well known offset assignment algorithms [1,2,3]..

History

Publication

SCOPES '08 Proceedings of the 11th international workshop on Software & compilers for embedded systems;pp. 53-59

Publisher

Association for Computing Machinery

Note

peer-reviewed

Rights

"© ACM, 2008. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in SCOPES '08 Proceedings of the 11th international workshop on Software & compilers for embedded systems,pp. 53-59, http://dl.acm.org/citation.cfm?id=1361106

Language

English

Usage metrics

    University of Limerick

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC