Generating synchronization statements in divide-and-conquer programs

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

Divide-and-conquer is a well-known and important programming model that supports efficient execution of parallel applications on multi-cores, clusters, and grids. In divide-and-conquer systems such as Satin or Cilk, recursive calls are automatically transformed into jobs that execute asynchronously. Since the calls are non-blocking, consecutive calls are the source of parallelism. However, programmers have to manually enforce synchronization with sync statements that indicate where the system has to wait for the result of the asynchronous jobs. In this article, we investigate the feasibility of automatically inserting sync statements to relieve programmers of the burden of thinking about synchronization. We investigate whether correctness can be guaranteed and to what extent the amount of parallelism is reduced. We discuss the code analysis algorithms that are needed in detail. To evaluate our approach, we have extended the Satin divide-and-conquer system, which targets efficient execution on grids, with a sync generator. Our experiments show that, with our analysis, we can automatically generate synchronization statements in virtually all real-life cases: in 31 out of 35 real-world applications the sync statements are placed optimally. The automatic placement is correct in all cases, and in one case the sync generator corrected synchronization errors in an application (FFT). © 2011 Elsevier B.V. All rights reserved.
Original languageEnglish
Pages (from-to)75-89
JournalParallel computing
Volume38
Issue number1-2
DOIs
Publication statusPublished - 2012

Fingerprint

Divide and conquer
Synchronization
Parallelism
Generator
Grid
Algorithm Analysis
Parallel Applications
Real-world Applications
Fast Fourier transforms
Placement
Programming Model
Consecutive
Correctness
Target
Evaluate
Experiment
Experiments

Cite this

@article{8a288ce0aaed440f9f56dedc79013816,
title = "Generating synchronization statements in divide-and-conquer programs",
abstract = "Divide-and-conquer is a well-known and important programming model that supports efficient execution of parallel applications on multi-cores, clusters, and grids. In divide-and-conquer systems such as Satin or Cilk, recursive calls are automatically transformed into jobs that execute asynchronously. Since the calls are non-blocking, consecutive calls are the source of parallelism. However, programmers have to manually enforce synchronization with sync statements that indicate where the system has to wait for the result of the asynchronous jobs. In this article, we investigate the feasibility of automatically inserting sync statements to relieve programmers of the burden of thinking about synchronization. We investigate whether correctness can be guaranteed and to what extent the amount of parallelism is reduced. We discuss the code analysis algorithms that are needed in detail. To evaluate our approach, we have extended the Satin divide-and-conquer system, which targets efficient execution on grids, with a sync generator. Our experiments show that, with our analysis, we can automatically generate synchronization statements in virtually all real-life cases: in 31 out of 35 real-world applications the sync statements are placed optimally. The automatic placement is correct in all cases, and in one case the sync generator corrected synchronization errors in an application (FFT). {\circledC} 2011 Elsevier B.V. All rights reserved.",
author = "H.P. Hijma and {van Nieuwpoort}, R.V. and C.J.H. Jacobs and H.E. Bal",
year = "2012",
doi = "10.1016/j.parco.2011.10.007",
language = "English",
volume = "38",
pages = "75--89",
journal = "Parallel computing",
issn = "0167-8191",
publisher = "Elsevier",
number = "1-2",

}

Generating synchronization statements in divide-and-conquer programs. / Hijma, H.P.; van Nieuwpoort, R.V.; Jacobs, C.J.H.; Bal, H.E.

In: Parallel computing, Vol. 38, No. 1-2, 2012, p. 75-89.

Research output: Contribution to JournalArticleAcademicpeer-review

TY - JOUR

T1 - Generating synchronization statements in divide-and-conquer programs

AU - Hijma, H.P.

AU - van Nieuwpoort, R.V.

AU - Jacobs, C.J.H.

AU - Bal, H.E.

PY - 2012

Y1 - 2012

N2 - Divide-and-conquer is a well-known and important programming model that supports efficient execution of parallel applications on multi-cores, clusters, and grids. In divide-and-conquer systems such as Satin or Cilk, recursive calls are automatically transformed into jobs that execute asynchronously. Since the calls are non-blocking, consecutive calls are the source of parallelism. However, programmers have to manually enforce synchronization with sync statements that indicate where the system has to wait for the result of the asynchronous jobs. In this article, we investigate the feasibility of automatically inserting sync statements to relieve programmers of the burden of thinking about synchronization. We investigate whether correctness can be guaranteed and to what extent the amount of parallelism is reduced. We discuss the code analysis algorithms that are needed in detail. To evaluate our approach, we have extended the Satin divide-and-conquer system, which targets efficient execution on grids, with a sync generator. Our experiments show that, with our analysis, we can automatically generate synchronization statements in virtually all real-life cases: in 31 out of 35 real-world applications the sync statements are placed optimally. The automatic placement is correct in all cases, and in one case the sync generator corrected synchronization errors in an application (FFT). © 2011 Elsevier B.V. All rights reserved.

AB - Divide-and-conquer is a well-known and important programming model that supports efficient execution of parallel applications on multi-cores, clusters, and grids. In divide-and-conquer systems such as Satin or Cilk, recursive calls are automatically transformed into jobs that execute asynchronously. Since the calls are non-blocking, consecutive calls are the source of parallelism. However, programmers have to manually enforce synchronization with sync statements that indicate where the system has to wait for the result of the asynchronous jobs. In this article, we investigate the feasibility of automatically inserting sync statements to relieve programmers of the burden of thinking about synchronization. We investigate whether correctness can be guaranteed and to what extent the amount of parallelism is reduced. We discuss the code analysis algorithms that are needed in detail. To evaluate our approach, we have extended the Satin divide-and-conquer system, which targets efficient execution on grids, with a sync generator. Our experiments show that, with our analysis, we can automatically generate synchronization statements in virtually all real-life cases: in 31 out of 35 real-world applications the sync statements are placed optimally. The automatic placement is correct in all cases, and in one case the sync generator corrected synchronization errors in an application (FFT). © 2011 Elsevier B.V. All rights reserved.

U2 - 10.1016/j.parco.2011.10.007

DO - 10.1016/j.parco.2011.10.007

M3 - Article

VL - 38

SP - 75

EP - 89

JO - Parallel computing

JF - Parallel computing

SN - 0167-8191

IS - 1-2

ER -