University of Limerick Institutional Repository

On heuristic solutions to the simple offset assignment problem in address-code optimization

DSpace Repository

Show simple item record Shokry, Hesham El-Boghdadi, Hatem M. 2012-10-30T14:50:21Z 2012-10-30T14:50:21Z 2011
dc.description peer-reviewed en_US
dc.description.abstract The increasing demand for more functionality in embedded systems applications nowadays requires efficient generation of compact code for embedded DSP processors. Because such processors have highly irregular datapaths, compilers targeting those processors are challenged with the automatic generation of optimized code with competent quality comparable to hand-crafted code. A major issue in code-generation is to optimize the placement of program variables in ROM relative to each other so as to reduce the overhead instructions dedicated for address computations. Modern DSP processors are typically shipped with a feature called Address Generation Unit (AGU) that provides efficient address-generation instructions for accessing program variables. Compilers targeting those processors are expected to exploit the AGU to optimize variables assignment. This paper focuses on one of the basic offset-assignment problems; the Simple Offset Assignment (SOA) problem, where the AGU has only one Address Register and no Modify Registers. The notion of Tie-Break Function, TBF, introduced by Leupers and Marwedel [1], has been used to guide the placement of variables in memory. In this paper, we introduce a more effective form of the TBF; the Effective Tie-Breaking Function, ETBF, and show that the ETBF is better at guiding the variables placement process. Underpinning ETBF is the fact that program variables are placed in memory in sequence, with each variable having only two neighbors. We applied our technique to randomly generated graphs as well as to real-world code from the OffsetStone testbench [13]). In previous work [12], our technique showed up to 7% reduction in overhead when applied to randomlygenerated problem instances. We report in this paper on a further experiment of our technique on real-code from the Offsetstone testbench. Despite the substantial improvement our technique has achieved when applied to random problem instances, we found that it shows slight overhead reduction when applied to real-world instances in OffsetStone, which agrees with similar existing experiments. We analyze these results and show that the ETBF defaults to TBF. en_US
dc.language.iso eng en_US
dc.publisher Association for Computing Machinery en_US
dc.relation.ispartofseries ACM Transactions on Embedded Systems Computing (TECS);11(3), article 63
dc.rights "© ACM,2011. 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 ACM Transactions on Embedded Systems Computing (TECS), 11(3), article 63, en_US
dc.subject processors en_US
dc.subject compilers en_US
dc.subject optimizations en_US
dc.subject code size en_US
dc.subject offset assignment en_US
dc.title On heuristic solutions to the simple offset assignment problem in address-code optimization en_US
dc.type info:eu-repo/semantics/conferenceObject en_US
dc.type.supercollection all_ul_research en_US
dc.type.supercollection ul_published_reviewed en_US
dc.contributor.sponsor SFI en_US
dc.relation.projectid 03/CE2/I303_1 en_US
dc.rights.accessrights info:eu-repo/semantics/openAccess en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search ULIR


My Account