Advanced

Concurrent Circular Reference Attribute Grammars (Extended Version)

Öqvist, Jesper LU and Hedin, Görel LU (2017) In Technical report, LU-CS-TR 2017-254(Report 103).
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... (More)
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. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Book/Report
publication status
published
subject
keywords
Reference Attribute Grammar, Concurrency, Parallelization, Memoization, Circular Attributes
in
Technical report, LU-CS-TR
volume
2017-254
issue
Report 103
pages
20 pages
publisher
Department of Computer Science, Lund University
ISSN
1404-1200
language
English
LU publication?
yes
id
4809a5fc-f7e3-4082-bf41-314091c98e0d
date added to LUP
2017-10-19 11:50:17
date last changed
2017-10-23 10:14:22
@techreport{4809a5fc-f7e3-4082-bf41-314091c98e0d,
  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.<br/><br/>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.<br/><br/>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.},
  author       = {Öqvist, Jesper and Hedin, Görel},
  institution  = {Department of Computer Science, Lund University},
  issn         = {1404-1200},
  keyword      = {Reference Attribute Grammar,Concurrency,Parallelization,Memoization,Circular Attributes},
  language     = {eng},
  month        = {10},
  number       = {Report 103},
  pages        = {20},
  series       = {Technical report, LU-CS-TR},
  title        = {Concurrent Circular Reference Attribute Grammars (Extended Version)},
  volume       = {2017-254},
  year         = {2017},
}