А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 195

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 195)

о Анализ зависимостей данных отличается от анализа повторного использования тем, что одно из обращений при исследовании зависимостей данных должно быть обращением для записи. Очень важно, чтобы поиск зависимостей данных был корректным и точным. Чтобы быть корректным, он должен найти все зависимости и не должен найти ложные зависимости, которые могут привести к излишнему последовательному выполнению. При повторном использовании данных все, что нам надо, — найти места, тле сосредоточивается большинство повторных использований, которыми можно воспользоваться для повышения эффективности программы. Эта задача существенно проще, так что мы рассмотрим ее в этом разделе, а с зависимостями данных разберемся в следующем.

Мы упростим анализ повторного использования, игнорируя границы циклов, так как они редко влияют на повторное использование. Воспользоваться повторным использованием можно при помощи аффинного разбиения среди экземпляров обращений к олному и тому же массиву и обращений с одной и той же матрицей коэффициентов (которую мы обычно обозначаем как г в аффинной индексной функции). Как было показано выше, шаблоны обращений наподобие 7г'+ 3 и 3(+5 не представляют интереса с точки зрения повторного использования.

11.5.1 Типы повторных использований Начнем с примера 11.20, который демонстрирует различные типы поюорных использований. Далее мы должны четко отличать обращение как команду программы, например х = 2 [з, 3 ], от многократного выполнения этой команды, как, например, при выполнении вложенности циклов. Чтобы полчеркнуть это отличие, говоря об инструкции самой по себе, мы будем говорить о статическаи обращении (згайс ассезз), в то время как различные итерации инструкции при выполнении вложенности циклов булем называть динамическим обращением (дупаппс ассезз). Повторные использования можно классифицировать как собственные (зей) и ерунновые (8гоцр). Если итерации повторно используют одни и те же данные из одного и того жс статического обращения, мы говорим о собственном по- 953 1!.5.

Повторное использование данных вторном использовании. Если же они поступают от разных обращений, то мы говорим о групповом повторном использовании. Повторное использование является временным, если обращение происходит к одной и той же ячейке памяти, и прост)эанствеллым, если обращение выполняется к одной строке кэша. Пример 11.20. Рассмотрим следующую вложенность циклов: Г1оаГ Е[п]; аког (1 = ОГ з < и; 1++) тот (3 = 0~ 3 < и; 3++) 2[3 ь1] = (к[3] + 2[3+1] + 2[3+2])узз Обращения Я Ц, Я Г)) + 1] и У).) + 2] представляют собственные пространственные повторные использования, поскольку последовательные итерации одного и того жс доступа обращаются к последовательным элементам массива.

Скорее всего, последовательныс элементы располагаются в одной и той жс строке кэша. Кроме того, все они обладают собственно-временным повторным использованием, поскольку при каждой итерации внешнего цикла выполняется обращение к одним и тем же элементам. Они также имеют одинаковую матрицу коэффициентов, а значит, обладают групповым повторным использованием. Между различными обращениями имеется групповое повторное использование, как временное, так и пространственное.

Хотя всего в этом коде 4пз обращений, если суметь воспользоваться повторными использованиями, нам потребуется только около и/с загрузок строк в кэш, где с количество слов в строке кэша. Множитель и удаляется благодаря собственно-пространственному повторному использованию, множитель 4 — из-за группового повторного использования, а множитель с связан с пространственной локальностью. о Далее мы рассмотрим возможность применения линейной алгебры для получения информации о повторном использовании из аффинных обращений к массиву.

Нас интересует не только поиск потенциальной экономии, но и то, какие именно итерации повторно используют ланные, чтобы их можно было переупорядочить и разместить поближе друг к другу и чтобы в полной мере воспользоваться преимуществами, предоставляемыми повторными использованиями. 11.5.2 Собственные повторные использования Если суметь воспользоваться собственными повторными использованиями, можно получить существенную экономию обращений к памяти. Если данные, к которым выполняешься статическое обращение, имеют й измерений, а доступ вложен в цикл глубиной 4, где д ) к, то одни и те же данные могут быть повторно использованы и" ~ раз, где п — количество итераций в каждом цикле.

Например, если цикл с глубиной вложенности 3 обращается к одному столбцу массива, то потенциально множитель, определяющий экономию обращений, 954 Глава ! !. Оптимизация параллелизма и локальности равен и". Оказывается, что размерность обращения соответствует концепции ранеа матрицы коэффициентов обращения, и найти итерации, которые обращаются к одним и тем же ячейкам, можно путем поиска нуль-пространства !пп1! красе) матрицы, как поясняется далее. Ранг матрицы Ранг матрицы Р равен наибольшему количеству линейно независимых столбцов (или строк). Множество векторов называется линейно независимым, если ни один из них не может быть записан как линейная комбинация конечного количе- ства других векторов из этого множества.

