Содержание к диссертации
Введение
1. Структурно-процедурная организация вычислений 17
1.1. Актуальность задачи организации эффективных параллельных вычислений 17
1.2. Универсальные многопроцессорные вычислительные системы с массовым параллелизмом и программируемой архитектурой 27
1.3. Структурно-процедурная организация вычислений 33
1.4. Отображение кадровой структуры задачи на архитектуру МВС ПА 47
1.5. Анализ структуры задач различных классов и классификация информационных графов 51
1.6. Выводы 55
2. Преобразование информационного графа в кадровую форму и операции над кадровыми структурами 56
2.1. Отношения в информационных графах 58
2.2. Информационно-эквивалентные операции в информационных графах 63
2.3. Преобразование информационных подграфов в кадровые формы... 19
2.4. Отношения и операции в кадровых структурах 85
2.4.1. Операция Q-соединения 88
2.4.2. Операция Т-соединения 96
2.4.3. Операция Т-разъединения 102
2.4.4. Операция Q-разъединения 104
2.5. Формирование проблемно-ориентированных и специализированных макроопераций для их аппаратной реализации в макропроцессоре 108
2.6. Методы формирования структур данных и процедур параллельного бесконфликтного обращения к данным в каналах памяти многопроцессорной системы с программируемой архитектурой 113
2.7. Выводы 128
3. Эффективные кадровые формы функционально-регулярных задач 129
3.1. Общие принципы преобразования в структурно-процедурную форму функционально-регулярных подграфов 129
3.2. Структурно-процедурная реализация задачи математической физики 132
3.3. Структурно-процедурная реализация процедуры быстрого преобразования Фурье 160
3.4. Выводы 182
4. Преобразование в кадровую форму функционально-нерегулярных задач 184
4.1. Методы преобразования функционально-нерегулярных задач в структурно-процедурную форму 184
4.2. Структурно-процедурная реализация процедуры решения систем линейных уравнений 197
4.3. Структурно-процедурная реализация волновой трассировки 217
4.4. Структурно-процедурная организация вычислений в задаче кластерной группировки данных 232
4.5.Выводы 239
Заключение 240
Список использованных источников 242
- Универсальные многопроцессорные вычислительные системы с массовым параллелизмом и программируемой архитектурой
- Информационно-эквивалентные операции в информационных графах
- Структурно-процедурная реализация задачи математической физики
- Структурно-процедурная реализация процедуры решения систем линейных уравнений
Введение к работе
Актуальность темы. Последние десятилетия 20 века и начало 21 века характеризуются стремительным развитием многопроцессорных вычислительных систем (МВС). Это связано с тем, что с каждым годом возрастает сложность научно-технических задач, решить которые на однопроцессорных системах затруднительно, а то и просто не представляется. возможным. О темпах развития средств вычислительной техники, повышения их производительности говорит тот факт, что если два десятилетия назад наиболее мощные параллельные компьютеры имели производительность несколько Гфлопс, то в настоящее время наиболее мощные многопроцессорные системы имеют пиковую производительность, превышающую 40 Тфлопс. В настоящее время разрабатываются системы с производительностью до 100 и даже 1000 Тфлопс.
Бурное развитие микроэлектроники и создание семейств высокопроизводительных микропроцессоров привело к тому, что, доминирующими направлениями разработок МВС в настоящее время являются МВС с массовым параллелизмом, состоящие из тысяч параллельно функционирующих микропроцессоров, соединенных между собой через коммутационную систему.
Одной из фундаментальных проблем современной вычислительной техники является создание эффективных параллельных программ. Решением данной проблемы занимались такие видные зарубежные ученые как Дейкстра, Хоар, Хокни, Трилливен, а также многие российские ученые: А.В Каляев, Д.А. Поспелов, В.Г. Хорошевский, Р.Ю. Ясинявичус, В.В. Воеводин, В.А., Вальковскии и многие другие. Одному из направлений решения данной фундаментальной проблемы посвящена данная диссертация.
В настоящее время тысячи исследовательских групп и отдельных ученых ведут интенсивные исследования в направлении создания математических методов организации эффективных параллельных вычислений, разработки параллельных алгоритмов решения задач различных классов, а также разработки методов и программных средств автоматического распараллеливания программ для многопроцессорных систем различных архитектур. По данной тематике ежегодно публикуются тысячи статей, ежегодно проводятся десятки научно-технических конференций и симпозиумов различного уровня.
От эффективности математических и алгоритмических методов организации вычислений в современных МВС в значительной степени зависит разработка и создание их прикладного программного обеспечения и, в конечном счете, эффективность применения этих систем при решении сложных научно-технических задач больших размерностей.
Однако практически все существующие методы организации параллельных вычислений в МВС с массовым параллелизмом ориентированы на распараллеливание последовательных алгоритмов и программ. При этом исследуются только информационные взаимодействия смежных частей алгоритма (циклов, процедур и т.п.) и не уделяется должного внимания общей информационной структуре задачи. Существующие к настоящему времени методы организации параллельных вычислений ориентированы на решение сложных проблем адаптации структуры вычислительного алгоритма к структуре МВС.
До сих пор эти проблемы не решены, и это не позволяет создать масштабируемые параллельные программы для МВС с массовым параллелизмом, которые могли бы быть выполнены с одинаковой эффективностью на произвольной конфигурации вычислительной системы. В результате создание эффективных параллельных алгоритмов и программ решения задач различных классов при отсутствии эффективных методик организации вычислений в МВС с массовым параллелизмом, как правило, представляет сложную проблему.
Поэтому актуальной является задача разработки формальных методов, которые позволяют преобразовать задачу из ее исходной формы представления в форму, эффективную для реализации на МВС, и синтезировать параллельную программу, эффективно реализуемую на произвольной конфигурации системы. Большинство существующих в мире МВС с массовым параллелизмом использует мультипроцедурную организацию вычислений. При мультипроцедурной организации распараллеливание осуществляется по элементам структуры данных, и в каждом процессоре обработка ведется по независимой последовательной программе. Для обмена данными между процессорами в системе организуются специальные процедуры. Параллельные алгоритмы и параллельные программы решения сложных научно-технических задач, решаемых на МВС с массовым параллелизмом, обеспечивают достаточно низкую реальную производительность, зачастую не превышающую 10-15 % от пиковой производительности системы, вследствие того, что организация параллельных вычислений и процедуры межпроцессорных обменов требуют больше времени, чем непосредственно вычисления. В ряде случаев при создании параллельных программ для существующих МВС используются эвристические методы поиска локально-оптимальных вариантов распараллеливания, а эффективные параллельные программы удается создать лишь для определенного варианта распараллеливания.
В связи с этим программирование на МВС с массовым параллелизмом до сих пор является сложным и трудоемким процессом, намного превосходящим по сложности процесс программирования на однопроцессорных машинах. Это обуславливает чрезвычайно высокую стоимость прикладного и системного программного обеспечения МВС и ограничивает их применение.
Альтернативой существующим МВС с массовым параллелизмом являются многопроцессорные вычислительные системы с программируемой архитектурой (МВС ПА), Концепция таких систем была разработана в Научно-исследовательском институте многопроцессорных систем ТРТУ под руководством академика РАН А.В. Каляева /1, 2/.
Идея МВС с программируемой архитектурой заключается в том, чтобы позволить пользователю с помощью предоставляемых программных средств и
7соответствующей аппаратной поддержки программировать и формировать в исходной универсальной системе виртуальные специализированные вычислители, адекватные структуре решаемой задачи. Это позволяет не только подбирать структуру алгоритма к структуре системы, но и, наоборот, подбирать структуру многопроцессорной системы к структуре параллельного алгоритма,. отражающего, в первую очередь, "внутренний" параллелизм задачи, а не структуру вычислительных средств /3/.
Для многопроцессорной системы с программируемой архитектурой используется структурно-процедурная (кадровая) форма задачи. Кадр представляет собой структурно (аппаратно) реализованный подграф задачи, через который следует поток данных. Подобная организация вычислений обеспечивает максимальную скорость обработки данных, сопоставимую со скоростью специализированных вычислителей. Структура многопроцессорной системы адекватна структуре решаемой задачи. Вычисления в теле кадра-выполняются по принципу управления потоком данных и не требуют синхронизации. Настройка на кадры производится по единой управляющей программе, что обеспечивает фон-неймановский детерминизм вычислительной процедуры /4, 5/.
Для МВС ПА, как и для МВС других архитектур, актуальной является задача разработки формальных методов, позволяющих синтезировать эффективные параллельные алгоритмы и программы, которые обеспечивают высокую реальную производительность системы, максимально приближенную к ее пиковой производительности.
Разрабатываемые методы должны обеспечить оперативность создания параллельных программ задач различных классов МВС ПА. Для этого необходимо решить проблему разработки формальных методов преобразования задачи из ее исходной постановки в структурно-процедурную (кадровую) форму.
Объектом исследований являются структурно-процедурные методы организации вычислений в многопроцессорных системах с программируемой архитектурой.
Цель и задачи работы. Диссертационная работа направлена на решение проблем создания эффективных методов организации параллельных вычислений для МВС с программируемой архитектурой.
Целью работы является создание методики, позволяющей синтезировать эффективные параллельные структурно-процедурные алгоритмы задач различных классов, реализуемые на произвольной конфигурации многопроцессорной системы с программируемой архитектурой и структурно-процедурной организацией вычислений.
Разрабатываемая методика должна позволить без использования эвристических подходов преобразовать алгоритмически сформулированную _ задачу в параллельный структурно-процедурный алгоритм, позволяющий создать масштабируемую параллельную программу решения данной задачи, которая может быть выполнена на различной конфигурации МВС.
Для достижения этой цели в работе решаются следующие задачи.
1. Разработка формальных методов, позволяющих преобразовать алгоритмы задач различных классов в структурно-процедурную (кадровую) форму для различных вариантов распараллеливания задачи.
2. Разработка операций над кадрами для синтеза различных вариантов структурно-процедурных алгоритмов, реализуемых на различной t конфигурации МВС.
3. Разработка методов формирования структуры данных, обеспечивающих реализацию бесконфликтных эффективных процедур параллельного обращения к распределенной памяти МВС для решения задач различных классов.
4. Разработка эффективных масштабируемых параллельных алгоритмов решения задач различных классов на различной конфигурации МВС со структурно-процедурной организацией вычислений.
Методы исследований. При проведении исследований были использованы элементы теории вычислительных систем, элементы теории графов, теории множеств, а также реляционное исчисление. Теоретические исследования подтверждены вычислительными экспериментами на имитационной модели МВС со структурно-процедурной организацией вычислений, а также реализацией компонентов математического обеспечения на базовом модуле МВС со структурно-процедурной организацией вычислений.
Научная новизна работы заключается в разработке методики организации параллельных вычислений, базирующейся, в отличие от существующих методов, не на топологически эквивалентном преобразовании информационных графов, а на информационно-эквивалентном преобразовании графов и синтезе структурно-процедурной формы задачи, которая обеспечивает эффективную реализацию параллельных алгоритмов и линейный рост производительности системы при увеличении числа процессоров.
Разработанная методика обеспечивает высокую эффективность структурно-процедурной реализации задач различных классов, не уступающую эффективности реализации этих задач на специализированных вычислителях, при этом реальная производительность МВС ПА близка к пиковой производительности в широком диапазоне значений степени распараллеливания задач.
В ходе выполнения исследований решены следующие задачи и получены следующие результаты:
- формализовано и уточнено математическое определение кадра, на основе которого разработаны операции над кадровыми структурами, позволяющие реализовать различные варианты структурно-процедурного распараллеливания задачи;
- разработана система информационно-эквивалентных операций, обеспечивающая преобразование информационного графа в структурно-процедурную форму;
- разработаны методы бесконфликтного размещения данных в распределенной памяти многопроцессорной системы со структурно-, процедурной организацией вычислений, позволяющие синтезировать эффективные процедуры адресации и коммутации.
Практическая значимость работы заключается в том, что разработанные методы синтеза параллельных алгоритмов могут быть использованы при создании масштабируемых параллельных программ решения задач различных классов на многопроцессорных системах с программируемой архитектурой. При этом существенно (до двух раз) будут сокращены временные затраты на разработку параллельных программ, а также повышена реальная производительность системы при решении широких классов задач до. четырех раз. На основе методов преобразования задачи в структурно-процедурную форму разработан ряд оригинальных параллельных структурно-процедурных алгоритмов решения задач различных классов, в том числе, тех задач, для которых неизвестна параллельная реализация.
Использование результатов работы. Теоретические и практические результаты диссертационной работы использованы при выполнении госбюджетных и хоздоговорных НИР в НИИ МВС ТРТУ, непосредственным участником которой являлся автор диссертации.
Наиболее важными из них являются:
- "Исследование возможности путей создания вычислителя с программируемой архитектурой", руководитель НИР - член-корреспондент РАН И.А. Каляев;
- "Разработка инструментальной программно-математической системы суперкомпьютеров с массовым параллелизмом военного назначения", руководитель НИР - академик РАН А.В. Каляев, № ГР 01200100688;
- "Разработка универсальных мультимикропроцессорных систем с массовым параллелизмом и средствами аппаратно-программной поддержки синтеза виртуальных архитектур и модульной реконфигурации", руководитель . - академик РАН А.В. Каляев;
- "Многопроцессорные ЭВМ с параллельной структурой в бортовых системах принятия решений и управления автономных объектов", руководитель к.т.н. С.Г. Капустян, № ГР 01.9.90002062;
- "Дальнейшее развитие теории многопроцессорных вычислительных систем с массовым параллелизмом, программируемой под структуру задачи архитектурой и структурно-процедурной реализацией вычислительного процесса", руководитель - академик РАН А.В. Каляев, № ГР 01.2.00102845;
- "Разработка и создание методов и программно-аппаратных средств для структурно-процедурной организации вычислений в суперЭВМ с программируемой архитектурой", руководитель - академик РАН А.В. Каляев;
- "Разработка методологии организации структурно-процедурных вычислений на многопроцессорных суперЭВМ с массовым параллелизмом и программируемой архитектурой", руководитель - к.т.н. И.И.Левин, № ГР 01990002076;
- "Теоретические и практические основы построения и применения мультипроцессорных вычислительных систем с программируемой архитектурой для решения задач прикладной физики и математики", руководитель - академик РАН А.В. Каляев, № ГР 01970003041;
- "Разработка и исследование архитектуры, принципов построения и элементной базы высокопроизводительного универсального суперпроцессора со структурной организацией вычислений", руководитель - академик РАН А.В.Каляев, № ГР 019100054183;
- "Исследование и разработка фундаментальных принципов и методов программирования многопроцессорных вычислительных систем с массовым параллелизмом, программируемой архитектурой и структурно-процедурной организацией вычислений", руководитель - академик РАН А.В. Каляев.
Апробация работы. Основные результаты работы докладывались и обсуждались на всероссийских и международных научно-технических конференциях:
Всероссийская научно-техническая конференция "Актуальные проблемы твердотельной электроники и микроэлектроники", Таганрог, 1994 г.;
-Всероссийская научно-техническая конференция с международным участием "Теория цепей и сигналов", Новочеркасск, 1996 г.;
- VI международный семинар "Распределенная обработка информации", Новосибирск, 1998 г.;
- Всероссийская научно-техническая конференция с международным участием "Компьютерные технологии в инженерной и управленческой деятельности", Таганрог, 1998 г.;
- IV всероссийская научно-техническая конференция "Нейрокомпьютеры щ и их применение", Москва, 1998 г.;
- V всероссийская научно-техническая конференция "Нейрокомпьютеры и их применение", Москва, 1999 г.;
-Международная конференция "Интеллектуальные многопроцессорные системы (ИМС 99)", Таганрог, 1999 г.;
- Международная конференция "Искусственный интеллект-2000",-Кацивели, 2000 г.;
- Международная конференция "Интеллектуальные и многопроцессорные
системы-2001", пос. Дивноморское, 2001 г.
По теме диссертации опубликовано 18 печатных работ, в том числе 7 - в центральной печати.
Наиболее важными из публикаций являются:
Левин И.И., Пономарев И.М. Реализация алгоритма волновой трассировки на многопроцессорной системе со структурной организацией вычислений. //Деп. ВИНИТИ, N 1553-В95, 1995, 49 с. t Левин И.И., Пономарев И.М. Реализация БПФ на многопроцессорной системе со структурной организацией вычислений. // Электромеханика, N 4, 1995,33 с.
Пономарев И.М. Методы преобразования задач в структурно-процедурную форму. // Труды международной конференции
"Интеллектуальные многопроцессорные системы (ИМС 99)". -Таганрог. Изд-во ТРТУ, 1999. -с. 147-150.
Левин И.И., Пономарев И.М. Структурно-процедурная реализация кластерной группировки данных в задачах обработки изображений. // "Электромеханика", 1999, № 2. с. 54-57.
Каляев А.В., Левин И.И., Пономарев И.М. Базовый модуль многопроцессорной вычислительной системы с программируемой архитектурой для эффективного решения исследовательских и производственных задач. // Наука - производству, 1999 г., №11. с.33-39.
Левин И.И., Пономарев И.М. Методика организации высокоэффективных параллельных вычислений в многопроцессорных системах. // Труды международной конференции "Искусственный интеллект-2000". Таганрог: Изд-во ТРТУ, 2000.-с. 142-144.
Левин И.И., Пономарев И.М., Шматок А.В. Методы преобразования параллельных программ под структуру вычислительной системы. // Искусственный интеллект. Донецк (Украина): изд-во ДонГИИИ "Наука і освіта" №3, 2001, с. 213-227.
Основные положения, выносимые на защиту:
- формальные методы преобразования алгоритма задачи в структурно-процедурную (кадровую) форму, которая естественным образом отображается в структуру многопроцессорной вычислительной системы с программируемой архитектурой; -методы формирования кадровых структур, позволяющие синтезировать кадровые формы задач для различных вариантов распараллеливания и, как следствие, решить задачу на различной конфигурации МВС;
- методы организации структуры данных, обеспечивающие бесконфликтное параллельное обращение к каналам памяти многопроцессорной вычислительной системы с программируемой архитектурой;
- параллельные структурно-процедурные алгоритмы задач различных классов, подтверждающие эффективность разработанных формальных методов синтеза масштабируемых параллельных алгоритмов.
Структура диссертации. Диссертация состоит из введения, четырех глав, заключения и библиографического списка.
Во введении обоснована актуальность работы, дана ее общая характеристика, сформулированы цель и задачи исследования.
В первой главе формализуются основные определения структурно-процедурной организации вычислений и формулируются задачи преобразования вычислительного алгоритма в форму, эффективную для реализации в МВС ПА. Проведен анализ различных методов организации параллельных вычислений для МВС с массовым параллелизмом, показаны нерешенные проблемы создания эффективных параллельных программ.
Описаны общие принципы преобразования алгоритма задачи в структурно-процедурную форму, которая наиболее эффективно реализуется в многопроцессорных системах с программируемой архитектурой.
Проведен анализ структуры задач различных классов и определены проблемы преобразования этих задач в структурно-процедурную форму.
Формализовано описание структурно-процедурной (кадровой) формы задачи, что позволяет выработать более точные требования к реализации формальных математических методов преобразования алгоритма задачи в параллельную программу.
Во второй главе на основании определений структурно-процедурной организации вычислений излагаются формальные методы преобразования информационного графа задачи в структурно-процедурную (кадровую) форму. Представлена система информационно-эквивалентных операций над информационными графами, позволяющая преобразовать граф в функционально-регулярную форму, из которой естественным образом может быть синтезирована кадровая форма задачи.
На основании уточненного определения кадра задачи и его компонентов формализовано преобразование множества информационных подграфов в кадр.
Формализована система операций над кадрами, которая позволяет синтезировать кадры для различных вариантов распараллеливания и, как следствие, реализовать их на различных конфигурациях МВС ПА.
Рассмотрены методы формирования структуры данных, единой для всех кадров задачи, а также методы формирования процедур доступа к каналам распределенной памяти многопроцессорной системы.
В третьей главе на основании методов преобразования задачи в кадровую форму и методов формирования бесконфликтных процедур обращения к памяти формулируется методика преобразования функционально-регулярных задач в структурно-процедурную форму.
Представлены примеры структурно-процедурной реализации типичных представителей функционально-регулярных задач, доказывающие эффективность разработанной методики.
Для процедуры быстрого преобразование Фурье синтезировано семейство структурно-процедурных алгоритмов, на основе которых может быть создана масштабируемая параллельная программа для МВС ПА. Показано, что применение разработанных операций над кадровыми структурами позволило оптимизировать процедуры адресации и коммутации и повысить эффективность решения задач на МВС до эффективности реализации задачи на специализированном вычислителе. Аналогичный результат получен для задачи математической физики, решаемой итерационным методом одновременных смещений.
В четвертой главе формулируется расширенная методика, позволяющая синтезировать параллельные структурно-процедурные алгоритмы для функционально-нерегулярных задач, в том числе, тех, для которых в настоящее время неизвестна эффективная параллельная реализация. Представлено формализованное описание операции векторизации информационных вершин, которая позволяет преобразовать исходный функционально-нерегулярный граф
в векторизированный граф, который может быть преобразован в кадровую форму.
На основе расширенной методики синтезированы эффективные структурно-процедурные алгоритмы типичных представителей
функционально-нерегулярных задач - задачи решения СЛАУ методом Гаусса, а также задачи трассировки по волновому алгоритму Ли.
На примере структурно-процедурной реализации задачи решения СЛАУ показано применение методов синтеза структур данных и процедур обращения к распределенной памяти и методов минимизации программных и аппаратных затрат на реализацию кадров задачи, обеспечивающих высокоэффективное решение задачи на различной конфигурации МВС.
На примере структурно-процедурной реализации задачи трассировки показано практическое применение операции векторизации, позволяющее преобразовать исходный функционально-нерегулярный граф задачи и представить его в виде множества функционально-регулярных информационных подграфов, которые могут быть преобразованы в кадры.
Синтезирован оригинальный параллельный алгоритм, эффективно реализуемый на МВС ПА. Показано, что средняя эффективность решения данной задачи на МВС со структурно-процедурной организацией вычислений составляет около 0,5, что примерно в четыре раза выше, чем эффективность существующих параллельных алгоритмов.
На примере преобразования задачи кластерной группировки данных в структурно-процедурную форму показано, что комплексный анализ общей структуры задачи позволяет объединять различные кадры задачи в единую вычислительную структуру, что упрощает параллельные программы и обеспечивает более высокую эффективность их структурно-процедурной реализации.
Универсальные многопроцессорные вычислительные системы с массовым параллелизмом и программируемой архитектурой
Для эффективного решения широкого круга задач на универсальной МВС с массовым параллелизмом необходимо решить ряд важнейших проблем, связанных с ее архитектурой и организацией вычислений. При этом комплекс программно-аппаратных средств МВС должен обеспечить зависимость реальной производительности от числа процессоров суперкомпьютера, близкую к линейной и приближающуюся к пиковой производительности, а также простоту и оперативность создания эффективных параллельных программ.
Одним из средств обеспечения высокой реальной производительности МВС является адекватность ее структуры структуре решаемой задачи. В ряде случаев данная проблема решается путем создания специализированных вычислителей, в которых обеспечена безызбыточность, и, как следствие, высокая эффективность решения задачи. Например, подобные вычислители создаются для решения специальных задач управления, обработки сигналов и изображений, для решения задач криптографии. Для таких систем характерны максимальный уровень аппаратной поддержки всех выполняемых функций и узкая специализация выполняемых ими функций. Применение специализированных вычислителей оправдано только в случае, если решается один тип задач- В противном случае, необходимо расширение их номенклатуры, что ведет к удорожанию системы и понижению коэффициента использования оборудования.
Что касается универсальных суперЭВМ с массовым параллелизмом, то, как указывается в /13/, для таких систем проблема адекватности архитектуры системы и структуры решаемых задач является проблемой первостепенной важности и далеко не тривиальной вследствие чрезвычайно широкого спектра классов решаемых задач. Решена эта проблема для универсальных суперЭВМ с массовым параллелизмом может быть только в том случае, если пользователю будет обеспечена возможность программировать архитектуру суперЭВМ с массовым параллелизмом под структуру решаемой задачи или под структуру класса решаемых задач /13/.
Фактически это означает, что пользователю должна быть предоставлена возможность программировать в рамках фрейм-архитектуры универсальной многопроцессорной суперЭВМ с массовым параллелизмом виртуальные специализированные вычислители, структура которых адекватна решаемой задаче. При этом программирование структуры подобных виртуальных специализированных вычислителей должно осуществляться как в статическом (до начала решения), так и в динамическом (в процессе решения задачи) режимах. Только в этом случае возможно обеспечить высокую реальную производительность универсального суперкомпьютера с массовым параллелизмом, близкую к пиковой производительности, и линейный рост производительности при росте числа параллельно работающих процессоров /13/.
В 1970-2000 гг. в НИИ многопроцессорных вычислительных систем Таганрогского государственного радиотехнического университета (НИИ МВС ТРТУ) под руководством академика РАН А.В. Каляева была разработана, теоретически и экспериментально подтверждена и апробирована на реальных образцах многопроцессорных ЭВМ с параллельной структурой tie имеющая аналогов в мире концепция универсальных многопроцессорных суперЭВМ с программируемой архитектурой и структурно-процедурной организацией вычислений /1,28-37/. Существо указанной концепции состоит в следующем.
В процессе разработки и конструирования архитектура суперкомпьютера с массовым параллелизмом не формируется окончательно и остается в определенном смысле незавершенной и открытой. При этом суперкомпьютер, основывается на аппаратных и программных подсистемах, которые дают пользователю возможность оперативно настраивать его архитектуру с целью получить виртуальную архитектуру, адекватную структуре решаемой задачи. Программирование архитектуры универсального суперкомпьютера с массовым параллелизмом включает в себя; - программирование коммутационной системы, обеспечивающей соединение компонентов системы в соответствии со структурой фрагмента задачи; - программирование структуры процессоров и межпроцессорных ( информационных связей для структурного выполнения макроопераций; -программирование структуры распределенной памяти и процедур параллельного бесконфликтного доступа процессоров к распределенной памяти; - программирование внутренних и внешних каналов связи системы в целом и, в известной степени, структуры распределенного системного программного обеспечения многопроцессорной суперЭВМ с массовым параллел измом.
Для всех этих операций программирования и аппаратной настройки, многопроцессорной суперЭВМ на необходимую архитектуру проработаны соответствующие методы и механизмы, проверенные в реальных системах.
Информационно-эквивалентные операции в информационных графах
Информационный подграф задачи должен быть представлен не только в виде пары собственных вершин и внутренних дуг, как показано в (2.1), но и внешних источников (вершин и дуг) и внешних приемников. Таким образом, подграф задачи в общем виде определяется как упорядоченная шестерка; где Vx - множество внешних входных вершин (VQO VX=0), Ах - множество внешних входных дуг» источниками которых являются вершины, принадлежащие множеству Vx, а приемниками - вершины, принадлежащие множеству VQ, VQ - множество внутренних операционных вершин, AQ - множество внутренних операционных дуг, Vy - множество внешних выходных вершин (VQ П Vy=0), Ay - множество внешних выходных дуг, источниками которых являются вершины, принадлежащие множеству VY, а приемниками - вершины, принадлежащие множеству VQ. Дополнительные компоненты высказывания (2,14) могут быть определены из графа задачи G и подграфа задачи g с помощью следующих реляционных выражений: Следует отметить, что структурная реализация подграфа для наибольшего быстродействия требует, чтобы множество VQ содержало только операционные вершины. Если информационный граф задачи невозможно отобразить полностью в структуре МВС, то его придется реализовать фрагментарно.
Очевидно, что информационная связь между подграфами реализуется через память. Для выделенного подграфа, принадлежащего графу задачи, необходимо включить на каждую внешнюю дугу информационную вершину. Таким -образом, производится преобразование информационного графа задачи G в модернизированный граф G . Очевидно, что такое преобразование является информационно-эквивалентным, так как обращение к памяти не изменяет результатов вычислений. Подобное преобразование может быть выполнено с использованием операции группировки подграфа. Для операции группировки введем следующее обозначение: где G - исходный информационный граф, G - модернизированный информационный граф g - выделенный информационный подграф. Операция группировки подграфа подразумевает выполнение следующих действий. Для выделенного подграфа g, принадлежащего информационному графу G, определяется множество входных внешних дуг Ах. Поскольку в результате преобразования необходимо, чтобы внешними вершинами графа g были только информационные вершины, то из множества Ах должны быть исключены дуги, вершинами-источниками которых уже являются информационные вершины. Множество внешних входных дуг, которые должны быть модернизированы, определяется следующей реляционной формулой: Здесь и далее INF - множество операций информационных вершин. Аналогично, множество внешних выходных дуг, которые должны быть модернизированы, определяется следующей реляционной формулой:
При выполнении операции группировки в информационный граф G добавляется два множества информационных вершин 1\ и IY, при этом количество информационных вершин, принадлежащих їх, равно числу дуг Ux, а количество информационных вершин, принадлежащих 1у, равно числу дуг Каждая внешняя входная дуга ах є Ux заменяется парой дуг ах! и ахІ5 при этом вершиной-приемником дуги axi и вершиной-источником ах2 является информационная вершина іх є їх - Каждая внешняя выходная дуга ау є UY, заменяется парой дуг ayi и ау2, при этом вершиной-приемником дуги ауі и вершиной-источником ау2 является информационная вершина іу є Іу Для подобной замены множества дуг введем операцию включения множества вершин, которую обозначим следующим образом; где G - результирующий граф, G - исходный граф, U - множество модернизируемых дуг. Операция включения информационных вершин G =W(A?G) может быть определена через элементарные операции следующим образом: где G =2X4(U, G) - операция удаления множества дуг U из графа G, формирующая граф G , G =J4K(VS G) - операция добавления вершин, принадлежащих множеству V в граф G, формирующая граф G , Gr=AA(A, G) - операция включения множества дуг А в информационный граф G, формирующая граф G , I - множество вставляемых информационных вершин с уникальными именами, М - множество дуг с уникальными именами. Множество М формируется с помощью графа G и множества U в соответствии со следующим реляционным отношением: Определим компоненты формулы (2.23). Отношение DA(A, G, G ) определяет операцию удаления дуг, принадлежащих множеству А, из графа G и может быть записана следующим образом: Отношение AA(A,G G) определяет операцию добавления дуг, принадлежащих множеству А, в граф G и может быть записана следующим образом: Операцию можно выполнить тогда и только тогда, когда источники и приемники дуг, принадлежащих множеству А принадлежат исходному графу G.
Структурно-процедурная реализация задачи математической физики
Для многих типов многопроцессорных систем с массовым параллелизмом характерна архитектура, в которой каждому процессорному элементу соответствует собственная локальная память, к которой данный процессор обращается в процессе вычислений. Локальная память процессора имеет последовательный доступ. При мультипроцедурной организации вычислений, когда каждый процессор Pi функционирует по собственной программе, организуется множество независимых процедур последовательного доступа Prj к блокам локальной памяти Sj. Для межпроцессорных обменов в мультипроцедурных системах разрабатываются специальные процедуры, которые исключают конфликты, но замедляют процесс решения задачи, поскольку реализуются в режиме разделения во времени. В связи с этим, проблема организации структур в многопроцессорных системах с мультипроцедурной организацией вычислений является достаточно тривиальной, в то время как основной проблемой синтеза параллельной программы является организация процедур межпроцессорного обмена и обеспечение синхронности выполняемых процессов.
При структурно-процедурной организации вычислений информационный граф задачи разбивается на множество подграфов таким образом, чтобы количество операционных вершин каждого подграфа не превышало количество элементарных процессоров в системе, а множество дуг подграфа соответствовало бы возможностям коммутационной системы. Структурно-процедурная форма предполагает разделение задачи на структурную и процедурную компоненты. При этом структурная компонента реализуется в виде аппаратно реализуемых кадров. Процедурная компонента реализуется в виде программы, описывающей последовательность смены кадров /10/. В свою очередь, кадр может быть представлен как двумерный поток данных, следующих через аппаратно (структурно) реализованный на совокупности элементарных процессоров фрагмент задачи. При этом первое измерение соответствует параллельному доступу к каналам распределенной памяти, а второе - последовательному обращению к ячейкам распределенной памяти /4/.
При преобразовании задачи в структурно-процедурную форму кортежи изоморфных подграфов преобразуются в кортежи кадровых структур Kj=(R,Q,W)j, При этом множества информационных вершин подграфов заменяются функциональными узлами чтения и записи, которым поставлены в соответствие кортежи функций чтения и функций записи.
Если в кортеже функций чтения (функций записи) двум и более переменным ставится в соответствие один и тот же момент времени t, то при структурно-процедурной реализации это означает необходимость параллельного обращения к ним. Как было показано в главе 1, для МВС со структурно-процедурной организацией вычислений характерна сегментная память, и массивы данных являются двумерными: первое измерение определяет номер канала Nk распределенной памяти, иторое измерение - адрес ячейки Ас.
Одной из основных задач синтеза кадровой формы задачи является размещение данных в каналах памяти многопроцессорной системы. Исходя из кадровой структуры задачи и конфигурации многопроцессорной системы (количества каналов памяти, топологии коммутационной системы, а также количества элементарных процессоров), необходимо выбрать рациональные варианты размещения данных в памяти, не допускающих конфликтов обращения.
Первый тип возможных конфликтов происходит тогда, когда хоія бы два данных, требующих параллельного обращения, размещены в одном канале по разным адресам.
Второй тип возможных конфликтов происходит, когда число переменных в кадре, требующих параллельного доступа к памяти, превышает количество каналов памяти многопроцессорной системы.
Третий тип возможных конфликтов возникает, когда возможности коммутационной системы не позволяют осуществить параллельный доступ к данным, содержащимся в каналах распределенной памяти.
Четвертый тип конфликтов возникает, когда данный вариант распараллеливания не может быть реализован из-за отсутствия процессоров.
Разрешение вышеперечисленных конфликтов является одной из основных задач организации структурно-процедурных вычислений.
Важным аспектом организации структурно-процедурных вычислений является синтез процедур обращения к элементам структуры данных, расположенных в каналах распределенной памяти (функции адресации и функции коммутации). Вопросы синтеза функции коммутации и функции адресации находятся в тесной взаимосвязи с вопросами формирования структур данных. От того, насколько оптимальна структура данных, зависит сложность процедур обращения к ее элементам, определяющая сложность программных конструкций и время решения задачи, а также коэффициент использования оборудования многопроцессорной вычислительной системы.
Перед тем как рассмотреть методы и алгоритмы формирования структур данных, необходимо формально определить структуру данных с точки зрения структурно-процедурной организации вычислений.
Определение 2,2. Структура данных определяется множеством функций Fs, отображающим множество переменных, принадлежащих кадрам задачи, на множество адресов сегментированной памяти МВС ПА в соответствии с системой ограничений, определяющих реализуемость выбранного варианта распараллеливания на множестве элементарных процессоров системы и каналов распределенной памяти, соединенных коммутационной системой.
В обшем случае для задачи, представленной в кадровой форме, существует некоторое трехместное отношение
Структурно-процедурная реализация процедуры решения систем линейных уравнений
В настоящей главе представлены методы преобразования задач, которые относятся к классу функционально-нерегулярных. Анализ структуры таких задач был проведен в первой главе. Структура вычислительных алгоритмов функционально-нерегулярных задач (информационные зависимости, количество операций вычислительного алгоритма на каждом шаге) определяется как входными данными, так и промежуточными результатами вычислений.
Типичными представителями функционально-нерегулярных задач являются, например, задачи трассировки по волновому алгоритму, задачи функционального и логического моделирования, задачи кластерного анализа, некоторые задачи вторичной обработки изображений (построение контуров объектов, гистограммная обработка, построение скелета объекта и т.д.).
Для преобразования таких задач в эффективную структурно-процедурную форму разработана методика, основанная на анализе структуры параллельного информационного графа алгоритма задачи и предполагающая последовательное выполнение ряда информационно-эквивалентных преобразований.
Тривиальным решением структурно-процедурной организации вычислений для вышеперечисленных типов параллельных информационных графов является построение параллельного информационного графа, имеющего прямоугольную ярусно-параллельную форму, с последующим преобразованием этого графа в кадровую форму. Однако данный путь неэффективен, поскольку такие информационные графы обладают функциональной избыточностью: большинство информационных базовых подграфов соответствуют "пустым" операциям, когда результаты выполнения таких операций тождественно равны ее входным данным, В этом случае эффективность структурно-процедурной реализации вычислений очень низка.
Однако для таких графов возможно провести структурно-процедурную форму в виде последовательности кадров. При этом возможно обеспечить потоковую обработку данных и получить достаточно высокие характеристики эффективности решения задач на МВС ПА На первом этапе алгоритм задачи представляется в абсолютно-параллельной форме - в виде параллельного информационного графа. На втором этапе устраняется функциональная избыточность параллельного информационного графа и формируется промежуточный функционально-нерегулярный граф. На третьем этапе выполняется специальное преобразование - векторизация информационных вершин в параллельном графе /54/.
При выполнении данной операции множество непересекающихся подмножеств информационных вершин, в каждом из которых существует ациклический путь, соединяющий в определенном порядке информационные вершины, или другое правило детерминированного упорядочивания вершин, заменяется специальным объектом — вершиной-массивом. Данная вершина соответствует расположению структуры данных в каналах распределенной памяти МВС. Каждое подмножество информационных вершин будет расположено в отдельном канале распределенной памяти. Адреса, по которым будут расположены вершины в канале, взаимно однозначно соответствуют номеру вершины на пути, соединяющему эти вершины в графе. После выполнения операции векторизации информационные дуги, источниками или приемниками которых являлись векторизированные информационные вершины, исключаются и заменятся дугами, источником или приемником которых является вершина-массив Особенностью для получения векторизированного подграфа является следующее: в исходном подграфе выделяются подграфы (слои), информационные вершины которых заменяются специальной вершиной-массивом. Дугам векторизованного графа присваивается пара признаков: адрес и временная метка. Адресный признак однозначно соответствует имени входной информационной вершины, а временная метка определяет принадлежность информационной вершины определенному слою. В дальнейшем, если того требует задача, возможно провести дополнительную векторизацию адресных вершин.
Операция векторизации информационных вершин позволяет представить задачу в виде функционально-регулярных информационных подграфов (слоев), в которых правила отображения базовых подграфов друг на друга определены через правила отображения адресных вершин. Данные информационные подграфы преобразуются в кадры, реализуемые для произвольной степени распараллеливания.
Особенность формирования бесконфликтной структуры данных и функции адресации и коммутации для подобных задач заключается в том, что процедура векторизации информационных вершин, за исключением некоторых особых случаев, предполагает использование косвенной адресации. Для различных задач механизм косвенной адресации может быть реализован по-разному. В одних случаях адреса обращения к каналам памяти возможно вычислить на этапе формирования функций исполнительной адресации и записать их в отдельный массив памяти. В дальнейшем при реализации кадра задачи обращение к элементам информационных массивов (массивы входных данных и массивы результатов) осуществляется через обращение к адресным массивам. В других случаях массивы адресов обращения к каналам памяти вычисляются на элементарных процессорах.
