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

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

Штейнберг Борис Яковлевич

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

Специальность

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

АВТОРЕФЕРАТ

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

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

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

Официальные оппоненты: д.ф.-м.н., проф. Евстигнеев Владимир

Анатольевич. (ИСИ РАН г. Новосибирск) д.т.н., проф. Белявский Григорий Исаакович (РГАС г. Ростов-на-Дону) д.т.н., проф. Бабенко Людмила Климентьевна (ТРТУ, г. Таганрог)

Ведущая организация - Научно-исследовательский институт Проблем управления им. ВА Трапезникова РАН, г. Москва

Защита состоится 10 декабря 2004 г. в 14-00 на заседании диссертационного совета Д 212.259.05 при Таганрогском государственном радиотехническом университете по адресу: 347922, г. Таганрог, Ростовская обл., ул. Чехова, 2, аудитория И-347.

С диссертаций можно ознакомиться в библиотеке ТРТУ.

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

2004 г.

Просим Вас прислать отзыв, заверенный печатью учреждения по адресу: 347928, г. Таганрог, Ростовская обл., ГСП-17-а, пер. Некрасовский 44, Таганрогский государственный радиотехнический университет, Ученому секретарю диссертационного совета Д. 212.259.05 Кухаренко А.П.

aoos-ч

Актуальность темы.

С каждым годом все большую роль в прогрессе общества играют суперкомпьютеры. Высокопроизводительные вычисления давно используются многими важными отраслями хозяйства. Создание самолетов, автомобилей, ядерных энергетических систем, исследование семантики ДНК, прогноз погоды и изменений климата, проведение вычислительных экспериментов вместо опасных или дорогих натурных экспериментов невозможно без высокопроизводительных вычислений. Такие вычисления обеспечивают получение возможности успешнее участвовать в конкуренции, быстрее организовать производственные циклы, раньше выйти на рынок. Область применения суперкомпьютеров постоянно пополняется задачами радиолокации, криптографии, гидроакустики, моделирования зрения и слуха, распознавания образов, экономического планирования, задачами математической физики и связанными с ними вычислительными экспериментами, расчетами оптимальных конструкций и математическим моделированием сложных систем. Проблемы обороны, промышленности и науки пополняют список приложений суперЭВМ каждый год. Применяются параллельные вычисления и в задачах целочисленной оптимизации. Многие фундаментальные математические исследования в области многомерных интегральных уравнений остаются на уровне разработки методов и не доводятся до численного решения ввиду большого объема вычислений. Автору данной диссертации это знакомо в связи с работами [8] - [14], в частности, в [10] решена проблема, поставленная математиками из ФРГ на международной конференции по приложениям чистой математики к механике (Meister E., Speck F.-O. Some multi-dimensional Winner-Hopf equations with applications of Pure Mathematics to Mechanics, Kozubnik, Poland, 12-17 September, 1977 - препринт). Мировая гонка в повышении производительности суперкомпьютеров отражается в Интернете на сайте top500.

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

Параллельная память (много модулей памяти) позволяет считывать одновременно много данных - по одному из каждого модуля памяти. Наиболее просто эта возможность реализуется в суперкомпьютерах с распределенной памятью. Такими являются кластерные системы, n-Cube, Connection Machine, мультитранспьютерные системы, отечественные суперкомпьютеры МВС-1000 и МВС 100, распространенная в свое время в нашей стране система ПС-2000 и многие другие суперкомпьютеры. Но в таких компьютерах получение процессором данных из модуля .памяти другого

процессора ( м е ж п р о шерес] операцией.

ижа). л ь н о й

БИБЛИОТЕКА Г

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

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

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

В многочисленных статьях приводятся методы автоматического распараллеливания для суперкомпьютеров с общей памятью: скалярных, векторных, VLIW, SMP архитектур. Для таких компьютеров разрабатываются и эффективные распараллеливающие компиляторы, например, компиляторы Intel для Pentium4 и Itanium2 с архитектурой Hyper Threading или распараллеливающие компиляторы для SMP компьютеров на основе системы POLARIS, эффективность которых еще не совершенна и в этой области продолжаются активные исследования. Для суперкомпьютеров с распределенной памятью либо предлагаются методы ручного распараллеливания, либо системы с частично автоматическим распараллеливанием. Нет методов распараллеливания для суперкомпьютеров с параллельной общеис-пользуемой, памятью, такой, как у суперкомпьютера RP-3 или суперкомпьютеров со структурно-процедурной организацией вычислений. Недостаточно развита теория преобразования программ, которая оптимизировала, в основном, преобразования линейных участков или одномерных циклов, что позволяло получать приемлемый уровень оптимизирующих или распараллеливающих компиляторов на векторные или VLIW архитектуры. С повышением размерностей решаемых задач все более, актуальной становится проблема оптимизации вычислений в гнездах вложенных циклов. Новых методов распараллеливания требуют новые параллельные компьютеры, в которых на одном кристалле содержится несколько процессоров,

суперкомпьютеры с перестраиваемыми архитектурами и архитектурами потоков данных.

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

Объект исследований.

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

Цель работы.

Расширение класса эффективно распараллеливаемых программ и расширение класса параллельных компьютеров, допускающих эффективное автоматическое распараллеливание.

Из сформулированной цели вытекают следующие задачи:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Значительно сократить время разработки параллельных программ,

что особенно актуально в наше время, когда компьютеры быстро

морально устаревают.

• Существенно удешевить разработку параллельных программ.

• Ускорить выполнение некоторых программ на десятки процентов, а иногда и в несколько раз.

• Понизить требования к квалификации программистов, пишущих параллельные программы.

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

• Упростить перенос некоторых разработанных программ с последовательных компьютеров на параллельные.

• Эффективнее проектировать программно-аппаратные комплексы, с учетом новых методов распараллеливания.

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

Личный вклад.

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

Использование результатов работы.

Разработанные в диссертации методы автоматического распараллеливания для суперкомпьютера с архитектурой перестраиваемого конвейера с параллельной памятью были использованы при разработке программного обеспечения для параллельного суперкомпьютера, разработанного в НИИ МВС ТРТУ.

Методы оптимизирующих преобразований программ были использованы для ускорения (более чем в 20 раз) компьютерной нейронной модели слухового восприятия, разработанной в НИИ Нейрокибернетики РГУ.

Результаты диссертации использовались в Южном научном центре РАН в НИР «Исследование принципов построения сверхвысокопроизводительных вычислительных систем со структурной организацией вычислений»,

Описанные в диссертации методы нашли применение в НКБ Высокопроизводительных систем при выполнении НИР «Исследование и разработка методов и технических средств создания модульных интегрированных информационно управляющих систем нового поколения на основе ре-конфигурируемых вычислительных систем»

Часть исследований диссертации поддерживалась грантами: Комплексный проект РГУ гранта 2002-2006 гг. ФЦП «Интеграция», Гос. контракт - Б0024/2148, «Разработка комплекса программных средств для высокопроизводительных вычислений». Проект 0074 ФНЦ «Интеграция» 1999-2001 гг.

Грант РФФИ 02-07-90064 «Разработка и создание технологии ресурсо-независимого параллельного программирования для многопроцессорных систем с массовым параллелизмом». (Руководитель - акад. РАН А.В. Каляев, НИИ МВС при ТРТУ)

Результаты работы использовались в учебном процессе при чтении спецкурса «параллельные вычисления и преобразования программ» на мехмате РГУ. Эти результаты вошли в 5 методических пособий автора для студентов, слушающих данный спецкурс и в обучающую программу, представленную на научно-методической конференции.

На мехмате РГУ по темам, сопряженным с материалами диссертации, под руководством автора защищено две кандидатских диссертации и более 15 магистерских и дипломных работ.

Апробация работы. Основные результаты диссертации докладывались и обсуждались на Всероссийских и Международных научно-технических конференциях:

- 1-я Всесоюзная конференция "Однородные вычислительные среды и систолические структуры", 17-20 апреля 1990 г., г. Львов.

- Всесоюзный научно-технический семинар (г. Калинин) "Разработка системного и прикладного программного обеспечения МВК ПС-2000/2100, ПС-3000/3100", Москва, 1990.

- Фундаментальные и прикладные аспекты разработки больших распределенных программных комплексов. Всероссийская научная конференция. Новороссийск. 21-26.09.98. Москва: МГУ, 1998.

- Международная научно-техническая конференция <Интеллектуальные многопроцессорные системы>/1-5 сентября, 1999, Таганрог, Россия.

- Высокопроизводительные вычисления и их приложения/ Сборник трудов Всероссийской научной конференции, 30 октября - 2 ноября, 2000, г. Черноголовка.

- РАСО'2001/ Международная конференция «Параллельные вычисления и задачи управления». М., 2-4 октября 2001 г., ИЛУ РАН.

- Всероссийская научно-техническая конференция "Телематика 96". 13-17 мая 1996 г. С-Петербург.

- Интеллектуальные и многопроцессорные системы - 2001/ Международная научная конференция. Таганрог: Изд-во ТРТУ, 2001.

- СуперЭВМ и многопроцессорные вычислительные системы. МВС2002/ Международная научно-техническая конференция 26-30 июня 2002, Таганрог. Россия.

- Интеллектуальные и многопроцессорные системы ИМС-2003, Международная научно-техническая конференция/ 22-27 сентября 2003, Дивно-морское, Россия.

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

Всероссийская научно-техническая конференция «Параллельные вычисления в задачах математической физики», Ростов-на-Дону, 21-25 июня 2004 г.

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

1) Методы преобразования программ на основе решетчатого графа, которые включают в себя подстановку и переименование индексных переменных и позволяют значительно расширить класс оптимизируемых программ.

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

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

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

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

Публикации. По теме диссертации опубликовано 1 монография, 33 научных статьи и 5 методических работ. Среди научных статей 14 входят в издания «Перечня ведущих научных журналов и изданий, выпускаемых в Российской Федерации» ВАК.

Структура и объем диссертации. Диссертация состоит из введения, пяти глав, заключения и списка литературы из 213 наименований. Диссертация содержит 334 страницы текста, 27 рисунков, 45 теорем, 126 примеров.

ОСНОВНОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

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

В параграфе 1.1. делается обзор публикаций по распараллеливанию программ, из которого видно, что распараллеливание для суперкомпьютеров с параллельной памятью развито недостаточно. Здесь упоминаются методы координат и гиперплоскостей Л. Лампорта, методы параллелепипедов и гиперплоскостей В. Вальковского, разработанный в ИПУ РАН метод линейных преобразований. Упоминаются обзоры по векторизации и конвейеризации ВА. Евстигнеева, Ю.А. Французова, А.П. Черняева. Приводятся ссылки на распараллеливающие или исследующие параллелизм программные системы Московского центра «Спарк-технологий» (ИТМ и ВТ РАН) под руководством В. Волконского для суперкомпьютера с VLIW архитектурой, проекты ИПМ им. Келдыша НОРМА для параллельного программирования задач математической физики и DVM-система, в которой обычные языки программирования ФОРТРАН и С снабжены дополнительными параллельными командами, разработанная в ИПС РАН в Пере-яславль-Залесском под руководством СМ. Абрамова среда параллельного программирования с поддержкой автоматического динамического распараллеливания программ Т-система, разрабатываемая в Новосибирске под руководством В А. Евстигнеева (ИСИ РАН) система автоматического распараллеливания программ ПРОГРЕСС, система для исследования параллелизма V-Ray, разработанная под руководством чл.-корр РАН Вл. В. Воеводина (НИВЦ) и основанная на методах академика РАН В В. Воеводина. Упоминаются работы P. Feautreir, близкие по технике преобразований к исследованиям В В. Воеводина. Большое внимание уделяется зарубежным системам распараллеливания: системе исследования (тестирования) распараллеливающих и оптимизирующих компиляторов SUIF (Stanford University Intermediate Format) с Моникой Лэм и распараллеливающей системе POLARIS, разрабатываемой в Urbana University с привлечением большого числа студентов и аспирантов под руководством D. Padua.

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

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

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

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

