Simultaneous inspection: Hiding the overhead of inspector-executor style dynamic parallelization
Author(s): Brinkers D, Philippsen M, Veldema R
Editor(s): James Brodman, Peng Tu
Title edited volumes: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Publishing place: Berlin Heidelberg
Publication year: 2015
Title of series: Lecture Notes in Computer Science (LNCS)
Conference Proceedings Title: Languages and Compilers for Parallel Computing, 27th International Workshop, LCPC 2014
Pages range: 101-115
Event: International Workshop on Languages and Compilers for Parallel Computing (LCPC 2014)
Event location: Hillsboro, OR, USA
Start date of the event: 15/09/2014
End date of the event: 17/09/2014
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.
FAU Authors / FAU Editors Focus Area of Individual Faculties 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). 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.