Параллельное вычисление CRC64

Май 25, 2009 — Шарахов А.П.

Эти заметки дополняют мою статью ”Параллельное вычисление CRC32”. Предлагается алгоритм вычисления CRC64, основанный на тех же идеях. Производительность алгоритма в 2-2.5 раза выше стандартной табличной реализации вычисления CRC64. На компьютере с процессором E6850/3.2GHz он расходует 2.66 такта процессора на байт, т.е. скорость обработки данных при вычислении CRC64 составляет 0.375 байта за такт центрального процессора или 1.2*10^9 байтов в секунду.

Стандартный табличный алгоритм вычисления CRC64

Для вычисления CRC64 мы будем использовать многочлен 42F0E1EBA9EA3693 (ECMA DLT). У другого кандидата на эту роль – многочлена 000000000000001B (ISO 3309) – из-за его недостаточной плотности было обнаружено большое число коллизий на реальных данных. Стандартный табличный алгоритм вычисления CRC64 выглядит примерно так:

//Вариант 1 стандартный табличный алгоритм вычисления нормальной CRC64
procedure ReferenceRefreshCRC64(var CRC: int64; BufPtr: pointer; BufLen: integer);
asm
  test edx, edx
  jz @ret
  neg ecx
  jge @ret
  sub edx, ecx
 
  push ebx
  push esi
  push edi
  push eax
 
  mov ebx, [eax+4]
  mov esi, [eax]
  mov eax, ebx
 
@next:
  movzx edi, byte [edx + ecx]
  shr ebx, 24
  xor edi, ebx
  shld eax, esi, 8
  xor eax, [edi*8 + ReferenceTable64 + 4]
  shl esi, 8
  xor esi, [edi*8 + ReferenceTable64]
  mov ebx, eax
  add ecx, 1
  jz @done
 
  movzx edi, byte [edx + ecx]
  shr eax, 24
  xor edi, eax
  shld ebx, esi, 8
  xor ebx, [edi*8 + ReferenceTable64 + 4]
  shl esi, 8
  xor esi, [edi*8 + ReferenceTable64]
  mov eax, ebx
  add ecx, 1
  jnz @next
 
@done:
  pop eax
  mov [eax], esi
  mov [eax+4], ebx
  pop edi
  pop esi
  pop ebx
@ret:
  end;

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

Этот вариант алгоритма вычисления CRC64 мы будем использовать в качестве отправной точки, его скорость работы почти совпадает со скоростью работы стандартной реализации вычисления CRC32 на двух протестированных компьютерах (E6850 и Pentium-D).

Зачем нам кузнец

Внимательный читатель, глядя на приведенный код, наверняка заметил, что в противоположность CRC32 при подсчете CRC64 применяется нормальная, а не зеркальная форма представления многочлена и контрольной суммы. Так велит стандарт, именно нормальная форма используется, например, в PostgreSQL и других продуктах.

Понятно, что нормальный алгоритм медленнее зеркального из-за того, что требуется выполнить две лишние операции: копирование старшего слова контрольной суммы и сдвиг старшего байта контрольной суммы. Копирование мы нейтрализовали развертыванием цикла, а вот что делать со сдвигом?

Давайте на секунду отвлечемся и посмотрим, как выглядит реализация зеркального алгоритма вычисления CRC64:

//Вариант 2 стандартный табличный алгоритм вычисления зеркальной CRC64
//на E6850 работает в 1.15 раза быстрее варианта 1
//на Pentium-D работает в 1.1 раза быстрее варианта 1
procedure ReflectedRefreshCRC64(var CRC: int64; BufPtr: pointer; BufLen: integer);
asm
  test edx, edx
  jz @ret
  neg ecx
  jge @ret
  sub edx, ecx
 
  push ebx
  push esi
  push eax
 
  mov ebx, [eax]
  mov esi, [eax+4]
  xor eax, eax
@next:
  mov al, byte [edx + ecx]
  xor al, bl
  shrd ebx, esi, 8
  xor ebx, [eax*8 + ReflectedTable64]
  shr esi, 8
  xor esi, [eax*8 + ReflectedTable64 + 4]
  add ecx, 1
  jnz @next
 
@done:
  pop eax
  mov [eax], ebx
  mov [eax+4], esi
  pop esi
  pop ebx
@ret:
  end;

Сравнивая алгоритмы 1 и 2, мы видим, что их отличия заключаются в использовании разных таблиц остатков и разных направлений в операциях сдвига. Понятно также, что нормальный и зеркальный алгоритмы по-разному извлекают очередной байт контрольной суммы для формирования индекса в таблице остатков.

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

//Вариант 3 усовершенствованный алгоритм вычисления нормальной CRC64
//используется таблица остатков с зеркально переставленными байтами  
//на E6850 работает в 1.15 раза быстрее варианта 1
//на Pentium-D работает в 1.1 раза быстрее варианта 1
procedure NormalRefreshCRC64(var CRC: int64; BufPtr: pointer; BufLen: integer);
asm
  test edx, edx
  jz @ret
  neg ecx
  jge @ret
  sub edx, ecx
 
  push ebx
  push esi
  push eax
 
  mov ebx, [eax+4]
  mov esi, [eax]
  bswap ebx
  bswap esi
  xor eax, eax
@next:
  mov al, byte [edx + ecx]
  xor al, bl
  shrd ebx, esi, 8
  xor ebx, [eax*8 + ByteSwappedTable64]
  shr esi, 8
  xor esi, [eax*8 + ByteSwappedTable64 + 4]
  add ecx, 1
  jnz @next
 
@done:
  bswap ebx
  bswap esi
  pop eax
  mov [eax+4], ebx
  mov [eax], esi
  pop esi
  pop ebx
@ret:
  end;

Скорость этого варианта алгоритма равна скорости зеркального и на процессоре E6850 примерно в 1.15 раза выше, чем у первого варианта.

Кусочно-параллельный алгоритм вычисления CRC64

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

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

Основной цикл алгоритма мы позаимствуем из кусочно-параллельного алгоритма вычисления CRC32. В случае CRC64 он будет выглядеть так:

//Вариант 4 вычисления нормальной CRC64, работа с 64-битными блоками сообщения
//используется таблица остатков с зеркально переставленными байтами  
//на E6850 работает в 2.45 раза быстрее варианта 1
//на Pentium-D работает в 2.0 раза быстрее варианта 1
@bodyloop:
  mov eax, [edx + ebp - 8]
  xor eax, ebx
  movzx edi, al
  mov ecx, [edx + ebp - 4]
  xor ecx, esi
  mov ebx, [edi*8 + ByteSwappedTable64 + 2048*7]
  mov esi, [edi*8 + ByteSwappedTable64 + 2048*7 + 4]
  movzx edi, ah
  xor ebx, [edi*8 + ByteSwappedTable64 + 2048*6]
  xor esi, [edi*8 + ByteSwappedTable64 + 2048*6 + 4]
  shr eax, 16
  movzx edi, al
  xor ebx, [edi*8 + ByteSwappedTable64 + 2048*5]
  xor esi, [edi*8 + ByteSwappedTable64 + 2048*5 + 4]
  movzx edi, ah
  xor ebx, [edi*8 + ByteSwappedTable64 + 2048*4]
  xor esi, [edi*8 + ByteSwappedTable64 + 2048*4 + 4]
 
  movzx edi, cl
  xor ebx, [edi*8 + ByteSwappedTable64 + 2048*3]
  xor esi, [edi*8 + ByteSwappedTable64 + 2048*3 + 4]
  movzx edi, ch
  xor ebx, [edi*8 + ByteSwappedTable64 + 2048*2]
  xor esi, [edi*8 + ByteSwappedTable64 + 2048*2 + 4]
  shr ecx, 16
  movzx edi, cl
  xor ebx, [edi*8 + ByteSwappedTable64 + 2048*1]
  xor esi, [edi*8 + ByteSwappedTable64 + 2048*1 + 4]
  movzx edi, ch
  xor ebx, [edi*8 + ByteSwappedTable64 + 2048*0]
  xor esi, [edi*8 + ByteSwappedTable64 + 2048*0 + 4]
 
  add ebp, 8
  jle @bodyloop

Этот цикл предназначен для обработки четного числа двойных слов сообщения, головные и хвостовые байты данных мы будем обрабатывать отдельными циклами, подобными циклу из предыдущего варианта вычисления CRC64.

Мы используем таблицу остатков размером 8x256 учетверенных слов, построенную аналогично таблице параллельного алгоритма вычисления CRC32. Еще раз заметим, что только от этой таблицы зависит, какая контрольная сумма (нормальная или зеркальная) вычисляется в основном цикле.

Скорость этого варианта алгоритма вычисления CRC64 на процессоре E6850 примерно в 2.45 раза выше, чем у первого варианта, и по очевидной причине примерно в 2 раза ниже достигнутой нами ранее скорости вычисления CRC32.

Заключение

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

Читатели, используя прилагаемые к статье исходные тексты, могут проверить работу алгоритмов на других процессорах. Буду признателен, если результаты тестов будут ими добавлены на мою страничку (http://guildalfa.ru/alsha/node/4).

Те, кто дочитал до конца, могут снять комментарии кое-где в исходных текстах и поэкспериментировать с зеркальной формой многочлена, который предложил David T. Jones в качестве замены ISO 3309 для хеширования белковых последовательностей. По идее этот многочлен должен хорошо хешировать текстовые данные. При сравнении результатов имейте ввиду, что David T. Jones не выполняет инвертирование значений битов результата в конце вычислений.

на главную

Прикрепленный файл	Размер
ShaCRC32.zip	2.83 кб
ShaCRC64.zip	4.33 кб

Добавить комментарий

Comments (17)

i7-2600

Март 21st, 2012 — Гость

ReferenceRefreshCRC64 2028 msec
NormalRefreshCRC64 1747 msec
ReflectedRefreshCRC64 1763 msec
ShaNormalRefreshCRC64 499 msec
ShaReflectedRefreshCRC64 484 msec

ответить

i5-2300

Август 29th, 2011 — Гость

   ReferenceRefreshCRC64 2449 msec
      NormalRefreshCRC64 2137 msec
   ReflectedRefreshCRC64 2138 msec
   ShaNormalRefreshCRC64 592 msec
ShaReflectedRefreshCRC64 593 msec

ответить

Pentium D 2.80GHz

Сентябрь 17th, 2009 — Гость

   ReferenceRefreshCRC64 3266 msec
      NormalRefreshCRC64 2953 msec
   ReflectedRefreshCRC64 2953 msec
   ShaNormalRefreshCRC64 1641 msec
ShaReflectedRefreshCRC64 1641 msec

ответить

Intel Pentium 4 HT 2400 MHz

Сентябрь 15th, 2009 — Гость

   ReferenceRefreshCRC64 3187 msec
      NormalRefreshCRC64 2828 msec
   ReflectedRefreshCRC64 2813 msec
   ShaNormalRefreshCRC64 2500 msec
ShaReflectedRefreshCRC64 2484 msec

ответить

Alexo

Июнь 24th, 2009 — Гость

Тест на E7200@3.1 Ghz (Разгон)

   ReferenceRefreshCRC64 1670 msec
      NormalRefreshCRC64 1497 msec
   ReflectedRefreshCRC64 1467 msec
   ShaNormalRefreshCRC64  686 msec
ShaReflectedRefreshCRC64  686 msec

ответить

Athlon X2 2,97 ГГц L2=2x512Кб, L3=2Мб

Июнь 7th, 2009 — Гость

   ReferenceRefreshCRC64 1797 msec
      NormalRefreshCRC64 1656 msec
   ReflectedRefreshCRC64 1656 msec
   ShaNormalRefreshCRC64  641 msec
ShaReflectedRefreshCRC64  625 msec

Причем два последних результата Normal и Reflected часто менялись местами.

ответить

Точность измерений составляет 15 msec

Июнь 7th, 2009 — Гость

Так и должно быть. Для оценки времени выполнения использована функция GetTickCount. Она возвращает значения, которые на Windows XP тикают раз в 15-16 msec.

ответить

Нельзя ли преобразовать функцию ShaCrcRefresh в процедуру?

Май 29th, 2009 — Гость

Огромная просьба - нельзя ли преобразовать функцию ShaCrcRefresh в процедуру, как ShaNormalRefreshCRC64 ?

ответить

Нельзя ли преобразовать функцию ShaCrcRefresh в процедуру?

Май 29th, 2009 — Гость

А зачем? Ведь всегда можно написать:

  CRC:=ShaCrcRefresh(CRC, BufPtr, BufLen);

Причем в этом случае мы оставляем компилятору полный простор для оптимизации распределения переменных. Скажем, если этот вызов встретится внутри цикла, то для CRC компилятор имеет возможность использовать регистр eax. Если бы у нас была процедура с var-параметром, то компилятор был бы вынужден распределить переменную в памяти.

Есть еще один плюс. Если, например, нам требуется вычислить много мелких CRC для всех слов предложения, то удобна такая форма вызова:

  CRC:=not ShaCrcRefresh($FFFFFFFF, BufPtr, BufLen);

В случае процедуры нам потребовалось бы 2 оператора.

А если я вас не убедил, можете написать процедуру-обертку :)

ответить

Нельзя ли переделать ShaReflectedRefreshCRC64 в функцию?

Июнь 1st, 2009 — Гость

Спасибо, убедили !
А почему тогда ShaReflectedRefreshCRC64 - процедура ?
И тогда нельзя ли её переделать в функцию ?
Зачем ? Чтобы было однообразие вызовов. :)

ответить

Нельзя ли переделать ShaReflectedRefreshCRC64 в функцию?

Июнь 1st, 2009 — Гость

Мешают эстетические соображения.

Компилятор Delphi всегда размещает переменные типа int64 в оперативной памяти. По моим наблюдениям, в регистрах он может держать их только во время вычисления одного оператора. Кроме того, передачу параметров типа int64 по значению компилятор Delphi выполняет через стек. Получается, что после такой переделки при последовательных вызовах функции каждый раз текущее значение CRC64 (два двойных слова) будет копироваться из оперативной памяти на стек (т.е. опять же в оперативную память). В то время как сейчас просто выполняется загрузка адреса параметра.

Давайте посмотрим в окне CPU, какую последовательность инструкций компилятор генерирует при различных вариантах передачи параметров, на следующем примере:

function fval(a: int64): int64;
begin;
  Result:=a;
  end;
 
function fconst1(const a: int64): int64;
begin;
  Result:=a;
  end;
 
function fconst2(const a): int64;
begin;
  Result:=int64(a);
  end;
 
function fvar(var a: int64): int64;
begin;
  Result:=a;
  end;
 
procedure TForm1.Button3Click(Sender: TObject);
const
  c=$0807060504030201;
var
  a, b: int64;
begin;
  a:=fval(c);         //push
  b:=fconst1(c);      //push
  a:=a+fval(b);       //push
  b:=b+fconst1(a);    //push
  a:=a+fconst2(b);    //lea
  b:=b+fvar(a);       //lea
  ShowMessage(IntToHex(b,16));
  end;

Видно, что только в двух последних случаях компилятор Delphi использует передачу параметра по ссылке. Однако предпоследний вариант мне кажется недостаточно правильным, т.к. в нем не производится проверка типа. Кроме того, он не позволяет передавать константу -1. Поэтому процедура ShaReflectedRefreshCRC64 пока остается процедурой.

ответить

Cпасибо за подробный и

Июнь 1st, 2009 — Гость

Cпасибо за подробный и исчерпывающий ответ !

ответить

Использование MMX-инструкций для вычисления CRC64.

Май 28th, 2009 — Гость

Спасибо огромное за модули !
Скорость впечатляет !
И такой вопрос: почему бы в CRC64 не использовать MMX инструкцию PXOR ?
Интересно, как это скажется на быстродействии ?

ответить

Использование MMX-инструкций для вычисления CRC64.

Май 29th, 2009 — Гость

Была у меня такая мысль. Для проверки поставил 2 эксперимента.

Сначала попробовал заменить пары команд вида:

  xor ebx, [edi*8 + ReflectedTable64 + 2048*7] 
  xor esi, [edi*8 + ReflectedTable64 + 2048*7 + 4]

на одну:

  pxor mmN, [edi*8 + ReflectedTable64 + 2048*7]

где N=0,1,2,3,4,5,6,7 или N=0,1,0,1,0,1,0,1

Понятно, что после такой замены зависимых команд не стало больше, однако время работы чуть-чуть выросло.
Выходит, что у нас не остается времени на перенос данных из MMX-регистров в обычные для формирования адреса.

Затем развернул цикл в два раза и использовал в 2 раза большую таблицу (16x256 значений). С учетом времени на перенос данных, получил примерно ту же скорость на E6850, что и без MMX. Поэтому отказался от этой затеи.

ответить

Инструкция CRC32 в SSE 4.2

Май 29th, 2009 — Гость

Спасибо !
Любопытно что в Intel наконец-то ввели инструкцию CRC32, начиная с SSE 4.2.
Интересно насколько она оптимизирована ?

ответить

Инструкция CRC32 в SSE 4.2

Май 29th, 2009 — Гость

Если не ошибаюсь, время выполнения команды составляет 3 такта. Это означает, что можно вычислять CRC32 еще в 1.78 раза быстрее. Но есть несколько минусов:

SSE 4.2 реализован далеко не в каждом процессоре.
Выбранный Intel многочлен великолепен с математической точки зрения, но архиваторы используют другой многочлен. У программиста же возможность изменить запаянный в процессор многочлен отсутствует.
Для программиста, на мой взгляд, более актуальна реализация в железе CRC64.

ответить

Тест на AMD-K6-III@500MHz

Май 27th, 2009 — Гость

   ReferenceRefreshCRC64 14821 msec
      NormalRefreshCRC64 13139 msec
   ReflectedRefreshCRC64 13139 msec
   ShaNormalRefreshCRC64  6990 msec
ShaReflectedRefreshCRC64  5959 msec

Разница в 17% у двух последних функций может показаться довольно странной, ведь основной цикл у них совпадает.
Предположил, что дело в выравнивании кода (в первом случае выравнивание метки @bodyloop 06, во втором - 0E).
Чтобы поменять смещения в процедуру ShaNormalRefreshCRC64 перед меткой вставил 8-байтовую последовательность

  movzx edi, al
  mov edi, 0

Предположение подтвердилось, результат изменился на противоположный:

   ReferenceRefreshCRC64 14771 msec
      NormalRefreshCRC64 13129 msec
   ReflectedRefreshCRC64 13129 msec
   ShaNormalRefreshCRC64  5959 msec
ShaReflectedRefreshCRC64  6990 msec

Итого имеем ускорение 2.1-2.5 раза.

ответить

Блог Шарахова А.П.

Primary links

Параллельное вычисление CRC64

Стандартный табличный алгоритм вычисления CRC64

Зачем нам кузнец

Кусочно-параллельный алгоритм вычисления CRC64

Заключение

Comments (17)

i7-2600

i5-2300

Pentium D 2.80GHz

Intel Pentium 4 HT 2400 MHz

Alexo

Athlon X2 2,97 ГГц L2=2x512Кб, L3=2Мб

Точность измерений составляет 15 msec

Нельзя ли преобразовать функцию ShaCrcRefresh в процедуру?

Нельзя ли преобразовать функцию ShaCrcRefresh в процедуру?

Нельзя ли переделать ShaReflectedRefreshCRC64 в функцию?

Нельзя ли переделать ShaReflectedRefreshCRC64 в функцию?

Cпасибо за подробный и

Использование MMX-инструкций для вычисления CRC64.

Использование MMX-инструкций для вычисления CRC64.

Инструкция CRC32 в SSE 4.2

Инструкция CRC32 в SSE 4.2

Тест на AMD-K6-III@500MHz