Resynchronization of cyclo-static dataflow graphs

Joost P.H.M. Hausmans, Marco J.G. Bekooij, Henk Corporaal

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

3 Citations (Scopus)

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.

Original languageEnglish
Title of host publicationProceedings - Design, Automation and Test in Europe Conference and Exhibition, DATE 2011
Pages1315-1320
Number of pages6
Publication statusPublished - 2011
Event14th Design, Automation and Test in Europe Conference and Exhibition, DATE 2011 - Grenoble, France
Duration: 14 Mar 201118 Mar 2011

Conference

Conference14th Design, Automation and Test in Europe Conference and Exhibition, DATE 2011
Country/TerritoryFrance
CityGrenoble
Period14/03/1118/03/11

Fingerprint

Dive into the research topics of 'Resynchronization of cyclo-static dataflow graphs'. Together they form a unique fingerprint.

Cite this