Разработка и реализация методов потокового анализа распараллеливаемых программ в Преобразователе программ СБкЗ_ПП - Дипломная работа

Доказательство того, что цели, сформулированные в задании, достигнуты.Вариант 1Потребность в распараллеливающих компиляторах появилась практически сразу с началом работы над параллельными архитектурами, поскольку появилась необходимость в адаптации накопленного багажа последовательных алгоритмов к параллельным архитектурам. В мире предложено уже много различных схем для последовательных программ, оптимизирующие преобразования описываются в терминах различных схем программ, что затрудняет объединение преобразований в рамках одного транслятора. Поэтому возникает проблема стандартизации системы понятий для описания схемы программы, в терминах которой можно было бы описывать все возможные оптимизирующие преобразования, направленные на улучшение параллельности. Однако период времени, который обычно проходит от момента публикации описания нового преобразования до момента окончания реализации оптимизирующего компилятора, содержащего в своем наборе данное преобразование, настолько велик, что результаты компьютерных экспериментов с этим преобразованием оказываются мало актуальными. Несмотря на то, что проблема оптимизации программ для компьютеров с параллельной архитектурой существует уже более 20 лет, ее решение до сих пор нельзя считать удовлетворительным.· Оптимизация на базе профилейвозможность запустить программу в тестовом режиме, собрать данные о времени прохождения фрагментов кода внутри часто используемых функций, а затем использовать эти данные для оптимизации · Поддержка OPENMP для программирования на SMP-системахна кластере рекомендуется преимущественно пользоваться интерфейсом MPI; имеет смысл пользоваться библиотеками, распараллеленными для общей памяти. · "Диспетчеризация" кода для различных процессороввозможность генерации кода для различных процессоров в одном исполняемом файле, что позволяет использовать преимущества новейших процессоров для достижения на них наибольшей производительности, при сохранении двоичной совместимости программ с более ранними процессорами; на нашем кластере это пока не актуально, т.к. используются только процессоры Pentium III, а также не предполагается передача и запуск на других машинах программ, откомпилированных на кластере. На первом этапе система определяет основные машинно-независимые свойства программ, а именно, потенциал параллелизма и локальность использования данных. На основе этой информации система предлагает возможные преобразования программ, затем пользователь или система выбирает те из них, которые наиболее подходят к архитектуре конкретного компьютера, и только после этого производятся необходимые преобразования.Исходя из перспективности параллельных архитектур, разработчики считают целесообразным разработку системы, ориентированной: · на исследование эффективности применения различных систем преобразований в процессе трансляции с императивных и функциональных языков для разных классов программ и ЭВМ (включая ее зависимость от форм промежуточного представления программ, наборов трансформаций, выбора контекстных условий и стратегий применения преобразований); Эти средства должны позволять пользователю управлять процессом преобразования программы (например, заданием дополнительной информации о свойствах программы), а системе - комментировать результирующую программу информацией о процессе преобразования программы. Совокупности преобразований, поддерживаемые системой ПРОГРЕСС, должны базироваться на богатой библиотеке преобразований, содержащей базовые преобразования для разных промежуточных представлений программ, и развитых средствах конструирования систем преобразований. Считается целесообразным исследование таких форм промежуточного представления программ, как абстрактное синтаксическое дерево, управляющий граф, SSA-форма, граф программных зависимостей, иерархический граф заданий, идеограф, сеть программных зависимостей, граф потока зависимостей, а также представления IF1 и IF2, применяемые в компиляторах языка SISAL. Подсистема оценки и моделирования - позволяет оценивать качество результирующей программы с помощью статического анализа программы и моделирования прогона программы на аппаратуре, а также собирать требуемую информацию о процессах выполнения программы.Поэтому целесообразно программу один раз разобрать, записать результат разбора в специальном виде - внутреннем представлении - и затем работать с этим внутренним представлением. Внутреннее представление программы в компиляторе - это специальная структура, в форме которой хранится информация о преобразуемой (компилируемой, оптимизируемой, конвертируемой) программе. В это внутреннее представление должны преобразовываться программы на языках ФОРТРАН, ПАСКАЛЬ, Си. Если бы все операторы программы были однотипные (например, присваивания), то вместо указателя на оператор можно было бы хранить сам оператор (в разобранном виде).

Оглавление

Введение

1. Обзор литературы по теме «потоковый анализ программ в распараллеливающих и оптимизирующих компиляторах»

1.1 Распараллеливающие компиляторы

1.2 Представление программ

1.3 Задачи потокового анализа

1.4 Методы потокового анализа

1.5 Теоретические свойства методов

1.6 Опыт реального применения распараллеливающего компилятора

1.7 Средства реализации распараллеливающего компилятора

1.8 Компиляция с переменным набором оптимизирующих преобразований

1.9 .Выводы из обзора

2. Описание предметной области, решаемых задач и методов их решения

2.1 Описание предметной области

2.1.1 Граф алгоритма

2.1.2 Графы зависимостей и минимальные графы

2.1.3 Циклы PARDO и избыточные вычисления

2.1.4 Эквивалентные по вычислениям преобразования программ

2.2 Модель структурных программ

2.2.1 Термины объекта оптимизации

2.2.2 Описание терминов потокового анализа МСП

2.3 Постановка задач и методы их решения

2.3.1 Алгоритм добавления атрибутов PARDO

2.4 Представление методов потокового анализа программ

2.4.1 Абстрактный синтаксис языка методов потокового анализа программ

2.4.2 Операционная семантика языка методов потокового анализа программ

2.4.3 Расширение базы методов потокового анализа программ

3. Техническая часть

3.1 Назначение программного средства (ПС)

