автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Аналитические и инструменатльные средства исследования тонкой структуры программ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. М.В. ЛОМОНОСОВА

Факультет вычислительной математики и кибернетики

9 | ]/',р 7 На правах рукописи

ВОЕВОДИН Владимир Валентинович

АНАЛИТИЧЕСКИЕ И ИНСТРУМЕНТАЛЬНЫЕ СРЕДСТВА ИССЛЕДОВАНИЯ ТОНКОЙ СТРУКТУРЫ ПРОГРАММ

Специальность 05.13.11 — математическое и программное обеспечение вычислительных мащин, комплексов, систем и сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора физико-математических наук

Москва, 1997

Работа выполнена в Научно-исследовательском вычислительном центре Московского государственного университета им. В.М.Ломоносова

Официальные оппоненты: член-корреспондент РАН, профессор Г.Г. РЯБОВ, доктор физико-математических наук, профессор А.Н. ТОМИЛИН, доктор физико-математических наук, профессор A.M. ПОПОВ.

Ведущая организация: Институт прикладной математики РАН им. М.В.Келдыша.

Защита диссертации состоится ^Л^^Го.— ^997 года в ц часов

на заседании специализированного Совета Д 053.05.38 при Московском государственном университете им. М.В.Ломоносова по адресу: 119899, ГСП, Воробьевы горы, МГУ, факультет ВМиК, аудитория 685.

С диссертацией можно ознакомиться в библиотеке факультета вычислительной математики и кибернетики МГУ.

Автореферат разослан 1997

года.

Ученый секретарь Специализированного

совета, профессор ^^ Н.П. ТРИФОНОВ

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Стремительное развитие суперкомпьютеров и параллельных вычислительных систем позволило совершить радикальный прорыв в численном решении крупнейших прикладных проблем в таких областях как нефте- и газодобыча, автомобилестроение, сейсморазведка, прогноз погоды, моделирование биологических процессов, новых химических соединений и т.д. Реальность сегодняшнего дня такова, что с появлением массивно-параллельных компьютеров исчезли многие принципиальные проблемы на пути существенного увеличения пиковой производительности вычислительной техники. Уже сейчас готовится техническая база для создания сверхмощных вычислительных систем и разрабатываются проекты решения сверхсложных прикладных проблем. Именно поэтому США приняли общенациональную программу " Высокопроизг водительные вычисления и коммуникации" (High Performance Computing and Communications). Аналогичная программа находится на рассмотрении Европейского Сообщества, активно стимулирующего применение параллельных компьютеров для решения сложных и важных задач. Соответствующая деятельность идет и в нашей стране.

Однако стремительное развитие вычислительной техники сопровождается не менее стремительным ростом трудностей ее использования. Недостаточное внимание к их преодолению приводит к снижению реальной производительности по сравнению с пиковой в десятки, сотни, а иногда и тысячи раз. Доступными для пользователей средствами повышения реальной производительности на конкретных задачах является лишь разработка новых методов решения задач и реструктурирование реализующих их программ. Поэтому для параллельных компьютеров проблема создания эффективного программного обеспечения становится актуальной. Председатель комитета по параллельным вычислениям, средствам связи и информационным технологиям при президенте США Кен Кеннеди (Ken Kennedy) в одном из своих интервью признал: "Мы подошли к осознанию того, что основная проблема параллельных вычислений— это, прежде всего, проблема создания эффективного программного обеспечения". Резюме третьего семинара по параллельным вычислениям в корпорации Fujitsu (г.Кавасаки,

Япония) сформулировано следующим образом: "Несмотря на то, что заголовки газет пестрят объявлениями о новых возможностях аппаратуры, именно разработка эффективного программного обеспечения и реальных приложений, в конечном счете, и определяют успех новых параллельных компьютеров".

Если фиксирован метод решения конкретной прикладной проблемы, то единственным средством достижения максимально возможной скорости его реализации на любом конкретном параллельном компьютере остается реструктуризация программы, описывающей данный метод. Целью реструктуризации является выбор такого порядка вычислений, который сохранял бы эквивалентность получаемых результатов, но был бы при этом наиболее согласован с требованиями архитектуры компьютера. Частично такую реструктуризацию осуществляет компилятор. В силу ограниченности используемых компилятором методов она редко бывает удовлетворительной. Поэтому основная работа по модернизации программы под требования целевого компьютера традиционно возлагается на пользователя.

Для облегчения выполнения этой работы уже давно создаются автономные программные системы (Rn, Parafrase, PIPS, FORGE, препроцессоры КАР, VAST и другие). Как правило, они реализуются на инструментальных ЭВМ и могут функционировать независимо от целевого компьютера. Несмотря на значительное число подобных систем, проблема поиска модификации программы, обеспечивающей достаточно высокую реальную производительность компьютера на конкретной программе, все еще остается далекой от решения. В конечном счете, ее решение определяется тем, насколько точно позволяют устанавливать информационные связи между отдельными операциями методы анализа структуры программ, включаемые в автономные системы.

