[Перевод] Высокопроизводительное сжатие DEFLATE с оптимизацией для геномных наборов данных
igzip — высокопроизводительная библиотека для выполнения сжатия gzip или DEFLATE. Она была изначально описана в статье Высокопроизводительное сжатие DEFLATE для процессоров с архитектурой Intel. В этой статье описывается связанный выпуск исходного кода, содержащий необязательные (во время сборки) оптимизации для повышения степени сжатия геномных наборов данных в форматах BAM и SAM. igzip работает примерно в 4 раза быстрее, чем Zlib при настройке на максимальную скорость, и с примерно такой же степенью сжатия для геномных данных. Мы считаем, что igzip можно схожим образом оптимизировать для других областей применения, где наборы данных отличаются от обычных текстовых данных.ОбзорМожно собрать две основные версии igzip: igzip0c и igzip1c. Первая работает быстрее, а вторая — чуть медленнее, но с более высокой степенью сжатия. Обе эти версии значительно быстрее, чем стандартные gzip -1 или Zlib -1, но отличаются чуть меньшей степенью сжатия. В этих реализациях используется набор инструкций SSE 4.2. Они предназначены для процессоров Intel, поддерживающих этот набор инструкций.В статье, указанной выше, мы описали степень сжатия и производительность igzip при работе над данными общего назначения. После этого мы расширили реализацию для эффективной обработки геномных данных. В вычислительном процессе, используемом при определении геномной последовательности, серьезным ограничением производительности является сжатие данных. Существуют сценарии использования с долгосрочным хранением, когда требуется очень высокая степень сжатия, особенно если учесть значительные размеры наборов геномных данных. Тем не менее на различных этапах определения геномной последовательности существуют операции, в которых требуется очень быстрое сжатие с умеренной степенью сжатия. В этом исследовании мы сосредоточились на двух основных форматах данных, используемых для определения геномной последовательности; это форматы SAM и BAM.Анализ этих форматов показал, что содержимое данных весьма специфично, встречается только в геномных данных и значительно отличается от обычных данных (например, от наборов данных в коллекции Университета Калгари). Мы выявили следующие основные свойства геномных данных: очень малая длина совпадений при обработке LZ77 (~90% совпадений длиной менее 8 байт), очень малые смещения (у ~90% совпадений сдвиг менее 1024 байт) и очень разнообразное распределение литералов (например, в формате SAM значительное количество символов A, T, G, C из обработанных строк последовательностей). Мы изменили таблицы Хаффмана в igzip таким образом, чтобы учесть эти особенности, и добились примерно такой же степени сжатия, как у Zlib-1, но в 4 раза быстрее.
Интерфейс программирования API: struct LZ_Stream2 { UINT8 *next_in; // Next input byte UINT32 avail_in; // number of bytes available at next_in UINT32 total_in; // total number of bytes read so far UINT8 *next_out; // Next output byte UINT32 avail_out; // number of bytes available at next_out UINT32 total_out; // total number of bytes written so far UINT32 end_of_stream; // non-zero if this is the last input buffer LZ_State2 internal_state; }; void init_stream (LZ_Stream2 *stream); void fast_lz (LZ_Stream2 *stream); Основной принцип состоит в том, что next_in указывает на входной буфер, а avail_in указывает длину этого буфера. Аналогичным образом next_out указывает на пустой выходной буфер, avail_out указывает размер этого буфера.Поля total_in и total_out начинаются с 0 и обновляются функцией fast_lz (). Они соответствуют общему количеству прочтенных или записанных байт на текущий момент на случай, если такая информация нужна вызывающему приложению.Функция init_stream () статически инициализирует структуру данных потока, и в частности внутреннее состояние.Вызов fast_lz () возьмет данные из входного буфера (обновив next_in и avail_in) и запишет сжатый поток в выходной буфер (обновив next_out и avail_out). Функция возвращается, когда либо avail_in, либо avail_out выдаст нуль (т. е. когда закончатся входные данные либо когда заполнится выходной буфер).После передачи последнего входного буфера следует задать флаг end_of_stream. При этом процедура обработает битовый поток до конца входного буфера, если в выходном буфере достаточно места.Простой пример
LZ_Stream2 stream; UINT8 inbuf[LEN_IN], outbuf[LEN_OUT]; init_stream (&stream); stream.end_of_stream = 0; do { stream.avail_in = (UINT32) fread (inbuf, 1, LEN_IN, in); stream.end_of_stream = feof (in); stream.next_in = inbuf; do { stream.avail_out = LEN_OUT; stream.next_out = outbuf; fast_lz (&stream); fwrite (outbuf, 1, LEN_OUT — stream.avail_out, out); } while (stream.avail_out == 0); assert (stream.avail_in == 0); } while (! stream.end_of_stream); Операция Zlib FLUSH_SYNC в данный момент не поддерживается.
Версии исходного кода
Параметры в файле options.inc определяют, какая версия будет собрана. Это определяет количество символов в синтаксисе YASM. Сценарий Perl преобразует этот файл в options.h для использования в коде C. Редактировать файл options.h вручную не следует. (Если Perl недоступен, можно вручную отредактировать options.h, но затем убедиться, что параметры в файлах options.h и options.inc совпадают.)Как уже было сказано выше, две основные версии — это 0c и 1c. Версия выбирается путем редактирования файла options.inc, где может быть одна из следующих строк.
%define MAJOR_VERSION IGZIP0C
или %define MAJOR_VERSION IGZIP1C
(В этом выпуске версии IGZIP0 и IGZIP1 не поддерживаются.)В любой из этих версий можно выбрать одну из трех таблиц Хаффмана. Таблица по умолчанию предназначена для использования с большинством файлов. Существуют две другие таблицы, оптимизированные для использования с геномными приложениями, в частности для файлов в формате SAM и BAM. Чтобы выбрать одну из этих таблиц, раскомментируйте соответствующие строки (удалив начальную точку с запятой).
;%define GENOME_SAM
;%define GENOME_BAM
Если обе строки закомментированы (как показано выше), используются таблицы по умолчанию. Не следует раскомментировать обе эти строки одновременно.По умолчанию igzip создает файл в формате GZIP (RFC 1952). Если строка
;%define ONLY_DEFLATE
раскомментирована, то будут сформированы выходные данные формата DEFLATE, т. е. без заголовков GZIP.
Рисунок 1. Поддерживаемые (протестированные) версии в этом выпуске
Код можно собрать в Linux или Windows. Существует Makefile для Linux. Код сочетает C и ассемблер. Для сборки ассемблерного кода следует использовать ассемблер YASM. Путь к YASM в Makefile можно изменить в соответствии с местом установки YASM в среде пользователя.Собрать код можно (под управлением Linux) в виде статической библиотеки, например make lib0c или make lib1c, или в виде общего объекта, например make slib0c или make slib1c.
Результаты Этот выпуск igzip поддерживает не только две основные версии (igzip0c и igzip1c), но и дополнительную оптимизацию для геномных наборов данных, в частности для файлов BAM и SAM. Эти файлы довольно сильно отличаются от обычных файлов, а распространенность статистических данных по каждому типу этих файлов означает, что можно оптимизировать таблицы Хаффмана для этой статистики и добиться более высокой степени сжатия.Для иллюстрации три тестовых файла были сжаты при разных конфигурациях. Одним из тестовых файлов был progl из коллекции Университета Калгари (так называемого корпуса Калгари). Он соответствует обычному файлу. Два других файла — произвольные примеры геномных файлов форматов BAM и SAM. В каждом тесте была вычислена степень сжатия как частное от деления размера сжатого файла на размер несжатого файла (чем меньше, тем лучше). Для краткости показана только степень сжатия для «предпочитаемой» версии igzip (т. е. при запуске igzip0c-bam для файла BAM). Как и ожидалось, предпочитаемая версия обеспечивает более высокую степень сжатия, чем другие версии (например, при запуске igzip0c для файла SAM вместо igzip0c-sam). Кроме того, для упрощения мы показываем производительность igzip только для предпочитаемых типов данных. Производительность не слишком различается из за разных таблиц Хаффмана в igzip, она больше зависит от входного типа данных.
Примечание. Тесты и оценки производительности проводятся на определенных компьютерных системах и компонентах и соответствуют приблизительной производительности продуктов Intel в этих тестах. Любые отличия в оборудовании системы и в программном обеспечении или конфигурации могут повлиять на фактическую производительность. При выборе приобретаемых продуктов следует обращаться к другой информации и тестам производительности. Дополнительные сведения о тестах производительности и о производительности продуктов Intel см. здесь.Результаты производительности, приведенные в этом разделе, были получены при измерении на процессоре Intel® Core™ i7 4770 (Haswell). Тесты проводились при отключенной технологии Intel® Turbo Boost Technology и представляют производительность без использования технологии гиперпоточности Intel® (Intel® HT) на одном ядре. Мы предлагаем результаты для данных в памяти, исключая файловый ввод-вывод.
Мы скомпилировали реализации Zlib с помощью компилятора GCC с параметрами оптимизации aggressive. В качестве эталона для сравнения мы использовали Zlib версии 1.2.8.Временные показатели измерялись с помощью функции rdtsc (), которая возвращает счетчик штампа времени процессора (TSC). TSC — это количество тактовых циклов после последнего сброса. TSC_initial — значение TSC, записанное перед вызовом функции. После завершения работы функции rdtsc () вызывается снова, чтобы записать новый счетчик циклов TSC_final. Фактическое количество циклов для вызванной процедуры вычисляется с помощью выражения: кол-во циклов = (TSC_final — TSC_initial).Для каждого файла проведено значительное количество таких измерений с последующим усреднением их результатов.
Рисунок 2. Разница в скорости и в степени сжатия igzip0c* по сравнению с gzip/Zlib -1
Таблица 1. Производительность сжатия (циклов на байт) и степень сжатия
В таблице показаны степень сжатия и производительность для «предпочитаемой» версии igzip для соответствующего типа файлов. Видно, что, в частности, для тестовых файлов BAM и SAM, степень сжатия igzip очень близка с zlib -1. Для файлов в формате SAM степень сжатия и скорость оказались такими же, как для некоторых обычных файлов из набора данных Университета Калгари, тогда как для формата BAM и степень сжатия, и скорость ниже, чем для SAM (это касается и igzip, и Zlib). В формате BAM значительная часть данных полей уже упакована в двоичном формате, из-за чего сжатие при помощи алгоритмов LZ77 незначительно. В результатах видно, что по скорости igzip примерно в 4 раза быстрее Zlib (при настройке на максимальную скорость в обоих случаях).
Заключение igzip — библиотека для высокоскоростного сжатия по алгоритму DEFLATE/gzip. Возможны ее различные конфигурации с разным соотношением степени сжатия и скорости. Кроме того, существуют дополнительные возможности оптимизации для геномных файлов BAM и SAM. При оптимизации степень сжатия близка к gzip -1, но скорость существенно выше. Изучив форматы SAM и BAM, мы считаем, что можно анализировать различные наборы данных из других приложений, которые могут довольно сильно отличаться от стандартных текстовых данных, и разрабатывать индивидуально подобранные реализации igzip со схожими результатами.Дополнительные сведения об оптимизации компиляторов см. в нашем уведомлении об оптимизации.Скачать исходный код igzip.
