А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 215
Текст из файла (страница 215)
3. Онтимизаиия. Все взаимодействия не обязательно выполняются в точках синхронизации. Предпочтительно, чтобы каждый процессор отсылал данные, как только они становятся доступными, так что другим процессорам не нужно было бы ожидать необходимых им данных. С другой стороны, с обработкой каждого сообщения связаны существенные накладные расходы, так что следует избегать генерации слишком большого их количества. Описанные здесь методы имеют и иные применения. Например, встроенные системы специального назначения могут использовать сопроцессоры для того, чтобы разгрузить основной процессор. Или вместо выборки данных в кэш встроенная система может использовать отдельный контроллер для загрузки и выгрузки данных из кэша или иных буферов данных, в то время как процессор работает с другими данными. В этих случаях для генерации кода и перемещения данных могут быть использованы методы, подобные описанным.
11.11.2 Процессоры с одновременным выполнением нескольких команд Аффинные преобразования циклов могут использоваться и для оптимизации производительности машин с одновременным выполнением нескольких команд. 1052 Глава ! !. Оптимизация параллелизма и локальности Как говорилось в разделе !0.5, производительность программно конвейеризованного цикла ограничена двумя факторами: наличием циклов в ограничениях пред- шествования и использованием критичных ресурсов.
Путем изменения внутреннего цикла эти ограничения можно уменьшить. Можно попытаться применить преобразование циклов для создания внутренних распараллеливаемых циклов, тем самым полностью устраняя циклы пред- шествования. Предположим, что программа имеет два цикла, причем внешний цикл распараллеливаемый, а внутренний — нет. Можно переставить эти два цикла, чтобы сделать распараллеливаемым внутренний цикл и тем самым увеличить количество возможностей для параллелизма на уровне команд.
Заме~им, что итерации во внутреннем цикле не обязаны быть полностью распараллеливаемыми. Достаточно, чтобы циклы зависимостей были довольно короткими, так чтобы аппаратные ресурсы использовались полностью. Можно также ослабить ограничения, связанные с использованием ресурсов, корректно балансируя циклы. Предположим, что один цикл использует только слагаемое, а второй — только множитель.
Или один цикл ограничен использованием памяти, а второй — вычислительными ресурсами. Такие пары циклов желательно объединить, чтобы одновременно использовать все функциональные единицы. 11.11.3 Векторные и $1МР-команды Помимо одновременного выполнения нескольких команд, имеются два других важных вида параллелизма на уровне команд: векторные и 51МР-команды. В обоих случаях выполнение одной команды приводит к применению одной и той же операции к вектору данных. Как уже упоминапось, многие ранние суперкомпьютеры использовали векторные команды.
Векторные операции выполняются в стиле конвейера; элементы вектора выбираются последовательно, а вычисления над разными элементами перекрываются. В усовершенствованных векторных машинах операции могут быть сцепленными !сЬа!пед): после получения элементов результирующего вектора они тут же используются операциями другой векторной команды, без ожидания, когда станут доступными все результаты целиком.
Кроме того, в машинах со специальным аппаратным обеспечением (всацег!йа!)зег) элементы векторов не обязаны быть смежными; для указания местоположения элементов векторов используются индексные векторы. 51МР-команды указывают, что одна и та же операция выполняется над смежными ячейками памяти. Такие команды параллельно загружают данные из памяти в специальные широкие регистры и проводят вычисления параллельно с использованием специальных аппаратных средств.
Многие приложения мультимедиа, графические или цифровой обработки сигналов, с успехом используют такие операции. Недорогие медиапроцессоры могут достичь параллелизма на уровне команд 1053 1),11. Прочие применения аффинных преобразований простым использованием 51МП-команд.
Мощные процессоры способны комбинировать применение 51МП-команд с одновременным выполнением нескольких команд для достижения более высокой производительности. Генерация $1МП-команд и векторных команд имеет много общего с оптимизацией локальности. Когда мы находим независимые части, которые работают со смежными ячейками памяти, мы располосовываем эти итерации и чередуем эти операции во внутренних циклах. Генерация Б1М1)-команд имеет две дополнительные трудности.
Во-первых, некоторые машины требуют, чтобы 51МП-данные, выбираемые из памяти, были выровнены. Например, может потребоваться, чтобы 256-байтные 51МП-операнды размещались в адресах, значения которых кратны 25б. Если исходный цикл работает более чем с одним массивом, одновременное выравнивание всех данных может оказаться невозможным. Во-вторых, данные, используемые последовательными итерациями цикла, могут не быть смежными. Примерами могут служить многие важные алгоритмы цифровой обработки сигналов, такие как декодеры Витерби или быстрое Фурье-преобразование.
Для использования Б1М1Э-команд могут потребоваться дополнительные операции по перемещению данных. 11.11.4 Предвыборка Никакая оптимизация локальности данных не в состоянии устранить все обращения к памяти; например, данные, которые используются программой в первый раз, должны быть выбраны из памяти. Для сокрытия задержки, связанной с операциями с памятью, во многих высокопроизводительных процессорах используются команды лредвыборки (ргеГе1сЬ )пзтгцсйопз). Предвыборка представляет собой машинную команду, которая указывает процессору, что, скорее всего, вскоре будут использованы некоторые данные, так что их желательно загрузить в кэш, если их там еще нет. Для оценки вероятных промахов нэша можно применить анализ повторных использований из раздела 11.5. При генерации команд предвыборки следует принять во внимание два важных момента.
Если выполняется обращение к последовательным ячейкам памяти, то для каждой строки кэша надо выполнить только одну команду предвыборки. Команды предвыборки должны быть выполнены заранее, чтобы данные находились в кэше в тот момент, когда они будут использоваться. Однако команды предвыборки не должны выполняться слишком рано, поскольку при этом в кэше могут оказаться замещенными данные, которые еще будут нужны; при слишком ранней предвыборке могут оказаться удаленными из кэша и данные, которые были загружены командами предвыборки. Пример П.73. Рассмотрим следующий код: аког (1=0; з1<З; х++) 1054 Глава 11.
Оптимизация параллелизма и локальности аког (э=О; э<100; з++) А[1,9] Предположим, что целевая машина имеет команды предвыборки, которые могут одновременно выбирать только два слова, и что задержка при выполнении команды предвыборки составляет время, примерно требуемое для выполнения шести итераций цикла. Код предвыборки для данного примера показан на рис.
11.68. аког (1=0; 11<3; 1++) аког (3=0; З<б; э+=2) рге1етс)т(йА[1,О]); аког (З=О; э<94; э+=2) ( ргейеГс)т(йА[1,~+б]); А[з., з ] А[з.,э+1] ) аког (Э=94; ~<1001 ~++) А[1,э] Рис. 11.68. Код, модифицированный для предвыборки данных Мы дважды разворачиваем внутренний цикл с тем, чтобы предвыборка могла быть выполнена для каждой строки кэша.
Для предвыборки данных за шесть итераций до их использования мы воспользовались концепцией программной конвейеризации. Пролог загружает данные для первых шести итераций. Устойчивое состояние цикла выполняет предвыборку за шесть команд до их участия в вычислениях. В эпилоге предвыборка не производится, здесь просто выполняются оставшиеся итерации. и 11.12 Резюме к главе 11 + Параллелизм и локальность при обращении к массивам.
Наиболее важные возможности распараллеливания и оптимизации локальности связаны с обращением к массивам в циклах. Такие циклы обычно имеют ограниченные зависимости между обращениями к элементам массива, а сами обращения выполняются в соответствии с регулярным шаблоном, что при хорошей локальности позволяет эффективно использовать кэш, + Аффиппые обращения. Почти вся теория и методы распараллеливания и оптимизации локальности считают, что обращение к массивам аффинное, т.е. выражения для индексов массивов представляют собой линейные функции от индексов циклов. 1055 11.12.
Резюме к главе 11 + Пространства итераций. Вложенность циклов с д вложенными циклами определяет д-мерное пространство итераций. Точками пространства являются Й-кортежи значений, которые могут принимать индексы циклов в процессе выполнения вложенности циклов. В случае аффинных обращений пределами каждого индекса цикла являются линейные функции от индексов внешних циклов, так что пространство итераций представляет собой многогранник. в Исключение Фурье — Манкина.
Ключевой операцией над пространствами итераций является переупорядочение циклов, определяющих пространство итераций. Для этого требуется, чтобы многогранное пространство итераций было спроецировано на подмножество своих измерений. Алгоритм Фурье-Моцкина заменяет верхний и нижний пределы данной переменной неравенствами с участием границ. + Зависимости данных и обращения к массивам. Центральной проблемой, которую следует решить при распараллеливании и оптимизации локальности, является вопрос о наличии зависимости данных между двумя обращениями к массиву (которые могут обращаться к одному и тому же элементу массива).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
