А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 200
Текст из файла (страница 200)
1!.22. Поиск целочисленного решения системы неравенств В строках 1 — 3 алгоритм пытается найти рациональное решение неравенств. Если рационального решения не существует, не существует и целочисленного ре- 975 11.6. Анализ зависимости данных в массивах щения. Если же рациональное решение найдено, значит, неравенства определяют непустой многогранник. Относительно редко в таком многограннике нет ни одной целой точки — это означает, что многогранник должен быть очень тонким вдоль одного измерения и располагаться между целыми точками.
Строки 4 — 9 пытаются быстро определить наличие целочисленного решения. Каждый шаг алгоритма исключения Фурье — Моцкина дает многогранник, у которого на одно измерение меньше, чем у предыдущего. Мы рассматриваем многогранники в обратном порядке, начиная с многогранника с одним измерением и назначая этой переменной целочисленное решение, находящееся примерно посредине диапазона допустимых значений.
Затем это значение подставляется во все другие многогранники, уменьшая тем самым количество переменных в них на 1. Этот процесс повторяется до тех пор, пока не будут обработаны все многогранники. При этом либо будет найдено целочисленное решение, либо будет найдена переменная, для которой целочисленного решения не существует. Если мы не в состоянии найти целочисленное значение даже для первой переменной, значит, целочисленного решения задачи не существует (строка 10).
В противном случае все, что мы знаем, — это то, что нет целочисленного решения, включающего данную комбинацию выбранных целых значений; окончательный вывод о существовании целочисленного решения на основании этих данных сделать нельзя. Строки 11 — 13 представляют шаг алгоритма с использованием метода ветвей и границ. Если переменная п; имеет рациональное решение, но ее целое решение не найдено, разбиваем многогранник на два. В первом требуется, чтобы о; была целым числом, меньшим, чем найденное рациональное решение, а во втором — большим. Если ни один из многогранников на дает решения, зависимостей не существует.
11.6.6 Резюме Мы показали, что существенная часть информации, которую компилятор может собрать из обращений к массивам, представляет собой определенные стандартные математические концепции. Пусть дана функция обращения У = (Е,Г,В,Ь). 1. Размерность области данных, к которым выполняется обращение, определяется рангом матрицы Р. Размерность пространства обращений к одному и тому же месту определяется нуль-пространством Р.
Итерации, разности между которыми принадлежат нуль-пространству Р, обращаются к одним и тем же элементам массива. 2. Итерации с собственным временным повторным использованием обращения отделяются векторами в нуль-пространстве Р. Собственное пространственное повторное использование может быть вычислено аналогично, как 976 Глава 11. Оптимизация параллелизма и локальности ответ на вопрос, когда две итерации используют одну и ту же строку (а не один и тот же элемент).
Два обРашениЯ, Р1~ + Е и Нз + 1з, совместно используют локальность вдоль направления и, если д — частное решение уравнения Ед = (1з — 1з). В частности, если 6 — направление, соответствующее наиболее глубоко вложенному циклу, т.е. представляет собой вектор (0,0,..., О, Ц, то в случае построчного хранения массива имеется пространственная локальность. 3. Задача анализа зависимостей данных — могут лн два обращения обращаться к одним и те же данным — эквивалентна задаче целочисленного линейного программирования.
Зависимости данных имеются, если для двух функций обращения существуют такие целочисленные векторы 1 н 1', что В1 > О, В'1' > 0 и И+1= к'1'+ 1'. 11.6.7 Упражнения к разделу 11.6 Упражнение 11.6.1. Найдите НОД для следующих множеств целых чисел: а) (16,24,56)„ б) ( — 45,105,240); 1 в) (84, 105, 180, 315, 350). Упражнение 11.6.2. Для цикла аког(1 = Оз 1 < 10з 1++) н(1) = А[10 1); укажите все а) истинные зависимости (запись, за которой следует чтение из той же ячейки памяти); б) антизависимости (чтение, за которым следует запись той же ячейки памяти); в) зависимости через выход (запись, за которой следует другая запись в ту же ячейку памяти).
! Упражнение 11.6.3. Во врезке об алгоритме Евклида имеется ряд утверждений, приведенных без доказательства. Докажите следующее. а) Алгоритм Евклида всегда работает. В частности, йсс1 (5, с) = 8сб (а, 5), где с — ненулевой остаток от деления а/5. 977 ! 1.6. Анализ зависимости данных в массивах б) ясс1(а, Ь) = ясс1(а, — 6). в) ясй(ам аз,...,а„) = дед (ясс1 (аз,аз),аз,а4,...,а„) при п ) 2. г) НОД является функцией от множества целых чисел, т.е.
их порядок значения не имеет. Покажите выполнимость закона кольиутативности для НОД: ась (а, 6) = ясб (6, а). Затем докажите более сложный закон ассоциативности: ясд (ясс1 (а, 6), с) = бсср (а, ясб (6, с)). Наконец, покажите, что из этих законов вытекает, что НОД множества чисел всегда один и тот же, независимо от порядка вычисления НОД для пар целых чисел из этого множества. д) Если Я и Т вЂ” множества целых чисел, то йсс)(Я(.)Т) = йсб(йсд(Я)(.)ясй(Т)). ! Упражнение 11.6.4. Найдите другое решение второго диофантового уравнения в примере 11.33. Упражнение 11.6.5. Примените проверку независимых переменных в следую- щей ситуации.
Вложенность циклов представляет собой Гог (1=0; 1<100; 1++) Гог (3=0; 3<100; З++) аког ()<=Оз )с<100з )с++) Внутри вложенности имеется присваивание, включающее обращения к массивам. Определите, имеются ли зависимости данных для каждой из следующих инструкций: а) А[1,3,)с] = А[э.+100,>+100,)с+100]; б) А[з.,3,)с] = А[3+100,)с+100,1+100]; в) А [ з., 3, )с ] = А [ 3 -5 О, )с-5 О, з.-5 О ]; г) А[з.,3,)с] = А[з.+99,)с+100,3].
Упражнение 11.6.6. В ограничениях 1 < г < у — 100 3 < г < 2у — 50 устраните г, заменяя ее константной нижней границей у. Упражнение 11.6.7. Примените проверку вычетов циклов к следующему множе- ству ограничений: 0<г<99 у<т,— 50 0<у<99 г<у — 00 0 < г < 99 978 Глава 11, Оптимизация параллелизма и локальности Упражнение 11.6.8.
Примените проверку вычетов циклов к следующему множе- ству ограничений; О < х < 99 у < х — 50 0<у<99 а<у+50 0<а<99 х<я+20 Упражнение 11.6.9. Примените проверку вычетов циклов к следующему множе- ству ограничений: 0<х<99 у<х — 100 0<у<99 з<у+бО 0 < а < 99 х < г+ 50 11.7 Поиск параллельности, не требующей синхронизации Теперь, когда у нас разработана теория аффинного обращения к массивам, повторного использования данных и зависимостей между ними, пора применить ее к распараллеливанию и оптимизации реальных программ. Как говорилось в разделе 11.1.4, при поиске параллелизма важно минимизировать взаимодействия между процессорами. Начнем с рассмотрения задачи распараллеливания приложения, когда между процессорами нет никакого взаимодействия или синхронизации.
Такое ограничение может показаться чисто академическим примером — как часто можно встретить программы с таким видом параллелизма? Но на самом деле такие программы встречаются в реальности, и алгоритм для решения такой задачи оказывается весьма полезным. Кроме того, концепции, использованные при решении этой задачи, могут быть затем расширены для работы с синхронизацией и взаимодействием процессоров. 11.7.1 Вводный пример На рис.
11.23 приведен фрагмент трансляции на С (с массивами в стиле гогГгап для ясности) 5000-строчного многосеточного алгоритма для решения трехмерных уравнений Эйлера, написанного на гогпап. Большую часть времени программа тратит на выполнение небольшого количества подпрограмм наподобие показанных на рис. 11.23. Это типично для многих численных программ, которые часто состоят из множества циклов 1ог с различными уровнями вложенности, содержащих много обращений к массивам, причем все они представляют собой аффинные выражения от индексов охватывающих циклов.
Чтобы пример был обозримым, мы убрали из исходной программы строки со сходными характеристиками. 11.7. Поиск параллельности, не требующей синхронизации йог (3 = 2; 3 <= 311 3++) йот (1=2, 1 <=11, 1++) ( АР [3, з.) Т = 1.0/(1.0 + АР[3, 1]); 0[2,],з.] = т*АР[3,з.]' пн[1,2,3, 1] = Т*0Х[1,2,3,з.]; йог (К = 3; )с <= )с1-1; )с++) йот (3 = 2; 5 <= 3 1; 3 ++ ) Кот (1 = 21 1 <= 11; 1++) ( Ам[3, 1] = АР[3, 1]; АР [3, з.] т = ...АР[3,'] — Ам[3,1]*0[к-1,3, Р[)с,],з.] = Т*АР[3,1]з 1)и[1,)с,й,з.] = т*(1и[1,)с,3,1] + пи[1,)с-1,3,1])..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
