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).
Keywords: Data Partition, Pairwise Alignment, Parallel Processing, Shared Memory
Author: Auriza Rahmad Akbar, Heru Sukoco, Wisnu Ananta Kusuma
Journal Code: jptkomputergg150080

Artikel Terkait :