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)

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 languageUndefined
Title of host publicationDesign, Automation & Test in Europe Conference & Exhibition, DATE 2011
Place of PublicationUSA
PublisherIEEE Computer Society
Pages1-6
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

Name
PublisherIEEE Computer Society
ISSN (Print)1530-1591

Conference

Conference2011 Design, Automation & Test in Europe Conference & Exhibition, DATE 2011
Abbreviated titleDATE
CountryFrance
CityGrenoble
Period14/03/1118/03/11

Keywords

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

Cite this

Hausmans, J. P. H. M., Bekooij, M. J. G., & Corporaal, H. (2011). Resynchronization of Cyclo-Static Dataflow Graphs. In Design, Automation & Test in Europe Conference & Exhibition, DATE 2011 (pp. 1-6). USA: IEEE Computer Society.
Hausmans, J.P.H.M. ; Bekooij, Marco Jan Gerrit ; Corporaal, Henk. / Resynchronization of Cyclo-Static Dataflow Graphs. Design, Automation & Test in Europe Conference & Exhibition, DATE 2011. USA : IEEE Computer Society, 2011. pp. 1-6
@inproceedings{41fc5813f45641138c584098f686c435,
title = "Resynchronization of Cyclo-Static Dataflow Graphs",
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.",
keywords = "METIS-278758, EWI-20434, IR-78100",
author = "J.P.H.M. Hausmans and Bekooij, {Marco Jan Gerrit} and Henk Corporaal",
year = "2011",
month = "3",
day = "17",
language = "Undefined",
isbn = "978-1-61284-208-0",
publisher = "IEEE Computer Society",
pages = "1--6",
booktitle = "Design, Automation & Test in Europe Conference & Exhibition, DATE 2011",
address = "United States",

}

Hausmans, JPHM, Bekooij, MJG & Corporaal, H 2011, Resynchronization of Cyclo-Static Dataflow Graphs. in Design, Automation & Test in Europe Conference & Exhibition, DATE 2011. IEEE Computer Society, USA, pp. 1-6, 2011 Design, Automation & Test in Europe Conference & Exhibition, DATE 2011, Grenoble, France, 14/03/11.

Resynchronization of Cyclo-Static Dataflow Graphs. / Hausmans, J.P.H.M.; Bekooij, Marco Jan Gerrit; Corporaal, Henk.

Design, Automation & Test in Europe Conference & Exhibition, DATE 2011. USA : IEEE Computer Society, 2011. p. 1-6.

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

TY - GEN

T1 - Resynchronization of Cyclo-Static Dataflow Graphs

AU - Hausmans, J.P.H.M.

AU - Bekooij, Marco Jan Gerrit

AU - Corporaal, Henk

PY - 2011/3/17

Y1 - 2011/3/17

N2 - 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.

AB - 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.

KW - METIS-278758

KW - EWI-20434

KW - IR-78100

M3 - Conference contribution

SN - 978-1-61284-208-0

SP - 1

EP - 6

BT - Design, Automation & Test in Europe Conference & Exhibition, DATE 2011

PB - IEEE Computer Society

CY - USA

ER -

Hausmans JPHM, Bekooij MJG, Corporaal H. Resynchronization of Cyclo-Static Dataflow Graphs. In Design, Automation & Test in Europe Conference & Exhibition, DATE 2011. USA: IEEE Computer Society. 2011. p. 1-6