Параграф 1.5. содержит новые, разработанные автором диссертации, преобразования программ - подстановку и переименование индексных переменных в многомерных циклах. Эти преобразования являются обобщением известных аналогичных преобразований скалярных переменных. Частный случай подстановки - протягивание констант - одно из наиболее используемых преобразований, как при распараллеливании, так и при скалярной оптимизации. Переименование переменных - важнейшее преобразование для удаления выходных дуг информационной зависимости и приведения фрагмента программы к виду с однократным присваиванием (SSA form - Single Static Assignment form), которое необходимо для распараллеливания на многие типы компьютеров. Для обоснования эквивалентности этих преобразований не достаточно обычного графа информационных связей и используется решетчатый граф программы, исследованию которого много работ посвятили В.В. Воеводин и Paul Feautrier. Попутно с подстановкой и переименованием рассматривается расщепление многомерных циклов, имеющее самостоятельную ценность для распараллеливания.

Пример 1. Двойной цикл имеет выходную зависимость по данным Do 444 1 = 3,100 Do 444 J = 3,100 X(I-l,J+2) = ...

... =X(I,J)+X(I-2,J) X(I+1,J-1) = 444 CONTINUE

Переименование приводит исходный цикл к эквивалентному фрагменту программы

DO HI J = 3,Ю0

111 XX(1,J) = X(1,J) DO 112 J = 3,4

112 XX(2,J) = X(1,J) DO 4441 = 3,100 DO 444 J = 3,100 XX(I-l,J+2) = ...

... = X(I,J)+XX(I-2,J) X(I+1,J-1) = 444 CONTINUE

DO 555 J = 3,100 555 X(2,J+2) = XX(2,J+2)

DO 666 J = 3,100 666 X(3,J+2) = XX(3,J+2)

DO 7771=3,100 777 X(I-l,100) = XX(I-l,100)

DO 888 I = 3,100 888 X(I-l,101) = XX(I-l,101)

DO 9991=3,100 999 X(I-l,102) = XX(I-l,102)

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

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

С помощью такого преобразования, как «разбиение цикла» можно одномерные циклы, в теле которых много операторов, заменять несколькими циклами, в которых мало операторов. Интересны те циклы, которые дальше разбивать уже не получается. Эти циклы, как правило, содержат рекуррентность.

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

Неизбежность пересылок в суперкомпьютерах с распределенной памятью показана и для многих циклов без рекуррентной зависимости. Известно много работ по распараллеливанию рекуррентных циклов для параллельных компьютеров с общей памятью и с длинным командным словом (УЬ!^. Для суперкомпьютеров с распределенной памятью распараллеливание эффективно, если достаточно велико так называемое расстояние зависимости.

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

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

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

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

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

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

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

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

Пример 2. Пусть Х(1) = Х(0) = 1. Цикл

DO 991 = 2,101 99 X® = 3*X(I-l) + 4*X(I-2)

эквивалентен не рекуррентному циклу 99

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

БО 99 ¡ = 2,101,10 Х0+1) = (А*(-1) + В* 4)/5

99

Если массив X после вычисления должен быть распределен по процессорным элементам для дальнейшей обработки и если межпроцессорная пересылка на два порядка дольше умножения, то данный метод уменьшает время выполнения цикла более, чем на порядок (вместо 10 пересылок, 200 последовательных умножений и 100 сложений выполняется 2 возведения в степень, каждое из которых отнимет до 10 умножений, плюс 22 одновременных умножения плюс 10 сложений).

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

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

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

Рис. 1. Схема принципа сдваивания.

Пусть D - подмножество Ят и Д - множество отображений пространства D в D, которое замкнуто относительно операции суперпозиции.

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

1. Множество А - замкнуто относительно операции суперпозиции.

2. Существует число и алгоритм, который для любых двух отображений С] и вг из D вычисляет суперпозицию в] О вг за время Тсу-

3. Существует число Тфуикщш и алгоритм, который для любого G из Д и х из D вычисляет G(x) за время Тфуикщя.

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

Будем рассматривать цикл, в котором вычисляются элементы массива:

DO 99^1^ 99 X® = G(I)(X(I-1))

(1)

Здесь G(I), 1=1,...^ - отображения из ^рекуррентного множества Д. В частности, если G(I)(Y)=Y+A(I), то цикл (1) для каждого k=l,...,N вычисляет суммы чисел А(1), 1=1,...,к. 00 99К=1,к^

ООРАЯ 991=2К1+1,Ы (2)

Х(1) = С(1)(Х(1-2К1)) 99 0(1) = 0(1)°С(1-2К"1)

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

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

Для архитектуры УЬ^ рассмотрим этот подход на примере

Пример 3.

БО 991 = 1,100 99Х(1) = А(1)*Х(1-1)+В(1)

Заменим этот цикл следующим равносильным фрагментом программы БО 661=1, 50

АА(1+50) = А(1+50)*А(М+50) ВВ(1+50)=А(1+50)*В(1-1+50)+В(1+50) 66 Х(1) = А(1)*Х(1-1)+В(1) БО 55 1=51,100,2 Х(1) = АА(1)*Х(1-2)+ВВ(1) 55 Х(1+1) = АА(1+1)*Х(1-1)+ВВ(1+1)

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

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

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

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

БО 111 1 = 1, М 111 Х(1) = 0(1)(Х(1-1))

БО2221 = М + 1^ 222 Х(1) = С(1)(Х(1-1))

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

БО 111 = 1, М 11Х(1) = 0(1)(Х(1-1)) БО221 = М+1^ 2200(1) = 0(1)°0(1-1) БО 551 = М + 1, N 55 Х(1) = 00(1)(Х(1-2))

Здесь все итерации цикла 22 могут выполняться независимо друг от друга и параллельно с циклом 11, а в цикле 55 можно параллельно считать четные и нечетные итерации.

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

БО 111 = 1, М 11Х(1) = 0(1)(Х(1-1))

БО221 = М+1^,2 2200(1) = 0(1)°0(1-1) БО331 = M + 1,N,2 33 00(1+1) = 0(1+1)°0(1)

БО441 = М+ 1 ,N,2 44 Х(1) = 00(1)(Х(1-2))

БО551 = М+1, N,2 55 Х(1+1) = 00(1)(Х(1-1))

Теперь вычисления могут быть организованы на кластере из трех процессоров. Сначала каждый из трех процессоров считает соответственно циклы с метками 11, 22, 33. Затем, первый процессор пересылает Х(М-1) во второй, а Х(М) в третий процессоры, после чего прекращает работу. С этого момента второй и третий процессоры начинают вычислять циклы с метками 44 и 55 соответственно.

Константу М надо выбрать так, чтобы циклы 11, 22 и 33 одновременно закончили выполнение. Таким образом, М должна удовлетворять равенству

М * Тфу„КШ1И ~ (N-N1)72* ТСуПерП03НЦИИ

Из этого равенства вытекает

М N/(1+2* Тфункции /Тсуперпотиции .)

Время работы этого алгоритма равно

— 2*ТпереСЬ|ЛкИ ТфуНкцИН * ( 1 + 1/(2"г4* ТфуНкиии /Тсуперпозиции •) )

Ясно, что быстродействие зависит от константы М. Эту константу можно уменьшить, если цикл 22 вычислять не на двух, а на большем количестве процессоров. Но следует иметь в виду, что такое распараллеливание приведет к дополнительным межпроцессорным пересылкам, в случае распределенной памяти.

Рис. 2. Схема метода опережающего вычисления коэффициентов

На рисунке 2 буквой «ф» обозначена операция вычисления функции, а буквой «С» - вычисление суперпозиции отображений.

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

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

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

Теорема 1. Пусть для любого 1=1,...,N элементы массивов s(l), u(I), v(I), A(I) удовлетворяют условиям u(I)*s(I)+v(I) < A(I), u(I)>0 . Тогда цикл

DO 331 = 1 ,N

IF X(I-l)>s(I) THEN X(I)=A(I)

ELSE X{I)=u(I)*X(I-l)+v(I)

33 ENDIF.

эквивалентен следующему фрагменту программы R = l

DO 99 К =1, log(N) DO PAR I = R+1,N (* Одновременное вычисление суперпозиций условных операторов 1-го и (I-R)-ro* для всех I *)

IF (A(I-R) < s(I)) THEN A(I) = u(I)*A(I-R)+v(I) u(I) = u(I)*u(I-R) v(I) = u(I)*v(I-R)+v(I) IF s(I-R) < (s(I) - v(I-R))/u(I-R) THEN s(I) = s(I-R)

ELSE s(I) = (s(I)- v(I-R))/u(I-R)

88 ENDIF 99 R=2*R

(* Вычисление искомых значений массива X *) DO 55 1 = 1, N

IF X(0) > s(I) THENX(I) = A(1)

ELSEX(I) = u(I)*X(O) + v(I)

55 ENDIF

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

Содержательным примером рассмотренных в теореме циклов может служить программа вычисления минимума последовательности чисел s(I). Аналогично могут распараллеливаться программы вычисления

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

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

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

В параграфе 3.1. рассматривается зависимость времени выполнения рекуррентного цикла (на примере задачи вычисления суммы N чисел) от количества процессорных элементов, числа итераций цикла, от времени выполнения сложения и времени на пересылку данного. Оказывается, что ставшие уже привычными суперкомпьютеры с распределенной памятью ограничены в возможностях получения ускорения при распараллеливании широкого класса программ. Эта проблема связана с медленностью межпроцессорных пересылок данных по сравнению с арифметическими операциями. Чем больше процессорных элементов (ПЭ) - тем, с одной стороны, меньше тактов с арифметическими операциями, но, с другой стороны, больше пересылок данных. Это подтверждает и эксперимент, проведенный на ВЦ Ростовского госуниверситета еще в 1989 году на суперЭВМ ПС-2000.

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

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

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

Будем рассматривать размещения массивов, при которых элемент массива находится в секторе памяти с

номером Ii mod p, где р - количество процессорных элементов. Тогда переразмещение n-мерного массива X может быть сведено к переприсваиваниям следующего вида

где ранг матрицы

равен п.

Пусть d - делитель числа р и числа q =p/d. Тогда предыдущий цикл эквивалентен следующему циклу (4):

Здесь минимум берется по всем возможным наборам целых чисел tj, je{l,...,n-I}, а максимум выбирается из двух наибольших общих делителей. Очевидно, что d является делителем числа р .

Теорема 2. Пусть числа tj подобраны так,что HOfl(ti,...,tn i , р)=1 и d п-1 п-1

тах( НОД(Ью+ 1 Ь|Д ,р), НОД(а10+ I а,/ t, , р) ). Тогда фрагмент

программы (4) можно выполнить на МВС с универсальным коммутатором за pn"'*d пересылок. Меньшее количество пересылок невозможно.

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

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

Р(А(а,о+ а,/1^...,ат0+ £ гт*1), В(Ь10+ £ .....Ьт0+ £ Ьт/1Д...)

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

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

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

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

Алгоритмы размещения для архитектуры перестраиваемого конвейера могут быть применены и к другим архитектурам суперкомпьютеров (например, для архитектуры с очень длинным командным словом - УЬГ^ для которой может быть организован программный конвейер). Важно, чтобы все модули сегментированной памяти были равноправны по отношению к каждому процессору. Это отличительная особенность от суперкомпьютеров с распределенной памятью, в которых каждый процессор может иметь один свой модуль локальной памяти с быстрым доступом - а доступ к модулям памяти других процессоров долгий.

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

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

Пример 4. БО 991=3, N Х(1) = А(1)+В(1) 99 г(1) = У(1)+г(1-1)*Х(1-2)

Свернутый (склеенный) граф этого цикла имеет следующий вид (рис. 3):

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

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

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

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

т

Рис. 3. Свернутый граф цикла.

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

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

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

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

Пример 5.

DO 99 1 = 2, N

DO99j = 2,М 99 Х(1+) = А(Ш*Ха+Я)+В(()

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

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

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

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

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

Пример 6.

БО 11= 1, N

1 = Х(а1*1+Ь1) + У(а2*1+Ь2)

При конвейерном выполнении приведенного выше цикла возникает необходимость для каждого 1 одновременно считывать из памяти переменные Х(а1*1-гЬ1) и У(а2*1+Ь2). Следовательно, массивы Х и У надо разместить так, чтобы для каждого I оба числа Х(а1*1+Ь1) и У(а2*1+Ь2) оказывались в разных секторах памяти.

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

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

Размещение массива A (array[l..N]) будем называть полурегулярным если существуют такие множество натуральных чисел {1,.,р} и число b, что для любого I из {1,..,N} элемент массива А[1] находится в сегменте памяти с номером . Число b будем назы-

вать сдвигом размещения полурегулярного массива А.

Теорема 3. Пусть массив X полурегулярно размещен. Для того чтобы при достаточно больших N элементы Х(а1*1+Ь1) и Х(а2*1+Ь2) массива X для некоторого I из {1,..,N} одновременно оказались в одном и том же сегменте памяти необходимо и достаточно, чтобы Ь2-Ы делилось на нод(а1-а2,д).

Теорема 4. Пусть даны два вхождения X(a1*I+b1) и Y(a2*I+b2) массивов X и Y полурегулярно размещенных в одних и тех же q сегментах памяти и пусть для каждого допустимого значения I элемент массива Х(1) находится в сегменте памяти с номером Si moci q , a Y(I) в сегменте памяти с номером Для того чтобы при некотором I оба элемента Х(а1*1+Ы) и Y(a2*I+b2) оказались в одном и том же сегменте памяти необходимо и достаточно, чтобы для некоторого t е Z константа с имела вид

с=нод(а1,а2) * нод( q/uod(q, (нод(а1,а2))2), (а1-а2)/нод(а1,а2) )*t+b2-b1

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

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

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

1) Ускорить разработку параллельного программного обеспечения

2) Удешевить разработку параллельного программного обеспечения

3) Создавать более надежное программное обеспечение

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

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

6) Позволяет моделировать деятельность проектируемых ЭВМ и одновременно проектировать вычислительную аппаратуру и программное обеспечение.

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

8) Позволяет создавать системы полуавтоматического распараллеливания.

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

