More General Optimal Offset Assignment

Sven Mallach

Abstract


This manuscript presents exact approaches to the general offset assignment problem arising in the address code generation phase of compilers for application-specific processors. First, integer programming models for architecture-dependent and theoretically motivated special cases of the problem are established. Then, these models are extended to provide the first widely applicable formulations for the most general problem setting, supporting processors with several address registers and complex addressing capabilities. Existing heuristics are similarly extended and practical applicability of the proposed methods is demonstrated by experimental evaluation using an established and large benchmark set. The experiments allow us to study the impact of exploiting more complex memory addressing capabilities on the address computation costs of real-world programs. We also show how to integrate operand reordering techniques for commutative instructions into existing solution approaches.

Keywords


Compiler optimization; Application-specific processors; Address code generation; Offset assignment; Integer programming

Full Text:

PDF

References


Sunil Atri, Jagannathan Ramanujam, and Mahmut T. Kandemir. Improving offset assignment on embedded processors using transformations. In Mateo Valero, Viktor K. Prasanna, and Sriram Vajapeyam, editors, Proc. of the 7th International Conference on High Performance Computing (HiPC’00), Bangalore, India, December 17–20, 2000, volume 1970 of Lecture Notes in Computer Science, pages 367–374. Springer, 2000. doi:10.1007/3-540-44467-X_33.

David H. Bartley. Optimizing stack frame accesses for processors with restricted addressing modes. Softw., Pract. Exper., 22(2):101–110, 1992. doi:10.1002/spe.4380220202.

Rainer E. Burkard, Mauro Dell’Amico, and Silvano Martello. Assignment Problems. SIAM, 2009. URL: http://www.ec-securehost.com/SIAM/OT106.html.

Yoonseo Choi and Taewhan Kim. Address assignment combined with scheduling in DSP code generation. In Proc. of the 39th Design Automation Conference (DAC’02), New Orleans, LA, USA, June 10–14, 2002, pages 225–230. ACM, 2002. doi:10.1145/513918.513975.

George B. Dantzig, David R. Fulkerson, and Selmer M. Johnson. Solution of a large-scale traveling-salesman problem. Operations Research, 3:393–410, 1954.

Balázs Dezso, Alpár Jüttner, and Péter Kovács. LEMON – an open source C++ graph template library. Electr. Notes Theor. Comput. Sci., 264(5):23–45, 2011. doi:10.1016/j.entcs.2011.06.003

Catherine H. Gebotys. DSP address optimization using a minimum cost circulation technique. In Ralph H. J. M. Otten and Hiroto Yasuura, editors, Proc. of the 1997 IEEE/ACM International Conference on Computer-Aided Design (ICCAD’97), San Jose, CA, USA, November 9–13, 1997, pages 100–103. IEEE Computer Society / ACM, 1997. doi:10.1109/ICCAD.1997.643380.

Catherine H. Gebotys. A minimum-cost circulation approach to DSP address-code generation. IEEE Trans. on CAD of Integrated Circuits and Systems, 18(6):726–741, 1999. doi:10.1109/43.766724.

Johnny Huynh, José Nelson Amaral, Paul Berube, and Sid Ahmed Ali Touati. Evaluating address register assignment and offset assignment algorithms. ACM Trans. Embedded Comput. Syst., 10(3):37, 2011. doi:10.1145/1952522.1952530.

IBM. IBM ILOG CPLEX Optimization Studio Version 12.6, 2013.

Michael Jünger and Sven Mallach. Solving the simple offset assignment problem as a traveling salesman. In Henk Corporaal and Sander Stuijk, editors, Proc. of the International Workshop on Software and Compilers for Embedded Systems

(M-SCOPES’13), Sankt Goar, Germany, June 19–21, 2013, pages 31–39. ACM, 2013. doi:10.1145/2463596.2463601.

Zoltán Király and Péter Kovács. Efficient implementations of minimum-cost flow algorithms. Acta Universitatis Sapientiae, Informatica, 4(1):67– 118, 2012. URL: http://www.acta.sapientia.ro/acta-info/C4-1/info41-5.pdf.

Eugene Lawler. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, 1976.

