Paper Info
Title
MASA-StarPU: Parallel Sequence Comparison with Multiple Scheduling Policies and Pruning
Abstract
Sequence comparison tools based on the Smith-Waterman (SW) algorithm provide the optimal result but have high execution times when the sequences compared are long, since a huge dynamic programming (DP) matrix is computed. Block pruning is an optimization that does not compute some parts of the DP matrix and can reduce considerably the execution time when the sequences compared are similar. However, block pruning's resulting task graph is dynamic and irregular. Since different pruning scenarios lead to different pruning shapes, we advocate that no single scheduling policy will behave the best for all scenarios. This paper proposes MASA-StarPU, a sequence aligner that integrates the domain specific framework MASA to the generic programming environment StarPU, creating a tool which has the benefits of StarPU (i.e., multiple task scheduling policies) and MASA (i.e., fast sequence alignment). MASA-StarPU was executed in two different multicore platforms and the results show that a bad choice of the scheduling policy may have a great impact on the performance. For instance, using 24 cores, the 5M × 5M comparison took 1484s with the dmdas policy whereas the same comparison took 3601s with lws. We also show that no scheduling policy behaves the best for all scenarios.
Year
DOI
Venue
2020
10.1109/SBAC-PAD49847.2020.00039
2020 IEEE 32nd International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD)
Keywords
DocType
ISSN
parallel sequence comparison,parallel programming environments,dynamic programming
Conference
1550-6533
ISBN
Citations 
PageRank 
978-1-7281-9925-2
0
0.34
References 
Authors
12
3
Name
Order
Citations
PageRank
Rafael A. Lopes100.34
Samuel Thibault200.34
Alba Cristina Magalhaes Alves De Melo325333.90