Resynchronization of Cyclo-Static Dataflow Graphs

J.P.H.M. Hausmans, Marco Jan Gerrit Bekooij, Henk Corporaal

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

    3 Citations (Scopus)


    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 languageUndefined
    Title of host publicationDesign, Automation & Test in Europe Conference & Exhibition, DATE 2011
    Place of PublicationUSA
    PublisherIEEE Computer Society
    Number of pages6
    ISBN (Print)978-1-61284-208-0
    Publication statusPublished - 17 Mar 2011
    Event2011 Design, Automation & Test in Europe Conference & Exhibition, DATE 2011 - Grenoble, France
    Duration: 14 Mar 201118 Mar 2011

    Publication series

    PublisherIEEE Computer Society
    ISSN (Print)1530-1591


    Conference2011 Design, Automation & Test in Europe Conference & Exhibition, DATE 2011
    Abbreviated titleDATE


    • METIS-278758
    • EWI-20434
    • IR-78100

    Cite this