Содержание к диссертации
Введение
1. Структурно-процедурная организация параллельных вычислений 18
1.1. Методы организации параллельных вычислений 18
1.2. Модели параллельных вычислений 29
1.3. Формальное определение структурно-процедурных вычислений 35
1.4. Основные принципы преобразования задачи в структурно-процедурную форму 42
1.5. Выводы 54
2. Методы преобразования задачи к эффективной структурно-процедурной форме 56
2.1. Преобразование функционально-регулярных графов 56
2.2. Преобразование в структурно-процедурную форму информационных графов нерегулярной структуры 73
2.3. Структурно-процедурная реализация нерегулярных информационных графов 77
2.4. Эффективность структурно-процедурных вычислений 92
2.5. Выводы 107
3. Средства описания структурно-процедурных вычислений 108
3.1. Описание языка параллельного программирования высокого уровня для структурно-процедурной организации вычислений 108
3.2. Некоторые особенности и алгоритмы трансляции 131
3.3. Выводы 149
4. Технология индуктивных структурно-процедурных программ 151
4.1. Принципы построения технологии индуктивных структурно-процедурных программ 151
4.2. Планировщик индуктивных заданий 155
4.3. Система посттрансляции индуктивных заданий 169
4.4. Программные средства поддержки технологии индуктивных программ . 182
4.5. Выводы 187
5. Элементная база многопроцессорных систем с программируемой архитектурой и структурно- процедурной организацией вычислений и средства ее программирования 189
5.1. Макропроцессор 191
5.1.1. Структура макропроцессора 191
5.1.2. Программирование макроопераций 199
5.2. Макрокоммутатор 206
5.2.1. Структура макрокоммутатора 206
5.2.2. Описание коммутационных структур 210
5.3. Контроллер распределенной памяти 212
5.3.1. Структура КРП 212
5.3.2. Программирование РП 225
5.4. Выводы 228
6. Архитектура многопроцессорной системы для структурно-процедурного решения задач различных проблемных областей 230
6.1. Синтез структуры многопроцессорной вычислительной системы для решения задач структурно-процедурным методом распараллеливания., 230
6.2. Анализ вариантов построения коммутационных структур МВС со структурно-процедурной организацией вычислений 237
6.2.1. МВС с фиксированной топологией информационных связей 237
6.2.2. Иерархическая коммутационная система 239
6.2.3. Ортогональная система коммутации 241
6.2.4. МВС с коммутационной системой косвенного бинарного п-куба 243
6.2.5. Многоуровневая коммутационная структура 246
6.3. Модульная организация МВС 249
6.3.1. Структура базового модуля МВС с иерархической коммутационной системой 249
6.3.2. Структурная схема базового модуля с ортогональной системой коммутации 257
6.3.3. Конструкция базового модуля 271
6.4. Выводы 277
Заключение... 279
Список использованных источников 285
- Основные принципы преобразования задачи в структурно-процедурную форму
- Структурно-процедурная реализация нерегулярных информационных графов
- Программные средства поддержки технологии индуктивных программ
- Структура базового модуля МВС с иерархической коммутационной системой
Введение к работе
Суперкомпьютеры предназначены для решения сложнейших проблем современности, требующих обработки гигантских объемов информации в короткие промежутки времени. Создание и использование суперкомпьютеров относится к факторам стратегического развития науки и техники и входит в первую десятку приоритетных технологий развитых стран [1]. Без суперкомпьютеров невозможно моделировать экономические и социальные системы, прогнозировать экологические процессы и природные геофизические явления, разрабатывать важнейшие техногенные объекты, решать проблемы космонавтики, астрофизики, медицины. Развитие микроэлектроники и создание семейств высокопроизводительных микропроцессоров привело к тому, что доминирующим направлением построения суперкомпьютеров в настоящее время являются многопроцессорные вычислительные системы (MB С) с массовым параллелизмом, содержащие тысячи параллельно функционирующих микропроцессоров, связанных между собой с помощью коммутационной системы.
О темпах развития вычислительной техники говорит тот факт, что два десятилетия назад наиболее мощные суперкомпьютеры имели производительность в несколько Гфлопс; в настоящее время эксплуатируются суперкомпьютеры с производительностью более триллиона операций в секунду, наиболее мощные суперкомпьютеры имеют производительность, превышающую 50 Тфлопс, и разрабатываются системы с производительностью от 100 до 1000 Тфлопс [2]. В то же время для ряда сложных расчетоемких задач реальная производительность современных суперкомпьютеров существенно ниже пиковой производительности [3].
Как правило, при создании параллельных программ для существующих МВС используются эвристические методы поиска локально-оптимальных вариантов распараллеливания, а эффективные параллельные программы удается создать лишь для определенного варианта распараллеливания. В связи с этим программирование на МВС с массовым параллелизмом до сих пор является сложным и трудоемким процессом, намного превосходящим по сложности процесс программирования на однопроцессорных машинах. Это обуславливает чрезвычайно высокую стоимость прикладного и системного программного обеспечения МВС и ограничивает их применение.
От эффективности математических методов и программно-аппаратных средств организации параллельных вычислений в значительной степени зависит эффективность применения многопроцессорных систем для решения научно-технических задач.
Большинство существующих МВС использует мультипроцедурную организацию вычислений, когда распараллеливание осуществляется по элементам структуры данных, и в каждом процессоре обработка ведется по независимой последовательной программе. Для обмена данными между процессорами в системе организуются специальные процедуры. Параллельные алгоритмы и параллельные программы решения сложных научно-технических задач, решаемых на МВС с массовым параллелизмом, обеспечивают достаточно низкую реальную производительность, зачастую не превышающую 10-15 % от пиковой производительности системы, вследствие того, что организация параллельных вычислений и процедуры межпроцессорных обменов требуют больше времени, чем непосредственно вычисления.
Поэтому актуальной является решаемая в диссертации научная проблема организации эффективных параллельных вычислений в многопроцессорных вычислительных системах с массовым параллелизмом, обеспечивающих их реальную производительность, близкую к пиковой на широком классе задач. Решение этой проблемы обеспечит увеличение рентабельности высокопроизводительных вычислительных комплексов за счет более рационального использования оборудования многопроцессорных систем и сокращения времени, необходимого для организации параллельных вычислений, что, в свою очередь, позволит существенно сократить сроки и стоимость проведения фундаментальных исследований, а также решения важнейших прикладных задач народно-хозяйственного значения и повышения обороноспособности страны.
Решением данной проблемы занимались такие видные ученые как Э. Дейкстра, Ч. Хоар, Р. Хокни, В. Хейдлер, Д. Чамберлен, а также российские ученые: B.C. Бурцев, В.Е. Котов, В.К. Левин, Д.А. Поспелов,
В.Г. Хорошевский, Р.Ю. Ясинявичус, В.В. Воеводин, В.А. Вальковский и многие другие.
Практически все существующие методы организации параллельных вычислений в МВС с массовым параллелизмом ориентированы на распараллеливание последовательных алгоритмов и программ. При этом исследуются только информационные взаимодействия смежных частей алгоритма (циклов, процедур и т.п.) и не уделяется должного внимания общей информационной структуре задачи. Существующие к настоящему времени методы организации параллельных вычислений ориентированы на решение сложных проблем адаптации структуры вычислительного алгоритма к архитектуре МВС. До сих пор эти проблемы не решены, и это не позволяет создать масштабируемые параллельные программы для МВС с массовым параллелизмом, которые могли бы быть выполнены с одинаковой эффективностью на произвольной конфигурации вычислительной системы.
Альтернативой существующим МВС с массовым параллелизмом являются многопроцессорные вычислительные системы с программируемой архитектурой (МВС ПА). Концепция таких систем была разработана в Научно-исследовательском институте многопроцессорных систем ТРТУ под руководством академика РАН |А. В .Каляева] [4, 5, 6, 7, 8,9,10,11,12].
Идея МВС с программируемой архитектурой заключается в том, чтобы обеспечить пользователю возможность с помощью программно-аппаратных средств программировать и формировать в универсальной системе виртуальные специализированные вычислители, адекватные структуре решаемой задачи. Это позволяет не только подбирать структуру алгоритма к архитектуре системы, но и, наоборот, адаптировать структуру многопроцессорной системы к параллельному алгоритму, что выводит на передний план "внутренний" параллелизм задачи, а не организацию вычислительных средств [13].
Для многопроцессорной системы с программируемой архитектурой используется структурно-процедурная (кадровая) форма задачи. Кадр представляет собой структурно (аппаратно) реализованный подграф задачи, через который следует поток данных. Подобная организация вычислений обеспечивает максимальную скорость обработки данных, сопоставимую со скоростью специализированных вычислителей. Вычисления в теле кадра выполняются по принципу управления потоком данных и не требуют синхронизации. Настройка на кадры производится по единой управляющей программе, что обеспечивает фон-неймановский детерминизм вычислительной процедуры [14, 15,16].
Однако реализация этих принципов требует разработки новых математических методов организации вычислительных процессов и создания аппаратно-программных средств для их поддержки.
Целью работы является разработка и создание формальных математических методов синтеза структурно-процедурных параллельных программ, эффективно реализуемых на различных конфигурациях многопроцессорных систем с программируемой архитектурой, и программно-аппаратных средств, обеспечивающих реальную производительность МВС ПА при решении задач различных классов, близкую к пиковой, а также линейный рост производительности при увеличении ресурсов системы,
В соответствии с поставленной целью определены задачи диссертации:
Провести анализ методов и моделей параллельных вычислений и на их основе разработать основные принципы эффективных структурно-процедурных вычислений.
Разработать формальные математические методы преобразования алгоритмов задач различных классов в структурно-процедурную форму, обеспечивающие решение задач с реальной производительностью, близкой к пиковой производительности системы, для различных степеней распараллеливания.
Разработать средства описания структурно-процедурных вычислений на основе неявного представления параллелизма, обеспечивающие естественное и однозначное отображение параллельного алгоритма на архитектуру многопроцессорной вычислительной системы, а также эффективную реализацию масштабируемых параллельных программ.
Разработать технологию создания масштабируемых структурно-процедурных программ, обеспечивающую эффективную реализацию параллельных программ на различных конфигурациях МВС ПА, и рост производительности, близкий к линейному, при увеличении ресурса системы, выделенного для решения задачи.
Разработать аппаратно-программные средства, обеспечивающие реализацию структурно-процедурных вычислений на уровне элементной базы.
Разработать аппаратные средства для эффективной реализации структурно-процедурных вычислений на основе модульно-наращиваемых многопроцессорных систем.
Методы исследований. При проведении исследованй были использованы: теория вычислительных систем, элементы теории .графов, теория множеств, а также реляционное исчисление. Теоретические^ исследования подтверждены вычислительными экспериментами на имитационной модели МВС со структурно-процедурной организацией вычислений, а также реализацией программных средств на созданных модульно-наращиваемых МВС ПА в интересах ряда предприятий и организаций.
Использование результатов работы. Теоретические и практические результаты диссертационной работы использованы при выполнении госбюджетных и хоздоговорных НИР в НИИ МВС ТРТУ, непосредственным участником которой являлся автор диссертации.
Наиболее важными из них являются; "Исследование возможности путей создания вычислителя с программируемой архитектурой", руководитель НИР - член-корреспондент РАН И.А. Каляев, заказчик в/ч 26165; "Инструментальная программно-математическая система суперкомпьютеров с массовым параллелизмом для решения различных военно-прикладных задач", руководитель НИР - академик РАН А.В. Каляев, № ГР ИН-858; "Разработка универсальных мультимикропроцессорных систем с массовым параллелизмом и средствами аппаратно-программной поддержки синтеза виртуальных архитектур и модульной реконфигурации", руководитель - академик РАН А.В. Каляев; № ГР 01200100688; "Исследование и разработка математических и программных средств для эффективного распараллеливания прикладных задач на высокопроизводительных вычислительных комплексах", руководитель - член-корреспондент РАН И.А, Каляев, по договору с в/ч 11135; "Разработка модульно-наращиваемой многопроцессорной системы со структурно-процедурной организацией вычислений и программируемой архитектурой на основе ПЛИС-технологии", главный конструктор, кандидат техн. наук И.И. Левин, по договору с ОАО НИЦЭВТ и в рамках Программы Союзного государства «Разработка и освоение в серийном производстве семейства высокопроизводительных вычислительных систем с параллельной архитектурой (суперкомпьютеров) и создание прикладных программно-аппаратных комплексов на их основе» (шифр «СКИФ»), утвержденная Постановлением Исполнительного Комитета Союза Беларуси и России от 22 ноября 1999 г. №43; "Многопроцессорные ЭВМ с параллельной структурой в бортовых системах принятия решений и управления автономных объектов", руководитель - к.т.н. С.Г. Капустян, № ГР 01.9.90002062; "Дальнейшее развитие теории многопроцессорных вычислительных систем с массовым параллелизмом, программируемой под структуру задачи архитектурой и структурно-процедурной реализацией вычислительного процесса", руководитель - академик РАН А.В. Каляев, № ГР 01.2.00102845; "Разработка и создание методов и программно-аппаратных средств для структурно-процедурной организации вычислений в суперЭВМ с программируемой архитектурой", руководитель - академик РАН А.В. Каляев; "Разработка методологии организации структурно-процедурных вычислений на многопроцессорных суперЭВМ с массовым параллелизмом и программируемой архитектурой", руководитель - к.т.н. И.И. Левин, № ГР 01990002076; "Теоретические и практические основы построения и применения мультипроцессорных вычислительных систем с программируемой архитектурой для решения задач прикладной физики и математики", руководитель - академик РАН А.В. Каляев, № ГР 01970003041; "Разработка и исследование архитектуры, принципов построения и элементной базы высокопроизводительного универсального суперпроцессора со структурной организацией вычислений", руководитель - академик РАН А.В. Каляев, № ГР 019100054183; "Разработка и исследование принципов создания интеллектуальной самонастраиваемой элементной базы для построения структурно- перестраиваемых процессорных полей MB С со структурно-процедурной организацией вычислений", руководитель - к.т.н. И.И. Левин, №ГР 01.20.0001267; "Исследование и разработка фундаментальных принципов и методов программирования многопроцессорных вычислительных систем с массовым параллелизмом, программируемой архитектурой и структурно-процедурной организацией вычислений", руководитель - академик РАН А.В. Каляев; "Разработка и изготовление экспериментального образца модульно-наращиваемой многопроцессорной системы со структурно-процедурной организацией вычислений и программируемой архитектурой на основе ПЛИС-технологии ", главный конструктор - к.т.н. И.И. Левин; "Исследования по созданию программно-аппаратных средств телевизионного автомата слежения за целями для перспективных наземных автономных роботизированных комплексов", руководитель - член-корреспондент РАН И.А. Каляев; "Исследование и разработка математических и программных средств для эффективного распараллеливания прикладных задач на высокопроизводительных вычислительных комплексах", руководитель - член-корреспондент РАН И.А. Каляев.
Апробация работы. Основные результаты работы докладывались и обсуждались на всероссийских и международных научно-технических конференциях: -Всероссийская научно-техническая конференция "Актуальные проблемы твердотельной электроники и микроэлектроники", Таганрог, 1994 г.;
Всероссийская научно-техническая конференция с международным участием "Теория цепей и сигналов", Новочеркасск, 1996 г.;
4-th International Conference, РаСТ-97. Yaroslavl, Russia, 1997 г.; VI международный семинар "Распределенная обработка информации", Новосибирск, 1998 г.;
Всероссийская научно-техническая конференция с международным участием "Компьютерные технологии в инженерной и управленческой деятельности", Таганрог, 1998 г.;
IV всероссийская научно-техническая конференция "Нейрокомпьютеры и их применение", Москва, 1998 г.; V всероссийская научно-техническая конференция "Нейрокомпьютеры и их применение", Москва, 1999 г.;
Международная конференция "Интеллектуальные многопроцессорные системы (ИМС99)", Таганрог, 1999 г.; -Международная конференция "Искусственный интеллект-2000",-Кацивели, 2000 г.;
Всероссийская научная конференция "Высокопроизводительные вычисления и их приложения", Черноголовка, 29 октября - 2 ноября 2000 г.;
Третья международная научно-техническая конференция "Электроника и информатика - XXI век", 22-24 ноября, Зеленоград-Москва, МИЭТ, 2000 г.;
Международная конференция "Интеллектуальные и многопроцессорные системы-2001", пос. Дивноморское, 2001 г.
Международная конференция "Параллельные вычисления и задачи управления (РАСО'2001)", М: ИПУ РАН им. В.А.Трапезникова, 2001 г.;
Международная конференция "Искусственный интеллект-2002",-Кацивели, 2002 г.;
Международная научно-техническая конференция "СуперЭВМ и многопроцессорные вычислительные систем ьт-2002", Таганрог, 2002 г.;
Конференция "С.А. Лебедев и развитие отечественной вычислительной техники", Москва, 2002 г.;
Международная конференция "Интеллектуальные и многопроцессорные системы-20031', пос. Дивноморское, 2003 г.;
Первая Всероссийская научная конференция "Методы и средства обработки информации". Москва, ф-т вычислительной математики и кибернетики МГУ им. М.В. Ломоносова, 2003 г.
По теме диссертации опубликованы 102 печатные работы, в том числе, 1 монография, 30 статей в центральной печати, из них 10 - в изданиях, входящих в "Перечень ведущих научных журналов и изданий, выпускаемых в Российской Федерации" ВАК, получено 4 патента на изобретение.
Наиболее важными из публикаций являются:
Каляев А.В., Левин И.И. Модульно-наращиваемые многопроцессорные системы со структурно-процедурной организацией вычислений. - М.: Лнус-К, 2003. - 380 с. (опубликована при поддержке РФФИ, грант № 02-07-95004-д).
Левин И.И., Пономарев И.М. Реализация БПФ на многопроцессорной системе со структурной организацией вычислений // Электромеханика, 1995. -№ 4. - С.72 - 74.
Левин И.И., ГузикВ.Ф., Сафронов О.О. Представление параллелизма в программах для многопроцессорной системы с программируемой архитектурой // Известия ВУЗов. Северокавказский регион. Технические науки, 1996. - № 2. -С. 4-15.
Каляев А.В., Фрадкин Б.Г.Левин И.И., Унифицированная элементная база для построения реконфигурируемых под задачу вычислительных систем // Известия вузов. Электроника, 1997. - № 1. - С.75-83.
Каляев А.В., Каляев И.А., Левин И.И., Пономарев И.М. Базовый модуль для построения реконфигурируемых под задачу вычислительных систем // Известия вузов. Электроника, 1998. - № 4. - С. 67-74.
Каляев А.В., Левин И.И. Многопроцессорные системы с перестраиваемой архитектурой; концепции развития и применения //Наука- производству, 1999. -№11.-С. 11-19.
Каляев А.В., Левин И.И., Пономарев И.М, Базовый модуль многопроцессорной вычислительной системы с программируемой архитектурой для эффективного решения исследовательских и производственных задач // Наука - производству, 1999. - № 11. - С. 33-39.
Левин И.И., Пономарев И.М. Структурно-процедурная реализация кластерной группировки данных в задачах обработки изображений // Электромеханика, 1999. - №2. - С. 54-57.
Левин И.И. Структурно-процедурная реализация электрического моделирования на многопроцессорной системе // Известия ВУЗов. Электромеханика, 2002. - №1. - С. 27-30.
Левин И.И., Коробкин В.В., Чернов Е.И. Об одном подходе к проблеме повышения надежности управляющего вычислительного комплекса с использованием технологии MB С ПА // Мехатроника, автоматизация, управление. - М.: Новые технологии, 2003. - № 4. - С. 40-43.
Левин И.И., Трунов Г.Л. Отказоустойчивое функционирование ре конфигурируемых МВС // Электромеханика, 2004. - № 4. - С. 11-15.
Каляев В.А., Левин И.И., Фомин СЮ. Об оценке эффективности решения задач математической физики на многопроцессорных системах // Электронное моделирование, 1989. - № 6. - С. 11-15. Kalyaev A.V., Kaliaev I.A., Levin IЛ. The Base Module of Multiprocessor System with Structural-Procedural Organization of Computing II Parallel Computing Technologies. Proceedings of 4-th International Conference, PaCT-97. Yaroslavl, Russia, 1997.-Pp. 394-396.
Левин И.И. Язык параллельного программирования высокого уровня для структурно-процедурной организации вычислений // Труды Всероссийской научной конференции "Высокопроизводительные вычисления и их приложения", Черноголовка, 2000. - М: Изд-во МГУ. - С. 108-112.
Каляев А.В., Левин И.И. Структурно-процедурная организация параллельных вычислений // Труды межд. конф. "Параллельные вычисления и задачи управления (РАСО'2001)". - М: ИПУ РАН им. В.А.Трапезникова, 2001. -Т. 5.-С. 112-121.
Левин И.И., Штейнберг Б.Я. Сравнительный анализ эффективности параллельных программ для различных архитектур многопроцессорных систем // Искусственный интеллект. - Донецк: Наука і освіта, 2001. - №3. - С. 234-242.
Левин И.И., Шахов Р.В., Шматок А.В., Сластен Л.М. Математическое обеспечение многопроцессорных вычислительных систем с программируемой архитектурой II Искусственный интеллект. - Донецк: Наука і освіта, 2002. - №3. - С. 286-294.
Левин И.И. Многопроцессорная система с программированием архитектуры на нескольких уровнях // Труды Первой Всероссийской научной конференции "Методы и средства обработки информации". - М.: МГУ, 2003, -С. 111-118.
Левин И.И., Пономарев И.М. Структурно-процедурная реализация задачи трассировки // Искусственный интеллект. Донецк: Наука і освіта, 2003. - №3. -С. 121-129.
Левин И.И. Ресурсонезависимое параллельное программирование // Искусственный интеллект- - Донецк: Наука і освіта, 2002. - №3. - С. 277-285.
Левин И.И. Модульно-наращиваемая многопроцессорная вычислительная система со структурно-процедурной организацией вычислений на основе ПЛИС-технологии // Искусственный интеллект. - Донецк: Наука і освіта, 2003. -№4.-С. 446-453.
Матричный коммутатор: Патент РФ № 2059288 на изобретение по заявке № 94029855/09. / Левин И.И., Ерохин А.В., Рыжих О.А., Фрадкин Б.Г. - Заявл. 05.08.1994; Опубл. 27.04.1996. - Бюлл. № 12. - 5 с.
Матричный коммутатор: Патент РФ № 2103729 на изобретение по заявке № 94029856/09. / Левин И.И., Ерохин А.В., Рыжих О.А., Фрадкин Б.Г. - Заявл. 05.08.1994; Опубл. 27.01.1998. - Бюлл. №3.-7 с.
Макропроцессор: Патент РФ № 2210808 на изобретение по заявке № 2001100388. / Каляев А.В., Левин И.И., Виневская Л.И., Станишевский О.Б. -Заявл. 05.01.2001; Опубл. 20.08.2003. - Бюлл. № 23. - 26 с.
Мультиконтроллер распределенной памяти: Патент РФ № 2210804 на изобретение по заявке № 2001122359. / Каляев А.В., Левин И.И., Виневская Л.И., Дмитренко Н.Н. - Заявл. 08.08.2001; Опубл. 20.08.2003. -Бьолл. № 23. - 44 с.
Левин И.И., Каляев В.А., Фомин СЮ. Многопроцессорная система для оперативного моделирования гидрофизических процессов // Сб. "Профаммные и аппаратные средства машинного моделирования", Москва, 1988.
Левин И.И. Сопроцессор для решения задач математической физики структурно-процедурным методом распараллеливания // Сб. "Анализ эффективности вычислительных систем". - Львов, 1991. - Препринт НТЦ "Интеграл". - № 9-16.
Левин И .И., Рвачев В .Л., Шевчен ко А .Н., Кошелен ко А .И. S oftware and Hardware of Simulation of Phisical Mechanical Fillds If Сб. "Parallel Computing Technologies Word Scientific". - Новосибирск, 1991.
Левин И.И., Пономарев И.М. Реализация алгоритма волновой трассировки на многопроцессорной системе со структурной организацией вычислений. - М., 1995. - Деп. ВИНИТИ, № 1553-В95. - 49 с.
Левин И.И. Высокоэффективный алгоритм структурно-процедурной реализации задачи логико-временного моделирования на многопроцессорной системе. - М., 1995. - Деп. ВИНИТИ, № 1445-В95. - 31 с.
Левин И.И. Структурно-процедурная реализация функционального моделирования на многопроцессорной системе. - М,, 1995. - Деп. ВИНИТИ, № 2043-В95.-25с.
Левин И.И., Пономарев И.М., Фрадкин Б.Г. Анализ эффективности структурно-процедурной организации вычислительного процесса при решении прикладных задач на MB С // Сборник аннотаций и научных статей по результатам исследований, проведенных в ходе выполнения межвузовской научно-технической программы "Фундаментальные исследования в области прикладной физики и математики в технических ВУЗах России". ФИЗМАТ 1992-1995. - М.: ГК РФ по Высшему образованию, 1995.
Левин И.И., Виневская Л.И., Дмитренко Н.Н., Логвинов С.А. Элементная база для построения высокопроизводительных систем // Труды международной конференции "Интеллектуальные многопроцессорные системы". - Таганрог: Изд-во ТРТУ, 1999. - С. 93-97.
Левин И.И., Шматок А. В. Технология параллельных индуктивных программ // Труды международной конференции "Интеллектуальные многопроцессорные системы (ИМС99)". -Таганрог: Изд-во ТРТУ, 1999. - С. 142-146.
Левин И.И. Методы построения самонастраиваемой элементной базы // Тезисы международной конференции "Интеллектуальные и многопроцессорные системы-2001". - Таганрог: Изд-во ТРТУ, 2001. - С. 126-129.
Левин И.И., Трунов Г.Л. Отказоустойчивое функционирование многопроцессорных систем с массовым параллелизмом // Искусственный интеллект. - Донецк: Наука і освіта, 2002. - №3. - С. 295-302.
Левин И.И. Отображение структурно-процедурной формы задачи на архитектуру многопроцессорной системы // Материалы Международной научно-технической конференции "СуперЭВМ и многопроцессорные вычислительные системы". - Таганрог: Изд-во ТРТУ, 2002. - С. 95-98.
Каляев А.В., Каляев И. А., Левин И.И. Модульно-наращиваемые многопроцессорные системы с программируемой архитектурой и структурно-процедурной организацией вычислений // Сборник докладов конференции "С.А. Лебедев и развитие отечественной вычислительной техники". - М., 2002. -С. 112-116.
Левин И.И., Шахов Р.В. Алгоритмы трансляции структурно-реализуемого фрагмента задачи для многопроцессорной системы с программируемой архитектурой // Искусственный интеллект. - Донецк: Наука і освіта, 2003. - №3. -С. 138-146.
Основные положения, выносимые на защиту:
Доказательство более высокой эффективности (отношение ускорения, достигаемого на MB С, по сравнению с однопроцессорной ЭВМ, к числу процессоров) структурно-процедурных вычислений по сравнению с традиционными методами организации параллельных вычислений.
Принципы и методы преобразования алгоритмов решения задач различных классов в структурно-процедурную форму, эффективно реализуемую в МВС ПА для различных степеней распараллеливания, обеспечивающие линейный рост производительности при увеличении ресурсов системы.
Язык программирования высокого уровня для описания структурно-процедурных вычислений на основе неявного представления параллелизма за счет объявления типов массивов переменных и индексации их элементов, обеспечивающий естественное и взаимодополняющее отображение параллельного алгоритма в структуру многопроцессорной вычислительной системы.
Технология индуктивных программ, обеспечивающая высокую эффективность решения структурно-процедурных программ на различных аппаратных ресурсах, и сокращение времени прохождения потока заданий.
Программно-аппаратные средства поддержки реализации структурно-процедурных вычислений на уровне элементной базы, позволяющие достигать реальной производительности системы, близкой к пиковой, для широкого класса задач и повышающие удельную производительность системы.
Аппаратные средства, обеспечивающие реализацию структурно-процедурных вычислений на основе модульно-наращиваемых многопроцессорных систем для различных вариантов распараллеливания задач различных проблемных областей.
Структура диссертации. Диссертация состоит из введения, шести глав, заключения и библиографического списка.
Во введении обоснована актуальность работы, дана ее общая характеристика, сформулированы цель и задачи исследования.
В первой главе проведен аналитический обзор методов и моделей организации параллельных вычислений. Показаны нерешенные проблемы в области создания эффективных параллельных алгоритмов и программ. Сформулированы и формализованы основные определения структурно- процедурных вычислений. Описаны принципы организации структурно-процедурных вычислений.
Во второй главе на основании принципов организации структурно-процедурных вычислений излагаются методы преобразования алгоритмов решения задачи в структурно-процедурную форму. Определяются методы формирования структуры данных и процедур параллельного бесконфликтного обращения к каналам распределенной памяти МВС.
Описываются преобразования функционально-регулярных графов на примере задачи математической физики, обеспечивающие естественную реализацию параллельного алгоритма на различных конфигурациях МВС (аппаратных ресурсах) с эффективностью проблемно-ориентированных вычислений.
Излагаются методы приведения нерегулярных подграфов в регулярную форму, основанные на процедуре векторизации (с демонстрацией применения данных методов для задачи трассировки) и мажорирования информационных подграфов (с демонстрацией примера задачи логико-временного моделирования).
Приводится методика построения масштабируемых структурно-процедурных параллельных программ на основе приведения информационного графа алгоритма в функционально-регулярную форму, из которой естественным образом синтезируются структурно-процедурные формы (СПФ) организации параллельных вычислений, обеспечивающие выполнение параллельного алгоритма с различной степенью распараллеливания, и реальной производительностью, близкой к пиковой производительности.
Излагаются процедуры преобразования нерегулярных подграфов в СПФ.
Доказано, что структурно-процедурная организация вычислений (СПОВ) обладает более высокой эффективностью по сравнению с традиционными методами организации параллельных вычислений.
В третьей главе представлены средства описания структурно-процедурной организации вычислений (СПОВ) на основе языка программирования высокого уровня с неявным представлением параллелизма. Приводятся основные конструкции языка программирования, позволяющего описать различные степени распараллеливания, и параллельные алгоритмы, однозначно отображаемые в структуру МВС и обеспечивающие детерминизм выполнения параллельных программ.
Приводятся примеры описания структурно-процедурных (СП) параллельных программ с помощью языка программирования. Излагаются некоторые особенности трансляции.
В четвертой главе представлены методы и средства технологии индуктивных параллельных программ, обеспечивающие реализацию параллельных СП программ для различных конфигураций МВС СПОВ, когда каждое задание может быть реализовано на любом количестве и произвольном сочетании базовых модулей системы.
Описаны алгоритмы построения планировщика индуктивных заданий, позволяющего повысить эффективность использования оборудования МВС, а также алгоритмы системы посттрансляции, обеспечивающей за счет применения методов преобразования кадровых структур повышение степени распараллеливания задачи в зависимости от выделенного ресурса.
Приведены программные средства описания графов минимальной конфигурации задачи и правил наращивания аппаратно-программного ресурса, выделенного для решения задачи.
В пятой главе предлагаются программно-аппаратные средства, поддерживающие СП вычисления на уровне элементной базы. Определяются функции элементной базы МВС со СПОВ. Описаны принципы построения программно-аппаратных средств макропроцессора, структурно-реализующего вычисления крупных функционально-законченных программно-неделимых фрагментов задачи. Описаны пример построения и алгоритмы функционирования элементов коммутирующей системы - макрокоммутатора, обеспечивающего реализацию коммутационных структур модульно-наращиваемых МВС и выполнение задач различных проблемных областей с реальной производительностью, близкой к пиковой.
Приводятся принципы построения, функциональные схемы и алгоритмы функционирования управляющего элемента МВС со СПОВ - контроллера распределенной памяти, обеспечивающего высокоскоростной бесконфликтный доступ к каналам распределенной памяти и управление вычислительным процессом.
Описаны методы и средства программирования элементов системы.
В шестой главе предлагаются варианты построения аппаратных средств МВС, эффективно реализующих СП вычисления на основе модульной наращиваемости. Приводятся различные варианты построения коммутационных структур и систем синхронизации вычислений. Представлены различные варианты построения базовых модулей многопроцессорных систем.
Приведены примеры создания модульно-наращиваемых МВС на основе описанных принципов построения систем со СПОВ и их характеристики. Рассмотрены вопросы конструирования модульно-наращиваемой МВС со СПОВ.
Таким образом, в диссертации сформулирована крупная и актуальная научная проблема, имеющая важное народно-хозяйственное значение.
Внедрение полученных в диссертации результатов позволит повысить скорость обработки больших объемов информации и сократить стоимость решения задач, что имеет важное значение для развития экономики нашей страны и повышения ее обороноспособности.
Результаты диссертации внедрены в ОАО "Научно-исследовательский центр электронной вычислительной техники", г. Москва; Московском государственном институте электронной техники (технический университет), г.Москва; в/ч 26165, г. Москва; в/ч 25714, г. Курск; Таганрогском государственном радиотехническом университете, г. Таганрог; НИИ многопроцессорных вычислительных систем Таганрогского государственного радиотехнического университета, г. Таганрог; Научно-конструкторском бюро вычислительных систем Таганрогского государственного радиотехнического университета, г. Таганрог.
Созданные в рамках диссертации программные средства и многопроцессорные вычислительные системы демонстрировались на ряде международных научно-технических выставок, в том числе: на Всемирных выставках оргтехники, информации и телекоммуникаций CeBIT, Ганновер, Германия, 1997, 1998,2001; на Международных выставках SIMO ТО, Мадрид, Испания, 1997, 1998; на Международной выставке-ярмарке Russian week in Holland, Флиссенген, Голландия, 1997, на Международной выставке-ярмарке Hannover Messe, Ганновер, Германия, 2002.
Основные принципы преобразования задачи в структурно-процедурную форму
Для большинства существующих в настоящее время реконфигурируемых систем [50,52] нерешенной является проблема взаимодействия между множеством вычислительных элементов и сегментами распределенной памяти, что ограничивает область применения реконфигурируемых вычислителей для определенного класса задач и не обеспечивает адекватного роста производительности при увеличении вычислительного ресурса системы.
Этих недостатков лишена развиваемая в 1970-2000 г.г. в НИИ МВС Таганрогского государственного радиотехнического университета под руководством академика РАН А.В, Каляева концепция МВС с программируемой архитектурой [10, 13, 14, 56, 57, 58, 59, 60, 61].
Существо данной концепции состоит в следующем. В процессе разработки и конструирования архитектура многопроцессорных систем с массовым параллелизмом не формируется окончательно и остается в определенном смысле незавершенной и открытой. При этом система основывается на аппаратных и программных подсистемах, которые дают пользователю возможность очень быстро, как до начала решения задачи, так и в процессе ее решения, в отличие от других реконфигурируемых систем, программировать и настраивать архитектуру суперЭВМ с массовым параллелизмом с целью получить виртуальную архитектуру, адекватную структуре решаемой задачи.
В то же время на сегодняшний день не разработаны формальные математические методы, позволяющие синтезировать эффективные параллельные программы для различных классов задач, выполняемые с высокой реальной производительностью на различных конфигурациях системы, а также не создан комплекс программно-аппаратных средств для решения этой важной научно-технической проблемы.
Программирование архитектуры универсальной системы с массовым параллелизмом включает программирование: прямых информационных каналов связи между параллельно работающими процессорами; а также структуры процессоров для параллельного выполнения макроопераций и процедуры параллельного бесконфликтного доступа к распределенной памяти [56]. Для всех этих операций программирования и аппаратной настройки многопроцессорной суперЭВМ на необходимую архитектуру должны быть разработаны соответствующие методы и механизмы.
В многопроцессорных системах с программируемой архитектурой целесообразно использовать структурную организацию вычислений. При структурной организации вычислительного процесса распараллеливание осуществляется по операционным вершинам информационного графа задачи. При этом имеет место соответствие вершин информационного графа множеству процессорных элементов, через которые в соответствии с множеством информационных связей (дуг графа) циркулируют элементы структуры данных.
Если число процессоров в системе не меньше количества операций, необходимого для аппаратной реализации вычислений, то для глубоких потоков данных, следующих через вычислительную структуру, временем заполнения конвейера можно пренебречь, и, следовательно, производительность системы при структурной реализации параллелизма будет значительно выше, чем при мультипроцедурнои реализации. Если структура вычислительной системы полностью покрывает информационный граф (число процессоров равно количеству операционных вершин, а число дуг - числу каналов коммутационной системы), задача может быть решена структурно. Если оборудования недостаточно для структурной реализации вычислений, задача должна быть представлена в структурно-процедурном виде, при этом реализация вычислений из структурной переходит в структурно-процедурную.
МВС со структурной реализацией вычислений является своеобразным гибридом между фон-неймановской архитектурой и машиной потоков данных. Вычисления здесь выполняются по единой управляющей программе, которая представляет собой последовательность вызовов кадров.
Кадром называется программно-неделимая конструкция, представляющая собой совокупность команд для элементарных процессоров, коммутаторов и контроллеров распределенной памяти. Можно сказать, что кадр представляет собой подграф задачи, через который следует двумерный поток данных. Одно измерение (пространственное) соответствует параллельному обращению к каналам распределенной памяти, переключением которых занимаются пространственные коммутаторы, второе измерение (временное) соответствует последовательному обращению к ячейкам распределенной памяти данных.
Настройка на кадры производится по единой управляющей программе, что обеспечивает фон-неймановский детерминизм вычислительной процедуры. Процедура представляет собой последовательность операторов, телом которых являются кадры.
В настоящее время наиболее распространена мультипроцедурная организация параллельных вычислений. При мультипроцедурнои организации вычислений распараллеливание осуществляется по элементам структуры данных и в каждом процессоре обработка ведется по независимой последовательной программе [62,46]. Программа и данные каждого процессора, как правило, хранятся в его локальной памяти. Для обмена данными между процессорами в системе организуются специальные процедуры. Вычислительный процесс описывается совокупностью асинхронно выполняемых последовательных программ и процедурами обмена данными между ними и представляется в виде логически объединенной совокупности процессов, каждый из которых представляет собой пару (Pit Prt). Здесь Р, -элементарный процессор, Prt -процедура, выполняемая i-u процессором.
При разработке программ для многопроцессорных вычислительных систем (МВС) с мультипроцедурным распараллеливанием исходной формой представления задачи является последовательный алгоритм, который распараллеливается по множеству локальных независимых участков. При этом в основном исследуются только информационные взаимодействия смежных частей алгоритма (циклов, процедур и т.п.) и не уделяется должного внимания общей информационной структуре задачи.
Высокая реальная производительность систем с мультипроцедурной организацией вычислений достигается при условии, что время обработки информации существенно превышает время выполнения процедур обмена данными, что имеет место при решении на МВС либо множества отдельных задач, либо при решении слабо с вязанной задачи.
Здесь и далее слабосвязанной задачей мы будем называть задачу, параллельный алгоритм которой требует выполнить пересылок информации существенно меньше (по крайней мере, на порядок), чем количество операций над данными. Сильносвязанной задачей будем называть задачу, в параллельном алгоритме которой количество пересылок информации между процессорами сопоставимо с количеством или больше числа выполняемых операций. Для сильносвязанных задач, класс которых достаточно представителен, имеет место значительное снижение реальной производительности по сравнениго с пиковой за счет роста накладного времени (времени, необходимого для организации параллельного процесса).
Существующие параллельные алгоритмы и параллельные программы решения сложных задач на МВС с массовым параллелизмом обеспечивают достаточно низкую реальную производительность вследствие того, что организация параллельных вычислений и процедуры межпроцессорных обменов требуют больше времени, чем непосредственно сами вычисления [3].
Структурно-процедурная реализация нерегулярных информационных графов
При реализации кадровых структур в аппаратуре МВС функция чтения преобразуется в функцию адресации чтения RA и функцию коммутации чтения RK, а функция записи соответственно в функцию адресации чтения WA и функцию коммутации чтения WK. Данные функции описывают процедуры параллельного и последовательного доступа к данным, размещенным в памяти МВС.
Для эффективной реализации параллельных вычислений целесообразно, чтобы память МВС состояла из множества сегментов (данные, требующие параллельного обращения, должны быть расположены в разных сегментах памяти). В результате массивы данных являются двумерными, первое измерение определяет номер сегмента (канала) Ык, а второе - адрес ячейки в канале Ас- Для параллельного обращения к группе данных, размещенных в разных сегментах памяти, требуется задать вектор двумерных адресов
Одной из основных задач синтеза кадровой формы задачи является размещение данных в сегментной памяти. При этом, исходя из кадровой структуры задачи, а также с учетом конфигурации многопроцессорной системы (количества сегментов памяти, топологии коммутационной системы и количества элементарных процессоров), следует выбрать рациональные варианты размещения данных в памяти, которые исключали бы конфликты параллельного обращения. Чтобы реализовать бесконфликтное параллельное обращение к каналам памяти многопроцессорной системы, необходимо сформулировать систему ограничений, позволяющих выбрать ограниченное количество рациональных вариантов размещения данных в сегментированной памяти для определенного варианта распараллеливания.
Для этого для каждой задачи в соответствии с выбранным вариантом распараллеливания задачи и конфигурацией вычислительной системы (количеством элементарных процессоров и типом коммутационной системы) формулируется система реляционных отношений, которая определяет семейство вариантов размещения множества данных, используемых в кадрах задачи. На основе этих ограничений может быть выбран рациональный вариант размещения элементов многомерных массивов в распределенной памяти MB С. С помощью определения порядка перечисления элементов многомерных массивов и варианта размещения формируется функциональная структура каждого кадра задачи (функции чтения и записи). На основании функций чтения и сформированной структуры данных могут быть реализованы рекуррентные выражения для функции адресации, а также выражения для функции коммутации в каждом кадре.
Система ограничений включает в себя фундаментальные ограничения, невыполнение которых не позволяет реализовать выбранный вариант распараллеливания в архитектуре вычислительной системы, а также дополнительные ("мягкие") ограничения, невыполнение которых лишь уменьшает эффективность структурно-процедурной реализации задачи.
Фундаментальное ограничение параллельного доступа можно сформулировать следующим образом. Если функция чтения или функция записи ставит в соответствие моменту времени t два операнда dj и d?, то они должны быть расположены в разных каналах распределенной памяти (вершине d; функция Fs должна ставить в соответствие адрес 6/=(Л /, ЛСІ), вершине U2 функция Fs должна ставить в соответствие адрес Ь2=(№к2, сгХ при этом
Фундаментальное ограничение информационной эквивалентности может быть сформулировано следующим образом. Если функция записи и , кадра Kj ставит в соответствие моменту времени t\ операнд d а функция чтения rj кадра Kj ставит в соответствие моменту времени t2 операнд d2, при этом операнды di и U2 являются информационно-эквивалентными, то они должны быть расположены в одной ячейке памяти. В этом случае функция Fs ставит в соответствие информационным вершинам diwd2 адрес b/—(Nfa, ЛСі).
Фундаментальное ограничение сегментирования памяти накладывается на множество каналов, в которых размещаются переменные, принадлежащие кадрам задачи, и формулируется следующим образом: количество каналов сегментированной памяти, которому соответствует множество переменных с уникальными именами, не должно превышать некоторое наперед заданное значение Стах.
Фундаментальное ограничение архитектуры накладывается на множество элементарных процессоров, которые соответствуют операционным вершинам кадров задачи: мощность множества вершин в кадре задачи не должна превышать некоторое, наперед заданное значение Nmax, определяемое мощностью множества процессоров в графе вычислительной системы.
Одной из основных задач организации эффективных структурно-процедурных вычислений является задача преобразования информационного графа задачи в кадровую форму таким образом, чтобы обеспечить минимальное время решения задачи, что достигается минимизацией числа кадров и максимизацией размеров потока данных, обрабатываемых в кадрах, и минимизацией времени поступления операнда.
Дополнительное ограничение регулярности накладывается на размещение элементов в сегментированной памяти многопроцессорной системы таким образом, чтобы программные затраты на реализацию функций чтения и записи были минимизированы.
В соответствии с системой фундаментальных и жестких ограничений разработчик может выбрать единственное решение для размещения данных в сегментной памяти.
Полученная структура данных, а также функции чтения и записи позволяют синтезировать функцию параллельного обращения (функцию коммутации) и функцию последовательного обращения (функцию адресации) в кадрах задачи. Функция коммутации представляет собой отображение моментов времени на множество кортежей, элементами которых являются номера каналов распределенной памяти, к которым требуется параллельное обращение. Если множеству моментов времени соответствует один и только один кортеж каналов распределенной памяти, то такая коммутация называется статической и является наиболее предпочтительной с точки зрения аппаратной процедуры параллельного обращения. Между функцией коммутации и функцией адресации существует неразрывная связь, определяемая структурой данных и функцией чтения (записи). При реализации различных вариантов распараллеливания функция адресации может переходить в функцию коммутации и наоборот - функция коммутации может переходить в функцию адресации. Функции коммутации и адресации используются для программирования процедур обращения к данным и после соответствующей адаптации к системе команд МВС могут быть реализованы ее аппаратными средствами.
При работе с двумерными информационными массивами индексы обоих переменных, в общем случае, зависят друг от друга. В то же время для каждого канала распределенной памяти необходимо выполнить фиксированную процедуру обращения к данным, расположенным в канале, независимо от коммутации. Таким образом, необходимо так преобразовать функции адресации, чтобы они зависели только от номера канала и момента времени обращения к данным, расположенным в канале.
Программные средства поддержки технологии индуктивных программ
При увеличении размеров сеточной области доля накладного времени, определяемая tpip\ine и tseiupy уменьшается, а эффективность приближается к единице. Кроме того, зависимость времени решения задачи от степени распараллеливания L близка к гиперболической.
Таким образом, гарантируется близкий к линейному рост реальной производительности МВС при увеличении числа параллельно функционирующих узловых процессоров. Рассмотренный пример реализации задачи на МВС является достаточно простым, однако он в полной мере демонстрирует возможности технологии преобразования задач в структурно-процедурную форму решения.
Технология структурно-процедурного программирования позволяет без семантического разрыва выполнить последовательность преобразований от исходного представления задачи до ее параллельной программы и оперативно разработать эффективные параллельные программы решения широкого класса задач различных проблемных областей.
Полученные результаты в предыдущем подразделе можно расширить на случай, когда информационный граф задачи состоит из нескольких подграфов G], G2, ..., Gn, каждый из которых является функционально-регулярным, при этом подграфы Gj, G2, ..., G„ не изоморфны друг другу. В этом случае каждый подграф G}, G2, ..., G„ будет преобразован в отдельный кадр. Кадры К/, К2, ..., К„, соответствующие подграфам G/, Cr;, ..., Gn, выполняются последовательно.
Механизм преобразования подграфа в кадр практически не отличается от механизма преобразования графа в кадр. Следует отметить, что функции чтение/запись могут быть более сложными, чем в предыдущем случае, например, коммутация каналов распределенной памяти и структурно распределенного графа может не оставаться неизменной, а переключаться. В предельном случае изменение коммутации может происходить с каждым данным. Структурно-процедурные алгоритмы решения различных задач математической физики подробно описаны в работах [69,77,78,79,80,81,82,83].
В Приложении 1 рассмотрен процесс преобразования в кадровую форму более сложной задачи - процедуры свертки в частотной области с использованием алгоритма быстрого преобразования Фурье (БПФ) [84, 85]. Структурно-процедурные алгоритмы процедуры описаны в работе [86].
Можно выделить несколько основных типов информационных графов процесса решения задачи, для отображения которых в структурно-процедурную форму требуется выполнение специальных информационно -эквивалентных преобразований.
К таким графам следует отнести информационные графы (подграфы) решения задачи, которые хоть и имеют детерминированную структуру и могут быть представлены в виде кортежа информационно-зависимых подграфов (слоев), но функциональная зависимость между базовыми подграфами явно не выражена. Первый тип информационных графов (подграфов) характерен тем, что количество слоев в подграфе заранее определено, однако каждый слой содержит разное количество базовых подграфов, при этом существует правило отображения базовых подграфов внутри каждого слоя, а правило отображения слоев либо является слишком сложным, либо определяется для каждого конкретного варианта данной задачи. Второй тип графа представляют собой задачи, у которых количество базовых подграфов, принадлежащих слою, одинаково, но правила отображения базовых подграфов внутри каждого слоя различны, а правило отображения слоев определяется конкретной реализацией данной задачи.
Кроме того, существуют задачи, графы вычислительного процесса решения которых содержат различное и заранее неизвестное количество базовых подграфов, принадлежащих слою. При этом мощность слоя, содержащего базовые подграфы, зависит от результатов вычислений на предыдущих слоях графа (подграфа) задачи.
Тривиальным решением структурно-процедурной организации вычислений для вышеперечисленных типов параллельных графов вычислительного процесса решения задачи является построение параллельного информационного графа, имеющего прямоугольную ярусно-параллельную форму, с последующим преобразованием этого графа в кадровую форму. Однако данный путь неэффективен, поскольку такие графы вычислительного процесса решения задачи обладают функциональной избыточностью: большинство базовых подграфов соответствует «пустым» операциям, когда результаты выполнения таких операций тождественно равны ее входным данным [87].
Если процедура секвенции не позволяет сразу получить функционально-регулярные графы, обеспечивающие рациональную параллельную программу, то для таких графов возможно провести специальные информационно-эквивалентные преобразования и получить структурно-процедурную форму в виде последовательности кадров. При этом возможно обеспечить вычислительный конвейер и получить достаточно высокие характеристики эффективности решения задач на МВС.
Для нерегулярных задач на первом этапе алгоритм задачи представляется в абсолютно-параллельной форме - в виде графа вычислительного процесса решения задачи. На втором этапе устраняется функциональная избыточность графа вычислительного процесса решения задачи и формируется промежуточный функционально-нерегулярный граф. На третьем этапе предлагается выполнить специальное преобразование - векторизацию информационных вершин в графе [88]. Данное преобразование существенно отличается от векторизации циклов и процедур [89, 90, 91, 92, 93].
При выполнении данной операции множество непересекающихся подмножеств информационных вершин, в каждом из которых существует ациклический путь, соединяющий в определенном порядке информационные вершины, или другое правило детерминированного упорядочивания вершин, заменяется специальным объектом - вершиной-массивом. Данная вершина соответствует расположению структуры данных в каналах распределенной памяти МВС. Каждое подмножество информационных вершин, соединенных ациклическим путем в информационном графе или отобранное другим правилом упорядочивания, будет расположено в отдельном канале распределенной памяти. Адреса, по которым будут расположены вершины в канале, взаимно однозначно соответствуют номеру вершины на пути, соединяющему эти вершины в графе, или номеру в кортеже упорядочивания. После выполнения операции векторизации информационные дуги, источниками или приемниками которых являлись векторизированные информационные вершины, исключаются и заменятся дугами, источником или приемником которых является вершина-массив.
Структура базового модуля МВС с иерархической коммутационной системой
Однако для реализации векторного варианта схемы целесообразно предварительно преобразовать разрабатываемую схему таким образом, чтобы она состояла из однотипных элементов, имеющих т входов и один выход. Это могут быть, например, как логические элементы ИЛИ-НЕ или И-НЕ, так и табличные модели представления логических элементов.
Важным является только требование реализуемости модели логического элемента в структурном виде. В этом случае не требуется перестраиваться с одной вычислительной структуры, реализующей некий фрагмент схемы, на другую вычислительную структуру, что существенно сократит время реализации функций схемы [98]. Следует отметить, что наличие разнородных элементов в векторе структурных моделей возможно, однако в этом случае коэффициент использования оборудования будет ниже 0,5 [99].
На рис.2.8 представлена схема кадра, структурно-процедурно реализующего логико-временную модель электрической схемы. Вычислительная структура содержит две матрицы памяти с текущими и вычисленными значениями на выходах логических функций. Помимо матриц внутренних состояний необходимо реализовать буфер входных воздействий X и блок обработки (БО), представляющий собой п структурных моделей логических функций, коммутатор (К) и блок проверки окончания события (БПОС).
Для эффективной работы вычислительного устройства описание схемы должно быть представлено в виде матрицы адресов чтения Ап и коммутаций
В первоначальный момент из матрицы 5, производится чтение элементов по адресу первого вектора матрицы А1ГГ. Считанный вектор поступает на коммутатор, где, в соответствии с адресами коммутации, преобразуется. На вектор моделей логических функций поступают соответствующие группы входных сигналов. Здесь и далее рассматривается пример, где функциональный блок имеет т входов и один выход.
Отклики на выходе моделей записываются в матрицу В2 и одновременно поступают в БПОС. Запись в В2 производится по инкрементируемому с каждым вектором адресу записи Азп. В первоначальный момент А317=0.
Обработка производится непрерывным потоком до тех пор, пока не будут обработаны все элементы схемы. После чего, если событие не завершено, происходит переключение матриц В{ и В2. Матрица В2 будет источником данных а матрица В, - приемником. Процесс продолжается до тех пор, пока БПОС не выдаст сигнал, свидетельствующий о том, что все элементы схемы не переключаются. В этом случае производится увеличение на единицу адреса входных сигналов Ах. Работа продолжается до тех пор, пока не будут обработаны все вектора входных сигналов Для реализации данной вычислительной структуры необходимо, чтобы схема была предварительно мажорирована таким образом, чтобы при обращении к каналам распределенной памяти не было конфликтов. Бесконфликтное обращение к каналам распределенной памяти достигается тогда и только тогда, когда справедливы следующие условия. Для всех векторов логических функций требуется, чтобы совокупность источников одновременно моделируемых элементов была расположена в двумерной матрице Bj{B2) бесконфликтно, т.е. в соответствии с ограничениями, описанными в подразделе 1.3. Источниками для моделируемых элементов являются элементы, с выходов которых информационные сигналы поступают на вход моделируемых элементов. Также необходимо, чтобы число источников не превышало бы степени распараллеливания n.
Следует отметить, что первой координатой ВУ(В2) является номер информационного канала, второй - адрес ячейки распределенной памяти в данном канале. Источники моделируемого вектора логических элементов должны быть расположены в матрице B BJ таким образом, что бы их вторые координаты (номера каналов распределенной памяти) были различны. Структурная схема БПОС представлена на рис.2.9. Структурная реализация БПОС представляет собой вектор равнозначностей, проверяющих, переключились или нет моделируемые элементы. Результаты с вектора сравнений поступают на пирамиду конъюнкций. С вершины пирамиды информация поступает на накапливающий конъюнктор. Если после прохождения всех векторов моделируемых элементов на выходе БПОС будет логическая единица, то это означает, что все элементы схемы не переключились; событие следует считать завершенным и необходимо произвести считывание нового вектора входных сигналов (увеличить на единицу Ах). В противном случае событие продолжается, И в том, и в другом случае триггер накапливающего конъюнктора очищается. Алгоритм мажорирования схемы состоит из двух этапов (проходов). На первом проходе формируется промежуточная матрица А размерностью п х К, где п - степень распараллеливания, К - количество каналов распределенной памяти многопроцессорной системы. Модуль элемента матрицы А - Ш является номером элемента схемы, используемого при моделировании у-го фрагмента схемы. Если 4, 0, то данная ячейка (itj) соответствует ячейке матрицы В, в которой хранится значение на выходе элемента. Если А0 0 то это означает, что в данном случае не задеиствуется ячейка матрицы В. Если Ад=0, то в этом случае элемент моделируемой схемы не ставится в соответствие с элементом матрицы А. Количество ненулевых строк матрицы А определяет эффективность структурно-процедурной реализации схемы. Если число ненулевых строк больше —, то можно считать, что данная схема хорошо укладывается в 2и структурно-процедурную форму. На втором проходе алгоритма из матрицы А формируется матрица адресов чтения А,л. и адресов коммутации KX,KY. Ниже приведен алгоритм первого прохода мажорирования моделируемой схемы.
