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

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

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

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

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

• 1961: IBM Stretch
  
• 1964: CDC 6000
  
• 1975: Cray-1
  
• 2005: SPARC
  
• 2005: ARM NEON
  
• 2007: AMD K10
  
• 2008: Intel Nehalem

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

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

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

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

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

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

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

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

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

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

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

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

popcount(01000110) = 3

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

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

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

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

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

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

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

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

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

Более подробно см. здесь и здесь.

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

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

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

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

Hash array mapped tries (HAMT)

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

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

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

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

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

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

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

Вывод

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