MASA-StarPU: Parallel Sequence Comparison with Multiple Scheduling Policies and Pruning - INRIA - Institut National de Recherche en Informatique et en Automatique Accéder directement au contenu
Communication Dans Un Congrès Année : 2020

MASA-StarPU: Parallel Sequence Comparison with Multiple Scheduling Policies and Pruning

Résumé

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.
Fichier principal
Vignette du fichier
lopes_rafael_paper25_sbacpad2020.pdf (2.52 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02914793 , version 1 (12-08-2020)

Identifiants

Citer

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⟩
128 Consultations
217 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More