ОРС представляет собой набор модулей следующих типов:

1) Внутреннее представление программ, которое представляет собой древовидную структуру данных (классы C++), ориентировано на хранение и преобразование программ.

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

3) Генератор компиляторов, имеющий на входе грамматики входных языков в виде форм Бэкуса-Наура, а на выходе преобразователи исходных текстов во внутреннее представление.

4) Библиотека распараллеливающих (оптимизирующих) преобразований программ во внутреннем представлении.

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

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

7) Модули распределения данных в параллельной памяти.

8) Библиотека подпрограмм переразмещения данных.

9) Программа, обучающая методам распараллеливания.

10) Интерфейс для полуавтоматического и диалогового распараллеливания.

11) Программа автоматического тестирования эквивалентности преобразований.

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

Огкрытая рягааршмсликнощал система

Рис. 5. Обучающая программа ОРС. Рис. 6. Граф информационных связей

« 71x11® ^ И'Р'-*" | ^ !)■«» [ В] | 1

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

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

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

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

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

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

Рис. 8. Граф вычислений и автоматическая синхронизация конвейера.

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

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

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

1. распознавание преобразуемого фрагмента

2. проверка (обеспечение) корректности преобразования

3. проверка эквивалентности

4. проверка целесообразности

5. выбор лучшего варианта преобразования из нескольких

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

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

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

Ниже (рис. 9, 10) представлены копии двух экранных форм с фрагментами программ (исходным и результирующим) при диалоговом выполнении преобразования «слияние циклов».

0Р5Е»ЛП0 ей"'^ 7105

«Г

(<= Л Пар, I I

Прюбразомиия программ Выбрано преобразование "Слияние циклов"

Вызовите $«тр1»* Мападм для того, чтобы загрузить одо из примерев грогрлмм

Совет {вызов Бвлр!« Мапвдоо}.

|«пр1в 1оа<1е4.

■я*яте зелечио лр>*.1енеио 'впгц *иссе«Ц» допе. >атр1е (сьаЬе!

успеино пр*е^емено 'агепд «цссесОД ¿огл 1дтр1еЬ«()е<1

й!

«[11] Ы| Ы11) 1« с[ 11] яа1с() { X 1вг а - 0; а < 10); 1 - (1 ♦ 1)) с[1] - Ь[1] «мблют^э ойесбрадовйчий | Гр^' |«ВнУТРвмнев представление | 'V ; [:. Введетев^е^вП'Ллмлсснаэе * ' ' ' ^жайплемистесНороа^мйичклое • " * < _ * Слюнимом«* 1 Р«РММ><Й«М' йфйми» {

«ог (1,- 0; и < 10); 1 - и + 1))

ЬСи - »[1]

* т ' * 1 У >

Г Г - л

Рис. 9. Выделение исходных циклов для последующего слияния в ОРС. -

Рис. 10. Результат слияния двух выделенных циклов в ОРС.

В заключении подводятся итоги выполнения поставленных задач:

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

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

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

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

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

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

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

Список основных опубликованных работ:

1. монография Штейнберг Б Я Математические методы распараллеливания рекуррентных программных циклов на суперкомпьютеры с параллельной памятью // Ростов-на-Дону, Издательство Ростопрамг) унин1»рситета-2ОТ4 г, 192 с

] РОС НАЦИОНАЛЬНАЯ I СНБЛИОТЕКА

I со*кит

1 О» М «аг

2. Штейнберг Б.Я, Распараллеливание рекуррентных циклов с условными операто-рами//Автоматика и телемеханика/ 1995, N6, с. 176-184.

3. Штейнберг Б.Я. Оптимальные параллельные переразмещения двумерных масси-вов.//Программирование, N 6,1993 г. с.81-88.

4. Штейнберг Б.Я. Бесконфликтные размещения массивов при параллельных вычислениях// Кибернетика и системный анализ/1999, N 1, с. 166-178.

5. Штейнберг Б.Я. Распараллеливание рекуррентных программных циклов.// Информационные технологии, №4,2004 г., с. 16 - 23.

6. Штейнберг Б.Я. Подстановка и переименование индексных переменных в многомерных циклах.// Известия вузов. Северокавказский регион. Юбилейный выпуск. 2002 г., с. 94-99.

7. Штейнберг Б.Я., Напрасникова М.В. Минимальное множество контрольных дуг при тестировании программных модулей.// Известия ВУЗов. Северо-Кавказский регион. Естественные науки, 2003, №4, с. 15-18.

8. Штейнберг Б.Я. Операторы типа дискретной свертки и их нетеровость.- Математические заметки, 1978, т. 23, вып. 3. с. 417-423.

9. Штейнберг Б.Я. Об операторах типа свертки на локально компактных группах.-Функциональный анализ и его приложения, 1981, т.15, вып. 3., с. 95-96.

10. Штейнберг Б.Я. Ограниченность и компактность операторов свертки с неограниченными коеффициентами на локально компактных группах.- Математические заметки, 1985, т.38, вып.2., с. 278-292.

11. Деундяк В.М., Штейнберг Б.Я. Об индексе операторов свертки с медленно изменяющимися коэффициентами на абелевых группах.- Функциональный анализ и его приложения, 1985, т. 19, вып.4., с. 84-85.

12. Штейнберг Б.Я. Операторы Винера-Хопфа с осциллирующими коэффициентами.-Дифференциальные уравнения, 1987, т.23, N 9, с. 1645-1647.

13. Штейнберг Б.Я. Нетеровость и индекс многомерных сверток с коэффициентами типа быстро осциллирующих.- Сибирский математический журнал, 1990, т. 31, N 4, с. 180-186.

14. Штейнберг Б.Я. Компактификация локально компактных групп и нетеровость операторов свертки с коэффициентами на факторгруппах// Труды С.-Петербургского математического общества, т.6,1998, с.242-260.

15. Штейнберг Б.Я. Интегральные операторы свертки с быстро изменяющимися коэффициентами на локально компактных группах// Интегро-дифференциальные операторы и их приложения, межвузовский сборник научных трудов, Ростов-на-Дону, Донской государственный технический университет, 1996, с. 142-145.

16. Steinberg B.J. The Compactification of a Local Compact Group and a Fredholmness of Convolutions with coefficients on Factor Groups// Mark Krein International Conference "Operator Theory and Applications"/ Odessa, August 18-22.1997, Abstracts.

17. Штейнберг Б.Я. Разбиение циклов для исполнения на суперкомпьютере со структурой перестраиваемого конвейера. // Искусственный интеллект. Научно-теоретический журнал. Институт проблем искусственного интеллекта НАНУ. Украина, Донецк, ДонДИШИ, "Наука и Освита", 2002, № 3 , с. 331-338.

18. Левин И.И., Штейнберг Б.Я. Сравнительный анализ эффективности параллельных программ для различных архитектур параллельных ЭВМ. // Искусственный интеллект. Научно-теоретический журнал. Институт проблем искусственного интеллекта НАНУ. Украина, Донецк, ДонДИШИ, "Наука и Освита", 2001, № 3, с. 234-242.

19. Штейнберг Б.Я., Макошенко Д.В., Черданцев Д.Н., Шульженко A.M. Внутреннее представление в открытой распараллеливающей системе// Искусственный интеллект. Научно-теоретический журнал. Институт проблем искусственного интеллекта НАНУ. Украина, Донецк, ДонДИШИ, "Наука и Освита", 2003, № 3 , с. 89-96.

20. Штейнберг Б.Я., Черданцев Д.Н., Науменко С.А., Бутов А.Э., Петренко В.В. Преобразования программ для открытой распараллеливающей системы// Искусственный интеллект. Научно-теоретический журнал. Институт проблем искусственного интеллекта НАНУ. Украина, Донецк, ДонДИШИ, "Наука и Освита", 2003, № 3, с. 97-104.