Все разработанные до настоящего времени системы в качестве методов такого анализа используют тесты или критерии, определяющие достаточные условия информационной независимости множества операций (GCD тест, неравенство Банерджи, Л-тест, Delta-тест, метод Шостака, метод Фурье-Моцкина и т.п.). В создание подобных тестов вовлечено большое число специалистов (M.Wolfe, D.Kuck, K.Keimedy, R.Allen, J.Hennessy,

M.Lam, W.Pugh, U.Banerjee и другие) и эта деятельность продолжает развиваться. Однако использование достаточных критериев в системах анализа и преобразования программ имеет целый спектр серьезных недостатков. Все критерии с широкой областью применения очень грубы. Более или менее точные критерии всегда имеют очень узкую область применения. Для анализа многих достаточно простых ситуаций критерии просто отсутствуют. В этих условиях существующие системы анализа и преобразования программ не дают и принципиально не могут дать гарантий того, что ненахождение того или иного свойства или преобразования программы действительно означает их несуществование. Попав в подобную ситуацию, пользователь системы не получает никакой информации о том, что делать дальше: разрабатывать новый метод решения задачи, попытаться каким-то образом искать узкие места программы или воспользоваться другой системой для анализа структуры программы.

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

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

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

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

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

Разработка новой методологии исследования программ позволила предложить новые принципы построения инструментальных систем для изучения и визуализации тонкой структуры программ. Одна из таких систем, получившая название V-Ray System, работает на платформах Microsoft Windows и X Window. Эта система апробирована на большом числе реальных программ. Программы, на основе полученных сведений об их структуре, модифицировались под требования архитектуры различных современных параллельных компьютеров и супер-ЭВМ (CRAY EL, CRAY Y-MP C90, IBM SP2, CRAY T3D и других). Дополнительное ускорение, получаемое только за счет использования данной информации, достигало на разных программах 2-10 раз и более. Отметим, что вся модификация программ осуществлялась только на уровне языка высокого уровня без

использования ассемблерных вставок и обращений к высокоэффективным библиотечным программам.

Практическая значимость. Описанные в диссертации новая методология выявления многоступенчатой иерархической структуры больших программных комплексов и новые принципы построения инструментальных систем для изучения и визуализации тонкой структуры программ могут быть применены для достижения различных практических целей. Многоцелевое применение объясняется их независимостью от архитектуры целевого компьютера.

Основное применение связано с созданием автономных систем для изучения информационной структуры программ, в особенности тонкой структуры на уровне связей между отдельными операциями. Такие системы могут быть использованы для обнаружения узких мест программ по параллелизму вычислений, использованию памяти, точности вычислений, их избыточности и т.п. Знание узких мест программ дает возможность их устранить и построить новые, более эффективные параллельные методы. Привлечение сведений об архитектуре конкретных параллельных компьютеров позволяет автоматизировать процесс преобразования программ под требования этих компьютеров.

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

Одной из серьезных существующих проблем является создание порта-бельного численного программного обеспечения для параллельных компьютеров и супер-ЭВМ. Возможность исследования информационной структуры программ до их реализации открывает перспективы решения задачи портабельности, по крайней мере, для конкретных классов компьютеров, например, для SMP компьютеров, имеющих несколько скалярных и/или векторных процессоров, работающих над общей памятью, массивно-параллельных компьютеров, кластеров и сетей рабочих станций.

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

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

Апробация работы. Основные положения работы обсуждались на научно-исследовательских семинарах кафедры АСВК факультета ВМиК МГУ, НИВЦ МГУ, ИВМ РАН, на объединенном научно-исследовательском семинаре кафедр автоматизации систем вычислительных комплексов, алгоритмических языков и системного программирования факультета ВМиК МГУ, на российско-французском семинаре "Теоретическое и численное исследование атмосферной и океанической циркуляции" (Москва, 1996), на совместном семинаре Государственного комитета по науке и технологиям Российской Федерации и IBM (USA).

Результаты диссертации докладывались на П-й Всесоюзной конференции по актуальным проблемам информатики и вычислительной техники (Ереван, 1987), на международной конференции "High Performance Computing in the Geosciences" (Франция, 1993), на 1-ой и 2-ой международных конференциях "Программное обеспечение для многопроцессорных систем: теория, практика, опыт" (Москва, 1993,1994), на международном симпози-

уме "High Performance Computing" (Phoenix, Arizona, USA, 1995), на Ломоносовских чтениях в МГУ (1995, 1996), на семинарах в компаниях Thinking Machines (USA), CRAY Research Inc. (USA), Intel Corp. (USA), опубликованы в трудах международного семинара "Workshop on Numerical Analysis and Applications" (Russe, Bulgary, 1996) и 22-й международной конференции "Euromicro Conference" (Prague, 1996).

Публикации. По теме диссертации опубликовано 27 работ, в том числе одна монография.

Структура и объем диссертации. Диссертация состоит из введения, четырех частей, заключения и списка литературы (175 наименований); изложена на 207 страницах, включает 33 рисунка и 14 таблиц.

СОДЕРЖАНИЕ РАБОТЫ

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

Во введении обосновывается актуальность темы и дается обзор содержания диссертации.

В первой части рассматриваются различные вопросы, связанные с информационной структурой программ. Во введении к ней обсуждается проблема оптимизации программ для компьютеров с параллельной архитектурой. Констатируется, что используемые в настоящее время критерии для обнаружения параллелизма в программах, такие как GCD тест, неравенство Банерджи, А-тест, Delta-тест, метод Шостака, метод Фурье-Моцкина и другие лишь в небольшом числе случаев позволяют получить более или менее достоверные результаты. Делается вывод, что изучение архитектуры компьютеров влечет за собой изменение характера задач в исследовании программ и, следовательно, изменение модели исследуемых программ. Теперь необходимым становится построение истории реализа-

ции: операционной, информационной или какой-либо другой, определяемой спецификой конкретной задачи исследования программы.

Раздел 1 начинается с подробного анализа методов формального описания программ. В рамках операционного подхода исследуется структура множества графовых моделей программ, показала взаимосвязь операционных и информационных моделей, конечных моделей и историй. Исходя из специфики исходной задачи, в качестве основы для всей последующей работы выбирается информационная история выполнения программ. Ориентация именно на данный вид моделей является принципиально важным моментом, так как исследование тонких свойств программ требует описания их структуры с точностью до отдельных срабатываний отдельных операторов. Дано описание программ базового класса, для которых существует алгоритм построения компактной формы представления их информационной структуры на основе анализа только исходного текста.

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

Ясно, что на практике далеко не все программы или их фрагменты принадлежат базовому классу. Именно поэтому, для расширения множества анализируемых программ, разработаны методы обработки фрагментов специальной структуры (раздел 3). Это позволило значительно расширить базовый класс, дополнив его фрагментами, содержащими альтернативные операторы (обобщенное название для разного рода условных операторов, переключателей и т.п.) с вычисляемыми условиями, фрагментами, содержащими обращения к подпрограммам и/или вызовы функций

типа MIN/MAX в стандартной линейной форме.

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

Для базового и/или расширенного класса программ все истории имеют унифицированное описание, в котором для каждого входа каждого оператора программы указывается конечное число троек (Fi, Д*, Nt). N,t — линейный многогранник в пространстве fix внешних переменных программы, значения которых на момент построения графа неизвестны. Д* — линейный многогранник в пространстве итераций П/, размеры и положение которого могут зависеть от точек мпогогранника N¡.. Функция F* линейная и имеет вид F* = JkX + Ф¡.N, где N — это вектор внешних переменных программы, a. J¡¡, Фк — целочисленные матрицы. Областью определения функции Fk является многогранник Д*. Значениями функций являются точки пространства итераций, причем точка х задает конечную вершину дуги, а выражение J¡.x + Ф*АГ — начальную.

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

базового класса программ с помощью следующего критерия:

