Skip to Main content Skip to Navigation
Conference papers

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 x 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.
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download
Contributor : Samuel Thibault Connect in order to contact the contributor
Submitted on : Wednesday, August 12, 2020 - 4:12:08 PM
Last modification on : Friday, September 9, 2022 - 3:30:04 AM
Long-term archiving on: : Monday, November 30, 2020 - 6:50:39 PM


Files produced by the author(s)




Rafael Alvares da Silva Lopes, Samuel Thibault, Alba Cristina Magalhães Alves De Melo. MASA-StarPU: Parallel Sequence Comparison with Multiple Scheduling Policies and Pruning. SBAC-PAD 2020 - IEEE 32nd International Symposium on Computer Architecture and High Performance Computing, Sep 2020, Porto, Portugal. ⟨10.1109/SBAC-PAD49847.2020.00039⟩. ⟨hal-02914793⟩



Record views


Files downloads