Введение к работе
Актуальность темы.
С каждым годом все большую роль в прогрессе общества играют суперкомпьютеры. Высокопроизводительные вычисления давно используются многими важными отраслями хозяйства. Создание самолетов, автомобилей, ядерных энергетических систем, исследование семантики ДНК, прогноз погоды и изменений климата, проведение вычислительных экспериментов вместо опасных или дорогих натурных экспериментов невозможно без высокопроизводительных вычислений. Такие вычисления обеспечивают получение возможности успешнее участвовать в конкуренции, быстрее организовать производственные циклы, раньше выйти на рынок. Область применения суперкомпьютеров постоянно пополняется задачами радиолокации, криптографии, гидроакустики, моделирования зрения и слуха, распознавания образов, экономического планирования, задачами математической физики и связанными с ними вычислительными экспериментами, расчетами оптимальных конструкций и математическим моделированием сложных систем. Проблемы обороны, промышленности и науки пополняют список приложений суперЭВМ каждый год. Применяются параллельные вьгаисления и в задачах целочисленной оптимизации. Многие фундаментальные математические исследования в области многомерных интегральных уравнений остаются на уровне разработки методов и не доводятся до численного решения ввиду большого объема вычислений. Автору данной диссертации это знакомо в связи с работами [8] - [14], в частности, в [10] решена проблема, поставленная математиками из ФРГ на международной конференции по приложениям чистой математики к механике (Meister Е., 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 и многие другие суперкомпьютеры. Но в таких компьютерах получение процессором данных из модуля .памяти другого процессора ( м е ж п р о шерефгік^-<№(Шв№&ЙЬ1йм> л ь н о й
операцией.
По-другому организован доступ к параллельной памяти у суперкомпьютеров со структурно процедурной организацией вычислений. Такие компьютеры разрабатываются в НИИ МВС ТРТУ в г. Таганроге на основе идей академика РАН А.В. Каляева. У суперкомпьютеров такого типа время доступа каждого процессора к любому модулю памяти одинаково. При этом каждый процессор может одновременно получить два аргумента для бинарной операции. А сами процессоры с помощью коммутатора могут .соединяться в конвейер в соответствии с любым графом вычислений.
Для задач слабо связанных, то есть таких, которые разбиваются на семейства самостоятельных подзадач, не предполагающих частые обмены данными, суперкомпьютеры с распределенной памятью достаточно эффективны. Суперкомпьютеры со структурно-процедурной организацией вычислений способны решать и широкий класс регулярных сильно связанных задач. Но и в том и в другом случае разработка программного обеспечения оказывается очень дорогой.
Распараллеливание можно разделить на два типа: ручное (человек пишет параллельную программу) и автоматическое (компилятор или препроцессор преобразуют последовательную программу в параллельную). Оба подхода имеют свои плюсы и минусы и сосуществуют в течение многих лет, обогащая друг друга. С одной стороны, приемы автоматического распараллеливания можно использовать при ручном распараллеливании. С другой стороны, многие приемы ручного распараллеливания могут быть заложены в распараллеливающий компилятор.
В многочисленных статьях приводятся методы автоматического распараллеливания для суперкомпьютеров с общей памятью: скалярных, векторных, VLrW, SMP архитектур. Для таких компьютеров разрабатываются и эффективные распараллеливающие компиляторы, например, компиляторы Intel для Pentium4 и Itanium2 с архитектурой Hyper Threading или распараллеливающие компиляторы для SMP компьютеров на основе системы POLARIS, эффективность которых еще не совершенна и в этой области продолжаются активные исследования. Для суперкомпьютеров с распределенной памятью либо предлагаются методы ручного распараллеливания, либо системы с частично автоматическим распараллеливанием. Нет методов распараллеливания для суперкомпьютеров с параллельной общеис-пользуемой, памятью, такой, как у суперкомпьютера RP-3 или суперкомпьютеров со структурно-процедурной организацией вычислений. Недостаточно развита теория преобразования программ, которая оптимизировала, в основном, преобразования линейных участков или одномерных циклов, что позволяло получать приемлемый уровень оптимизирующих или распараллеливающих компиляторов на векторные или VLIW архитектуры. С повышением размерностей решаемых задач все более, актуальной становится проблема оптимизации вычислений в гнездах вложенных циклов. Новых методов распараллеливания требуют новые параллельные компьютеры, в которых на одном кристалле содержится несколько процессоров,
суперкомпьютеры с перестраиваемыми архитектурами и архитектурами потоков данных.
Из всего выше сказанного вытекает важная проблема, состоящая в разработке новых методов автоматического распараллеливания программ для различных суперкомпьютеров, в том числе и с параллельной памятью, которые могли бы повысить эффективность их использования, понизить требования к квалификации программистов, уменьшить время разработки и повысить надежность параллельного программного обеспечения.
Объект исследований.
Последовательные программы и их преобразования до соответствия архитектурам параллельных суперкомпьютеров.
Цель работы.
Расширение класса эффективно распараллеливаемых программ и расширение класса параллельных компьютеров, допускающих эффективное автоматическое распараллеливание.
Из сформулированной цели вытекают следующие задачи:
-
Обобщить классические преобразования программ (переименование переменных и подстановку) для приведения широкого класса циклов к конвейеризуемому виду, этим самым, расширив множество эффективно распараллеливаемых программ.
-
Расширить возможности старых и разработать новые методы распараллеливания рекуррентных циклов, как наиболее информационно связанных фрагментов программ.
-
Разработать методы эффективного распараллеливания программ для суперкомпьютеров с распределенной памятью, включая методы минимизации межпроцессорных пересылок при переразмещении данных.
-
Разработать методы эффективного распараллеливания программ для суперкомпьютеров с архитектурой перестраиваемого конвейера, включая автоматическую конвейеризацию циклов и бесконфликтное размещение данных в параллельной памяти.
-
Разработать методы создания эффективных распараллеливающих программных систем.
Методы исследований.
В процессе решения рассматриваемых задач использовались методы теории распараллеливающих/оптимизирующих преобразований программ, теории графов, теории чисел. Многие теоретические результаты практически подтверждены численными экспериментами.
Научная новизна.
1) Впервые построено обобщение таких наиболее широко применимых и эффективных преобразований, как подстановка и переименование, со случая скалярных переменных на массивы в многомерных циклах, что дает возможность получать ускорение для компьютеров широкого класса архитектур, как параллельных, так и последовательных.
-
Впервые разработаны методы распараллеливания рекуррентных циклов, обобщающие принцип сдваивания и описан класс циклов, допускающих эффективное распараллеливание. Впервые получены алгоритмы распараллеливания рекуррентных циклов с условными операторами, ранее допускавших только последовательное выполнение.
-
Исследована зависимость эффективности распараллеливания рекуррентных циклов для суперкомпьютеров с распределенной памятью от количества процессорных элементов и от соотношения времени выполнения арифметических операций ко времени подготовки (пересылки) данных и получены формулы оптимального количества процессоров.
-
Впервые разработаны оптимальные алгоритмы переразмещения данных в параллельной памяти, обобщающие транспонирование матриц, позволяющие получать оптимальное (с неулучшаемым количеством межпроцессорных пересылок) распараллеливание многомерных циклов, содержащих только входные зависимости.
-
Впервые получены методы автоматического распараллеливания циклов на суперкомпьютеры с архитектурой перестраиваемого конвейера (со структурно-процедурной организацией вычислений), причем для компьютеров такой архитектуры впервые описаны условия и получены алгоритмы автоматического бесконфликтного размещения данных в параллельной памяти.
-
Разработана концепция Открытой распараллеливающей системы, которая содержит новые подходы построения систем автоматического и автоматизированного распараллеливания.
Достоверность полученных результатов подтверждается строгими математическими формулировками и доказательствами более чем 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 г.
Основные положения, выносимые на защиту:
-
Методы преобразования программ на основе решетчатого графа, которые включают в себя подстановку и переименование индексных переменных и позволяют значительно расширить класс оптимизируемых программ.
-
Методы распараллеливания рекуррентных циклов, включающие метод опережающего вычисления коэффициентов, метод автоматической замены циклов с линейной рекуррентностью и постоянными коэффициентами на циклы без рекуррентности (и выполняемые без межпроцессорных пересылок), алгоритмы распараллеливания рекуррентных циклов с условными операторами.
-
Методы распараллеливания программ для суперкомпьютеров с распределенной памятью, включающие: формулы оптимального количества процессорных элементов для вычисления программных циклов с учетом влияния межпроцессорных пересылок; метод распараллеливания многомерных циклов, содержащих только входные зависимости, основанный на алгоритмах переразмещения многомерных массивов в параллельной памяти и доказательство оптимальности этих алгоритмов в случае полнодоступного коммутатора.
4). Методы автоматического распараллеливания последовательных программ для суперкомпьютера с архитектурой перестраиваемого конвейера, включающие алгоритмы эффективной конвейеризации программных циклов; методы преобразования программных циклов к конвейеризуемому виду; методы бесконфликтного размещения данных в параллельной (об-щеиспользуемой) памяти, которые впервые позволяют разработать для такого класса компьютеров распараллеливающие компиляторы и, этим самым, расширить возможности и эффективность их применения.
5) Открытая распараллеливающая система, воплощающая новый подход к разработке автоматически распараллеливающего программного обеспечения, которая позволяет быстрее разрабатывать системы автоматического распараллеливания для широкого класса параллельных компьютеров.
Публикации. По теме диссертации опубликовано 1 монография, 33 научных статьи и 5 методических работ. Среди научных статей 14 входят в издания «Перечня ведущих научных журналов и изданий, выпускаемых в Российской Федерации» ВАК.
Структура и объем диссертации. Диссертация состоит из введения, пяти глав, заключения и списка литературы из 213 наименований. Диссертация содержит 334 страницы текста, 27 рисунков, 45 теорем, 126 примеров.
