Aggregate Update Problem for Multi-clocked Dataflow Languages
| Title | Aggregate Update Problem for Multi-clocked Dataflow Languages |
| Publication Type | Conference Paper |
| Year of Publication | 2022 |
| Authors | Kallwies, H, Leucker, M, Scheffel, T, Schmitz, M, Thoma, D |
| Conference Name | 2022 IEEE/ACM International Symposium on Code Generation and Optimization (CGO) |
| Publisher | IEEE Computer Society |
| Keywords | aggregate update problem, compiler optimization, dataflow |
| Abstract | Dataflow languages have, as well as functional languages, immutable semantics, which is often implemented by copying values. A common compiler optimization known from functional languages involves analyzing which data structures can be modified in-place instead of copying them. This paper presents a novel algorithm to this so called Aggregate Update Problem for multi-clocked dataflow languages, i.e. those that allow streams to have events at disjoint timestamps, like e.g. Lucid, Lustre and Signal. Unrestricted multi-clocked languages require a static triggering analysis on how events and hence data values are read, written and replicated. We use TeSSLa as a generic stream transformation language with a small set of operators to develop our ideas. We implemented the solution in a TeSSLa compiler targeting the Java VM via Scala code generation which combines persistent data structures and mutable data structures for those data values which allow in-place editing. Our empirical evaluation shows considerable speedup for use cases where queues, maps or sets are dominant data structures. |
| URL | https://doi.ieeecomputersociety.org/10.1109/CGO53902.2022.9741275 |
| DOI | 10.1109/CGO53902.2022.9741275 |
@inproceedings {1408,
title = {Aggregate Update Problem for Multi-clocked Dataflow Languages},
booktitle = {2022 IEEE/ACM International Symposium on Code Generation and Optimization (CGO)},
year = {2022},
publisher = {IEEE Computer Society},
organization = {IEEE Computer Society},
abstract = {<p>Dataflow languages have, as well as functional languages, immutable semantics, which is often implemented by copying values. A common compiler optimization known from functional languages involves analyzing which data structures can be modified in-place instead of copying them. This paper presents a novel algorithm to this so called Aggregate Update Problem for multi-clocked dataflow languages, i.e. those that allow streams to have events at disjoint timestamps, like e.g. Lucid, Lustre and Signal. Unrestricted multi-clocked languages require a static triggering analysis on how events and hence data values are read, written and replicated. We use TeSSLa as a generic stream transformation language with a small set of operators to develop our ideas. We implemented the solution in a TeSSLa compiler targeting the Java VM via Scala code generation which combines persistent data structures and mutable data structures for those data values which allow in-place editing. Our empirical evaluation shows considerable speedup for use cases where queues, maps or sets are dominant data structures.</p>
},
keywords = {aggregate update problem, compiler optimization, dataflow},
doi = {10.1109/CGO53902.2022.9741275},
url = {https://doi.ieeecomputersociety.org/10.1109/CGO53902.2022.9741275},
author = {Hannes Kallwies and Martin Leucker and Torben Scheffel and Malte Schmitz and Daniel Thoma}
}