Resynchronization of Cyclo-Static Dataflow Graphs


Hausmans, Joost P.H.M. and Bekooij, Marco J.G. and Corporaal, Henk (2011) Resynchronization of Cyclo-Static Dataflow Graphs. In: Design, Automation & Test in Europe Conference & Exhibition, DATE 2011, 14-18 March 2011, Grenoble, France (pp. pp. 1-6).

[img] PDF
Restricted to UT campus only
: Request a copy
Abstract:Parallel stream processing applications are often executed on shared-memory multiprocessor systems. Synchronization between tasks is needed to guarantee correct functional behavior. An increase in the communication granularity of the tasks in the parallel application can decrease the synchronization overhead. However using coarser-grained synchronization can result in deadlock or violation of the throughput constraint for the application in case of cyclic data dependencies. Resynchronization tries to change the synchronization behavior in order to reduce the synchronization overhead. Determining the amount of resynchronization while preventing deadlock and satisfying the throughput constraint of the application, forms a global analysis problem. In this paper we present a Linear Programming (LP) algorithm for minimizing synchronization by means of resynchronization that is based on the properties of dataflow models. We demonstrate our approach with an extended Constant Modulus Algorithm (CMA) in a beam-forming application. For this application we reduce the number of synchronization statements with 30% while having a memory constraint of 200 tokens. The algorithm which calculates this reduction takes less than 20 milliseconds for this problem instance.
Item Type:Conference or Workshop Item
Copyright:© 2011 IEEE
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:
Official URL:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page