ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ

На правах рукописи

Штейнберг Роман Борисович

АВТОМАТИЧЕСКОЕ ОТОБРАЖЕНИЕ ПРОГРАММ

НА КОНВЕЙЕРНЫЕ И МНОГОКОНВЕЙЕРНЫЕ АРХИТЕКТУРЫ

05.13.11 – МАТЕМАТИЧЕСКОЕ И ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ

ВЫЧИСЛИТЕЛЬНЫХ МАШИН, КОМПЛЕКСОВ И КОМПЬЮТЕРНЫХ СЕТЕЙ

ДИССЕРТАЦИЯ

на соискание учёной степени кандидата физико-математических наук

Научный руководитель:

заслуженный работник высшей школы РФ, кандидат физико-математических наук, профессор Ерусалимский Яков Михайлович Ростов-на-Дону Оглавление Список сокращений

Введение

Теория графов и графовые представления программ

1.

Необходимые понятия из теории графов

1.1.

Информационные зависимости в программах

1.2.

Граф информационных связей

1.3.

Основные понятия теории решетчатых графов

1.4.

Элементарные решетчатые графы

1.4.1.

Максимальный и минимальный решетчатые графы

1.4.2.

Граф вычислений.

1.5.

Выводы к первой главе

1.6.

Конвейерные вычисления

2.

Конвейерные задержки и интервал инициализации итераций

2.1.

Вспомогательные утверждения

2.2.

Алгоритм поиска множества всех элементарных циклов, содержащих данную 2.3.

обратную дугу

Алгоритм вычисления интервала инициализации итераций

2.4.

Полиномиальный алгоритм вычисления интервала инициализации итераций.... 2.5.

Составление расписания для организации конвейерных вычислений 2.6.

одномерного цикла

Примеры составления расписания для конвейерных вычислений................. 2.6.1.

Вспомогательный алгоритм составления расписания и вычисления 2.6.2.

буферных задержек на подграфе графа вычислений, который содержит один источник и не содержит обратных дуг

Склеивание двух подграфов с рассчитанными расписаниями 2.6.3.

(вспомогательный алгоритм)

Алгоритм составления расписания и вычисления буферных задержек на 2.6.4.

дугах графа вычислений

Выводы ко второй главе

2.7.

Многоконвейерные вычисления

3.

Многоконвейерная модель вычислений

3.1.

Отображение программ на многоконвейерную модель вычислений

3.2.

Влияние зависимостей в самом вложенном цикле на задержку в стартах 3.3.

конвейеров

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

Формула вычисления задержки в стартах конвейеров для тесного двумерного гнезда циклов

Постановка задачи

Случай |A| 0, |B| 0.

Случай |A| = 0, |B| 0.

Случай |A| 0, |B| = 0

Случай |A| = 0, |B| = 0, c12 c2 0.

Случай |A| = 0, |B| = 0, c12 c2 0.

Выводы к третьей главе

Вспомогательные результаты

Линейная форма представления выражений

Система тестирования

Применение автоматического построения графа вычислений к генерации HDLописаний. Конвертер с языка C в VHDL

Выводы к четвертой главе

Заключение

Приложение 1

Литература

АЛУ – арифметико-логическое устройство БДОП – быстрое дискретное ортогональное преобразование ДВОР – диалоговый высокоуровневый оптимизирующий распараллеливатель МВС – многопроцессорная вычислительная система ОРС – открытая распараллеливающая система ПЛИС – программируемая логическая интегральная схема ПО – программное обеспечение ПЭ – процессорный элемент РГА – редуцированный граф алгоритма ЦЛП – целочисленное линейное программирование DSP – Digital Signal Processor FPGA – Field Programmable Gate Array HDL – Hardware Description Language VBA – Visual Basic for Applications VLIW – Very Long Instruction Word Актуальность темы. Сегодня c использованием высокопроизводительных вычислительных систем решаются задачи прогноза погоды, межмолекулярного взаимодействия, биоинформатики, нефтегазовой разведки, наноинженерии, механики, гидродинамики и т.д. [38, 46]. В мире представлено большое многообразие архитектур высокопроизводительных вычислительных систем, но никакой суперкомпьютер не способен решать разные задачи с одинаковой эффективностью. Более того, известны случаи, когда решение задачи на кластере проигрывало по сравнению с ее решением на одном вычислительном узле этого же кластера. В данной работе рассматривается отображение гнезд циклов на модель многоконвейерной вычислительной системы.

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

