А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 213
Текст из файла (страница 213)
) аког ()с=)с1-1, )с>=2, )с--) РВ)[1, К, з, 1) = Р(4[1,)с, з, з.) +Р[)с] *РН[1,)с+1, з, 1] Рнс. !!.62. Код на рис. (!.23 после разбиения (рнс. !!.24) н сжатия массивов каждая операция с ними, такая как сложение или умножение, будет требовать большого количества чтений и записи ячеек памяти при относительно небольшом количестве арифметических операций. Важно переупорядочить операции так, чтобы данные потреблялись сразу же после их получения, и сжать массивы до скалярных переменных. 2.
Суперкомпьютеры 80-х и 90-х годов были векторными машинами, так что масса научных приложений была оптимизирована именно для этих машин. Несмотря на наличие векторизующих компиляторов многие программисты продолжают писать код, выполняющий операции одновременно над целыми векторами.
Примером такого стиля служит рассматривавшийся нами многосеточный код. 3. Возможности сжатия массивов привносятся и компилятором. Как иллюстрирует переменная Т в многосеточном примере, компилятор расширяет массивы для повышения степени параллелизма. Мы должны выполнять сжатие там, где такое расширение не является необходимым.
Пример 11.67. Выражение с массивами У = И'+ Х + У транслируется в код аког (з.=О; 1<п; з.++) Т[1.) = в)[1] + к[1]; Тог (з.=О; 1<п; 1++) 2[1) = Т[з.] + 1[1]! 1043 1! .10. Оптимизации локальности Если переписать код как Еог (з.=0; 1<пг 3++) ( Т = (4[з] + Х[11; Е[з1 = Т + У[11 это может значительно увеличить скорость его выполнения. Конечно, на уровне исходного текста С нам не надо использовать даже временную переменную Т, так как можно записать присваивание Л [г] как единую инструкцию. Однако здесь мы пытаемся смоделировать уровень промежуточного кода, на котором выполняет свои операции векторный процессор.
о Алгоритм 11.68. Сжатие массива Вход: программа, преобразованная алгоритмом 11.64. Выход: эквивалентная программа с массивом с уменьшенным количеством размерностей. МетОд: размерность массива может быть сведена к единственному элементу, если выполняются следующие условия. 1. Каждая независимая часть кода использует только один элемент массива.
2. Значение, которое хранилось в этом элементе до входа в часть, в этой части не используется. 3. Значение элемента не активно при выходе из части. Определяем сжимаемые измерения — которые удовлетворяют трем указанным условиям — и заменяем их единственным элементом. и В алгоритме 11.68 предполагается, что первоначально программа была трансформирована алгоритмом 11.64, который размещает все зависимые операции в одной части и последовательно выполняет части программы. Алгоритм находит те массивы, диапазоны активности элементов которых в разных итерациях не пересекаются.
Если эти переменные не являются активными после выхода из цикла, алгоритм сжимает такие массивы, заставляя процессор работать с одним и тем же скаляром. После сжатия может оказаться необходимым выборочно расширить скаляры до массивов для обеспечения распараллеливания и иных оптимизаций локальности. В данном случае требуется более сложный анализ активности переменных, чем рассматривавшийся в разделе 9.2.5. Если массив объявлен как глобальная переменная или представляет собой параметр процедуры, то, чтобы убедиться, что он не используется после выхода из цикла, требуется выполнить межпроцедурный анализ.
Кроме того, необходимо определить активность каждого отдельного элемента массива — консервативное рассмотрение массива как скадара будет слишком неточным. 1О44 Глава 11. Оптимизация параллелизма и локальности 11.10.3 Чередование частей Различные части цикла зачастую считывают одни и те же данные, или читают и пишут одни и те же строки кэша.
В этом и двух последующих разделах мы рассмотрим оптимизацию в случае повторного использования, пересекающего границы частей. Повторное использование во внутренних блоках Примем простую модель, в которой данные находятся в кэше, если они повторно используются в пределах небольшого количества итераций. Если внутренний цикл имеет большие или неизвестные границы, то выгода от локальности достигается только при повторном использовании, пересекающем границы итераций.
Блокирование создает внутренние циклы с небольшими известными границами, позволяя воспользоваться повторными использованиями как в пределах блоков, так и с пересечением их границ. Таким образом, блокирование позволяет извлечь выгоду из повторного использования с большим количеством размерностей. Пример 11.69. Рассмотрим код умножения матриц на рис. 11.5 н его блочную версию на рис. ! 1.7. Умножение матриц содержит повторные использования вдоль всех трех размерностей пространства итераций. В исходном коде внутренний цикл имеет и итераций, где п — неизвестное значение, которое может быть очень большим. Наша простая модель предполагает, что в кэше могут находиться только те данные, которые повторно используются итерациями внутреннего цикла.
В блочной версии три внутренних цикла выполняют трехмерный блок вычислений с В итерациями вдоль каждой стороны блока. Размер блока В выбирается компилятором достаточно малым для того, чтобы все строки кэша, считываемые и записываемые в пределах блока вычислений, могли разместиться в кэше. Таким образом, данные, повторно используемые итерациями третьего внешнего цикла, могут быть найдены в каше. и Будем называть внутреннее множество циклов с небольшими известными границами внутренним блоком (1ппеппозг Ыос1с). Желательно, чтобы внутренний блок по возможности включал все размерности пространства итераций с повторными использованиями.
Максимизация длин сторон блока не так важна. В случае примера с умножением матриц трехмерное блокирование снижает количество обращений к данным для каждой матрицы в Вз раз. При наличии повторных использований лучше иметь дело с блоками высокой размерности и малой стороной, чем с большими блоками малой размерности. Можно оптимизировать локальность внутренней полностью переставляемой вложенности циклов путем блокирования подмножеств циклов, разделяющих повторные использования.
Можно обобщить понятие блокирования, чтобы воспользоваться повторными использованиями, обнаруженными среди итераций внешних параллельных циклов. Заметим, что блокирование, в первую очередь, чередует 1045 11.10. Оптимизации локальности выполнение небольшого количества экземпляров внутреннего цикла. При умножении матриц каждый экземпляр внутреннего цикла вычисляет один элемент результирующего массива; всего таких элементов — п .
Блокирование чередует 2 выполнение блоков экземпляров, вычисляя за один раз В итераций из каждого экземпляра. Аналогично можно чередовать итерации параллельных циклов, чтобы получить выгоду от повторных использований между ними. Ниже будут определены два примитива, которые могут уменьшить дистанцию между повторными использованиями в разных итерациях. Мы будем многократно применять эти примитивы, начиная с внешнего цикла, до тех пор, пока все повторные использования не будут перемещены по соседству друг к другу во внутреннем блоке. Чередование внутренних циклов в параллельном цикле Рассмотрим ситуацию, когда внешний параллелизуемый цикл содержит внутренний цикл.
Чтобы воспользоваться повторными использованиями из разных итераций внешнего цикла, мы чередуем выполнения фиксированного количества экземпляров внутреннего цикла, как показано на рнс. 11.63. Создавая двумерные внутренние блоки, это преобразование сокращает расстояние между повторными использованиями последовательных итераций внешнего цикла. аког (11=0; 11<о; 11+=4) аког (3=0; 3<п; 3++) гог (1=11; 1<пап(п, 11+4); 1++) <Я> б) Преобразованный код аког (1=0; 1<п; 1++) гог (3=0' 3<п; З++) <Я> а) Исходная программа Рис. 11.63. Чередование четырех экземпляров внутреннего цикла Шаг, превращающий цикл аког (1=0; 1<п; 1++) <Я> аког (11=0; 11<п; 11+=4) аког (1=11; 1<яз1п(п, 11+4); 1++) <Я> известен как раслолосовалие (з(прш)пшй).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
