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

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

Автоматическое отображение программ на конвейерные и многоконвейерные архитектуры

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

АВТОРЕФЕРАТ

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

- 1 [іір 2012

Москва-2012 год

005011185

Работа выполнена на факультете математики, механики и компьютерных наук Южного федерального университета.

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

заслуженный работник высшей школы РФ, кандидат

физико-математических наук,

профессор Ерусалимский Яков Михайлович.

Официальные оппоненты:

доктор физико-математических наук, Лацис Алексей Оттович, доктор технических наук,

Лебедев Валентин Григорьевич.

Ведущая организация:

Санкт-Петербургский государственный университет.

Защита состоится З-И бМЛ, в ^ ^-00 назаседании

диссертационного совета Д 002.024.01 Института прикладной математики имени М.В. Келдыша РАН по адресу: 125047, Москва, Миусская пл., 4.

С диссертацией можно ознакомиться в библиотеке Института прикладной математики имени М.В. Келдыша РАН.

Автореферат разослан Р) ^ 0 ^ ^

Ученый секретарь диссертационного совета

доктор физико-математических наук Полилова Т.А.

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

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

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

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

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

Настройку связей между вычислителями в компьютерах с программируемой архитектурой удобно реализовывать на базе ПЛИС (программируемые логические интегральные схемы, РРвА). Конфигурирование (программирование) ПЛИС осуществляется с помощью специальных программных пакетов, поставляемых производителем ПЛИС. Эти пакеты получают на вход описание схемы и выполняют настройку. Этот процесс называется синтезом схемы по ее описанию. Наиболее распространенными языками для описания схем являются УГОЬ и Уеп1^.

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

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

4

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

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

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

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

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

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

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

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

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

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

Методы исследований

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

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

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

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

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

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

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

Научная новизна

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

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

3. Предложен новый алгоритм линеаризации выражений на этапе компиляции.

Практическая значимость

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

Описанные алгоритмы уже используются в реализации проекта С2НБЬ [13, 15], разрабатываемого группой ОРС (www.ops.rsu.ru). Этот конвертер предполагает по программе на языке С генерацию семейства алгоритмически эквивалентных УНБЬ-описаний микросхем с разными параметрами синтеза. Итоговое решение по выбору наиболее качественного

7

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

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

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

Внедрение результатов работы

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

Система автоматизации тестирования программ по принципу «черного ящика» использовалась при тестировании высокопроизводительного программного комплекса НРС-ИАЗК.

Визуализация программы построения графа вычислений и расчета характеристик конвейера используется в составе «Тренажера параллельного программиста» в учебном процессе на мехмате ЮФУ в спецкурсе «Параллельные вычисления и преобразования программ».

Апробация работы

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

международная научно-техническая конференция «Интеллектуальные и многопроцессорные системы ИМС-2003» (2003 г., Дивноморское); научнометодическая конференция «Современные информационные технологии в образовании: Южный федеральный округ» (2004 г., Ростов н/Д);

всероссийская научно-техническая конференция «Параллельные вычисления в задачах математической физики» (2004 г., Ростов н/Д); международная конференция «Математика. Экономика. Образование» (2005 г., Ростов н/Д); всероссийская научная конференция «Научный сервис в сети Интернет: технологии распределенных вычислений» (2005 г., Новороссийск);

VI международная конференция памяти академика А.П. Ершова «Перспективы систем информатики», рабочий семинар «Наукоемкое программное обеспечение» (2006 г., Новосибирск); международная

конференция РАСО-2006 (2006 г., Москва); международная конференция IEEE East & West Design and Test (2009 г., Москва); международная суперкомпьютерная конференция «Научный сервис в сети Интернет: суперкомпьютерные центры и задачи» (2010 г., Новороссийск);

международная конференция «Параллельные вычисления и задачи

управления» РАСО’2010. (2010 г., Москва).

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

тестированием разработанных программных модулей.

Личный вклад

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

9

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

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

