RecordNumber
130
Author
Alex Stivala, Peter J. Stuckey, Maria Garcia de la Banda, Manuel Hermenegildo, Anthony Wirth
Title of Article
Lock-free Parallel Dynamic Programming
Title Of Journal
Journal of Parallel and Distributed Computing
PublishInfo
Elsevier
Publication Year
2010
Volum
70
Issue Number
8
Page
839-848
Keywords
Dynamic programming , Lock-free hash tables , Constraint programming , Multicores , Parallelism
Notes
براي دانلودو مشاهده مقاله به قسمت لينكهاي مرتبط مراجعه نماييد
Abstract
We show a method for parallelizing top down dynamic programs in a straightforward way by a careful choice of a lock-free shared hash table implementation and randomization of the order in which the dynamic program computes its subproblems. This generic approach is applied to dynamic programs for knapsack, shortest paths, and RNA structure alignment, as well as to a state-of-the-art solution for minimizing the maximum number of open stacks. Experimental results are provided on three different modern multicore architectures which show that this parallelization is effective and reasonably scalable. In particular, we obtain over 10 times speedup for 32 threads on the open stacks problem.
URL
http://www.sciencedirect.com/science/article/pii/S0743731510000110,/DL/Data Entry/DataEntryForm/EnterDocInfo.aspx,/DL/Data Entry/NewEdit/Documents/Math_English_Electronic_Articles_EditDoc_925.aspx