Диалоговая оболочка системы автоматизации распараллеливания программ (только введение) (848065), страница 2
Текст из файла (страница 2)
1
5 A(I) = … 15
1
6 … = A(I) A, T (T – True Dependence)
16
Система предоставляет возможность редактирования зависимостей, например, можно указать, что зависимости нет, т.е. удалить ее из графа.
После окончания редактирования графа, система предлагает некоторый вариант распределения данных и коммуникаций. Пользователь может внести свои изменения или согласится с предложением системы.
Система CAPO (Computer-Aided Parallelizer and Optimizer) это система автоматического распараллеливания программ для работы на машинах с общей памятью. CAPO встроена в пакет CAPTools, который был разработан в Университете Гринвича, и независимо разработан в Исследовательском центре NASA как один из компонентов для проекта Legacy Code Modernization. CAPTools - это инструментарий для автоматической генерации кода в модели передачи сообщений. CAPTools работает с последовательной программой на языке FOTRAN 77: производит анализ зависимостей, генерирует маски для распределенных массивов и необходимые коммуникации. Ключевые особенности пакета CAPTools состоят в том, что, во-первых, он использует дополнительные методы анализа, поэтому он позволяет получить более точную информацию о зависимостях и более эффективный код, и, во-вторых, CAPTools содержит набор браузеров, которые помогают пользователю влиять на процесс распараллеливания.
Используя информацию о зависимости по данным, полученную при помощи CAPTools, CAPO генерирует директивы OpenMP или SGI для последовательной программы на языке FORTRAN. Основные стадии работы CAPO:
- Распознавание параллельных циклов
- Создание и оптимизация параллельных областей вокруг этих циклов
- Вставка директив OpenMP
Так же, как и Parawise, система CAPO на каждом шаге работы взаимодействует с пользователем, позволяя вносить свои изменения и рекомендации по распараллеливанию циклов, генерации и оптимизации директив.
Одной из основных стадий работы системы автоматизации распараллеливания программ является анализ последовательной программы. Для выявления зависимостей в программе могут применяться статический или динамический методы анализа. Статический анализатор работает с текстом программы на этапе компиляции, в статике. Динамический анализатор выявляет зависимости во время работы программы. В процессе своей работы оба анализатора вырабатывают некоторый набор информации о ходе выполнения программы, которая затем используется для получения параллельного кода программы. Эта информация должна быть передана пользователю, чтобы он мог разобраться в последовательной программе и, возможно, сделать какие-то уточнения или дополнения.
Существенными недостатками обеих рассмотренных систем является то, что обе они производят только статический анализ последовательных программ, который не дает полной картины, поэтому генерация сколько-нибудь оптимального и вообще корректного параллельного кода требует постоянного вмешательства пользователя, уточнений и разъяснений с его стороны. В противном случае нельзя надеяться на получение эффективной параллельной программы.
Динамический же анализ позволяет рассчитывать на достижение более глубокой степени параллелизма, так как в общем случае только в динамике возможно определить, когда и сколько параллельных ветвей возникнет в процессе счета, какие информационные связи будут установлены между ними и какая синхронизация между ними потребуется для их корректного выполнения.
Целью дипломной работы является создание диалоговой оболочки системы автоматического распараллеливания программ, основанной на динамическом анализе.
В основе изучения структуры программ сформировались два подхода. Денотационный подход опирается на исследование состояния памяти и используется редко. Второй подход - операционный. Исполнение любой программы представляется в виде набора выполненных действий, каким-то образом связанных между собой. Этот подход позволяет для каждой программы построить граф, в котором вершины - операторы программы, а дуги - связи между ними. Связи между операторами программы могут быть по управлению или по данным. Связи по управлению показывают факт выполнения одного оператора после другого. Связи по данным связаны с использованием в одном операторе результатов выполнения другого оператора.
Сопоставим каждому оператору программы вершину графа. Проведем дугу между двумя вершинами, если оператор, соответствующий одной из вершин, может выполняться непосредственно после оператора, соответствующего второй вершине. Такой граф обычно называют графом потоков управления. Модифицируя этот граф можно получать другие модели программы, содержащие необходимую информацию.
В процессе динамического анализа программы формируется дерево контекстов. Полученное дерево представляет собой один из вариантов развертывания графа потоков управления. Вершинами этого дерева являются процедуры, циклы, операторы вызова процедуры или доступа к памяти. Циклы выделяются особо, так как имеют большое значение для распараллеливания программы. Корнем дерева является функция main(), основное тело программы или другое аналогичное понятие из используемого языка программирования. Листья соответствуют простым операторам - операторам присваивания. При этом одной и той же строке программы может соответствовать несколько вершин, если эта строка выполняется несколько раз в разных контекстах. Это позволяет однозначно идентифицировать точку выполнения программы на этапе анализа. Дуги в графе представляют собой отношение «вызывается из». Так, например, все операторы, образующие тело цикла являются потомками этого цикла. Также в каждой вершине хранится некоторая информация о выявленных в ходе анализа зависимостях по данным между витками этого цикла и витками вышестоящих циклов.
Одной из задач создания диалоговой оболочки системы автоматизации распараллеливания программ является отображения графа, полученного в результате динамического анализа, в удобочитаемом для пользователя виде.
В процессе распараллеливания программы может появиться необходимость изменить текст программы таким образом, чтобы результаты ее выполнения оказались теми же, но новая программа была бы удобнее для распараллеливания. Например, может возникнуть необходимость разбить цикл на несколько циклов или заменить одномерный массив двумерным. Подобные рекомендации могут появиться после динамического анализа последовательной программы. Отсюда вытекает еще одна задача диалоговой оболочки - это обеспечение автоматической отладки новой версии программы.
Для решения этой задачи можно использовать механизм сравнительной отладки. Сравнительная отладка предполагает сравнение результатов выполнения отлаживаемой программы с ранее полученными эталонными значениями. В данном контексте можно считать эталонными значения, полученные во время работы исходной последовательной программы.
Интерес представляет организация сравнения выполнения двух программ. Одно из решений было реализовано в сравнительном отладчике Guard. Guard изначально создавался для отладки различных версий одной и той же программы. Затем были разработаны версии для сравнительной отладки параллельных программ. Сравнительная отладка различных версий одной программы основана на том, что одна версия признается правильно работающей, и при отладке новой версии результаты работы старой версии можно использовать в качестве эталонных значений, с которыми сравниваются результаты работы новой версии программы. Новая версия может значительно отличаться от старой, однако можно выделить такие точки в программе, где обе программы должны получать один и тот же результат. Сравнительный отладчик Guard требует от пользователя расстановки таких контрольных точек. Например, в разных версиях программы могут использоваться разные алгоритмы решения одной и той же задачи, но результаты должны быть одинаковыми в определенных пользователем точках программы. Сравнение результатов работы двух программ будет производиться в этих точках.
Отладчик Guard реализует данный подход следующим образом: пользователь отмечает в программах контрольные точки, программы выполняются под контролем отладчика до тех пор, пока не встретится контрольная точка. В этих точках выполнение программ приостанавливается, и отладчик сравнивает указанные пользователем переменные. Любое расхождение результатов считается ошибкой в отлаживаемой программе. Если обнаружена ошибка, создается соответствующий отчет, если ошибок нет, то выполнение программ продолжается. Данный подход достаточно прост в реализации и избавляет пользователя от рутинного сравнения результатов разных программ вручную.
В дипломной работе для сравнения результатов выполнения двух программ используются трассировки программ, полученные при помощи отладчика, входящего в состав DVM-системы. Он позволяет получать трассировки, как для последовательных программ, так и для DVM-программ. Пользователь должен вручную указать отладчику, какие переменные в новой версии программы соответствуют другим переменным в изначальной версии, указать линейные выражения для установления соответствия между индексами старых и новых массивов, если изменилась размерность. Например, если одномерный массив был заменен двумерным - это должно быть указано. Затем отладчик сравнивает результаты выполнения двух программ, которые отражены в трассах, используя информацию о соответствии между переменными.
Для реализации диалоговой оболочки используется библиотека Qt. Qt - библиотека классов C++, предоставляющая разработчикам все функциональные возможности, необходимые для создания приложений с графическим интерфейсом пользователя.
Литература:
1. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб.: БХВ-Петербург, 2004. 608 с.
2. Головкин Б.А. Вычислительные системы с большим числом процессоров. М.: Радио и связь, 1995. 320 с.
3. Документация к системе DVM. http://www.keldysh.ru/dvm
4. Информационно-аналитический центр по параллельным вычислениям http://parallel.ru/
5. Антонов А.С. Введение в параллельные вычисления. М.: Издательский отдел научно-исследовательского вычислительного центра МГУ, 2002. 69 с.
6. А. А. Букатов, В. Н. Дацюк, А. И. Жегуло. Программирование многопроцессорных
вычислительных систем. Ростов-на-Дону: Издательство ООО «ЦВВР», 2003, 208 с.
7. Abramson D., Foster, I., Michalakes, J. and Sosic R. Relative Debugging: A new paradigm for debugging scientific applications. The Communications of the Association for Computing Machinery (CACM), Vol 39, No 11, pp 67 - 77, Nov 1996
8. Sosic R., Abramson D. A. Guard: A Relative Debugger. Software Practice and Experience, Vol 27(2), pp 185 206 (Feb 1997)
9. Abramson D.A., Sosic R. Relative Debugging using Multiple Program Versions. Key Note Address, 8th Int. Symp. on Languages for Intensional Programming , Sydney, 3-5th May, 1995. In Intensional Programming I, World Scientific, ISBN 981-02-2400-1.
10. Документация к системе ParaWise (http://www.parallelsp.com/documentation.htm)
11. Документация к системе CAPO
(ftp://keldysh.ru/K_student/AUTO_PARALLELIZATION/CAPO)
- 8 -
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
