Executing Task Graphs Using Work-Stealing
NABBIT is a work-stealing library for execution of task graphs with arbitrary dependencies which is implemented as a library for the multithreaded programming language Cilk++. We prove that Nabbit executes static task graphs in parallel in time which is asymptotically optimal for graphs whose nodes...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2012
|
| Online Access: | http://hdl.handle.net/1721.1/73204 https://orcid.org/0000-0001-8783-0274 |
| _version_ | 1826216611918381056 |
|---|---|
| author | Agrawal, Kunal Leiserson, Charles E. Sukha, Jim |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Agrawal, Kunal Leiserson, Charles E. Sukha, Jim |
| author_sort | Agrawal, Kunal |
| collection | MIT |
| description | NABBIT is a work-stealing library for execution of task graphs with arbitrary dependencies which is implemented as a library for the multithreaded programming language Cilk++. We prove that Nabbit executes static task graphs in parallel in time which is asymptotically optimal for graphs whose nodes have constant in-degree and out-degree. To evaluate the performance of Nabbit, we implemented a dynamic program representing the Smith-Waterman algorithm, an irregular dynamic program on a two-dimensional grid. Our experiments indicate that when task-graph nodes are mapped to reasonably sized blocks, Nabbit exhibits low overhead and scales as well as or better than other scheduling strategies. The Nabbit implementation that solves the dynamic program using a task graph even manages in some cases to outperform a divide-and-conquer implementation for directly solving the same dynamic program. Finally, we extend both the Nabbit implementation and the completion-time bounds to handle dynamic task graphs, that is, graphs whose nodes and edges are created on the fly at runtime. |
| first_indexed | 2024-09-23T16:50:13Z |
| format | Article |
| id | mit-1721.1/73204 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T16:50:13Z |
| publishDate | 2012 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/732042022-09-29T21:51:17Z Executing Task Graphs Using Work-Stealing Agrawal, Kunal Leiserson, Charles E. Sukha, Jim Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Leiserson, Charles E. Sukha, Jim NABBIT is a work-stealing library for execution of task graphs with arbitrary dependencies which is implemented as a library for the multithreaded programming language Cilk++. We prove that Nabbit executes static task graphs in parallel in time which is asymptotically optimal for graphs whose nodes have constant in-degree and out-degree. To evaluate the performance of Nabbit, we implemented a dynamic program representing the Smith-Waterman algorithm, an irregular dynamic program on a two-dimensional grid. Our experiments indicate that when task-graph nodes are mapped to reasonably sized blocks, Nabbit exhibits low overhead and scales as well as or better than other scheduling strategies. The Nabbit implementation that solves the dynamic program using a task graph even manages in some cases to outperform a divide-and-conquer implementation for directly solving the same dynamic program. Finally, we extend both the Nabbit implementation and the completion-time bounds to handle dynamic task graphs, that is, graphs whose nodes and edges are created on the fly at runtime. National Science Foundation (U.S.) (Grant 0615215) 2012-09-27T14:55:39Z 2012-09-27T14:55:39Z 2010-05 2010-04 Article http://purl.org/eprint/type/ConferencePaper 978-1-4244-6442-5 1530-2075 http://hdl.handle.net/1721.1/73204 Agrawal, Kunal, Charles E. Leiserson, and Jim Sukha. “Executing Task Graphs Using Work-stealing.” Proceedings of the IEEE International Symposium on Parallel & Distributed Processing (IPDPS), 2010. 1–12. © Copyright 2010 IEEE https://orcid.org/0000-0001-8783-0274 en_US http://dx.doi.org/10.1109/IPDPS.2010.5470403 Proceedings of the IEEE International Symposium on Parallel & Distributed Processing (IPDPS), 2010 Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Institute of Electrical and Electronics Engineers (IEEE) IEEE |
| spellingShingle | Agrawal, Kunal Leiserson, Charles E. Sukha, Jim Executing Task Graphs Using Work-Stealing |
| title | Executing Task Graphs Using Work-Stealing |
| title_full | Executing Task Graphs Using Work-Stealing |
| title_fullStr | Executing Task Graphs Using Work-Stealing |
| title_full_unstemmed | Executing Task Graphs Using Work-Stealing |
| title_short | Executing Task Graphs Using Work-Stealing |
| title_sort | executing task graphs using work stealing |
| url | http://hdl.handle.net/1721.1/73204 https://orcid.org/0000-0001-8783-0274 |
| work_keys_str_mv | AT agrawalkunal executingtaskgraphsusingworkstealing AT leisersoncharlese executingtaskgraphsusingworkstealing AT sukhajim executingtaskgraphsusingworkstealing |