liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
Integrated Optimal Code Generation for Digital Signal Processors
Linköping University, Department of Computer and Information Science, PELAB. Linköping University, The Institute of Technology.
2006 (English)Doctoral thesis, monograph (Other academic)
Abstract [en]

In this thesis we address the problem of optimal code generation for irregular architectures such as Digital Signal Processors (DSPs).

Code generation consists mainly of three interrelated optimization tasks: instruction selection (with resource allocation), instruction scheduling and register allocation. These tasks have been discovered to be NP-hard for most architectures and most situations. A common approach to code generation consists in solving each task separately, i.e. in a decoupled manner, which is easier from a software engineering point of view. Phase-decoupled compilers produce good code quality for regular architectures, but if applied to DSPs the resulting code is of significantly lower performance due to strong interdependences between the different tasks.

We developed a novel method for fully integrated code generation at the basic block level, based on dynamic programming. It handles the most important tasks of code generation in a single optimization step and produces an optimal code sequence. Our dynamic programming algorithm is applicable to small, yet not trivial problem instances with up to 50 instructions per basic block if data locality is not an issue, and up to 20 instructions if we take data locality with optimal scheduling of data transfers on irregular processor architectures into account. For larger problem instances we have developed heuristic relaxations.

In order to obtain a retargetable framework we developed a structured architecture specification language, xADML, which is based on XML. We implemented such a framework, called OPTIMIST that is parameterized by an xADML architecture specification.

The thesis further provides an Integer Linear Programming formulation of fully integrated optimal code generation for VLIW architectures with a homogeneous register file. Where it terminates successfully, the ILP-based optimizer mostly works faster than the dynamic programming approach; on the other hand, it fails for several larger examples where dynamic programming still provides a solution. Hence, the two approaches complement each other. In particular, we show how the dynamic programming approach can be used to precondition the ILP formulation.

As far as we know from the literature, this is for the first time that the main tasks of code generation are solved optimally in a single and fully integrated optimization step that additionally considers data placement in register sets and optimal scheduling of data transfers between different registers sets.

Place, publisher, year, edition, pages
Institutionen för datavetenskap , 2006. , 173 p.
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1021
Keyword [en]
Instruction-level parallelism, integrated code generation, dynamic programming, instruction scheduling, instruction selection, clustered VLIW architecture, integer linear programming, architecture description language
National Category
Computer Science
URN: urn:nbn:se:liu:diva-6568ISBN: 91-85523-69-0OAI: diva2:21877
Public defence
2006-06-07, Planck, Fysikhuset, Campus Valla, Linköpings universitet, Linköping, 13:15 (English)
Available from: 2006-06-09 Created: 2006-06-09 Last updated: 2014-10-08

Open Access in DiVA

fulltext(1266 kB)1895 downloads
File information
File name FULLTEXT01.pdfFile size 1266 kBChecksum SHA-1
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Bednarski, Andrzej
By organisation
PELABThe Institute of Technology
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 1895 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 1073 hits
ReferencesLink to record
Permanent link

Direct link