Методы организации систем параллельной обработки на основе скоростной реализации базовых логических операций Маханек, Михаил Михайлович

Введение к работе

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

Существенный вклад в развитие данного направления внесли научные школы Н.М. Амосова и Э.М. Куссуля в Институте кибернетики им. В.М. Глушкова, применивших нейронные сети для разработки и исследования систем искусственного интеллекта, А.Н. Галушкина в Советской транспьютерной ассоциации, разработавшего нейросетевые архитектуры для решения широкого круга прикладных задач, В.Л. Дунина-Барковского в Научно-исследовательском институте нейрокибернетики Ростовского университета, исследовавшего информационные процессы в нейронных структурах, B.C. Танаева в Институте технической кибернетики АН Беларуси и др.

Типичными областями приложений разрабатываемых в диссертации СПО являются, в частности, « распознавание образов, в том числе рукописных текстов и речи,

создание человеко-машинного интерфейса,

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

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

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

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

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

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

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

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

1. Разработать нейрокомпьютер (рабочую станцию) для решения прикладных задач параллельной обработки информации сложной структуры. Период выполнения темы - 1992-1994 гг. Раздел 01.03.03 республиканской научно-технической программы "Информатика".

2. Разработка многопроцессорных архитектур для обработки и распознавания изображений. Период выполнения темы - 1994-1995 гг. Раздел 1.13.12 программы фундаментальных исследований "Проблемы искусственного интеллекта".

3. Разработка методов и средств скоростной параллельной обработки информации с использованием нейроархитектур в системах и образцах В и ВТ для принятия решений в режиме критическом по времени, обработки и распознавания видеоизображений, радиоакустических сигналов. НИР Шифр "Район АН" № 02.03.05 НТК МО Республики Беларусь.

4. Исследование и разработка алгоритмов обнаружения и классификация полутоновых объектов на сложном фоне. НИР Шифр "Ракита - 2" № 02.01.02 НТК МО Республики Беларусь.

5. Разработка методов создания системы искусственного интеллекта для решения задач распознавания биомедигпшских изображений сложной структуры. Раздел 16 государственной программы фундаментальных исследований "Волна" на 1996-2000 гг.

6. Параллелыше логические процессоры для многопроцессорных систем. Период выполнения темы - 1991-1993 гг. и 1994-1996 гг., № Ма 1150/8-1 и 438 113/117/0, Немецкое Исследовательское Общество (DFG).

7. Параллельные логические процессоры для реализации логических операций в многопроцессорных системах. Период выполнения темы - 1993-1995 гг., № 436 WER 113-1-0, Немецкое Исследовательское Общество (DFG).

8. Европейская научно-технологическая сеть передачи информации. Период выполнения темы- 1995-1996гг., № Е96-08, ЕС, Брюссель.

9. Демонстрация скоростной параллельной архитектуры для обработки изображений. Период выполнения темы - 1994-1995 гг., № INTAS-93-1050, Брюссель, Европейское Сообщество.

10. Научно-исследовательская компьютерная сеть г. Минска. Период выполнения темы - 1995-1996 гг., № SA 12-5-02 (CN.IG 951430) 454/JPN/119, Отдел Научных исследований и окружающей среды НАТО, Брюссель.

11. Разработка научно-исследовательской компьютерной сети Академии наук Беларуси. Период выполнения темы - 1994-1995 гг., № 450/ВYE/09/9508004, ЮНЕСКО, Париж.

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

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

Задачи исследований:

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

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

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

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

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

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

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

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

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

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

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

Результаты исследования были сформулированы в виде конкретного предложения по усовершенствованию разрабатываемого в рамках стандарта SCI, ANSMEEE Std 1596-1992 и ISO/IEC 13961 современного интерфейса многопроцессорных систем, а автор был введен в директорат по разработке данного стандарта.

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

Разработанные методы и алгоритмы организации управления взаимодействием параллельных процессов послужили основой для разработки ряда программно-технических комплексов и систем, которые позволяют решать задачи скоростной обработки информации с использованием нейроархитектур для обработки видеоизображений, радиоакустических сигналов, принятия решений в режиме критическом по времени. Результаты исследований внедрены в университете г. Мангейма, Германия при создании многопроцессорных систем NERV и dsPLAY и на ряде предприятий Республики Беларусь, в том числе:

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

2. Система распределеной обработки информации и идентификации длительности логических операций в распределенной многопроцессорной среде для

скоростной обработки видеосигналов для оптико-электронных средств разведки и наведения.

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

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

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

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

Экономическая значимость полученных результатов. Достигнута принцшшально новая возможность проектирования программно-технических средств для решения задач в режиме критическом по времени в системах и образцах вооружений и военной техники, обработки трехмерных биомедацинских изображений за счет интеллектуализации процесса обработки информации. Обеспечивается близкий к линейному рост производительности систем параллельной обработки информации при наращивании количества процессоров. Время реализации базовых ЛО систем параллельной обработки информации -арбитража, синхронизации и параллельного обмена информацией сокращается на 30-50%, а поиска, сравнения и сортировки - на 20-30%. Предложенные методы, алгоритмы и программно-технические решения составляют основу новых наукоемких современных информационных технологий, пользующихся повышенным спросом на рынке, представлены в виде коммерческого продукта для реализации в Республике Беларусь и зарубежных странах.

Реализация результатов работы.

Основные результаты исследований реализованы путем:

- опытного использования многопроцессорного вычислительного комплекса
"NERV" при решении прикладных задач обработки информации сложной
структуры и принятия решений в режиме критическом по времени в НИИ ЭВМ,
п/я 2838, НТК МО РБ, Академии наук Беларуси, а также в рамках вьшолнения
заданий по Республиканской научно-технической программе "Информатика";

