[mira_talk] Re: Mira and GPUs?

On Wednesday 04 March 2009 Jan van Haarst wrote:
> What do you think of this ?

I'm all for it :-)

Hi Jan, Greg,

sorry for the late reply. Regarding current plans of MIRA and GPU support: I 
have none. I briefly looked into the area when the first papers (Smith-Waterman 
on GPUs) came out 2 or 3 years ago, but I didn't see any chance for me to get 
that flying (programming these things is pretty close to metal) while still 
doing the development for MIRA to support the high throughput sequencing 
technologies that started to become a reality.

One obvious target could be, of course, Smith-Waterman for DNA alignments. The 
speed-ups there are , however, not the ones one would wish for: due to the 
sequential nature of dynamic programming, the matrix can be computed at best 
diagonally (i.e., one "processor" per row or column) and furthermore each 
row/column must start later than the predecessor. Interestingly, all papers 
I've seen so far are just about computing the matrix, no one has ever tried to 
parallelise the backtracking step (or I missed a paper). Not sure sure whether 
it would be possible. A banded Smith-Waterman that runs in near linear time 
(MIRA does that already) and memory (MIRA doesn't do that) would also be very 
welcome.

Another target I could think of is the "sieve" part at the very beginning of 
an assembly, where one must sieve out those read pairs that *could* match from 
all other read-pairs that probably do not match. The two classical ways to do 
this: suffix trees and hash based. In MIRA, this is the "SKIM" part (hash 
based) 
that got pretty efficient over time, but speed-ups are always welcome.

I'm not sure whether GPUs can be efficiently used to compute problems from 
graph 
theory (sub-paths and things like that). If yes: MIRA could have a need there, 
I need to think this through somewhat thoroughly.

In general, the major problem MIRA currently faces is RAM. I'm ashamed to say 
that MIRA is a real memory hog ... but this is unfortunately nothing a GPU can 
solve.

Regarding integration in MIRA: some things would be easy to do like, e.g., the 
SW alignment part. The code for it is amongst the oldest in MIRA and almost 
unchanged since years. This doesn't mean it's 100% efficient or has the best 
possible interfaces ... it just works. I would of course provide support and 
write some additional documentation to help to anyone who's interested to 
plug-into the existing structures.

Regards,
  Bastien


-- 
You have received this mail because you are subscribed to the mira_talk mailing 
list. For information on how to subscribe or unsubscribe, please visit 
http://www.chevreux.org/mira_mailinglists.html

Other related posts: