К. Касперски - Техника оптимизации программ, Эффективное использование памяти (1127752), страница 73
Текст из файла (страница 73)
Количество порций данных, загружаемых за олин шинный цикл обращения к памяти, на разных процессорах различно и определяется размером линеек каша второго уровня. В частности, Р-П и Кб с 32-байтовыми кэш-линейками заполняют их четырьмя 64- битовыми порциями данных. Легко подсчитать, что полное время доступа к памяти требует от !О до 12 тактов системной шины, но только 4 из них уходят на непосредственную перелачу данных, а все остальное время шина свободна. Однако если адрес следуюцзей обрабатываемой ячейки известен заранее, процессор может отправить контроллеру очередной запрос, не дожидаясь завершения предыдущего.
Конвейеризация позволяет скрыть латентность (начальную задержку) памяти, сократив время доступа к памяти с 10(12) тактов до 4 (рис. 3.42). Правла, чтение первой ячейки будет по-прежнему требовать !Π— 12 тактов, но при циклической обработке данных этой задержкой можно пренебречь. Вот и ответ на вопрос — почему для эффективной предвыборки данных потребовался сдвиг на одну итерацию. Это необходимо для компенсации времени латентности (Т!), которая в данном случае существенно превосходит полезное время передачи данных (Ть). Глава 3 зло ть Рис. 3.42.
Демонстрация конвейеризации обмена с памятью Время выполнения цикла без использования предвыборки. В отсутствие пред- выборки время выполнения цикла определяется суммой времени выполнения вычислительных инструкций цикла (Т,), времени латентности (Т~) и времени загрузки данных (Ть). Причем, во время выполнения вычислений системная шина простаивает, а во время загрузки данных, наоборот, вычислительный конвейер простаивает, а шина — работает. Причем, время доступа к памяти определяется не пропускной способностью шины, а латентностью подсистемы памяти. Шина же в лучшем случае нагружена на 15%— 20% (рис.
3.43). Исполнительные нкпы Рис. 3.43. Исполнение цикла без использования предвыборки Время выполнения цикла в случае Т, >= Т~+ Ть. Если время выполнения вычислительных инструкций цикла равно или превышает сумму времени латентности памяти и времени загрузки данных, упреждаюшая предвыборка Кзш эффективно распараллеливает работу системной шины с работой вычислительного конвейера (рис. 3.44).
Исполнительные циклы Итерация !+1 Итерация ! Системная шина Тв Исполнительный конвейер Рис. 3.44. Исполнение цикла Т, > = Т, + Т„с дистанцией предвыбсрки в одну итера- цию. Стрелкой с символом Ф показана зависимость пс данным Задержки доступа к памяти полностью маскируются, и время выполнения цикла определяется исключительно объемом вычислений, при этом произ- Т, +Ть водительность увеличивается в ! + ' ' раз, т, е, в лучшем случае (при Т, Т, = Т! + Т,) время выполнения цикла сокращается вдвое. Минимальная дистанция предвыборки равна одной итерации, однако если программа попадет на быстрый компьютер с медленной памятью (что типично для офисных и домашних компьютеров), запрошенные ячейки не успеют загрузиться за время выполнения предыдущей итераций. Это приведет к образованию "затора" на шине, вынужденному простою процессора и, как следствие, — потере производительности. Наилучший выход из ситуации — увеличить дистанцию предвыборки до двух-трех итераций.
Да, мы теряем несколько первых проходов цикла, но при болыпом числе итераций два-три прохода — это "капля в море"! Время выполнения цикла в случае Т! + Ть > Т, > Ть. Если полное время лоступа к памяти (т. е. сумма времени латентности н времени загрузки данных) превышает время выполнения вычислительных инструкций (Т,), а время выполнения вычислений в свою очередь превышает время загрузки данных, то эффективное распараллеливание по-прежнему возможно (рис. 3.45)! Необходимо лишь конвейеризовать запросы на загрузку данных, запрашивая очередную порцию данных до получения предыдущей.
Это достигается увеличением дистанции предвыборки на несколько итераций, минимальное количество которых определяется по формуле: Т, +Т„ (3.1) рад = Т, Глава 3 Згг где рзг! — Рге(его!з Яс!тег)ц!(пй 01ьчапсе — планируемая дистанция предвыборки, измеряемая в количестве итераций. Точно так, как и в предыду1цем примере, в данном случае дистанцию предвыборки лучше взять с запасом, чем недобрать. В худшем случае производительность уыеличиыаел1сл ы дыа раза, а в среднем— от 4 до 5раз (поскольку типичная латенптость памяти порядка 1О тактов, а 10+4 время загрузки ланных — 4 такта, то при Т, = Ть получаем: 1 е = 4,5), 4 причем загрузка системной шины достигает 80 — 90% (в идеале — все 100%).
Великолепный результат, не так ли? Исполнительные циклы Системная шина н1,,ть !+2,' " Ть нз Рис. 3.45. Исполнение цикла Т, + Ть > Т, > Ть с дистанцией предвысорки в две итерации. Стрелкой с символом Ьт показана зависимость по денным рзй = 1 е — . Т, Ть (3.2) Время выполнения цикла в случае Ть > Т,. Наконец, если время загрузки данных (Ть) превышает время выполнения вычислительных инструкций цию1а, полный параллелизм становится невозможен в принципе, — раз загрузка превышает продолжительность одной итерации, простой вычислителыюго конвейера неизбежен и никакая предвыборка тут не поможет (рис. 3.46).
Тем не менее, предвыборка все же будет полезной, поскольку позволит маскировать латентность памяти, что приведет к двух- трехкратному приросту производительности. Согласитесь — величина не малая. Оптимальная дистанция предвыборки определяется по формуле: Каг и Поскольку время выполнения цикла определяется исключительно скоростью загрузки данных (т.
е. фактически частотой системной шины, загрузка которой в этом случае достигает !00%), излишне усердствовать над оптимизацией кода — в этом нет никакого смысла. Такая ситуация имеет место, в частности, при копировании или сравнении блоков памяти.(Хотя об оптимизации копирования — разговор особый, см. разд.
"Секреты копирования палгяпггг или практическое применение новых колганд процессоров Рептгит-Ш и Репггит-4" этой главы). Исполнительные циклы Т, Ть Щфф т,, Системная нина т. Ть Исполнительный «онеейер г+рга г+рм+1 г+рм+2 ырм+3 Рнс. 3.46. Исполнение цикла То > Т, с дистанцией предвыборки в три итерации. Стрелкой с символом ь' показана зависимость по данным Практическое планирование предвыборкн. Для вычисления оптимальной дистанции предвыборки необходимо знать; величину латентности памяти (Тг), время загрузки данных (Ть) и продолжительность выполнения одной итерации цикла (Т,). Поскольку все три аргумента аппаратно-зависимы, приходится либо динамически определять их значения в ходе выполнения программы, либо статически вычислять нижний предел дистанции предвыборки.
Рассмотрим оба алгоритма подробнее. Динамггческое определение дает наивысший прирост производительности и достаточно просто реализуется. Один из возможных алгоритмов выглядит так: замеря время выполнения первой итерации цикла (это можно сделатгн например, посредством инструкции аотзс), мы получаем сумму Т, + Тг+ Ть. Затем, повторным выполнением этой же итерации мы находим величину Т, (т. к. данные уже находятся в каше, время доступа к ним пренебрежительно мало). Разность этих двух величин даст сумму Тг+ Ть, которой, вкупе с "чистой" Т„вполне достаточно для вычисления по формуле (3.1).
Правда, определить "чистое" время Ть, необходимое лля формулы (3.2), таким способом довольно затруднительно, и лучше прибегнуть к алгоритму Глава 3 374 р зо = Х!осеир р Хх6:г (Хргсг р 1(а) СР1 Х„„, (З.З) где: рЫ вЂ” дистанция предвыборки (итераций цикла); Х„,к„— латентность памяти (тактов); Х„„,„— время загрузки кэш-строки (тактов); Х„„г и Մ— количество предвыбираемых н сбрасываемых кэш-линий (штук); СР! — время выполнения одной инструкции (такты); Х„„, — количество инструкций в одной итерации цикла (штуки). В этой формуле почти все члены — неизвестные.
Латентность памяти варьируется в очень широких пределах, поскольку определяется и типом самой памяти (Б!ЗКАМ, ООК БОКАМ, КаптЬцз ОКАМ), и качеством чипов памяти (т. е. латентностью сигналов КАБ и САБ), и "продвинутостью" чипсета, и, наконец, отношением частоты системной шины к частоте ядра процессора. Время загрузки кэш-строк пропорционально длине этих самых строк, которые составляют 32, 64 или 128 байт в зависимости от модели процессора "вилки", суть которого заключается в следующем, Перебирая различные дистанции предвыборки и сравнивая продолжительность соответствующих им итераций цикла, мы всего за несколько проходов найдем наиболее оптимальное значение, да не просто оптимальное, а самое оптимальное, т. к.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
