А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 196
Текст из файла (страница 196)
Например, уравнение, которое мы получим из третьей строки — 4х + 5у + бз = О, — может быть получено путем вычитания первого уравнения из второго. Мы должны исключить как можно большее количество переменных из полученных уравнений. Начнем с первого уравнения и выразим из него х; х = — 2у— — 3=. Затем подставим х во второе уравнение и получим — Зу = бх, или у = — 2х. Поскольку х = — 2у — Зг, а у = — 2з, мы получаем х = х.
Таким образом, вектор '[г,у, "] на самом деле представляет собой вектор [з, — 2х, г[. Мы можем взять любое ненулевое значение г для того, чтобы получить единственный базисный вектор нуль-пространства. Например, выбрав г = 1, мы получим базисный вектор нуль-пространства, равный [1, — 2, Ц.
о 957 11.5. Повторное использование данных Пример 11.24. Ранги, размерности нуль-пространств и сами нуль-пространства для всех обращений из примера 11.17 показаны на рис. 11.19. Заметьте, что сумма ранга и размерности нуль-пространства во всех случаях равна глубине вложения циклов, 2. Поскольку обращения У [1,Я и Я [1, г, 2 *1+ Я имеют ранг 2, все итерации обращаются к разным элементам. Рис.
1! .19. Ранг и размерность нуль-пространств аффинных обращений Оба обращения, Х [1 — Ц и У [~, 1 + Ц, имеют матрицы ранга 1, так что к одним и тем же элементам обращаются О 1п,) итераций. В первом случае к одному и тому же элементу обращается целая строка в пространстве итераций. Другими словами, итерации, отличающиеся только размерностью з, обращаются к одному и тому же элементу, что кратко представлено базисом нуль-пространства [О, Ц, В случае У [1, 1 + Ц к одному элементу обращается столбец пространства итераций; этот факт представлен базисом нуль-пространства [1, О). Наконец, в случае У [1, 2) к одному и тому же элементу обращаются все итерации.
Нуль-пространство в данном случае имеет два базисных вектора — [О, Ц и [1, 0], — которые означают, что все пары итераций обращаются к одному и тому же элементу массива. а 958 Глава 11. Оптимизация параллелизма и локальности 11.5.3 Собственное пространственное повторное использование Анализ пространственного повторного использования зависит от схемы размещения данных в матрице. Матрицы в С располагаются построчно, а в Рогггап— постолбцово.
Другими словами, элементы массивов Х р, Я и Х ~1, 1 + Ц являются соседними в языке программирования С, а в языке программирования Еогггап соседними будут элементы Х ~г, Я и Х р + 1,Я. Без потери общности в оставшейся части главы будем считать, что используется построчная схема размещения массивов из С.
В качестве первого приближения мы рассмотрим два элемента массива, находящихся в одной строке кэша тогда и только тогда, когда они находятся в одной строке двумерного массива. В общем случае, если массив имеет размерность Н, то элементы такого массива располагаются в одной строке кэша, если они отличаются один от другого только значением индекса последнего измерения. Поскольку для типичного массива и кэша в одной строке кэша располагается множество элементов массива, наблюдается существенное ускорение при построчном доступе, несмотря на то что, строго говоря, время от времени приходится ожидать загрузки новой строки кэша. Выявление и использование преимуществ собственного пространственного повторного использования состоит в отбрасывании последней строки из матрицы коэффициентов Е. Если ранг получившейся усеченной матрицы меньше глубины вложенности циклов, то обеспечить пространственную локальность можно путем такого преобразования кода, что в наиболее глубоко вложенном цикле изменяется только последняя координата массива.
Пример 11.25. Рассмотрим последнее обращение парис. 11.19 — У 11, 1,2 *1+ З]. Если удалить последнюю строку, можно получить усеченную матрицу [':1 Очевидно, что ранг данной матрицы — 1, так что, поскольку глубина вложенности циклов равна 2, имеется возможность обеспечить пространственное повторное использование. В нашем случае, поскольку индексной переменной внутреннего цикла является 1', внутренний цикл посещает соседние элементы построчно хранящегося массива У.
Если сделать индексом внутреннего цикла переменную г, пространственное повторное использование получено не будет, так как при изменении 1 будут изменяться и вторая, и третья координаты массива. и Общее правило определения наличия собственного пространственного повторного использования выглядит следующим образом.
Как обычно, мы полагаем, что индексы цикла соответствуют столбцам матрицы коэффициентов в порядке, 959 1!.5. Повторное использование данных в котором первым следует самый внешний цикл, а последним — наиболее глубоко вложенный. Тогда для наличия пространственного повторного использования в нуль-пространстве усеченной матрицы должен иметься вектор !О, О,...,О, Ц.
Причина этого в том, что если такой вектор есть в нуль-пространстве, то при фиксации всех индексов циклов, кроме наиболее глубоко вложенного, у всех динамических обращений в пределах выполнения внутреннего цикла будет изменяться только последний индекс массива. Если массив хранится построчно, то все эти элементы будут близки друг к другу и, возможно, будут находиться в одной строке кэша.
Пример !1.26. Заметим, что в усеченной матрице из примера 11.25 имеется транспонированный вектор-столбец !О, Ц. Таким образом, как упоминалось ранее, можно ожидать, что, если индексом вложенного цикла является ), будет достигнута пространственная локальность. С другой стороны, если изменить порядок циклов, так что внутренним циклом станет цикл 1, то матрица коэффициентов примет вид ~о о~ Теперь |О, Ц нс входит в нуль-пространство этой матрицы.
Нуль-пространство теперь генерируется базисным вектором !1, О). Таким образом, как и предполагалось в примере! 1.25, нельзя ожидать пространственной локальности, если внутренним циклом является цикл ~'. Мы, однако, должны заметить, что проверки наличия [О, О,..., О, Ц в нуль- пространстве не вполне достаточно для гарантии пространственной локальности. Предположим, например, что обращение имеет вид не Я !1,1,2 * 1+ 1), а У !1, 1', 2 *1+ 50 * Я. Тогда в процессе выполнения внутреннею цикла обращение будет только к каждому пятидесятому элементу и повторного использования строк кэша не будет, если они недостаточно длинны, чтобы хранить более 50 элементов.
11.5.4 Групповое повторное использование Групповое повторное использование вычисляется только среди обращений с одной и той же матрицей коэффициентов. Если даны два динамических обращения, И1+ Т1 и И2 + $2, повторное использование одних и тех же данных требует выполнения условия И! + 1'1 = И2 + 12 или Р (11 12) Ф2 11) . 960 Глава 11.
Оптимизация параллелизма н локальности Предположим, что решением этого уравнения является вектор т. Тогда, если и— любой вектор из нуль-пространства г, то вектор т + зк также является решением, и такие векторы охватывают все решения уравнения. Пример 11.27. Вложенность циклов глубиной 2 аког(1 = 1; 1 <= и; 1++) аког(з = 1; э <= и; э++) К(1,э) = г('-1,з1; содержит два обращения к массиву Я, а именно — Е [(,Я и У [( — 1,)]. Оба этн обращения характеризуются матрицей коэффициентов ["1 как и обращение У [г, )] на рис. 11.19. Данная матрица имеет ранг 2, так что собственного временного повторного использования в данном случае нет.
Однако каждое обращение проявляет собственное пространственное повторное использование. Как говорилось в разделе 1!.5.3, если мы удалим нижнюю строку матрицы, то останемся только с верхней строкой [1,0], имеющей ранг 1. Поскольку в нуль-пространство этой усеченной матрицы входит вектор [1,0], ожидается наличие пространственного повторного использования. Так как каждое увеличение индекса внутреннего цикла ) увеличивает второй индекс массива на 1, мы обращаемся к соседним элементам массива и максимально используем каждую строку кэша.
Хотя у каждого из обращений отсутствует собственное временное повторное использование, заметим, что две ссылки, Я [(, з] и У (( — 1, з], обращаются почти к одинаковым множествам элементов. Иначе говоря, мы имеем дело с групповым временным повторным использованием, поскольку данные, считанные обращением Я [( — 1,)], те же, что и записываемые обращением У [(,Я, за исключением случая ( = 1. Этот простой шаблон применяется ко всему пространству итераций н может быть использован для повышения локальности данных в коде. Формально, без учета границ цикла, две ссылки, У [г, з] и У [( — 1, )], обращаются к одним и тем же данным в итеРациЯх [ги )з) и [(з,ув) пРн Условии Переписывая данное уравнение, получаем 961 1! .5.
Повторное использование данных Пример 11.28. Предположим, что во вложенности циклов глубиной 3 с индекса- ми т, з и 1с (от внешнего цикла к внутреннему) имеются два обращения: А [а,у,г'+Я и А [я+ 1,т' — 1,к+Я Тогда два обращения, 11 = [зт, 11, 1сг] и!з = [тз, уз, 1сз], повторно используют один и тот же элемент при условии т'з 1 0 0 тз 1 0 0 Я + IС1 О 1 О 1 1 0 lсз 0 1 0 1 1 0 Решением этого уравнения относительно вектора у = [зд — зз, уд — уз, 1ст — Ц является вектор у = [1,-1,0], т.е. зт = аз + 1, 51 = уз — 1 и йт = йз." Нуль- пространство матрицы 1 0 0 Р= 0 1 0 1 1 0 генерируется базисным вектором [0,0, 1], т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
