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

Текст из файла

Новый подход к построению методов межпроцедурного анализа программ

(Работа поддержана грантом РФФИ №96-01-01433)

А.С. Антонов, Вл.В. Воеводин

Введение

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

В данной работе рассматривается новый подход, основанный на анализе свойств графа алгоритма [1,2,3] впервые описанный в [4].

1 Обзор существующих методов межпроцедурного анализа

Одним из первых методов разрешения проблемы межпроцедурного анализа была предложена подстановка тела подпрограммы на место вызова (inline expansion [14]), но она сильно затруднена, если в графе вызовов есть контуры, что приводит к значительному увеличению размера кода и времени анализа. В известных обзорах [5,15] большое внимание уделялось методам межпроцедурного анализа без учета индексных переменных. Но такой анализ является весьма грубым и недостаточным для реальных программ, поскольку в большинстве случаев необходима информация о существовании зависимости между ссылками на отдельные элементы массивов.

Последующее развитие методов межпроцедурного анализа шло по двум направлениям: с одной стороны, уточнение методов нахождения входных и выходных данных подпрограмм, а с другой - описание найденных данных в терминах фактических параметров (обратная подстановка).

В большинстве работ, посвященных межпроцедурному анализу, входные и выходные данные аппроксимируются вырезками массивов, используемыми или изменяемыми в анализируемой подпрограмме. Следуя [9], будем называть такие области READ и WRITE областями. Все методы описания READ и WRITE областей можно разделить на два класса: неточные и точные методы. Неточные методы проще, но, в отличие от точных, описывают только некоторую аппроксимацию необходимой области. Точные же методы могут потребовать много памяти и времени для анализа программ. В некоторых случаях используются комбинированные методы, например, приближенное описание объединения точно описанных областей.

Среди неточных методов получения READ и WRITE областей можно отметить ограниченные регулярные секции (restricted regular sections [8]), описания с помощью триплетов (bounded regular sections [11]), простые секции (simple sections [6]), описание в виде минимальной выпуклой оболочки (convex hull) [9,17]. Из точных методов можно указать подход Бурке-Сайтрона [7] и построение совокупного образа (merged image) [16].

Однако знания READ и WRITE областей недостаточно для полноценного анализа, так как READ области могут содержать данные, вычисленные ранее в исследуемой подпрограмме, а, следовательно, они не будут представлять входных данных анализируемой процедуры. WRITE области могут содержать данные, которые не потребуются нигде в дальнейшем тексте программы, что также не соответствует выходным данным подпрограммы. Для более точного анализа вводятся IN и OUT области, которые представляют именно входные и выходные данные подпрограммы, то есть данные, необходимые для выполнения подпрограммы, и данные, вычисляемые в исследуемой подпрограмме и используемые где-либо далее. Метод получения IN и OUT областей из READ и WRITE областей подробно описан в [9,10].

Методы описания входных и выходных данных подпрограммы в терминах фактических параметров описаны в работах [9,16].

2 Получение входных и выходных данных подпрограмм с помощью графа алгоритма

Использование графа алгоритма, введенного в [1,2,3], позволяет получить точное описание входных и выходных данных фрагмента программы.

Основная идея этого метода заключается в том, чтобы получить описание нужного множества в пространстве элементов массива средствами анализа пространства итераций программы. Если из всей области срабатывания оператора _J [3] вычесть все области _k из описания графа алгоритма фрагмента по входу A_i (напомним, что точки областей _k являются конечными точками дуг графа алгоритма данного фрагмента), то полученная область _inp будет описывать множество точек пространства итераций, в которых A_i потребляет входные для исследуемого фрагмента данные.

Теперь нужно получить описание области пространства итераций _inp в пространстве элементов массива A. Рассмотрим задачу для входа A_i(P(J)) массива A, где P(J) - это векторная функция, определяющая индексные выражения данного входа. Будем предполагать, что для входа A_i найдена подобласть пространства итераций ⁱ_inp, в каждой точке которой аргументом для входа A_i являются начальные данные. По определению данной области, для любой точки Jⁱ_inp элемент массива A_i(P(J)) нигде в данном фрагменте не вычисляется, а берется из входных данных, т.е. является элементом искомого множества.

Cконструируем вспомогательный фрагмент, содержащий вход A₀ по переменной A:

DO I₁ = l₁, u₁

...

DO I_d = l_d, u_d

... = ... A₀(I₁, I₂, ..., I_d) ...

END DO

...

END DO ,

где d - это размерность переменной A, а l_k, u_k - нижняя и верхняя границы k-го измерения массива A соответственно, k=1,d. Будем считать, что данный фрагмент достижим из каждой точки программы и всегда срабатывает последним - этого всегда можно добиться эквивалентным преобразованием фрагмента.

Возьмем любую точку J области ⁱ_inp. Ясно, что элемент массива A_i(P(J))=A_i(p₁(J),...,p_d(J)) принадлежит искомому множеству и надо найти описание всех подобных точек P(J) в пространстве элементов массива A.

Предположим, что в каждой точке J области ⁱ_inp происходит не использование, а определение элемента A_i(P(J)), т.е. вход A_i будет играть роль выхода. Будем считать областью срабатывания оператора, содержащего A_i, не область _J, а область ⁱ_inp. Область срабатывания входа A₀ определяется только границами циклов вспомогательного фрагмента, так как он безусловно достижим из каждой точки программы.

