Linearly Ordered Attribute Grammar Scheduling Using SAT-Solving. / van Binsbergen, L. Thomas.

Tools and Algorithms for the Construction and Analysis of Systems. Vol. 9035 Springer Berlin / Heidelberg, 2015. p. 289-303 (Lecture Notes in Computer Science; Vol. 9035).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Published

Abstract

Many computations over trees can be specified using attribute grammars. Compilers for attribute grammars need to find an evaluation order (or schedule) in order to generate efficient code. For the class of linearly ordered attribute grammars such a schedule can be found statically, but this problem is known to be NP-hard.
In this paper, we show how to encode linearly ordered attribute grammar scheduling as a SAT-problem. For such grammars it is necessary to ensure that the dependency graph is cycle free, which we approach in a novel way by transforming the dependency graph to a chordal graph allowing the cycle freeness to be efficiently expressed and computed using SAT solvers.
There are two main advantages to using a SAT-solver for scheduling: (1) the scheduling algorithm runs faster than existing scheduling algorithms on real-world examples, and (2) by adding extra constraints we obtain fine-grained control over the resulting schedule, thereby enabling new scheduling optimisations.
Original languageEnglish
Title of host publicationTools and Algorithms for the Construction and Analysis of Systems
PublisherSpringer Berlin / Heidelberg
Pages 289-303
Number of pages15
Volume9035
ISBN (Electronic)978-3-662-46681-0
ISBN (Print)978-3-662-46680-3
DOIs
StatePublished - 1 Jan 2015
EventTACAS 2015 - London, United Kingdom

Publication series

NameLecture Notes in Computer Science
Volume9035
ISSN (Print)0302-9743

Conference

ConferenceTACAS 2015
CountryUnited Kingdom
CityLondon
Period13/04/1517/04/15

Activities

This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 26451795