Analysis techniques for static dataflow models with access patterns

Signal processing and multimedia applications are commonly specified using Static Dataflow (SDF) models. The SDF model explicitly captures how much data is produced and consumed during computation. This results in strong compile time predictability of many useful execution properties. However, the SDF model is limited in its ability to specify how this data is accessed in time. This often leads to sub-optimal implementations that may use more resources than necessary. An extension to the SDF model, called Static Dataflow with Access Patterns (SDF-AP), overcomes this limitation and captures the precise timing of data accesses. The SDF-AP model retains the analyzability of SDF-like models while accurately capturing the interface timing behavior by including access patterns. The main contribution of this paper is a formalization of static analysis techniques for the SDF-AP model. We discuss properties of the SDF-AP model related to boundedness, deadlock, throughput, and buffer size and present algorithms to analyze them. Based on these properties, we demonstrate a tool to efficiently capture, analyze, and deploy practical signal processing applications modeled in SDF-AP on hardware targets.