В совместных работах [7,8,11,15-18] личным вкладом автора является разработка алгоритмов отображения программ на многоконвейерную модель вычислений, алгоритмов построения и анализа графа вычислений. В совместных работах [16, 18] также описывается и используется линеаризация выражений, выполненная лично автором. В совместных работах [13,14] описывается тестирующая система, в разработке которой автор принимал участие вместе с соавторами. В частности, формат представления файлов с данными разработан лично автором.

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

• НИОКР «Разработка системной поддержки

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

• ФЦП «Научные и научно-педагогические кадры инновационной

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

оптимизирующий распараллеливатель программ и его

10

приложения», госконтракт 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 г.

Публикации

Результаты диссертации опубликованы в 18 печатных работах, из которых 5 статей, в т.ч. 4 в журналах перечня ВАК и 1 в украинском журнале, и 13 публикаций в сборниках трудов и тезисов конференций.

Объем и структура диссертации

Диссертация состоит из введения, четырёх глав, заключения, приложения и списка литературы (93 наименования). Объем диссертации 152 страницы. Работа содержит 6 лемм, 6 теорем, 54 рисунка, 6 таблиц.

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

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

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

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

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

I

I

Рис. 1. Граф вычислений в ОРС 5 (ДВОР)

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

I итераций, буферов задержек) и вспомогательные алгоритмы.

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

Ш = тах[~£/(с)/р(с)~\, (1)

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

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

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

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

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

В качестве примера, можно привести следующий фрагмент программы: for (i=0; i<N; ++i)

{

у [i] = b[i] ;

for (j=0; j <N; ++j)

у [i] = у [i] +A [i] [ j ] *x [ j ] ;

}

Этот фрагмент программы может быть отображен на многоконвейерную систему как набор независимых конвейеров.

Рис. 2. Организация вычислений без передачи информации между конвейерами

Рассмотрим другой пример: for (i=l; i<N; ++i)

for (j=l; j<M; ++j)

x[i][j] = a[i] [j]*x[i-l] [j]+b[i] [j]*x[i] [j-l]+c[i][j];

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

* —► + -

\ ^

Конвейер

* + —» + -

\

Конвейер

Рис. 3. Организация вычислений с передачей информации между конвейерами

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

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

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

где в - граф информационных связей тела самого вложенного цикла в гнезде циклов, с/-дуга графа (?, система функций {/^а}, 1 < а<т описывает элементарный решетчатый граф, построенный по дуге с1, а набор выпуклых множеств {Д/,а}, I й а<т, каждое из которых является областью определения соответствующей функции /^ ц, семейство {1Уа}, 1 < а< г представляет собой семейство цепочек зависимостей такое, что цепочка Жа имеет вид {&>а р}, 1 < р< 2с/(а)+2, при этом {Т7^}, 1 < а < г семейство соответствующих функций зависимости с областями определения Д*, функции Т\ и 72 определяются следующими равенствами:

2 > шах шах

а>а,\'(0а,гд(а)^

' ,_Ч \

тыс («,/) + ч х Тсп, + £тЫс {™1а^) - ш X (I - г;)

Т2(и, V, /, 7) =------------------------2=!---------.-------------------,

I а-ОЕН^+О

а=1V, />=а У

+ Л-1 - 4-1

/= О), /2, ... ,4),/=0Г1,У2, ,Л), 5 - количество циклов в гнезде, Мх) -

