Optimal General Offset Assignment

Sven Mallach, Roberto Castañeda Lozano

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

We present an exact approach to the General Offset Assignment problem arising in the domain of address code generation for application specific and digital signal processors. General Offset Assignment is composed of two subproblems, namely to find a permutation of variables in memory and to select a responsible address register for each access to one of these variables. Our method is a combination of established techniques to solve both subproblems using integer linear programming. To the best of our knowledge, it is the first approach capable of solving almost all instances of the established OffsetStone benchmark set to global optimality within reasonable time. We provide a first comprehensive evaluation of the quality of several state-of-the-art heuristics relative to the optimal solutions.
Original languageEnglish
Title of host publicationProceedings of the 17th International Workshop on Software and Compilers for Embedded Systems
Place of PublicationNew York, NY, USA
PublisherAssociation for Computing Machinery, Inc
Number of pages10
ISBN (Print)978-1-4503-2941-5
Publication statusPublished - 10 Jun 2014
Event17th International Workshop on Software and Compilers for Embedded Systems - Schloss Rheinfels, St. Goar, Germany
Duration: 10 Jun 201411 Jun 2014
Conference number: 17


Workshop17th International Workshop on Software and Compilers for Embedded Systems
Abbreviated titleSCOPES 2014
CitySt. Goar
Internet address

Keywords / Materials (for Non-textual outputs)

  • branch-and-cut
  • application specific processors
  • digital signal processors
  • compiler optimization
  • integer programming
  • address code generation
  • offset assignment


Dive into the research topics of 'Optimal General Offset Assignment'. Together they form a unique fingerprint.

Cite this