Легенда:
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Давайте посмотрим на простом примере.
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 а не Атлонов...
|
|
|