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

Direct link
BETA
Bednarski, Andrzej
Publications (10 of 12) Show all publications
Kessler, C., Bednarski, A. & Eriksson, M. (2007). Classification and generation of schedules for VLIW processors. Concurrency, 19, 2369-2389
Open this publication in new window or tab >>Classification and generation of schedules for VLIW processors
2007 (English)In: Concurrency, ISSN 1040-3108, E-ISSN 1096-9128, Vol. 19, p. 2369-2389Article in journal (Refereed) Published
Abstract [en]

We identify and analyze different classes of schedules for instruction-level parallel processor architectures. The classes are induced by various common techniques for generating or enumerating them, such as integer linear programming or list scheduling with backtracking. In particular, we study the relationship between VLIW schedules and their equivalent linearized forms (which may be used, e.g., with superscalar processors), and we identify classes of VLIW schedules that can be created from a linearized form using an in-order VLIW compaction heuristic, which is just the static equivalent of the dynamic instruction dispatch algorithm of in-order issue superscalar processors. We formulate and give a proof of the dominance of greedy schedules for instruction-level parallel architectures where all instructions have multiblock reservation tables, and we show how scheduling anomalies can occur in the presence of instructions with non-multiblock reservation tables. We also show that, in certain situations, certain schedules generally cannot be constructed by incremental scheduling algorithms that are based on topological sorting of the data dependence graph. We also discuss properties of strongly linearizable schedules, out-of-order schedules and non-dawdling schedules, and show their relationships to greedy schedules and to general schedules. We summarize our findings as a hierarchy of classes of VLIW schedules. Finally we provide an experimental evaluation showing the sizes of schedule classes in the above hierarchy, for different benchmarks and example VLIW architectures, including a single-cluster version of the TI C62x DSP processor and variants of that. Our results can sharpen the interpretation of the term optimality used with various methods for optimal VLIW scheduling, and help to identify sets of schedules that can be safely ignored when searching for a time-optimal schedule.

Keywords
instruction-level parallelism, instruction scheduling, code generation, code compaction, integer linear programming, VLIW architecture, superscalar processor
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-40156 (URN)10.1002/cpe.1175 (DOI)52451 (Local ID)52451 (Archive number)52451 (OAI)
Available from: 2009-10-10 Created: 2009-10-10 Last updated: 2018-01-13
Kessler, C. & Bednarski, A. (2006). Classification and generation of schedules for VLIW processors. In: 2th Int. Workshop on Compilers for Parallel Computers,2006 (pp. 60).
Open this publication in new window or tab >>Classification and generation of schedules for VLIW processors
2006 (English)In: 2th Int. Workshop on Compilers for Parallel Computers,2006, 2006, p. 60-Conference paper, Published paper (Refereed)
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-35766 (URN)28498 (Local ID)28498 (Archive number)28498 (OAI)
Available from: 2009-10-10 Created: 2009-10-10 Last updated: 2018-01-13
Bednarski, A. & Kessler, C. (2006). Integer Linear Programming versus Dynamic Programming for Optimal Integrated VLIW Code Generation. In: 12th Int. Workshop on Compilers for Parallel Computers,2006 (pp. 73).
Open this publication in new window or tab >>Integer Linear Programming versus Dynamic Programming for Optimal Integrated VLIW Code Generation
2006 (English)In: 12th Int. Workshop on Compilers for Parallel Computers,2006, 2006, p. 73-Conference paper, Published paper (Refereed)
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-35767 (URN)28499 (Local ID)28499 (Archive number)28499 (OAI)
Available from: 2009-10-10 Created: 2009-10-10 Last updated: 2018-01-13
Bednarski, A. (2006). Integrated Optimal Code Generation for Digital Signal Processors. (Doctoral dissertation). : Institutionen för datavetenskap
Open this publication in new window or tab >>Integrated Optimal Code Generation for Digital Signal Processors
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. p. 173
Series
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1021
Keywords
Instruction-level parallelism, integrated code generation, dynamic programming, instruction scheduling, instruction selection, clustered VLIW architecture, integer linear programming, architecture description language
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-6568 (URN)91-85523-69-0 (ISBN)
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: 2018-01-13
Kessler, C. & Bednarski, A. (2006). Optimal integrated code generation for VLIW architectures. Concurrency and Computation, 18(11), 1353-1390
Open this publication in new window or tab >>Optimal integrated code generation for VLIW architectures
2006 (English)In: Concurrency and Computation, ISSN 1532-0626, E-ISSN 1532-0634, Vol. 18, no 11, p. 1353-1390Article in journal (Refereed) Published
Abstract [en]

We present a dynamic programming method for optimal integrated code generation for basic blocks that minimizes execution time. It can be applied to single-issue pipelined processors, in-order-issue superscalar processors, VLIW architectures with a single homogeneous register set, and clustered VLIW architectures with multiple register sets. For the case of a single register set, our method simultaneously copes with instruction selection, instruction scheduling, and register allocation. For clustered VLIW architectures, we also integrate the optimal partitioning of instructions, allocation of registers for temporary variables, and scheduling of data transfer operations between clusters. Our method is implemented in the prototype of a retargetable code generation framework for digital signal processors (DSPs), called OPTIMIST. We present results for the processors ARM9E, TI C62x, and a single-cluster variant of C62x. Our results show that the method can produce optimal solutions for small and (in the case of a single register set) medium-sized problem instances with a reasonable amount of time and space. For larger problem instances, our method can be seamlessly changed into a heuristic. Copyright (c) 2006 John Wiley & Sons, Ltd.

Keywords
instruction-level parallelism, integrated code generation, dynamic programming, instruction scheduling, instruction selection, clustered VLIW architecture, data partitioning
National Category
Engineering and Technology
Identifiers
urn:nbn:se:liu:diva-45996 (URN)10.1002/cpe.1012 (DOI)
Available from: 2009-10-11 Created: 2009-10-11 Last updated: 2017-12-13
Bednarski, A. & Kessler, C. (2006). Optimal integrated VLIW code generation with Integer Linear Programming. In: Wolfgang E. Nagel, Wolfgang V. Walter and Wolfgang Lehner (Ed.), Euro-Par 2006 Parallel Processing 12th International Euro-Par Conference, Dresden, Germany, August 28 – September 1, 2006. Proceedings: (pp. 461-472). Springer Berlin/Heidelberg, 4128
Open this publication in new window or tab >>Optimal integrated VLIW code generation with Integer Linear Programming
2006 (English)In: Euro-Par 2006 Parallel Processing 12th International Euro-Par Conference, Dresden, Germany, August 28 – September 1, 2006. Proceedings / [ed] Wolfgang E. Nagel, Wolfgang V. Walter and Wolfgang Lehner, Springer Berlin/Heidelberg, 2006, Vol. 4128, p. 461-472Chapter in book (Refereed)
Abstract [en]

We give an Integer Linear Programming (ILP) solution that fully integrates all steps of code generation, i.e. instruction selection, register allocation and instruction scheduling, on the basic block level for VLIW processors.

In earlier work, we contributed a dynamic programming (DP) based method for optimal integrated code generation, implemented in our retargetable code generator OPTIMIST. In this paper we give first results to evaluate and compare our ILP formulation with our DP method on a VLIW processor. We also demonstrate how to precondition the ILP model by a heuristic relaxation of the DP method to improve ILP optimization time.

Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2006
Series
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 4128
National Category
Engineering and Technology
Identifiers
urn:nbn:se:liu:diva-48061 (URN)10.1007/11823285_48 (DOI)3-540-37783-2 (ISBN)978-3-540-37783-2 (ISBN)
Available from: 2009-10-11 Created: 2009-10-11 Last updated: 2018-01-30Bibliographically approved
Bednarski, A. & Kessler, C. (2004). Energy-Optimal Integrated VLIW Code Generation. In: CPC04 11th Int. Workshop on Compilers for Parallel Computers,2004 (pp. 227-238).
Open this publication in new window or tab >>Energy-Optimal Integrated VLIW Code Generation
2004 (English)In: CPC04 11th Int. Workshop on Compilers for Parallel Computers,2004, 2004, p. 227-238Conference paper, Published paper (Other academic)
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-22664 (URN)1951 (Local ID)1951 (Archive number)1951 (OAI)
Available from: 2009-10-07 Created: 2009-10-07 Last updated: 2018-01-13
Bednarski, A. & Kessler, C. (2004). Exploiting Symmetries for Optimal Integrated Code Generation. In: Int. Conf. on Embedded Systems and Applications ESA04,2004.
Open this publication in new window or tab >>Exploiting Symmetries for Optimal Integrated Code Generation
2004 (English)In: Int. Conf. on Embedded Systems and Applications ESA04,2004, 2004Conference paper, Published paper (Refereed)
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-22663 (URN)1950 (Local ID)1950 (Archive number)1950 (OAI)
Available from: 2009-10-07 Created: 2009-10-07 Last updated: 2018-01-13
Bednarski, A. & Kessler, C. (2003). Optimal integrated code generation for VLIW architectures. In: Proc. of CPC'03 10th Int. Workshop on Compilers for Parallel Computers, Amsterdam, The Netherlands, January 2003'. Leiden, The Netherlands: Leiden Institute of Advanced Computer Science
Open this publication in new window or tab >>Optimal integrated code generation for VLIW architectures
2003 (English)In: Proc. of CPC'03 10th Int. Workshop on Compilers for Parallel Computers, Amsterdam, The Netherlands, January 2003', Leiden, The Netherlands: Leiden Institute of Advanced Computer Science , 2003Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
Leiden, The Netherlands: Leiden Institute of Advanced Computer Science, 2003
Keywords
code generation, VLIW architecture, Digital signal processor, instruction scheduling, instruction selection, register allocation, dynamic programming
National Category
Engineering and Technology
Identifiers
urn:nbn:se:liu:diva-61612 (URN)
Available from: 2010-11-17 Created: 2010-11-17 Last updated: 2014-10-08
Bednarski, A. (2002). A dynamic programming approach to optimal retargetable code generation for irregular architectures. (Licentiate dissertation). Linköping: Linköpings universitet
Open this publication in new window or tab >>A dynamic programming approach to optimal retargetable code generation for irregular architectures
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. p. 117
Series
Linköping Studies in Science and Technology. Thesis, ISSN 0280-7971 ; 1001
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-42655 (URN)67699 (Local ID)91-7373-591-4 (ISBN)67699 (Archive number)67699 (OAI)
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: 2018-01-12
Organisations

Search in DiVA

Show all publications