К. Касперски - Техника оптимизации программ, Эффективное использование памяти (1127752), страница 63
Текст из файла (страница 63)
"Буферы записи" згпои алвеы. С лругой стороны: такое выравнивание приводит к "разрыхлению" упаковки данных и требует значительно большего количества памяти, в результате чего вполне может сажаться так, что данные просто не поместятся в кэшпамяти первого (а то и второго) уровня. Тем самым мы рискуем вместо Глава 3 З7Е ожидаемого увеличения скорости нарваться на большие "тормоза", "съедаю- шиеь весь выигрыш параллельной обработки! Насколько значительными будут последствия конфликта кэш-банков? А вот сейчас и увидим! Чтобы выяснить это, мы напишем программу (листинг 3.6), учитывая при ее разработке следующие обстоятельства: С3 на процессоре Р-Ш конфликт кэш-банков приводит к падению производительности только в случае комбинирования операций чтения с операциями записи (т.
е. на Р-П1 всего одно устройство чтения, загрузить две ячейки за такт даже из двух различных банков он, увы, не сможет); О //- НЕТ КОНФЛНКТОВ // Распределение перемеииьш по кэш-баикам иа Р-111 О !<ЬапхО>)<Ьап11» <Ьапх2>'<ЬапХЗ>!<Ьап14>!<Ьап15>!<Ьап26>)<Ьап27>' // )О 1 2 3!4 5 б 7!8 9 0 1!2 3 4 5!б 7 8 9!О 1 2 3!4 5 б 7)8 9 0 1!<- огГаес // ~*-*-*- « — ! )1пь) р32 . « — )! Ь)р32- ! « — Ы1пс) р32 е ! « — ))апо) р32 а ь 0); а ь 4)! а 412); а +16)) // ! О ! ~* * * *~ ~*-* *-*~ ~*-*-*-*~ // Распределение перемеииьл по кэш-баикам иа АМО АоЬ1оп // )< — Ь Х О вЂ >)< — Ь Х 1 †>)< — Ьапх 2 †>)< — ЬапХ З вЂ >! // )О 1 2 3 4 5 б 7 В 9 0 1 2 3 4 5 б 7 8 9 0 1 2 3 4 5 6 7 В 9 О 1 « — ))1пс) р32 + а + 2)) // '*-*-*-* ('.3 цикл обработки памяти лолжен быть развернут минимум на четыре итерации, т.
к. в противном случае буферизация записи позволит переждать задержки, вызванные конфликтом банков, и отложить выгрузку данных "до лучших времен", а единственной инструкции записи просто будет не с чем спариваться! (Полный исходный текст программы (листинг 3.6) читатель найдет в файле ))Вгс',[3].сас!1е')Ьап)45.0, который нахолится на прилагаемом компакт-диске.) Хорошо! Давайте же вызовем джина из бутьшки. "Ало„джин ибн Конфликт Кэш-Банков — появись!" Как вы думаете, он появится? Кэш // // ! // ! . « — (( О) р32 « а + 6)) ! « — ((спс) р32 + а «-12); ! « — ((спо) р32 + а «16)с * * *! 1* * * * ороТК1са(спо * р32) ! упс а) 1пс онр32 = О) атос(а = О) а < 81ОСК 8128) а += 32) Спр32 += *(спо *) ((1по) р32 «а + О)! // Ьапв О (ВОЬ1опс Ьапв О) *(сп *) ((1пс) р32 + а +12) = сзр32) // Ьап1 3 (АОЬ1опс Ьап)с 1) ОКР32 = *(ап» *) ((У Ь) Р32 + а + 4)) // Ьап1 1 (АОЬ1оп: Ьап)с 0) *(апо *) ((1пс) о32 « а +16) = пар32; // ЬапЕ 4 (ВСЬЬоп: ЬапЕ 2) // //" ЛемонстрзЦия кОнФликту БанкОВ // Распрелеление пе)семенник по кзн-банхан на Р-111 // ! ЪапКО>!«Эзп3с1>)<Ьап3с2>)<Ьап3св>!«Эсап3сА>!«Ьапх5>!«Эсаплб>)<ЬапК7>! // !О 1 2 3!4 5 6 7(В 9 0 1!2 3 4 5)6 7 8 9)0 1 2 3)4 5 б 7! 8 9 0 1 <- оРРаес // ! -+-+-+-+-+-+-+- ! -+-+-+-+-+-+-+-! -+-+-+-+-+-+-+-! -+-+-+-+-+-+ — !— // ! * * * * с с * *-*-* с с* — * — * — *с с* — * — « — *с с) с ! ! ! <- КОНФЛИКТ // Распределение переменных по кзк-банкаи на лип АУЭс3.оп // )< — Ьап)с 0 — >!< — Ьап)с 1 — >!< — Ьап1с 2 — >!< — Ьао)с Э вЂ” >! // !О 1 2 3 4 5 б 7!8 9 0 1 2 3 4 5 б 7 8 9 0 1 2 3 4 5 б 7 В 9 0 1 // ! -+-+-+-+-+-+-+- ! -+-+-+-+-+-+-+-! -+-+-+-+-+-+-+-! -+-+-+-+-+-+-+-+ // ! // ! // ! // // // ! «"- ((1па) р32 + а + 2! ! « — ((1пс) р32 + а + 6) ! « — ((1пс) р32 + а +12) « — ((1по) р32 + а +16) з(в Глава 3 // ! * *-*-* ! « — ((1пг) р32 + а + 2) > ! « — ((1пс) р32 + а + б); ! « — ((гпс) р32 + а +12)> « — ((1пс) р32 + а +16) > // ! // ' 1* * * * // ! // ! // // оопб11<С(гпг * р32) апс а> 1пС Спр32 = 0> бог(а = О) а < Вьсск Б12е> а += 32> ( Сар32 + *(апг *)((гпг) р32+а+2» О Ьапх 0 + 1 (АСЬ1оп: Ьапх О] *(1пг *)((зпС) р32<аа12) = Спр32> // Ьапх 3 * (АСЬ1оп: Ьапх 1) // "*" МАпк ВАюкб ссвгь1ст // * Спр32 а= (гпг *>((АВС) р32+а+б» // Ьапа 1 + 2 (АСЬ1оп: Ьапх С + 1) * (1ПС *) ((АПС) р32+а+1б) Сар32> // Ьапх 4 [Агезоп: Ьапх 2) ) На процессоре Р-1П "джин" появляется, да еще какой джин (рис.
3.30)! Чтением двух смежных 32-разрядных ячеек, смешенных относительно начала первого банка на 16 бит, мы вызвали более чем трехкратное падение производительности, что и неудивительно, т. к. в этом случае чтение двух ячеек ПРОИСХОДИТ НЕ За даа ТВКТВ, КВК ЭТО ДОЛЖНО бЫТЬ, а За 2 + рапа1гу ТВКТОВ. Поскольку на процессоре Р-Ш величина пенальти составляет пять тактов, 2 с5 мы проигрываем 100% * = 350%, что очень близко к эксперименталь- 2 ному значению — 320% (завышенная оценка объясняется тем, что мы не учли накладных расходов на запись и организацию цикла). На процессоре АМР А(1)!оп последствия конфликта кэш-банков оказались гораздо меньшими, всего на 9% увеличив время выполнения программы.
Рис. З.ЗО. Демонстрация конфликта каш-банков на процессорах Рси! и Амп Апаол Такое преимущество над Р-111 объясняется тем, что благодаря двойному превосходству в ширине кэш-банков мы перекрыли всего лишь два из них и вместо полного затора (как на Р-1П) на Ай!оп образовалась лишь маленькая, быстро рассасываюшаяся пробка.
Разумеется, это отнюдь не означает, что на процессоре АМР Ай!оп вызвать затор невозможно, — возможно, и еше как! Достаточно добиться перекрытия сразу нескольких банков, но для этого понадобится совсем другая программа, которая окажется непригодной для тестирования процессора Р-111. Тем не менее, вероятность спонтанного конфликта кэш-банков на АМР Ай!оп все-таки ниже. Выравнивание команд Выравнивание команд выходит за рамки данной книги и будет полробно рас- смотрено в следующей книге настоящей серии, посвяшенной процессору. Глава 3 320 Учет ограниченной ассоциативности каша До тех пор, пока в процессорах не появятся полностью ассоциативные кэши, оптимальная организация данных останется прерогативой программистов. В разд.
"Оргоназоцоя кэшо" этой главы было показано, что каждая ячейка кэшируемой памяти может претендовать не на л(обую, а всего лишь на несколько кэш-строк, число которых и определяется ассоциативностью кэша. Поскольку ассоциативность кэш-памяти первого уровня обычно очень невелика (так, на Р-П/Р-111 она равна четырем, а на АМг) Агй!оп и вовсе двум), становится очевидным. что неудачная организация данных способна сократить размер кэш-памяти на один-два порядка, а то и более того! Если установочные биты кэшируемых ячеек равны, то они отображаются на одну и ту же кэш-строку, поэтому таких ситуаций следует избегать. Как вычисляются установочные адреса? Для этого можно воспользоваться следующей формулой: зе1.аддгеза = пэу.аддгеза к ((пэаз)4.Ьап)4 — 1) бг (пэаз!4.1!пе— — 1)), где гпаа)4.!!пе (маска кэш-линий) определяется как: 2агааг "аа = САСНЕ.Ы!ЧЕ В)ХЕ, а пэаз)(.Ьап!4 (маска банка) — как: 2а1аах ьаах == == ВА?г(К.В!ХЕ.
В частности, 4-ассоциативный !б-килобайтовый кэш процессоров Р-П/Р-111 задействует под установочные адреса биты с 11 по 4 линейного адреса памяти. Таким образом, обработка ячеек памяти с шагом, равньам или кратньни размеру кэш-банка, крайне непроизводительно и этого зюбой ценой следует избегать.
Что касательно размера кэш-банков, то позвольте поделиться наблюдением: на всех известных мне процессорах он равен или кратен 4 Кбайт. Эта цифра, конечно, не догма, но как рабочий вариант вполне сойдет. А теперь скажите, как вы думаете, можно ли назвать следующий код (листинг 3.7) оптимальным кодом? :"4114щйигГ(4 У.".Г!ри(Млеем де44аногтрнгруЮщИ(!.,КОНФЛйхт?иоьщуМйевиг(4 ~~44Вт:„,'~,:,"",„'".","".
';:" ' в).рвгиичвйнай-стер Гог(а — 0; а < эооэо1г а+~( ( // а1 а= Ьаг(4096*1(; а2 += Ьаг(4096"2Ы аз э= Ьаг(4096*9(г а4 += Ьаг(4096*4(: а5 а= Ьаг(4096*5(: // Кэш 321 Увы, оптимальности здесь и близко нет. Смотрите, что происходит при исполнении программы процессорами Р-П/Р-Ш: в первом проходе цикла г = ячейки ь [аозо[ еше не содержится в сверхоперативной памяти первого уровня и возникает задержка в два-четыре такта на время загрузки данных из каша второго уровня (а в худшем случае — из оперативной памяти). Поскольку установочный адрес ячейки равен нулю (условимся считать, что массив ь выровнен по 4-килобайтовой границе, хотя это и не критично), кэш-контроллер помещает считанные 32 байта в нулевую кэш-строку первого (точнее, условного первого) кэш-банка.
Идем далее. Установочный адрес ячейки ьаа[аозо"г[ тоже равен нулю и очередная порция считанных данных также претендует на нулевую кэш-строку! Поскольку нулевая строка первого кэш-банка уже занята, кэш-контроллер задействует второй банк. Но ведь количество кэш-банков не безгранично! Напротив — оно очень мало, и на момент чтения пятой по счету ячейки — ьаа[аоэо*з! — нулевые кэш-строки всех четырех кэш-банков уже заняты, а данная ячейка претендует именно на нулевую кэш-строку! Кэш-контроллер (а что ему еше остается делать?) безжалостно ликвидирует наиболее "дряхлую" нулевую строку первого кэш-банка (к ней дольше всего не было обращения) и записывает в нее "свежие" данные. Как следствие — в следующем проходе цикла: ячейки ь [аооо[ вновь не оказывается в сверхоперативной памяти первого уровня и вновь возникнет задержка на время ее загрузки! Кэш-контроллер, обнаружив, что свободных банков совсем нет, ликвидирует нулевую строку, но теперь уже второго банка — ту, что хранила ячейку ь а[аозо*г! Чувствуете, что происходит? Правильно, кэш работает на !00% "вхолостую", не обеспечивая ни одного кэшпопадания — одни лишь промахи.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
