Висновок., Різне, Програмування, статті

Автор: Кулях Олександр


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


Для обчислення 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 немає необхідності створювати повністю паралельний алгоритм, як ми це робили для 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.


Ми використовуємо таблицю залишків розміром 8×256 учетверенной слів, побудовану аналогічно таблиці паралельного алгоритму обчислення CRC32. Ще раз зауважимо, що тільки від цієї таблиці залежить, яка контрольна сума (нормальна або дзеркальна) обчислюється в основному циклі.


Швидкість цього варіанту алгоритму обчислення CRC64 на процесорі E6850 приблизно в 2.45 рази вище, ніж у першого варіанта, і з очевидної причини приблизно в 2 рази нижче досягнутої нами раніше швидкості обчислення CRC32.


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


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


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

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*