21. Штейнберг Б.Я., Напрасникова М.В., Нис З.Я. Тестирование преобразований Открытой распараллеливающей системы // Искусственный интеллект. Научно-теоретический журнал. Институт проблем искусственного интеллекта НАНУ. Украина, Донецк, ДонДИШИ, "Наука и Освита", № 3,2004 г., с. 257-264.

22. Штейнберг Б.Я. Стандартные процедуры для распараллеливания некратных циклов. Рукоп. деп. в ВИНИТИ 10.02.89, т. 701-89,1989 г., 8 с.

23. Штейнберг Б.Я. Конвейеризация двумерных циклов для суперкомпьютеров с архитектурой перестраиваемого конвейера// Высокопроизводительные вычисления и их приложения/ Сборник трудов Всероссийской научной конференции, 30 октября - 2 ноября, 2000, г. Черноголовка, с. 170-174.

24. Штейнберг Б.Я. Открытая распараллеливающая система.// РАСО'2001/ Труды международной конференции «Параллельные вычисления и задачи управления». М., 2-4 октября 2001 г., ИПУ РАН, с. 214-220.

25. Штейнберг Б.Я. Вершины области изменения параметров циклов и информационная независимость.- 1-я Всесоюзная конференция "Однородные вычислительные среды и систолические структуры", 17-20 апреля 1990 г., тезисы докладов, т.З, г. Львов, с. 112-116.

26. Штейнберг Б.Я. Распараллеливание с анализом области изменения параметров циклов и с анализом внешних переменных в индексных выражениях. - Всесоюзный научно-технический семинар (г. Калинин) "Разработка системного и прикладного программного обеспечения МВК ПС-2000/2100, ПС-3000/3100", тезисы докладов, Москва, 1990, с. 5-6.

27. Штейнберг Б.Я. Оптимальные параллельные переразмещения многомерных массивов при параллельных вычислениях// Международная научно-техническая конференция Интеллектуальные многопроцессорные системы>/1-5 сентября, 1999, Таганрог, Россия, Сборник трудов, с. 151-155.

28. Штейнберг Б.Я., Арутюнян О.Э., Бутов А.Э., Гуфан К.Ю., Морылев Р., Науменко С.А., Петренко В.В., Тузаев А., Черданцев Д.Н., Шилов М.В., Штейнберг Р.Б., Шуль-женко A.M. Обучающая распараллеливанию программа на основе ОРС.// Научно-методическая конференция «Современные информационные технологии в образовании: Южный федеральный округ», Ростов-на-Дону, 12-15 мая 2004 г., с. 248-250.

29. Адигеев М.Г., Дубров Д.В., Лазарева С.А., Штейнберг Б.Я. Экспериментальный распараллеливающий компилятор на Супер-ЭВМ со структурной организацией вычислений// Фундаментальные и прикладные аспекты разработки больших распределенных программных комплексов. Тезисы докладов всероссийской научной конференции. Новороссийск. 21-26.09.98. Москва: МГУ, 1998. с.101-108.

Издательство ООО «ЦВВГ». Лицензия ЛР № 65-36 от 05.08 99 г. Сдано в набор 19.10.04 г. Подписано в печать 19.10 04 г. Формат 60*84 1/16. Заказ № 542. Бумага офсетная. Гарнитура «Тайме». Оперативная печать. Тираж 150 экз. Печ. лист.2,0. Усл.печ л. 2.0. Типография: Издательско-полиграфический комплекс « Биос» РГУ 344091, г. Ростов-на-Дону, ул. Зорге, 28/2, кора 5 «В», тел. 929-516,659-532. Лицензия на полиграфическую деятельность № 65-125 от 09.02.98 г.

07 8

РНБ Русский фонд

2005-4 19255

ВВЕДЕНИЕ.

ГЛАВА 1. РАСПАРАЛЛЕЛИВАЩИЕ/ОПТИМИЗИРУЮЩИЕ ПРЕОБРАЗОВАНИЯ ПРОГРАММ.

1.1. ОБ ИССЛЕДОВАНИЯХ РАСПАРАЛЛЕЛИВАНИЯ ПРОГРАММ.

1.2. ИНФОРМАЦИОННАЯ ЗАВИСИМОСТЬ В ПРОГРАММЕ.

1.3. КОРРЕКТНОСТЬ ПРЕОБРАЗОВАНИЙ.

1.4. ПРЕОБРАЗОВАНИЯ ПРОГРАММ.

1.4.1. Перестановка фрагментов.

1.4.2 Канонизация циклов.

1.4.3. Раскрутка цикла.

1.4.4. Расщепление одномерного цикла.

1.4.5. Разрыв итераций, гнездование цикла и подобные им преобразования.

1.4.6. Развертка цикла.

1.4.7. Расщепление вершин (Введение временных массивов).

1.4.8. Растягивание скаляров (Замена переменной массивом).

1.4.9. Разбиение цикла.

1.4.10. Слияние циклов.

1.4.11. Приведение цикла к разбиваемому виду.

1.5. ПРЕОБРАЗОВАНИЯ ИНДЕКСНЫХ ПЕРЕМЕННЫХ В МНОГОМЕРНЫХ ЦИКЛАХ.

1.5.1. Информационная зависимость в многомерных циклах.

1.5.2. Расщепление многомерных циклов.

1.5.3. Подстановка вперед.

1.5.4. Подстановка.

1.5.5. Переименование переменных.

ВЫВОДЫ К ПЕРВОЙ ГЛАВЕ.

ГЛАВА 2. РАСПАРАЛЛЕЛИВАНИЕ РЕКУРРЕНТНЫХ ЦИКЛОВ.

2.1. ЦИКЛЫ С РЕКУРРЕНТНО ВЫЧИСЛЯЕМЫМИ ПЕРЕМЕННЫМИ.

2.2. РАСПАРАЛЛЕЛИВАНИЕ ЛИНЕЙНЫХ РЕКУРРЕНТНЫХ ЦИКЛОВ И РЕШЕНИЕ СЛАУ С ТРЕУГОЛЬНЫМИ ЛЕНТОЧНЫМИ МАТРИЦАМИ.

2.3. ЦИКЛЫ С НЕЛИНЕЙНОЙ РЕКУРРЕНТНОЙ ЗАВИСИМОСТЬЮ.

2.4. ПОСТОЯННЫЕ ЛИНЕЙНЫЕ РЕКУРРЕНТНЫЕ ЗАВИСИМОСТИ.

2.5. ПРИНЦИП СДВАИВАНИЯ ДЛЯ ВЫЧИСЛЕНИЯ РЕКУРРЕНТНЫХ ЦИКЛОВ

2.6. ПАРАЛЛЕЛЬНОЕ ВЫЧИСЛЕНИЕ РЕКУРРЕНТНЫХ ЦИКЛОВ С ОПЕРЕЖАЮЩИМ ВЫЧИСЛЕНИЕМ КОЭФФИЦИЕНТОВ.

2.7. РАСПАРАЛЛЕЛИВАНИЕ РЕКУРРЕНТНЫХ ЦИКЛОВ С УСЛОВНЫМИ ОПЕРАТОРАМИ.

2.7.1. Частично рекуррентные циклы с условными операторами.

2.7.2. Вычисление суперпозиции условных операторов.

2.7.3. Обобщение вычисления минимального элемента массива.

ВЫВОДЫ КО ВТОРОЙ ГЛАВЕ.

ГЛАВА 3. ВЛИЯНИЕ ПЕРЕСЫЛОК ДАННЫХ НА ЭФФЕКТИВНОСТЬ

ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ.

3.1. ОБ ОПТИМАЛЬНОМ КОЛИЧЕСТВЕ ПРОЦЕССОРОВ ПРИ ПАРАЛЛЕЛЬНОМ ВЫЧИСЛЕНИИ ПРОГРАММНЫХ ЦИКЛОВ.

3.1.1. Устройства для обменов данными.

3.1.2. Размещение массивов.

3.1.3. Рекуррентное вычисление массивов данных.

3.1.4. Вычисление циклов при горизонтальном размещении данных.

Ф 3.1.5. Вычисление скалярных переменных.

3.1.6. Остальные циклы и программы.

3.1.7. Возможность вычислений без пересылок данных при параллельном решении матричных задач.

3.2. ОПТИМАЛЬНЫЕ ПАРАЛЛЕЛЬНЫЕ ПЕРЕРАЗМЕЩЕНИЯ МНОГОМЕРНЫХ МАССИВОВ.

3.2.1. Пересылки данных.

3.2.2. Вспомогательные теоретико-числовые результаты.

3.2.3. Преобразования циклов.

3.2.4. Преобразования массива на суперкомпьютере с универсальным коммутатором.

3.2.5. Преобразования массива на суперкомпьютере с кольцевой сетью.

ВЫВОДЫ К ТРЕТЬЕЙ ГЛАВЕ.

ГЛАВА 4. РАСПАРАЛЛЕЛИВАНИЕ ПРОГРАММ ДЛЯ СУПЕРКОМПЬЮТЕРОВ С

• АРХИТЕКТУРОЙ ПЕРЕСТРАИВАЕМОГО КОНВЕЙЕРА.

4.1. АВТОМАТИЧЕСКАЯ СИНХРОНИЗАЦИЯ КОНВЕЙЕРА ПРИ РАСПАРАЛЛЕЛИВАНИИ ЦИКЛОВ.

4.1.1. Граф вычислений программы.

4.1.2. Граф вычислений и информационные зависимости.

4.1.3. Отображение цикла на архитектуру компьютера.

4.1.4. Синхронизация конвейера.

4.2. ОТОБРАЖЕНИЕ ПРОГРАММНЫХ ЦИКЛОВ НА ПЕРЕСТРАИВАЕМЫЙ КОНВЕЙЕР.

4.2.1. Предварительные преобразования перед конвейеризацией.

4.2.2. Разбиение программы на кадры.

4.2.3. Двумерная конвейеризация.

4.2.4. Распараллеливание рекуррентных циклов для суперкомпьютера со структурно-процедурной реализацией вычислений.

4.3. БЕСКОНФЛИКТНЫЕ РАЗМЕЩЕНИЯ МАССИВОВ ДЛЯ СУПЕРКОМПЬЮТЕРОВ СО СТРУКТУРНО-ПРОЦЕДУРНОЙ ОРГАНИЗАЦИЕЙ

• ВЫЧИСЛЕНИЙ.

4.3.1. Определения, обозначения и постановка задачи.

4.3.2. Размещение массивов для оптимального выполнения циклов.

4.3.3. Размещение массивов для оптимального выполнения развертки цикла.

4.3.4. Размещение массивов в пересекающихся множествах сегментов памяти „

4.3.5. Расширение класса индексных выражений.

4.3.6. Основной алгоритм размещения данных.

4.3.7. Улучшения разбиения множества массивов.

4.3.8. Вычисление множества бесконфликтных размещений массива с самим собой.

4.3.9. Совместные бесконфликтные размещения двух массивов.

4.3.10. Совместные бесконфликтные размещения нескольких массивов.

ВЫВОДЫ К ЧЕТВЕРТОЙ ГЛАВЕ.

ГЛАВА 5. ОТКРЫТАЯ РАСПАРАЛЛЕЛИВАЮЩАЯ СИСТЕМА.

