prikaz prve stranice dokumenta C/C++ biblioteka za dinamičko programiranje korištenjem SIMD instrukcija
Rad nije dostupan
diplomski rad
C/C++ biblioteka za dinamičko programiranje korištenjem SIMD instrukcija
Zagreb: Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva, 2014. urn:nbn:hr:168:952646
Šošić, Martin
Sveučilište u Zagrebu
Fakultet elektrotehnike i računarstva

Institucijski repozitorij: Repozitorij FER-a

Citirajte ovaj rad

Šošić, M. (2014). C/C++ biblioteka za dinamičko programiranje korištenjem SIMD instrukcija (Diplomski rad). Zagreb: Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva. Preuzeto s https://urn.nsk.hr/urn:nbn:hr:168:952646

Šošić, Martin. "C/C++ biblioteka za dinamičko programiranje korištenjem SIMD instrukcija." Diplomski rad, Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva, 2014. https://urn.nsk.hr/urn:nbn:hr:168:952646

Šošić, Martin. "C/C++ biblioteka za dinamičko programiranje korištenjem SIMD instrukcija." Diplomski rad, Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva, 2014. https://urn.nsk.hr/urn:nbn:hr:168:952646

Šošić, M. (2014). 'C/C++ biblioteka za dinamičko programiranje korištenjem SIMD instrukcija', Diplomski rad, Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva, citirano: 07.09.2024., https://urn.nsk.hr/urn:nbn:hr:168:952646

Šošić M. C/C++ biblioteka za dinamičko programiranje korištenjem SIMD instrukcija [Diplomski rad]. Zagreb: Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva; 2014 [pristupljeno 07.09.2024.] Dostupno na: https://urn.nsk.hr/urn:nbn:hr:168:952646

M. Šošić, "C/C++ biblioteka za dinamičko programiranje korištenjem SIMD instrukcija", Diplomski rad, Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva, Zagreb, 2014. Dostupno na: https://urn.nsk.hr/urn:nbn:hr:168:952646

Za citiranje koristite ovu mrežnu adresu: https://urn.nsk.hr/urn:nbn:hr:168:952646
Podaci o radu
NaslovC/C++ biblioteka za dinamičko programiranje korištenjem SIMD instrukcija
Naslov (engleski)An SIMD dynamic programming C/C++ Library
AutorMartin Šošić
MentorMile Šikić (mentor)
Član povjerenstvaMile Šikić (predsjednik povjerenstva)
Član povjerenstvaMladen Vučić (član povjerenstva)
Član povjerenstvaDamir Seršić (član povjerenstva)
Ustanova koja je dodijelila
akademski / stručni stupanj		Sveučilište u Zagrebu
Fakultet elektrotehnike i računarstva
Zagreb
Datum i država obrane2014-09-24, Hrvatska
Znanstveno / umjetničko
područje, polje i grana		TEHNIČKE ZNANOSTI
Računarstvo
Sažetak
Deterministički algoritmi za poravnanje sekvenci poput Smith-Waterman algoritma i Needleman-Wunsch algoritma su spori ali daju optimalno rješenje. Koriste se u mnogim bioinformatičkim alatima kao centralna komponenta i često veliki dio ukupnog vremena računanja odlazi upravo na njih. Kako bi se takvi algoritmi ubrzali nastale su brojne brze implementacije, od kojih veliki dio provodi paralelizaciju korištenjem ista-instrukcija-različiti-podaci (Single Instruction Multiple Data) (SIMD) podrške na procesoru ili grafičkoj kartici. Većina takvih brzih implementacija su samostalni alat ili dio nekog većeg alata te nisu napravljene za ponovno korištenje, što ograničava njihovu uporabu. Kako bismo neke od brzih implementacija učinili ponovno iskoristivima implementirali smo dvije C/C++ biblioteke za poravnanje sekvenci, obje temeljene na brzim SIMD implementacijama. SWIMD je biblioteka za pretragu baze i temelji se na Faster Smith-Waterman database searches (SWIPE) od Rognes-a. U našoj implementaciji dodali smo jednu globalnu i dvije polu-globalne metode poravnanja. Također smo dodali podršku za AVX2 skup instrukcija. Usporedili smo SWIMD sa trenutno najboljim implementacijama: SSW, SSEARCH i SWIPE. Pokazali smo da je SWIMD uz korištenje AVX2 skupa instrukcija najbrža implementacija. SWIMD je dostupan na http://github.com/Martinsos/swimd. EDLIB je biblioteka za poravnanje dvaju sekvenci koristeći udaljenost uređivanja i temelji se na Fast Bit-Vector Algorithm od Myers-a. u EDLIB-u smo dodali jednu globalnu i jednu polu-globalnu metodu poravnanja. Za globalnu metodu smo pokazali kako izračunati pojas ćelija u matrici koje su dio rješenja. Također smo dodali pronalazak puta poravnanja. EDLIB je dostupan na https://github.com/Martinsos/edlib. Stvorivši SWIMD i EDLIB stvorili smo ponovno iskoristive komponente važne za brojne bioinformatičke alate ali također iskoristive i u druge svrhe. Vjerujemo da će SWIMD i EDLIB omogućiti širu upotrebu brzih SIMD algoritama i da će mnogi alati imati koristi od njih.
Sažetak (engleski)
Deterministic sequence alignment algorithms like Smith-Waterman and Needleman-Wunsch are slow but give optimal result. They are used in many bioinformatic tools as core components and very often they consume significant amount of CPU time. In order to make them faster, different fast implementations have been implemented, many of them performing parallelization using Single Instruction Multiple Data (SIMD) support on CPU or GPU. However, most of these fast implementations are either stand-alone tool or part of larger tool and were not made to be reusable, which is limiting their usage. In order to make some of this implementations reusable, we implemented two C/C++ libraries for sequence alignment, both based on fast SIMD implementations. SWIMD is library for database search and is based on Rognes's Faster Smith-Waterman database searches (SWIPE). In our implementation we added one global and two semi-global alignment methods. We also added support for AVX2 instruction set. We compared SWIMD with currently best implementations like SSW, SSEARCH and SWIPE and showed that SWIMD implementation using AVX2 is the fastest. SWIMD is available from http://github.com/Martinsos/swimd. EDLIB is library for pairwise sequence alignment using edit distance and is based on Myers's Fast Bit-Vector Algorithm. We added one global and one semi-global alignment method. For global method we have shown how to calculate the band. We also added finding of alignment path. EDLIB is available from https://github.com/Martinsos/edlib. By implementing this two libraries we provided reusable components important for many bioinformatic tools, but also usable for other purposes. We believe this will enable wider usage of fast SIMD algorithms and that many tools could benefit from using them.
Ključne riječi
Ključne riječi (engleski)
Jezikengleski
URN:NBNurn:nbn:hr:168:952646
Studijski programNaziv: Računarstvo
Vrsta studija: sveučilišni
Stupanj studija: diplomski
Akademski / stručni naziv: magistar/magistra inženjer/inženjerka računarstva (mag.ing.comp.)
Vrsta resursaTekst
Način izrade datotekeIzvorno digitalna
Prava pristupaZatvoreni pristup
Uvjeti korištenjaIkona licence Zaštićeno autorskim pravom.
Javna napomena
Datum i vrijeme pohrane2018-02-06 12:21:32