ВКР: Система автоматизированного распараллеливания Фортран-программ - анализ многомодульных программ

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

1 Введение
На данный момент вычислительные технологии развиваются очень интенсивно. Потенциально современные вычислительные системы открывают огромные возможности для решения теоретических и прикладных задач, но это влечет за собой необходимость написания эффективного программного кода, который должен исполняться на современных суперкомпьютерах. Написание программного кода в свою очередь осложняется тем, что развитие современных вычислительных систем идет не столько по пути увеличения производительности отдельно взятого процессора, сколько за счет создания сложных вычислительных комплексов, включающих тысячи узлов, соединяемых высокоскоростными линиями связи. Причем узлы могут состоять из процессоров включающих в свой состав несколько ядер. В связи с этим возникает потребность в написании такого программного кода, который бы обеспечивал максимальную загрузку каждого ядра в каждый момент времени. Для этого необходимо разбить конкретную задачу на блоки, которые могут быть вычислены параллельно, но так как все выделенные подзадачи направлены на решение одной исходной задачи, возникает необходимость обмениваться данными между различными блоками, что в свою очередь может значительно увеличить время, необходимое на решение данной задачи. Поэтому должны быть созданы средства для анализа исходной задачи, направленные на то, чтобы эффективнее вычислять ее решение, то есть выделить подзадачи, которые могут быть решены параллельно при условии минимального количества обменов данными между ними. Для этого при расщеплении исходной задачи на блоки должен быть найден компромисс. Но прежде, чем приступать к поиску такого компромисса, необходимо выделить те участки задачи, которые могут быть выполнены параллельно и те которые потребуют данные, получаемые на других участках. Создание эффективных средств анализа позволит в значительной степени понизить сложность создания эффективного параллельно выполнимого программного кода. Эффективные средства анализа также позволят значительно повысить производительность уже существующих программных комплексов за счет их автоматизированного распараллеливания. Это является особенно важным потому, что при поиске параллельных участков программы необходимо четко понимать структуру самой программы, но в случае достаточно сложных задач, которые в наибольшей степени являются кандидатами на распараллеливание, ручной анализ кода в условиях отсутствия точной документации может потребовать огромных временных затрат, что может оказаться неприемлемым. К тому же создание параллельного варианта решения задачи вручную, может привести к возникновению ошибок, характерных для параллельных программ. Например, возможно такая ситуация, что разработчик, неправильно определил независимые участки кода, и в результате их параллельного вычисления программа, работающая до этого корректно, стала выдавать неверные результаты. Такие ошибки, проявляющиеся только при параллельном выполнении программы, очень сложно обнаружить, что также является минусом при создании параллельного кода вручную. Между тем использование автоматических и автоматизированных средств по распараллеливанию программ позволяет исключить риск возникновения ошибок, связанных с некорректным пониманием разработчиком последовательной программы. Использование автоматизированных средств распараллеливания позволяет следить за теми местами в создаваемой программе, где такие ошибки могут возникнуть в связи с особыми указаниями разработчика. В данном дипломе речь пойдет об анализе последовательной программы. Результаты полученные в данном дипломе планируется использовать в Системе Автоматизации Распараллеливания Фopтран-программ (далее САПФОР) [1]. Существует также другая аналогичная система — Parawise [2]. Это единственная известная система автоматизации распараллеливания для кластеров. Основное отличие САПФОР от нее — использование внутри САПФОР автоматически распараллеливающего компилятора (при построении вариантов распараллеливания программиста ни о чем не спрашивают - спрашивают при анализе, при выборе среди построенных вариантов распараллеливания). САПФОР включает в свой состав 5 компонент: диалоговая оболочка, анализатор, эксперт, генератор кода и база данных. САПФОР направлена на получение эффективных параллельных программ из последовательных при участии пользователя. В работе речь пойдет об идеях, используемых только в анализаторе, но для более точного понимания целей работы кратко охарактеризуем каждый компонент. Диалоговая оболочка обеспечивает взаимодействие пользователя с системой. Она служит для достижения двух целей: во-первых, визуализация получаемых в ходе работы системы данных, а во-вторых, конструктивный диалог с пользователем. Это позволяет пользователю принимать участие в распараллеливании последовательной программы в удобном для него режиме. При этом средствами системы осуществлять контроль за выполняемыми им действиями. Среди таких действий может быть, например, явное указание отсутствия зависимостей в цикле, если пользователь абсолютно уверен в этом, а анализатор не может

2 Постановка задачи
Задача данной дипломной работы заключается в разработке алгоритмов анализа на зависимости по данным многомодульных программ и реализации на их основе анализатора для САПФОР. Иными словам, задача данной дипломной работы заключается в установлении факта существования или отсутствия зависимости по данным для каждого цикла анализируемой программы и в выявлении переменных программы, породивших данную зависимость. Разрабатываемый алгоритм должен выполняться за приемлемое время и находить все те зависимости, которые необходимы для правильной работы эксперта САПФОР. Данная задача разбивается на следующие подзадачи: ● разработка алгоритмов анализа для циклов; ● разработка алгоритмов межпроцедурного анализа. Рассмотрим отдельно каждую из подзадач.