5.1 СТРУКТУРА ОТКРЫТОЙ РАСПАРАЛЛЕЛИВАЮЩЕЙ СИСТЕМЫ.

5.1.1. Библиотека преобразований программ.

5.1.2. Архитектурно ориентированные комбинации преобразований.

5.1.3. Внутреннее представление.

5.1.4. Анализ информационных зависимостей.

• 5.1.5. Размещение данных и разбивка программы.

5.1.6. Канонический вид операторов и выражений.

5.2 ДРУГИЕ ЭЛЕМЕНТЫ И ОСОБЕННОСТИ СИСТЕМЫ.

Ф 5.2.1. Отладка и тестирование модулей системы.

5.2.2. Метод проб и ошибок при автоматическом распараллеливании.

5.2.3. Программная реализация.

5.2.4. Полуавтоматическое распараллеливание.

5.2.5. Обучающая программа на основе ОРС.

5.2.6. Сравнение ОРС с системой POLARIS.

5.2.7. Дополнительные возможности ОРС.

ВЫВОДЫ К ПЯТОЙ ГЛАВЕ.

Актуальность темы.

С каждым годом все большую роль в прогрессе общества играют суперкомпьютеры. Высокопроизводительные вычисления давно используются многими важными отраслями хозяйства [25]. Создание самолетов, автомобилей, ядерных энергетических систем, исследование семантики ДНК, прогноз погоды и изменений климата, проведение вычислительных • экспериментов вместо опасных или дорогих натурных экспериментов невозможно без применения суперЭВМ. Такие вычисления обеспечивают получение возможности успешнее участвовать в конкуренции, быстрее организовать производственные циклы, раньше выйти на рынок. Область применения суперкомпьютеров постоянно пополняется задачами криптографии, гидроакустики, радиолокации, моделирования зрения и слуха, распознавания образов, экономического планирования, задачами математической физики и связанными с ними вычислительными экспериментами, расчетами оптимальных конструкций и математическим моделированием сложных систем. Проблемы обороны, промышленности и науки пополняют список приложений суперЭВМ каждый год. Применяются параллельные вычисления и в задачах целочисленной оптимизации [132]. Многие фундаментальные математические исследования в области многомерных интегральных уравнений остаются на уровне разработки методов и не доводятся до численного решения ввиду большого объема вычислений. Автору данной диссертации это знакомо в связи с работами [147] - [155], в частности, в [149, с. 286] решена проблема, поставленная математиками из ФРГ на международной конференции по приложениям чистой математики к механике (Meister Е., Speck F.-O. Some multi-dimensional Winner-Hopf equations with applications of Pure Mathematics to Mechanics, Kozbunik, Poland, 12-17 September, 1977 - препринт). Мировая гонка в повышении производительности суперкомпьютеров отражается в Интернете на сайте top500 [210]. И наряду с развитием передовых по производительности вычислений суперкомпьютеров в различных университетах и НИИ исследователи для повышения быстродействия используют параллельные вычисления на кластерах имеющихся в их распоряжении локальных сетей. Современные технологии производства приводят к использованию принципов параллельных вычислений на однокристальных процессорах.

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

Параллельная память (много модулей памяти) позволяет считывать одновременно много данных - по одному из каждого модуля памяти. Наиболее просто эта возможность реализуется в суперкомпьютерах с распределенной памятью. Такими являются кластерные системы, n-Cube, Connection Machine, мультитранспьютерные системы, отечественные суперкомпьютеры МВС-1000 и МВС 100, распространенная в свое время в нашей стране система ПС-2000 и многие другие. Но в таких компьютерах получение процессором данных из модуля памяти другого процессора (межпроцессорная пересылка) оказывается очень длительной операцией.

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

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

Следует отметить относительность понятия «суперкомпьютер», поскольку многие идеи параллельных вычислений сегодня закладываются в однокристальные микропроцессоры. Процессоры компании Intel Pentium4 и Itanium используют технологию Hyper Treading, компания AMD готовит к выпуску двуядерный процессор, и дальнейшую перспективу увеличения производительности эти компании видят не в увеличении частоты, а в использовании параллелизма. ПЛИСы при соответствующей запрограммированности, могут работать, как несколько процессоров.

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

В многочисленных статьях приводятся методы автоматического распараллеливания на суперкомпьютеры с общей памятью: скалярных, векторных, VLIW, SMP архитектур. Для таких компьютеров разрабатываются и эффективные распараллеливающие компиляторы, например, компиляторы Intel для Pentium4 Hyper Threading и Itanium2 или распараллеливающие компиляторы для SMP компьютеров на основе системы POLARIS. Для суперкомпьютеров с распределенной памятью либо предлагаются методы ручного распараллеливания, либо системы с частично автоматическим распараллеливанием. Нет методов автоматического распараллеливания на суперкомпьютеры с параллельной, но не распределенной, памятью, такой, как у суперкомпьютера RP-3 [173] или суперкомпьютеров со структурно-процедурной организацией вычислений [71].

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

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

Объект исследований.

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

Цель работы.

Расширение класса эффективно распараллеливаемых программ и расширение класса параллельных компьютеров, допускающих эффективное автоматическое распараллеливание.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Существенно удешевить разработку параллельных программ.

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

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

• Упростить перенос многих разработанных программ с последовательных компьютеров на параллельные.

• Эффективнее проектировать программно-аппаратные комплексы, с учетом новых методов распараллеливания.

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

Личный вклад.

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

Использование результатов работы.

Разработанные в диссертации методы автоматического распараллеливания для суперкомпьютера с архитектурой перестраиваемого конвейера с параллельной памятью были использованы при разработке экспериментального распараллеливающего компилятора для суперкомпьютера, разработанного в НИИ МВС ТРТУ [4].

Методы оптимизирующих преобразований программ были использованы для ускорения (более чем в 20 раз) компьютерной нейронной модели слухового восприятия, разработанной в НИИ Нейрокибернетики РГУ.

Результаты диссертации использовались в Южном научном центре РАН в НИР «Исследование принципов построения сверхвысокопроизводительных вычислительных систем со структурной организацией вычислений»,

Описанные в диссертации методы нашли применение в НКБ Высокопроизводительных систем при выполнении НИР «Исследование и разработка методов и технических средств создания модульных интегрированных информационно управляюих систем нового поколения на основе ре-конфигурируемых вычислительных систем»

Часть исследований диссертации поддерживалась грантами: Комплексный проект РГУ гранта 2002-2006 гг. ФЦП «Интеграция», Гос. контракт - Б0024/2148, «Разработка комплекса программных средств для высокопроизводительных вычислений». Проект 0074 ФНЦ «Интеграция» 1999-2001 гг.

Грант РФФИ 02-07-90064 «Разработка и создание технологии ресурсо-независимого параллельного программирования для многопроцессорных систем с массовым параллелизмом». (Руководитель - акад. РАН А.В. Каляев, НИИ MB С при ТРТУ)

Результаты работы использовались в учебном процессе при чтении спецкурса «Параллельные вычисления и преобразования программ» на мехмате РГУ. Эти результаты вошли в 5 методических пособий автора для студентов, слушающих данный спецкурс [166] — [170] и в обучающую программу, представленную на научно-методической конференции [164].

На мехмате РГУ по темам, сопряженным с материалами диссертации, под руководством автора защищено две кандидатских диссертации и более 15 магистерских и дипломных работ.

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

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

- 1-я Всесоюзная конференция "Однородные вычислительные среды и систолические структуры", 17-20 апреля 1990 г., тезисы докладов, т.З, г. Львов.

- Всесоюзный научно-технический семинар (г. Калинин) "Разработка системного и прикладного программного обеспечения МВК ПС-2000/2100, ПС-3000/3100", тезисы докладов, Москва, 1990.

- Фундаментальные и прикладные аспекты разработки больших распределенных программных комплексов. Всероссийская научная конференция. Новороссийск. 21-26.09.98. Москва: МГУ, 1998.

- Международная научно-техническая конференция <Интеллеюуальные многопроцессорные системы>/1-5 сентября, 1999, Таганрог, Россия.

- Высокопроизводительные вычисления и их приложения/ Сборник трудов Всероссийской научной конференции, 30 октября - 2 ноября, 2000, г. Черноголовка.

- РАСО'2001/ Международная конференция «Параллельные вычисления и задачи управления». М., 2-4 октября 2001 г., ИЛУ РАН.

- Интеллектуальные и многопроцессорные системы - 2001/ Международная научная конференция. Таганрог: Изд-во ТРТУ, 2001.

- СуперЭВМ и многопроцессорные вычислительные системы. МВС'2002/ Международная научно-техническая конференция 26-30 июня 2002, Таганрог. Россия.

- Интеллектуальные и многопроцессорные системы ИМС-2003, Международная научно-техническая конференция/ 22-27 сентября 2003, Дивномор-ское, Россия.

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

- Всероссийская научно-техническая конференция «Параллельные вычисления в задачах математической физики», Ростов-на-Дону, 21-25 июня 2004 г.

По теме диссертации опубликована одна монография [160], более 30 научных статей [136] - [165], [4], [31], [98], [99], [108], [109] и 5 методических работ [166] - [170]. Среди научных статей 14 входят в издания «Пе-реченя ведущих научных журналов и изданий, выпускаемых в Российской Федерации» ВАК.

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

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

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

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

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

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

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

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

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

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

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

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

1) Ускорить разработку параллельного программного обеспечения

2) Удешевить разработку параллельного программного обеспечения

3) Создавать более надежное программное обеспечение

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

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

6) Позволяет моделировать деятельность проектируемых ЭВМ.

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

8) Сделать возможным переносимость программ (на уровне исходного текста), написанных для одного суперкомпьютера, на другой суперкомпьютер.

9) Позволяет создавать системы полуавтоматического распараллеливания.

5§С dfC »fS ^ ^ jjg ^ ^ ^ jj* ^ ^ «|« ^ ^ ^ ^ ^ jj^ ^

Автор выражает искреннюю благодарность академику РАН и Заслуженному деятелю науки

Анатолию Васильевичу Каляеву

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

Автор признателен за программную реализацию Открытой распараллеливающей системы, на которую потрачено сил больше, чем это предполагается программой обучения на мехмате РГУ, своим ученикам, аспирантам, магистрам и студентам: Д. Черданцеву, Д. Макошенко, В. Петренко, А. Шульженко, А. Бутову, С. Науменко, Р. Штейнбергу, 3. Нису, М. Шилову, В. Кривошлыкову, К. Огреничу, М. Еремеевой, М. Напрасниковой, К. Гуфану, Р. Морылеву, А. Ту-заеву, О. Арутюняну.

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

ВЫВОДЫ К ПЯТОЙ ГЛАВЕ

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

Приведенный в диссертации класс распараллеливаемых рекуррентных циклов с условными операторами вряд ли возможно существенным образом расширить. Это связано с тем, что суперпозиция условных операторов, вообще говоря, уже не может быть записана, как условный оператор. Это уже оператор типа SWITCH языка С с четырьмя альтернативами. Суперпозиция N условных операторов будет иметь 2AN альтернатив. Вычисление такого оператора потребует не менее log(2/vN) = N шагов -т.е. никакого выигрыша по сравнению с последовательным вычислением. Исключение составляют лишь случаи, в которых суперпозиция условных опера торов опять является условным оператором (с двумя альтернативами), который и рассмотрен в данной работе.

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

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

