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

Direct link
Integrated Software Pipelining
Linköping University, Department of Computer and Information Science. Linköping University, The Institute of Technology. (Pelab)
2009 (English)Licentiate thesis, monograph (Other academic)
Abstract [en]

In this thesis we address the problem of integrated software pipelining for clustered VLIW architectures. The phases that are integrated and solved as one combined problem are: cluster assignment, instruction selection, scheduling, register allocation and spilling.

As a first step we describe two methods for integrated code generation of basic blocks. The first method is optimal and based on integer linear programming. The second method is a heuristic based on genetic algorithms.

We then extend the integer linear programming model to modulo scheduling. To the best of our knowledge this is the first time anybody has optimally solved the modulo scheduling problem for clustered architectures with instruction selection and cluster assignment integrated.

We also show that optimal spilling is closely related to optimal register allocation when the register files are clustered. In fact, optimal spilling is as simple as adding an additional virtual register file representing the memory and have transfer instructions to and from this register file corresponding to stores and loads.

Our algorithm for modulo scheduling iteratively considers schedules with increasing number of schedule slots. A problem with such an iterative method is that if the initiation interval is not equal to the lower bound there is no way to determine whether the found solution is optimal or not. We have proven that for a class of architectures that we call transfer free, we can set an upper bound on the schedule length. I.e., we can prove when a found modulo schedule with initiation interval larger than the lower bound is optimal.

Experiments have been conducted to show the usefulness and limitations of our optimal methods. For the basic block case we compare the optimal method to the heuristic based on genetic algorithms.

This work has been supported by The Swedish national graduate school in computer science (CUGS) and Vetenskapsrådet (VR).

Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press , 2009. , 88 p.
Linköping Studies in Science and Technology. Thesis, ISSN 0280-7971 ; 1393
Keyword [en]
Code generation, compilers, instruction scheduling, register allocation, spill code generation, modulo scheduling, integer linear programming, genetic programming.
National Category
Computer Science
URN: urn:nbn:se:liu:diva-16170Local ID: LIU-TEK-LIC-2009:1ISBN: 978-91-7393-699-6OAI: diva2:133729
2009-02-16, Alan Turing, Campus Valla, Linköpings universitet, Linköping, 13:15 (English)
Available from: 2009-01-14 Created: 2009-01-07 Last updated: 2014-10-08Bibliographically approved

Open Access in DiVA

Integrated Software Pipelining(716 kB)791 downloads
File information
File name FULLTEXT02.pdfFile size 716 kBChecksum SHA-512
Type fulltextMimetype application/pdf
Cover(55 kB)25 downloads
File information
File name COVER01.pdfFile size 55 kBChecksum SHA-512
Type coverMimetype application/pdf

Search in DiVA

By author/editor
Eriksson, Mattias
By organisation
Department of Computer and Information ScienceThe Institute of Technology
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 791 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: 582 hits
ReferencesLink to record
Permanent link

Direct link