Improving matrix-based dynamic programming on massively parallel accelerators

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F16%3A10326736" target="_blank" >RIV/00216208:11320/16:10326736 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1016/j.is.2016.06.001" target="_blank" >http://dx.doi.org/10.1016/j.is.2016.06.001</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.is.2016.06.001" target="_blank" >10.1016/j.is.2016.06.001</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Improving matrix-based dynamic programming on massively parallel accelerators

Popis výsledku v původním jazyce

Dynamic programming techniques are well-established and employed by various practical algorithms, including the edit-distance algorithm or the dynamic time warping algorithm. These algorithms usually operate in an iteration-based manner where new values are computed from values of the previous iteration. The data dependencies enforce synchronization which limits possibilities for internal parallel processing. In this paper, we investigate parallel approaches to processing matrix-based dynamic programming algorithms on modern multicore CPUs, Intel Xeon Phi accelerators, and general purpose GPUs. We address both the problem of computing a single distance on large inputs and the problem of computing a number of distances of smaller inputs simultaneously (e.g., when a similarity query is being resolved). Our proposed solutions yielded significant improvements in performance and achieved speedup of two orders of magnitude when compared to the serial baseline.

Název v anglickém jazyce

Improving matrix-based dynamic programming on massively parallel accelerators

Popis výsledku anglicky

Dynamic programming techniques are well-established and employed by various practical algorithms, including the edit-distance algorithm or the dynamic time warping algorithm. These algorithms usually operate in an iteration-based manner where new values are computed from values of the previous iteration. The data dependencies enforce synchronization which limits possibilities for internal parallel processing. In this paper, we investigate parallel approaches to processing matrix-based dynamic programming algorithms on modern multicore CPUs, Intel Xeon Phi accelerators, and general purpose GPUs. We address both the problem of computing a single distance on large inputs and the problem of computing a number of distances of smaller inputs simultaneously (e.g., when a similarity query is being resolved). Our proposed solutions yielded significant improvements in performance and achieved speedup of two orders of magnitude when compared to the serial baseline.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GP14-14292P" target="_blank" >GP14-14292P: Nasazení moderních paralelních architektur ve specifických oblastech databázových systémů</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2016

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Information Systems

ISSN

0306-4379

e-ISSN

—

Svazek periodika

64

Číslo periodika v rámci svazku

March 2017

Stát vydavatele periodika

GB - Spojené království Velké Británie a Severního Irska

Počet stran výsledku

19

Strana od-do

175-193

Kód UT WoS článku

000391900000014

EID výsledku v databázi Scopus

2-s2.0-85003548394