Cycle-Breaking Techniques for Scheduling Synchronous Dataflow Graphs

Abstract

System-level modeling, simulation, and synthesis using the synchronous dataflow (SDF) model of computation is widespread in design automation for communication and digital signal processing (DSP) systems. SDF scheduling has a large impact on the performance and memory requirements of implementations. One of the major problems in scheduling SDF graphs is that the existence of cycles in the targeted systems prevents or greatly restricts application of many useful optimization techniques that are available for acyclic SDF graphs. The loose interdependence algorithms framework (LIAF) has been developed to decompose cycles in SDF graphs into hierarchies of acyclic subgraphs whenever possible. However, LIAF does not specify any specific algorithm to break cycles, but rather it specifies the constraints that such an algorithm must satisfy. In this report, we present a low-complexity (linear-time) cycle-breaking algorithm for decomposing and breaking cycles in SDF graphs so that subsequent acyclic scheduling techniques can be easily applied. We also present a technique for computing buffer bounds on edges that are removed during the cycle-breaking process so that buffer sizes can be computed for such edges. We have implemented our cycle-breaking algorithm and buffer size computation technique in the state-of-art simulation-oriented scheduler, and our results demonstrate the effectiveness of these techniques.