Comparison of Data Partitioning Schema of Parallel Pairwise Alignment on Shared Memory System
Abstract: The pairwise
alignment (PA) algorithm is widely used in bioinformatics to analyze biological
sequence. With the advance of sequencer technology, a massive amount of DNA
fragments aresequenced much quicker and cheaper. Thus, the alignment algorithm
needs to be parallelized to be ableto align them in a shorter time. Many
previous researches have parallelized PA algorithm using variousdata partitioning
schema, but it is unknown which one is the best. The data partitioning schema
isimportant for parallel PA performance, because this algorithm uses dynamic
programming technique that needs intense inter-thread communication. In this
paper, we compared four partitioning schemas to find the best performing one on
shared memory system. Those schemas are: blocked columnwise, rowwise, antidiagonal,
and blocked columnwise with manual scheduling and loop unrolling. The testing
is done on quad-core processor using DNA sequence of 1000 to 16000 bp as the
input. The blocked columnwise with manual scheduling and loop unrolling schema
gave the best performance of 89% efficiency. Thesynchronization time is
minimized to get the best performance possible.This result provided high performance
parallel PA with fine-grain parallelism that can be used further to develop
parallels multiple sequence alignment (MSA).
Author: Auriza Rahmad Akbar,
Heru Sukoco, Wisnu Ananta Kusuma
Journal Code: jptkomputergg150080