Please use this identifier to cite or link to this item:
http://dspace.mediu.edu.my:8181/xmlui/handle/1721.1/7430| Title: | On-the-Fly Maintenance of Series-Parallel Relationships in Fork-Join Multithreaded Programs |
| Keywords: | Amortized analysis algorithms Cilk data race data structure dynamic set fork-join graph least common ancestor locking multi-threading mutual exclusion on the fly order maintenance parallel computing parse tree race detection series-parallel SP-bags SP-hybrid SP-order thread trace tree work stealing |
| Issue Date: | 9-Oct-2013 |
| Description: | A key capability of data-race detectors is to determine whether one thread executes logically in parallel with another or whether the threads must operate in series. This paper provides two algorithms, one serial and one parallel, to maintain series-parallel (SP) relationships "on the fly" for fork-join multithreaded programs. The serial SP-order algorithm runs in O(1) amortized time per operation. In contrast, the previously best algorithm requires a time per operation that is proportional to Tarjan’s functional inverse of Ackermann’s function. SP-order employs an order-maintenance data structure that allows us to implement a more efficient "English-Hebrew" labeling scheme than was used in earlier race detectors, which immediately yields an improved determinacy-race detector. In particular, any fork-join program running in T₁ time on a single processor can be checked on the fly for determinacy races in O(T₁) time. Corresponding improved bounds can also be obtained for more sophisticated data-race detectors, for example, those that use locks.
By combining SP-order with Feng and Leiserson’s serial SP-bags algorithm, we obtain a parallel SP-maintenance algorithm, called SP-hybrid. Suppose that a fork-join program has n threads, T₁ work, and a critical-path length of T[subscript â ]. When executed on P processors, we prove that SP-hybrid runs in O((T₁/P + PT[subscript â ]) lg n) expected time. To understand this bound, consider that the original program obtains linear speed-up over a 1-processor execution when P = O(T₁/T[subscript â ]). In contrast, SP-hybrid obtains linear speed-up when P = O(√T₁/T[subscript â ]), but the work is increased by a factor of O(lg n). Singapore-MIT Alliance (SMA) |
| URI: | http://koha.mediu.edu.my:8181/xmlui/handle/1721 |
| Other Identifiers: | http://hdl.handle.net/1721.1/7430 |
| Appears in Collections: | MIT Items |
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.