Latency Minimization for Synchronous Data Flow Graphs
Synchronous Data Flow Graphs (SDFGs) are a very
useful means for modeling and analyzing streaming applications.
Some performance indicators, such as throughput, have been studied before. Although throughput is a very useful performance indicator for concurrent real-time applications, another important
metric is latency. Especially for applications such as video conferencing, telephony and games, latency beyond a certain limit
cannot be tolerated. This paper proposes an algorithm to determine the minimal achievable latency, providing an execution
scheme for executing an SDFG with this latency. In addition, a
heuristic is proposed for optimizing latency under a throughput
constraint. Experimental results show that latency computations
are efficient despite the theoretical complexity of the problem. Substantial latency improvements are obtained, of 24-54% on average
for a synthetic benchmark of 900 models, and up to 37% for a
benchmark of six real DSP and multimedia models. The heuristic
for minimizing latency under a throughput constraint gives optimal latency and throughput results under a constraint of maximal
throughput for all DSP and multimedia models, and for over 95%
of the synthetic models.
-
Latency Minimization for Synchronous Data Flow Graphs
A.H. Ghamarian, S. Stuijk, T. Basten, M.C.W. Geilen, B.D. Theelen.
In H. Kubatova, editor, Digital System Design, 10th EUROMICRO Conference, DSD 2007, Proceedings, pages 189-196. Lübeck, Germany, 29-31 August 2007. IEEE Computer Society Press, Los Alamitos, CA, USA, 2007. (abstract, pdf).
|
