Как используется странная инструкция popcount в современных процессорах

Это псевдорасшифровка моей презентации на !!Con 2019 ^[1].

В большинстве используемых сегодня процессорных архитектур есть инструкция под названием popcount, сокращённо от 'population count'. Она делает следующее: подсчитывает количество установленных битов в машинном слове. Например (возьмём 8-битные слова для простоты), popcount(00100110) равно 3, а popcount(01100000) равно 2.

Вас это может сильно удивить, как и меня, но это всё, что она делает! Кажется не очень полезным, правда?

Я думал, что это какое-то недавнее дополнение для некоторых гиперспециализированных вариантов использования, но на самом деле она присутствует в архитектурах процессоров, по крайней мере, с 1961 года:

• 1961: IBM Stretch ^[2]
• 1964: CDC 6000 ^[3]
• 1975: Cray-1 ^[4]
• 2005: SPARC ^[5]
• 2005: ARM NEON ^[6]
• 2007: AMD K10 ^[7]
• 2008: Intel Nehalem ^[8]

Так что же происходит?

Инструкция АНБ

popcount также известна как «инструкция АНБ», и в очень интересном треде на comp.arch ^[9] обсуждается её использование в криптографии. Ходят слухи, что её первоначально добавили в набор инструкций CPU по просьбе АНБ. Как сказано в этом архивированном почтовом треде ^[10]:

Было почти традицией одну из каждой партии более быстрых машин CDC отправлять «хорошему клиенту» — приезжал неизвестный грузовик, и больше о ней никогда не слышали.

Отличная легенда, но для чего они её использовали?

Один из показателей информационного содержания — вес Хэмминга ^[11], который представляет собой количество ненулевых символов в строке. Для двоичной строки это именно popcount!

Как объяснялось здесь ^[12], АНБ требовалось проводить криптоанализ перехваченных сообщений, а поскольку CDC 6000 работала с 60-битными словами, одного слова было достаточно для хранения большинства алфавитов, которые их интересовали. Они были в состоянии:

1. Разбить сообщение на строки
2. Установить бит для каждого уникального символа в строке
3. Использовать popcount для подсчёта числа разных символов
4. Использовать счётчик в качестве хэша для дальнейшего криптоанализа

Любопытно, что popcount, похоже, исчез из наборов инструкций между серединой 1970-х и серединой 2000-х годов, поэтому возвращение должно объясняться чем-то ещё, кроме криптографических приложений. Для чего ещё её можно использовать?

Исправление ошибок

С понятием веса Хэмминга связано расстояние Хэмминга ^[13], которое представляет собой количество различных позиций между двумя строками одинаковой длины. Для двух двоичных строк x и y, это просто popcount после XOR. Например:

00100110
01100000 ^
--------
01000110

popcount(01000110) = 3

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

Затем мы можем спроектировать соответствующий код исправления ошибок ^[14]. Например, если передача должна выдерживать до двух изменённых битов, то кодовые слова должны отличаться по расстоянию Хэмминга по крайней мере на 5.

Бинарные свёрточные нейросети

А теперь нечто совсем иное: двоичные свёрточные нейронные сети! Но сначала, что это такое?

• Бинарность означает, что мы используем матрицы только из значений +1 (кодируется как 1) и -1 (кодируется как 0), в отличие от 32-разрядных значений с плавающей запятой.
• Свёртка означает умножение матриц?
• Нейронные сети — это системы, вдохновлённые мозгом ^[15] животных (здесь я немного плаваю).

Таким образом, мы должны выполнить умножение бинарных матриц. Но что особенного в бинарных матрицах?

Обычное умножение матриц на 32-битные значения хорошо подходит для настольных компьютеров с мощными CPU и GPU, но всё чаще мы хотим выполнять полезную работу на небольших и простых устройствах, таких как смартфоны, маршрутизаторы, умные часы и т. д. Мы можем разложить эти более сложные матрицы на слои бинарных матриц, а с ними настолько легче работать и хранить их, что мы в выигрыше даже несмотря на увеличение количества слоёв.

Тут вступает в игру popcount. Он используется для вычисления скалярного произведения двух бинарных матриц:

a = xnor(x, y)
b = popcount(a)
c = len(a)
dot(x, y) = 2 × b − c

Более подробно см. здесь ^[16] и здесь ^[17].

Шахматное программирование

Многие шахматные программы хранят данные в представлении bitboard ^[18], которое удобно вписывается в 64-битное слово. Операция Population Count использовалась для значимых операций с этим представлением, таких как вычисление подвижности ^[19] фигуры.

Молекулярный фингерпринтинг

Это тоже связано с расстоянием Хэмминга: молекулы каким-то образом хэшируются и сравниваются (с помощью popcount), чтобы определить степень их похожести. Подробнее см. здесь ^[20].

Hash array mapped tries (HAMT)

Вот где я впервые узнал о popcount! HAMT — это структура данных (впервые созданная Филом Бэгвеллом ^[21]), которая может хранить очень большое количество значений (обычно 32 или 64) в массиве на каждом узле trie. Однако выделение памяти для 32 или 64-элементного массива каждый раз может быть невероятно расточительным, особенно если массив на самом деле содержит всего несколько элементов. Решение состоит в том, чтобы добавить битовую маску, в которой количество установленных бит соответствует количеству элементов в массиве, что позволяет массиву расти и сжиматься по мере необходимости. Вычисление индекса для данного элемента эффективно может быть сделано с помощью popcount. В моём блог-посте ^[22] с реализацией структур HAMT можете узнать больше, как они работают.

Сжатые структуры данных

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

• rank(i) подсчитывает количество бит, заданных до i-го индекса в бит-векторе
• select(i) находит индекс, в котором установлен i-й бит

Чтобы сделать эти операции эффективными на больших бит-векторах, требуется построить индекс и эффективно его использовать, в обоих случаях с участием popcount. Вот здесь ^[23] есть хороший обзор индекса RRR. И, насколько я могу судить, самый передовой современный подход описан в статье Space-Efficient, High-Performance Rank & Select Structures on Uncompressed Bit Sequences ^[24].

Оптимизации компиляторов

popcount стала настолько распространённой, что и GCC ^[25], и Clang ^[26] способны её обнаружить и заменить встроенной инструкцией. Представьте такого Клиппи: «О, я вижу, что вы пытаетесь реализовать popcount, позвольте мне выйти и исправить это для вас»! Соответствующий код LLVM находится здесь ^[27]. Даниэль Лемир приводит его как пример удивительного ума современных компиляторов.

Вывод

Окутанная тайной в начале своей истории, инструкция popcount стала повсеместно использоваться, хотя и осталась немного необычной инструкцией CPU. Мне нравится, как она связывает такие разные области информатики, и мне интересно, сколько ещё существует других таких же странных инструкций. Если у вас есть своя любимая, хотелось бы услышать о ней!

Автор: m1rko

Источник ^[28]