Implementation of hyyrö’s bit-vector algorithm using advanced vector extensions 2

Kyle Matthew Chan Chua (Computer Technology Department, College of Computer Studies, De La Salle University)
Janz Aeinstein Fauni Villamayor (Computer Technology Department, College of Computer Studies, De La Salle University)
Lorenzo Campos Bautista (Computer Technology Department, College of Computer Studies, De La Salle University)
Roger Luis Uy (Computer Technology Department, College of Computer Studies, De La Salle University)

International Journal of Advances in Intelligent Informatics
Vol 5, No 3 (2019): November 2019

The Advanced Vector Extensions 2 (AVX2) instruction set architecture was introduced by Intel’s Haswell microarchitecture that features improved processing power, wider vector registers, and a rich instruction set. This study presents an implementation of the Hyyrö’s bit-vector algorithm for pairwise Deoxyribonucleic Acid (DNA) sequence alignment that takes advantage of Single-Instruction-Multiple-Data (SIMD) computing capabilities of AVX2 on modern processors. It investigated the effects of the length of the query and reference sequences to the I/O load time, computation time, and memory consumption. The result reveals that the experiment has achieved an I/O load time of ϴ(n), computation time of ϴ(n*⌈m/64⌉), and memory consumption of ϴ(n). The implementation computed more extended time complexity than the expected ϴ(n) due to instructional and architectural limitations. Nonetheless, it was par with other experiments, in terms of computation time complexity and memory consumption.