Обработка больших объемов данных в биоинформатике

Глава 12 из книги "Производительность приложений с открытым исходным кодом".

Оригинал: Working with Big Data in Bioinformatics
Авторы: Eric McDonald, C. Titus Brown
Перевод: А.Панин

Оптимизация

Повышение эффективности работы приложения является достаточно полезной работой, особенно в условиях обработки триллионов байт средствами этого приложения. Именно поэтому мы приступим к описанию различных мер, которые мы предприняли для повышения производительности. Мы разделим наше описание на две части: оптимизация операций чтения и разбора исходных данных и оптимизация операций изменения и записи данных из структуры Bloom filter.

Обобщенные способы оптимизации

Перед подробным рассмотрением некоторых специфических особенностей нашей работы по оптимизации приложений из состава khmer, нам хотелось бы кратко упомянуть о некоторых обобщенных способах повышения производительности приложений. Предназначенный для промышленной эксплуатации код обычно собирается с применением набора безопасных и простых оптимизаций; эти оптимизации в общем случае не должны изменять семантик кода (т.е., не должны вносить дополнительных ошибок) и должны требовать только одного раунда компиляции. Компиляторы, однако, предоставляют дополнительные возможности оптимизации кода. Эти дополнительные возможности могут грубо классифицироваться как агрессивные оптимизации (agressive optimizations), которые достаточно часто описываются в компьютерной литературе, а также профильные оптимизации (profile-guided optimizations - PGO) [6]. (Две этих категории, строго говоря, не являются взаимоисключающими, хотя обычно содержат различные оптимизации).

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

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

Поставщик данных и операции их разбора

Наши измерения показали, что время, затрачиваемое на подсчет k-меров, превышает время, затрачиваемое на осуществление операций чтения данных из хранилища. Принимая во внимание этот интересный факт, можно предположить, что мы направили все наши усилия на улучшение производительности функций, обслуживающих структуру Bloom Filter. Но рассмотрение поставщика данных и системы разбора также было полезным по нескольким причинам. Первой причиной являлась потребность в изменении архитектуры существующих поставщика данных и системы разбора для их работы в многопоточном режиме с целью достижения максимальной масштабируемости. Другая причина заключалась в нашей заинтересованности в сокращении количества операций копирования данных между буферами в памяти, что позволяло повысить производительность механизмов взаимодействия функций структуры Bloom Filter с системой разбора. Третья причина заключалась в нашем желании предоставить методы агрессивного предварительного чтения или предварительного кэширования данных, причем в случае успеха у нас появлялась возможность повышения эффективности логики подсчета k-меров до такой степени, что время чтения данных станет сопоставимым с временем подсчета. Следует отметить, что также существовали проблемы с поддержкой и расширением системы, не связанные с оптимизацией ее производительности.

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

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

Некоторые операционные системы, такие, как Linux, позволяют немного корректировать размеры окон для предварительного чтения данных. Например, для этого можно осуществить вызовы функций posix_fadvise(2) и readahead(2) для определенного файлового дескриптора. Однако, эти вызовы очень ограничены и не позволяют обойти систему кэширования. Мы же заинтересованы в обходе кэша, поддерживаемого средствами операционной системы. На самом деле этот кэш может быть преодолен в том случае, если файл открывается с флагом O_DIRECT и файловая система поддерживает его. Использование режима непосредственного доступа к данным не позволяет получить неограниченный прямой доступ к данным, так как операции чтения с дискового накопителя должны осуществляться с использованием буфера с размером, кратным размеру блока накопителя, а также данные должны помещаться в область памяти, базовый адрес которой также кратен тому же размеру блока накопителя. Это обстоятельство требует от программы выполнения дополнительных действий, которые обычно выполняются на уровне файловой системы. Мы реализовали систему непосредственного чтения данных, включая механизмы выполнения необходимых при этом действий. Существуют, однако, случаи, при которых мы все еще пытаемся настроить размер окна предварительного чтения. Наш метод доступа к хранилищу данных является последовательным и мы можем сообщить операционной системе о том, что следует предварительно считать больше данных, чем это делается в обычном режиме, используя функцию posix_fadvise(2) в качестве подсказки.

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

