Change search
Refine search result
1 - 10 of 10
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • 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.
    Castaneda Lozano, Roberto
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Integrated Register Allocation and Instruction Scheduling with Constraint Programming2014Licentiate thesis, monograph (Other academic)
    Abstract [en]

    This dissertation proposes a combinatorial model, program representations, and constraint solving techniques for integrated register allocation and instruction scheduling in compiler back-ends. In contrast to traditional compilers based on heuristics, the proposed approach generates potentially optimal code by considering all trade-offs between interdependent decisions as a single optimization problem. The combinatorial model is the first to handle a wide array of global register allocation subtasks, including spill code optimization, ultimate coalescing, register packing, and register bank assignment, as well as instruction scheduling for Very Long Instruction Word (VLIW) processors. The model is based on three novel, complementary program representations: Linear Static Single Assignment for global register allocation; copy extension for spilling, basic coalescing, and register bank assignment; and alternative temporaries for spill code optimization and ultimate coalescing. Solving techniques are proposed that exploit the program representation properties for scalability. The model, program representations, and solving techniques are implemented in Unison, a code generator that delivers potentially optimal code while scaling to medium-size functions. Thorough experiments show that Unison: generates faster code (up to 41% with a mean improvement of 7%) than LLVM (a state-of-the-art compiler) for Hexagon (a challenging VLIW processor), generates code that is competitive with LLVM for MIPS32 (a simpler RISC processor), is robust across different benchmarks such as MediaBench and SPECint 2006, scales up to medium-size functions of up to 1000 instructions, and adapts easily to different optimization criteria. The contributions of this dissertation are significant. They lead to a combinatorial approach for integrated register allocation and instruction scheduling that is, for the first time, practical (it robustly scales to medium-size functions) and effective (it yields better code than traditional heuristic approaches).

  • 2.
    Castaneda Lozano, Roberto
    et al.
    RISE - Research Institutes of Sweden, ICT, SICS. KTH Royal Institute of Technology, Sweden .
    Carlsson, Mats
    RISE - Research Institutes of Sweden, ICT, SICS.
    Blindell, Gabriel
    KTH Royal Institute of Technology, Sweden .
    Schulte, Christian
    RISE - Research Institutes of Sweden, ICT, SICS. KTH Royal Institute of Technology, Sweden .
    Combinatorial register allocation and instruction scheduling2019In: ACM Transactions on Programming Languages and Systems, ISSN 0164-0925, E-ISSN 1558-4593, Vol. 41, no 3, article id 17Article in journal (Refereed)
    Abstract [en]

    This article introduces a combinatorial optimization approach to register allocation and instruction scheduling, two central compiler problems. Combinatorial optimization has the potential to solve these problems optimally and to exploit processor-specific features readily. Our approach is the first to leverage this potential in practice: it captures the complete set of program transformations used in state-of-the-art compilers, scales to medium-sized functions of up to 1,000 instructions, and generates executable code. This level of practicality is reached by using constraint programming, a particularly suitable combinatorial optimization technique. Unison, the implementation of our approach, is open source, used in industry, and integrated with the LLVM toolchain. An extensive evaluation confirms that Unison generates better code than LLVM while scaling to medium-sized functions. The evaluation uses systematically selected benchmarks from MediaBench and SPEC CPU2006 and different processor architectures (Hexagon, ARM, MIPS). Mean estimated speedup ranges from 1.1% to 10% and mean code size reduction ranges from 1.3% to 3.8% for the different architectures. A significant part of this improvement is due to the integrated nature of the approach. Executing the generated code on Hexagon confirms that the estimated speedup results in actual speedup. Given a fixed time limit, Unison solves optimally functions of up to 946 instructions, nearly an order of magnitude larger than previous approaches. The results show that our combinatorial approach can be applied in practice to trade compilation time for code quality beyond the usual compiler optimization levels, identify improvement opportunities in heuristic algorithms, and fully exploit processor-specific features.

  • 3.
    Castaneda Lozano, Roberto
    et al.
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Drejhammar, Frej
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Schulte, Christian
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Constraint-based Register Allocation and Instruction Scheduling2012Conference paper (Refereed)
    Abstract [en]

    This paper introduces a constraint model and solving techniques for code generation in a compiler back-end. It contributes a new model for global register allocation that combines several advanced aspects: multiple register banks (subsuming spilling to memory), coalescing, and packing. The model is extended to include instruction scheduling and bundling. The paper introduces a decomposition scheme exploiting the underlying program structure and exhibiting robust behavior for functions with thousands of instructions. Evaluation shows that code quality is on par with LLVM, a state-of-the-art compiler infrastructure. The paper makes important contributions to the applicability of constraint programming as well as compiler construction: essential concepts are unified in a high-level model that can be solved by readily available modern solvers. This is a significant step towards basing code generation entirely on a high-level model and by this facilitates the construction of correct, simple, flexible, robust, and high-quality code generators.

  • 4.
    Castaneda Lozano, Roberto
    et al.
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Hjort Blindell, Gabriel
    KTH Royal Institute of Technology, Sweden.
    Schulte, Christian
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Combinatorial Spill Code Optimization and Ultimate Coalescing2014Conference paper (Refereed)
    Abstract [en]

    This paper presents a novel combinatorial model that integrates global register allocation based on ultimate coalescing, spill code optimization, register packing, and multiple register banks with instruction scheduling (including VLIW). The model exploits alternative temporaries that hold the same value as a new concept for ultimate coalescing and spill code optimization. The paper presents Unison as a code generator based on the model and advanced solving techniques using constraint programming. Thorough experiments using MediaBench and a processor (Hexagon) that are typical for embedded systems demonstrate that Unison: is robust and scalable; generates faster code than LLVM (up to 41% with a mean improvement of 7%); possibly generates optimal code (for 29% of the experiments); effortlessly supports different optimization criteria (code size on par with LLVM). Unison is significant as it addresses the same aspects as traditional code generation algorithms, yet is based on a simple integrated model and robustly can generate optimal code.

  • 5.
    Castaneda Lozano, Roberto
    et al.
    RISE, Swedish ICT, SICS, Computer Systems Laboratory. KTH Royal Institute of Technology, Sweden.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Hjort Blindell, Gabriel
    KTH Royal Institute of Technology, Sweden.
    Schulte, Christian
    RISE, Swedish ICT, SICS, Computer Systems Laboratory. KTH Royal Institute of Technology, Sweden.
    Register allocation and instruction scheduling in Unison2016In: Proceedings of the 25th International Conference on Compiler Construction, 2016, 6, p. 263-264Conference paper (Refereed)
    Abstract [en]

    This paper describes Unison, a simple, flexible, and potentially optimal software tool that performs register allocation and instruction scheduling in integration using combinatorial optimization. The tool can be used as an alternative or as a complement to traditional approaches, which are fast but complex and suboptimal. Unison is most suitable whenever high-quality code is required and longer compilation times can be tolerated (such as in embedded systems or library releases), or the targeted processors are so irregular that traditional compilers fail to generate satisfactory code.

  • 6.
    Castaneda Lozano, Roberto
    et al.
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Hjort Blindell, Gabriel
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Drejhammar, Frej
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Schulte, Christian
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Constraint-based Code Generation2013Conference paper (Refereed)
  • 7.
    Castaneda Lozano, Roberto
    et al.
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Schulte, Christian
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Survey on Combinatorial Register Allocation and Instruction Scheduling2014In: arXiv:1409.7628 [cs.PL]Article in journal (Refereed)
    Abstract [en]

    Register allocation and instruction scheduling are two central compiler back-end problems that are critical for quality. In the last two decades, combinatorial optimization has emerged as an alternative approach to traditional, heuristic algorithms for these problems. Combinatorial approaches are generally slower but more flexible than their heuristic counterparts and have the potential to generate optimal code. This paper surveys existing literature on combinatorial register allocation and instruction scheduling. The survey covers approaches that solve each problem in isolation as well as approaches that integrate both problems. The latter have the potential to generate code that is globally optimal by capturing the trade-off between conflicting register allocation and instruction scheduling decisions.

  • 8.
    Castaneda Lozano, Roberto
    et al.
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Schulte, Christian
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Wahlberg, Lars
    Testing Continuous Double Auctions with a Constraint-based Oracle2010Conference paper (Refereed)
    Abstract [en]

    Computer trading systems are essential for today's financial markets where the trading systems' correctness is of paramount economical significance. Automated random testing is a useful technique to find bugs in these systems, but it requires an independent system to decide the correctness of the system under test (known as oracle problem). This paper introduces a constraint-based oracle for random testing of a real-world trading system. The oracle provides the expected results by generating and solving constraint models of the trading system's continuous double auction. Constraint programming is essential for the correctness of the test oracle as the logic for calculating trades can be mapped directly to constraint models. The paper shows that the generated constraint models can be solved efficiently. Most importantly, the approach is shown to be successful by finding errors in a deployed financial trading system and in its specification.

  • 9.
    Hjort Blindell, Gabriel
    et al.
    KTH Royal Institute of Technology, Sweden.
    Castaneda Lozano, Roberto
    RISE, Swedish ICT, SICS, Computer Systems Laboratory. KTH Royal Institute of Technology, Sweden.
    Carlsson, Mats
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Schulte, Christian
    RISE, Swedish ICT, SICS, Computer Systems Laboratory. KTH Royal Institute of Technology, Sweden.
    Modeling Universal Instruction Selection2015In: Principles and Practice of Constraint Programming, 2015, 7, Vol. 9255, p. 609-626Conference paper (Refereed)
    Abstract [en]

    Instruction selection implements a program under compilation by selecting processor instructions and has tremendous impact on the performance of the code generated by a compiler. This paper introduces a graph-based universal representation that unifiees data and control flow for both programs and processor instructions. The representation is the essential prerequisite for a constraint model for instruction selection introduced in this paper. The model is demonstrated to be expressive in that it supports many processor features that are out of reach of state-of-the-art approaches, such as advanced branching instructions, multiple register banks, and SIMD instructions. The resulting model can be solved for small to medium size input programs and sophisticated processor instructions and is competitive with LLVM in code quality. Model and representation are significant due to their expressiveness and their potential to be combined with models for other code generation tasks.

  • 10.
    Mallach, Sven
    et al.
    Universität zu Köln, Germany.
    Castaneda Lozano, Roberto
    RISE, Swedish ICT, SICS, Computer Systems Laboratory.
    Optimal General Offset Assignment2014Conference paper (Refereed)
    Abstract [en]

    We present an exact approach to the General Offset Assignment problem arising in the domain of address code generation for application specific and digital signal processors. General Offset Assignment is composed of two subproblems, namely to find a permutation of variables in memory and to select a responsible address register for each access to one of these variables. Our method is a combination of established techniques to solve both subproblems using integer linear programming. To the best of our knowledge, it is the first approach capable of solving almost all instances of the established OffsetStone benchmark set to global optimality within reasonable time. We provide a first comprehensive evaluation of the quality of several state-of-the-art heuristics relative to the optimal solutions.

1 - 10 of 10
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • 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
v. 2.35.10