Sequence alignment, nVidia CUDA of ATi Stream?

[KoosDijk]

Beste mensen,

Ik heb dit topic hier geplaatst, dit leek me het best passend.

Voor een project ben ik bezig met zogenaamde 'sequence alignment'. Dit is een vorm van dynamisch programmeren dat ik in mijn geval gebruik voor DNA-alignment. Hierbij worden twee files met DNA-sequenties (dus A,T,C,G) met elkaar vergeleken. Opzich is dit geen probleem en kan dit heel erg snel. Zo is het percentage overeenkomst tussen twee databestanden ook simpel te berekenen.

Het wordt echter ingewikkelder als je ook addities en deleties wilt meenemen in de DNA-analyse. Een additie in een DNA-streng is het tussenvoegen van een base, een deletie is het verwijderen ervan. Zonder een speciaal algorithme zou na 1 additie of deletie het percentage overeenkomstige basen sterk dalen. Dit is natuurlijk niet de bedoeling.

Met DNA-alignment kun je door middel van het Needleman–Wunsch algoritme deze addities of deleties kan opsporen. Hiervoor bestaat ook speciale software zoals BLAST.

Deze taken zijn bij grote DNA-strengs zeer CPU en RAM intensief. Op mijn systeem (specs, zie verder) kon ik nog wel twee soorten bacteriën (4,7 miljoen baseparen elk) vergelijken, maar ingewikkeldere sequenties (twee chromosomen van bijv. de mens en de kip) duurt zeer lang. Zo lang dat ik de run niet heb afgemaakt.

Nu las ik over verschillende technieken om voor deze intensieve bewerkingen één of meerdere videokaarten te gebruiken. Hiervoor bestaat oa nVidia CUDA maar ook ATi Stream. Na een aantal benchmarks gezien te hebben bleek in sommige gevallen CUDA beter te presteren, en in sommige gevallen Stream.

Bij de specificaties van de kaarten viel me nog meer op. Zo zitten ze high-end kaarten van nVidia rond de 200 CUDA-cores per videokaart, terwijl ATi vaak honderden of zelfs duizenden cores op een plaatje krijgt. Zo heeft het topmodel, de ATI Radeon HD 5970, al 3200 streamprocessors. Recente benchmarks zijn vrij schaars, en al helemaal met dit soort wetenschappelijke taken.

Natuurlijk speelt het kostenplaatje ook een rol. De nVidia GTS250 vind ik best aardig geprijsd, maar de Radeon HD5770 (50 euro duurder) bevat wel 4 maal zoveel verwerkingseenheden.

Tenslotte is BLAST volgensmij alleen herschreven voor CUDA. Ik zou moeten kijken naar andere applicaties voor Stream support vermoed ik, tenzij BLAST (public domain) aan te passen is voor ATi Stream.

Kunnen jullie hier eens je licht over laten schijnen? Laat maar weten als het één of ander niet duidelijk is, dan zal ik het proberen verder uit te werken.

Specificaties systeem:

- AMD Phenom 9500
- 4 GB RAM
- 80 GB Intel SSD X-25
- (op dit moment) ATi Radeon HD 2600 Pro

[noguru]

Mooi project. De gedachte om cuda of stream hiervoor te gebruiken is niet nieuw. Maar wat ik er over vind is Smith-Waterman en niet het Needleman–Wunsch algoritme (en CUDA) .
De keuze voor Nvidia of Ati is de keuze tussen cuda of stream. Het aantal cores op de processor is niet zo relevant, Nvidia heeft er minder maar ze zijn complexer en hoger geklokt.
Wat voor Needleman-Wunsch het beste werkt, CUDA of Stream, zal je hardware keuze bepalen.

[KoosDijk]

Inderdaad, BLAST gebruikt een algoritme dat Smith-Waterman benaderd, maar vele malen sneller is. Ik weet niet welk algoritme effectiever is, het Needleman-Wunsch of het Smith-Waterman algoritme, maar er zijn geen benchmarks te vinden van BLAST op CUDA en Stream. Dat maakt het vergelijken dus nogal lastig...

De cores van de nVidia zijn ongetwijfeld krachtiger. Toch blijkt uit (weliswaar totaal irrelevante benchmarks voor dit doel) dat de ATi-kaarten beter presteren voor games. Zou dit dan ook gelden voor CUDA en Stream?

Edit:

Ik vond een onderzoek hier. Hieruit blijkt dat het werken met CUDA in ieder geval wel een performance boost geeft (zie figuur 4). En dit is op een 8800GTX, met 16 CUDA-processors, terwijl de nVidia GT 250 al 128 CUDA-cores heeft. Dit moet dus zeker merkbaar zijn.

[ Voor 24% gewijzigd door KoosDijk op 09-05-2010 13:07 ]

[Juup]

KoosDijk schreef op zondag 09 mei 2010 @ 10:22:
Tenslotte is BLAST volgensmij alleen herschreven voor CUDA.

Probeer het eens uit op een pc'tje met een recente CUDA kaart (of koop een minder recente, gewoon om te proberen).

[DukeBox]

Voor benchmarks zou je misschien naar DC projecten moeten kijken (zie /5), met name dingen als folding@home, find a drug etc.. hebben mogelijk soortgelijke berekeningen maar wel recentere benchmarks.
Ikzelf werk alleen maar met grafische render omgevingen, daar is nvidia wel toegankelijker en iets verder met hun tesla/fermi architectuur waar wij meestal op basis van de DirectCompute api gebruik van maken.
Verder heb je nog c/c++, fortran en opencl.

[Verwijderd]

Hey een mede Bio-informaticus .

Ik zou eerder kijken richting CUDA. Simpel weg omdat het een stuk volwassener is dan stream (Op de cuda zone kan je ook veel hulp vinden). Ik zou je niet laten gek maken door naar de aantal cores te kijken. Je moet bedenken dat die cores van de HD5970 over 2 GPU kernen zitten en 5 weg zijn geordend. Je kan het beter zo zien. Een kern daarvan heeft 1600/5=320 processortjes. Deze kunnen per tik 5 bewerkingen doen. Helaas lukt dit niet altijd en zit je dus tussen 320 en het maximaal aantal bewerkingen van 1600 in. Voor Nvidia geld dit niet. Het aantal kernen wat je daar ziet is ook gelijk aan het aantal bewerkingen. Het voordeel voor nvidia is dat deze kernen op een hogere snelheid lopen.(=hevige versimpeling, als je gaat CUDA programmeren zit je namelijk in grids te werken. Waarbij het belangrijkste is dat je deel berekeningen in de local cache past)

Schaamteloze reclame: Lees ook mijn review, daar heb ik het in jip en janneke taal uit gelegd. productreview: Jetway X4850-EN-512M review door Verwijderd

[ Voor 9% gewijzigd door Verwijderd op 10-05-2010 11:01 ]