liu.seSearch for publications in DiVA
Change search
Refine search result
1 - 12 of 12
CiteExportLink to result list
Permanent 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
Rows per page
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sort
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the Create feeds function.
  • 1.
    Bednarski, Andrzej
    Linköping University, Department of Computer and Information Science, PELAB - Programming Environment Laboratory. Linköping University, The Institute of Technology.
    A dynamic programming approach to optimal retargetable code generation for irregular architectures2002Licentiate 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. 

  • 2.
    Bednarski, Andrzej
    Linköping University, Department of Computer and Information Science, PELAB. Linköping University, The Institute of Technology.
    Integrated Optimal Code Generation for Digital Signal Processors2006Doctoral 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.

  • 3.
    Bednarski, Andrzej
    et al.
    Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, PELAB - Programming Environment Laboratory.
    Kessler, Christoph
    Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, PELAB - Programming Environment Laboratory.
    Energy-Optimal Integrated VLIW Code Generation2004In: CPC04 11th Int. Workshop on Compilers for Parallel Computers,2004, 2004, p. 227-238Conference paper (Other academic)
  • 4.
    Bednarski, Andrzej
    et al.
    Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, PELAB - Programming Environment Laboratory.
    Kessler, Christoph
    Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, PELAB - Programming Environment Laboratory.
    Exploiting Symmetries for Optimal Integrated Code Generation2004In: Int. Conf. on Embedded Systems and Applications ESA04,2004, 2004Conference paper (Refereed)
  • 5.
    Bednarski, Andrzej
    et al.
    Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, PELAB - Programming Environment Laboratory.
    Kessler, Christoph
    Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, PELAB - Programming Environment Laboratory.
    Integer Linear Programming versus Dynamic Programming for Optimal Integrated VLIW Code Generation2006In: 12th Int. Workshop on Compilers for Parallel Computers,2006, 2006, p. 73-Conference paper (Refereed)
  • 6.
    Bednarski, Andrzej
    et al.
    Linköping University, Department of Computer and Information Science, PELAB - Programming Environment Laboratory. Linköping University, The Institute of Technology.
    Kessler, Christoph
    Linköping University, Department of Computer and Information Science, PELAB - Programming Environment Laboratory. Linköping University, The Institute of Technology.
    Optimal integrated code generation for VLIW architectures2003In: 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 (Refereed)
  • 7.
    Bednarski, Andrzej
    et al.
    Linköping University, Department of Computer and Information Science, PELAB - Programming Environment Laboratory. Linköping University, The Institute of Technology.
    Kessler, Christoph
    Linköping University, Department of Computer and Information Science, PELAB - Programming Environment Laboratory. Linköping University, The Institute of Technology.
    Optimal integrated VLIW code generation with Integer Linear Programming2006In: 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.

  • 8.
    Kessler, Christoph
    et al.
    Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, PELAB - Programming Environment Laboratory.
    Bednarski, Andrzej
    Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, PELAB - Programming Environment Laboratory.
    A Dynamic Programming Approach to Optimal Integrated Code Generation2001In: ACM SIGPLAN Workshop on Languages, Compilers, and Tools for Embedded Systems LCTES2001,2001, New York, USA: ACM , 2001, p. 165-174Conference paper (Refereed)
    Abstract [en]

    Phase-decoupled methods for code generation are the state of the art in compilers for standard processors but generally produce code of poor quality for irregular target architectures such as many DSPs. In that case, the generation of efficient code requires the simultaneous solution of the main subproblems instruction selection, instruction scheduling, and register allocation, as an integrated optimization problem. In contrast to compilers for standard processors, code generation for DSPs can afford to spend much higher resources in time and space on optimizations. Today, most approaches to optimal code generation are based on integer linear programming, but these are either not integrated or not able to produce optimal solutions except for very small problem instances. We report on research in progress on a novel method for fully integrated code generation that is based on dynamic programming. In particular, we introduce the concept of a time profile. We focus on the basic block level where the data dependences among the instructions form a DAG. Our algorithm aims at combining time-optimal scheduling with optimal instruction selection, given a limited number of general-purpose registers. An extension for irregular register sets, spilling of register contents, and intricate structural constraints on code compaction based on register usage is currently under development, as well as a generalization for global code generation. A prototype implementation is operational, and we present first experimental results that show that our algorithm is practical also for medium-size problem instances. Our implementation is intended to become the core of a future, retargetable code generation system.

  • 9.
    Kessler, Christoph
    et al.
    Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, PELAB - Programming Environment Laboratory.
    Bednarski, Andrzej
    Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, PELAB - Programming Environment Laboratory.
    Classification and generation of schedules for VLIW processors2006In: 2th Int. Workshop on Compilers for Parallel Computers,2006, 2006, p. 60-Conference paper (Refereed)
  • 10.
    Kessler, Christoph
    et al.
    Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, PELAB - Programming Environment Laboratory.
    Bednarski, Andrzej
    Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, PELAB - Programming Environment Laboratory.
    Optimal integrated code generation for clustered VLIW architectures2002In: joint conference on Languages, compilers and tools for embedded systems: software and compilers for embedded systems LCTES-SCOPES02,2002, New York, USA: ACM , 2002, p. 102-Conference paper (Refereed)
    Abstract [en]

    In contrast to standard compilers, generating code for DSPs can afford spending considerable resources in time and space on optimizations. Generating efficient code for irregular architectures requires an integrated method that optimizes simultaneously for instruction selection, instruction scheduling, and register allocation.We describe a method for fully integrated optimal code generation based on dynamic programming. We introduce the concept of residence classes and space profiles, which allows us to describe and optimize for irregular register and memory structures. In order to obtain a retargetable framework we introduce a structured architecture description language, ADML, which is based on XML. We implemented a prototype of such a retargetable system for optimal code generation. Results for variants of the TI C62x show that our method can produce optimal solutions to small but nontrivial problem instances with a reasonable amount of time and space.

  • 11.
    Kessler, Christoph
    et al.
    Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, PELAB - Programming Environment Laboratory.
    Bednarski, Andrzej
    Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, PELAB - Programming Environment Laboratory.
    Optimal integrated code generation for VLIW architectures2006In: Concurrency and Computation, ISSN 1532-0626, E-ISSN 1532-0634, Vol. 18, no 11, p. 1353-1390Article in journal (Refereed)
    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.

  • 12.
    Kessler, Christoph
    et al.
    Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, PELAB - Programming Environment Laboratory.
    Bednarski, Andrzej
    Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, PELAB - Programming Environment Laboratory.
    Eriksson, Mattias
    Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, PELAB - Programming Environment Laboratory.
    Classification and generation of schedules for VLIW processors2007In: Concurrency, ISSN 1040-3108, E-ISSN 1096-9128, Vol. 19, p. 2369-2389Article in journal (Refereed)
    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.

1 - 12 of 12
CiteExportLink to result list
Permanent 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