С незапамятных времен человечество стремилось делать вещи меньше ...
Эрлих Блахман
В предыдущей части мы представили результаты нашего нового алгоритма сжатия Middle-out для данных временных рядов. Сегодня мы углубимся в технические детали.
Средняя часть
Все мы знаем, как работает сжатие Middle-out на шоу HBO [2], но как мы на самом деле применим это к данным временных рядов?
Взгляните на следующую схему. Есть входной вектор данных. Этот вектор разделен на средние сегменты. Для простоты в изображении всего четыре сегмента, но при сжатии фактически используется восемь. Это связано с тем, что векторные инструкции AVX-512 могут обрабатывать до 8 дублей одновременно. Если бы мы использовали числа с одинарной точностью, то у нас было бы 16 средних сегментов и обрабатывать 16 элементов за раз.
Первые элементы каждого сегмента (обозначены синим цветом) являются ссылочными значениями. Эти значения хранятся как есть перед сжатыми данными.
Пока у нас есть несколько опорных точек, мы можем вычислять различия между следующими значениями параллельно. Это позволяет нам перебирать все промежуточные сегменты одновременно в одном блоке инструкций SIMD. В рамках каждой итерации текущие значения подвергаются операции XOR с предыдущими, а результаты этой операции сохраняются в одном блоке данных.
Если есть напоминание о делении длины входного вектора на количество промежуточных блоков, значения из этого напоминания сохраняются в несжатом виде в конце сжатых данных.
Конечно, несжатый верхний и нижний колонтитулы добавляют некоторые накладные расходы на пространство, но мы предполагаем, что накладные расходы будут амортизированы по крайней мере среди нескольких тысяч значений.
Каждый блок данных начинается с битовой маски, определяющей, какие значения совпадают с предыдущими. Если соответствующий бит установлен, то мы знаем, что значение не изменилось. Если все биты установлены, никакая дополнительная информация не сохраняется - все значения такие же, как и предыдущие. В этом случае мы можем сохранить неизменное значение всего в одном бите.
Затем мы сохраняем правильные смещения (конечные нули) с округлением до байтов. Пока мы адресуем целые байты, нам нужно всего 3 бита для хранения этого смещения. Сохраняются только смещения, соответствующие измененным значениям. Затем сохраняется максимальная длина (в этом блоке) ненулевого значения XOR. Эта длина также содержит байты, и мы знаем, что максимальная длина не может быть 0; это будет означать, что все значения такие же, как и предыдущие, и мы вообще не будем хранить эту информацию. Следовательно, нам нужно хранить только длины от 1 до 8, которые могут быть сохранены в 3 битах. Мы сохраняем длину только один раз для каждого блока, потому что предполагаем, что все сжатые данные будут иметь, как правило, одинаковые характеристики, то есть изменяться примерно на одно и то же значение. Все эти значения, закодированные в 3 битах (смещения и длина), объединяются, и при необходимости для достижения границы байта вставляется дополнительное заполнение.
Наконец, части XOR хранятся в конце блока данных.
Преимущества этого сжатия от AVX-512
У нас есть две реализации: одна использует векторные инструкции, а другая нет. И мы видим, что AVX-512 предлагает большое ускорение, фактически, это первый набор инструкций, который предлагает все векторные инструкции, необходимые для этого алгоритма.
Прежде всего, это векторная инструкция подсчета начальных нулей. AVX2 не предлагает такой инструкции, поэтому данные придется перемещать туда и обратно между скалярными и векторными регистрами.
Инструкции сбора (загрузка данных в вектор из разных мест памяти) уже были введены в AVX2, но их аналог - Scatter (хранение данных), наконец, прибыл и был включен в AVX-512. . Знаете ли вы, что символы разброса на самом деле можно использовать в качестве инструкций по сжатию? Один простой трюк - писать по перекрывающимся адресам. Гарантируется, что эти магазины будут выполнены в одном конкретном порядке. Без этой оптимизации сжатие, пересекающее границы векторных элементов, было бы намного дороже.
Следующим шагом вперед в AVX-512 является поддержка маскированных инструкций с выделенными регистрами маски. Битовая маска позволяет указать элементы, над которыми должны выполняться вычисления. Это позволяет нам избавиться от непредсказуемого ветвления в критических для производительности циклах.
Есть даже инструкция, которая называется сжать. Эта инструкция непрерывно сохраняет только выбранные элементы из исходного вектора в другой вектор или в ячейку памяти.
Вывод
Мы настроили наши реализации, чтобы выжать максимум из производительности. Мы позаботились о том, чтобы ни одна инструкция не пропала зря. Например, в векторной реализации внутреннего цикла распаковки всего около 80 инструкций. Это примерно 10 инструкций ЦП на одно значение в распакованном виде.
Как оказалось, промежуточный подход может иметь значительные преимущества при обработке данных, и мы собираемся изучить другие области, в которых он может быть применен. Если у вас есть какая-либо сложная задача, для которой могут быть полезны векторные инструкции, не стесняйтесь обращаться к нам.
Исходные коды векторизованной и скалярной реализации можно найти на Github [1].
