Double Inspection for Run-Time Loop Parallelization

Philippsen M, Tilmann N, Brinkers D (2013)

Publication Language: English

Publication Type: Conference contribution, Original article

Publication year: 2013

Publisher: Springer

Series: Lecture Notes in Computer Science (LNCS)

City/Town: Berlin Heidelberg

Book Volume: 7146

Pages Range: 46-60

Conference Proceedings Title: Languages and Compilers for Parallel Computing, 24th International Workshop, LCPC 2011

Event location: Fort Collins, CO, USA US

ISBN: 978-3-642-36035-0

DOI: 10.1007/978-3-642-36036-7_4

Abstract

The Inspector/Executor is well-known for parallelizing loops with irregular access patterns that cannot be analyzed statically. The downsides of existing inspectors are that it is hard to amortize their high run-time overheads by actually executing the loop in parallel, that they can only be applied to loops with dependencies that do not change during their execution and that they are often specifically designed for array codes and are in general not applicable in object oriented just-in-time compilation. In this paper we present an inspector that inspects a loop twice to detect if it is fully parallelizable. It works for arbitrary memory access patterns, is conservative as it notices if changing data dependencies would cause errors in a potential parallel execution, and most importantly, as it is designed for current multicore architectures it is fast - despite of its double inspection effort: it pays off at its first use. On benchmarks we can amortize the inspection overhead and outperform the sequential version from 2 or 3 cores onward. © 2013 Springer-Verlag.

Authors with CRIS profile

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

How to cite

APA:

Philippsen, M., Tilmann, N., & Brinkers, D. (2013). Double Inspection for Run-Time Loop Parallelization. In Sanjay Rajopadhye, Michelle Mills Strout (Eds.), Languages and Compilers for Parallel Computing, 24th International Workshop, LCPC 2011 (pp. 46-60). Fort Collins, CO, USA, US: Berlin Heidelberg: Springer.

MLA:

Philippsen, Michael, Nikolai Tilmann, and Daniel Brinkers. "Double Inspection for Run-Time Loop Parallelization." Proceedings of the 24th International Workshop on Languages and Compilers for Parallel Computing (LCPC 2011), Fort Collins, CO, USA Ed. Sanjay Rajopadhye, Michelle Mills Strout, Berlin Heidelberg: Springer, 2013. 46-60.

BibTeX: Download