130

Journal of Parallel and Distributed Computing

Elsevier

2010

70

8

839-848

Dynamic programming , Lock-free hash tables , Constraint programming , Multicores , Parallelism

براي دانلودو مشاهده مقاله به قسمت لينكهاي مرتبط مراجعه نماييد

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.

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