Latency Minimization for Synchronous Data Flow Graphs
Ghamarian, AH Amir, Stuijk, Sander Sander, Basten, AA Twan, Geilen, MCW Marc, Theelen, BD Bart · 2007
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 stud-ied before. Although throughput is a very useful performance in-dicator for concurrent real-time applications, another important metric is latency. Especially for applications such as video con-ferencing, telephony and games, latency beyond a certain limit cannot be tolerated. This paper proposes an algorithm to de-termine 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 efcient despite the theoretical complexity of the problem. Sub-stantial 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 opti-mal latency and throughput results under a constraint of maximal throughput for all DSP and multimedia models, and for over 95% of the synthetic models.