В этой работе рассматривается один из вариантов распараллеливания по данным — конвейерные вычисления. В процессе конвейерных вычислений одновременно выполняются независимые этапы одного и того же вычисления.

Конвейеры создавались для вычисления отдельных алгоритмов (уровень функций) [14, 36], для вычисления отдельных операций (уровень АЛУ) [14, 25, 45], для набора операций (VLIW) [14, 47], для инструкций процессора. Несмотря на то, что все эти конвейеры сильно отличаются друг друга по реализации, в их основе лежит идея разбиения вычислений на ступени и одновременного выполнения этих ступеней (для разных данных).

Программные конвейеры [20, 22, 47] используются в работе большинства современных процессоров от Intel, AMD, Apple. Для построения специализированных вычислителей [45, 75], таких как бортовые компьютеры, устройства фильтрации сигналов, активно используется конвейерный подход.

Сегодня в России, как и в других странах мира, ведутся исследования в области и аппаратного [29, 31, 33, 83], и программного обеспечения [34] суперкомпьютеров, в том числе и связанные с компьютерами с перестраиваемой архитектурой (reconfigurable architecture). Одним из наиболее крупных проектов по созданию суперкомпьютера с архитектурой перестраиваемого конвейера является проект Merrimac [78]. Многие компьютеры с программируемой архитектурой позволяют создавать перестраиваемые (программируемые) конвейеры [28, 31, 77], показывающие большую эффективность при работе с рекуррентными циклами. В этой архитектуре основной идей является конфигурирование системы для организации вычислений по заданной программе. Как правило, для этого настраиваются связи между элементарными вычислителями внутри компьютера. При создании компиляторов с языков высокого уровня для таких архитектур, желательно организовать автоматическое формирование связей между вычислителями в соответствии с потоком данных в компилируемой программе. Задачу автоматического формирования связей на этапе компиляции позволяет решить модель графа вычислений программы и построенная на ее основе модель многоконвейерных вычислений.

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

Обзор литературы Начнем рассмотрение публикаций по конвейерным вычислениям с работ, посвященных программным конвейерам (software pipelining). В серии работ [20], [21], [22] рассматриваются гнезда циклов, содержащие только операторы присваивания.

Рассматривается развертка внешних циклов этих гнезд как средство повышения эффективности программной конвейеризации. В обзоре [20] рассматриваются алгоритмы планирования программных конвейеров, в основном VLIW-подобные архитектуры.

Проводится сравнение различных вариантов алгоритмов планирования по модулю, а также методы глобального планирования (иерархическая редукция, if-конверсия, метод суперблоков, усовершенствованное планирование по модулю). Рассматривается генерация конвейерного кода, в частности оптимизация его объема. В работе [22] говорится о том, что она является развитием метода гиперплоскостей Лампорта [81] и использует ЦЛПподход к решению задачи планирования конвейера. Предлагается в итоге свести задачу вычисления коэффициентов развертки к задаче ЦЛП над векторами расстояния зависимостей (distance vector). Алгоритм приведен в общих чертах.

В работе [86] предлагается итеративный алгоритм для нахождения минимального интервала инициализации итераций, применительно к программным конвейерам.

В области ПО для суперкомпьютерного рынка также происходят существенные изменения. Например, 1 сентября 2010 г. журнал HPCWire опубликовал пресс-релиз программного продукта C-to-FPGA, который разработан компанией Stone Ridge Technology в рамках проекта ImpulseC (см. [91]). Этот продукт предназначен для генерации HDL-описаний в RTL-форме на основе алгоритма, написанного на языке высокого уровня. По оценкам экспертов, это позволит сэкономить до 2/3 времени разработки проектов на ПЛИС. В России также существуют группы исследователей, занимающиеся изучением новых языковых средств параллельного программирования (см.

[29], [37], [57]), а также предлагаются сервисы по исследованию программы на параллельность [43, 89 (см. web-ops)].

В главе 5 работы [45] рассматривается оптимизация проектирования конвейерных вычислителей на базе ПЛИС. Для этого создано полуавтоматическое ПО Paredit, в котором необходимо задать РГА, для последующей оптимизации конфигурации алгоритма и отображения его на микросхему. В данной диссертации рассматривается автоматическое создание графа вычислений (или РГА), что может существенно помочь в цикле проектирования конвейерных вычислителей, описанном в [45].

В работах [8, 9] рассматривается комплексный подход по созданию программноаппаратных систем. В основе лежит язык описания макроархитектуры процессора – PADLA (Processor Architecture Description Language), из которого автоматически генерируются все необходимые средства разработки, а также VHDL-описание процессора.

