Ускорение исследований геномики с OpenCL и FPGA

С появлением оборудования секвенирования второго поколения, расходы на сравнение генов значительно сократились, что привело к доступности получения данных о генной последовательности.

Корреляция вариаций геномов применима к широкому спектру медицинских исследований.

Каждый человек обладает более чем тремя миллиардами пар генов, и требуется значительная вычислительная мощность, емкость хранилища и пропускная способность сети для вычисления генной последовательноси.

Genome Analysis Toolkit (GATK) - это программный пакет, разработанный в Broad Institute для анализа большого объема данных и с высокой вычислительной мощностью. Здесь описывается примеры вычислений на основе алгоритма GapK Haplotype Caller с использованием Altera®, теперь входящего в состав Intel, FPGAs на основе SDK от Altera для OpenCL.

Суть проблемы

Обнаружение генного варианта совпвдений представляет собой значительную проблему: схема взаимного расположения структурных генов, регуляторных элементов и генетических маркеров, а также относительных расстояний между ними на хромосоме (группе сцепления) требет больших вычислительных мощностей.

Однако несколько основных проблем в вычислении данных последовательностей и расположений делают это процесс весьма сложным. Среди них можно выделить:

  • Многочисленные ошибки и неточности, возникающие во время подготовки к самим вычислениям
  • Ошибки во время секвенирования библиотек
  • Ошибки программного обеспечения и ошибки сихронизации или построения генетических карт (генетическим картированием)

Из-за всех этих ошибок сами по себе вычисления становятся весьма трудоемкими. Существующие варианты и методы применения различных алгоритмов с использованием стандартных микропроцессоров требуют до нескольких дней вычислительного времени.

Гетерогенные вычисления и язык программирования OpenCL

Стандартный процессор с присоединенным ускорительным устройством, таким как графический процессорный блок (GPU) или FPGA, может ускорить широкий спектр функций, включая поиск данных, обработку изображений, финансового или любого другого моделирования. С помощью этих гетерогенных систем программирования появились стандарты, позволяющие упростить адаптацию алгоритмов от стандартных систем до ускоренных гетерогенных систем.

OpenCL - это среда для написания программ, которые выполняются в гетерогенных платформах, состоящих из процессоров, графических процессоров, цифровых сигнальных процессоров (DSP), FPGA и других многоядерных процессоров.

OpenCL (Open Computing Language, открытый язык вычислений) — это открытый стандарт для параллельного программирования, предлагающий эффективный и переносимый способ использования возможностей разнородных вычислительных многоядерных платформ (CPU, GPU и др.). Он включает в себя программный интерфейс (API) для координирования параллельных вычислений в среде разнородных процессоров и кроссплатформенный язык, используемый в определённом вычислительном окружении.

На конкретной системной платформе стандарт реализуется в виде исполняемых модулей (библиотек), достаточных для запуска пользовательских OpenCL-приложений. Разработка подобных приложений предполагает наличие также C/C++-компилятора системной платформы и набора необходимых заголовочных файлов.

Несколько поставщиков, включая Altera, предоставляют компиляторы для OpenCL.

Технология FPGA

Программи́руемая по́льзователем ве́нтильная ма́трица (ППВМ, англ. field-programmable gate array, FPGA) — полупроводниковое устройство, которое может быть сконфигурировано производителем или разработчиком после изготовления; отсюда название: «программируемая пользователем». ППВМ программируются путём изменения логики работы принципиальной схемы, например, с помощью исходного кода на языке проектирования, на котором можно описать эту логику работы микросхемы. ППВМ является одной из архитектурных разновидностей программируемых логических интегральных схем (ПЛИС).

FPGA - это реконфигурируемые интегральные схемы, состоящие из программируемой маршрутизации сети, связывающие блоки логических блоков, блоки встроенной памяти и DSP блоки. Напротив, процессоры и графические процессоры содержат фиксированные пути и топологии данных.

Ресурсы ПЛИС могут быть сконфигурированы и связаны друг с другом. Архитектура FPGA может использоваться для решения определенных типов вычислительных задач очень эффективно.

Программирование с помощью ПЛИС

Первоначально разработчики аппаратного обеспечения проверили цифровые схемы основанные на ПЛИС на уровне передачи регистров (RTL) с использованием языков описания аппаратного обеспечения (HDL), таких как Verilog HDL и VHDL. Хотя эти традиционные методы и эффективны для обеспечения использования некоторых устройств, они непрактичны для реализации комплекса алгоритмов, таких как секвенирование генов.

