Change search
CiteExportLink to record
Permanent link

Direct 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
Implied Constraints for the Unison Presolver
KTH, School of Information and Communication Technology (ICT).
2015 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

Unison is a compiler back-end that differs from traditional compiler approaches in that the compilation is carried out using constraint programming rather than greedy algorithms. The compilation problem is translated to a constraint model and then solved using a constraint solver, yielding an approach that has the potential of producing optimal code. Presolving is the process of strengthening a constraint model before solving, and has previously been shown to be effective in terms of the robustness and the quality of the generated code. This thesis presents an evaluation of different presolving techniques used in Unison’s presolver for deducing implied constraints. Such constraints are logical consequences of other constraints in the model and must therefore be fulfilled in any valid solution of the model. Two of the most important techniques for generating these constraints are reimplemented, aiming to reduce Unison’s dependencies on systems that are not free software. The reimplementation is shown to be successful with respect to both correctness and performance. In fact, while producing the same output a substantial performance increase can be measured indicating a mean speedup of 2.25 times compared to the previous implementation.

Abstract [sv]

Unison är kompilatorkomponent för generering av programkod. Unison skiljer sig från traditionella kompilatorer i den meningen att villkorsprogrammering används för kodgenerering i stället för giriga algoritmer. Med Unisons metodik modelleras kompileringsproblem i en villkorsmodell som därefter kan lösas av en villkorslösare. Detta gör att Unison har potentialen att generara optimal kod, något som traditionella kompilatorer vanligtvis inte gör. Tidigare forskning har visat att det går att öka Unisons möjligheter att generera högkvalitativ kod genom att härleda extra, implicerade, villkor från villkorsmodellen innan denna löses. Ett implicerat villkor är en logisk konsekvens av andra villkor i modellen och förstärker modellen genom att minska den tid som lösaren spenderar i återvändsgränder. Denna avhandling presenterar en utvärdering av olika tekniker för detektering av implicerade villkor i den villkorsmodell som används av Unison. Två av de mer effektiva teknikerna för detektering av dessa villkor har även omimplementerats, med syfte att minska Unisons beroenden på annan icke kostadsfri programvara. Denna omimplementation har visats inte bara vara korrekt, det vill säga generera samma resultat, utan också även väsentligt snabbare än den ursprungliga implementationen. Experiment utföra under arbetet med denna avhandling har påvisat en uppsnabbning (med avseende på exekveringstid) på i medeltal 2,25 gånger jämfört med den ursprungliga implementationen av dessa tekniker. Detta resultat gäller när båda implementationerna generar samma utdata givet samma indata.

Place, publisher, year, edition, pages
2015. , 91 p.
Series
TRITA-ICT-EX, 2015:74
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:kth:diva-175838OAI: oai:DiVA.org:kth-175838DiVA: diva2:862630
Examiners
Available from: 2015-10-23 Created: 2015-10-23 Last updated: 2016-05-10Bibliographically approved

Open Access in DiVA

fulltext(1011 kB)40 downloads
File information
File name FULLTEXT01.pdfFile size 1011 kBChecksum SHA-512
c261bbc5128940b66b88e166da28be5bddbe5508ad090a64128afa25100c254e679732f3a749579bb7b191edec4408778515ab77d3a076ad0bf29727d5fe4755
Type fulltextMimetype application/pdf

By organisation
School of Information and Communication Technology (ICT)
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 40 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 238 hits
CiteExportLink to record
Permanent link

Direct 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