информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Сетевые кракеры и правда о деле ЛевинаВсе любят медЗа кого нас держат?
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Три миллиона электронных замков... 
 Doom на газонокосилках 
 Умер Никлаус Вирт 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / dnet
Имя Пароль
ФОРУМ
все доски
FAQ
IRC
новые сообщения
site updates
guestbook
beginners
sysadmin
programming
operating systems
theory
web building
software
hardware
networking
law
hacking
gadgets
job
dnet
humor
miscellaneous
scrap
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Давайте посмотрим на простом примере. 01.03.04 16:27  Число просмотров: 2489
Автор: xelator Статус: Незарегистрированный пользователь
<"чистая" ссылка>
Давайте посмотрим на простом примере.
Пусть мы хотим понять сколько работает следующая конструкция на языке С в предположении, что мы находимся на 32битной x86 архитектуре:

r = (a << n) | ( a >> (32-n))
r = (r << n) | ( r >> (32-n))

Это одна из базовых операций для RC5 (и также имеет наибольший вес в конечной производительности RC5).

1) прямолинейный способ:
r = ROL a, n
r = ROL r, n

ROL - инструкция вращения бит в 32битном регистре. Та самая, которая по нелепой версии отсутствует в железе у P4. Так вот, первая инструкция ROL и вторая - зависимые, т.к. вторая в качестве одного и операндов имеет результат первой иснтрукции ROL. Таким образом, стоимость в тактах исполнения вышеуказанной последовательности равно:

cost = latency(ROL) + latency(ROL).

Получается для AMD: cost_amd = 1+1 = 2
для P4: cost_p4 = 4+4 = 8
для Prescott: cost_psc = 1+1 = 2.
Делаем выводы о том, кто сколько работает в тактах, теперь умножаем на частоту чтобы получить время в секундах. Для данного неблагоприятного для P4 примера у него должна быть частота в 4 раза больше чем у Атлона, чтобы "в жизни" этот маленький кернел на них выполнялся одинаково быстро.

2) развертка цикла.
Теперь предположим, что мы наш маленький пример делаем в цикле много раз:

for(i=0;i<n;i++) {
r[i] = (a[i] << n) | ( a[i] >> (32-n))
r[i] = (r[i] << n) | ( r[i] >> (32-n))
}

Применим развертку цикла на 8 - исходный цикл превратится в следующий
(для простоты пусть n делится нацело на 8)
for(i=0;i<n/8;i+=8) {
r[i] = (a[i] << n) | ( a[i] >> (32-n))
r[i] = (r[i] << n) | ( r[i] >> (32-n))
r[i+1] = (a[i+1] << n) | ( a[i+1] >> (32-n))
r[i+1] = (r[i+1] << n) | ( r[i+1] >> (32-n))
...
r[i+7] = (a[i+7] << n) | ( a[i+7] >> (32-n))
r[i+7] = (r[i+7] << n) | ( r[i+7] >> (32-n))
}

Важное отличие от простейшего случая заключается в том, что теперь у нас есть независимые операции вращения, т.к. мы развернули внутри цикла 8 независимых итераций. Теперь тело цикла можно записать так:

r[i] = ROL(a[i],n); r[i] = ROL(r[i],n);
r[i+1] = ROL(a[i+1],n); r[i+1] = ROL(r[i+1],n);
...
r[i+7] = ROL(a[i+7],n); r[i+7] = ROL(r[i+7],n);

Итак инструкции для вычисления r[i], r[i+1], .. r[i+7] - независимы.
Это означает, что время исполнения тела цикла теперь равно темпу исполения инструкций ROL (на английском - throuhgput).
Темп исполнения заданного типа инструкции - это количество тактов через которое функциональное устройство процессора для выполнения этой инструкции может начать исполнять следующую инструкцию того же типа.
На первый взгляд это цифра должа равняться длительности исполнения инструкции (английское - latency), однако например на P4 все устройства конвееризированы и для инструкции вращения известно, что длительность исполнения = 4 тактам, но темп исполнения (troughput) = 1такту!
Т.е. каждый такт мы можем запускать новую инструкцию ROL на испролнение, если она независит по данным от уже запущенных.

Получается что на P4 исполнение развернутого тела цикла будет происходить так:

r[i] = ROL(a[i],n)
r[i+1] = ROL(a[i+1],n)
...
r[i+7] = ROL(a[i+7],n)
r[i] = ROL(r[i],n)
r[i+1] = ROL(r[i+1],n)
..
r[i+7] = ROL(r[i+7],n)

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

Итак, если у нас только одно устройство исполнения вращений, то стоимость выполнения цикла развернутого на 8 равно:
на AMD - cost_amd = troughput(ROL)*8 = 1*8 = 8 тактов на 8 элементов
на P4 - cost_amd = troughput(ROL)*8 = 1*8 = 8 тактов на 8 элементов
на Prescot - cost_psc = troughput(ROL)*8 = 1*8 = 8 тактов на 8 элементов
Т.е. если устройство для выполнения инструкций вращения одно, то производительность нашего цикла развернутого на 8 равна 8 тактов на 8 элементов, или 1 такт на 1 элемент на всех платформах.

Далее продолжайте сами. Возьмите другие инструкции, посчитайте сколько инструкий разного типа в алгоритме RC5, посчитайте сколько из них зависимые, посчитайте где нужно использовать темп исполнения (throughput) вместо длительности исполнения (latency) ну и в конце концов получите цифру в тактах = сколько стоит проверить один ключ.

Именно эти цифры и сходились у меня при теоретической оценке производительности RC5 для AMD, но не для P4. Имеено эта причина побудила меня посмотреть в коды для P4 и поискать там огрехи кодирования.

Кстати наконец посчитав время в тактах на ключ для разных платформ, учтите разницу в частотах процессоров и сравните со статистикой в dnet.

*Мой* IMHO вывод - алгоритм для P4 написан далеко неоптимально. На AMD он просто меньше тормозит, а не быстрей работает. Что касается RC5-72, то у меня есть в заготовках алгоритм написанный на чистом С, который не уступает по производительности (+0.5%) ассемблерной версии для P4.
Не верите? Посчитайте цифры для RC5-72 вышеописанным способом.

P.S. Для фанатов - на AMD этот алгоритм тормозит, потому что подчеркивает архитектруные особенноси P4 а не Атлонов...




<dnet> Поиск 






Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2024 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach