Latency Minimization for Synchronous Data Flow Graphs
- 1 August 2007
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 189-196
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.Keywords
This publication has 13 references indexed in Scilit:
- Latency Minimization for Synchronous Data Flow Graphs2007
- Throughput Analysis of Synchronous Data Flow Graphs2006
- Exploring trade-offs in buffer requirements and throughput constraints for synchronous dataflow graphs2006
- Experimental analysis of the fastest optimum cycle ratio and mean algorithmsACM Transactions on Design Automation of Electronic Systems, 2004
- Task-level timing models for guaranteed performance in multiprocessor networks-on-chip2003
- Scheduling for optimum data memory compaction in block diagram oriented software synthesis2002
- Faster maximum and minimum mean cycle algorithms for system-performance analysisIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1998
- Faster parametric shortest path and minimum‐balance algorithmsNetworks, 1991
- Static Scheduling of Synchronous Data Flow Programs for Digital Signal ProcessingIEEE Transactions on Computers, 1987
- A characterization of the minimum cycle mean in a digraphDiscrete Mathematics, 1978