К. Касперски - Техника оптимизации программ, Эффективное использование памяти (1127752), страница 72
Текст из файла (страница 72)
На процессоре Р-4 данный пример в оптимизации вообще не нуждается, т. к. процессор и сам, определив последовательность обращений к данным, осуществит их упреждающую загрузку самостоятельно. Инструкция программной предвыборки будет лишним балластом, лишь снижающим производительность системы (впрочем, не намного). Для переноса примера (см. листинг 3.20) на процессор Кб (тУ(А СЗ) достаточно лишь заменить инструкцию р гетсппта на ее ближайший аналог— ртегетсв. Рис. 3.39.
Эффективность программной предвыборки в оптимизации примера (см. листинг Згао) Глава 3 Определение предпочтительной кэш-иерархии Народная мудрость "подальше положишь — поближе возьмешь" в отношении предвыборки данных практически всегда неверна. Чем ближе к процессору в кэш-иерархии расположены данные, тем быстрее они могут быть получены. Следовательно, если уж и осуществлять предвыборку, то предпочтительнее всего в каше первого уровня (редкие исключения из этого правила будут рассмотрены далее).
Если данные используются многократно, то их предвыборку желательно осуществлять в кэш-уровни всех иерархий, — тогла при вытеснении из каша первого уровня данные за короткое время будут получены из каша второго уровня и процессору не придется обращаться к медленной оперативной памяти. Напротив, однократно используемые данные (равно как и данные, гарантированно не вытесняемые из каша первого уровня), загружать в кэш второго уровня нецелесообразно, особенно если в нем в это время хранится нечто полезное.
Сказанное в высшей степени справедливо для процессора Р-)П, но не совсем верно в отношении Р-4 (точнее, не верно совсем). Поскольку вместо загрузки данных в кэш первого уровня процессор Р-4 помешает их в первый банк кэша второго уровня, то особенной свободы выбора у программистов и нет. И единственное различие между командами р га«с««а и р га«а«еа заклк>чается в том, что р га«ала«а не может вытеснить из кэша второго уровня более одной восьмой обьема его данных. (А по закону "бугерброда" вытесняются именно те данные, которые вам нужнее всего.) На процессоре Кб (У)А СЗ) никаких проблем с определением предпочтительной кэш-иерархии нет, поскольку нет и самой возможности ее выбора, т.
к, данные всегда загружаются в кэш-уровни всех иерархий, вытесняя содержимое Е2-каша еще интенсивнее, чем на Р-4! Поэтому разработчики, оптимизирующие свои программы под Кб (У(А СЗ), не найдут в этом разделе лля себя ничего интересного. Но довольно теории, перейдем к конкретным примерам. Вернемся к листингу 3.20. Достаточно очевидно, что совершенно все равно: какой командой предвыборки пользоваться — р гаеаь «а или р га«а««е, поскольку к каждой ячейке обращение происходит лишь однократно, а в каше второго уровня не хранится никаких ценных данных, которые было бы жалко вытеснять.
(Впрочем, не стоит забывать, что в многозадачных операционных системах кэш приходится делить между несколькими приложениями и без острой надобности затирать его содержимое, право же, не стоит.) А вот команды р г~«с«т/р га«аь«г на процессоре Р-Ш покажут значительно Кзш 365 худший результат, даже отставая отнеоптимизированного варианта на 45% (рис.
3.40). На процессоре Р-4 все эти команды одинаково эффективны. Рис. 3.40. Сравнительная эффективность различных типов предвыборки А теперь рассмотрим другой случай, вообразив себе алгоритм, обрабатывающий в цикле два блока, один из которых — вьоскт — целиком помещается в кэш второго уровня, а другой — в оскз — значительно превосходит Ь2-кэш в размерах (листинг 3.21). Конечно, оба блока в Ь2-кэш все равно не втиснешь, но должно же там найтись место хотя бы для меньшего из них! Увы, ничего не получится. Процессор, пытаясь кэшировать все обрабатываемые ячейки, будет постоянно вытеснять данные блока вьоск из каша, замещая их ячейками блока вьоска, В результате, при следующей итерации цикла в каше не останется ни блока вьоскт, ни блока вьоскз и придется вновь ожидать их загрузки из медленной оперативной памяти.
Глава 3 зве Яффа '", .::~а':..„'в'"'((а)м~~~ь,„-'!"!ь';~, ь„'.".'!'.; Гос(.. Л // цикл, испопняюшийся по крайней мере несколько раз гос( -О(с<в.сск2 вькк(с+=вткв вткк( // Обрабатьшаем блок ВЬОСК1 // Поскольку он обрабатывается в цикле (имеется в виду цикл Гот (.. Л(, желательно, // чтобы шшто ке вытесняло ето из Ь2-коша. ьа=р1[б(( 11 ((ба=32( > Вьсск1 в1ек( с=0( // Аелаем некоторые вычисления Ь(=Ь ь (са1(ь // Обрабатываем блок ВЬОСН2. // этот блок значительно превосходит Ь2-кэш в размерах, // поэтому кэшировать ело абсолютно не обязательно // все равно при последуььеих итерациях цикла // нужньш данных в «эше не окажатся... // К тому же в кеше уже содержится ВЬССК1, '/ вытеснять который нежелательно. Но, увы! // Процессор в порядке собственной инициативы // помешает данные блока Вьосх2 в ь2.кэш, // выбирая самую неоптимальную стратешпо кэширования... Ь~=р2(с(( Возможно ли, не очень усложнив алгоритм, как-нибудь уменьшить количество кэш-промахов, увеличивая тем самым производительность? Конечно же, да! Но только ие для лроцессора Кб ('кл/а СЗ).
Достаточно лишь воспользоваться командой предвыборки невременных данных, "убивая одним выстрелом двух зайцев наповал". Во-первых, предвыборка избавляет нас от ожидания загрузки ячеек блока вьсск2, а, во-вторых, она позволяет подгружать блок вьсск2 напрямую в кэш первого уровня (на Р-4 в первый банк кэша второго уровня), не затирая содержимого блока вьоск1, храняшегося в (.2-кэше. (На Р-4 — увы — блок вьоск1 все же будет частично затираться). Следовательно, в данном случае выгоднее всего воспользоваться инструкцией рсегессгюса, а не рсегессьсх, поскольку она не затирает (на Р-4 милий(ально затирает) кэш второго уровня (листинг 3.22).
Кэш аи1':,Ф:иР1))9Щ)ах)иь"В14ие~~1~ЙУ)14)бой))~~ф;;..'-:-1 год н ..) Гог)с=б;с<ВПОСК2 ВТВВ/с =Втер ЗТВВ) // Обрабатываем блок ВЬОСК1 )находявввтся в Ь2-кеше). // Предвыборка в '1-кэш не нужна, т, к. это все равно // не увештвит производительности, ввиду того, что на // Р-111 время доступа к кэшу второго уровня // пренебрежительно ыало, а Р-4 и вовсе не позволяет // грузить данные в кэш первого уровня Ь+=р1 Щ; Г Ыб+=Зг) > ВЬЗСК1 Зггв) б=б; // Перед тем как заняться вычисленишчи, отдаем команду на // предвыборку данных блока ВП1СК2 в Ы-кэш )в 12 на Р-4) // Во-первьш, избавляясь тем самыч от ожидания загрузки // данных из медленной оперативной памяти, а во-вторых, // предотвраюая вытеснение данных блока В12 ск1 из ь2-кэпа р .еееьсьпьа(рг+с+Втвг ВТВВ); // Обратите внимание, что загружаются данные, обрашение // к которым произойдет только в следуюшей итерации.
// Почему именно так> Дело в том, что время загрузки // превышает время вычисления "Ь+=Ь Ъ )сь1)" и... // Загружая данные следуюией итерации, мы теряем лишь // первую итерацию цикла, а не через одну, // как может показаться вначале, т. к. этот прием вполне Ц законен и обеспечивает максимальный прирост О быстродействия.
Ь+=Ь 4 ) +Ы) // Теперь данные загружаются иэ Ы-кеша) )из П2 на Р-4) Ьь=р2)с)) На процессоре Р-1Н использование инструкции р гессь са на 40% увелиЧнааЕт ПрОИЗВОдИтЕЛЬНОСтЬ, В тО ВрЕМя КаК р гегсьво — На 20% уМЕНЬШаЕт ее, что и не удивительно, т. к. прелвыборка временных данных приводит к вытеснению из кзша второго уровня содержимого блока вьоск1, ничего не давая взамен (рис.
3.41). Глава 3 Рис. 3.41. Влияние различных типов првлвыборки нв производительность различных приложений Планирование дистанции предвыборки Поскольку оперативная память — устройство медленное, загрузка кэшлинеек — дело долгое. Соответственно, предвыборку необходимо выполнять заблаговременно, с таким расчетом, чтобы, когда дойдет очередь до обрабатываемых данных, то они уже находились бы в кэше. При линейной обработке данных добиться этого очень просто, вот циклы— дело другое. Как быть, если время загрузки данных превышает продолжительность одной итерации? В примерах, приведенных ранее, проблема решалась предвыборкой данных, обрабатываемых в следующей итерации цикла. Обратите внимание — именно следующей итерации, а не через одну итерацию. Поэтому лишь при первом проходе цикл исполняется неэффективно, а все последующие идут "на ура".
Как же это получается?! Ведь если предвыборка успевает загружать данные за время выполнения предыдущей итерации, продолжительность загрузки не превышает продолжительности одной итерации, а раз так, то зачем вообще Кэш потребовался этот сдвиг, ведь по идее данные должны успевать загружаться в течение текущего прохола цикла? Ответ на вопрос кроется в механизме взаимолействия ядра процессора с подсистемой памяти. Подробно он рассматривался в главе 2 настоягцей книги (сгс разд. "Взоцмодейспгвие пазгяти и процессора" главы 2), здесь же напомним читателю лишь основные моменты. В первую очередь нас будет интересовать поведение процессора при чтении ячеек памяти, отсутствующих в кэш-памяти обоих уровней.
Убедившись, что ни в Е1-, ни в Е2-кэше требуемой ячейки нет (и израсходовав на это один такт), процессор принимает решение получить недостающие данные из оперативной памяти. Выставив на адресную шину адрес ячейки процессор, ценой еще нескольких тактов, передает его контроллеру памяти. Затем чипсет вычисляет номер столбца и номер строки ячейки, и определяет: открыта ли соответствующая страница памяти или нет? Если страница действительно открыта, чипсет выставляет сигнал САВ и спустя 2 — 3 такта (в зависимости от величины задержки САЯ, обусловленной качеством микросхемы памяти) на шине появляются долгожланные данные. (Если же требуемая строка закрыта, но максимально допустимое количество одновременно открытых строк еше нс достигнуто, чипсет посылает микросхеме памяти сигнал ЙАЯ вместе с адресом строки и дает ей 2 — 3 такта на его "переваривание", затем посылается сигнал САЯ и все происходит по сценарию, описанному выше, в противном случае приходится терять еще такт на закрытие одной из страниц.) Контроллер памяти "проглатывает" первую порцию данных за один такт и с началом следующего такта передает ее уже "заждавшемуся" процессору, параллельно с этим получая из микросхемы памяти вторую.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
