OPTIMIST project homepage

• Project members
• Project goals
• Project description
• Project publications
• Software download
• Project funding and cooperation partners

Project members:
Christoph Kessler, project leader
Mattias Eriksson, PhD

Former project members:
Andrzej Bednarski, PhD 2006
Previous master thesis students: Anders Edqvist, David Landén, Yuan Yongyi, Andreas Rehnströmer, Lukas Kemmer, Oskar Skoog

Project goals:
We develop optimization algorithms for integrated code generation, where optimal can be in terms of execution time, register/stack space, energy, or program length, and we allow additional constraints on time (deadlines), space (available registers), energy (energy budget), or length (program memory size). Integrated code generation means that we simultaneously solve instruction scheduling, instruction selection, partitioning, and register allocation as a combined optimization problem. While our methods work for standard processors as well, an integrated approach is crucial especially for irregular VLIW and DSP architectures to achieve high code quality as required in time-critical regions of embedded applications. A method that is capable of computing optimal solutions for non-trivial problem sizes will be useful to assess the quality of fast heuristics and to evaluate the potential of a given processor architecture for a fixed application. As a byproduct, an optimal method can often be relaxed to faster heuristics, too. We develop and implement our optimization algorithms in our retargetable optimizing code generator framework called OPTIMIST.

Project description:
Previous work focused on a generic dynamic programming approach for optimal integrated code generation at the basic-block level. The method allows to optimize for execution time, register/temporary space, energy consumption, and constrained and mixed optimization goals. Domain-specific properties are exploited to prune the solution space and terminate construction as early as possible. The method allows to derive optimal code for basic blocks of small and (in the case of a single register set) medium size. For larger problem instances, the method can be seamlessly relaxed to a heuristic.
Another optimization engine is based on integer linear programming. This method has been successfully applied for fully integrated code generation at both basic block level and loop level (integrated software pipelining).
We also have developed heuristics to tackle really large problem instances. A recently developed one is based on genetic programming for the basic block level.
All these methods support also clustered VLIW architectures. Note that clustering makes the code optimization problem much more complex compared to the homogeneous single-cluster VLIW case.
Our integrated code generator framework OPTIMIST is retargetable: We use our XML-based architecture description language xADML to specify the target processor architecture for the code generator. Our method can handle code selection with tree, DAG and forest patterns on a low-level intermediate representation of the program. Case studies done so far involve the processors TI C62x, ARM9E and Motorola MC56K.

• C. Kessler: Final report for CENIIT project 01.06 (2001-2007) Optimization algorithms for integrated code generation , Jan. 2008

Implementation:
We use LCC as C front end and the LCC-IR (node DAGs) as intermediate representation. A recently finished interface from the Open Research Compiler (ORC) allows to use ORC's high-level transformations and additional frontends for C++ and Fortran77. xADML is parsed with Xerces. The rest of the system is written in C++, using the Boost library. DAGs and solution spaces are visualized with VCG.

Project publications:

1. Christoph Kessler, Andrzej Bednarski: A Dynamic Programming Approach to Optimal Integrated Code Generation. Proc. ACM SIGPLAN 2001 Workshop on Languages, Compilers, and Tools for Embedded Systems (LCTES'2001), June 22-23, 2001, Snowbird, Utah, USA. PDF, Postscript, PowerPoint slides. Details on the experimental evaluation of timeopt.
2. Christoph Kessler, Andrzej Bednarski: Optimal Integrated Code Generation for Clustered VLIW Architectures. Proc. ACM SIGPLAN 2002 Conference on Languages, Compilers, and Tools for Embedded Systems (LCTES-SCOPES'02), June 19-21, 2002, Berlin, Germany. Postscript, PDF, PDF slides.
3. Christoph Kessler, Andrzej Bednarski: Optimal Integrated Code Generation for VLIW Architectures. Proc. CPC'03 Tenth international workshop on compilers for parallel computers, Amsterdam, The Netherlands, Jan. 2003.
4. Andrzej Bednarski: A Dynamic Programming Approach to Optimal Retargetable Code Generation for Irregular Architectures. Licentiate thesis, Linköping studies in science and technology Thesis No. 1001, Jan. 2003.
5. Andrzej Bednarski, Christoph W. Kessler: Exploiting Symmetries for Optimal Integrated Code Generation. Proc. Int. Conf. on Embedded Systems and Applications (ESA'04), June 21-24, 2004, Las Vegas, Nevada, USA.
6. Andrzej Bednarski, Christoph W. Kessler: Energy-Optimal Integrated VLIW Code Generation. Proc. of CPC'04 11th Int. Workshop on Compilers for Parallel Computers, Seeon, Germany, July 2004.
7. Anders Edqvist: High-level optimizations for OPTIMIST.
   Master thesis LITH-IDA-EX-04/078-SE, Linköpings universitet, Nov. 2004.
8. David Landen: ARM9E Processor Specification for OPTIMIST. Master thesis LITH-IDA-EX-05/022-SE, Linköpings universitet, Feb. 2005.
9. Christoph W. Kessler, Andrzej Bednarski: Optimal integrated code generation for VLIW architectures.
   Concurrency and Computation: Practice and Experience 18: 1353-1390, Wiley, 2006.
10. Christoph W. Kessler, Andrzej Bednarski: Classification and generation of schedules for VLIW processors.
    Proc. of CPC'06 12th Int. Workshop on Compilers for Parallel Computers, A Coruna, Spain, Jan. 2006, pp. 60-72.
11. Andrzej Bednarski, Christoph W. Kessler: Integer Linear Programming versus Dynamic Programming for Optimal Integrated VLIW Code Generation.
    Proc. of CPC'06 12th Int. Workshop on Compilers for Parallel Computers, A Coruna, Spain, Jan. 2006, pp. 73-85.
12. Yuan Yongyi: Optimization of amplifier code for the Motorola DSP 56367 processor with OPTIMIST.
    Master thesis, Linköping university - Institute of Technology, April 2006.
13. Andreas Rehnströmer: A Graphical Editor for Writing xADML Processor Specifications.
    Master thesis LITH-IDA-EX-ING--06/006--SE, Linköping university - Institute of Technology, May 2006.
14. Andrzej Bednarski: Optimal Integrated Code Generation for Digital Signal Processors.
    PhD thesis, Linköping university - Institute of Technology, Linköping, Sweden, June 2006.
15. Andrzej Bednarski, Christoph Kessler:
    Optimal Integrated VLIW Code Generation with Integer Linear Programming.
    Proc. Euro-Par 2006 conference, Springer LNCS 4128, pp. 461-472, Aug. 2006.
16. Christoph Kessler, Andrzej Bednarski, Mattias Eriksson:
    Classification and generation of schedules for VLIW processors.
    Concurrency and Computation - Practice and Experience 19:2369-2389 (2007).
17. Mattias Eriksson, Oskar Skoog, Christoph Kessler:
    Optimal vs. Heuristic Integrated Code Generation for Clustered VLIW Architectures.
    Proc. 11th International Workshop on Software and Compilers for Embedded Systems (SCOPES 2008), München, Germany, 2008.
18. Mattias Eriksson, Christoph Kessler:
    Integrated Modulo Scheduling for Clustered VLIW Architectures.
    Proc. HiPEAC-2009 High-Performance and Embedded Architecture and Compilers, Paphos, Cyprus, Jan. 2009. Springer LNCS 5409, pp. 65-79.
19. Mattias Eriksson:
    Integrated Software Pipelining.
    Licentiate thesis No. 1393, Linköping university, Feb. 2009. Linköping University Electronic Press, ISBN 978-91-7393-699-6.
20. Christoph Kessler:
    Compiling for VLIW DSPs.
    Book chapter, 38 pages, accepted for publication in: S. S. Bhattacharyya, E. Deprettere, R. Leupers, and J. Takala, eds., Handbook on Signal Processing Systems, Springer, to appear 2010.
21. Mattias Eriksson and Christoph W. Kessler.
    Integrated Code Generation for Loops.
    Accepted for publication in ACM Transactions on Embedded Computing Systems, 2010
22. Mattias Eriksson and Christoph W. Kessler.
    Integrated Offset Assignment.
    Proc. ODES-2011, Chamonix, France, April 2011.
23. Mattias Eriksson:
    Integrated Code Generation.
    PhD thesis No. 1375, Dept. of Computer and Information Science, Linköping University, June 2011.

Software download:
The OPTIMIST framework with complete source code and example xADML specifications for ARM9E, ARM9E Thumb, MC 56K DSP and TI C62x, installation guide and documentation, is available on the page http://www.ida.liu.se/~chrke/optimist/download.html
Comments and suggestions are welcome!

Acknowledgements:

The integrated software pipelining branch of this project was funded 2006-2008 and 2010-2012 by a project grant from the Swedish national science foundation (Vetenskapsrådet).

The OPTIMIST main project was supported 2001-2007 as a long-term research effort by CENIIT.
During July 2004-June 2005 and July 2006-Dec. 2007 it was also supported by SSF project RISE, subproject RISE-OPTIMIST resp. subproject RISE-CODECOMP.

The case study for ARM9E was supported by IAR Systems AB.
The case study for MC56K is a cooperation with Softube AB.

Industrial cooperation:
IAR Systems AB, Uppsala
Ericsson AB Softlab, Linköping