Действительно, если цикл можно разбить на части, то задача распараллеливания исходного цикла сводится к задаче распараллеливания двух циклов меньшей величины. Поэтому достаточно научиться распараллеливать только неразбиваемые циклы. При этом полезной может быть статистика: какой нераспараллеливаемый цикл как часто встречается. И архитектуру универсальных параллельных ЭВМ следует проектировать так, чтобы эффективно распараллеливалось широкое множество часто встречающихся неразбиваемых циклов. Ясно, что в неразбиваемых циклах должны быть какие-то зависимости (рекуррентные или трудно определяемые), препятствующие разбиению. Суперкомпьютеры с распределенной памятью плохо распараллеливают рекуррентные циклы из-за неизбежных и длительных обменов данными. Более удобной для распараллеливания рекуррентных циклов представляется архитектура с перестраиваемым конвейером. Эта архитектура допускает распараллеливание многих рекуррентных циклов. Классификация неразбиваемых циклов сродни классификации линейных операторов в конечномерных пространствах (через Жордановы формы) или классификации неприводимых линейных представлений групп.

1. Абрамов С., Адамович А., Коваленко М. Т-система: среда программирования с поддержкой автоматического динамического распараллеливания на платформе «IP-сеть UNIX-компьютеров». www.botik.ru/4 abram/ts-pabs.html

2. Адигеев М.Г. Экономичные коммутационные схемы и распараллеливание программ. Диссертация на соискание ученой степени кандидата технических наук, Ростов-на-Дону, ростовский госуниверситет, 2000 г., 143 с.

3. Аллен Р., Кеннеди К. Автоматическая трансляция Фортран-программ в векторную форму.//Векторизация программ: теория, методы, реализация. М.: Мир, 1991. С. 77-140.

4. Андрианов А.Н., Ефимкин К.Н., Задыхайло И.Б. Непроцедурный язык для решения задач математической физики.// Программирование, №2, 1991, с. 80-94.

5. Антонов А.С., Крысанов Б.Ю. Сравнение характеристик кластерных систем при помощи вычислительного полигона // Научный сервис в сети Интернет. Труды Всероссийской научной конференции, г. Новороссийск, 22-27 сентября 2003. М.: изд-во МГУ, с. 342-344.

6. Антонов А.С. Параллельное программирование с использованием технологии MPI.// М.: Изд-во МГУ, 2004 г., 71 с.

7. Артамонов Г.Т. Топология регулярных вычислительных сетей и сред/ М., «Радио и связь», 1985, 192 с.

8. Артамонов Г.Т., Тюрин В.Д. Топология сетей ЭВМ и многопроцессорных систем// М., «Радио и связь», 1991,248 с.

9. Архангельская А.А., Ершов В.А., Нейман В.И. Автоматическая коммутация каналов связи. М.: «Связь», 1970, 192 е.

10. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов// М., «Мир», 1979, 536 с.

11. Бабаян Б.А. Уровень программирования и архитектурные принципы построения ЭВМ //В сб. «Кибернетика и вычислительная техника», М., «Наука», 1986, №2, с. 18-27.

12. Бабаян Б. Основные принципы архитектуры Е2К. "Main Principles ofE2K Architecture", Free Software Magazine, v. 1, Issue 02, Feb 2002 17. (Китай).

13. Бабичев А.В., Лебедев В.Г. Распараллеливание программных циклов./ Программирование// 1983, N 5, с. 52-63.

14. Бахтеяров С.А., Язык программирования ОККАМ//М.: МНИИПУ, 1989, 87 с.

15. Бахтин В.А., Коновалов Н.А., Крюков В.А. Расширение языка ОрепМР Fortran для программирования GRID-приложений. Научный сервис в сети Интернет. Труды Всероссийской научной конференции, 23-28 сентября 2002, г. Новороссийск. М.: изд-во МГУ, с. 273.

16. Белецкий В.Н. Многопроцессорные и параллельные структуры с организацией асинхронных вычислений. // Киев, «Наукова думка», 1988,240 с.

17. Бенеш В.Э. Математические основы теории телефонных сообщений.-М.: «Связь», 1968,292 с.

18. Большие задачи и суперЭВМ.// ТИИЭР, том 77, №7, 1989 г.

19. Бочаров Н.В. Технологии и техника параллельного программирования.// Программирование. №1,2003, с. 5-23.

20. Букатов А.А., Дацюк В.Н., Жегуло А.И. Программирование многопроцессорных вычислительных систем// Ростов-на-Дону: Изд-во ООО «ЦВВР», 2003 г.

21. Бурцев B.C. новые подходы к оценке качества вычислительных средств.// Интеллектуальные и многопроцессорные системы — 1999/ Тезисы докладов Международной научной конференции. Таганрог: Изд-во ТРТУ, 1999, с. 9-21.

22. Головков С.JI., Рубин А.Г. Смирнов В.К. Монитор поддержки параллельных научно-технических задач в сети Интернет // Научный сервис в сети Интернет. Труды Всероссийской научной конференции, г. Новороссийск, 22-27 сентября 2003, М.: изд-во МГУ, с. 79-82.

23. Вальковский В.А., Распараллеливание алгоритмов и программ. Структурный подход/ М., «Радио и связь», 1989 г., 176 с.

24. Вальковский В.А. Параллельное выполнение циклов. Метод пирамид. Кибернетика. 1983, N 5. с. 51-55.

25. Вальковский В.А. Параллельное выполнение циклов. Метод параллелепипедов. Кибернетика. 1982, N 2. с. 51-62.

26. Валях Е. Последовательно-параллельные вычисления// М., Мир, 1985, 456 с.

27. Векторизация программ. // Векторизация программ: теория, методы, реализация. / Сборник переводов статей М.: Мир, 1991. С. 246 267.

28. Воеводин В.В. Математические модели и методы в параллельных процессах// М.: Наука, гл. ред. физ.-мат. лит., 1986, 296 с.

29. Воеводин В.В. Математические основы параллельных вычислений, М., МГУ, 1991,345 с.

30. Воеводин В.В. Воеводин Вл.В. Параллельные вычисления, С-Петербург «БХВ-Петербург», 2002, 599 с.

31. Воеводин В.В. Пакулев В.В. Определение дуг графа алгоритма. М., Отдел вычислительной математики АН СССР, 1989,22 с. (препринт).

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

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

34. Воробьев Н.Н. Числа Фибоначчи// М., Наука, Гл. ред. физ. мат. лит., 1984, 144 с.

35. Вьюкова Н.И., Галатенко В.А., Самборский С.В., Шумаков С.М. Генерация эффективного кода для процессорных архитектур с явным параллелизмом// Программирование, 2002, № 5, с. 27-51.

36. Галюк Ю.Н., Золотарев В.И., Менонов В.П. GRID: отказоустойчивая схема многокластерных вычислений // Научный сервис в сети Интернет. Труды Всероссийской научной конференции, г. Новороссийск, 22-27 сентября 2003. М.: изд-во МГУ, с. 87.

37. Гельфонд А.О. Решение уравнений в целых числах. М.: «Гос. изд-во техн.-теоретич. Литературы», 1952. 63 с.

38. Головкин Б.А. Параллельные вычислительные системы.// М., Наука,. Гл. ред. физ.-мат. лит., 1980, 518 с.

39. Гохберг И.Ц., Фельдман И.А. Уравнения в свертках и проекционные методы их решений. М.: Наука, 1971.

40. Евстигнеев В.А. Некоторые особенности программного обеспечения ЭВМ с длинным командным словом (Обзор) //Программирование, 1991, N 2, с. 69-80.

41. Евстигнеев В.А. Применение теории графов в программировании// М. «Наука», Главная редакция физико-математической литературы, 1985 г., 352 с.

42. Евстигнеев В.А., Касьянов В.Н. Оптимизирующие преобразования в распараллеливающих компиляторах// Программирование, 1996, № 6, с. 1226.

43. Евстигнеев В.А., Мирзуитова И.А. Анализ циклов: выбор кандидатов на распараллеливание. Препринт № 58, ИСИ РАН, Новосибирск, 1999, 41 с.

44. Евстигнеев В.А., Спрогис С.В. Векторизация программ. В сборнике: "Векторизация программ: теория, методы, реализация." - М.: Мир, 1991, с. 246-267.

45. Ершов Н.М., Попов A.M. Оптимизация параллельных вычислений с учетом архитектуры и быстродействия связей в вычислительной системе.// Вестн. Моск. ун-та. Сер. 15, Вычислительная математика и кибернетика. 1993, N 1.С. 24-30.

46. Жегуло О.А. Непроцедурное представление преобразований программ в системе поддержки распараллеливания. // Компьютерное моделирование. Вычислительные технологии. Ростов-на-Дону, ЦВВР, 2003 г. с. 27-40.

47. Затуливетер Ю.С. Введение в проблему параметризованного синтеза программ для параллельных компьютеров/М., ИПУ РАН, препринт, 1993, 89с.

48. Затуливетер Ю.С. К глобальному компьютеру// Научный сервис в сети Интернет. Труды Всероссийской научной конференции, г. Новороссийск, 22-27 сентября 2003. М.: изд-во МГУ, с. 186-190.

49. Игумнов А.С., Открытая платформа отладки параллельных программ// Научный сервис в сети Интернет. Труды Всероссийской научной конференции, г. Новороссийск, 22-27 сентября 2003. М.: изд-во МГУ, с. 92-94.

50. Иванников В.П., Гайсарян С.С. Особенности систем программирования для векторно-конвейерной ЭВМ//В сб. «Кибернетика и вычислительная техника», М., «Наука», 1986, №2, с. 3-17.

51. Касперский К. Техника оптимизации программ. Эффективное использование памяти. СПб.: БХВ-Петербург, 2003 г. - 456 с.

52. Касьянов В.Н., Оптимизирующие преобразования программ/ М., «Наука», 1988 г., 336 с.

53. Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. СПб.: БХВ-Петербург, 2003 г. - 1104 с.

54. Каляев А.В., Левин И.И. Модульно-наращиваемые многопроцессорные системы со структурно-процедурной организацией вычислений //М., «Янус-К», 2003, 380 с.

55. Каляев А.В., Однородные коммутационные регистровые структуры// М., «Советское радио», 1978, 334 с.

56. Каляев А.В., Многопроцессорные системы с программируемой архитектурой, М., «Радио и связь», 1984, 240 с.

57. Сэм Канер, Джек Фолк, Енг Кек Нгуен Тестирование программного обеспечения.//Киев, DiaSoft, 2000, 544 с.

58. Ки-Чанг Ким Мелкозернистое распараллеливание неполных гнезд циклов// Программирование, 1997, №2, с. 52-66.

59. Ковалев М.М. Дискретная оптимизация./ Мн. Изд-во БГУ, 1977, 192 с.

60. Коваль В.В. Современные методы трансформации программ. // Компьютерное моделирование. Вычислительные технологии. Ростов-на-Дону, ЦВВР, 2003 г. с. 41-58.

61. Кодачигов В.И. Электронная коммутация информационных каналов. — Ростов-на-Дону, изд-во Ростовского университета, 1983,208 с.

62. Корнеев В.В. Параллельные вычислительные системы// М., «Нолидж», 1999, 311 с.

