А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 199
Текст из файла (страница 199)
Одним из решений является х = — 1, у = 0 и з = 1, но, помимо него, имеется бесконечное множество иных решений. и Первый шаг к решению задачи анализа зависимостей данных состоит в использовании для решения данных уравнений стандартного метода, такого как метод исключения Гаусса. Каждый раз при построении линейного уравнения применяется теорема 11.32 для выяснения, существует ли его решение в целых числах. Если решение существует, то оно используется для снижения количества переменных в неравенствах. Пример 11.34. Рассмотрим два уравнения: х — 2у+з = 0 Зх+2у+х = 5 Если взглянуть на каждое уравнение по отдельности, то они имеют решения.
В первом уравнении йс(1(1,— 2,1) = 1 является делителем О, а во втором ксй(3,2,1) = 1 является делителем 5. Но если использовать первое уравнение, вывести из него г = 2у — х и подставить во второе уравнение, то можно получить 2х + 4у = 5. Но это диофантово уравнение не имеет целочисленных решений, поскольку ясг1 (2, 4) = 2 не является делителем 5. и 11.6.4 Эвристики для решения задачи целочисленного линейного программирования Задача анализа зависимостей данных требует решения большого количества простых задач целочисленного линейного программирования.
Здесь мы рассмотрим некоторые методы работы с простыми неравенствами. 970 Глава 11. Оптимизация параллелизма и локальности Проверка независимых переменных Многие задачи целочисленного линейного программирования, возникающие при анализе зависимостей данных, состоят из неравенств с единственным неизвестным.
Такие задачи могут быть решены простой проверкой существования целых чисел между константными верхними и нижними границами. Пример 11.35. Рассмотрим вложенный цикл аког(1 = 0; 1 <= 10; 1++) аког(з = 0; з <= 10р з++) Е (з., > ] = Е [>+10, 1+11 3 1 Чтобы выяснить, имеется ли зависимость мехсду Я '(з',Я и Я '() + 10,1+ 1Ц, мы проверяем, существуют ли целые числа (, ), (' и ~', такие, что Проверка НОД, примененная к данным двум уравнениям, позволяет определить, что данные уравнения могут иметь целочисленные решения. Эти решения можно выразить как 1 = (ы ) = гз, 1~ = (з — 11, ул = 11 — 10 для произвольных (1 и 1з.
Подстановка переменных г1 и 1з в линейные неравенства дает 0< 11 <10 О< 1 <Ю 0 < 8з — 11 < 10 о<( — ю< ю Объединяя нижние границы из двух последних неравенств с верхними границами из первых двух, мы выводим ю<( <ю 11 < (з < 10 Поскольку нижняя граница гз оказывается больше верхней, можно сделать вывод, что целочисленного решения исходной системы не существует„а значит, нет и зависимостей данных.
Этот пример показывает, что даже при наличии нескольких уравнений с несколькими переменными можно прийти к неравенствам, в которых используется по одной переменной. о 971 11.6. Анализ зависимости данных в массивах Проверка ацикличиости Еще одна простая эвристика заключается в выяснении, не существует ли переменной, ограниченной снизу или сверху константой.
При некоторых условиях можно безопасно заменить переменную константой; упрощенные неравенства имеют решение тогда и только тогда, когда решение имеют исходные неравенства. В частности, предположим, что каждая нижняя граница для с; имеет вид се < с1п2 для некоторого с; > О, при этом верхние границы для п; имеют вид г с; < се + с1с1 + + с1 1е; ~ + с,~1пь 1 + + с„п„, где с; неотрицательно.
Тогда можно заменить переменную и, ее наименьшим возможным целым значением. Если такой нижней границы нет, то мы просто заменяем гл на — со. Аналогично, если все ограничения, включающие со могут быть записаны в представленном выше виде, но с обратными направлениями неравенств, то мы можем заменить и; наибольшим возможным положительным целым числом нли оо, если верхней границы не существует. Этот шаг можно повторять, чтобы упростить неравенства, а в некоторых случаях даже получить решение. Пример 11.3б, Рассмотрим следующие неравенства: 1<оыо2<10 О< из <4 т2 ~ ~с1 < ез+4 Переменная о1 ограничена снизу переменной и2, а сверху — значением из + 4.
Однако с2 ограничена снизу константой 1, а пз ограничена сверху константой 4. Таким образом, заменяя в неравенствах п2 на 1, а сз на 4, мы получим систему 1<с1 <10 1 < п1 с1 <8 Она легко решается методом проверки независимых переменных. Проверка вычетов циклов Теперь рассмотрим ситуацию, когда переменная ограничена сверху и снизу другими переменными. В анализе зависимостей данных весьма распространены Глава 11. Оптимизация параллелизма н локальности ограничения вида о; < и + с, которые могут быть решены при помощи упрощенной проверки вычета цикла (1оор-гез1оце гевг) Шостака (Язоз1а(с).
Множество таких ограничений может быть представлено ориентированным графом, узлы которого помечены переменными. Для каждого ограничения тч < ту + с имеется ребро нз с, в сгэ помеченное с. Определим вес пути как сумму меток всех ребер, составляющих путь. Каждый путь в графе представляет собой комбинацию ограничений в системе, т.е.
если существует путь от и до о' с весом с, то можно заключить, что с < с'+ с. Наличие в графе цикла с весом с представляет ограничения о < о + с для каждого узла с в цикле. Если в графе можно найти цикл с отрицательным весом, это означает, что можно получить невозможное ограничение с < с. В таком случае мы заключаем, что система неразрешима, а значит, зависимостей данных нет. В проверку можно также включить ограничения вида с < о и с < с для переменной с и константы с. Мы вводим в систему неравенств новую фиктивную переменную со, которая добавляется к каждой константе, представляющей нижнюю или верхнюю границу. Конечно, переменная со должна иметь значение О, но поскольку нас интересуют только циклы, фактические значения переменных не имеют значения. Для константных границ мы заменяем о<снап<со+с, с < ц на оо < с — с.
Пример 11.37. Рассмотрим неравенства 1 < сы сг < 10 О< оз <4 сг < 2с1 < 2сз — 7 Константные верхняя и нижняя границы для с1 превращаются в со < с1 — 1 и с1 < со + 10; константные границы для иг и сз обрабатываются аналогично. Преобразуя последнее ограничение в с1 < оз — 4, мы получаем граф, показанный на рис. 11.21. Цикл с1 — оз — со — о1 имеет вес — 1, так что данная система неравенств решения не имеет. и Запоминание при выполнении Часто приходится неоднократно решать одни н те же задачи анализа зависимостей данных, поскольку простые шаблоны обращений часто повторяются в программе. Одним из важных методов ускорения обработки зависимостей данных является запоминание лри выполнении (шешо)га11оп).
При использовании этого 973 11.6, Анализ зависимости данных в массивах Рнс. 11.21. Граф ограничений из примера 11.37 метода результаты решения задачи вносятся в специальную таблицу, и при решении новой задачи сначала выполняется поиск в таблице готового решения. Решение "с нуля*' выполняется только в том случае, если такого решения еще нет в таблице. 11.6.5 Решение обобщенной задачи целочисленного линейного программирования В этом разделе мы опишем общий подход к решению задачи целочисленного линейного программирования.
Задача является ХР-полной; наш алгоритм использует метод ветвей и границ, который в худшем случае может потребовать экспоненциального времени работы, Однако ситуация, когда эвристики из раздела 1!.6.4 не в состоянии справиться с задачей, возникает достаточно редко, и даже когда мы вынуждены прибегнуть к описываемому здесь алгоритму, он редко требует выполнения шага ветвей и границ.
Ваш подход вначале проверяет наличие рационального решения неравенств. Это классическая задача линейного программирования. Если рационального решения системы неравенств не существует, области данных, с которыми работают рассматриваемые обращения, не перекрываются и зависимостей данных нет. Если же рациональное решение суп1ествует, то мы сначала пытаемся доказать существование целочисленного решения 1которое в таком случае обычно существует).
Если же нам это не удается, то мы разбиваем многогранник, ограниченный неравенствами, на два меньших и решаем задачу рекурсивно. Пример 11.38. Рассмотрим следующий простой цикл: аког(х = 1; х < 101 х++) Е[х] = Е[з.+10]1 Обращение Я [г] работает с элементами Я [1],..., У [9], а обращение Я [г + 10]— с элементами Л [П],...,У, [19]. Эти диапазоны не перекрываются, а следова- 974 Глава 11.
Оптимизация параллелизма и локальности тельно, зависимостей данных нет. Более формально мы должны показать, что не существует двух динамических обращений ! и Г, таких, что 1 < ! < 9, 1 < г' < 9 и ! = г' + 10. Если бы такие целые числа ! и г' существовали, то мы могли бы подставиты'+ 10 вместо ! и получить ограничения на г'. 1 < Г < 9 и 1 < Г + + 10 < 9. Однако из г'+ 10 < 9 вьпекает Г < — 1, что противоречит ограничению 1 < Г.
Таким образом, искомых целых чисел ! и г' не существует. П Алгоритм 11.39 описывает, как определить, может ли быть найдено целочисленное решение множества линейных неравенств на основе алгоритма исключения Фурье-Моцкина. Алгоритм 11.39. Решение задачи целочисленного линейного программирования методом ветвей и границ ВХОД: выпуклый многогранник Я„над переменными пг,..., е„. Выход: "да", если Я„имеет целочисленное решение; "нет*' в противном случае. Мптод; выполнить алгоритм, представленный на рис.
11.22. и 1) Применить к Я„алгоритм 11.11 для переменных е„, с„ы..., сг в указанном порядке 2) Пусть Я; — многогранник, полученный после исключения и;~~ для!=и — 1,п — 2,...,0; 3) !!' оо = гл ге!пгп "нет"; !* Рационального решения не существует, если Яо (включающее только константы) содержит неудовлетворимые ограничения *! 4) Гог(г = 1; г < и; !++) ! 5) !!' !о, не включает целое значение) Ьгеа!с; 6) Выбираем сч целое значение в средине диапазона и, в К; 7) ИЗМЕНЯЕМ Ям ЗаМЕНЯЯ Пг На С,; 8) 9) !Г (! == п + 1) ге!пгп "да"; 10) !Г (! == 1) ге!игл "нет"; 11) Пусть нижняя и верхняя границы е; в Я; представляют собой 1, и и, соответственно; 12) Рекурсивно применяем данный алгоритм к 5„1.1 (и, < ~Ц) и к Я„1.! 1п, > ~и,~ ); 13) !!' (любой из вызовов алгоритмов вернул "да") гегцгп "да*' е!ве ге!пгп "нет"; Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
