А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 178
Текст из файла (страница 178)
Однако иногда полезным может оказаться и перемещение, которое требует добавления компенсирующего кода. Один из вариантов поддержки такого перемещения кода состоит в следовании планированию на основе областей с простым проходом. При выполнении этого прохода можно просмотреть все пары базовых блоков, выполняющиеся один за другим, и проверить, нельзя ли переместить какую-либо операцию между ними для снижения общего времени выполнения этих базовых блоков.
Если такая пара найдена, то следует проверить, не надо ли продублировать перемещаемую команду на других путях. Перемещение выполняется, если оно дает чистый выигрыш времени выполнения. Такое простое расширение алгоритма может оказаться достаточно эффективным для повышения производительности циклов. Например, оно может переместить операцию в начале одной итерации в конец предыдущей, а операцию из первой итерации вынести за пределы цикла.
Такая оптимизация особенно привлекательна для небольших циклов, итерации которых состоят всего лишь из нескольких команд. Однако возможности этого метода ограничены тем фактом, что каждое решение о перемещении кода принимается локально и независимо от других. 874 Глава 1О. Параллелизм иа уровне команд аког (г = 0; з.+4 < М; з.+=4) Я(1); Я(з+1); Я(з.+2); Я(з.+3) 1 ) аког ( з з. < Из з.++) ( Я ( з. ); а) Развертка цикла Гог гереас ( Я; гй (С) Ьгеа)<г Я; гй (С) Ьгеа1с; Я; гй (С) Ъгеакз цпсг1 С; б) Развертка цикла гереа( Рис. 10.16.
Развертка циклов 10.4.6 Усовершенствованные методы перемещения кода Если наша целевая машина статически планируема и обладает высоким параллелизмом на уровне команд, то может потребоваться более агрессивный алгоритм. Вот высокоуровневое описание дальнейших усовершенствований алгоритма. 1. Для упрощения рассматривающихся ниже расширений можно добавить новые базовые блоки вдоль ребер потока управления, исходящих из блоков с более чем одним предшественником. Эти базовые блоки будут устранены в конце планирования кода, если окажутся пустыми. Одна из полезных эвристик состоит в перемещении команд из почти пустых базовых блоков, чтобы затем полностью устранить такой блок.
2. В алгоритме 10.11 код, который будет выполняться в каждом базовом блоке, планируется раз и навсегда при посещении блока. Такого простого подхода достаточно, поскольку алгоритм может перемещать операции только вверх в доминирующие блоки. Чтобы разрешить перемещения, которые требуют 875 10.4.
Глобальное планирование кода добавления компенсирующего кода, используется несколько иной подход. При посещении базового блока В мы планируем только команды этого блока В и блоков, эквивалентных ему с точки зрения управления. Мы сначала пытаемся разместить эти команды в предшествующих блоках, которые уже были посещены и для которых уже существуют частичные планы. Мы пытаемся найти целевой блок, который может привести к улучшению часто выполняемого пуги, а затем помещаем копии команды на других путях для обеспечения корректности программы. Если команда не может быть перемещена вверх, она, как и ранее, планируется в текущем базовом блоке.
3. Реализация нисходящего перемещения кода в алгоритме, который посещает базовые блоки в топологическом порядке, оказывается более сложной, поскольку целевые блоки при этом еще не спланированы. Однако все равно имеется несколько возможностей и для такого перемещения кода. Итак, мы перемещаем все операции, которые а) могут быть перемещены; б) не могут быть выполнены бесплатно в их исходных блоках.
Такая простая стратегия хорошо работает на целевых машинах с большим количеством неиспользуемых аппаратных ресурсов. 10.4.7 Взаимодействие с динамическими планировщиками Динамический планировщик обладает тем преимуществом, что он может создавать новые планы в зависимости от условий времени выполнения, не рассматривая заблаговременно все возможные планы.
Если целевая машина оснащена динамическим планировщиком, основная функция статического планировщика заключается в обеспечении ранней выборки команд с большими задержками, чтобы динамический планировщик мог выполнить их как можно раньше. Промахи кэша представляют собой класс непредсказуемых событий, которые могут привести к большим разбросам производительности программы.
Если доступны команды предвыборки данных, статический планировщик может существенно помочь динамическому, размещая эти команды как можно раньше, чтобы к тому моменту, когда потребуются некоторые данные, они уже были в кэше. Если же такие команды у целевой машины недоступны, то неплохо, если компилятор в состоянии оценить, какие данные вызовут промахи кэша, и попытается загрузить их как можно ранее. Если целевая машина не оснащена динамическим планировщиком, статический планировщик должен быть консервативен и разделять все пары команд 876 Глава !О. Параллелизм на уровне команд с зависимостями данных минимальной задержкой. Однако при наличии динамического планировщика от компилятора требуется только разместить зависимые по данным операции в правильном порядке, чтобы гарантировать корректность программы.
Для достижения наилучшей производительности компилятор должен назначать большие задержки наиболее вероятным зависимостям и небольшие— маловероятным. Важной причиной потери производительности является неверное предсказание ветвлений. В связи с этим наивысший приоритет при планировании должен назначаться командам, которые позволяют снизить стоимость неверного предсказания ветвления. 10.4е8 Упражнения к разделу 10.4 Упражнение 10.4.1. Покажите, каким образом можно развернуть обобщенный цикл зн)з!1е: мМ.1е (С) Я!.
Упражнение 10.4.2. Рассмотрим следующий фрагмент кода; а=Ь л.й (х == О) е1ве а = с; Будем считать, что машина использует модель задержек из примера 10.6 (загрузка занимает два такта, все прочие команды — по одному такту). Предположим также, что машина в состоянии выполнять одновременно две команды. Найдите наикратчайшее возможное выполнение этого фрагмента. Не забудьте рассмотреть вопрос о том, какие регистры лучше всего использовать для каждого шага копирования.
Чтобы избежать излишних загрузок и сохранений, не забудьте воспользоваться информацией, которую дают дескрипторы регистров, описанные в разделе 8.6. 10.5 Программная конвейеризация Как говорилось во введении к данной главе, обычно численные приложения обладают высокой степенью параллелизма. В частности, в них зачастую имеются циклы, итерации которых совершенно независимы одна от другой. Такие циклы, известные также как универсальные (до-а!! сус1ев), особенно привлекательны с точки зрения параллелизма, позволяя полностью использовать все ресурсы и все возможности параллельных вычислений процессора. В этом разделе будет рассмотрен алгоритм, известный как лрогралсиная конвейеризация (зойзнаге р!рейшпд), планирующий весь цикл целиком, который обеспечивает максимальное использование возможностей параллельных вычислений.
877 !0.5. Программная конвейеризация 10.5.1 Введение В примере 10.12 приведен универсальный цикл, который будет использоваться во всем разделе для пояснения программной конвейеризации. Сначала будет показана важность межитерационного планирования, связанная с относительно малым параллелизмом операций в пределах одной итерации. Затем мы покажем, как развертка цикла повышает производительность путем перекрытия развернутых итераций. Однако граница развернутого цикла остается непреодолимым барьером для перемещения кода, и развертка оставляет немало неиспользованных возможностей для повышения производительности кода. Метод же программной конвейеризации допускает перекрытие нескольких последовательных итераций, пока все они не будут выполнены, тем самым позволяя получить высокоэффективный и компактный код.
Пример 10.12. Вот пример типичного универсального цикла: аког(1 = 0; 1 < и; 1++) Р[1] = А[1] * В[1] + сз Итерации этого цикла выполняют запись в разные ячейки памяти, которые, в свою очередь, не совпадают ни с одним из адресов, по которым выполняется чтение данных. Следовательно, между итерациями не имеется никаких зависимостей данных, и все итерации могут выполняться параллельно. В этом разделе мы примем следующую модель целевой машины. ° За один такт машина может выполнить: одну загрузку, одно сохранение, одну арифметическую операцию или одну операцию ветвления. ° Машина имеет операцию цикла вида ВЬВ, Ь Эта операция уменьшает значение регистра В и, если оно не равно О, осуществляет переход к Ь.
° Операции с памятью могут выполняться в автоинкрементном режиме, на что указывают символы ++ после регистра. Значение регистра автоматически увеличивается с тем, чтобы после каждого обращения указывать на следующий адрес в памяти. ° Арифметические операции полностью конвейеризуемы. Они могут быть инициированы на любом такте, но их результаты становятся доступны два такта спустя.
Задержка всех прочих команд — один такт. 878 Глава !О. Параллелизм на уровне команд Если итерации выполняются по одной, то наилучший план, который можно получить в рамках нашей машинной модели, показан на рис. 10.17. На этом рисунке указаны некоторые предположения о размещении данных: регистры 81, К2 и КЗ хранят адреса начала массивов А, В и В; регистр В4 хранит константу с, а регистр В10 — значение п — 1, вычисляемое вне цикла. Такое вычисление, в основном, последовательное и занимает семь тактов; единственное имеющееся перекрытие — команды цикла и последней операции в итерации.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
