А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 198
Текст из файла (страница 198)
'Вспомним о разнице между статическим и динамическим обращениями. Статическое обращение — зто ссылка на массив в определенном месте программы, в то время как динамическое представляет собой одно выполнение статического обращения. 965 11.6. Анализ зависимости данных а массивах В разделе 11.7 рассматривается, как можно систематически использовать такую информацию при распараллеливании.
11.6.1 Определение зависимостей данных доступов к массивам Рассмотрим два статических обращения к одному и тому же массиву, возможно, в разных циклах. Первое представлено функцией доступа и границами У' = = (Г, Г, В, Ь) и находится во вложенности циклов глубиной д; второе представлено функцией доступа и границами У' = (Р', т", В', Ь') и находится во вложенности циклов глубиной Н'. Эти обращения зависимы через данные, если 1.
хотя бы одно из них — обращение для записи; г 2. существуют векторы 1е Г~ и 1' е Я", такие, что а) В!>О; б) В'(' ) О; в) Р1+ Г= Г'('+ $'. Поскольку статическое обращение обычно объединяет множество динамических обращений, имеет смысл задаться вопросом, не могут ли эти динамические обращения ссылаться на одно место в памяти? Для поиска зависимостей между экземплярами одного и того же статического обращения мы полагаем У' = У' и дополняем приведенное выше определение дополнительным ограничением 1 ф 1', чтобы избежать тривиального решения. Пример 11.29. Рассмотрим вложенность циклов единичной глубины: аког(з = 1; з < 10; 1++) ( Е(х) = Е(х-1)з В этом цнкпс находятся два обращения — Я [1 — 1] и Я [(]. Первое представляет собой чтение, а второе — запись.
Чтобы найти все зависимости данных в программе, мы должны проверить наличие зависимостей как между разными обращениями для записи, так и между обращениями для записи и обращениями для чтения. 1. Зависимости данныхмеясду Я [( — 1] и У [(]. За исключением первой итерации, каждая итерация считывает значение, записанное в предыдущей итерации. Математически зависимость существует, так как существуют такие целые числа ( и ю', что 966 Глава 11. Оптимизация параллелизма и локальности Существует девять решений приведенной системы ограничений: (1 = 2, т'=1), (1=3,Г =2) ит.д.
2. Зависимости данных между обращением о (1) и им же. Легко видеть, что различные итерации цикла выполняют запись в разные места памяти, т.е. зависимостей данных между экземплярами обрашения для записи г [1) нет. Математически зависимости нет, так как не существует 1 и 1', удовлетворяюших условиям 1 < 1 < 10, 1 < 1' < 10, 1 = 1' и 1 ф г' Заметим, что третье условие, 1 = з', вытекает из требования, чтобы 2 [1) и г. [1') обрашались к одному и тому же месту в памяти. Оно противоречит четвертому условию — 1 ф г', — которое вытекает из требования нетривиальности зависимости между разными динамическими обращениями. Нет необходимости рассматривать зависимости данных между обращением для чтения г [1 — 1] и им же самим, поскольку любые два обращения для чтения независимы.
о 11.6.2 Целочисленное линейное программирование Зависимости данных требуют решения вопроса о существовании целых чисел, удовлетворяющих системам, состоящим из уравнений и неравенств. Уравнения вытекают из матричного представления обращений, а неравенства — из границ циклов. Уравнения могут быть выражены в виде неравенств: равенство х = р можно заменить двумя неравенствами — х > у и д ) х. Таким образом, зависимости данных могут быть выражены как поиск целочисленных решений, удовлетворяющих множеству линейных неравенств, т.е. как решение хорошо известной задачи целочисленного линейного программирования. Известно, что целочисленное линейное программирование является НР-полной задачей.
Полиномиальный алгоритм для ее решения неизвестен, но имеется ряд эвристик для задач с многими переменными, причем во многих случаях они достаточно быстрые. К сожалению, такие стандартные эвристики непригодны для анализа зависимостей данных, где проблема заключается в решении большого количества небольших и простых задач целочисленного линейного программирования, а не в решении одной большой сложной задачи. Алгоритм анализа зависимостей данных состоит из трех частей.
1. Поиск наибольшего общего делителя 1НОД) для проверки существования целочисленного решения уравнений с применением теории линейных диофантовых уравнений. Если целочисленных решений не существует, нет и зависимостей данных. В противном случае мы используем уравнения 967 1! .6.
Анализ зависимости данных в массивах для подстановки части переменных, чтобы получить более простые нера- венства. 2. Использование набора простых эвристик для работы с большим количеством типичных неравенств. 3. В редких случаях, когда эвристики не срабатывают, используется решение задачи целочисленного линейного программирования с применением метода ветвлений и границ на основе исключения Фурье-Моцкина. И.б.З НОД Первая подзадача состоит в проверке существования целочисленного решения уравнений.
Уравнения с условием, что их решения представляют собой целые числа, известны как диофантовы уравнения. В приведенном ниже примере показано, откуда берется условие целочисленности решений, и демонстрируется, что, несмотря на то что в наших примерах рассматривается по одной вложенности циклов, понятие зависимости данных может применяться и к разным циклам. Пример 11.30. Рассмотрим следующий фрагмент кода: йот(1 = 1; 1 < 10; 1++) ( Е (2*з.] тот(3 = 1; 3 < 10; 3++) ( К(2*3+1) = ...; Обращение л, ]2* я] выполняет запись только в четные элементы массива Я, а 7 [2*7+ 1] — в нечетные. Понятно, что зависимости данных между этими обращениями неть, какими бы ни были границы циклов.
Можно выполнить итерации второго цикла до первого, можно чередовать итерации обоих циклов. Этот пример не настолько искусственен, как можно подумать. Примером может служить работа с массивом комплексных чисел, в котором действительные и мнимые части хранятся друг за другом. Доказать отсутствие зависимости данных в приведенном примере можно следующим образом. Предположим, что существуют такие целые числа з и у, что Я (2 * з] и Я (2 * у + Ц обращаются к одному и тому же элементу массива л . Мы получаем диофантово уравнение 2з = 2) + 1 Если, конечно, таковая не появляется нз-за выражений, результаты которых записываются в массне Л н которые в исходном тексте показаны троеточнямн.
— Прим. лед. Глава 11. Оптимизация параллелизма и локальности Алгоритм Евклида Алгоритм Евклида для поиска код (а,Ь) работает следующим образом. Будем считать, что а и 6 — положительные целые числа и а > 6. Заметим, что НОД отрицательных чисел или НОД отрицательного и положительного числа тот же, что и НОД их абсолютных значений, так что мы можем считать, что все целые числа положительны. Если а = 6, то код(а,Ь) = а. Если же а > 6, то пусть с — остаток от деления а/6. Если с = О, то 6 является делителем а, так что код (а, 6) = 6.
В противном случае вычисляем лед (6, с); результат вычисления будет равен бсс1 (а, Ь). Чтобы найти ясд(аз,аз,...,а„) при и > 2, воспользуемся алгоритмом Евклида для вычисления код(ам аз) = с, а затем рекурсивно вычислим бей (с, аз, а4,..., а„). Не существует целых чисел 1 и /, которые удовлетворяли бы данному уравнению. Доказательство этого состоит в том, что каким бы ни было целое число 1, значение 21 всегда четно. Аналогично, каким бы ни было целое число з, значение 2у + 1 всегда нечетно. Но никакое число не может быть одновременно и четным, и нечетным. Следовательно, уравнение не имеет целочисленных решений, а значит, нет и зависимостей между обрашениями для записи и для чтения.
и Чтобы выяснить, существует ли решение линейного диофантового уравнения, нам нужна концепция наибольшего общего делителя, НОД (йгеа1ез1 сошпюп 61н1зог — ОСР), двух или более целых чисел. НОД целых чисел аы аз,..., а„, обозначаемый как ксс1 (аы аз,..., а„), представляет собой наибольшее целое число, на которое без остатка делятся все указанные числа.
НОД может быть эффективно вычислен при помощи широко известного алгоритма Евклида. Пример 11.31. код (24, 36, 54) = 6, так как 24/6, 36/6 и 54/6 имеют остаток от деления, равный О, причем любое число, большее 6, будет давать по крайней мере один остаток при делении на него 24, Зб и 54. Например, 24 и Зб делятся нацело на 12, но при делении 54 на 12 получается остаток б. Важность НОД заключается в следующей теореме.
Теорема 11.32. Линейное диофантово уравнение а1х1+ азх2+ + а„х„= с имеет целочисленное решение хы хз,..., х„тогда и только тогда, когда ксс1(аы аз,... а„) является делителем с. и 969 11.6. Анализ зависимости данных в массивах Пример 11.33. В примере 11.30 мы видели, что линейное диофантово уравнение не имеет решения. Это уравнение можно записать как 21 — 2з =1 Поскольку ясй(2, — 2) = 2, а 2 не является делителем 1, указанное уравнение решений не имеет. В качестве еще одного примера рассмотрим уравнение 24х + Збу + 54з = 30 Поскольку ясг1 (24,36,54) = 6, а 30/6 = 5, решение приведенного уравнения в целых числах существует.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
