Lock-free parallel dynamic programming
Alex Stivala, Peter J Stuckey, Maria Garcia de la Banda, Manuel Hermenegildo, Anthony Wirth
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING | ACADEMIC PRESS INC ELSEVIER SCIENCE | Published : 2010
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. © 2010 ..View full abstract
Awarded by Spanish Ministry of Science
This research made use of the Victorian Partnership for Advanced Computing HPC facility and support services. The first author is funded by an Australian Postgraduate Award. NICTA is funded by the Australian Government as represented by the Department of Broadband, Communications and the Digital Economy and the Australian Research Council through the ICT Centre of Excellence Program. The fourth author is funded in part by Spanish Ministry of Science project TIN-2008-05624 DOVES and CM project S-0505/TIC/0407 PROMESAS. IMDEA is funded by the Madrid Regional Government (CM).