Synchronous Dataflow

Analysis techniques

Consistency

Tool sdf3analysis-sdf --algo 'consistency'
API isSDFgraphConsistent()

Consistency of an SDFG is an important property. A non-consistent SDFG requires unbounded memory to execute or it deadclocks during its execution. An SDFG is called consistent if its repetition vector is not equal to the null-vector.

This example shows an SDFG that is inconsistent. Actor A produces too few tokens on the channel between A and B to allow an infinite execution of the graph. Note that the number of initial tokens does not influence the concistency of an SDFG.

MCM/MCR analysis

Tool sdf3analysis-sdf --algo 'mcm[(cycle,dasdan,karp,howard,yto,yto-mcr)]'
API maximumCycleMeanCycles() / maximumCycleMeanDasdanGupta() / maximumCycleMeanKarp() / maximumCycleMeanHoward() / maximumCycleYoungTarjanOrlin()

Maximum Cycle Mean (MCM) or Maximum Cycle Ratio (MCR) analysis is the most commenly used means to compute the throughput of an SDFG. It requires a conversion of the SDFG to its correpsonding HSDFG. After that, an MCR algorithm can be performed. Alternatively, the HSDFG can be converted into a weighted directed graph on which an MCM algorithm can be executed. The later requires a longest-path computation on the HSDFG. In Ghamarian06, it is shown that both the MCM and MCR approach are typically slower then the state-space technique presented in this paper. SDF3 implement the MCR algorithm from Young-Tarjan-Orlin and five different MCM algorithms (cycle-based, Howard, Dadan-Gupta, Young-Tarjan-Orlin and Karp). SDF3 also implements the state-based approach from Ghamarian06.

In this example, the throughput of the SDFG is computed using an MCM algorithm. The critical cycle (the cycle limiting the throughput), is the upper cycle in the HSDFG. The execution time of the actors on the cycle is equal to two time-units and only one token is present on the cycle.

Compute the repetition vector

Tool sdf3analysis-sdf --algo 'repetition_vector'
API computeRepetitionVector()

The repetition vector indicates how often each actor must fire with respect to other actors without a net chance in the token distribution.

In this example, the repetition vector indicates that actor A should fire 3 times, actor B 2 times and actor C 1 time to have no chance in the tokens on the channels.

Trade-offs between throughput and storage-space

Tool sdf3analysis-sdf --algo 'buffersize'
API class SDFstateSpaceBufferAnalysis

In Stuijk06DAC, a technique is presented to compute all possible optimal trade-offs between the storage-space allocated to the channels of an SDFG and the maximal throughput realized under these storage-space constraints.

The figure at the bottom shows the complete trade-off space for the SDFG shown at the top.