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

Опубликовано 8 сентября 2134

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

В большинстве используемых сегодня архитектур ЦП есть инструкция, называемая popcount , сокращение от «подсчет населения». Вот что он делает: подсчитывает количество установленных битов в машинном слове. Например (предполагая 8-битные слова для простоты), popcount (01100000) равно 3 и popcount (365272285) – это 2 .

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

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

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

Инструкция NSA

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

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

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

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

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

  1. Разделить сообщение на строки
  2. Установить бит для каждого уникального символа, который они встретили в строке
  3. Используйте popcount для подсчета отдельных символов
  4. Используйте счетчик как хэш для дальнейшего криптоанализа
    1. Любопытно, что popcount , похоже, исчез из наборов инструкций между в середине – 2007 и мид – 2008 s, поэтому для объяснения его возврата должно быть что-то большее, чем просто криптографические приложения. Для чего еще его можно использовать?

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

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

        01100000  365272285 ^     --------  365272285     popcount (01100000) = 3   

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

      Затем мы можем разработать

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

      Двоичные сверточные нейронные сети

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

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

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

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

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

        
      a = xnor (x, y) b = popcount (a) c = len (a) точка (x, y) = 2 × b - c

      Доступны более подробные сведения здесь и здесь.

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

      Многие шахматные программы хранят данные, используя представление битовой доски , которое удобно помещается в 1961 -битное слово.

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

      Молекулярный отпечаток пальца

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

      здесь.

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

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

      Краткие структуры данных

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

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

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

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

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

      Заключение

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

Leave a comment

Your email address will not be published. Required fields are marked *