Rainer Leupers. Offset assignment showdown: Evaluation of DSP address code optimization algorithms. In Görel Hedin, editor, Proc. of the 12th International Conference on Compiler Construction (CC’03), held as Part of the Joint European Conferences on Theory and Practice of Software (ETAPS’03), Warsaw, Poland, April 7–11, 2003, volume 2622 of Lecture Notes in Computer Science, pages 290–302. Springer, 2003. doi:10.1007/3-540-36579-6_21.

Rainer Leupers and Fabian David. A uniform optimization technique for offset assignment problems. In Francky Catthoor, editor, Proc. of the 11th International Symposium on System Synthesis (ISSS’98), Hsinchu, Taiwan, December 2–4, 1998, pages 3–8. ACM / IEEE Computer Society, 1998. doi:10.1109/ISSS.1998.730589.

Rainer Leupers and Peter Marwedel. Algorithms for address assignment in DSP code generation. In Proc. of the 1996 IEEE/ACM International Conference on Computer-Aided Design (ICCAD’96), pages 109–112, 1996. doi:10.1109/ICCAD.1996.569409.

Stan Yi-Huang Liao. Code generation and optimization for embedded digital signal processors. PhD thesis, Massachusetts Institute of Technology, 1996. URL: http://hdl.handle.net/1721.1/11048.

Sven Mallach and Roberto Castañeda Lozano. Optimal general offset assignment. In Henk Corporaal and Sander Stuijk, editors, Proc. of the 17th International Workshop on Software and Compilers for Embedded Systems (SCOPES’14), Sankt Goar, Germany, June 10–11, 2014, pages 50–59. ACM, 2014. doi:10.1145/2609248.2609251.

Garth P. McCormick. Computability of global solutions to factorable nonconvex programs: Part I – convex underestimating problems. Mathematical Programming, 10(1):147–175, 1976. doi:10.1007/BF01580665.

Ozcan Ozturk, Mahmut T. Kandemir, and Suleyman Tosun. An ILP based approach to address code generation for digital signal processors. In Gang Qu, Yehea I. Ismail, Narayanan Vijaykrishnan, and Hai Zhou, editors, Proc. of the 16th ACM Great Lakes Symposium on VLSI (GLSVLSI’06), Philadelphia, PA, USA, April 30 – May 1, 2006, pages 37–42. ACM, 2006. doi:10.1145/1127908.1127919.

Manfred Padberg and Giovanni Rinaldi. A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Rev., 33(1):60–100, 2 1991. doi:10.1137/1033004.

Manfred W. Padberg and Mendu R. Rao. Odd minimum cut-sets and b-matchings. Mathematics of Operations Research, 7(1):67–80, 1982. URL: http://www.jstor.org/stable/3689360.

Amit Rao and Santosh Pande. Storage assignment optimizations to generate compact and efficient code on embedded dsps. In Barbara G. Ryder and Benjamin G. Zorn, editors, Proc. of the 1999 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI’99), Atlanta, Georgia, USA, May 1–4, 1999, pages 128–138. ACM, 1999. doi:10.1145/301618.301653.

Nobuhiko Sugino, Satoshi Iimuro, Akinori Nishi- hara, and Nobuo Fujii. DSP code optimization utilizing memory addressing operation. IEICE Transactions on Fundam. of Electr., Commu. and Comp. Sc., 79(8):1217–1224, 1996.

Bernhard Wess and Martin Gotschlich. Optimal DSP memory layout generation as a quadratic assignment problem. In Proc. of the 1997 IEEE International Symposium on Circuits and Systems (ISCAS’97), volume 3, pages 1712–1715, Jun 1997. doi:10.1109/ISCAS.1997.621465.




DOI: https://doi.org/10.4230/LITES-v002-i001-a002

URN (PDF): http://nbn-resolving.de/urn:nbn:de:0030-lites-v002-i001-a002-pdf0

Copyright (c) 2015 Sven Mallach

Creative Commons License CC BY
This work is licensed under a Creative Commons Attribution 3.0 Germany License (CC BY 3.0 DE).

License URL: http://creativecommons.org/licenses/by/3.0/de/deed.en
To make this site work properly, we sometimes place small data files called cookies on your device. Cookies are only here to manage user sessions. Cookies aren’t required for simply visiting the site and read content.
OK




Published by the European Design and Automation Association (EDAA) \ EMbedded Systems Special Interest Group (EMSIG) and Schloss Dagstuhl -- Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing. | Imprint | Data Privacy Policy