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
A dynamic programming approach to optimal retargetable code generation for irregular architectures
Linköping University, Department of Computer and Information Science, PELAB - Programming Environment Laboratory. Linköping University, The Institute of Technology.
2002 (English)Licentiate 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 tasks: instruction selection, instruction scheduling and register allocation. These tasks have been discovered to be NP-difficult for most of the 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 an engineering point of view. Decoupled phase based compilers produce good code quality for regular architectures, but if applied to DSPs the resulting code is of significantly lower performance due to strong interdependencies between the different tasks.

We report on a novel method for fully integrated code generation based on dynamic programming. It handles the most important tasks of code generation in a single optimization step and produces 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 on irregular processor architectures into account.

In order to obtain a retargetable framework we developed a first version of a structured hardware description language, ADML, which is based on XML. We implemented a prototype framework of such a retargetable system for optimal code generation.

As far as we know from the literature, this is 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 registers. 

Place, publisher, year, edition, pages
Linköping: Linköpings universitet , 2002. , 117 p.
Series
Linköping Studies in Science and Technology. Thesis, ISSN 0280-7971 ; 1001
National Category
Computer Science
Identifiers
URN: urn:nbn:se:liu:diva-42655Local ID: 67699ISBN: 91-7373-591-4 (print)OAI: oai:DiVA.org:liu-42655DiVA: diva2:263512
Presentation
2003-01-30, Alan Turing, Hus B, Linköpings Universitet, Linköping, 10:15 (Swedish)
Available from: 2009-10-10 Created: 2009-10-10 Last updated: 2013-11-08

Open Access in DiVA

No full text

Authority records BETA

Bednarski, Andrzej

Search in DiVA

By author/editor
Bednarski, Andrzej
By organisation
PELAB - Programming Environment LaboratoryThe Institute of Technology
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 73 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