ТЕХНИКА ОПТИМИЗАЦИИ ПРОГРАММ

       

В кэше первого уровня


Смотрите (см. graph 1): до тех пор, пока размер обрабатываемого блока не превышает размера кэш-памяти первого уровня (32Кб для AMD K6), все четыре графика идут практически горизонтально, – т.е. скоростной показатель остается практически неизменным, причем сейчас, после удаления линейной составляющей, это видно наглядно и нам уже не приходится вычислять коэффициент пропорциональности с линейкой и калькулятором в руках.

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

Помимо этого, увеличенный масштаб графика (ведь мы собственноручно растянули его в сто раз по вертикали – см. 100*Ax_GET) позволяет безо всякого труда установить, что запись ячеек памяти происходит в три раза быстрее чтения и в четыре раза быстрее чтения, последующим за записью. Виною тому – накладные расходы на организацию цикла. Компилятор Microsoft Visual C++ 6.0, которым транслировалась тестовая программа, сумел распознать цикл записи и заменил его всего одной машинной командой: REP STOSD, в то время как цикл чтения занял несколько машинных команд.

В зависимости от микро архитектуры процессора, обращение к кэш-памяти может занимать от одного до трех тактов, а максимальное количество одновременно обрабатываемых ячеек варьируется от двух до четырех. Характеристики некоторых, наиболее популярных процессоров, приведены в таблице 3.

процессор

латентность

пропускная способность

макс. операций



K5

чтение

1

2

R+R | R+W

запись

1

K6

чтение

2

1

R + W

запись

1

1

Athlon

чтение

?

2

R+R+W+W

запись

?

2

P-II, P-III

чтение

3

1

R+W

запись

1

1

P-4

чтение

2

1

R+W

запись

2

1

Таблица 3 Основные характеристики кэш памяти некоторых моделей процессоров.


Как рассчитать реальное время доступа к ячейке? Давайте сделаем это на примере процессора AMD K6. Только сначала уточним, что именно мы условимся понимать под "реальным временем доступа". Графа "латентность" сообщает количество тактов, прошедших с момента обращения к ячейке, до завершения операции чтения (записи). В частности, операция чтения ячейки осуществляется за два этапа (так же называемых стадиями): вычисление эффективного адреса и загрузка данных. На AMD K6 каждый из этих этапов выполняется за один такт, и поэтому полное время чтения ячейки составляет два такта.

Тем не менее, при отсутствии зависимости по данным, процессор может приступать к загрузке следующей ячейке не через два такта, а всего лишь через один, ведь устройство вычисления эффективного адреса уже освободилось и к началу следующего такта вновь готово к работе! Таким образом, N независимых ячеек могут быть прочитаны за N*Throughput + Latency

тактов. Очевидно, что при большом N, величиной латентности можно полностью пренебречь, приняв среднее время доступа к ячейке в 1 такт на K6 и 0.5 таков на Athlon (Athlon способен загружать две 32 битных ячейки за такт).

Правда тут есть одно "но". Параллельное выполнение команд осуществляется как минимум при наличии этих самых команд. В свернутом цикле вида for(a=0; a < BLOCK_SIZE; a++) x+=p[a]; происходит лишь одно обращение к памяти за каждую итерацию (при условии, что переменные a

и x

расположены в регистрах, конечно), поэтому время выполнения данного цикла окажется значительно больше, чем N*Throughput + Latency. Решение проблемы состоит в развороте цикла по крайней мере на две итерации. Подробнее этот вопрос уже рассмотрен в ("Часть I. Оптимизация работы с памятью. Разворачивание циклов") сейчас же нас больше интересует другой аспект, а именно: как изменится производительность при выходе за кэш первого уровня.


Содержание раздела