В таких предположениях решим стандартную задачу построения элементарного графа алгоритма A_iA₀ и найдем область , на которой определены дуги графа алгоритма. Особенность множества заключается в том, что, являясь многогранником в пространстве итераций, он одновременно является и описанием множества входных данных в пространстве элементов массива A для входа A_i.

Аналогичным образом данная задача решается для всех входов, а искомое подмножество входных элементов массива A является объединением областей, полученных при решении данной задачи для каждого отдельного входа.

Использование такого метода позволяет получить точное описание IN и OUT областей подпрограммы. Существование эффективных алгоритмов построения графа алгоритма обеспечивает возможность использования этого метода при анализе реальных программ.

3 Описание входных и выходных данных подпрограммы в терминах фактических параметров

Перейдем теперь к решению второй задачи межпроцедурного анализа - описанию входных и выходных данных подпрограммы в терминах фактических параметров. Описываемый здесь метод опирается на [9,16] и требует, чтобы входные и выходные данные подпрограммы уже были описаны в виде системы линейных неравенств.

Пусть в программе есть две подпрограммы P и Q, такие, что:

SUBROUTINE P(...)

DIMENSION A_p(lp₁:up₁,...,lp_p:up_p)

...

CALL Q(...,A_p(op₁,...,op_p),...)

...

END

SUBROUTINE Q(...,A_q,...)

DIMENSION A_q(lq₁:uq₁,...,lq_q:uq_q)

...

END

Пусть элементы массива A_q, представляющие часть входных и выходных данных подпрограммы Q, представлены в виде области _q, описанной с помощью набора линейных равенств и неравенств. Требуется пересчитать эту область в терминах вырезки из соответствующего фактического параметра-массива A_p.

Запишем условие Г_pq того, что два элемента массивов A_p(₁,..., _p) и A_q(₁,..., _q) ссылаются на одну и ту же область памяти:

где .

Тогда пересечение трех областей =_qГ_pq{lp_iiup_i, i =1,p} неявно задает область _p массива A_p, соответствующую области _q массива A_q. Для получения явного описания _p необходимо получить проекцию (p+q)-мерной области на p-мерное подпространство, соответствующее массиву A_p. Это можно сделать с помощью исключений Фурье-Моцкина [12,13], если равенство Г_pq линейно. Определение условий его линейности рассматривается дальше.

Если равенство Г_pq нелинейно, то при некоторых условиях можно получить более простое условие. Если массивы A_p и A_q имеют одинаковое число элементов в первых (d-1) размерностях (то есть {up_i - lp_i = uq_i - lq_i, 1 i d-1}), и {op_i=lp_i, 1 i d-1}, то добавим в описание области равенства {_i - lp_i=_i - lq_i, 1 i d-1} и составим частичное уравнение ранга d:

где .

Это уравнение проще, чем Г_pq, и в реальных случаях может оказаться линейным, в то время как полное уравнение таковым не является. Если количество размерностей с одинаковым числом элементов равно q, но меньше p, то в описание области вместо условия Г^d_pq нужно добавить равенства {_i=op_i, | i=q+1,p }.

Для того, чтобы получить проекцию (p+q)-мерной области на p-мерное пространство, необходимо исключить переменные, введенные для описания _q, из всех равенств и неравенств. Это можно сделать методом Фурье-Моцкина [12,13], если все ограничения, содержащие эти переменные, линейны. Так как в описание _q входят только линейные ограничения, нелинейность по данным переменным может возникнуть только в равенстве Г_pq (Г^d_pq). Кроме того, для проведения дальнейшего анализа программы важно, чтобы все получающиеся ограничения также были линейными. Поэтому нужно выделить условия на внешние переменные, при которых Г_pq (Г^d_pq) будет линейным по всем переменным.

Для этого берем равенство Г_pq (Г^d_pq), приводим в нем подобные, после чего приравниваем к нулю все нелинейные части. Если из получившихся равенств можно выразить переменные, введенные для описания _q, через внешние переменные, и подстановка этих выражений в ограничения вместо переменных не входит в противоречие с заданными ограничениями на внешние переменные, то добавим к равенству Г_pq (Г^d_pq) с зануленными нелинейными частями ограничения {lp_iiup_i|1ip} и {lq_iiuq_i|1iq}. После этого исключаем из получившихся линейных ограничений все переменные, кроме внешних, и получаем искомые ограничения на внешние переменные.

4 Определение параллелизма по графу алгоритма

Циклы, все итерации которых информационно независимы, будем называть PARDO циклами. Независимость итераций сразу говорит о возможности их выполнения в любом порядке, в частности, параллельно. Данный вид параллелизма исключительно важен на практике, прежде всего, в силу простоты использования.

Точное определение информационной структуры программ позволяет точно выделять все PARDO циклы расширенного базового класса программ с помощью следующего критерия. Предположим, что исследуется цикл с параметром i₁.

Для того чтобы цикл обладал свойством ParDo, необходимо и достаточно, чтобы для любой тройки (F_k, _k, N_k) графа алгоритма данного цикла включение _k G_k было верным на множестве N_k, где

G_k - область, задаваемая равенством f₁^k = i₁,

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

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

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