В работе [25] рассматривается новая автоматическая система проектирования, специализированная на автоматизации ранних этапов проектирования устройств трехмерной голографической памяти.

Наиболее распространенными языками для описания электронных схем на сегодняшний день являются VHDL, Verilog. Тем не менее можно встретить работы, например [7], в которых авторы пытаются развить существующие языки описаний. В частности, это может повлиять и на способы описания конвейерных вычислений.

В работе [49] рассматривается абстрактная модель, предназначенная для оптимизации проектирования конвейерных вычислителей на базе DSP. Пользователю программы Simulink, входящей в состав пакета MatLab, предлагается вручную задать архитектурную модель системного уровня. Тестирование такой модели представляется более трудоемким, чем тестирование программы на языке C. В настоящей диссертации рассматриваются вопросы генерации HDL-описаний по программе на языке C.

В работе [35] рассматривается проектирование однородных вычислительных сред.

Такие вычислительные среды рассматривались и ранее в качестве архитектур, позволяющих эффективное параллельное вычисление широкого класса задач [27, 31].

Работа [28] является закономерным развитием работы [27] и содержит описание архитектуры суперкомпьютеров со структурно-процедурной организацией вычислений, получившей практическое применение. В основе этой архитектуры лежит идея настройки компонент компьютера под задачу, особенно эффективно это применимо для организации конвейерных вычислений. В других источниках такие суперкомпьютеры называются компьютерами с перестраиваемой архитектурой (см. [32, 77, 78]). В работе [28] подробно рассматриваются идеология такой архитектуры и принципы взаимодействия компонент компьютера. Также рассматриваются вопросы выполнения программ на компьютерах этой архитектуры, в частности, отображение графового представления программы на вычислительную систему этой архитектуры и разбиение программы на кадры. Задача автоматического разбиения программы на кадры рассматривается в [2].

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

В ней рассматривается возможность организации мультиконвейерных вычислений для задач быстрых дискретных ортогональных преобразований (БДОП) на базе двумерного линейно-циклического процессора (см. [44, §5.5]). В работе [75] рассматриваются разные алгоритмы решения одномерных, двумерных и трехмерных задач цифровой фильтрации сигналов. Утверждается, что для одномерной задачи, параллельно-конвейерный (многоконвейерный) алгоритм является наиболее эффективным [75, с. 58]. В работе [29] рассматриваются однородные вычислительные среды, модульно-наращиваемая реализация реконфигурируемых мультиконвейерных архитектур, а также инструменты разработки программ для таких архитектур. Такими программными инструментами являются среда разработки параллельных программ Argus IDE и среда разработки вычислительных структур Fire!Constructor, разработанные в НИИ МВС (г. Таганрог).

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

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

информационных зависимостей к проектированию электронных схем. Так, например, в работе [6] описывается новый подход к проектированию микросхем. Целью этого подхода является улучшение качественных характеристик разрабатываемых микросхем при увеличении времени разработки не более чем в 2 раза. Результатом явились более 20 реализованных микросхем объемом от нескольких сот тысяч до десятков миллионов транзисторов, при этом параметры (частота микросхемы) были улучшены в 3 раза, а в некоторых случаях и более.

В работах В.В. Воеводина [14, 15, 16, 17, 19] рассматриваются различные графовые модели применительно к параллельным вычислениям. Особо надо выделить работу [14], которая содержит описания моделей и архитектур для организации параллельных вычислений. Также представлены несколько классификаций архитектур, использующих параллельные вычисления. Дан широкий обзор графовых моделей программ: граф информационных связей, история вычислений, решетчатый граф и т.д. Описываются возможные применения графовых моделей в аппаратно-программных комплексах.

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

Целью диссертации

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

К достижению этой цели приводит решение следующих задач:

1) автоматическое определение характеристик конвейера, таких как интервал инициализации итераций, буферные задержки, обратные дуги (см. 2.6);

2) автоматическое составление расписания работы каждого конвейера в рамках многоконвейерной модели вычислений (см. 2.6);

3) разработка алгоритмов синхронизации конвейера в рамках многоконвейерной модели вычислений (см. 3.3-3.4);

4) разработка методов и алгоритмов эффективного автоматического отображения программ на многоконвейерную модель вычислений (см. 3.3-3.5);

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

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

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

2. Предложен упрощенный алгоритм отображения на многоконвейерную архитектуру двумерных гнезд циклов. Указанный алгоритм применим к меньшему классу программ, чем общий, но при этом решает рассматриваемую задачу эффективнее. Этот алгоритм отображения, в частности, применим к программам, решающим задачи цифровой фильтрации сигналов, рассмотренные в работе М.С. Яджака [75], и позволяет вычислять характеристики конвейера автоматически.

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

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

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

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

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

Система тестирования, описываемая в диссертации, использовалась для тестирования преобразований в ОРС, а также при тестировании высокопроизводительного программного комплекса HPC-NASIS.

Внедрение результатов работы Результаты работы реализованы в виде программных модулей в рамках проектов ОРС и ДВОР.

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

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

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

Все рисунки в данной диссертации выполнены с помощью программных средств, в разработке которых автор принимал дейстельное участие. Часть из них являются экранными формами, созданными с помощью OPSDemo 3, OPSDemo 5 — программных продуктов сделанных в рамках проекта ОРС. Другие рисунки — с помощью макросов, написанных на VBA под MS Word лично автором.

В совместных работах [26, 56, 57, 59, 60, 62, 63] личным вкладом автора является разработка многоконвейерной модели вычислений, алгоритмов построения и анализа графа вычислений. В совместных работах [11, 62, 63, 64] также описывается и используется линеаризация выражений, выполненная лично автором.

В совместных работах [26, 61] описывается тестирующая система, в разработке которой автор принимал участие вместе с соавторами. В частности, формат представления файлов с данными разработан лично автором.

Гранты, поддерживавшие исследования диссертации.

НИОКР «Разработка системной поддержки высокопроизводительного программного комплекса для квантово-механических расчетов и моделирования наноразмерных атомно-молекулярных систем и комплексов», госконтракт 02.524.11.4005, шифр: 2008-04-2.4-15-02-003.

ФЦП «Научные и научно-педагогические кадры инновационной России» по лоту «Проведение научных исследований коллективами научно-образовательных центров в области информатики» по теме: «Диалоговый высокоуровневый оптимизирующий распараллеливатель программ и его приложения», госконтракт 02.740.11.0208 от 07 июля 2009 г., шифр: 2009-1.1-113-050-043.

ФЦП «Научные и научно-педагогические кадры инновационной России» по лоту «Проведение научных исследований коллективами научно-образовательных центров в области: геномных и постгеномных технологий создания лекарственных средств; клеточных технологий; биоинженерии; биоинформационных технологий»

по теме: «Создание биоинформационной технологии поиска взаимосвязанных сценариев организации в геномах животных и человека некодирующей ДНК и кодирующей белок ДНК», госконтракт 14.740.11.0006 от 01 сентября 2010 г.

Грант Российско-Белорусского сотрудничества «ТРИАДА», НИЦЭВТ, 2005г.

Внутренний грант Южного федерального университета «Учебно-научная лаборатория оптимизации и распараллеливания программ», 2007г.

ФЦП «Научные и научно-педагогические кадры инновационной России» на 2009– 2013 гг., в рамках реализации мероприятия № 1.4 «Развитие внутрироссийской мобильности научных и научно-педагогических кадров путем выполнения научных исследований молодыми учеными и преподавателями в научно-образовательных центрах», госконтракт 14.740.11.0442 от 30 сентября 2010 г.

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

