К. Касперски - Техника оптимизации программ, Эффективное использование памяти (1127752), страница 64
Текст из файла (страница 64)
А ведь обрабатываемых ячеек памяти всего лишь пять. Во избежание падения производительности обрабатываемые данные необходимо реорганизовать так, чтобы читаемые ячейки попадали в различные кэш-линии, и если это невозможно, то обрабатывать их не в одном, а в нескольких последовательных циклах, например, так (листинг 3.8).
гоа[а = о; а < чоочом а++[ а[=ьаг [4096[; аг=ьаа[аозо*гм Глава 3 згг аЗ Ьаг14096*31; // бог!а = О! а < чоочом ага! 1 а4=Ьаг14096*41; а5=Ьаг14096*51; // ... А теперь разберем как будет исполняться следуюший код !листинг 3.9) на процессоре АМР А1)4!оп, На первый взгляд, все произойдет по сценарию, описанному выше, с той лишь разницей, что двухассоциативный кэш процессора АЙ!оп "завалится" уже на третьей итерации. Точнее, мы думаем, что он "завалится", а на самом же деле, никакого сколь- нибудь заметного падения производительности не наблюдается. Гог1а = 0; а < чоочо'; ааа1 ат а= Ьа<140961; а2 += Ьа<14096*21; аЗ а= Ьаг14096*З1: а4 а= Ьаг14096*414 а5 а= Ьаг[4096*51; Первое впечатление — вот зто номер! Ай да Ай!оп! Второе впечатление (немного остынув от восторга, мы задаемся известным вопросом) — но почему? Как это реализовано? Прочитав руководство по оптимизации от начала до конца, в приложении "А" мы находим междустрочный ответ на вопрос.
Оказывается в процессорах АМО АФ!оп имеется очередь чтения/записи на 12 входов, которая временно сохраняет данные, считанные из каша первого уровня. Конфликты кэш-линий все-таки возникают, но они маскируются системой буферизации данных. Выходит, что при оптимизации программы исключительно под А!Ион нехватки ассоциативности можно не опасаться? Увы, не все так радужно, В данном случае падения производительности не наблюдается лишь только потому, что количество одновременно обрабатываемых ячеек не превышает двенадцати.
Особенно щепетильным следует быть при выборе величины шага чтения при обработке блочных алгоритмов. Если она окажется кратной размеру кзш-банка (или хотя бы производной от него), то многократного падения производительности не избежать. Рассмотрим следующий пример (листинг 3.10). (Полный исходный текст программы читатель найдет в файле ~згс'ДЗ).сас)зе~).1.очегаввос.с, который находится на прилагаемом компакт-диске.) Ебеттпе И ттва 466 // кол-во итераций // теоретически будет востребовано 4беттпе САСНЕ ВАИК 51КЕ ~4*К Абет1пе ЫИЕ Втгв Кбетапе ВЬОСК Втгв ~~САСНЕ вАИК Втгвавьсв Втгв~*и 11ЕА> // размер блока */ 1пс очес аваос Гьпт *р~ тпс а; чо1атс1е тлС к=01 // внимание: сор-3.ече1 цикл пропущен, поскольку профайлер // и без того прокрутит этот цикл 10 раз тос(а=04 а // // // // // // ЫИЕ Втгв*И ттЕА байт кэш-памяти, // т.е.
в данном случае 466*64 -30 Кбайт ) // размер кэш-банка 64 // максимально возможный размер кэш †лин < и ттевг аь+~ читаем память с шагам 4 Кбайт, в результате и на Р-11/Р-111/Р-4 и на АМО АСА1оп быстро наступает насышение каша и идет его перегруз; поскольку обрабатывается более 12 ячеек, буферизация чтения на АСЬтоп положения Згн Глава 3 // уше не спасает хе=* свит *4 ~~1пт1р + а*Слоне ВВНК Шгнм етытп х; При шаге чтения, равном 4 Кбайт, данная программа будет "буксовать" на всех процессорах, поскольку в кэш-память не поместится вообще ни одной ячейки! (Чу! Слышу голоса: "Почему ни одной ячейки? Ведь должны же сохраниться четыре ячейки на процессоре Р-П/Р-П1 и две — на Аг)4!оп, в соответствии с величиной их ассоциативности".
Увы! При очередном проходе цикла последние сохраненные ячейки будут выкинуты из каша.) Как можно предотвратить кэш-конфликты? Для этого мы должны реструктурировать обрабатываемый массив с таким расчетом, чтобы установочные адреса всех загружаемых ячеек были бы различны. Один из возможных путей решения — увеличить величину шага на размер кэш-линейки. (Конечно, для этого необходимо изменить и сам массив, т. к. при этом будут читаться уже другие данные.) Оптимизированный пример может выглядеть приблизительно так, как показано в листинге 3.11. (Полный исходный текст программы читатель найдет в файле 16гс~[3).сасове~(.1.оуегаввос.с, который находится на прилагаемом компакт-диске.) вввнвнт, исволнвхиийся ввз конелнктов 1пп арп1хд.хе Свят *р1 1пт а 0; чо1ать1е 1пт х=О; // внимание: тор-1ече1 цикл пропущен, поскольку провайдер // и беэ тато прокрутит этот цикл 10 рач гот(а=04 а < и 1тввг аты О читаем пять с шагом свснв ввнк втгв+шнв вггв, // т.
е. в данном случае 4096 т 64 = 4160 байт; Кэш Згб // поскольку установочные адреса всех ячеек различны, // мы не имеем конфликтов и используем емкость // кзв-памяти на все 100$ х~=*(1пт м ((1пмр + а" (сксне ВАЕК Б1ееьыне Бтзе( ы тетотп х; Прогон программы показывает, что в результате оптимизации ее скорость увеличилась более, чем в ввесть раз на процессоре Р-П! 733 и более чем в лягпь раз на процессоре АМ!3 Ай!оп 1050 (рис. 3.31).
Согласитесь, очень неплохая прибавка к производительности и зто при том, что мы только читали конфликтуюгцие ячейки, но не модифицировали их. Конфликт же записи обойлется вам приблизительно в полтора раза "дороже"! Рис. 3.31. Демонстрация падения производительности при попадании загружаемых данных в одну и ту же кзш-линейку, Конфликт записи обходится приблизительно в полтора раза дороже Глава 3 Поэтому, если ваша нрограмма несмотря на крошечный размер обрабаты- ваемых данньи4 работает на удивление медленно, — в первую очередь иро- верьте — не замешан ли здесь кон!рликт кэ1и-линеек. Особенности обработки двумерных массивов Фбегзпе Н ВОИ Фаееьпе И СОЬ ~ 512,' !512! О неоптимальное кол-во строк матр.
О поскольку оно кратно размеру уу кзш-банка и кзш используется у/ не полностьш Техника параллельной загрузки данных (подробно рассмотренная в гл. 2 настоящей книги) — весьма эффективный способ отправить свою программу на "кладбище". Подсистема памяти не так проста, как кажется, и один неосторожный шаг способен свести всю оптимизацию к нулю.
Но довольно лирики! Переходим к делу. Допустим, у нас имеется очень большой двухмерный массив, сумму ячеек которого и требуется подсчитать. Для определенности возьмем матрицу 512к512, состоящую из переменных типа ы Двухмерность массива порождает буриданову проблему: как вести подсчет — по строкам или по столбцам? Подсчет по строкам фактически сводится к последовательному чтению памяти, а это (как мы помним) далеко не лучший способ обработки данных. Куда заманчивее читать массив по столбцам.
Если ширина матрицы превышаег длину пакетного цикла обмена, запросы к памяти генерируются при каждом кзш-промахе (см. раэд. Параллельная обработка данных" главы 2). Единственное условие — это произведение столбцов на размер кзш-линии не должно превышать емкости кзш-памяти первого уровня. Соблюдается ли это условие в данном случае? На первый взгляд как будто бы соблюдается. Смотрите: на Р-П1 размер кзш-линеек составляет 32 байт, а размер кэш-памяти первого уровня — 16 Кбайт.
В то же время: 512*32 = = 16 384. Совпадают ли цифры? Совпадают! Хорошо, возьмем, например, процессор АМП А!Ыоп, имеющий кзш-память 64 Кбайт при длине линеек в 64 байта. Умножаем 512 на 64 — получаем 32 Кбайт, что с лихвой должно вместиться в кэш. Но вместится ли? Сейчас проверим! Запустим на выполнение следующий пример (листинг 3.12). (Полный исходный текст программы читатель найдет в файле 1,втсп[3!.сасйе1,со1цшп.Ь!8.с, который находится на прилагаемом компакт-диске.) 327 Кэш послвяоватавьвая оввавоп(а массива по столвцам */ . г гсй соь('.
г (*гоп) [к соь) ) ( гпг х, у; гпГ г - О( бог (х О;х < Н ИИ( х-н-) ( Гог (у О," у < и СОЫ ут+) г т Гоо[х) (у): гесогп г: псслвдоватвпып(я (жвавстка массива по строкам */ гпГ Гсй НСН(тпт (*Гоп) [В СО(.) ) ( тпг х, у) Гпс г-О! Гог (х = О; х < я СО(м х++) // внимание: если высота матрипы кратна размеру // кзм-банка, то вследствии ограниченной ассоанитивности // каза его звфективная емкость значительно снизится // и кзз-памяти может попросту // не хватить, что приведет к постоянньаа промахам! бог (у О; у < Н Лск( у++) г е= гоп[у)[х); гегогп г; Да как бы не так! Мы совсем забыли про ассоциативность — поскольку адреса читаемых ячеек кратны 4096, то всего лишь четыре ячейки могут одновременно находиться в кэше, но никак не 1024! Даже емкости кэша второго уровня Глава 3 ЗгВ для этих целей окажется недостаточно! Допустим, мы имеем четырех- ассоциативный 1.2-кэш емкостью в 128 Кбайт.
Каждый его банк способен хранить сасне.зтзвунхтузтвн.зтзв - тзт.очггчгчоэь — зг таких ячеек. Следовательно, четыре банка разместят 32*4 = 128 ячеек. А у нас их аж 1024! Сверхоперативная память будет крутиться полностью "вхолостую", а величина кэш-промахов достигнет даже не 100%, а 800% на процессорах Р-П/РП1 и 1600% на АМ13 А11ч1оп (рис. 3.32)! Действительно, ведь в силу пакетного обмена, кэш-строки заполняются целиком, но только мачая их часть оказывается реально востребована! В результате, данный код будет исполняться очень медленно. Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
