Change search
ReferencesLink to record
Permanent link

Direct link
Evaluation and Implementation of Dominance Breaking Presolving Techniques in the Unison Compiler Back-End
KTH, School of Information and Communication Technology (ICT).
2015 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesisAlternative title
Utvärdering och Implementation av Dominansbrytande Presolving-tekniker i Unison Kompilatorn (Swedish)
Abstract [en]

Constraint-based compiler back-ends use constraint programming to solve some of the translation stages that a compiler back-end typically is constructed of. Using constraint programming enables the compiler to generate optimal target code that is faster and more robust compared to code generated by a traditional compiler back-end. With constraint programming, problems are modeled and automatically solved by a constraint solver. A method to make the solving less time-consuming is presolving. Presolving derives new information about a problem that can be applied to its model before the actual solving. This thesis focuses on evaluating a set of dominance breaking presolving techniques in a constraint-based compiler back-end. A dominance relation in constraint programming is two assignments that are in some sense equivalent. Based on the evaluation some of the presolving techniques are re-implemented in an open source constraint-solving toolkit, to remove dependencies on proprietary, but commonly available, systems inside the constraint-based compiler. The re-implemented techniques show similar or better performance than the original implementations of the techniques. In the best case, the re-implemented techniques shows an efficiency increase of 50 % compared to the original implementations.

Abstract [sv]

Villkorsprogrammeringsbaserade kompilatorer använder villkorsprogrammering för att lösa vissa delar av översättningsprocessen som en traditionell kompilator-back-end typisk är konstruerad av. Genom användningen av villkorsprogrammering kan kompilatorn generera kod som är optimal och snabbare än kod genererad av en traditionell kompilatorback- end. Med villkorsprogrammering modelleras problem som sedan löses automatiskt av en constraint solver. En metod för att göra lösningsprocessen mindre tidskrävande är presolving. Presolving härleder ny information om ett problem och adderar informationen till problemets modell innan det löses. Denna masteravhandling evaluerar en grupp av dominansbrytande presolving-tekniker i en villkorsprogrammeringsbaserad kompilator. Baserat på denna utvärdering är några av dessa tekniker om-implementerade i ett open source villkorsprogrammerings-toolkit för att ta bort beroenden av proprietära, men tillgängliga, system. De om-implementerade teknikerna har samma eller bättre effekt som originalimplementationerna. I det bästa fallet visar om-implementationerna en effektivitetsökning på 50 % jämfört med originalimplementationen.

Place, publisher, year, edition, pages
2015. , 87 p.
TRITA-ICT-EX, 2015:73
National Category
Computer and Information Science
URN: urn:nbn:se:kth:diva-175835OAI: diva2:862615
Educational program
Master of Science - Embedded Systems
Available from: 2015-10-23 Created: 2015-10-23 Last updated: 2016-05-10Bibliographically approved

Open Access in DiVA

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

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

Search outside of DiVA

GoogleGoogle Scholar
Total: 15 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

Total: 71 hits
ReferencesLink to record
Permanent link

Direct link