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

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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.
Series
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
Identifiers
URN: urn:nbn:se:liu:diva-6568ISBN: 91-85523-69-0 (print)OAI: oai:DiVA.org:liu-6568DiVA: diva2:21877
Public defence
2006-06-07, Planck, Fysikhuset, Campus Valla, Linköpings universitet, Linköping, 13:15 (English)
Opponent
Supervisors
Available from: 2006-06-09 Created: 2006-06-09 Last updated: 2014-10-08

Open Access in DiVA

fulltext(1266 kB)1958 downloads
File information
File name FULLTEXT01.pdfFile size 1266 kBChecksum MD5
ce9f651373c94ff787fe099a647730e8075ec40c21d3fc6be86a167b367e2908e79dc893
Type fulltextMimetype application/pdf

Authority records BETA

Bednarski, Andrzej

Search in DiVA

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

Search outside of DiVA

GoogleGoogle Scholar
Total: 1958 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

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 1162 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf