Provably efficient randomized work stealing with first-class parallel loops
This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2019
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/1721.1/123035 |
| _version_ | 1811092842625368064 |
|---|---|
| author | Pitimanaaree, Nipun. |
| author2 | Tao B. Schardl. |
| author_facet | Tao B. Schardl. Pitimanaaree, Nipun. |
| author_sort | Pitimanaaree, Nipun. |
| collection | MIT |
| description | This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. |
| first_indexed | 2024-09-23T15:29:49Z |
| format | Thesis |
| id | mit-1721.1/123035 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T15:29:49Z |
| publishDate | 2019 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1230352019-11-22T03:05:38Z Provably efficient randomized work stealing with first-class parallel loops Pitimanaaree, Nipun. Tao B. Schardl. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Electrical Engineering and Computer Science. This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2019 Cataloged from student-submitted PDF version of thesis. Includes bibliographical references (pages 67-68). 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. by Nipun Pitimanaaree. M. Eng. M.Eng. Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science 2019-11-22T00:03:33Z 2019-11-22T00:03:33Z 2019 2019 Thesis https://hdl.handle.net/1721.1/123035 1127650653 eng 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. http://dspace.mit.edu/handle/1721.1/7582 68 pages application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Pitimanaaree, Nipun. Provably efficient randomized work stealing with first-class parallel loops |
| title | Provably efficient randomized work stealing with first-class parallel loops |
| title_full | Provably efficient randomized work stealing with first-class parallel loops |
| title_fullStr | Provably efficient randomized work stealing with first-class parallel loops |
| title_full_unstemmed | Provably efficient randomized work stealing with first-class parallel loops |
| title_short | Provably efficient randomized work stealing with first-class parallel loops |
| title_sort | provably efficient randomized work stealing with first class parallel loops |
| topic | Electrical Engineering and Computer Science. |
| url | https://hdl.handle.net/1721.1/123035 |
| work_keys_str_mv | AT pitimanaareenipun provablyefficientrandomizedworkstealingwithfirstclassparallelloops |