63. Корнеев В.В., Киселев А.В., Современные микропроцессоры. 2 издание. М., «НОЛИДЖ», 2000 г., с. 315.

64. Корнеев В.В., Хорошевский В.Г. Архитектура вычислительных систем с программируемой структурой// Новосибирск, Ин-т математики СО АН СССР, препринт ОВС-Ю, 1979, 48 с.

65. Корнеев В.В., Хорошевский В.Г. Структура и функциональная организация вычислительных систем с программируемой структурой// Новосибирск, Ин-т математики СО АН СССР, препринт ОВС-11, 1979,48 с.

66. Котов В.Е., Сети Петри/ М. «Наука», Гл. редакция ф.-м. лит., 1984, 159 с.

67. Котов В.Е., Черкасова Л.А. Сетевой подход к описанию семантики параллельных систем и процессов. //В сб. «Кибернетика и вычислительная техника», М., «Наука», 1986, №2, с. 75-94.

68. Коуги П.М. Архитектура конвейерных ЭВМ//М., «Радио и связь», 1985 г. 358с.

69. Кристофидес Н. Алгоритмы на графах. М.: Мир, 1974. "

70. Кун С. Матричные процессоры на СБИС// М. Мир., 1991, 672 с.

71. Лазарева С.А. Многоуровневое представление программ при автоматическом распараллеливании// Математическое моделирование, 1997, т. 9, № 2, с. 31-33.

72. Лацис А.О. Как собрать и использовать суперкомпьютер.// М. «Бестселлер», 2003,238 с.

73. Лиходед Н.А. Распределение операций и массивов данных между процессорами.// Программирование, 2003, №3, с. 73-80.

74. Луговой В.В. Методы реализации внутреннего представления программ в CASE-системе распараллеливания программ. // Компьютерное моделирование. Вычислительные технологии. Ростов-на-Дону, ЦВВР, 2003 г. с. 91-99.

75. Маккиман У., Хорнинг Дж., Уортман Д. Генератор компиляторов// М., «Статистика», 1980, 527 с.

76. Маркушевич А.И. Возвратные последовательности. // М., Наука, Гл. ред. физ. мат. лит., 1983, 47 с.

77. Малер Д., Препарата Ф. Нахождение пересечения двух выпуклых многогранников./ Кибернетический сборник. Новая серия. Вып. 20// М: Мир, 1983, 224 с.

78. Матиясевич Ю.В. Вещественные числа и ЭВМ. //В сб. «Кибернетика и вычислительная техника», М., «Наука», 1986, №2, с. 104-133.

79. Метлицкий Е.А., Каверзнев В.В. Системы параллельной памяти. Теория, проектирование, применение. Ленинград, ЛГУ, 1989

80. Миренков Н.Н., Параллельное программирование для многомодульных вычислительных систем.// М., «Радио и связь», 1989, 320 с.

81. Напрасникова М.В., Штейнберг Б.Я. Автоматизация тестирования программ в учебном процессе// Тезисы докладов учебно-методической конференции "Современные информационные технологии в учебном процессе" (25-26 апреля 2000 г).-Ростов-на-Дону, 2000.

82. Немнюгин С., Стесик О. Параллельное программирование для многопроцессорных вычислительных систем. // С.-Петербург, «БХВ-Петербург», 2002,

83. Подлазов B.C. Свойства мультикольцевых и гиперкубовых коммутаторов на произвольных перестановках. // РАСО'2001/ Труды международной конференции «Параллельные вычисления и задачи управления». М., 24 октября 2001 г., ИПУ РАН, с. 152-164.

84. Прангишвили И.В., Виленкин СЛ., Медведев И.Л., Параллельные вычислительные системы с общим управлением// М.: Энергоатомиздат, 1983.-312 с.

85. Программирование на параллельных вычислительных системах. Под редакцией Р. Бэбба. // М., Мир, 1991, 372 с.

86. Самарский А.А. Введение в численные методы.-М.: Наука, 1987, 280 с.

87. Самофалов К.Г., Луцкий Г.М. Основы теории многоуровневых конвейерных вычислительных систем. Москва: Радио и связь, 1989, 272 с.

88. Серебряков В.А. Циклическая программная конвейеризация и трансляция DO циклов для сильносвязанных многопроцессорных систем// Программирование, 1992, №3, с. 54-60.

89. Системы параллельной обработки// Под редакцией Д. Ивенса, М., Мир, 1985,413 с.

90. Трахтенгерц Э.А. Программное обеспечение параллельных процессов. Москва: Наука, 1987.

91. Фаддеева В.Н., Фаддеев Д.К. Параллельные вычисления в линейной алгебре. 1.// Кибернетика.-1977.- N 6, с. 28-40.

92. Фаддеев Д.К., Фаддеева В.Н. Параллельные вычисления в линейной алгебре. 2. Кибернетика, 1982, № 3, с. 18-31,44.

93. Филамофитский М.П. Система Х-СОМ: организация распределенных вычислений в сети Интернет// Научный сервис в сети Интернет. Труды Всероссийской научной конференции, г. Новороссийск, 22-27 сентября 2003. М.: изд-во МГУ, с. 363-367.

94. Французов Ю.А. Обзор методов распараллеливания кода и программной конвейеризации// Программирование, 1992, № 3, с. 16-37.

95. Фролов А. В. Оптимизация размещения массивов в ФОРТРАН-программах на многопроцессорных вычислительных системах.// Программирование, 1998, № 3, с. 70-80.

96. Фролов А. В. Нахождение и использование ориентированных разрезов реальных графов алгоритмов/ЯТрограммирование, 1998, № 3, с. 70-80.

97. Фролов А.В. Инструментальная система для распараллеливания фортран-программ как пример использования Интернет-технологий в программировании. Тезисы докладов всероссийской научной конференции. Новороссийск. 24-29.09.2001. Москва: МГУ, 2001. с. 221-222.

98. Хокни Р.У., Джесхоуп К.Р. Параллельные ЭВМ. Архитектура, программирование и алгоритмы/ М., «радио и связь», 1986 г., 392 с.

99. Хожайнова С.А. Статистические данные о распараллеливаемости программ.- Смешанные вычисления и преобразования программ. Тезисы докладов. Новосибирск, институт систем информатики и вычислительный центр АН СССР. 27-29 ноября 1990 .

100. Хохлюк В.И. Параллельные алгоритмы целочисленной оптимизации. // М., «Радио и связь», 1987, 224 с.

101. Черняев А.П. Программные системы векторизации и распараллеливания ФОРТРАН-программ для некоторых векторно-конвейерных ЭВМ (обзор)//Программирование, 1991, №2, с. 53-68.

102. Черняев А.П. Системы программирования для высокопроизводительных ЭВМ.// Итоги науки и техники. Вычислительные науки. Т.З. М., ВИНИТИ АН СССР, 1990, с. 1-141.

103. Ширай А.Е. Системная поддержка вычислений в комплексе с автоматическим распределением ресурсов. // Интеллектуальные и многопроцессорные системы 2003/ Тезисы докладов Международной научной конференции. Таганрог: Изд-во ТРТУ, 2003, с.54-55.

104. Штейнберг Б.Я. Распараллеливание рекуррентных циклов с условными операторами//Автоматика и телемеханика/ 1995, N6, с. 176-184.

105. Штейнберг Б.Я. Открытая распараллеливающая система.// РАСО'2001/ Труды международной конференции «Параллельные вычисления и задачи управления». М., 2-4 октября 2001 г., ИПУ РАН, с. 214-220.

106. Штейнберг Б .Я. Стандартные процедуры для распараллеливания некратных циклов. Рукоп. деп. в ВИНИТИ 10.02.89, т. 701-89, 1989 г., 8 с.

107. Штейнберг Б.Я. Вершины области изменения параметров циклов и информационная независимость.- 1-я Всесоюзная конференция "Однородные вычислительные среды и систолические структуры", 17-20 апреля 1990 г., тезисы докладов, т.З, г. Львов, с. 112-116.

108. Штейнберг Б.Я. Оптимальные параллельные переразмещения двумерных массивов.//Программирование, N 6, 1993 г. с.81-88.

109. Штейнберг Б.Я. Бесконфликтные размещения массивов при параллельных вычислениях// Кибернетика и системный анализ/1999, N 1, с. 166178.

110. Штейнберг Б.Я. Операторы типа дискретной свертки и их нетеро-вость.- Математические заметки, 1978, т. 23, вып. 3., с. 417-423.

111. Штейнберг Б.Я. Об операторах типа свертки на локально компактных группах.- Функциональный анализ и его приложения, 1981, т. 15, вып. 3., с. 95-96.

112. Штейнберг Б.Я. Ограниченность и компактность операторов свертки с неограниченными коэффициентами на локально компактных группах.-Математические заметки, 1985, т.38, вып.2., с. 278-292.

113. Деундяк В.М., Штейнберг Б.Я. Об индексе операторов свертки с медленно изменяющимися коэффициентами на абелевых группах.- Функциональный анализ и его приложения, 1985, т. 19, вып.4., с. 84-85.

114. Штейнберг Б.Я. Операторы Винера-Хопфа с осциллирующими коэффициентами Дифференциальные уравнения, 1987, т.23, N 9.

115. Штейнберг Б.Я. Нетеровость и индекс многомерных сверток с коэффициентами типа быстро осциллирующих.- Сибирский математический журнал, 1990, т. 31, N 4, с. 180-186.

116. Steinberg B.J. The Compactification of a Local Compact Group and a Fredholmness of Convolutions with coefficients on Factor Groups// Mark Krein International Conference "Operator Theory and Applications"/ Odessa, August 18-22,1997, Abstracts

117. Компактификация локально компактных групп и нетеровость операторов свертки с коэффициентами на факторгруппах//Труды С.-Петербургского математического общества, т.6, 1998, с.242-260.

118. Штейнберг Б.Я. Подстановка и переименование индексных переменных в многомерных циклах.// Известия вузов. Северокавказский регион. Юбилейный выпуск. 2002 г., с. 94-99.

119. Штейнберг Б .Я. Распараллеливание рекуррентных программных циклов.// Информационные технологии, №4,2004 г., с. 16 — 23.

120. Штейнберг Б.Я. Математические методы распараллеливания рекуррентных программных циклов на суперкомпьютеры с параллельной памятью.// Ростов-на-Дону, Издательство Ростовского университета, 2004 г., 192 с.

121. Штейнберг Б.Я., Напрасникова М.В. Минимальное множество контрольных дуг при тестировании программных модулей.// Известия ВУЗов. Северо-Кавказский регион. Естественные науки, 2003, №4, с. 15-18.

122. Штейнберг Б.Я. Преобразования программ и граф информационных связей//Ростов-на-Дону, РГУ, методические указания, 1997 г., с. 23.

123. Штейнберг Б.Я. Распараллеливающие и оптимизирующие преобразования программных циклов//Ростов-на-Дону, РГУ, методические указания, 1997 г., с. 24.

124. Штейнберг Б.Я. Распараллеливание III. Разбиение программных циклов.// Ростов-на-Дону: УПЛ РГУ, 1999. 31 с.

125. Штейнберг Б.Я., Распараллеливание, IY. Подстановка и переименование индексных переменных в многомерных циклах. // Ростов-на-Дону: УПЛ РГУ, 2000,26 с.

