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} }