Change search
Refine search result
1 - 11 of 11
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • harvard1
  • 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.
    Castañeda Lozano, Roberto
    KTH, School of Electrical Engineering and Computer Science (EECS), Software and Computer systems, SCS. RISE SICS (Swedish Institute of Computer Science).
    Constraint-Based Register Allocation and Instruction Scheduling2018Doctoral thesis, comprehensive summary (Other academic)
    Abstract [en]

    Register allocation (mapping variables to processor registers or memory) and instruction scheduling (reordering instructions to improve latency or throughput) are central compiler problems. This dissertation proposes a combinatorial optimization approach to these problems that delivers optimal solutions according to a model, captures trade-offs between conflicting decisions, accommodates processor-specific features, and handles different optimization criteria.

    The use of constraint programming and a novel program representation enables a compact model of register allocation and instruction scheduling. The model captures the complete set of global register allocation subproblems (spilling, assignment, live range splitting, coalescing, load-store optimization, multi-allocation, register packing, and rematerialization) as well as additional subproblems that handle processor-specific features beyond the usual scope of conventional compilers.

    The approach is implemented in Unison, an open-source tool used in industry and research that complements the state-of-the-art LLVM compiler. Unison applies general and problem-specific constraint solving methods to scale to medium-sized functions, solving functions of up to 647 instructions optimally and improving functions of up to 874 instructions. The approach is evaluated experimentally using different processors (Hexagon, ARM and MIPS), benchmark suites (MediaBench and SPEC CPU2006), and optimization criteria (speed and code size reduction). The results show that Unison generates code of slightly to significantly better quality than LLVM, depending on the characteristics of the targeted processor (1% to 9.3% mean estimated speedup; 0.8% to 3.9% mean code size reduction). Additional experiments for Hexagon show that its estimated speedup has a strong monotonic relationship to the actual execution speedup, resulting in a mean speedup of 5.4% across MediaBench applications.

    The approach contributed by this dissertation is the first of its kind that is practical (it captures the complete set of subproblems, scales to medium-sized functions, and generates executable code) and effective (it generates better code than the LLVM compiler, fulfilling the promise of combinatorial optimization). It can be applied to trade compilation time for code quality beyond the usual optimization levels, explore and exploit processor-specific features, and identify improvement opportunities in conventional compilers.

  • 2.
    Castañeda Lozano, Roberto
    KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS. SICS (Swedish Institute of Computer Science) and KTH (Royal Institute of Technology).
    Integrated Register Allocation and Instruction Scheduling with Constraint Programming2014Licentiate thesis, comprehensive summary (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).

  • 3.
    Castañeda Lozano, Roberto
    et al.
    SICS (Swedish Institute of Computer Science), Sweden.
    Carlsson, Mats
    SICS (Swedish Institute of Computer Science), Sweden.
    Drejhammar, Frej
    SICS (Swedish Institute of Computer Science), Sweden.
    Schulte, Christian
    KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS. SICS (Swedish Institute of Computer Science), Sweden.
    Constraint-Based Register Allocation and Instruction Scheduling2012In: Principles and Practice of Constraint Programming: 18th International Conference, CP 2012, Québec City, QC, Canada, October 8-12, 2012. Proceedings / [ed] Michela Milano, Springer, 2012, p. 750-766Conference 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.
    Castañeda Lozano, Roberto
    et al.
    KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS. SICS (Swedish Institute of Computer Science).
    Carlsson, Mats
    SICS (Swedish Institute of Computer Science).
    Hjort Blindell, Gabriel
    KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS.
    Schulte, Christian
    KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS.
    Register allocation and instruction scheduling in Unison2016In: Proceedings of CC 2016: The 25th International Conference on Compiler Construction, Association for Computing Machinery (ACM), 2016, 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.

  • 5.
    Castañeda Lozano, Roberto
    et al.
    KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS. SICS (Swedish Institute of Computer Science) and KTH (Royal Institute of Technology).
    Hjort Blindell, Gabriel
    KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS.
    Carlsson, Mats
    SICS (Swedish Institute of Computer Science).
    Drejhammar, Frej
    SICS (Swedish Institute of Computer Science).
    Schulte, Christian
    KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS.
    Constraint-based Code Generation2013In: Proceedings of the 16th International Workshop on Software and Compilers for Embedded Systems, M-SCOPES 2013, Association for Computing Machinery (ACM), 2013, p. 93-95Conference paper (Refereed)
    Abstract [en]

    Compiler back-ends generate assembly code by solving three main tasks: instruction selection, register allocation and instruction scheduling. We introduce constraint models and solving techniques for these code generation tasks and describe how the models can be composed to generate code in unison. The use of constraint programming, a technique to model and solve combinatorial problems, makes code generation simple, flexible, robust and potentially optimal.

  • 6.
    Castañeda Lozano, Roberto
    et al.
    KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS. SICS (Swedish Institute of Computer Science) and KTH (Royal Institute of Technology).
    Schulte, Christian
    KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS.
    Survey on Combinatorial Register Allocation and Instruction Scheduling2014Report (Other academic)
    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.

  • 7.
    Castañeda Lozano, Roberto
    et al.
    KTH, School of Electrical Engineering and Computer Science (EECS), Software and Computer systems, SCS. RISE SICS (Swedish Institute of Computer Science).
    Schulte, Christian
    KTH, School of Electrical Engineering and Computer Science (EECS), Software and Computer systems, SCS.
    Survey on Combinatorial Register Allocation and Instruction Scheduling2018In: ACM Computing Surveys, ISSN 0360-0300, E-ISSN 1557-7341Article in journal (Refereed)
    Abstract [en]

    Register allocation (mapping variables to processor registers or memory) and instruction scheduling (reordering instructions to increase instruction-level parallelism) are essential tasks for generating efficient assembly code in a compiler. In the last three decades, combinatorial optimization has emerged as an alternative to traditional, heuristic algorithms for these two tasks. Combinatorial optimization approaches can deliver optimal solutions according to a model, can precisely capture trade-offs between conflicting decisions, and are more flexible at the expense of increased compilation time.

    This paper provides an exhaustive literature review and a classification of combinatorial optimization approaches to register allocation and instruction scheduling, with a focus on the techniques that are most applied in this context: integer programming, constraint programming, partitioned Boolean quadratic programming, and enumeration. Researchers in compilers and combinatorial optimization can benefit from identifying developments, trends, and challenges in the area; compiler practitioners may discern opportunities and grasp the potential benefit of applying combinatorial optimization.

  • 8.
    Castañeda Lozano, Roberto
    et al.
    KTH, School of Information and Communication Technology (ICT), Communication: Services and Infrastucture (Closed 20120101), Software and Computer Systems, SCS (Closed 20120101).
    Schulte, Christian
    KTH, School of Information and Communication Technology (ICT), Communication: Services and Infrastucture (Closed 20120101), Software and Computer Systems, SCS (Closed 20120101).
    Wahlberg, Lars
    Testing Continuous Double Auctions with a Constraint-Based Oracle2010In: PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING-CP 2010 / [ed] Cohen D, 2010, Vol. 6308, p. 613-627Conference 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, School of Information and Communication Technology (ICT), Software and Computer systems, SCS. SICS RISE.
    Carlsson, Mats
    RISE SICS.
    Castañeda Lozano, Roberto
    KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS. RISE SICS.
    Schulte, Christian
    KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS. RISE SICS.
    Complete and Practical Universal Instruction Selection2017In: ACM Transactions on Embedded Computing Systems, ISSN 1539-9087, E-ISSN 1558-3465Article in journal (Refereed)
    Abstract [en]

    In code generation, instruction selection chooses processor instructions to implement a program under compilation where code quality crucially depends on the choice of instructions. Using methods from combinatorial optimization, this paper proposes an expressive model that integrates global instruction selection with global code motion.The model introduces (1) handling of memory computations and function calls, (2) a method for inserting additional jump instructions where necessary, (3) a dependency-based technique to ensure correct combinations of instructions, (4) value reuse to improve code quality, and (5) an objective function that reduces compilation time and increases scalability by exploiting bounding techniques. The approach is demonstrated to be complete and practical, competitive with LLVM, and potentially optimal (w.r.t. the model) for medium-sized functions. The results show that combinatorial optimization for instruction selection is well-suited to exploit the potential of modern processors in embedded systems.

  • 10.
    Lozano, Roberto Castaneda
    et al.
    SCALE, Swedish Institute of Computer Science, Sweden .
    Carlsson, Mats
    Hjort Blindell, Gabriel
    KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS.
    Schulte, Christian
    KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS.
    Combinatorial Spill Code Optimization and Ultimate Coalescing2014In: SIGPLAN notices, ISSN 0362-1340, E-ISSN 1558-1160, Vol. 49, no 5, p. 23-32Article in journal (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 4 1 % with a mean improvement of 7 %); possibly generates optimal code (for 2 9 % 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.

  • 11.
    Mallach, Sven
    et al.
    University of Cologne.
    Castañeda Lozano, Roberto
    KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS. SICS Swedish Institute of Computer Science, Sweden .
    Optimal General Offset Assignment2014In: Proceedings of the 17th International Workshop on Software and Compilers for Embedded Systems, SCOPES 2014, 2014Conference 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 - 11 of 11
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • harvard1
  • 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