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

Direct link
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.
Linköping Studies in Science and Technology. Thesis, ISSN 0280-7971 ; 1001
National Category
Computer Science
URN: urn:nbn:se:liu:diva-42655Local ID: 67699ISBN: 91-7373-591-4OAI: diva2:263512
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

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
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: 73 hits
ReferencesLink to record
Permanent link

Direct link