Simultaneous inspection: Hiding the overhead of inspector-executor style dynamic parallelization

Brinkers D, Philippsen M, Veldema R (2015)

Publication Language: English

Publication Type: Conference contribution, Original article

Publication year: 2015

Journal

Lecture Notes in Computer Science Springer Verlag

Publisher: Springer-verlag

Edited Volumes: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Series: Lecture Notes in Computer Science (LNCS)

City/Town: Berlin Heidelberg

Book Volume: 7146

Pages Range: 101-115

Conference Proceedings Title: Languages and Compilers for Parallel Computing, 27th International Workshop, LCPC 2014

Event location: Hillsboro, OR, USA US

ISBN: 978-3-319-17472-3

DOI: 10.1007/978-3-319-17473-0_7

Abstract

A common approach for dynamic parallelization of loops at runtime is the inspector-executor pattern. The inspector first runs the loop without any (side) effects to analyze whether there are data dependences that would prevent parallel execution. Only if no such dependences are found, does the executor phase actually run the loop iterations in parallel. In previous works, the overhead of the inspection must either be amortized by the parallel execution or is completely wasted if the loop turns out to be non-parallelizable.

In this paper we propose to run the inspection phase simultaneous to an instrumented sequential version of the loop. This way we can reduce and hide the overhead in case of a non-parallelizable loop. We discuss what needs to be done so that the sequentially executed iterations do not invalidate the inspector’s concurrent work (in which case sequential execution is needed for the whole loop).

Our measurements show that if a loop cannot be executed in parallel there is an overhead below 1.6 % compared to the runtime of the original sequential loop. If the loop is parallelizable, we see speedups of up to a factor of 3.6 on a quad core processor.

Authors with CRIS profile

Daniel Brinkers Lehrstuhl für Informatik 2 (Programmiersysteme) Michael Philippsen Lehrstuhl für Informatik 2 (Programmiersysteme) Ronald Veldema Lehrstuhl für Informatik 2 (Programmiersysteme)

How to cite

APA:

Brinkers, D., Philippsen, M., & Veldema, R. (2015). Simultaneous inspection: Hiding the overhead of inspector-executor style dynamic parallelization. In James Brodman, Peng Tu (Eds.), Languages and Compilers for Parallel Computing, 27th International Workshop, LCPC 2014 (pp. 101-115). Hillsboro, OR, USA, US: Berlin Heidelberg: Springer-verlag.

MLA:

Brinkers, Daniel, Michael Philippsen, and Ronald Veldema. "Simultaneous inspection: Hiding the overhead of inspector-executor style dynamic parallelization." Proceedings of the International Workshop on Languages and Compilers for Parallel Computing (LCPC 2014), Hillsboro, OR, USA Ed. James Brodman, Peng Tu, Berlin Heidelberg: Springer-verlag, 2015. 101-115.

BibTeX: Download