Когда использовать параллельный подсчет - MIT HAKMEM для подсчета битов, когда возникает проблема с памятью? - PullRequest
Новая
       45

Когда использовать параллельный подсчет - MIT HAKMEM для подсчета битов, когда возникает проблема с памятью?

6 голосов
/ 21 декабря 2011

Bitcounting может быть сделано несколькими способами, например.с установленным битовым итератором, неустановленным битовым итератором, предварительно вычисленными битами с таблицами поиска или параллельным счетом.Как я выяснил, выполняя поиск в Интернете, итератор с ненастроенными битами работает быстрее, когда меньше битов с неустановленными битами, и устанавливает итератор битов наоборот.Но когда следует использовать параллельный счет, в частности MIT HAKMEM (см. Ниже)?Это выглядит довольно быстро, хотя, вероятно, медленнее, чем таблицы поиска.Всегда ли это лучше по сравнению с установленным / неустановленным битом с точки зрения скорости?Есть ли другие соображения относительно того, какой из них выбрать, кроме скорости и памяти? 

 int BitCount(unsigned int u) {
     unsigned int uCount;

     uCount = u - ((u >> 1) & 033333333333) - ((u >> 2) & 011111111111);
     return ((uCount + (uCount >> 3)) & 030707070707) % 63;
 }

Ответы [ 4 ]

5 голосов
/ 10 января 2012

Зачем выбирать один метод подсчета бит вместо другого?Ну, это действительно зависит от вашей машины и проблемы, которую вы пытаетесь решить.Обратите внимание, что все приведенные ниже количества команд относятся к базовому процессору RISC и могут плохо переводиться на более сложного зверя, такого как x86.

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

Алгоритм, представленный Бо Перссоном, довольно быстр (2 + 5*pop(x) инструкции)но только если слово малонаселенное.Он также может быть изменен для работы с густонаселенными словами.Он также содержит ветви и не имеет существенного параллелизма на уровне команд.

РЕДАКТИРОВАТЬ: Метод поиска в таблице также может быть очень быстрым, но он осуществляет доступ к памяти.Если вся таблица находится в кеше L1, то это, вероятно, один из самых быстрых алгоритмов.Если таблица не находится в кеше, то она почти наверняка одна из самых медленных.

Алгоритм ниже представляет собой вариант одного из алгоритмов HAKMEM и представлен в книге Восторг хакера (Я очень рекомендую эту книгу, если вам нравятся такие вещи).Выполняется в 19 инструкциях и не имеет ответвлений.Он также не использует деление, но имеет умножение.Он также очень экономичен в том, что использует регистры, максимально используя одну и ту же маску.Здесь все еще нет существенного параллелизма на уровне команд, который я вижу. 

int pop(unsigned x) {
  unsigned n;

  n = (x >> 1) & 0x77777777;
  x = x - n;
  n = (n >> 1) & 0x77777777;
  x = x - n;
  n = (n >> 1) & 0x77777777;
  x = x - n;
  x = (x + (x >> 4)) & 0x0F0F0F0F;
  x = x * 0x01010101;
  return x >> 24;
}

В книге Хакера «Восхищение» также представлена ​​пара даже более специализированных алгоритмов для полей шириной 9–8–7 или использования операторов с плавающей запятой.Обратите внимание, что большая часть анализа, который я представил выше, также частично была взята из этой книги.

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

4 голосов
/ 10 января 2012

Это очень просто, но удивительно быстро, если задано всего несколько битов: 

int popCount (U64 x) {
   int count = 0;
   while (x) {
       count++;
       x &= x - 1; // reset LS1B
   }
   return count;
}

С Вики по шахматному программированию: путь Брайана Кернигана

1 голос
/ 11 января 2012

Если у вас есть x86-CPU, который поддерживает SSE4, у вас уже есть одна инструкция для выполнения всей работы: POPCNT.См. Справочник по программированию Intel® SSE4 .(PDF, 698 КБ)

Еще одно замечание: параллельные алгоритмы, такие как HAKMEM 169, не содержат условных ветвей.Это огромное преимущество.Современные процессоры предсказывают направление условных ветвлений, но имеют проблемы со случайными паттернами ветвления.Неправильные прогнозы очень дороги (стоимость может быть больше, чем эквивалент 100 инструкций).Лучше избегать циклов с переменным числом циклов и / или условных операторов, если важна производительность.Для получения дополнительной информации:

Я также рекомендую книгу Hackers Delight .

0 голосов
/ 11 января 2012

Как что-то вроде следующего:

  1. Из каждого необработанного слова r вычислите парное слово как w = r - (r & 0x55555555) `. Каждая пара битов будет содержать количество установленных битов в этой паре (0-2).
  2. Далее, из каждого парного слова вычислите четырехугольное слово `q = (w & 0x33333333) + ((w >> 2) & 0x33333333)`. Каждый квартет установленных битов будет содержать количество установленных битов в этом квартете (0-4).
  3. Суммируйте слова с квадратами в группы по два, и из каждой суммы `s` вычисляйте сумму с октетами` o = (s & 0x0F0F0F0F) + ((s >> 4) & 0x0F0F0F0F) `. Каждый октет будет содержать общее количество установленных бит в соответствующем октете в обоих входных словах (0-16).
  4. Суммируйте суммы в октетах в группах по восемь, и из каждой суммы `s` вычисляйте сумму в полуслова` h = (s & 0x00FF00FF) + ((s >> 8) & 0x00FF00FF) `. Каждое полуслово будет содержать общее количество установленных битов в соответствующем полуслове всех 16 входных слов (0-256).
  5. Суммируйте суммы, объединенные в половину слова, в группах по 128, и из каждой суммы `s` вычислите общую сумму` t = (s & 0x0000FFFF) + ((s >> 16) & 0xFFFF) `. Это будет содержать количество установленных бит в 1024 входных словах (0-32768)

Обратите внимание, что два шага выполняются для каждого слова, по одному для каждого другого слова, по одному для каждых шестнадцати и по одному для каждых 1024. Если слова представляют собой 64 бита вместо 32, для окончательного варианта потребуется дополнительный шаг сумма, но суммированные слова могут быть добавлены в группы по 65 536 (представляющих 67 108 864 входных слов).

...