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 metadatas

Cited literature [18 references]  Display  Hide  Download

https://hal.inria.fr/hal-02914793
Contributor : Samuel Thibault <>
Submitted on : Wednesday, August 12, 2020 - 4:12:08 PM
Last modification on : Friday, August 14, 2020 - 9:12:16 AM

File

lopes_rafael_paper25_sbacpad20...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02914793, version 1

Collections

Citation

Rafael Lopes, Samuel Thibault, Alba 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. ⟨hal-02914793⟩

Share

Metrics

Record views

87

Files downloads

238