Latency Minimization for Synchronous Data Flow Graphs
Abstract. 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 Digital System Design, 10th Euromicro Conference, DSD 07 Proceedings, pages 189-196. Lübeck, Germany, 27-30 August 2007. IEEE Computer Society Press, Los Alamitos, CA, USA, 2007. (abstract, pdf, doi).