prikaz prve stranice dokumenta C/C++ biblioteka za dinamičko programiranje korištenjem SIMD instrukcija
No public access
master's thesis
C/C++ biblioteka za dinamičko programiranje korištenjem SIMD instrukcija
Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing, 2014. urn:nbn:hr:168:952646
Šošić, Martin
University of Zagreb
Faculty of Electrical Engineering and Computing

Institutional repository: FER Repository

Cite this document

Šošić, M. (2014). C/C++ biblioteka za dinamičko programiranje korištenjem SIMD instrukcija (Master's thesis). Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing. Retrieved from https://urn.nsk.hr/urn:nbn:hr:168:952646

Šošić, Martin. "C/C++ biblioteka za dinamičko programiranje korištenjem SIMD instrukcija." Master's thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, 2014. https://urn.nsk.hr/urn:nbn:hr:168:952646

Šošić, Martin. "C/C++ biblioteka za dinamičko programiranje korištenjem SIMD instrukcija." Master's thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, 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', Master's thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, accessed 23 November 2024, https://urn.nsk.hr/urn:nbn:hr:168:952646

Šošić M. C/C++ biblioteka za dinamičko programiranje korištenjem SIMD instrukcija [Master's thesis]. Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing; 2014 [cited 2024 November 23] Available at: https://urn.nsk.hr/urn:nbn:hr:168:952646

M. Šošić, "C/C++ biblioteka za dinamičko programiranje korištenjem SIMD instrukcija", Master's thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, Zagreb, 2014. Available at: https://urn.nsk.hr/urn:nbn:hr:168:952646

Metadata
TitleC/C++ biblioteka za dinamičko programiranje korištenjem SIMD instrukcija
Title (english)An SIMD dynamic programming C/C++ Library
AuthorMartin Šošić
MentorMile Šikić (mentor)
Committee memberMile Šikić (predsjednik povjerenstva)
Committee memberMladen Vučić (član povjerenstva)
Committee memberDamir Seršić (član povjerenstva)
GranterUniversity of Zagreb
Faculty of Electrical Engineering and Computing
Zagreb
Defense date and country2014-09-24, Croatia
Scientific / art field,
discipline and subdiscipline		TECHNICAL SCIENCES
Computing
Abstract
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.
Abstract (english)
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.
Keywords
Keywords (english)
Languageenglish
URN:NBNurn:nbn:hr:168:952646
Study programmeTitle: Computing
Study programme type: university
Study level: graduate
Academic / professional title: magistar/magistra inženjer/inženjerka računarstva (magistar/magistra inženjer/inženjerka računarstva)
Type of resourceText
File originBorn digital
Access conditionsClosed access
Terms of useLicence In copyright icon
Public note
Created on2018-02-06 12:21:32