К. Касперски - Техника оптимизации программ, Эффективное использование памяти (1127752), страница 71
Текст из файла (страница 71)
Предвыборка отнюдь нс является оригинальным изобретением АМР н в мире нсперсональных компьютеров она достаточно широко распространена. Поскольку непосредственное управление кэшем не может осушествляться без учета характеристик подсистемы памяти с одной стороны, и архитектуры процессора с другой, то оно всегда аппаратно-зависимо. В мире "больших" компьютеров, конфигурации которых более или менее предсказуемы, подстройка оптимизации программы под конкретное оборудование — явление вполне нормальное. Кэш Но вот РС вЂ” дело другое, Оптимальная стратегия предвыборки зависит и от типа оперативной памяти, времени доступа к ней, ее латентности, характеристик чипсета, разрялности и тактовой частоты системной шины, частоты и архитектуры ядра процессора, политики кэширования, длины кэшлинеек, разрядности и частоты внутренней шины, латентности кэш-памяти.
Многообразие конфигураций персональных компьютеров приводит к тому, что программная предвыборка создает проблем больше, чем их решает. Создатели процессора Р-4 сделали большой шаг вперед, реализовав механизм аииаратной иредвыборки, или, иначе говоря, — усоверигенствованную стратегию уирезкдаюи(его считывания. До сих пор кэш-контроллеры всех бытовых микропроцессоров приступали к загрузке кэш-линейки лишь после явного обрагцения к ней, а предвидеть: какая линейка будет запрошена следующей, они не могли — интеллектуальности не хватало! Репгшш-4 не только осуществляет упреждающую загрузку последующих 256 байт (двух кэш-линеек) в кэш второго уровня, но и отслеживает регулярные шаблоны обращения к данным, что позволяет предугадывать, к каким кэш-линейкам в будущем произойдет обращение.
Алгоритм предсказаний недокументирован, но, тем не менее, суть его (по крайней мере, в общих чертах) понять несложно. Пусть, например, процессор фиксирует ряд кэш-промахов при обращении к линейкам г4, И+3,?4ч-б, Я+9. Не нужно быть ясновидящим, чтобы с высокой степенью достоверности предположить, что следующей на очереди стоит )ч+!2 линейка.
Таким образом, Р-4 умеет распознавать арифметическую прогрессию и вычислять ее члены. Насчет же распознавания геометрической прогрессии в документации ничего не сказано, а проверить экспериментально — под рукой процессора нет. Определить шаг арифметической прогрессии по нескольким ее элементам — это не проблема! Вот выделить прогрессию из произвольной последовательности — куда сложнее. Справляется ли с этим процессор Р-4? Нет! Его разработчики честно признаются в документации, что лаодоив оп?у оне вггеат рег 4К раве ~?оад ог вгоге)", Следовательно, в пределах одной страницы доступ к данным, обрабатываемым в цикле, должен происходить по одному регулярному шаблону, в противном случае механизм предсказаний "ослепнет" и аппаратная предвыборка осуществляться не будет.
Если же такая необходимость все же возникает (а практически она всегда возникает), обрабатываемые данные следует разбить на несколько блоков (числом не более восьми) и расположить их в различных 4-килобайтовых регионах. Восьми— потому, что процессор Р-4 умеет одновременно отслеживать не более восьми регулярных шаблонов (в терминологии разработчиков: лотоков данных— дага вггеат). Причем, упреждающая загрузка осуществляется только в пределах одного 4-килобайтового блока памяти — при выходе за его пределы механизм предсказаний дезактивируется и отслеживание шаблона обращений Глава 3 начинается сначала. Таким образом, процессор вновь дожидается нескольких кэш-промахов, определяет шаг прогрессии и только после этого приступает к очередному сеансу предвыборки.
Вследствие этого ячейки памяти, читаемые с большим шагом (порядка 1 Кбайт), никогда не предвыбираются и потому обрабатываются крайне неэффективно. Следовательно, аппаратная предвыборка не так уж и прозрачна для программистов, как убеждает фирма 1пге1. Да, в отличие от программной, аппаратная предвыборка ускоряет работу даже ничего не знающих о ней приложений, но максимальная эффективность достигается лишь при соответствующей организации структуры обрабатываемых данных.
Причем, далеко не во всех случаях такое структурирование выполнимо! Поэтому, при всем могуществе аппаратной предвыборки программная предвыборка не сдает своих позиций и на прцессоре Р-4 по-прежнему остается эффективнейшим средством оптимизации приложений. Эффективность предвыборки в многозадачных системах Процессы, исполняющиеся в многозадачных системах, владеют кэшпамятью не единолично, а вынуждены делить ее между собой.
Снижает ли это эффективность предвыборки? Эффективность предвыборки в кэш первого уровня — однозначно нет. Промежуток времени между переключением задач — это целая вечность для процессора, соответствующая, по меньшей мере, миллионам тактов. В любом случае, независимо от того, будет ли вытеснено содержимое Е1-кэша или нет, — предвыборка позволяет конвейеризовать загрузку ланных из памяти, предотвращая тем самым возможное падение производительности. С Е2-кэшем ситуация не так однозначна. Если оптимизируемый алгоритм позволяет распараллелить загрузку данных с их обработкой, то состояние Е2- кэша вообще не играет никакой роли, поскольку быстродействие программы ограничивается именно скоростью вычислений, а не пропускной способностью подсисгемы памяти (подробнее см. разд.
7)лавирование дистанции пред- выборки" этой главы). Однако если время обработки данных меньше времени их загрузки из основной памяти, падения производительности никак не избежать. Прелвыборка, конечно, увеличит производительность программы и в этом случае, но — увы — не на много, максимум в два-три раза. С другой стороны, одновременное выполнение двух или более приложений, интенсивно обменивающихся с памятью, на рабочих станциях случается очень редко (для серверов, правда, это — норма жизни).
В большинстве случаев пользователь активно работает лишь с одним приложением, другие же находятся в фоне и довольствуются минимальным количеством памяти, а порой и вовсе "спят", не трогая Е2-кэш и практически не снижая эффективности предвыборки. зе! Кэш Практическое использование предвыборки Если вычислительный алгоритм позволяет с той или иной вероятностью предсказать адрес следующей обрабатываемой ячейки, то это хороший кандидат на оптимизацию, причем выигрыш от использования предвыборки будет тем значительнее, чем точнее определяется адрес следующей обрабатываемой ячейки. В первую очередь это относится к циклам с постоянным шагом, геометрическим преобразованиям в 2!3/3!3-графике, операциям сортировки, копирования и инициализация памяти, строковым операциям и т.
д. В меньшей степени поддается оптимизации обработка списков и "двоичных деревьев". Поскольку порядок размещения их элементов заранее не известен и определяется исключительно в процессе прохода по списку (дереву), гарантированно определить адрес следующего обрабатываемого элемента в общем случае невозможно, Однако достаточно часто его удается угпдать. Например, можно предположить, что начало очередного элемента находится непосредственно за концом текущего.
Если список (двоичное дерево) не очень сильно фрагментирован, процент попаданий значительно превосходит количество промахов и предвыборка дает положительный эффект. Рассмотрим следующий пример (листинг 3.19). ((вагапа зтвр зтгв ш саснв здкв зггв гоп(а=о(а<вьсск згзв/ат=зтьр згаЮ // Делаем некоторые вычиоления (какие — не важна) )и (о, ьм // считываем очередную ячейку Ьт=р[о]/ Если обрабатываемый блок отсутствует в кэше первого и второго уровней, а шаг цикла равен или превышает размер кэш-линейки, то каждое обращение к памяти будет вызывать значительную задержку — порядка !Π— !2 тактов системной шины, требующихся на передачу запрашиваемых ячеек из медленной оперативной памяти в быстрый кэш.
На процессоре Р-П! 733 это составит более полусотни его тактов! В результате — время выполнения данного примера в большей степени зависит от быстродействия подсистемы памяти, и в меньшей — от тактовой частоты процессора. Однако поскольку адрес очередной обрабатываемой ячейки известен заранее, ланные можно загружать в кэш параллельно с выполнением вычисле- зег Глава 3 ний. Например, оптимизированный код под процессор Р-Ш в первом при- ближении будет выглядеть приблизительно так, как в листинге 3.20. №бегкпе ЕЕКР 51гК Ы СДСЯК ЫИК ШгК 1ог(а=01а<ВЬССК 512Е1ат=5ТЕР 512Е( // Даем команду на загрузку следухщей 32-байтовой строки // в Ы-кэш. Загрузка будет осуществляться параллельно // с выполнением функции Зп.
// Котла же соответствующая ячейка будет затребована, // она уже окажется в Ы-кеше, откуда процессор сможет // извлечь ее безо всяких задержек. р~екее~( ва(ремкткь Вккк(1 """"""" обратите внимание: в кэш // загружается ячейка, обрабатываемая не в текущей, а // следующей итерации цикла. Дело в том, что за время // выполнения функций Зп запрашиваемая кэш-линейка // просто не успевает загрузиться( О (подробнее см. разд. "планирование дистанции предвьборки" // этой главы) // Выполняем некоторые вычисления №п(с, Ы( // Считываем очередную ячейку // Во всех, кроме первой, итерациях цикла ячейка будет // гарантированно находиться в кэше первого уровня, // в результате время ее чтения сократится до 1 такта СРС Ь+=Р(С(1 На процессоре Р-1П 733/133/100 оптимизированный вариант выполняется быстрее на целых 66%, а на АМ(3 Аг(з!оп 1050/100/100 — на 60%, т.
е. предвыборка увеличивает производительность более чем в два раза! (рис. 3.39). И это при том, что в цикле выполняется лишь одно обращение к памяти за каждую итерацию. А чем больше происходит обращений к памяти — тем больший выигрыш дает оптимизация! Максимальный прирост производительности достигается в тех случаях, когда: П прелвыборка данных осуществляется в кэш-иерархию, соответствующую их назначению; П запрашиваемые данные загружаются в точности к моменту обращения; П осуществляется прелвыборка только тех данных, которым она действительно требуется (хотя ртететс⻠— неблокируемая инструкция и достаточно интеллектуальная для того, чтобы не загружать данные, уже находящиеся в каше, ее обработка достается "не бесплатно" и лишние вызовы снижают производительность).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
