Evaluation of Synchronous Dataflow Graph Mappings onto Distributed Memory Architectures
Youen Lesparre, Alix Munier-Kordon, Jean-Marc Delosme · 2016
The search of a mapping of a Synchronous Data Flow Graph (SDFG) on a distributed architecture that achieves a given throughput while satisfying memory constraints is a difficult challenge. Solving this problem calls for evaluating throughput and buffer capacities associated to a mapping. Since the available mapping evaluation methods are not polynomial with respect to the SDFG description, mapping techniques using them are not scalable. This paper develops a polynomial method for the evaluation of any given SDFG mapping on a distributed architecture. The method is based on a simple transformation of the SDFG to model communications through a Network on Chip. The key result is that the size of the memory required in order to guarantee the liveness or a given throughput of an application may be evaluated in polynomial time. Experimentally, computing the memory size guaranteeing liveness of a mapping of a 670-node H264 graph on a 4-cluster architecture takes 70 ms on an Intel Core i5-660 processor and grows linearly with graph size.