К. Касперски - Техника оптимизации программ, Эффективное использование памяти (1127752), страница 56
Текст из файла (страница 56)
Наиболее интенсивно используемые структуры данных обязательно должны быть организованы так, чтобы полностью умещаться в нем. При обработке больших массивов данных слелует ограничить свой "аппетит", по крайней мере, размером каша второго уровня и уж в самом крайнем случае "забираться" в оперативную память (подробнее см. равд. "Влияние размера обрабатываемых данных на производительность "этой главы). Проблема в том, что размер кэш-памяти в зависимости от модели процессора варьируется в очень широких пределах — попробуй, выбери, на какой из них рассчитывать.
Если есть такая возможность, программисту настоятельно рекоменлуется оптимизировать свою программу под кзш минимального уровня и "обкатывать" ее на процессоре именно с таким кзшем. С другой стороны, разумно ориентироваться на наиболее распространенные модели процессоров 1вот только как узнать — какая модель будет наиболее распространенной к моменту завершения программы?). Вторые по значимости характеристики — это степень ассоциативности и размер банков кэша. Если степень ассоциативности окажется хотя бы на единицу меньшей, чем зто вам необходимо, то кэш будет работать вхолостую, под час в лесятки раз снижая производительность. Чтобы этого не произошло, программист должен следить, чтобы интенсивно используемые данные по возможности не располагались по адресам, кратным размерам банков каша.
А это требование очень трудно обеспечить, поскольку размеры банков каша варьируются в очень широких пределах, да и их ассоциативность тоже. Чтобы быть уверенным в отсутствии коллизий, необходимо тестировать программу на всех доступных процессорах и при необходимости, корректировать размещение структур данных (подробнее см. равд. "Учет ограниченной ассоциативности кэша" этой главы).
Третья характеристика — политика записи. От нее зависит: насколько эффективно выполняется операция записи в память. Все каши современных процессоров поддерживают режим прямой записи с буферизацией и обратную запись, но количество буферов непостоянно и варьируется от процессора к процессору — от двух 64-битовых буферов младших моделей 1пге) Реппит до двенадцаги у Репгшгп РП (подробнее см. равд.
"Особенности буферизации записи" этой гливы). Кэш Таблица З.З. Основные характеристики 81- и ( 2-кешей современных процессоров Процессор Характеристика Реп!юга П Се!егоп Реп!вт П! Се)егоп Репйогп-4 А!Шов Размер(полный), Кбайт 32 32 128 раздельный раздельный раздельный раздельный тип 16 Кбайт 16 Кбайт Размер 12 К микро- инструкций 64 Кбайт Протокол Ассоциативность 8! 8) н!д 4няау 4-е(ау 32 байт 64 байт 32 байт Размер линеек 6 микро- инструкций н(д Банков в линии '1 н(д 4 Кбайт 4 Кбайт 32 Кбайт Размер банка *2 Кол-во портов Ьт КОД н(д 1 й0 сй0 н(д 'ьй0 Алгоритм заме- щения Политика записи не блок 1,0 к ядра не блок.
1,0 ядра не блок. 1,0 к ядра Блокировка Частота не блок. 1,0 к ядра 1 такт 1 такт 1 такт Время доступа 1 такт норма- льное бпе-врбп! 6 — 12 тактов н(д 6 — ! 2 тактов н(д 16 Кбайт 8 Кбайт 64 Кбайт МОЕ81 16 Кбайт ДАННЫЕ Размер МЕ8) МЕ81 МЕ81 Протокол Четвертая характеристика — длина кзш-лииий. В последних процессорах от !пге! и АМ0 она расширена до б4 байт. Но больше — еше не значит лучше.
Упреждаюшая загрузка наиболее эффективна именно при последовательной обработке данных, иначе кэш будет работать вхолостую. Помимо перечисленных сушествует еше и масса других факторов, но и без того уже ясно: оптили(зация кода под все лгикропроцессоры сразу — занятие не для слабонервных. В приведенной далее в табл. 3.3 перечислены основные характеристики ка- шей распространенных пропессоров.
Глава 3 гво Таблица З.З (продолжение) Процессор РепИцгп В Се1егоп Реп!!опт 111 Се1егоп Реп!пап-4 А11!! оп 2-ига у 4-чгау 4-тчау 4-тчау 32 байт 32 байт 64 байт Размер линеек 64 байт 2 Кбайт 4 Кбайт 4 Кбайт 32 Кбайт ДАННЫЕ Алгоритм заме- щения 1Я0 080 /.й0 ЕВ0 УУА ЬУА уут УУА цп!бед сп-бе цп/беб оп-бе оп-б!е н/д Размещение Размер, Кбайт 512, 1024, 2048 1пс/ц- ехс/сыче зме тип *3 Протокол МЕ8! МЕ81 МЕ8! МЕ81 4 8 4 8 2 16 Е2 32 байт 32, 64, 128 Кол-во портов 1.й0 *3 Ей0 1.й0 1.й0 УУВ УУВ УУВ не блок. не блок. не блок.
не блок. Частота 0,5х 1,0х О,бх 1,0х 1,0х 2 такта 4 такта 1О тактов 8 тактов* Время доступа 2-1-1-1 1.1.1-1 1-1-1-1 1-1-1-1 Формула 40 н!д йОВ, входов 40 й8, входов 20 20 4 х 32 байт 4 к 32 байт Вел Вц//ег н/д н/д Характеристика Ассоциативность Банков в линии *1 Размер банка *2 Кол-во портов Политика записи Блокировка Частота Время доступа Ассоциативность Размер кзш-линий Размер банка, Кбайт Алгоритм замещения Политика записи Блокировка не блок. 1,0 к ядра 128, 256, 512, > !пс/цз/че 32 байта 32, 64, 128 не блок. 1,0 х ядра 128, 256, 512, > !пс1цз!че не блок. +4 1,0 х ядра 128, 256, 512, > ехс/цзЬе 64 > 2 байт 32, 64, 128 не блок.
1,0 х ядра 64 байт 32 64 128 гв! Кэш Таблица 3.3 (окончание) * Данные ориентировочные. Оптимизация обращения к памяти и кэшу Влияние размера обрабатываемых данных на производительность Никто не спорит, что чем меньше массив данных, тем быстрее он обрабатывается — это общеизвестно. Для достижения наивысшей производительности следует проектировать алгоритм программы так, чтобы все интенсивно обрабатываемые блоки данных целиком умещались в сверхоперативной памяти первого или, на худой конец, второго уровня.
В противном случае обмен с оперативной памятью в мгновение ока "сожрет" все мегагерцы процессора. Но вот вопрос, — какой ииевяо зависимостью связан размер с производительностью? В частности; на сколько упадет быстродействие программы, если обрабатываемый блок данных "вылезет" за переделы кэш-памяти первого (второго) уровня, ну, скажем, на один килобайт? Еще вопрос: весь ли объем каша доступен для непосредственного использования или некоторую его часть необходимо резервировать для хранения стековых переменных, аргументов и адреса возврата из функции? Популярные руководства по оптимизации хранят "гробовое молчание" на этот счет, в основном ограничиваясь сухим правилом "кто не вместился в кэш — тот сам себе и виноват".
Даже такой авторитет, как Агнер Фог в свей монографии г(оы го орг(т)~е(ог Ие Репгшт (от(!у о) т(стзргосезэогэ' приводит всего лишь ориентировочное количество тактов различных иерархий памяти, требующихся для загрузки ячейки! Может быть, эта информация и полезна сама по себе, но она не гвг Глана 3 Лбефгпе ВиКК Етгк Ебееьпе Еткр Рйетак Ебеегпе Х 1715 К) // размер обрабатываемого блока памяти ~1*К~ // шаг приращения перебираемого размера // :'Ь' — тля вычитания линейной составляющей О ''1' — показывать график как есть // выявляем память р = ша11ос1ВЬОСК 51ЕЕ1 // шапка рггпвг~" †-'Г'Ч 1 Еог (Ь = 1*К; Ь < В1 ОСК 51ЕЕ; Ь Ь= ЕТЕР РАСТОЕ~ рг1пеео'Ъб1Г",Ь/км рггпвг~" 1п'Ч1 дает общего представления о картине.
Ведь "время доступа", как уже было показано (см. разд. Вычисление полного времени доступа" главы 2), — слишком абстрактное понятие, тесно переплетающееся с конвейером и параллелизмом. К тому же, Фог устарел и сегодня представляет разве что исторический интерес (во всяком случае — часть монографии, касающаяся времени доступа к памяти). Что ж! Ничего не остается, как "затовариться" пивом (или "Напитками из Черноголовки" — это уж кому как по вкусу) и плотно засесть за компьютер в надежде разобраться во всем самостоятельно. Давайте напишем следующую тестовую программу (листинг 3.1), обрабатывающую в цикле блоки все большего и большего размера, а затем выведем полученные результаты в виде графика на экран. (Полный исходный текст программы читатель найдет в файле 1егс',13).сас11е~сас(зе.ыге.с, который находится на прилагаемом компакт-лиске.) При этом булем исследовать четыре основных комбинации обработки данных: последовательное чтение, последовательная запись, чтение ячейки с последующей модификацией и запись ячейки с последующим чтением.
Конечно, не мешало бы исследовать еше и параллельную обработку (еле разд. "Параллельная обработка данных" главы 2), но — боюсь, — что в этом случае книга превысила бы все мыслимые размеры. Кэш рг1пет("Вчг")) тот (ь = 1*к) ь < вьсск втге( ь е= втер РАсток) ( Рвтнт Рксавевв(25*ь/в)лск Втге)) ччч) А ВЕЫН(О) Вот (с = О) с <= Ь) с += з1теот(тпт)) Гпр += *(1пе*)((1зт)р + с)) А ЕНО(0) рг1пет("ъбчг", 100*Ах ОЕТ(0)/х)) ) рг1птт("Хп")( /* рг1отт("нхг"); Тот (Ь - 1*К) Ь < ВГОСК втке) Ь +- Откр РАСТОВ) ( Рктнт РАООВ555(25+25*ь/вьсск 5155)( ччч) А ВЕСТЕ(1) йог (с = О) с <= Ь) с е= зтгеот(1пт)) (тпт*)((1пт)р е с) = Гпр) А ЕНО(1) рг1птт("Ъбхт", 100*Ах ОЕТ(1)/Х); рг1пгт("Хп")( ПОСНН((ОНАТЕЛЬНОЕ ЧТЕНИЕ попон ВИЗИСЬ рг1пгт("Вхчг")) тот (ь = 1*к) ь < Вьсск Втте) ь += 5тер ГАстск) ( Рктнт РВОБРВ55(50~25*ь/Вьсск втее)) ччч) А ВЕ515(2) тот (с = О) с <= Ь) с += 51геот(1пт)) тззр += * ртпт ) ((1пт)р + с) ) Глава 3 2о4 (епс") ((ппс)р е с) = ьгр1 ) А ЕКЬ(2) рсгппг('Иожо", 100*АХ СЕТ(2) /Х) ) р<1пег("3п")) Пссз)РДОНАТЕЛЬНОЕ ЧТЕНИЕ поппи Э)НТИСЬ Р11ПСК("НР'с")) 1ос (Ь = 1"К) Ь < БЬССК 512Е1 Ь е= 5ТЕР РАСТОА) РК1НТ РКООРЕББ(75+25*ЬКВЬССК Б12Е)) Ч))Ч; А 5501Н(3) гсс (С .= О) С <= Ь1 С += 511ЕО1(ЫЬ)) *(1пп*) (()пе)Р + с) = СИР1 Ьтр += "(Епп*)((1пп)р е с)) ) А ЕКО(3) Р<1п<1("ЪО'~С", 100 Ах ОЕТ(3)/Х)) ) рпппег ("1п" ) 1 Вид полученного графика может варьироваться в зависимости от архитектуры используемого процессора, но в целом должен выглядеть приблизительно так, как показано на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