Пример 11,21. Рассмотрим матрицу ! 2 3 5 7 9 5 2 ! О Вторая строка матрицы представляет собой сумму первой и третьей строк, а четвертая — разность третьей и удвоенной первой строк. Однако первая и третья строки линейно независимы — одна из них не кратна другой. Таким образом, ранг матрицы равен 2. Тот же вывод можно сделать и при рассмотрении столбцов. Третий столбец представляет собой разность между удвоенным вторым и первым столбцами. С другой стороны, любые два столбца линейно независимы. Таким образом, мы делаем вывод о том, что ранг матрицы равен 2. и Пример 11.22.

Рассмотрим обращения к массивам на рис. 11.18. Первое обращение, Х !г — !], имеет размерность 1, так как ранг матрицы [1 01 равен 1 (единственная строка является линейно независимой). Второе обращение, У !1,Я, имеет размерность 2. Причина этого в том, что матрица ["1 имеет две независимые строки (и, конечно, два независимых столбца). Третье обращение, У !1, з + Ц, — одномерное, так как матрица [' '1 имеет ранг !. Заметим, что строки матрицы идентичны, так что только одна из них линейно независима.

Интуитивно в большой квадратной матрице У обращения 955 11.5. Повторное использование данных выполняются только к элементам вдоль одномерной линии, лежащей над главной диагональю. Четвертое обращение, У [1, 2[, имеет размерность О, так как матрица, состоящая только из нулей, имеет нулевой ранг. Заметим, что для такой матрицы невозможно найти ненулевую линейную сумму даже из одной строки. И наконец, последнее обрашение, Я [г, г, 2 * Г + Я, имеет размерность 2. В матрице это~о обращения О О 1 О 2 1 последние две строки линейно независимы — нн одна из них не кратна другой.

Однако первая строка представляет собой линейную "сумму" лвух других с коэффициентами О. а Нуль-пространство матрицы Обращение во вложенности циклов глубиной И с рангом г обращается к О (п') элементам данных в 0 (и") итерациях, так что в среднем 0 (и" ") итераций должны обращаться к одному и тому же элементу массива. Какие же итерации обращаются к одним и тем же данным? Предположим, что обращение в данной вложенности циклов представлено матрично-векторной комбинацией Р и Г. Пусть 1 и Р— две итерации, которые обращаются к одному и тому же элементу. Тогда г1+ Г = ЕГ + Г. Переставляя члены, получим В линейной алгебре имеется хорошо известная концепция, которая говорит о том, когда 1 и Р удовлетворяют приведенному уравнению.

Множество всех решений уравнения Рк = О называется нуль-пространством г. Таким образом, две итерации обращаются к одному и тому же элементу массива, если разность их индексных векторов принадлежит нуль-пространству Е. Легко увидеть, что нулевой вектор т = О всегда удовлетворяет уравнению Ет = О. Иначе говоря, две итерации гарантированно обращаются к одному и тому же элементу массива, если их разность равна О, т.е.

если это одна и та же итерация. Далее, очевидно, что нуль-пространство является истинным векторным пространством, те. если Рк~ = О и Рта = О, то Р (т~ + кз) = О и Р (ск~) = О. Если матрица г имеет полный ранг, т.е. ее ранг равен Ы, то нуль-пространство г состоит из единственного нулевого вектора. В таком случае все итерации во вложенности циклов обращаются к разным данным. В общем случае размерность нуль-пространства равна д — г. Если д ) г, то для каждого элемента имеется (д — г)-мерное пространство итераций, обращающихся к этому элементу. 956 Глава 11.

Оптимизация параллелизма и локальности Нуль-пространство может быть представлено его базисными векторами. ймерное нуль-пространство представляется к независимыми векторами; любой вектор, который может быть выражен в виде линейной комбинации базисных векторов, принадлежит нуль-пространству. Пример 11.23. Вернемся к матрице нз примера 1!.21: 1 2 3 5 7 9 4 5 6 2 1 О Мы выяснили, что ранг этой матрицы равен 2; таким образом, размерность нуль- пространства равна 3 — 2 = 1.

Чтобы найти базис нуль-пространства, который в данном случае должен быть простым ненулевым вектором длиной 3, можем считать, что это вектор [х,у,х[, и попытаться найти решение уравнения 1 2 3 5 7 9 4 5 6 2 1 О Если умножить первые две строки на вектор неизвестных, можно получить два уравнения: х+ 2у+ Зх = О 5х+ 7у+ 9г = О Можно записать и уравнения, полученные из третьей и четвертой строк, но поскольку в матрице не имеется трех линейно независимых строк, мы знаем, что новые уравнения не дадут новых ограничений на переменные х, у и г.

Характеристики

Список файлов книги