-применения принципов и методов построения систем параллельной обработки информации при разработке устройств обработки видеосигналов в Военной академии Республики Беларусь;

- использования разработанного комплекса "NERV" для расширения возмо
жностей научно-информационной компьютерной сети Академии наук Беларуси;

-внедрения в эксплуатацию вычислительных и вычислительно-измерительных комплексов на Производственном объединении "Минский тракторный завод", в Научно-техническом комитете Министерства обороны, в Научно-исследовательском институте электронных вычислительных машин;

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

- использования при выполнении ряда республиканских НИР и Госзаказов, в которых автор являлся ответственным исполнителем, в том числе заданий Министерства обороны Республики Беларусь республиканских научно-технических программ "Информатика", "Информатизация", "Волна", международных научных проектов по программам Немецкого Исследовательского Общества, INTAS, ЮНЕСКО, COPERNICUS, Немецкого Министерства образования, науки и технологий, Беяаруского Фонда Сороса.

Основные положения диссертации, выносимые на зашиту.

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

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

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

минимизация адресного обмена информацией между процессорами и их асинхронное функциоїшрование при реализации логических операций,

оптимальное представление данных при реализации ЛО в многопроцессорной среде,

определите длительности выполняемой операции в динамике работы системы при отсутствии полной информации о производительности процессорных элементов (ПЭ), используемых исходных данных и составе участников операции,

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

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

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

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

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

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

5. Архитектура многопроцессорного комплекса NERV класса MTMD для
реализации генетических и нейросетевых алгоритмов, имеющего близкий к
линейному рост производительности при наращивании количества процессоров за
счет использования новых принципов фуішционирование его основных компо
нентов и введения в комплекс распределенного параллельного процессора класса
SIMD для скоростного выполнения наиболее часто встречающихся ЛО. Это позво
ляет использовать NERV для реализации генетических алгоритмов и моделей ней
ронных сетей с практически произвольными параметрами и сравнивать
эффективность достигнутых решении для конкретных прикладных задач.

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

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

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

Личный вклад соискателя. Основные положения, выносимые на защиту получены лично автором. В совместных с автором работах А.В. Шаренков, Н.Н. Легонин и Р. Хаузер (ФРГ) принимали участие в разработке системного и прикладного программного обеспечения системы NERV, А.Г. Ярусов, Г.А. Буткин и В.Е. Чернявский участвовали в разработке функциональных схем конкретных РПП, Г.Ю.Вальчевская разработала программное обеспечение для м делировапия основных ЛО, а также разработала методику и алгоритмы тестирования для скоростной реализации ЛО с целью верификации методов, предложенных автором. Совместно с В.Е.Чернявским был разработан алгоритм построения экстремальных кодов для реализации операции поиска максимального числа, а с Р. Хаузером и В.В. Анищенко - функциональная схема нейропроцессора. Техническая реализация двух образцов многопроцессорной системы NERV была выполнена сотрудниками совместной международной лаборатории, руководимой автором настоящей диссертации и проф. Р. Мэниером - руководителем отделения Информатика, заведующим кафедрой информатики V университета г. Мангейма, ФРГ.

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

1. Вторая Всесоюзная конференция "Информатит-87", Академия наук Армении, Ереван, Армения, 1987.

2. Второе международное совещание "Параллельная обработка: логика, организация, технология" (WOPPLOT 89), Вилдбад-Кройт, Германия, 1989.

3. Совместная международная конференция "Векторная и параллельная обработка" (CONPAR 90 - VAPPIV), ЕТН, Цюрих, Швейцария, 1990.

4. Шестой международный симпозиум "Информатика и вычислительная техника", Анталия, Турция, 1991.

5. Третье международное совещание "Параллельная обработка: логика,
организация, технология"(WOPPLOT 92), Тутцинг, Германия, 1992.

6. Вторая совместная международная конференция "Векторная и параллельная обработка" (CONPAR 92 - VAPP V), Лион, Франция, 1992.

7. Международное совещание "Разработка высокопроизводительных параллельных архитектур", Минск, Республика Беларусь, 1992.

8. Вторая международная конференция "Технологии параллельных вычислений"(РаСТ 93), Обнинск, Россия, 1993.

9. Международный симпозиум по параллельной обработке (IPPS'95), Сайта
Барбара, Калифорния, США, 1995.

10. Международная конференция "Автоматизация проектирования
дискретных систем" (CAD DD'95), Минск, Республика Беларусь, 1995.

11. Четвертая международная конференция "Параллельные системы и
алгоритмы"(PASA'96), Юлих, Германия, 1996.

12. Международная конференция "Автоматизация проектирования
дискретных систем", Минск, Республика Беларусь, 1995.

13. Международное совещание "Сетевой и информационный сервис в
странах Центральной и Восточной Европы", Благоевград, Болгария, 1996.

14. Международная конференция "Моделирование интеллектуальных
процессов проектирования и производства", Минск, Республика Беларусь, 1996.

Опублнкованность результатов. По материалам диссертации опубликовано 95 печатных работ, в том числе 1 монография, 2 брошюры, 32 статьи и 42 изобретения. Основные результаты достаточно полно отражены в 82 печатных работах, перечень которых приведен в автореферате.

Структура и объем диссертации. Диссертация изложена на 192 страницах. Она содержит введение (4 стр.), общую характеристику работы (10 стр.), 6 глав (170 стр., в том числе 48 рисунков, 20 таблиц), выводы (3 стр.) и список литературы, включающий 247 наименований (18 стр.). Приложение (88 стр.) включает акты о внедрении результатов работы, архитектуру и функциональное описание элементов комплекса NERV, а также сведения о его программном обеспечении.