Ä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
Survey on combinatorial register allocation and instruction scheduling
KTH Royal Institute of Technology, Sweden.
RISE - Research Institutes of Sweden, ICT, SICS.ORCID-id: 0000-0002-6283-7004
2019 (Engelska)Ingår i: ACM Computing Surveys, ISSN 0360-0300, E-ISSN 1557-7341, Vol. 52, nr 3, artikel-id 62Artikel i tidskrift (Refereegranskat) Published
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 past 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 article 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. .

Ort, förlag, år, upplaga, sidor
Association for Computing Machinery , 2019. Vol. 52, nr 3, artikel-id 62
Nyckelord [en]
Combinatorial optimization, Instruction scheduling, Register allocation, Computer programming, Constraint theory, Economic and social effects, Heuristic algorithms, Program compilers, Quadratic programming, Scheduling, Assembly code, Constraint programming, Instruction level parallelism, Literature reviews, Optimal solutions, Potential benefits, Integer programming
Nationell ämneskategori
Naturvetenskap
Identifikatorer
URN: urn:nbn:se:ri:diva-39459DOI: 10.1145/3200920Scopus ID: 2-s2.0-85068049964OAI: oai:DiVA.org:ri-39459DiVA, id: diva2:1335986
Tillgänglig från: 2019-07-08 Skapad: 2019-07-08 Senast uppdaterad: 2019-07-08Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltextScopus

Personposter BETA

Schulte, Christian

Sök vidare i DiVA

Av författaren/redaktören
Schulte, Christian
Av organisationen
SICS
I samma tidskrift
ACM Computing Surveys
Naturvetenskap

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 5 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
v. 2.35.7