Hi all,
I realise this may be a slightly naive question and my implementation is
certainly naive, however I'd like to see if anyone else has attempted
anything similar. Of course, by 'dynamic-programming' I 'm not referring
to dyncamic scope but to the statistical technique which divides
problems to subproblems and assembles optimal solutions from optimal
subsolutions.
I recently implemented the smith-waterman algorithm (for local sequence
allignment) which uses this and since functional D.P. is basically done
by reducing from within a reduce I thought I'd try using r/reduce (from
reducers) instead of plain reduce.
I identified that the single most expensive operation in my algorithm is
actually building the score-matrix. The fn that does this looks like this:
(defn- fill-scores "Fill the score-matrix."
[locations s1 s2 match mis]
(reduce #(scoring-fn s1 s2 match mis %1 %2) {} locations))
which I (naively) turned into this:
(defn- fill-scores-par "Fill the score-matrix in parallel."
[locations s1 s2 match mis]
(r/fold (r/monoid (partial merge-with into) hash-map) assoc
(r/reduce #(scoring-fn s1 s2 match mis %1 %2) {} locations)))
Now, you probably have guessed what happens....Even though they return
the same thing, the parallel version takes twice the time than the
original on a big sequence (23sec vs 11sec)! Observing the cpu, I can
see certain spikes during the first 5-6 seconds but then all 4 cores
suddenly become busy until the end! I understand that DP is an
inherently serial operation (in a non-FP language you do it with nested
for-loops), but a bit of googling revealed that other people have tried
parallelising it as well. The most relevant paper is [1] where they use
a concurrent hash-map and CAS operations (just like atoms in Clojure).
Has anyone else done any research on the matter? Is this something that
can be done relatively easily with the beautiful reducers library? For
example I've successfully parallelised minimax (still struggling with
alpha-beta though) very easily with reducers whereas all the rest
parallel implementations are ridiculously complex. This is why I thought
perhaps DP can be easily parallelised with reducers.
Thanks a lot in advance...
Jim
[1] Lock-free Dynamic-Programming (Stivala, Stukey, de la Banda,
Hermenegido & Wirth )
--
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups "Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