Операции со структурой Bloom Filter

Вспоминая о том, что мы работаем с последовательностями, составленными из символов алфавита из четырех букв: A, C, G и T, вы можете задаться вопросом о том, являются ли эти буквы прописными или строчными. Так как наше программное обеспечение работает непосредственно с передаваемыми пользователем данными, мы не можем считать, что все данные будут передаваться в верхнем или нижнем регистре, так как платформы обработки последовательностей и другие программные пакты могут изменять регистр символов. Хотя эту проблему и просто исправить для отдельных геномных чтений, нам необходимо повторять это действие для каждого чтения из миллионов и триллионов!

#define is_valid_dna(ch) \
    ((toupper(ch)) == 'A' || (toupper(ch)) == 'C' || \
     (toupper(ch)) == 'G' || (toupper(ch)) == 'T')

#define twobit_repr(ch) \
    ((toupper(ch)) == 'A' ? 0LL : \
     (toupper(ch)) == 'T' ? 1LL : \
     (toupper(ch)) == 'C' ? 2LL : 3LL)

Если вы читали страницу руководства для функции toupper или исследовали заголовочные файлы библиотеки языка программирования C от проекта GNU, вы могли заметить, что эта функция зависит от локализации и не является простым макросом. Исходя из этого, несложно догадаться о присутствии дополнительной работы, заключающейся в вызове потенциально нетривиальной связанной функции - по крайней мере при использовании библиотеки языка программирования C от проекта GNU. Но в нашем случае мы используем алфавит из четырех символов ASCII. Зависимая от локализации функции является чрезмерно усложненной для наших целей. Таким образом, нам хотелось бы не только убрать излишние операции, но и использовать что-либо более эффективное.

Мы решили привести последовательности к использованию символов в верхнем регистре до момента проверки их корректности. (И, конечно же, проверка должна происходить до попытки преобразования их в хэш-коды.) Хотя выполнение этой нормализации на уровне системы разбора и могло бы показаться идеальным, оказалось, что последовательности могут передаваться структуре Bloom Filter другими путями. Таким образом, на данный момент мы приняли решение о нормализации последовательностей прямо перед установлением их корректности. Это позволит нам отказаться от всех вызовов функции toupper и в рамках системы проверки корректности последовательностей и в рамках хэш-кодировщиков.

#define quick_toupper( c ) (0x60 < (c) ? (c) - 0x20 : (c))

c &= 0xdf; // более быстрое преобразование в верхний регистр

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

Хэш-таблицы нашей структуры Bloom Filter являются достаточно ... "обширными". Для увеличения счетчиков хэш-кода для определенного k-мера приходилось обходить практически N различных страниц памяти, где N является количеством хэш-таблиц, зарезервированных для функционирования фильтра. Во многих случаях страницы памяти, которые должны быть обновлены для следующего k-мера, являются полностью отличными от текущей страницы. Это может вести к высоким темпам обхода страниц памяти из основного пула памяти без возможности использования преимуществ кэширования. В том случае, если в нашем распоряжении находится геномное чтение с 79-символьной последовательностью и мы ищем k-меры длиной в 20 в условиях использования 4 хэш-таблиц, то потенциально может быть затронуто до 236 (59 * 4) различных страниц памяти. В том случае, если мы обрабатываем 50 миллионов чтений, очень просто увидеть насколько ресурсоемким будет процесс обработки. Что же делать с этим?

Одним из решений является поочередное обновление хэш-таблиц. Аккумулируя количество хэш-кодов для различных k-меров и после этого периодически используя их для увеличения счетчиков при переходе между таблицами, мы можем значительно улучшить производительность операций с кэшем. Начальная работа на этом фронте была очень многообещающей и, надеемся, в тот момент, когда вы читаете это, мы полностью интегрируем описанную модификацию в наш код. Кроме того, ранее в нашей дискуссии об измерении времени исполнения и профилировании мы не упомянули о программе cachegrid, являющейся частью комплекта поставки утилиты с открытым исходным кодом Valgrind [7] и зарекомендовавшей себя как полезный инструмент для оценки эффективности этого типа работы.

Продолжение статьи: Параллельное исполнение.