Т. П. Баранова, В. Ю. Вершубский, К. Н. Ефимкин, В. А. Федосимов
Развитие вычислительной техники за последнее десятилетие привело к появлению довольно большого числа многопроцессорных вычислительных установок. Доступность этих установок для пользователей, в свою очередь, породила интерес к преобразованию накопленных за прошлые годы больших программ, созданных для последовательных машин, в эффективные “параллельные” программы, пригодные для работы на многопроцессорных системах. Как правило, такое распараллеливание пока производится “вручную”, и в случае успеха приводит к значительному увеличению скорости решения вычислительных задач.
Работы по созданию систем, автоматизирующих в той или иной степени преобразование последовательных программ в параллельные, ведутся давно, и в настоящее время интенсивность таких исследований не снижается (Vray [1], Parawise [2], POLARIS [3], SUIF [4], ОРС [5] и др.). Это положение связано, по-видимому, с тем, что решить проблему автоматического распараллеливания программ в приемлемых, с практической точки зрения постановках, пока не удается, а средства автоматизации процесса распараллеливания требуются. С этой точки зрения, средства анализа, помогающие человеку разобраться в структуре последовательной программы, и облегчающие ее преобразование в параллельную, представляются весьма полезными. Тем более что часто анализ и преобразование последовательных программ в параллельные осуществляют не те, кто первоначально эти программы создавал, и проблема восприятия программ большого размера может стать решающей с точки зрения трудозатрат.
Решение попытаться создать средство (статический анализатор программ, написанных на Фортране), облегчающее “ориентирование” в больших программах возникло при выполнении в ИПМ им. М.В.Келдыша РАН работ по распараллеливанию практических расчетных задач, например, [6-8]. Одним из основных требований к анализатору было требование обеспечить навигацию, в широком смысле, по программам большого размера, с показом свойств программы полезных человеку для понимания того, как программа устроена, в том числе и для принятия решений о распараллеливании. Примером такой информации является, например, информация об определении-использовании массивов в рамках программной единицы или всей программы, классификация индексных выражений (со смещением-константой, линейные выражения, косвенная адресация и т.п.) в рамках программной единицы или всей программы. Конечно, анализатор должен определять и традиционные свойства программы, полезные при распараллеливании – свойства циклов, зависимости в циклах и т.п.
В качестве базы для создания анализатора выбран пакет
программ SAGE, являющийся продуктом совместной деятельности
сотрудников индианаполисского университета
(США) и орегонского университета (Канада). Пакет SAGE состоит из парсера (программы, преобразующей
текст исследуемой программы в граф), и набора инструментальных программ,
позволяющих осуществлять навигацию по графу, исследовать отдельные элементы
графа и вносить в граф изменения. Этот механизм оформлен в виде библиотеки классов,
отражающих основные сущности исследуемой программы: предложения, выражения,
типы данных, символы, а также производных классов, соответствующих
разновидностям этих сущностей. Программы SAGE ориентированы
на UNIX в режиме консоли. Пакет программ SAGE пришлось
подвергнуть некоторой адаптации, в частности, для работы в операционной среде Windows 2000 и для обеспечения оконного, графического,
интерактивного интерфейса с пользователем.
Результаты этой работы изложены в [9]. Для данной работы была использована версия
SAGE 1.9 от 05.1995
[10].
В настоящее время разработана первая версия анализатора для программ, написанных на языке Фортран 77 [11]. Его работа проверялась на нескольких больших проектах, имеющих размеры порядка десятков тысяч предложений исходного текста. Ниже приведены примеры сведений о последовательной программе, предоставляемых анализатором по запросу пользователя.
Информация о проекте “в целом”. Во-первых, это перечень описанных в проекте программных единиц. Эта информация представлена в отдельном окне в левой части экрана. Главная программа, процедуры и функции представлены разными цветами. Отмечены программные единицы, описанные в проекте, но не востребованные программой. Во-вторых, это сведения обо всех COMMON переменных, использованных в проекте, т.е. имена COMMON-блоков и входящих в них переменных. В-третьих, это граф вызовов программных единиц, который может быть выдан по требованию. При этом по указанию пользователя из этого графа могут быть исключены (для разгрузки графа) определенные программные единицы (например, встроенные или библиотечные функции). Граф вызовов может быть построен как от главной программной единицы – PROGRAM, так и от любой другой (описанной в проекте) по выбору пользователя. Кроме того, по поводу проекта “в целом” можно запросить поиск программных единиц, содержащих описание массивов заданной размерности, содержащих метки, на которые нет ссылок, содержащих операторы ввода-вывода.
Информация об описанной в проекте программной единице. Если пользователь указывает в упомянутом выше окне конкретную программную единицу, то ему в правой части экрана сразу предоставляется следующая информация: в отдельном окне текст программной единицы, в другом окне описанные в программной единице переменные и именованные константы. Константы предъявляются вместе с их значениями. Переменные отмечены значками разного цвета соответственно “природе” переменной: COMMON-переменная, формальный параметр, локальная переменная. По каждой переменной, используя запросы в контекстном меню, можно получить дополнительные сведения, например, способ объявления типа переменной: явно, в предложении IMPLICIT или неявно. Вид переменной: скаляр или массив. Для массива - его размерность и размеры по каждому измерению. Для COMMON-переменной имя соответствующего COMMON-блока и позиция переменной в описании блока.
Для программной единицы можно получить все обращения к ней со стороны других программных единиц проекта в виде строк вызова с фактическими параметрами. При этом возможна проверка соответствия формальных и фактических параметров. Можно получить сведения о том, является ли формальный параметр выходным, и если является, то в каких точках проекта (программная единица - предложение) ему присваивается значение. Аналогично можно получить сведения о точках присваивания значения для указанной переменной. Можно получить перечень всех обращений к другим программным единицам из данной программной единицы.
Для данной программной единицы можно получить список использованных в ней меток, список “лишних” меток, т.е. меток, на которые нет ссылок, список описанных, но не использованных переменных. Можно получить список предложений данной программной единицы, ссылающихся на заданную метку.
Для данной программной единицы можно получить матрицу достижимости предложений, составляющих ее тело и список определяющих вхождений для скаляра или имени массива в правой части выражения.
В отдельном окне предъявляются циклы DO, обнаруженные в данной программной единице. При этом структура циклов может быть отображена в свернутом виде, когда показаны только внешние заголовки циклов гнезд, в развернутом виде, когда показаны заголовки всех циклов гнезд, или в частично развернутом виде. Если указать в этом окне какой-либо цикл, то соответствующие ему строки текста будут отмечены в окне, содержащем текст программной единицы. Для тела указанного цикла DO возможен поиск приватных скаляров и предложений редукции.
В пакет SAGE входит программный механизм, осуществляющий поиск зависимостей при помощи Омега теста. Реализация этого механизма опирается на работы, выполненные в мерилендском университете [13]. Это средство позволяет для гнезд циклов DO умеренного размера (не более 50 циклов) получать зависимости для переменных внутри гнезда с указанием на исток и сток зависимости и вектор расстояния между истоком и стоком. Кроме того, это средство предоставляет разложение индексов для элементов массива, использованных на запись или на чтение внутри гнезда циклов, если индексы представляют собою линейные формы. К сожалению, данная версия Омега теста обладает значительными ограничениями, например, отказывается исследовать циклы с отрицательным шагом.
Анализатор предназначен для работы с большими программами, имеющими размер в десятки тысяч предложений исходного текста и часто использующими условную трансляцию, то есть содержащими директивы препроцессора. Такие программы требуют определенной подготовки для последующего анализа. Программа, использующая директивы условной трансляции (содержащая строки, начинающиеся со знака #) должна быть до предъявления ее парсеру пропущена через препроцессор. Строки директив препроцессора могут содержать в начале пробелы или знаки табуляции, что некоторые препроцессоры не принимают. Кроме того, ряд препроцессоров искажают некоторые русские буквы (в строках комментария). Часто Фортран-программа содержит предложения INCLUDE. Обычно включаемые файлы содержат объявления переменных. Парсер SAGE обрабатывает программы с предложениями INCLUDE, однако работать с такими файлами неудобно. Поэтому предпочтительнее осуществлять слияние текстов основного и включаемых файлов отдельным актом при помощи специальной программы. Большие производственные программы после слияния основного и включаемого текстов “разрастаются” еще больше. Работать с таким текстом трудно. Желательно разделить его на файлы меньшего размера, однако так, чтобы эти файлы содержали целое число программных единиц. Для преодоления этих технических затруднений нами была создана “технологическая оснастка” в виде четырех отдельных небольших консольных программ, которые в случае необходимости могут работать конвейером.
Возможности статического анализатора планируется развивать в следующих направлениях:
· расширение возможностей определения информационных зависимостей между переменными,
· оптимизация алгоритмов анализа программы при работе на графах,
· движение в сторону межпроцедурного анализа,
· определение интерфейсов с программным экспертом, осуществляющим распараллеливание на различные параллельные архитектуры в рамках работ по созданию системы автоматизированного распараллеливания программ на языке Фортран [13].
Работа выполнена при частичной поддержке в рамках гранта Президента РФ № НШ‑383.2006.9.
1. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления – СПб.: БХВ-Петербург, 2002.
2.
S.Johnson,
H.Jin and C.Ierotheou. “The Para WiseExpert Assistant – Widening Accessibility
to efficient, Scalable Tool Generated
Open MP Code”. Proceedings of WOMPAT 2004, (2004). (www.parallelsp.com)
3.
http://polaris.cs.uiuc.edu/newhome.
4.
www-suif.stanford.edu/research.
5. Открытая распараллеливающая система. http://ops.rsu.ru/about.shtml
6. А.Н. Андрианов, А.В. Березин, А.С. Воронцов, К.Н. Ефимкин, М.Б. Марков. Моделирование электромагнитных полей радиационного происхождения на многопроцессорных вычислительных системах. Препринт ИПМ им. М.В.Келдыша РАН, N74, 2006, 20c.
7.
А.Н. Андрианов, С.Б. Базаров, А.Б. Бугеря, П.И.
Колударов, И.М. Набоко. Фокусировка взрывных волн: моделирование на
параллельных компьютерах. Химическая физика, т.25, N11, 2006, с.54-59
8.
Андрианов А.Н., Ефимкин К.Н. Подход к
параллельной реализации численных методов на неструктурированных сетках. Журнал
Вычислительные методы и программирование, http://srcc.msu.su/num-meth/,
т.8, 2007, с.6-17.
9. Т.П.
Баранова, В. Ю. Вершубский. Использование библиотеки классов пакета “SAGE” для анализа программ,
написанных на языке Фортран. Препринт Института прикладной математики им. М. В.
Келдыша РАН № 69, Москва, 2004, 30 стр.
11. Т.П. Баранова, В. Ю. Вершубский. Анализатор программ, написанных на языке Фортран. Препринт Института прикладной математики им. М. В. Келдыша РАН № 124, Москва, 2005, 27 стр.
12. www.cs.umd.edu/projects/omega
13. М.С. Клинов. В.А. Крюков. Система автоматизированного распараллеливания программ на языке Фортран. DVM-эксперт. // Тезисы докладов, Научный сервис в сети Интернет: многоядерный компьютерный мир, сентябрь 2007 г., г. Новороссийск.