Распараллеливание программ для суперкомпьютеров с параллельной памятью и открытая распараллеливающая система тема диссертации и автореферата по ВАК РФ 05.13.11, доктор технических наук Штейнберг, Борис Яковлевич

• Штейнберг, Борис Яковлевич
• доктор технических наук
• 2004

Оглавление диссертации доктор технических наук Штейнберг, Борис Яковлевич

ВВЕДЕНИЕ.

ГЛАВА 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 шагов -т.е. никакого выигрыша по сравнению с последовательным вычислением. Исключение составляют лишь случаи, в которых суперпозиция условных опера торов опять является условным оператором (с двумя альтернативами), который и рассмотрен в данной работе.

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

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

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

Список литературы диссертационного исследования доктор технических наук Штейнберг, Борис Яковлевич, 2004 год

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. Карякин М.И.