Provably efficient randomized work stealing with first-class parallel loops

In parallel computing, do-all parallel loops are often a target for optimizations as loop iterations can be executed independently in any order and thus contribute to high parallelism. Techniques such as divide-and-conquer and lazy binary splitting have proven to be efficient in theory and/or in practice. However, these approaches can potentially be improved in terms of lower number of unnecessary splits and better cache efficiency. In this thesis, I introduce the design of first-class LoopFrame for parallel loops, which follows dynamic splitting protocol and is efficient in terms of cache-locality and execution time in randomized work stealing. In particular, two versions of LoopFrames are presented: 1-D LoopFrame and an extension to multi-dimensional (M-D) LoopFrame, for non-nested and nested parallel loops, respectively. This paper mainly contributes the theoretical analysis on execution time of randomized work stealing with both versions of LoopFrames. The execution time is asymptotically preserved and remained efficient, i.e., randomized work stealing with LoopFrames has an expected runtime of 0(T1/p+T[infinity], where T1 is the work (total computation) and T[infinity] is the span (length of longest dependency path). On the implementation side, M-D LoopFrame is benchmarked against nested forloops and divide-and-conquer methods on a matrix multiplication computation on a single processor. M-D LoopFrame proves to have efficient D1 cache misses, approximately the same as the divide-and-conquer method and 10x to 100x more efficient than for-loops. Execution time-wise, on multiplication of size 4001 square matrices, M-D LoopFrame runs approximately 50% faster than both nested for-loops and divide-and-conquer at grainsize 32.

Name thesis:degree_name

Master

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2019

Author dc:creator

• Pitimanaaree, Nipun.

Advisor dc:contributor.advisor

• Tao B. Schardl.

• Electrical Engineering and Computer Science.

Statement dc:rights

• MIT theses are protected by copyright. They may be viewed, downloaded, or printed from this source but further reproduction or distribution in any format is prohibited without written permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/123035

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/123035