Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Register allocation and instruction scheduling in Unison
KTH, Skolan för informations- och kommunikationsteknik (ICT), Programvaruteknik och Datorsystem, SCS. SICS (Swedish Institute of Computer Science).ORCID-id: 0000-0002-2806-7333
SICS (Swedish Institute of Computer Science).
KTH, Skolan för informations- och kommunikationsteknik (ICT), Programvaruteknik och Datorsystem, SCS.ORCID-id: 0000-0001-6794-6413
KTH, Skolan för informations- och kommunikationsteknik (ICT), Programvaruteknik och Datorsystem, SCS.ORCID-id: 0000-0002-6283-7004
2016 (Engelska)Ingår i: Proceedings of CC 2016: The 25th International Conference on Compiler Construction, Association for Computing Machinery (ACM), 2016, s. 263-264Konferensbidrag, Publicerat paper (Refereegranskat)
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.

Ort, förlag, år, upplaga, sidor
Association for Computing Machinery (ACM), 2016. s. 263-264
Nyckelord [en]
Combinatorial optimization, Instruction scheduling, Register allocation
Nationell ämneskategori
Datorsystem
Identifikatorer
URN: urn:nbn:se:kth:diva-183393DOI: 10.1145/2892208.2892237ISI: 000389808800026Scopus ID: 2-s2.0-84966560429ISBN: 9781450342414 (tryckt)OAI: oai:DiVA.org:kth-183393DiVA, id: diva2:910640
Konferens
25th International Conference on Compiler Construction, CC 2016, Barcelona, Spain, 17 March 2016 through 18 March 2016
Anmärkning

QC 20161122

Tillgänglig från: 2016-03-09 Skapad: 2016-03-09 Senast uppdaterad: 2018-07-13Bibliografiskt granskad
Ingår i avhandling
1. Constraint-Based Register Allocation and Instruction Scheduling
Öppna denna publikation i ny flik eller fönster >>Constraint-Based Register Allocation and Instruction Scheduling
2018 (Engelska)Doktorsavhandling, sammanläggning (Övrigt vetenskapligt)
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.

Abstract [sv]

Registerallokering (tilldelning av programvariabler till processorregister eller minne) och instruktionsschemaläggning (omordning av instruktioner för att förbättra latens eller genomströmning) är centrala kompilatorproblem. Denna avhandling presenterar en kombinatorisk optimeringsmetod för dessa problem. Metoden, som är baserad på en formell modell, är kraftfull nog att ge optimala lösningar och göra avvägningar mellan motstridiga optimeringsval. Den kan till fullo uttnyttja processorspecifika funktioner och uttrycka olika optimeringsmål.

Användningen av villkorsprogrammering och en ny programrepresentation möjliggör en kompakt modell av registerallokering och instruktionsschemaläggning. Modellen omfattar samtliga delproblem som ingår i global registerallokering: spilling, tilldelning, live range splitting, coalescing, load-store-optimering, flertilldelning, registerpackning och rematerialisering. Förutom dessa, kan den också integrera processorspecifika egenskaper som går utanför vad konventionella kompilatorer hanterar.

Metoden implementeras i Unison, ett öppen-källkods-verktyg som används inom industri- och forskningsvärlden och utgör ett komplement till LLVM-kompilatorn. Unison tillämpar allmänna och problemspecifika villkorslösningstekniker för att skala till medelstora funktioner, lösa funktioner med upp till 647 instruktioner optimalt och förbättra funktioner på upp till 874 instruktioner. Metoden utvärderas experimentellt för olika målprocessorer (Hexagon, ARM och MIPS), benchmark-sviter (MediaBench och SPEC CPU2006) och optimeringsmål (hastighet och kodstorlek). Resultaten visar att Unison genererar kod av något till betydligt bättre kvalitet än LLVM. Den uppskattade hastighetsförbättringen varierar mellan 1% till 9.3% och kodstorleksreduktionen mellan 0.8% till~3.9%, beroende på målprocessor. Ytterligare experiment för Hexagon visar att dess uppskattade hastighetsförbättring har ett starkt monotoniskt förhållande till den faktiska exekveringstiden, vilket resulterar i en 5.4% genomsnittlig hastighetsförbättring för MediaBench-applikationer.

Denna avhandling beskriver den första praktiskt användbara kombinatoriska optimeringsmetoden för integrerad registerallokering och instruktionsschemaläggning. Metoden är praktiskt användbar då den hanterar samtliga ingående delproblem, genererar exekverbar maskinkod och skalar till medelstora funktioner. Den är också effektiv då den genererar bättre maskinkod än LLVM-kompilatorn. Metoden kan tillämpas för att byta kompileringstid mot kodkvalitet utöver de vanliga optimeringsnivåerna, utforska och utnyttja processorspecifika egenskaper samt identifiera förbättringsmöjligheter i konventionella kompilatorer.

Ort, förlag, år, upplaga, sidor
Stockholm: KTH Royal Institute of Technology, 2018. s. 60
Serie
TRITA-EECS-AVL ; 2018:48
Serie
SICS Dissertation Series, ISSN 1101-1335 ; 78
Nyckelord
constraint programming, combinatorial optimization, register allocation, instruction scheduling, compiler construction
Nationell ämneskategori
Datorsystem Datavetenskap (datalogi)
Forskningsämne
Informations- och kommunikationsteknik
Identifikatorer
urn:nbn:se:kth:diva-232192 (URN)978-91-7729-853-3 (ISBN)
Disputation
2018-09-03, Sal Ka-208, Electrum, Kistagången 16, Kista, Stockholm, 13:15 (Engelska)
Opponent
Handledare
Anmärkning

QC 20180716

Tillgänglig från: 2018-07-16 Skapad: 2018-07-13 Senast uppdaterad: 2018-07-26Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltextScopus25th International Conference on Compiler Construction

Personposter BETA

Castañeda Lozano, RobertoHjort Blindell, Gabriel

Sök vidare i DiVA

Av författaren/redaktören
Castañeda Lozano, RobertoHjort Blindell, GabrielSchulte, Christian
Av organisationen
Programvaruteknik och Datorsystem, SCS
Datorsystem

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetricpoäng

doi
isbn
urn-nbn
Totalt: 1456 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf