Вы Не Поверите, Что Это Одна Странная Инструкция Процессора!

Большинство используемых сегодня процессорных архитектур имеют инструкцию , называемую popcountсокращенно “подсчет населения”. Вот что он делает: подсчитывает количество заданных битов в машинном слове. Например (предполагая 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 обсуждает его использование внутри и снаружи криптографии. Ходят слухи, что первоначально он был добавлен в инструкции процессора по указанию АНБ. Как говорит этот архивный поток электронной почты:

Это была почти традиция, что одна из первых из любой новой более быстрой машины CDC была доставлена “хорошему клиенту” - подобрана на заводе анонимным грузовиком, и больше о ней никогда не слышали.

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

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

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

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

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

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

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

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

popcount(01000110) = 3

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

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

Бинарные Сверточные Нейронные Сети

А теперь совсем другое: бинарные сверточные нейронные сети! Но сначала-что это?

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

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

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

- А popcountв чем тут дело? Он используется для вычисления точечного произведения двух двоичных матриц:

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

Более подробная информация доступна здесь и здесь.

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

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

Молекулярная дактилоскопия

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

Попытки сопоставления хэш-массива

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

Лаконичные Структуры данных

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

• rank(i) подсчитывает количество битов, настроенных до индекса ith в bitvector
• select(i) находит индекс, в котором iустановлен бит th ranked

Чтобы сделать эти операции эффективными на больших битовых векторах, необходимо построить индекс и эффективно использовать его, причем и то, и другое включает popcountв себя . Здесь есть хороший обзор индекса RRR, и, насколько я могу судить, текущий современный подход описан в Пространственно-эффективных, высокопроизводительных структурах Rank & Select на несжатых битовых последовательностях.

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

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

Вывод

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