Evaluation of Biological Sequence Similarity Using FPGA Technology

Approximate string matching, approximate palindrome detection, approximate tandem repeat detection, systolic array, programmable hardware, FPGA technology, nested loops mapping, design space exploration, high-level synthesis

Pochopení struktury a funkce DNA sekvencí tvoří jednu z nejdůležitějších oblastí výzkumu moderní biologie.  Algoritmy pro jejich analýzu jsou však často komplikovány výskytem mutací, které vznikají důsledkem evolučního procesu a projevují se obvykle ve formě záměny, vložení nebo odstranění znaku.  Časová složitost algoritmů vlivem těchto poruch roste a komplikuje jejich praktické použití.  Určitou naději do této oblasti přináší techniky urychlování s využitím specializovaných obvodů.  V posledním desetiletí proto vzniklo mnoho prací zabývajících se urychlením klíčových operací při prohledávání biologických dat.  Výsledné obvody jsou schopné dosáhnout zrychlení v řádu stovek až tisíců oproti nejvýkonnějším konvenčním procesorům.  I přes vysoké zrychlení, které nabízejí, nejsou tyto akcelerátory příliš rozšířeny. Jedním z hlavních důvodů je častá variabilita úloh, která vede na změnu parametrů obvodu a přizpůsobení jeho rozměrů s ohledem na vlastnosti použité cílové platformy.  Tyto úpravy obvykle vyžadují zásah ze strany zkušeného návrháře, což komplikuje jejich použitelnost v reálných aplikacích.  Cílem práce je proto návrh nových metod pro automatizované mapování architektur na obvody s technologií FPGA. Problematika mapování je nejprve podrobně analyzována a formálně definována. Na základě formálního popisu je následně navržena nová metoda, která je schopna oproti existujícím přístupům nalézt nejen optimální rozměry výsledného obvodu, ale navíc neomezuje popis jednotlivých elementů architektury pouze na lineární funkce.