Ускорение выравнивания строк на ПЛИС при помощи HaSCoL Олег Медведев (Ланит-терком, НИИ ИТ СПбГУ) SECR,

Множественное выравнивание MRKMSEEEFYLFKNISSVGPWDGPQYHIAPVWAFYLQAAFMGTV MNGTEGNNFYVPLSNRTGLVRSPFEYPQYYLAEPWQFKLLAVYM MKQVPEFHEDFYIPIPLDINNLSAYSPFLVPQDHLGNQGIFMAM * FLIGFPLNAMVLVATLRYKKLRQPLNYILVNV FFLICLGLPINGLTLICTAQHKKLRQPLNFILVNL SVFMFFIFIGGASINILTILCTIQFKKLRSHLNYILVNL

Множественное выравнивание ---MRKMS--EEEFYL-----FKNISSV--GPWDGPQYHIAPVWA ---MNGTE--GNNFYVP----LSNRTGLVRSPFEYPQYYLAEPWQ ---MKQVPEFHEDFYIPIPLDINNLS--AYSPFLVPQDHLGNQGI * * * * ** FYLQAAFMGTVFLIGFPLNAMVLVATLRYKKLRQPLNYILVNV FKLLAVYMFFLICLGLPINGLTLICTAQHKKLRQPLNFILVNL FMAMSVFMFFIFIGGASINILTILCTIQFKKLRSHLNYILVNL * * * * **** ** ****

Множественное выравнивание Задача формализуется несколькими способами В любом случае точно решается экспоненциальными алгоритмами Поэтому на самом деле решается приближенно Например, при помощи open source средства MAFFT

Производительность MAFFT Не очень хорошая (для самого «точного» варианта) При этом 90% времени тратится в процедуре выравнивания двух строк Её было решено ускорить аппаратно

Общий вид системы PC FPGA (ПЛИС) 100MBit/s Ethernet Эмулирует любую цифровую синхронную интегральную схему

Боремся за 10х и более ускорение PC FPGA (ПЛИС) Intel Core Duo 1.8GHz, оптимизированый код на Си Virtex5 xc5vlx50t-1 код на HaSCoL, написанный за 10 дней. Выравнивание двух строк Работает в 10 раз быстрее

В чем сложность подхода? PC FPGA (ПЛИС) Программируется на одном из множества языков Программируется на низкоуровневых VHDL/Verilog, либо средствами HLS

Средства high-level synthesis Синтез из Си-подобных языков, либо подмножеств Си (CatapultC, HandelC, SpecC, MitrionC, …) Попытки предложить свой язык (Bluespec, наш HaSCoL)

HaSCoL – набор вложенных расширяемых языков Не тактово-аккуратные расширения Конвейер, поток управления Поддержка обмена сообщениями Базовый уровень языка (типа VHDL/Verilog) Тактово- аккуратные расширения языка (уже реализованы

Целевая функция для выравнивания двух строк

Примерное устройство решения

Матрица возвратов

Примерное устройство решения: конвейер вычислителей

Один вычислитель -- реализация data previousValue : tWeight; data previousLeftValue : tWeight; in nextLeftValue(nextLeftValue : tWeight) { nextOurValue = someExpression(value, previousValue, previousLeftValue) | previousOurValue := nextOurValue | previousLeftValue := nextLeftValue ; send propagateToTheRight(nextOurValue) }

Сложность 1: короткий конвейер

Соответствующий управляющий код while colPos < s2len do inform initialCol(colPos, 0) | colPos = colPos + AlignerSize | reccoldiv := reccoldiv + 1 ; wait(AlignerSize); let lastCol = colPos >= s2len in { rowPos = (0 : int(16)) | lastCol = lastCol | rowWritePos := 0 | skipHead := if lastCol then s1lenModAlignerSizeR else 0 fi }; while rowPos

Сложность 2 Необходимость делать обратный проход по матрице, перевычисляя вертикальные полосы в обратном порядке, потому что матрицу возвратов сохранить невозможно Эту сложность мы преодолеваем примерно таким же образом

Еще раз результаты Примерно за 10 дней на HaSCoL реализовано устройство вычисления попарного выравнивания Оно протестировано на нескольких десятках тысяч тестов в симуляции Синтезировано для FPGA Virtex-5 xc5vlx50t-1, по результатам синтеза получена оценка: устройство будет работать примерно в 10 раз быстрее программной реализации попарного выравнивания

Контакты, ссылки Скачать тулы, статьи про наш язык GNU код на HaSCoL (разное – магистры ГУАП, студенты, аспирант, я сам)