В начале 2012 года Altera представила Altera SDK для OpenCL - комплект для разработки программного обеспечения, который позволяет использовать программирование OpenCL языка для программирования ПЛИС Altera вычислительных ускорительных устройств. В конце 2014 года Xilinx Corporation, другой ведущий поставщик FPGA, объявила, что они также разработка компилятора для OpenCL.

SDK Altera для OpenCL был использован для широкого спектра алгоритмов в различных вычислительных сфарах.

SDK от Altera для OpenCL

Altera SDK для OpenCL использует ту же модель программирования, что и другие производители и разработчики. Рисунок 1 иллюстрирует поток программирования. Для системы требуется FPGA основанная на SDK OpenCL, доступная от различных поставщикови не требуется дополнительное программирование уровня RTL. Достаточно программирование ПЛИС с использованием OpenCL.

Программа OpenCL состоит из хост-программы (предназначенной для запуска на стандартном процессоре) и кода ядра (предназначенного для запуска на ускорителе, в данном случае FPGA). С помощью стандартного IDE и компилятора GCC, программист пишет и компилирует свой хост код.

Используя OpenCL API, идет обмен данными с ядром OpenCL. В отдельном .cl файле, программист пишет OpenCL C, следуя соответствующей оптимизации рекомендованной для ПЛИС.

Используя автономный компилятор Altera, файл ядра OpenCL компилирует и запускает программное обеспечение Quartus® II или Quartus Prime в фоновом режиме для создания файла «.aocx».

Используемые устройства FPGA

Для целей этого эксперимента код Caller Haplotype разбит на разделы для запуска как на хосте, так и на FPGA для оптимизации производительности. Компонент OpenCL, первоначально предназначенный для создания кода для Altera Stratix® V FGPA, перенаправлен на более продвинутой FPGA Aria® 10 от Altera.

FPGA Stratix V является частью элитного семейства устройств и поставляется с серийного производства с 2012 года. Линейка продуктов построена с технологией кремниевого процессора 28 нм от корпорации TSMC.

Altera также поставляет устройства Arria 10, используя более продвинутый 20-нм процессор с большим количеством логических элементов, блоков DSP и памяти.

Дополнительно, Arria 10 ПЛИС работают на более высоких частотах. У FPGA Arria 10 есть продвинутые, закаленные, плавающие точки и элементы, которые делают функции с плавающей запятой более эффективными, чем с использованием стандартной логики.

Эти функции позволяют нам использовать больше вычислительных блоков, что приводит к повышению общей производительности и значительно лучшей производительности на ватт для алгоритма Caller Haplotype Caller.

Анализ генома

Вызов

Обнаружение генного варианта совпадений представляет собой значительную проблему: схема взаимного расположения структурных генов, регуляторных элементов и генетических маркеров, а также относительных расстояний между ними на хромосоме (группе сцепления) требет больших вычислительных мощностей.

Решение этой и многих других подобных проблем стало приоритетной задачей для многих в медицинском и высокотехнологичном сообществе.

Использование надежного алгоритма для решения этих задач стало современным вызовом

Набор инструментов анализа генома

GATK - это программный пакет, разработанный в Broad Institute для анализа highthroughput последовательности данных. Инструментарий предлагает широкий спектр методов, с приоритетом на обнаружении и генотипировании, а также на качестве данных.

  • Функция GATK Haplotype Caller - это алгоритм обнаружения возможных вариантов.
  • PairHMM является основным алгоритмом для сравнения последовательностей. Он вызывает SNP и indels одновременно путем локальной реорганизации гаплотипов в активной области.
  • Caller Haplotype определяет ActiveRegions, определяет гаплотипы путем повторной сборки ActiveRegion, определяет вероятность гаплотипов, учитывая данные и назначает образцы генотипов. (5)

Используя данные существенных вариаций, выявляются области, подлежащие дальнейшему анализу и известены как ActiveRegions. Затем программа создает граф, похожий на Бруджин, для того, чтобы в ActiveRegions собрать и определить возможные гаплотипы с использованием алгоритма Смита-Уотермана.

Используя алгоритм PairHMM, ActiveRegions попарно согласуются с каждым гаплотипом для создания матрицы вероятности гаплотипов на основе прочитанных данных. Затем эта матрица создает вероятности аллелей для каждого потенциального варианта. (5)

Обзор алгоритма PairHMM