Для того чтобы цикл обладал свойством РагБо, необходимо и достаточно, чтобы для любой тройки графа алгоритма данного цикла включение Д* С было верным на множестве N1, где вк — область, задаваемая равенством /* = ¿1, /* — первая компонента векторной функции ^ из тройки.

Разработан эффективный алгоритм, позволяющий проверять указанное включение, и, следовательно, определять независимость итераций циклов.

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

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

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

от внешних переменных. Данная задача имеет целый спектр приложений на практике, начиная от определения параллельной структуры всей программы целиком, поддержки корректности содержимого кэш-памяти в многопроцессорных системах (cache coherence problem) и заканчивая возможностью статического контроля выхода за границы массивов.

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

Нужно отметить, что выполненный анализ архитектуры параллельных компьютеров необходим по многим причинам. Он сразу же позволяет точно представить, что в каждой конкретной архитектуре или даже в целом классе архитектур может служить препятствием для достижения пиковой производительности. Например, в архитектуре компьютеров CRAY Y-MP С90 было выделено 10 узких мест, и все они одновременно, в той или иной мере, влияют на каждую программу. В самом деле, программы не бывают векторизуемыми на все 100%, вместе с этим обязательно будет присутствовать какое-то число конфликтов в памяти плюс, быть может легкая, несбалансированность в использовании функциональных устройств, для части операций может не хватать каналов чтения/записи и т.д. Если предположить, что влияние каждого отдельного фактора таково, что позволяет достичь 85% пиковой производительности, то их суммарное воздействие снизит реальную производительность менее, чем до 20% от пика.

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

DO k = 1,1000 DO j = 1,40 DO ¿ = 1,40

A(i,j,k) = A(i~\,j,k) + B(j,k) + B(j,k)

ENDDO

ENDDO

ENDDO

Рис. 1.

DO i = 1,40,2 DO j = 1,40 DO it = 1,1000

A(i,j,k) = A(i-l,j,k) + 2*BU,k)

A(i+\,j,k) = A{i,j,k) + 2* B(j,k)

ENDDO

ENDDO

ENDDO

Pue. S.

та на рис.1, на котором векторно-конвейерный компьютер CRAY Y-MP С90 дает 20 Mflop/s, к эквивалентному ему фрагменту на рис.2, на котором этот же компьютер уже имеет производительность 700 Mflop/s.

Третья часть посвящена Описанию разработанных инструментальных программных средств. Среди них центральное место занимает система V-Ray — система для анализа и визуализации структуры последовательных программ на языке Фортран. Она построена в строгом соответствии с основными принципами теории и технологии, описанными в разделах 1 и 2, и представляет собой эффективное средство, значительно облегчающее процесс адаптации программ к компьютерам с параллельной архитектурой. В настоящее время система V-Ray работает на двух платформах: Microsoft Windows и X Window, на компьютерах в стандартной конфигурации.

Исследование всех программ, выполненное как в процессе экспериментов, так и во время участия в различного рода проектах, были успешными во многом благодаря данной системе. Одна из исследованных программ содержала около 37 тысяч строк на языке Фортран в 490 подпрограммах и функциях — трудно представить, как без описанного программного инструментария можно было бы выполнить ее анализ.

В основу системы заложены три главных принципа: анализ на основе строгой математической теории, возможность исследования структуры фрагментов с разной степенью детальности и визуализация структуры программы на всех стадиях анализа. Ориентация на использование строго математического подхода, изложенного в части I, гарантирует точность проведения анализа. Развитые средства визуализации и возможность упра-

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

Система V-Ray воспринимает на входе текст программы на языке Фортран 77, дополненный элементами Фортрана 90, переводит его во внутреннее представление, по которому и определяет всю необходимую для дальнейшего анализа информацию. Особенностью основных этапов предварительной обработки программ, описанных в разделе 9, является то, что „практически весь последующий анализ опирается на исследование графовых структур: графа управления процедуры, расширенного и классического графа вызовов подпрограмм и функций, процедурного графа управления, дерева циклов (по сути дела это иерархическая система графов) и других. Этим, частично, объясняется как большое число предварительных этапов, так и ориентация на специфические внутренние структуры данных, поддерживающих одну из основных идей подхода — последовательное продвижение от общей структуры программы к локализации и детальному анализу ее "критических" фрагментов.

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

Для решения этой задачи V-Ray поддерживает целый спектр как традиционных, так и принципиально новых структур, описывающих различные свойства программ (раздел 10). Ориентация на анализ больших программных комплексов потребовала разработки различных способов визуального представления одних и тех же объектов и поддержки развитых средств

работы с ними.

В соответствии с общей стратегией анализа, сначала рассматриваются формы представления структуры программы на межпроцедурном уровне, затем макроструктура отдельных процедур, и в конце — микроструктура на уровне отдельных срабатываний операторов. Рассмотрим некоторые из них, останавливаясь более подробно лишь на нетрадиционных формах.

Простейшая форма графа вызовов процедур является традиционным объектом, помогающим получить первое представление о структуре программы. Каждой программной единице соответствует отдельная вершина, причем вершины А и В соединяются направленной дугой А —> В только в том случае, если процедура А содержит вызов процедуры В.

Основной недостаток графа вызовов заключается в том, что по выходящим дугам нельзя определить ни общего числа вызовов каждой конкретной процедуры (между любыми двумя вершинами не может быть кратных дуг), ни порядка, в котором вызовы следуют по тексту программы. Чтобы решить эту проблему, система поддерживает построение расширенного графа вызовов. Данный объект сложнее обычного графа вызовов, но он намного информативнее и свободен от указанных недостатков.

Много дополнительной информации можно получить, изменяя способ изображения графов или используя разметку вершин. Например, с помощью одного из способов разметки можно сразу найти начальные процедуры проекта (т.е. программные единицы, которые сами ниоткуда не вызываются). Следовательно, можно найти и те процедуры, которые когда-то были включены в проект, но по какой-либо причине сейчас не используются — они также будут помечены как начальные. В одном из проектов, содержащем около 490 процедур, таким образом было обнаружено более 80 (!) неиспользуемых подпрограмм.

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

10 : (GCMA3 Д DYNIMP1 -i RHSHLM' -Л FILTR31 -i FLX21 Л FFFT1 -1 PASS4) 10 : (GCMA* Д DYNIMP1 -1 HHSOLV3 -i GAUSPH' -i SINGL3) 8 : (GCMA3 Д RADFL24 -i RADFSW3 Л VARP84) Л DELED31 7 : (GCMA3 Д DYNIMP1 -i DYNADD1 Л ADDTPR' -i MMATRl2)

Конструкция вида Xa У3, используемая в качестве основного элемента каждого пути, означает следующее: процедура X вызывает процедуру Y в 7-мерном цикле, причем максимальная глубина вложенности циклов в самих процедурах X я Y равна а и /3 соответственна. Если X содержит несколько вызовов Y, то на месте 7 будет указано максимальное значение.

Ясно, что интерес представляет как значение а, так и 7 + (3. Самая левая колонка показывает максимальную суммарную вложенность циклов по каждому пути, а скобками отмечена та цепочка пути, на которой достигается указанное значение. Поскольку все пути отсортированы по убыванию данного суммарного показателя, среди всех путей можно сразу выделить наиболее "тяжелые" в качестве кандидатов для детального анализа.

Чтобы оценить возможное взаимодействие процедур проекта через объекты общей памяти, а для Фортрана это COMMON-блоки, строится граф использования общей памяти. Данный граф является двудольным графом, в котором одно множество вершин составляют процедуры, а другое — объекты общей памяти. Вершины разных множеств соединяются дугой тогда и только тогда, когда соответствующая процедура имеет доступ к соответствующему объекту общей памяти.

Для представления структуры отдельных процедур используется иерархическая система графов. Граф верхнего уровня показывает структуру процедуры в целом и состоит из вершин двух типов: вершины одного типа соответствуют самым внешним циклам процедуры, а вершины другого — линейным участкам между ними. В любом из этих графов две вершины А и В связываются направленной дугой А —> В тогда и только тогда, когда фрагмент В может быть выполнен сразу после фрагмента А, т.е. данный вид графа является модификацией графа управления. Поскольку каждый из циклов может представлять интерес для самостоятельного

анализа, то поддерживается построение аналогичных графов на всех последующих уровнях с детализацией структуры составных вершин вплоть до отдельных линейных участков.

Для проведения более детального анализа используются два классических графа управления. В первом все макровершины текущего фрагмента ' раскрываются вплоть до отдельных линейных участков, а во втором — до отдельных операторов. Эти способы представления активно используются во время детального исследования информационной структуры отдельных фрагментов программ.

Если в графе управления некоторого фрагмента оставить только те вершины, которые содержат обращения к другим подпрограммам и функциям, то получим редуцированную форму графа управления, названную процедурным графом управления. В отличие как от графа вызовов, так и от расширенного графа вызовов, данная форма представления содержит информацию о том, зависят ли срабатывания каждого вызова от срабатывания альтернатив аых операторов или нет.

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

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

В конце данного раздела рассматриваются методы локализации наиболее значимых фрагментов программ. Статические методы опираются на анализ текста программы и описанные выше графовые структуры. Динамические методы используют результаты многоуровневого профилиро-

ш

О

О

I

•ЦЦНЫ

О •

о

0 1(1 о

о •

о

о

о

Рис. 3.

Рис. 4.

вания. Для отображения результатов профилирования используются либо специальные средства, либо соответствующая разметка обсуждаемых выше структур.

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

Основной инструмент для исследования информационной структуры процедуры на макроуровне — это информационный граф. Вершинам графа соответствуют фрагменты текста, которые связываются направленной дугой тогда и только тогда, когда одна вершина (фрагмент) вычисляет данные для другой. Дуга направлена от вершины, производящей данные, к вершине их использующей. Ясно, что построенный таким образом граф содержит только истинные зависимости и, следовательно, позволяет определить потенциальный параллелизм процедуры на макроуровне.

Построение информационного графа преследует две цели. Во-первых,

мы имеем возможность сразу определить те вершины (т.е. фрагменты текста), которые в принципе являются информационно независимыми. В дальнейшем такие вершины можно будет исполнять в любом порядке. Во-вторых, информационный граф, показывая общую последовательность вычислений, позволяет упростить последующий процесс анализа. Предположим, что в графе вершина А связана с вершиной В: А —+ В. В этом случае, возможен раздельный анализ таких фрагментов, который и проще, и позволяет выделить практически весь потенциальный параллелизм части АВ исходной программы. Если же связь между данными фрагментами циклическая: А В, то ситуация принципиально иная, поскольку только совместный анализ фрагментов А и В позволит выделить скрытый скошенный параллелизм, приносящий, во многих случаях, ускорение на "порядок". Ясно, что за основу для проведения последующего микроанализа надо брать компоненты сильной связности информационного графа. Для графа А —» В это как А, так и В, а для графа А В это фрагмент АВ целиком. Если мы хотим не только оценить ресурс параллельности фрагмента, но и найти способ его реального использования, то надо построить единый граф для истинной зависимости, зависимости по выходу и антизависимости.

Для описания и визуализации макропараллельной структуры процедуры используется ярусно-параллелъная форма. По существу, данная форма, является объединением информационного графа и графа управления. Она показывает, какие части процедуры можно выполнять в любом порядке, а какие последовательно одна за другой. Ярусно-параллельная форма разбивает все вершины графа на непересекающиеся множества так, что все множества должны выполняться строго один за другим, но все вершины одного и того же множества информационно независимы и могут исполняться в произвольном порядке. На рис.4 показан пример ярусно-параллельной формы.

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

Ярусно-параллельная форма определена не однозначно. Любую вершину можно переместить на уровень с большим номером вместе с перемещением зависящих от нее вершин. Среди всего множества форм система V-Ray выбирает каноническую ярусно-параллельную форму, в которой любая вершина зависит от некоторой вершины предыдущего яруса. Этот факт гарантирует нахождение теоретически наискорейшего способа выполнения анализируемого фрагмента при неограниченном числе процессоров. Перемещая избыточные вершины на ярусы с большими номерами, можно дополнительно учесть ограничения конфигурации целевого компьютера.

Для описания тонкой структуры программ на микроуровне разработана технология визуализации истории выполнения программ на уровне отдельных срабатываний отдельных операторов. Основные сложности на данном этапе заключаются в нахождении удобного способа представления истории и удачном выборе функциональности. Разработано несколько альтернативных систем координат, в рамках которых удалось успешно справиться как со сложностью изображаемых объектов (историй программ), так и с их многомерностью.

Основной ресурс параллелизма программ на микроуровне определяется независимостью итераций циклов. Самый удобный для последующего использования тип параллелизма — это циклы PARDO (координатный параллелизм). Поскольку свойство PARDO относится к циклам анализируемой программы, то прямо в исходном тексте все циклы могут быть размечены системой в зависимости от того, обладают они" этим свойством' или нет.

В реальных программах циклы с данным свойством обладает одной особенностью. Если цикл помечен как PARDO, то это означает следующее: цикл в принципе обладает этим свойством, но для того, чтобы все итерации выполнять независимо, может потребоваться введение дополнительных переменных (что связано с антизависимостью и зависимостью по выходу между различными итерациями цикла). Система различает эти два случая, помечая циклы либо как истинные циклы PARDO, которые можно исполнять параллельно в том виде, как они представлены в тексте, либо как потенциальные циклы PARDO, которые можно преобразовать в

истинные введением новых переменных.

Описание основной части потенциального параллелизма фрагментов опирается на определенные выше структуры и свойство PARDO циклов. Если речь об отдельной процедуре, то это размеченный циклический профиль процедуры, либо ярусно-параллельная форма с помеченными PARDO циклами (на рис.4 соответствующие им вершины перечеркнуты). Если говорим о проекте целиком, то это расширенный граф вызовов с размеченным циклическим профилем. Определение свойства PARDO идет согласно критерию, сформулированному в разделе 4.1. Если необходим межпроцедурный анализ, то используется разработанный метод точного определения входных/выходных данных, описанный в разделе 4.5.

Четвертая часть полностью посвящена конкретным примерам использования как системы V-Ray, TáK и непосредственно самой технологии анализа программ, которые в совокупности позволяют подойти к решению задачи совместного анализа структуры программ и особенностей архитектуры современных компьютеров на принципиально ином уровне.

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

В разделе 12 очерчивается общий круг проблем, с которыми в той или иной степени приходится сталкиваться любому пользователю параллельных вычислительных систем. Изложение построено так, что каждая проблема формулируется в виде отдельного вопроса, иллюстрируется примерами реальных программ, и затем, указывается способ ее решения. В качестве подобных вопросов рассматриваются следующие.

• На программе очень плохая производительность. В чем причина?

о Причина известна. Как ее устранить? '

• Можно ли принципиально ускорить программу?

• Можно ли распределить данные так, чтобы не было пересылок между процессорами?

• Можно ли применить данное преобразование к программе?

• Нужно ли пытаться использовать какой-либо другой препроцессор или метод оптимизации?

• Тысячи строк исходного текста программ — можно ли в них разобраться?

• Соответствует ли структура программы особенностям параллельного компьютера? Если нет, то какой компьютер следует использовать для решения задачи?

• Можно ли оценить потенциал параллелизма алгоритма, используемого в программе?

В разделе 12.10 проанализирован изложенный в разделах 12.1-12.9 материал и выделены те основные положения технологии, на которых базировался проводимый в каждом случае анализ. Среди основных следует назвать: знание точной информационной структуры исследуемого фрагмента, математическая гарантия результатов исследования, согласование потенциального параллелизма с распределением данных, единый подход к анализу как простых, так и сложных фрагментов, мощные средства визуализации структуры программы на всех уровнях и другие.

Для первых численных экспериментов мы выбрали пакет Perfect Club Benchmarks, который уже в течение многих лет используется для определения реальной производительности параллельных компьютеров на промышленных приложениях. К настоящему времени его состав, структура отдельных программ, ключевые фрагменты отдельных процедур, производительности для большого числа различных компьютеров и многие другие параметры подробно исследованы и неоднократно описаны во многих работах. Однако именно широкая известность пакета и показалась привлекательной, так как только таким образом можно объективно оценить эффективность новой технологии по сравнению с существующими методами анализа и преобразования программ.

Из самого пакета были выбраны программы TRFD и FL052, так как первая имеет крайне низкую производительность на всех параллельных компьютерах фирмы CRAY, а вторая очень сложна для адаптации к массивно-параллельной архитектуре и, насколько нам известно, успешных попыток ее оптимизации не-было.

Суть проблемы легко объяснить на примере программы TRFD. На исходном варианте TRFD один процессор компьютера CRAY Y-MP С90 (пиковая производительность почти 1 Gflop/s) достигает только 89.5 Mflop/s. Лучший вариант ручной оптимизации этого кода увеличил производительность лишь до 139.7 Mflop/s1. Ясно, что программа в первоначальном виде не только достаточно плохо векторизуется, но и "ручные" изменения не могли существенно исправить положения дел.

Естественно сразу возникает вопрос: можно ли увеличить производительность только с помощью эквивалентного преобразования исходного текста данной программы? Исследования показали, что это сделать-можно. В результате проведенных исследований удалось, во-первых, поднять производительность одного процессора CRAY Y-MP С90 на данной программе до 579.7 Mflop/s, во-вторых, добиться устойчивого роста производительности для многопроцессорных конфигураций (и это верно для всего векторно-конвейерного ряда компьютеров CRAY), и, наконец, получить действительно масштабируемую программу с очень хорошим ростом производительности для массивно-параллельных компьютеров CRAY T3D и ЮМ SP2.

Процесс анализа и преобразования программ TRFD и FL052 описан в разделе 13. Результаты численных экспериментов с программой TRFD для векторно-конвейерных компьютеров CRAY Y-MP С90 и CRAY EL приведены в табл.1. Важно отметить, что вся оптимизация данной программы была выполнена на уровне Фортрана без использования вызовов высокоэффективных библиотечных подпрограмм и ассемблерных вставок.

Показано, что как для TRFD, так и для FL052 был использован практически весь потенциальный параллелизм, поэтому дальнейшая оптимиза-

1 Значения производительности после ручной оптимизации предоставлены Д.Бруксом из CRAY Research, Inc., Eagan MN, USA.

CRAY С90 Пик. произв. Баз. произв. Ручная опт. Y il;.;.' опт.

CPUs Mflop/s Mflop/s Mflop/s Mflop/s

1 960 89.5* 139.71! 579.7'

8 7680 89.6 962.68 2440.5*

CRAY EL Пик. произв. Баз. произв. Ручная опт. V-Ray опт.

CPUs Mflop/s Mflop/s Mflop/s Mflop/s

1 132 11.37 — 54.60

2 261 11.4(1 106.03

4 528 11.38 193.32

Табл.1. Результаты оптимизации программы TRFD для векторно-копвейерпых суперкомпьютеров CRAY

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

Результирующая параллельная программа для массивно-параллельного компьютера IBM SP2 была написана в терминах языка MPL (Message Passing Language), а для компьютера CRAY T3D в терминах MPI. Информация о локальности использования данных позволила выполнить дополнительную скалярную оптимизацию на уровне Фортрана для более эффективного использования кэш-памяти каждым процессором. Результаты адаптации для IBM SP2 показаны и табл.2.

IBM SP2 PEs без скал.оптимизации со скал.оптимизацией

seconds Mflop/s seconds Mflop/s

2 6.18 69.6 3.81 113

4 3.43 125 2.19 196

8 2.00 215 1.31 328

16 1.13 383 0.75 574

Табл.2. Результаты оптимизации TRFD для IBM SP2

Разделы 14 и 15 посвящены исследованию программы решения больших систем линейных уравнений с разреженными матрицами (ВЦ РАН) и

анализу модели общей циркуляции атмосферы (ИВМ РАН). В каждом случае найдена и удалена причина низкой производительности на векторно-конвейерных компьютерах типа CRAY Y-MP. В настоящее время, программа, реализующая модель общей циркуляции атмосферы, адаптировала к компьютеру CRAY Y-MP М90, установленному в Гидрометеоцентре РФ.

В разделе 16 описан процесс анализа и оптимизации программы моделирования эволюции крупномасштабных магнитных полей галактик (MHD), разработанной группой ученых физического факультета и научно-исследовательского вычислительного центра МГУ. Исходный вариант программы содержал более 2500 строк на языке Фортран, объединенных в 73 подпрограммы. Производительность одного процессора компьютера CRAY Y-MP С90 на исходном варианте составила 40 Mflop/c. После всего комплекса оптимизации производительность увеличилась в 7 раз и составила 280 Mflop/c.

Как и для программ TRFD и FL052, определив точную информационную структуру и весь потенциальный параллелизм программы MHD, можно быть уверенным в том, что все основные ресурсы параллелизма использованы, и, следовательно, любые другие попытки параллельного решения исходной задачи, использующие заложенный в MHD алгоритмический подход, заведомо не дадут принципиально лучшего результата.

Оптимизация программы, написанной для обработки сложных сверхширокополосных сигналов (SBBS), проводилась в рамках выполнения совместных работ с Государственным научно-исследовательским институтом авиационных систем. На исходной версии программы один процессор компьютера CRAY Y-MP С90 работал с производительностью около 32 Mflop/c. Используя разработанные инструментальные средства аналитического и визуального анализа структуры программ и зная особенности векторно-конвейерного компьютера CRAY Y-MP С90, удалось локализовать критический фрагмент программы, найти причину низкой производительности, ликвидировать ее и повысить производительность данного компьютера более чем в 10 раз, достигнув 365 Mflop/c.

В заключении сформулированы следующие

Основные результаты работы

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

• на основе обнаруживаемых информационных связей в программах построены новые критерии, в том числе неулучшаемые, для установления параллелизма вычислений, выполнения эквивалентных преобразований программ, выявления различных нетрадиционных свойств программ и т.п.;

• разработаны общие принципы построения инструментальных систем для изучения и визуализации тонкой структуры программ; эти принципы не предполагают получения от пользователя содержательных сведений о структуре программ; разработанные методы визуализации охватывают все основные структуры, начиная с уровня отдельных срабатываний операторов до межпроцедурного уровня всего программного комплекса в комбинации с различными видами связи (по управлению, информационная и другие) между исследуемыми объектами;

• создана и успешно апробирована многоцелевая система для изучения структуры больших программных комплексов и адаптации этих комплексов к требованиям целевых компьютеров с параллельной архитектурой;

• на основе работы с данной системой накоплен значительный опыт повышения эффективности реализации на современных параллельных компьютерах и супер-ЭВМ программ из различных предметных областей; для многих результирующих программ полученные показатели эффективности (время выполнения, производительность) во много раз превышают аналогичные показатели не только исходных,

но и уже существующих альтернативных вариантов; для многих программ представлены гарантии неулучшаемости полученных результатов.

Публикации по теме диссертации

По теме диссертации опубликовано 27 работ, в том числе одна монография. Основные результаты диссертации представлены в следующих работах.

1. Воеводин Вл.В. Система распараллеливания и статистический анализ программ. // Труды Н-й Всесоюзной конференции по актуальным проблемам информатики и выч.техники, Ереван, 1987.

2. Воеводин Вл.В. Статистические оценки возможности выявления параллельной структуры последовательных программ //Программирование. 1990. № 4. С.44-54.

3. Воеводин Вл.В. Статический анализ и вопросы эффективной реализации программ.- В кн.: Вычислительные процессы и системы. Вып.9. М.: Наука, 1992. С.249-301.

4. Воеводин Вл.В. Теория и практика исследования параллелизма последовательных программ// Программирование. 1992. № 3. С.38-53.

5. Voevodin VI. V. Use of the V-Ray system for optimization of serial programs for parallel computers. // Proc. of the 2nd Intern. Workshop SMS TPE'94, Moscow, 1994. P.399-405

6. Воеводин Вл.В., Капитонова А.П. Методы описания и классификации архитектур вычислительных систем - Изд-во Моск. университета, 1994. 79 с.

7. Воеводин Вл.В. Легко ли получить обещанный гигафлоп? //Программирование. 1995. № 4. С.13-23.