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

• Main Authors: Chua, Kyle Matthew Chan, Villamayor, Janz Aeinstein Fauni, Bautista, Lorenzo Campos, Uy, Roger Luis
• Format: text
• Published: Animo Repository 2019
• Subjects: SIMD (Computer architecture); Nucleotide sequence; High performance processors; Computer Sciences
• Online Access: https://animorepository.dlsu.edu.ph/faculty_research/2302
• Institution: De La Salle University

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. © 2019, Universitas Ahmad Dahlan. All rights reserved.