Сравнение двух последовательностей генов не так просто, как сравнение двух регулярных строк потому что каждая последовательность может иметь вставки, удаления и мутации.

Модель Маркова, заложенная в алгоритме PairHMM вычисляет вероятность совпадения и возможные изменения. Кроме того, когда точное совпадение неизвестно, сравнение должно выполняться с каждым совпадением.

Алгоритм требует ввода двух последовательностей генов. Первая - последовательность считывания, который содержит строку гена и некоторые факторы качества, основанные на том, как он был прочитан.

Вторая последовательность представляет собой последовательность гаплотипов, которая представляет собой цепочку генов без каких-либо дополнительных данных.

Заложенное модельное уравнение Маркова сравнивает последовательности и в результате передает следующей диагонали. Следующая диагональ сравнивает те же две последовательности снова с другим сравнением.

На рисунке 2 показаны две небольших последовательности и итерации диагоналей со сдвигом сравнения. Сопоставления Маркова представляют собой единую оценку вероятности, и это вычислительно "затратно", используя плавающую запятую.

Для последовательности длина n, результатом вычисления является O (n2). Кроме того, каждый расчет зависит от предыдущих вычислений от предыдущей строки и диагонали.

Рисунок 3 показывает эти зависимости. Вероятность в конце каждой диагонали суммируется для всех срвнений каждой последовательности. Этот балл определяет насколько хорошо две последовательности соответствуют всем сравнениям. Каждое окно на рисунке 3 показывает как результат вычисления PairHMM для двух символов последовательности используется в последующих вычислениях. Эта структура называется систолическим массивом и может быть легко сопоставляемой с FPGA-структурой.

Реализация PairHMM FPGA

Этот алгоритм можно довольно хорошо оптимизировать на процессоре с использованием векторных инструкций. Если последовательности малы, сравнение может быть выполнено полностью с использованием процессоров с внутренней кэш-памятью уровня 1. Однако с большими последовательностями пропускная способность ЦП может ограничить производительность. ЦП может иметь тактовую частоту 1 ГГц, но вычмсления по-прежнему должны быть разбиты на отдельные инструкции.

Между тем, этот алгоритм великолепно работает на FPGA. FPGA сам по себе значительно быстрее используя "конвейерный параллелизм". Поэтому FPGA проводит сотни сложных вычислений параллельно и запускает один за другим каждый цикл внутри одного потока. Компилятор OpenCL от Altera анализирует код и создает эти потоки автоматически. Более низкая тактовая частота FPGA обычно позволяет приложениям работать, потребляя гораздо меньше энергии.

Эксперимент

Алгоритм Caller GapK Haplotype был первоначально написан на Java. Алгоритм затем был преобразован в C ++ Broad Institute. Для нашего эксперимента мы импортировали Алгоритм PairHMM (который был первоначально написан Broad Institute (5)) из C ++ в OpenCL.

Кроме того, код был хорошо оптимизирован и постоянные значения уже были предварительно рассчитаны. Мы проверили код функциональной корректности на эмуляторе, который является частью SDK Altera для OpenCL; мы использовали тестовые примеры, которые встроены с исходным кодом Broad Institute на C ++.

Мы использовали код на устройстве Stratix V D8 на Bittware Corp. (партнер Altera).

Компилятор сгенерировал файл .aocx, который мы загрузили в Stratix V

Мы использовали ту же методологию для запуска алгоритма на устройстве Arria 10 при разработке Altera с кремнием ES2.

Выбор оптимального размера сетки вычислений

FPGA эффективно ускоряет этот алгоритм, поскольку алгоритм может быть отображен к двумерной систолической решетке. На рисунке 3 результаты верхних вычислений переходят к вычислениям ниже , таким образом результаты просачиваются через вычислительные единицы сетки. Определение размера сетки следует искать эксперементально.

Если вычислительная сетка слишком широка, используются FPGA M20k блоки увеличиваются, потому что доступ шире и с меньшей глубиной. Если глубина требуется меньше, чем физическая глубина блока M20k, блок недоиспользуется. Несколько переменных загружаются из памяти для каждого столбца, что значительно усиливает эффект.

Если глубина вычислительной сетки слишком глубокая, слишком много символов гаплотипа считываются из DDR одновременно, то это исчерпывает пропускную способность памяти DDR. Кроме того, в конце строки добавляются сумматоры. В результате глубина линейно увеличивает количество этих сумматоров.

Когда компилятор OpenCL создает функции для FPGA Stratix V, он может соответствовать 64 Элементы обработки PairHMM в сетке 8 x 8.