Интеллектуальные и многопроцессорные системы ИМС-2003, международная научно-техническая конференция (Россия, пос. Дивноморское, 2003 г) VI международной конференции памяти академика А.П. Ершова “Перспективы систем информатики”, рабочий семинар “Наукоемкое программное обеспечение” (Новосибирск, 2006 г.) международная конференция PACO-2010 (Москва, 2010 г.) международная конференция PACO-2006 (Москва, 2006 г.) международная конференция IEEE East & West Design and Test (Москва, 2009 г.) международная конференция «Математика. Экономика. Образование» (Ростов н/Д, международная суперкомпьютерная конференция “Научный сервис в сети Интернет: суперкомпьютерные центры и задачи” (Новороссийск, 2010 г.) всероссийская научно-техническая конференция «Параллельные вычисления в задачах математической физики» (Ростов н/Д, 2004 г.) всероссийская научная конференция «Научный сервис в сети Интернет: технологии распределенных вычислений» (Новороссийск, 2005 г.).

региональная научно-методическая конференция «Современные информационные технологии в образовании: Южный федеральный округ», Ростов-на-Дону, 12-15 мая Изложенные в диссертации результаты обсуждались на научно-технических семинарах:

семинар группы ОРС, мехмат, ЮФУ, г. Ростов-на-Дону, 2003–2010 гг.

семинар факультета компьютерной инженерии и управления, ХНУРЭ, г. Харьков, Украина (руководитель проф. Хаханов В.И.). 2008 г.

семинар научно-технического совета «НКБ ВС», г. Таганрог (руководитель директор ОАО «НКБ ВС», к.т.н. Итенберг И.И.). 2008 г.

Основные положения, выносимые на защиту.

1. Алгоритмы автоматической синхронизации взаимодействия конвейеров в многоконвейерной вычислительной системе для случая многомерного гнезда циклов.

2. Алгоритмы и программная реализация автоматической синхронизации взаимодействия конвейеров для случая тесного двумерного гнезда циклов.

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

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

5. Алгоритмы и программная реализация линеаризации выражений для вычисления информационных зависимостей и оптимизации программ, в том числе для конвейеризации циклов.

Структура диссертации.

Диссертация состоит из введения, четырёх глав и заключения.

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

Описываются способы представления решетчатых графов в памяти компьютера.

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

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

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

Основным результатом этой главы является алгоритм автоматической синхронизации конвейера, включающий расчет интервала инициализации итераций и расчет буферов задержек. Задача вычисления минимального интервала инициализации итераций в общем случае является NP-полной (см. [47]), и точный алгоритм её решения состоит в переборе всех циклов на графе вычислений. Известная формула расчета интервала инициализации итераций (см. [47]) выглядит следующим образом:

где максимум берется по всем c — циклам графа вычислений, d(c) — сумма задержек операций по вершинам цикла c, p(c) — сумма расстояний зависимости по дугам зависимости входящим в цикл c, а символом a обозначено округление с избытком числа a.

В диссертации доказывается следующая теорема.

Теорема: Всегда существует элементарный цикл, на котором достигается максимум выражения (1).

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

В третьей главе рассматривается модель многоконвейерных вычислений.

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

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

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

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

Линеаризацией выражения относительно набора переменных ai называется преобразование произвольного арифметического выражения к виду:

e1*a1+e2*a2+…+en*an+en+1, где ei – выражения, ai – переменные, входящие в исходное выражение, и при этом ни одна из них не входит ни в одно из выражений ei. Таким образом, программная реализация должна определить по входному выражению и набору переменных ai, коэффициенты его линейного представления ei. Также в первом параграфе рассматривается применение линеаризации к различным подпроектам ДВОР.

Описывается процесс развития библиотеки, реализующей линеаризацию в ДВОР, с целью соответствия как можно большему покрытию языка C.

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

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

тестирование на случайном наборе входных данных, тестирование на предопределенном наборе входных данных с эталонными тестирование параллельной версии программы на эквивалентность последовательному эталону, тестирование масштабируемости параллельной программы, тестирование преобразований программ, в частности, входящих в проект В последнем параграфе четвертой главы приводится информация о проекте экспериментального конвертера с языка в Описывается поэтапное преобразование исходной программы на языке C в описание схемы на VHDL. Основным преимуществом перед всеми существующими на сегодняшний день аналогичными программными средствами является то, что по программе на языке С будет сгенерировано целое семейство описаний схемы на VHDL. Причем эти описания будут получены с помощью оптимизирующих высокоуровневых преобразований исходной программы, ориентированных на распараллеливание. А далее будут выбираться различные, подходящие для конкретной ПЛИС, реализации стандартных функций. Таким образом, инженер-схемотехник получит возможность выбора между различными вариантами автоматически сгенерированных описаний. У этого конвертера промежуточным представлением программ является граф вычислений, который рассматривается во второй главе диссертации.

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

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

Напомним, определение операции объединение графов (см. [48]).

Определение 1. Объединением графов G1(X1, U1) и G2(X2, U2) называется граф G3(X3, U3) такой, что X3 = X1 X2, U3 = U1 U2.

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

Определение 2. Дуги графа, принадлежащие остовному дереву, будем называть дугами дерева.

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

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

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

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

Рис. 2. Типы дуг графа: древесные – черный, прямые – фиолетовый, обратные – синий, поперечные – зеленый. Красная вершина – Красным цветом изображена дополнительная вершина и дополнительные дуги.

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

древесные – черный, прямые – фиолетовый, обратные – синий, поперечные – зеленый.

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

Сформулируем и докажем лемму, которая будет необходима для обоснования корректности алгоритмов, описанных далее.

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

Доказательство. Пусть дан граф G = (X, U). Добавим вспомогательную вершину с дугами, ведущими ко всем источникам графа G. Обозначим (x) номер вершины x, в соответствии с указанной нумерацией.

Таким образом, вершина будет иметь тем больший номер, чем позже она будет просмотрена вместе со всеми вершинами, принадлежащими поддереву остовного дерева с корнем в данной вершине. Пусть u = (x, y) дуга в графе G. Очевидно, что если u древесная, прямая или поперечная дуга, то (x) > (y), т.е. номер начала больше номера конца дуги.

Если u обратная дуга, то (x) < (y), номер начала меньше номера конца.

Рассмотрим произвольный цикл (x1, u1, x2, u2, …, un, x1), где xi – вершины, а ui – дуги соединяющие xi и xi-1. Предположим, что этот цикл не содержит обратных дуг. Тогда все дуги древесные, прямые и поперечные. В соответствии со сказанным в предыдущем абзаце, (xi-1) > (xi), для любого i[2, n] и (xn) > (x1) больше номера вершины x1. Но тогда, очевидно, (x1) > (x2) > … > (xn) > (x1). Полученное противоречие доказывает, что предположение об отсутствии обратных дуг в цикле неверно.

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

Определение 7. Будем называть цикл простым, если все дуги этого цикла, встречаются в нем ровно один раз.

Определение 8. Будем называть цикл элементарным, если все вершины этого цикла встречаются в нем ровно один раз.

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

1.2. Информационные зависимости в программах В этом параграфе будут изложены основы теории информационных зависимостей [14, 76]. Будут введены такие понятия, как вхождение переменной и информационная зависимость. Также будут рассмотрены типы информационных зависимостей.

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

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

Определение 11. Два вхождения называются зависимыми, если они обращаются к одной и той же ячейке памяти. При этом говорят, что вхождение v зависит от вхождения u, если вхождение v обращается к некоторой ячейке памяти позже, чем вхождение u.

a = 10;

b = 100;

В этом фрагменте программы присутствует два вхождения переменной a, два вхождения переменной b и одно переменной c. Второе (по тексту программы) вхождение переменной a, зависит от первого (по тексту программы) вхождения переменной a. Для вхождений переменной b зависимость аналогична. Вхождение переменной c не связано зависимостями ни с одним другим вхождением в этом фрагменте программы.

Конец примера.

Любую зависимость между двумя вхождениями можно отнести к одному из четырех типов.

Определение 12. Пусть вхождение u зависит от вхождения v. Зависимость между u и v называется истинной (потоковой), если u – использование, а v – генератор. В английском языке: true (flow) dependence.

Определение 13. Пусть вхождение u зависит от вхождения v. Зависимость между u и v называется антизависимостью, если u – генератор, а v – использование. В английском языке: antidependence.

a = 10;

c = 20;

В этом фрагменте программы присутствуют два вхождения переменной a, два вхождения переменной b и одно переменной c. Вхождения переменной a связаны истинной зависимостью. Вхождения переменной b связаны антизависимостью. На следующем рисунке этот пример проиллюстрирован с помощью системы OPSDemo 5 [89].

Рис. 3. Скриншот системы OPSDemo 5, демонстрирующий зависимости:

синие дуги – истинная зависимость, красные – антизависимость Конец примера.

Определение 14. Пусть вхождение u зависит от вхождения v. Зависимость между u и v называется выходной, если u – генератор и v – генератор. В английском языке: output dependence.

Определение 15. Пусть вхождение u зависит от вхождения v. Зависимость между u и v называется входной, если u – использование и v – использование. В английском языке:

input dependence.

a = b + 10;

a = b + 20;

В этом фрагменте программы присутствуют два вхождения переменной a и два вхождения переменной b. Вхождения переменной a связаны выходной зависимостью.

Вхождения переменной b связанны входной зависимостью. На следующем рисунке этот пример проиллюстрирован с помощью системы OPSDemo 5 [89].

Рис. 4. Скриншот системы OPSDemo 5, демонстрирующий граф зависимости: зеленые дуги – выходная зависимость, фиолетовые – входная Есть еще одно понятие, которое важно для понимания движения потоков данных в программе.

Определение 16. Пусть вхождение u зависит от вхождения v1 и от вхождения v2, причем обе эти зависимости истинные. Зависимость между u и v2 называется ложной, если любое данное, записанное генератором v2, будет перезаписано в ту же ячейку памяти генератором v1, до того как оно будет использовано вхождением u. В английском языке:

false dependence.