3.2 Архитектурно-контекстная диаграмма СБКЗ_ПП

3.2.1 Подсистема потокового анализа

3.3 Архитектурно-контекстная диаграмма ПС

3.4 Требования к программному средству

3.4.1 Общие функциональные требования

3.4.2 Конкретные функциональные требования

3.4.3 Требования к программному обеспечению

3.4.4 Требования к надежности

3.4.5 Профиль пользователя

3.4.6 Жизненный цикл программного средства

3.4.7 Требования к интерфейсу

3.5 Проектная документация

3.5.1 Архитектура программного средства

3.5.2 Спецификации функций

3.5.3 Описание реализации программного средства

3.5.4 Описание использования программного средства

4. Тестирование

4.1 Тестовые ситуации

4.2 Тесты

5. Экспериментальное изучение свойств программного средства

5.1 Цель экспериментов

5.2 Описание среды

5.3 План экспериментов

Эксперимент №1

Эксперимент №2

Эксперимент №3

5.4 Результаты экспериментов

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

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

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

Основной задачей распараллеливающего компилятора является выявление скрытого (как правило) или явного (что редко) параллелизма. Такой анализ проводится не по самому тексту программы, а по ее модели.

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

Задача выявления параллелизма в большинстве случаев сводится к задаче определения различных типов зависимости между участками программы и итерациями циклов.

Основной проблемой в сфере науки о преобразованиях программ является невозможность своевременно выполнять компьютерные эксперименты. Цель таких экспериментов - определить, насколько часто в реальных программах применимы те или иные преобразования и какой эффект дает их применение. Единственным средством проведения подобных экспериментов являются оптимизирующие компиляторы, например, GCC [14, 23], распространяемый бесплатно (по лицензии GPL), а из коммерческих разработок - компиляторы Intel C и Fortran [10]. Однако период времени, который обычно проходит от момента публикации описания нового преобразования до момента окончания реализации оптимизирующего компилятора, содержащего в своем наборе данное преобразование, настолько велик, что результаты компьютерных экспериментов с этим преобразованием оказываются мало актуальными. Кроме того, оптимизирующий компилятор обычно содержит большой набор преобразований и встроенную стратегию их применения. Поэтому получить результаты компьютерных экспериментов, относящихся к отдельному преобразованию (а не ко всему набору), весьма проблематично.

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

Несмотря на то, что проблема оптимизации программ для компьютеров с параллельной архитектурой существует уже более 20 лет, ее решение до сих пор нельзя считать удовлетворительным. Было предложено много различных подходов к оптимизации, но ни один из них не предполагает комплексного решения всего множества возникающих проблем. Более того, как показали недавние исследования Иллинойского университета, большинство методов потокового анализа распознают лишь 15% из всех пар зависимостей. На этом фоне успешной выглядит система V-Ray [15], практическое экспериментальное исследование которой показало превосходство (порой весьма значительное) над другими системами оптимизации. Однако V-Ray является лишь инструментом для выявления параллелизма, а анализ результатов, выбор и применение ОП и производятся вручную и неинтерактивно, как и постановка экспериментов. Существуют интерактивные системы, как, например, Acovea [18] для компилятора GCC, позволяющие в диалоговом режиме управлять стратегией оптимизации, то есть выбирать оптимизирующие преобразования. Однако расширение множества целевых языков или преобразований потребует серьезной модификации программы. Разрабатывается система, в которой библиотека преобразований выделяется в отдельную самостоятельную часть - открытая распараллеливающая система (ОРС) [17]. Система предназначена для автоматического распараллеливания программ с процедурных языков программирования (Фортран, Паскаль, Си) на параллельные компьютеры, ориентированные на математические вычисления.

Помимо этого предложен новый подход - управляемый пакет оптимизаций [5]. Это пара , где Р - пакет оптимизаций, а М - менеджер пакета оптимизаций. Пакет оптимизаций представляет собой набор оптимизаций с одним и тем же объектом применения. Менеджер оптимизаций определяет порядок запуска оптимизаций пакета. Но данный проект пока не реализован до конца.

С целью решения упомянутых выше проблем в области разработки и применения оптимизирующих компиляторов в отделе интеллектуальных систем ИАПУ ДВО РАН предлагается концепция управления информацией о преобразованиях программ в рамках Специализированного банка знаний о преобразованиях программ (СБКЗ_ПП). СБКЗ_ПП состоит из информационного наполнения (ИН), оболочки ИН, программного наполнения (ПН) и блока администрирования (БА). Одной из компонент ПН является блок потокового анализа.

Целью данной дипломной работы является разработка и реализация подсистемы потокового анализа, управляемого знаниями, для распараллеливаемых программ в МСП как части СБКЗ_ПП.

Задачи дипломной работы: · Разработка представления методов потокового анализа программ.

· Разработка требований к системе потокового анализа распараллеливаемых программ, управляемой базой знаний.

· Разработка проекта верхнего и нижнего уровней для системы потокового анализа распараллеливаемых программ, управляемой базой знаний.

· Реализация системы потокового анализа распараллеливаемых программ, управляемой базой знаний.

Работа содержит следующие разделы: · Глава 1 - обзор литературы, в котором проанализированы существующие системы распараллеливания с акцентом на подсистему ПА, рассмотрены методы и задачи ПА и различные внутренние представления программ.

· Глава 2 - постановку задачи и математическую модель;

· Глава 3 - техническую документацию программного средства;

· Глава 4 - описание тестирования программного средства;

· Глава 5 - Экспериментальное изучение свойств программного средства.

· Глава 6 - доказательство того, что цели дипломной работы, сформулированные в задании, достигнуты. Обсуждение результатов работы.

1.