Эта конструкция полностью конвейерна и может выполнять 64 полных расчета PairHMM за такт. Рисунок 4 показывает визуальное представление меньшей вычислительной сетки 4 x 4. Когда выполняется тот же код через компилятор и перенаправляется на устройство Arria 10, он создает сетку 8 x 26, что на 3,25X больше, чем размер сетки Stratix V.

Это различие связано с Arria 10 а с также дополнительной логикой, памятью и коммутационным потоком. FPGA Arria 10 также работает на несколько более высокой частоте, добавляя к росту производительности.

Результаты

Использование ПЛИС

В таблице 1 приведены результаты компиляции FPGA. Как и ожидалось, FPGA Arria 10 подходит больше Блоки вычислений алгоритма PairHMM из-за упрощенного DSP с плавающей запятой. Утилизация ARIA 10 DSP составляет почти 100%.

Для устройства Stratix V размер вычислений меньше, поскольку блоки LE и DSP реализуют функции с плавающей запятой. Также, дизайн использовал только 20% доступных блоков DSP, так как многие LE были необходимых для операций с плавающей запятой. Использование большей ПЛИС не помогло бы потому что устройство D8 имеет большинство блоков DSP.

FMAX был не намного лучше в Arria 10 из-за ранних моделей кремния и синхронизации.

Эффективность

Мы сравнили результаты производительности с начальным временем выполнения Java, временем выполнения на 3,2 ГГц процессоре Intel Xeon с использованием оптимизированного кода языка ассемблера AVX и опубликованные результаты для графического процессора Nvidia K40. Мы использовали 10-секундный тест Java для сравнения, поскольку это опубликованное сравнение исходных данных для разных технологии. Мы также использовали алгоритм для больших наборов данных, однако опубликованных данных, с которыми мы могли бы сравнить наши результаты, мы не нашли.

Заключение

Altera SDK для OpenCL позволили нам реализовать и протестировать GATK PairHMM алгоритм эффективно и легко. ПЛИС Altera продемонстрировала значительную производительность по сравнению с другими технологиями. Портируя алгоритм PairHMM из Stratix V FPGA для более продвинутой FPGA Aria 10, мы получили почти 3X улучшение производительности. Этот эксперимент показывает большие перспективы. Наши рекомендации по будущей работе включают:

  • Включение ускоренных алгоритмов в полный GATK
  • Реализация алгоритмов сжатия в FPGA для хранения и переноса генома данных более эффективно
  • Ускоряющие аналитические механизмы, такие как GATK
  • Портирование дизайна на устройства Stratix 10 для получения дополнительной производительности

Для дополнительных улучшений производительности мы можем дополнительно оптимизировать OpenCL код. Например, в текущем проекте цепочка сумматора результата на рисунке 4 не является 100% использования циклов.

Ссылки

1. Van der Auwera, Geraldine A., et al. From FastQ Data to High Confidence Variant Calls: The Genome Analysis Toolkit Best Practices Pipeline www.ncbi.nlm.nih.gov/pmc/articles/PMC4243306/
2. Altera SDK for OpenCL Programming Guide documentation.altera.com/#/00015315-AA$NT00066862
3. Settle, Sean, High-performance Dynamic Programming on FPGAs with OpenCL, 2013. ieee-hpec.org/2013/index_htm_files/29-High-performance-Settle-2876089.pdf
4. OpenCL Specification, Version 1.2, Khronos Group, 2012 www.khronos.org/registry/cl/specs/opencl-1.2.pdf
5. The GATK Guide Book, Version 3.4-46, Broad Institute, 2015. www.broadinstitute.org/gatk/guide/version-history
6. Carneiro, Mauricio, PairHMM (GitHub repository) github.com/MauricioCarneiro/PairHMM
7. Carneiro, Mauricio, Acceleration Variant Calling, Intel Genomic Sequencing Pipeline Workshop, Mount Sinai, 2013. hpc.mssm.edu/files/Carneiro_workshop.pdf
8. Altera SDK for OpenCL is First in Industry to Achieve Khronos Conformance for FPGAs, Altera Corporation, 2013. newsroom.altera.com/press-releases/nr-altera-sdk-opencl-conformance.print
9. Bittware S5-PCIe-HQ board www.bittware.com/products-services-fpga-cots-hardware/s5-pcie-hq

Связь с нами

АО «Алмаз-СП»
127025, Москва, ул.Образцова, д.7, строение 2
+7 (495) 221-69-21