126. Штейнберг Б.Я. Параллельное решение СЛАУ с ленточными матрицами и распараллеливание рекуррентных циклов. // Ростов-на-Дону: УПЛ РГУ, 2000,31 с.

127. Электроника, т. 61, N 5 (787), 1988 г.

128. Almasi G.S., Gottlib A. Highly Parallel Computing.- 1989, The Benja-min/Cummings Publishing Company, inc.

129. The Charm++ Programming Language Manual// University of Illinois at Urbana-Champain, 78 p., http://charm.cs.uiuc.edu/research/bluegene/

130. Cooper K.D., Torcson L. Engineering a Compiler.// Morgan Kaufmann Publishers, Elsvier Science, San Francisko, USA, 2003. . .

131. Collard Jean-Francois, Feautrier Paul, Risset Tanguy Construction of DO Loops from Systems of Affine Constraints/ZLaboratoire de I'lnformatique du Parallelisme, Lyon, Institut IMAG, Research Report № 93-15, May 1993, p. 126.

132. Croz D.J.J., Mayes P.J.D., Wasnewski J. Wilson S. Applications of Level 2 BLAS in the NAG library. Parallel Computing, 8, 1988, p. 345-350. North-Holland. . . .

133. Cytron R., Ferrante J. What's in a name? Or The value of renaming for parallelism detection and storage allocation. IBM Res. Rep. RC 12785 (#55984), 1987.

134. Enzler R. The Current Status of Reconfigurable Computing. Swiss Federal Institute of Technology. CH-8092, Curich, Technical Report, July, 1999. 22 p.

135. Fahringer Т., Scholz B. A Unified Symbolic Evaluation Framework for Parallelizing Compilers// IEEE Transactions on Parallel and Distributed Systems, vol. 11, № 11, November 2000, c. 1105-1125.

136. Faigin K.A., Hoeflinger J.P., Padua D.A., Petersen P.M., Weatherford S.A. The Polaris Internel Representation // February 18, 1994, p. 1-32., http://polaris.cs.uiuc.edu .

137. Feautrier Paul Parametric Integer Programming// Laboratoire MASI, Institut Blaise Pascal, Universite de Versailles St-Quentin, 1988, p. 25.

138. Feautrier Paul Data Flow Analysis for Array and Scalar References// International Journal of Parallel Programming/V. 20, N 1, Feb. 1991, p. 23-53.

139. Feautrier Paul. Some efficient solutions no the affine scheduling problem. Part 1. One-dimentional Time. //"International journal of Parallel Programming", V. 21, № 5, Octouber, 1992.

140. Feautrier Paul. Some efficient solutions no the affine scheduling problem. Part 2. Multidimentional Time. // Technical Report, IBP/MASI, Number 92.78, Octouber, 1992,28 p.

141. Fernandez Augustin, Llaberia Jose M., Valero-Garcia Miguel. Loop Transformation Using Nonunimodal Matrices // IEEE Transactions on Parallel and Distributed Systems, 1995, vol. 6, № 8, pp. 832-840.

142. Hartenstein R.W. The Microprocessor is no more General Purpose: Why Furture Reconfigurable Platforms will win; Proceedings of the International Conference in Innovative Systems in Silicon, ISIS'97, Austin, Texas, USA, 8-10 October, 1997.

143. Hoeflinger J.P., Paek Y., Padua D.A. Region-Based Parallelization Using the Region Test// Tech. Report, University of Illinois at Urbana-Champaign, Cntr. for Supercomputing R&D, 1996, CSRD Report, p. 1-8. http://polaris.cs.uiuc.edu

144. Kuck D.J., Kuhn R.H., Leasure В., Wolfe M. Depedance graph and compiler optimizations. Proc. 8-th ACM Symp. On Principles of Progr. Lang. (Williamsburg, Va., Jan. 26-28), 1981, p. 207-218.

145. Kuck D. The structure of computers and computations. John Wiley and Sons. Inc., New York, NY, 1978.

146. Ku Jee Myeong The Design of an Efficient and Portable Interface between Parallelizing Compiler and its Target Machine. Thesis of Master of Science, University of Illinois, 1995. http://polaris.cs.uiuc.edu .

147. Kulkurni D., ,Stumm M. Loop and Data Transformations: A Tutorial. Technical Report CSRI 337, Computer Systems Research Institute, Univercity of Toronto, June 1993,53 p.

148. Lamport L. The Coordinate Method for the parallel execution of DO loops// Sagamore Computer Conference on Parallel Processing.- 1973, p. 1-12.

149. Lamport L. The parallel execution of DO loops// Commun. ACM.-1974.-v.17, N 2, p. 83-93.

150. Lim Amy W., Lam Monika S. Maximizing Parallelism and Minimizing Synchronization with Affine Partitions. Parallel Computing, 24, 1998, p. 445475.

151. Lim Amy W., Cheong Gerald I. and Lam Monika S. An Affine Partitioning Algorithm to Maximize Parallelism and Minimize Communication. Stanford University, Stanford, CA 94305, 10 p.

152. Lim Amy W., Lam Monika S. Cache Optimizing with Affine Partitioning. 14 p.

153. Lim Amy W., Lam Monika S. Maximizing Parallelism and Minimizing Synchronization with Affine Transformations. 14 p.

154. Padua D. Multiprocessors: Discussion of some theoretical and practical problems. Ph.D. thesis. Rep. 79-990. Dept. of Computer Science. Univ. of Illinois at Urbana Champaign. Oct. 1979.

155. Pugh W. The Omega Test: a fast and practical integer programming algorithm for dependence analysis.// Comm. Of the ACM, August, 1992.201. http://polaris.cs.uiuc.edu

156. Pottenger W.M. Theory, Techniques and Experiments in Solving Recurrences in Computer Programs. Thesis Ph/D in Computer Science, University of Illinois at Urbana-Champaign, 1997. http://polaris.cs.uiuc.edu

157. Pottenger W.M. The Role of Associativity and Commutativity in the Detection and Transformation of Loop level Parallelism. University of Illinois at Urbana-Champaign. http://polaris.cs.uiuc.edu

158. Paek Yunheung. Compiling for Distributed Memory Multiprocessors Based on Access Region Analysis. Thesis Ph/D in Computer Science, University of Illinois at Urbana-Champaign, 1997. http://polaris.cs.uiuc.edu

159. Saboo N., Singla A.K., Under J.M., Kale L.V. Emulating PetaFLOPS Ma-chins and Blue Gene.// University of Illinois at Urbana-Champain, http://charm.cs.uiuc.edu/research/bluegene/

160. Schauser K.E. Compiling Dataflow into Threads^/Research project, MS Thesis, July, 1991, University of California, Berkley, 71 p.www.es .ucsb .edu/schauser/papers/91 -fpca.ps

161. Treleaven P.C. Parallel architecture overview.// Parallel Computing, 8 (1988), p. 59-70. North-Holland.

162. Wolfe M. Beyond Induction Variables //SIGPLAN 1992, v. 27, № 7, p. 162-174.

163. Министерство образования н науки Российской Федерации

164. Ростовский государственный Университет

165. РАСПАРАЛЛЕЛИВАНИЕ ПРОГРАММ ДЛЯ СУПЕРКОМПЬЮТЕРОВ С ПАРАЛЛЕЛЬНОЙ ПАМЯТЬЮ И ОТКРЫТАЯ РАСПАРАЛЛЕЛИВАЮЩАЯ СИСТЕМА."

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

167. Оптимизация и распараллеливание вычисления рекуррентных циклов.

168. Катаев О.В., зав. лаб., с.н.с., к.т.н.

169. Мельник Э.В., зав. лаб., к.т.н.

170. Дордопуло А.И., с.н.с., к.т.н.настоящим актом подтверждает, что внедрены и использовались следующиенаучно-теоретические положения докторской диссертации Штейнберга Б.Я.:

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

172. Методы отображения одномерных циклов языков программирования ФОРТРАН С на архитектуру суперкомпьютера со структурно-процедурной организацией вычислений.

173. Методы отображающихся многомерных циклов на архитектуру суперкомпьютера со структурно-процедурной организацией вычислений на1. СИСТЕМА'иъъхоснове устранения выходной зависимости и антизависимости путем переименования индексных переменных.

174. Демонстрационная версия компилятора с языка С на многопроцессорную систему со структурно-процедурной организацией вычислений.

175. РАСПАРАЛЛЕЛИВАНИЕ ПРОГРАММ ДЛЯ СУПЕРКОМПЬЮТЕРОВ С ПАРАЛЛЕЛЬНОЙ ПАМЯТЬЮ И ОТКРЫТАЯ РАСПАРАЛЛЕЛИВАЮЩАЯ1. Комиссия в составе:

176. Левин И.И., зав. отделом MB и УС, к.т.н.

177. Семерников Е.А., с.н.с., к.т.н.

178. Трунов И.Л., с.н.с., к.т.н.настоящим актом подтверждает, что внедрены и использовались следующие научно-теоретические положения докторской диссертации Штейнберга Б.Я.:

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

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

181. Алгоритм определения оптимального количества процессоров при выполнении программных циклов, обеспечивающих максимальную1. СИСТЕМА'it

182. Зав. отделом MB и УС, к.т.н.1. И.И. Левин1. С.н.с., к.т.н.1. Е.А. Семерников1. С.н.с., к.т.н.1. И.Л. Трунов1. ЗУ/

183. ZD,OS. 2D04 /ir- DM.iSloS- Щ1. УТВЕРЖДАЮ

184. Пирек;кТр"ОАО НКБ ВС, к.т.н.нберг И.И.1. АКТоб использовании результатов докторской диссертации доцента Ростовского государственного университета Штейнберга Б.Я.

185. РАСПАРАЛЛЕЛИВАНИЕ ПРОГРАММ ДЛЯ СУПЕРКОМПЬЮТЕРОВ С ПАРАЛЛЕЛЬНОЙ ПАМЯТЬЮ И ОТКРЫТАЯ РАСПАРАЛЛЕЛИВАЮЩАЯ1. Комиссия в составе:

186. Сапрыкин В.А., зав. отделом., с.н.с., к.т.н.

187. Наумов В.В., главный конструктор проекта, к.ф.м.н.настоящим актом подтверждает, что в ОАО НКБ ВС использовались следующие научно-теоретические положения докторской диссертации Штейнберга Б.Я.

188. Методы отображения одномерных циклов языка1. СИСТЕМА'itпрограммирования С на архитектуру суперкомпьютера со структурно-процедурной организацией вычислений.

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

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

191. Зав. отделом., с.н.с., к.т.н.

192. Главный конструктор проекта, к.ф.м.н. суИ Наумов1. ЪНЬ5.0^20041. АКТоб использовании результатов докторской диссертации доцента кафедры алгебры и дискретной математики мехмата Ростовского государственного университета

193. Штейнберга Бориса Яковлевича «Распараллеливание программ для суперкомпьютеров с параллельной памятью и Открытаяраспараллеливающая система».

194. ПРЕДСЕДАТЕЛЬ КОМИССИИ декан мехмата, проф.1. Ерусалимский Я.М.

195. Зам. декана по научн. работе, доц.

196. ЧЛЕНЫ КОМИССИИ Зам. декана по уч. работе, доц.

197. Зам. декана по уч. работе, доц.1. Чернявская И. А.1. Кряквин В.Д.1. Карякин М.И.