Paper Info
Title
A rule-based quasi-static scheduling approach for static islands in dynamic dataflow graphs
Abstract
In this article, an efficient rule-based clustering algorithm for static dataflow subgraphs in a dynamic dataflow graph is presented. The clustered static dataflow actors are quasi-statically scheduled, in such a way that the global performance in terms of latency and throughput is improved compared to a dynamically scheduled execution, while avoiding the introduction of deadlocks as generated by naive static scheduling approaches. The presented clustering algorithm outperforms previously published approaches by a faster computation and more compact representation of the derived quasi-static schedule. This is achieved by a rule-based approach, which avoids an explicit enumeration of the state space. A formal proof of the correctness of the presented clustering approach is given. Experimental results show significant improvements in both, performance and code size, compared to a state-of-the-art clustering algorithm.
Year
DOI
Venue
2013
10.1145/2442116.2442124
ACM Trans. Embedded Comput. Syst.
Keywords
Field
DocType
clustering algorithm,rule-based approach,state-of-the-art clustering algorithm,clustering approach,rule-based quasi-static scheduling approach,dynamic dataflow graph,static dataflow subgraphs,static dataflow actor,static island,naive static scheduling approach,global performance,efficient rule-based clustering algorithm,data flow analysis,clustering,scheduling
Rule-based system,Data stream clustering,Correlation clustering,Computer science,Scheduling (computing),Correctness,Parallel computing,Theoretical computer science,Dataflow,Cluster analysis,Formal proof
Journal
Volume
Issue
ISSN
12
3
1539-9087
Citations 
PageRank 
References 
4
0.44
27
Authors
4
Name
Order
Citations
PageRank
Joachim Falk121517.27
Christian Zebelein2385.43
Christian Haubelt379668.77
Jürgen Teich42886273.54