Concurrent Circular Reference Attribute Grammars

Jesper Öqvist; Görel Hedin

doi:10.1145/3136014.3136032

Concurrent Circular Reference Attribute Grammars

Forskningsoutput: Kapitel i bok/rapport/Conference proceeding › Konferenspaper i proceeding › Peer review

Sammanfattning

Reference Attribute Grammars (RAGs) is a declarative executable formalism used for constructing compilers and related tools. Existing implementations support concurrent evaluation only with global evaluation locks. This may lead to long latencies in interactive tools, where interactive and background threads query attributes concurrently.

We present lock-free algorithms for concurrent attribute evaluation, enabling low latency in interactive tools. Our algorithms support important extensions to RAGs like circular (fixed-point) attributes and higher-order attributes.

We have implemented our algorithms in Java, for the JastAdd metacompiler. We evaluate the implementation on a JastAdd-specified compiler for the Java language, demonstrating very low latencies for interactive attribute queries, on the order of milliseconds. Furthermore, initial experiments show a speedup of about a factor 2 when using four parallel compilation threads.

Originalspråk	engelska
Titel på värdpublikation	Proceedings of the 10th ACM SIGPLAN International Conference on Software Language Engineering
Förlag	Association for Computing Machinery (ACM)
Sidor	151-162
Antal sidor	12
ISBN (elektroniskt)	978-1-4503-5525-4
DOI	https://doi.org/10.1145/3136014.3136032
Status	Published - 2017 okt. 23
Evenemang	10th ACM SIGPLAN International Conference on Software Language Engineering (SLE 2017) - Vancouver, BC, Canada — October 23 - 24, 2017, Vancouve, Kanada Varaktighet: 2017 okt. 23 → 2017 okt. 24

Konferens

Konferens	10th ACM SIGPLAN International Conference on Software Language Engineering (SLE 2017)
Land/Territorium	Kanada
Ort	Vancouve
Period	2017/10/23 → 2017/10/24

Ämnesklassifikation (UKÄ)

Datavetenskap (datalogi)

Tillgång till dokument

10.1145/3136014.3136032

1 Doktorsavhandling (sammanläggning)

Contributions to Declarative Implementation of Static Program Analysis
Öqvist, J., 2018 dec. 19, Lund: Department of Computer Science, Lund University. 197 s.
Forskningsoutput: Avhandling › Doktorsavhandling (sammanläggning)

Öppen tillgång
Fil

2 Avslutade

ELLIIT LU P05: Scalable Language Tools for Cyber-Physical Systems
Hedin, G., Fors, N. & Öqvist, J.
2016/01/01 → 2020/12/31
Projekt: Forskning
Bidrag till deklarativ utveckling av statisk programanalys
Öqvist, J., Hedin, G., Magnusson, B. & Söderberg, E.
Swedish Research Council
2013/02/01 → 2019/01/31
Projekt: Avhandling

Citera det här

@inproceedings{2b62015f726842dab4a59f0fa975138a,

title = "Concurrent Circular Reference Attribute Grammars",

abstract = "Reference Attribute Grammars (RAGs) is a declarative executable formalism used for constructing compilers and related tools. Existing implementations support concurrent evaluation only with global evaluation locks. This may lead to long latencies in interactive tools, where interactive and background threads query attributes concurrently.We present lock-free algorithms for concurrent attribute evaluation, enabling low latency in interactive tools. Our algorithms support important extensions to RAGs like circular (fixed-point) attributes and higher-order attributes.We have implemented our algorithms in Java, for the JastAdd metacompiler. We evaluate the implementation on a JastAdd-specified compiler for the Java language, demonstrating very low latencies for interactive attribute queries, on the order of milliseconds. Furthermore, initial experiments show a speedup of about a factor 2 when using four parallel compilation threads.",

keywords = "reference attribute grammar, concurrency, parallelization, memoization, circular attributes",

author = "Jesper {\"O}qvist and G{\"o}rel Hedin",

year = "2017",

month = oct,

day = "23",

doi = "10.1145/3136014.3136032",

language = "English",

pages = "151--162",

booktitle = "Proceedings of the 10th ACM SIGPLAN International Conference on Software Language Engineering",

publisher = "Association for Computing Machinery (ACM)",

address = "United States",

note = "10th ACM SIGPLAN International Conference on Software Language Engineering (SLE 2017) ; Conference date: 23-10-2017 Through 24-10-2017",

}

Öqvist, J & Hedin, G 2017, Concurrent Circular Reference Attribute Grammars. i Proceedings of the 10th ACM SIGPLAN International Conference on Software Language Engineering. Association for Computing Machinery (ACM), s. 151-162, 10th ACM SIGPLAN International Conference on Software Language Engineering (SLE 2017) , Vancouve, Kanada, 2017/10/23. https://doi.org/10.1145/3136014.3136032

TY - GEN

T1 - Concurrent Circular Reference Attribute Grammars

AU - Öqvist, Jesper

AU - Hedin, Görel

PY - 2017/10/23

Y1 - 2017/10/23

N2 - Reference Attribute Grammars (RAGs) is a declarative executable formalism used for constructing compilers and related tools. Existing implementations support concurrent evaluation only with global evaluation locks. This may lead to long latencies in interactive tools, where interactive and background threads query attributes concurrently.We present lock-free algorithms for concurrent attribute evaluation, enabling low latency in interactive tools. Our algorithms support important extensions to RAGs like circular (fixed-point) attributes and higher-order attributes.We have implemented our algorithms in Java, for the JastAdd metacompiler. We evaluate the implementation on a JastAdd-specified compiler for the Java language, demonstrating very low latencies for interactive attribute queries, on the order of milliseconds. Furthermore, initial experiments show a speedup of about a factor 2 when using four parallel compilation threads.

AB - Reference Attribute Grammars (RAGs) is a declarative executable formalism used for constructing compilers and related tools. Existing implementations support concurrent evaluation only with global evaluation locks. This may lead to long latencies in interactive tools, where interactive and background threads query attributes concurrently.We present lock-free algorithms for concurrent attribute evaluation, enabling low latency in interactive tools. Our algorithms support important extensions to RAGs like circular (fixed-point) attributes and higher-order attributes.We have implemented our algorithms in Java, for the JastAdd metacompiler. We evaluate the implementation on a JastAdd-specified compiler for the Java language, demonstrating very low latencies for interactive attribute queries, on the order of milliseconds. Furthermore, initial experiments show a speedup of about a factor 2 when using four parallel compilation threads.

KW - reference attribute grammar

KW - concurrency

KW - parallelization

KW - memoization

KW - circular attributes

U2 - 10.1145/3136014.3136032

DO - 10.1145/3136014.3136032

M3 - Paper in conference proceeding

SP - 151

EP - 162

BT - Proceedings of the 10th ACM SIGPLAN International Conference on Software Language Engineering

PB - Association for Computing Machinery (ACM)

T2 - 10th ACM SIGPLAN International Conference on Software Language Engineering (SLE 2017)

Y2 - 23 October 2017 through 24 October 2017

ER -

Concurrent Circular Reference Attribute Grammars

Sammanfattning

Konferens

Ämnesklassifikation (UKÄ)

Tillgång till dokument

Fingeravtryck

Forskningsoutput

Contributions to Declarative Implementation of Static Program Analysis

Projekt

ELLIIT LU P05: Scalable Language Tools for Cyber-Physical Systems

Bidrag till deklarativ utveckling av statisk programanalys

Citera det här