количество итераций в цикле с номером х из рассматриваемого гнезда циклов, 7’,СП(1 - время пересылки данного между вычислительными элементами системы, Та\с(и, Г) - время, которое пройдет с момента старта

1-2 ( г-2

итерации I на конвейере с номером N^(1) =

I Ш4М

а=1\ ,

+1,_1 +1

ДО

момента, когда будет получен результат вычисления значения генератора и, принадлежащего самому вложенному циклу, Гса1с(и) - время, которое потребуется для вычисления значения генератора и, не принадлежащего самому вложенному циклу.

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

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

Линеаризацией выражения относительно набора переменных а, называется преобразование произвольного арифметического выражения к виду: в]*а1+е2*а2+. ,.+е„*а„+е„+1, где е,- - выражения, а, - переменные, входящие в исходное выражение, и при этом ни одна из них не входит ни в одно из выражений е,. Таким образом, программная реализация должна определить по входному выражению и набору переменных а, коэффициенты его линейного представления е,. Также в первом параграфе рассматривается

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

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

• тестирование на случайном наборе входных данных,

• тестирование на предопределенном наборе входных данных с эталонными результатами,

• тестирование параллельной версии программы на эквивалентность последовательному эталону,

• тестирование масштабируемости параллельной программы,

• тестирование преобразований программ, в частности, входящих в проект ДВОР.

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

18

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

В заключении приведены основные результаты диссертации.

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

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

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

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

4. В работе сформулированы и обоснованы алгоритмы вычисления

различных характеристик конвейера: алгоритм определения

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

обоснования корректности этих алгоритмов. В рамках проекта ДВОР, была сделана программная реализация вычисления параметров конвейера по алгоритмам описанным в данной работе.

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

Список публикаций

1. Штейнберг Р. Б. Отображение гнезд циклов на многоконвейерную архитектуру // Программирование, 2010, № 3. С. 69-80. (Перечень ВАК)

Steinberg R. Mapping loop nests to multipipelined architecture // Programming and Computer Software. MAIK Nauka/Interperiodica distributed exclusively by Springer Science+Business Media LLC. 2010. Vol 36, №3 May, P 177-185.

2. Штейнберг Р.Б. Использование решетчатых графов для исследования многоконвейерной модели вычислений // Известия вузов. Северо-кавказский регион. Естественные науки. 2009. №2. С. 16-18. (Перечень ВАК)

3. Бухановский А. В., Марьин С. В., Князьков К. В., Сиднее А. А., Жабин С. Н.,

Баглий А. П., Штейнберг Р. Б., Шамакина А. В., Воеводин В. В., Головченко Е. Н., Фалалеев Р. Т., Духанов А. В., Тарасов А. А., Шамардин Л. В., Моисеенко А. И. Результаты реализации проекта «Мобильность молодых ученых» в 2010 году: развитие функциональных элементов технологии iPSE и расширение состава прикладных сервисов // Известия вузов. Приборостроение. 2011. № 10. С. 80-87. (Перечень ВАК)

4. Штейнберг Б. Я., Кравченко Е. Н., Морылев Р. И., Нис 3. Я., Петренко В. В.,

Скиба И. С., Шаповалов В. Н., Штейнберг О. Б., Штейнберг Р. Б. Особенности реализации распараллеливающих преобразований программ в системе ДВОР // Известия вузов. Приборостроение. 2011. № 10. С. 87-89. (Перечень ВАК)

5. Штейнберг Р.Б. Вычисление задержки в стартах конвейеров для суперкомпьютеров со структурно процедурной организацией вычислений // Искусственный интеллект, (научно-теоретический журнал) / Институт проблем искусственного интеллекта НАНУ. Украина, Донецк: ДонДИШИ, «Наука и Освита». 2003. № 4. С. 105-112.

6. Штейнберг Р.Б. Вычисление задержки в стартах конвейеров для суперкомпьютеров со структурно-процедурной организацией вычислений // Интеллектуальные и многопроцессорные системы ИМС-2003: материалы Международной научнотехнической конференции. Россия, Дивноморское, 22-27 сентября 2003г. Т. 2.

7. Штейнберг Б.Я., Аруткшян О.Э., Бутов А.Э., Гуфан К.Ю., Морылев Р.И.,

Науменко С.А., Петренко В.В., Тузаев А., Черданцев Д.Н., Шилов М.В.,

Штейнберг Р.Б., Шульженко А.М. Обучающая распараллеливанию программа на основе ОРС // Научно-методическая конференция «Современные информационные технологии в образовании: Южный федеральный округ»: тезисы докладов. Ростов-на-Дону, 12-15 мая 2004 г. Ростов н/Д, 2004.

8. Штейнберг Б.Я., Бутов А.Э., Науменко С.А., Петренко В.В., Черданцев Д.Н., Штейнберг Р.Б., Шульженко А.М. Полуавтоматическое распараллеливание на основе ОРС // Всероссийская научно-техническая конференция «Параллельные вычисления в задачах математической физики»: тезисы докладов. Ростов-на-Дону, 21-25 июня 2004 г. Ростов н/Д, 2004.

9. Штейнберг Р.Б. Реализация модели конвейерных вычислений в ОРС // XIII Международная конференция “Математика. Экономика. Образование”: тезисы докладов. Ростов н/Д, 2005. 195 с. - ISBN 5-94153-097-8.

10. Штейнберг Р.Б. Некоторые оптимизирующие преобразования программ для компьютеров, допускающих многоконвейерную обработку данных : труды Всероссийской научной конференции «Научный сервис в сети Интернет: технологии распределенных вычислений», Новороссийск, 19-23 сентября 2005г. М.: Изд-во МГУ, 2005. С. 85-87.

11. Штейнберг Б.Я., Нис З.Я., Петренко В.В., Черданцев Д.Н., Штейнберг Р.Б., Шульженко А.М. Состояние и возможности открытой распараллеливающей системы (лето 2006г.): сборник трудов VI международной конференции памяти академика А.П. Ершова «Перспективы систем информатики», рабочий семинар «Наукоемкое программное обеспечение» (Workshop on Science Intensive Applied Software). 2006r. Новосибирск, 2006. С. 122-125.

12. Штейнберг Р.Б. Вычисление задержки между стартами конвейеров с учётом времени пересылки данных: труды международной конференции РАСО-2006. М.: ИПУ РАН, 2006.

13. Штейнберг Б.Я., Алымова Е.В., Баглий А.П., Морылев Р.И., Нис З.Я., Петренко В.В., Штейнберг Р.Б. Автоматизация тестирования элементов высокопроизводительного программного комплекса // Научный сервис в сети Интернет: масштабируемость, параллельность, эффективность: труды Всероссийской суперкомпьютерной конференции. Новороссийск, 21-26 сентября 2009 г. М.: Изд-во МГУ, 2009.

С. 287-291.

14. Steinberg В., Alimova Е., Baglij A., Morilev R., Nis Z., Petrenko V., Steinberg R. The System for Automated Program Testing. Proceedings of IEEE East-West Design & Test Symposium (EWDTS’09). Moscow, Russia, September 18-21, 2009. P. 218-220.

15. Steinberg B., Abramov A., Alymova E., Baglij A., Guda S., Demin S., Dubrov D., Ivchenko A., Kravchenko E., Makoshenko D., Molotnikov Z., Morilev R., Nis Z.,

Petrenko V., Povazhnij A., Poluyan S., Skiba I., Suhoverkhov S., Shapovalov V., Steinberg O., Steinberg R. Dialogue-based Optimizing Parallelizing Tool and C2HDL Converter. Proceedings of IEEE East-West Design & Test Symposium (EWDTS’09). Moscow,

Russia, September 18-21,2009. P. 216-218.

16. Штейнберг Б.Я., Абрамов A.A., Алымова E.B., Баглий А.П., Гуда С.А., Дубров Д.В., Кравченко Е.Н., Морылев Р.И., Нис З.Я., Петренко В.В., Полуян С.В., Скиба И.С., Шаповалов В.Н., Штейнберг О.Б., Штейнберг Р.Б., Юрушкин М.В. Диалоговый высокоуровневый оптимизирующий распараллеливатель (ДВОР) // Научный сервис в сети Интернет: суперкомпьютерные центры и задачи: труды международной суперкомпьютерной конференции. Новороссийск, 20-25 сентября 2010г., М.: Изд-во МГУ, 2010. С. 71-75.

17. Дубров Д.В., Штейнберг Р.Б. Экспериментальный конвертер с языка С в HDL на основе диалогового высокоуровневого оптимизирующего распараллеливателя // РАСО’2010. Москва, 26-28 октября 2010 г., М.: ИПУ РАН, 2010. С. 865-878.

18. Штейнберг Б.Я., Абрамов А.А., Баглий А.П., Морылев Р.И., Петренко В.В.,

Полуян С.В., Штейнберг Р.Б. Уточнение зависимостей программы в ДВОР: труды международной конференции «Параллельные вычисления и задачи управления» РАСО’2010. Москва, 26-28 октября 2010 г., М.: ИПУ РАН, 2010. С. 855-864.

Подписано в печать 25.01.2012 г. Формат 60*84 7^ . Бумага офсетная. Печать офсетная.

Уел. печ. л. 1,0. Уч.-изд. л. 1,0. Тираж 120 экз. Заказ № 2178.

Отпечатано в типографии ЮФУ.

44090, г. Ростов-на-Дону, пр. Стачки, 200/1 .Тел. (863) 247-80-51.

61 12-1/531 ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ

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

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

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

Научный руководитель: заслуженный работник высшей школы РФ, кандидат физико-математических наук, профессор Ерусалимский Яков Михайлович

Ростов-на-Дону 2012

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

ДИССЕРТАЦИЯ на соискание учёной степени кандидата физико-математических наук

Оглавление

Список сокращений.......................................................................................................................4

Введение.........................................................................................................................................5

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.6.2. Случай \А\ Ф О, \В\ Ф 0...........................................................................................98

3.6.3. Случай \А\ = О, \В\ ф 0.........................................................................................102

3.6.4. Случай \А\ ф0, |2?| = 0.........................................................................................107

3.6.5. Случай \А\ = 0, |Я| = 0, cf + с22 ф 0....................................................................111

3.6.6. Случай \А\ = 0, |Д| = 0, cf +с22 =0....................................................................115

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

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

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

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

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

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

Заключение.................................................................................................................................132

Приложение 1.............................................................................................................................134

Литература.................................................................................................................................144

Список сокращений

АЛУ - арифметико-логическое устройство

БДОП - быстрое дискретное ортогональное преобразование

ДВОР - диалоговый высокоуровневый оптимизирующий распараллеливатель

МВС - многопроцессорная вычислительная система

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

ПЛИС - программируемая логическая интегральная схема

ПО - программное обеспечение

ПЭ - процессорный элемент

РГА - редуцированный граф алгоритма

ЦЛП - целочисленное линейное программирование

DSP - Digital Signal Processor

FPGA - Field Programmable Gate Array

HDL - Hardware Description Language

YBA - Visual Basic for Applications

VLIW - Very Long Instruction Word

Введение

Актуальность темы. Сегодня с использованием высокопроизводительных вычислительных систем решаются задачи прогноза погоды, межмолекулярного взаимодействия, биоинформатики, нефтегазовой разведки, наноинженерии, механики, гидродинамики и т.д. [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, предлагается вручную задать архитектурную модель системного уровня. Тестирование такой модели представляется более трудоемким, чем тестирование программы на языке С. В настоящей диссертации рассматриваются вопросы генерации HDL-описаний по программе на языке С.

В работе [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], которая содержит описания моделей и архитектур для организации параллельных вычислений. Также представлены несколько классификаций архитектур, использующих параллельные вычисления. Дан широкий обзор графовых моделей программ: граф информационных связей, история вычислений, решетчатый граф и т.д. Описываются возможные применения графовых моделей в аппаратно-программных комплексах. Рассматриваются эквивалентные преобразования программ и их применение в параллельных вычислениях. Описываются способы хранения графов, среди которых стоит особенно выделить хранение решетчатого графа в виде кусочно-аффинных функций.

Целью диссертации является разработка методов автоматизации отображения программ на конвейерные и многоко