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

Г Г" '3

I ¡.5 \Ы

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ; ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ

УДК 681.3

Маханск Михаил Михайлович

МЕТОДЫ ОРГАНИЗАЦИИ СИСТЕМ ПАРАЛЛЕЛЬНОЙ ОБРАБОТКИ НА ОСНОВЕ СКОРОСТНОЙ РЕАЛИЗАЦИИ БАЗОВЫХ ЛОГИЧЕСКИХ ОПЕРАЦИЙ

05.13.13. - Вычислительные машины, комплексы, системы и сети

Автореферат диссертации на соискание ученой степени доктора технических наук

Минск 1997

Работа выполнена в ордена Трудового Красного Знамени Институте технической кибернетики Национальной Академии наук Беларуси

Научный консультант: член-корреспондент НАНБ, доктор физико-

математических наук, профессор B.C. Танаев

Официальные оппоненты: д.т.н., профессор, Галушкин А.И.

д.т.ы., профессор, Мищенко В.А.

д.т.н., профессор, Вишняков В.А.

Оппонирующая организация: Научно-исследовательский институт

электронных вычислительных машин

Защита состоится " 2 " октября 1997 г. в 14°° часов на заседании совета по защите диссертаций Д 02.15.01 в Белорусском государственном университете информатики и радиоэлектроники по адресу: 220027, г. Минск, ул. П. Бровки, 6, БГУИР, корп. 1, ауд. 232.

С диссертацией можно ознакомиться в библиотеке Белорусского государственного университета информатики и радиоэлектроники

Автореферат разослан "г/-7 " июля 1997 г.

Ученый секретарь

совета по защите диссертаций,

доктор технических наук

Кешишьян В.А.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

* распознавание образов, в том числе рукописных текстов и речи,

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

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

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

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

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

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

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

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

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

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/BYE/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" для расширения возможностей научно-информационной компьютерной сети Академии наук Беларуси;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Личный вклад соискателя. Основные положения, выносимые на защиту получены лично автором. В совместных с автором работах A.B. Шаренков, H.H. Легонип и Р. Хаузер (ФРГ) принимали участие в разработке системного и прикладного программного обеспечения системы NERV, А.Г. Ярусов, Г.А. Буткин и В.Е. Чернявский участвовали в разработке функциональных схем конкретных РПП, Г.Ю.Вальчевская разработала программное обеспечение для м делировапия основных JIO, а также разработала методику и алгоритмы тестирования для скоростной реализации ЛО с целью верификации методов, предложенных автором. Совместно с В.Е.Чернявским был разработан алгоритм построения экстремальных кодов для реализации операции поиска максимального числа, а с Р. Хаузером и В.В. Анищенко - функциональная схема нейронроцессора. Техническая реализация двух образцов многопроцессорной системы 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, а также сведения о его программном обеспечении.

ОСНОВНОЕ СОДЕРЖАНИЕ

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

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

детально неизвестны юш сложно формулируются правила (алгоритмы) решения, но известно соответствие между последовательностями входной информации и реакцией системы;

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

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

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

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

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

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

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

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

На основании этих требований предложены следующие принципы построения СПО для скоростной реализации искусственных нейронных сетей и генетических алгоритмов:

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

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

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

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

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

Вторая глава посвящена разработке общей структуры распределенного параллельного процессора (РПП) класса БМО для скоростного параллельного выполнения логических операций. РПП состоит из Е ПЭ (Рис. 1).

Все входы и выходы РПП являются бинарными. ПЭ функционируют асинхронно и могут иметь различную производительность. Все ПЭ взаимосвязаны N шинами Ь;, ¡=1,2,.и тремя линиями синхронизации Р, О, К (для простоты опущены). Каждый ПЭ .¡, {1,...,Е}, имеет конвейерную структуру и состоит из N комбинационных узлов 1]пк(У), которые последовательно связаны между собой множеством индивидуальных линий управления СЫ(У). Все узлы одного каскада

¡6 {1,2,...,14} выполняют один и тот же шаг операции. Они принимают общие входные данные с шины Ь)-1 и локальные данные со входов Ба1а(],1) и выставляют сигналы на пшну 1д.

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

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

Третья глава посвящена разработке методов оптимального представления (кодирования) данных на входах ПЭ для. скоростной реализации логических операций в РПП. Основная идея состоит в следующем. В комбинационных сетях длительность выполняемой операции, как правило, определяется, как максимальная задержка распространения сигналов при ¡всех возможных комбинациях исходных данных, используемых ПЭ. Очевидно, что в большинстве случаев это максимальное значение обуславливается лишь небольшим числом из множества комбинаций сигналов на входах РПП. Исключение этих комбинаций не только не ухудшает в большинстве случаев функциональных возможностей РПП, но позволяет значительно сократить время выполнения операции. Рассмотрена проблема скоростной реализации базовых для нейронных сетей и генетических алгоритмов логических операций поиска максимума и медианы. Для решения этой проблемы предложены метод биномиального кодирования для поиска максимума и метод оптимального представление дашшх для поиска медианы и введены следующие понятия.

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

Пусть А[ч,г] является последовательностью разрядов

1<Ч<гЗЧ, двоичного слова А]=ча1,]...а>у>. Назовем последовательность ми последовательность А][ч,г]® соответственно "1"-интервалом или "0"-ттервалом слова А], если А][ц,г] состоит либо только из "1" либо только из "0" разрядов и если Ч>1, аг^аг+у, если г<14. Назовем биномиальным

кодом В1(п,1Ч) код, состоящий из всех 14-разрядных слов, которые имеют не более

п+1 интервалов, если их старший разряд равен "О", и не более п интервалов, если их старший разряд равен "1". Назовем медианным кодом Мс)(п,!Ч) множество всех возможных 14-разрядных слов, которые имеют независимо от значения их старшего разряда не более п интервалов.

В результате применения методов оптимального представления данных выявлен ряд свойств систем кодирования, позволяющих ускорить реализацию ЛО. Для формирования оптимальных кодов использовано экстремальное свойство их мощности:

Доказано, что биномиальный код ВЦпД) является оптимальным, имеет и состоит из максимально возможного для глубины п количества слов В1пу^=Х5_ф „С^. Предложены алгоритмы формирования оптимальных кодов

для заданных значений глубины п, т.е. кодов, при использовании которых длительность ЛО ограничена заданной величиной. Это позволяет разрабатывать РПП с заданными характеристиками производительности при минимальных затратах оборудования. Установлено, например, что при увеличении количества линий арбитража с N до N+1 арбитражные слова могут быть представлены кодом, который сокращает максимальное время поиска максимального числа в РПП в два раза. Это следует из доказанного соотношения: В¡^2'^2 1 - Доказано, что медианный код Мс1(п,М) является оптимальным, имеет и состоит из максимально возможного для глубины п количества слов > Его использование позво-

ляет сократить время поиска медианы в РПП в ^Д21Ч-1) раза, что следует из свойства Примеры оптимальных кодов приведены на Рис. 2.

11 11111

1 0 11110

00 11100

00 11000

00 1 0 000

11 01111

1 0 00 111

0 0 00011

00 00001

11 00000

10

00

11

10

0 1

00

В!(2,5) !УН(2,5)

Рис. 2. Примеры биномиального и медианного кодов.

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

ОПЕРАЦИЯ

Рис. 3. Многошаговая параллельная операция

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

Для реализации метода введены следующие понятия. Продолжительность Т(£) операции - это суммарное время выполнения всех ее шагов, где Z - множество ПЭ, участвующих в операции. Определим значение ^,1-1, если ПЭ} вносит наибольшую по времени задержку при реализации своей части 1-й, (¡6 {1,...,!Ч'}) распределенной операции, «^д =0 в противном случае, так чтобы Тогда

время выполнения ¡-го шага является суммой времени б| реализации ¡-й глобальной части и времени затрачиваемого на выполнение ¡-й распределенной

локальной части. может рассматриваться как индивидуальная "единица измерения времени", значение которой обратно пропорционально производительности ]-го ПЭ, а Ь1 является мерой сложности распределенной локальной части ¡-го шага. Тогда длительность параллельной операции 1 определится как £ ^^ где - количество

временных интервалов т\, вносимых ПЭ в общее время выполнения операции. Рассмотрены два случая. В первом - каждый ПЭ обладает информацией только о своем значении -г], поэтому справедливо условие 0<т]<<*>. Во втором - используется тот факт, что производительность ПЭ ограничена, т. е. Т1<т]<Тц

Определение продолжительности операции в системе осуществляется следующим образом. После того как все ПЭ попугали сигнал о начале операции I, они выставляют сигналы "1" на соответствующую линию синхронизации, например Р, с открытым коллектором, реализующую логическую функцию ИЛИ. При выполнении операции каждый ПЭ ^ ждет определенное время перед тем как изменить свой "1" сигнал на "О". Когда значение сигнала на линии Р переходит в состояние "О", это является для всех ПЭ признаком окончания операции. Следовательно, общее время ожидания окончания операции I в системе составляет Мах {^,1), ¡еТ,}, а условием корректного завершения операции является Мах

А™ возможных значений т]*, где п]=(1(],1)-

^¡=1 Таким образом, задача определения длительности параллельной

операции сводится к отысканию коэффициентов п].

Однако, в общем случае, исходя из предыдущего условия, невозможно вычислить ни один из коэффициентов и]*, так как он зависит от неизвестных величин т], ]£ Следовательно, для определения момента окончания операции

всем ПЭ необходимо определенным образом скоординировать свои действия. Такое возможно при помощи доказанных условий.

Необходимым и достаточным условием корректного завершения операции является E.g^i^/11])-! ДО» всех возможных значений Tj из интервала 0<tj<°®, и £jeZ((cjßj)/nj + (cjTH(l - ßj))/(TL Max {njV jeZ})21, для tj из интервала TLäTj<TH, где ßj=0, если Max {nj*, j'eZ}>(njTH)/TL> ßj=1>в противном случае.

Показано, что задача шшимизации среднего времени ожиданий для всех процессоров сводится к минимизации функции Г(Z)=2jе ^^JnJ' где К0ЭФФипРен'г

aj=^d=l ^.j^^iPdC^'^E-j)/С^Е, - вероятность того, что n3j* участвует в операции, рк - вероятность того, что в операции участвует группа из к (к={1,...,Е}) ПЭ, 1 EPd=1' ^ решению задачи ведут доказательства следующих выводов.

При выполнении условия (?je£cj/nj)=l минимальное значение функции F(Z) определяется по формуле F(Z)=(Ljg ^л/cjaj )2.

Если имеет место условие (£jigZ>cj7njO^(T^/nkTL)(Xj»6£..Cj',)=l, keZ',

то Min F = (-^ock(ck + Th/Tl 2j-6 z..cj») + IjeZU-\/cj'aj' )2.

На основании доказанных теорем был сформулирован метод отыскания оптимальных индивидуальных величин времени t(j,l) ожидания окончания операции. Так, в случае Octj<°° величина индивидуального времени ожидания для k-го процессора составит t(k,l)=(-\/ck /л/схк fa-

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

В пятой главе с целью сокращения общего времени ожидания реализации параллельных операций, в которых участвует большое количество процессоров предлагаются альтернативный принцип синхронизации и метод, позволяющий организовать скоростное выполнение параллельных процессов в распределенных многопроцессорных системах. Разработанный метод является альтернативой метода синхронизации Тауба, предложенного для стандарта IEEE 896, и также базируется на трех линиях синхронизации и распределенном синхронизаторе. В основе нового метода лежит следующий принцип: любой процессор может начать очередную операцию и любой процессор может инициировать ее окончание. Последнее возможно, если он распознает, что либо все результирующие выходные

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

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

сгенерированные всеми процессорами, и, следовательно, сигналы на линиях Р^и К монтажной логики установлены в 0, 0 и 1 соответственно. Тогда последовательность событий синхронизации реализуется в соответствии с алгоритмом (протоколом), представленным в табл. 1.

Таблица 1.

Предлагаемая синхронизация с периодом 2

# Шаги протокола синхронизации_РОВ.

1 2

3

4

9

10

11

0

1

0

1

1

Исходное состояние для начала первой операции. Начало первой операции. Процессор кеХ\, начинающий первую операцию, устанавливает вызывая переключение О в 1. Все остальные процессоры jeZ^ распознают 0=1 и также начинают первую операцию. Они устанавливают qj=l. Процессор веЖ] определяет, что остальные процессоры не смогут повлиять на результат первой операции. Для окончания операции он устанавливает р5=1, вызывая переключение Р в 1. Все остальные процессоры jeZ^ распознают окончание первой операции согласно Р=1. Они устанавливают р^=1. Все процессоры устанавливают г|=0, вызывая переключение К в 0. Все процессоры распознают И=0 и устанавливают Р]=0,

вызывая переключение Р в 0. Исходное состояние для второй операции.

Начало второй операции. Процессор Ье^, начинающий вторую операцию, устанавливает 1^=1, вызывая переключение К в 1. Все остальные процессоры jeZ2 распознают К=1 и начинают вторую операцию. Они устанавливают .

Процессор «е Ъ^ определяет, что остальные процессоры не смогут повлиять на результат второй операции. Для окончания операции он устанавливает р5=1, вызывая переключение Р в 1. Все остальные процессоры jeZ2 распознают окончание второй операции согласно Р=1. Они устанавливают р]=1.

12 Все процессоры устанавливают <у=0, вызывая переключение О в 0.

13 Все процессоры распознают 0=0 и устанавливают р]=0, вызывая переключение Р в 0. Исходное состояние для начала третьей операции.

Преимущество преложенного метода заключается в том, что он существенно повышает производительность системы, так как практически всегда момент

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

Для верификации достигнутых теоретических результатов и моделирования работы РПП была разработана система dsPLAY скоростной реализации ЛО. Система состоит из 16 логических модулей (ЛМ), в которых могут быть запрограммированы различные РПП; устройства измерения времени (УИВ) выполнения операций, имеющего высокую разрешающую способность; и интерфейса к управляющему компьютеру Macintosh (Рис. 4). Для обеспечения программного и операционного контроля система реализована в крейте стандарта VME. В системе dsPLAY применение микропроцессоров необязательно. С точки зрения ЛО задача микропроцессора заключается только в том, чтобы доставить в РПП значение индивидуального операнда, начать и завершить операцию. Все остальные процедуры выполняются аппаратно без контроля с его стороны. Время подготовки и загрузки значения операнда не увеличивают время выполнения ЛО, так как эти действия и выполнение ЛО осуществляются конвейерным путем. Реализация текущей ЛО и подготовка данных для последующей в большинстве случаев также выполняются конвейерным путем управляющим компьютером путем их загрузки через интерфейс Sbus-VMEbus в регистры каждого ЛМ.

Рис. 4. Архитектура системы dsPLAY для скоростной реализации ЛО.

Ядро логического модуля системы dsPLAY базируется на СБИС с вентильной матрицей ХЕЬШХ (ХС 3042), в которой программируется требуемая ЛО. Программа, определяющая внутренние связи СБИС, генерируется специальным программным обеспечением. Она должна быть загружена в СБИС всякий раз при включении dsPLAY или при необходимости реализации очередной ЛО. Иными словами, СБИС может быть перепрограммирована, т.е. настроена на очередную ЛО, в динамике работы системы.

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

предложенных принципов построении универсальной вычислительной среды для скоростной реализации нейронных сетей и генетических алгоритмов разработана архитектура многопроцессорного комплекса. Комплекс объединяет многопроцессорную систему - нейрокомпьютер NERV, состоящий из группы однотипных нейромодулей, хост-компьютер SPARCStation-2 с графическим интерфейсом пользователя в системе UNIX и управляющие компьютеры, связанные с NERV локальной сетью Ethernet, в том числе две SPARCstation-20 (рис. 5).

<

SPARC-SUN (хост компьютер)

VMEbus интерфейс —75Г-

S-bus-

VMEbus

интерфейс

7F <1>

>

НП НП

#1 ... #N

Плата запуска подтверждения

НЕИРОПРОЦЕССОР

И

Логика интерфейса, драйверы шины

"ТП

Статическая память

ТЧ

CPU Motorola

ПЭ для реализации ЛО

L

НЕИРОПЛАТА

VMEbus интерфейс,

логика и драйверы шины --

Нейро-процессор #1

локальная шина

¡S

Нейро-процессор #2

Рис. 5. Нейрокомпыотерный комплекс NERV

В комплекс также входят: стример для магнитных лент 4 мм емкостью 2 Гбайта, устройство чтения компакт дисков с интерфейсом FAST SCSI-2 в настольном исполнении., устройство записи-чтения магнитооптических дисков емкостью 1.2 и 1.3 Гбайта с интерфейсом SCSI-2 в настольном исполнении, два магнитооптических перезаписываемых дисков 5,25". сканер 1200 dpi для ввода изображений с их твердых копий, видеокамера SONY SSC-DC30 (570 линий, 0.9 Lux) для получения изображений с микроскопа, плата Matrox Marwell-П VID емкостью памяти 2 Мбайта для ввода видеоинформации с камеры в компьютер, принтер 1200 dpi Lexmark Optra R+, адаптер для подключения компьютера к компьютерному томографу

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

Нейрокомпьютер расположен в VME-крейте н базируется на стандартном интерфейсе VMEbus, в который введены дополнительные расширения для поддержки выполнения глобальных логических операций. Нейромодуль расположен на VME-плате и включает два нейропроцессора (НП), связанных общей локальной шиной. Модули нейрокомпьютера связаны с хост-компьютером, специализированной средой обмена, которая базируется на стандартном интерфейсе Sbus-VMEbus и поддерживает операции ввода/вывода. С целью достижения высокой плотности элементов и производительности НП разработаны таким образом, чтобы обеспечить реализацию лишь минимально необходимого набора функций. НП состоит из микропроцессора семейства MC68020, функционирующего с частотой 20 'MHz и имеющего локальную статическую память объемом 512 КВ.

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

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

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

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

- библиотеку стандартных функций NERV, которая обслуживает каждую программу, выполняющуюся в среде NERV;

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

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

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

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

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

ВЫВОДЫ

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

Полученные в диссертации новые научные выводы и результаты сводятся в основном к следующему:

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

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

- исходные данные поступают с помехами (искусственного или естественного характера),

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

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

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

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

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

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

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

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

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

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

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

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

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

СПИСОК ОСНОВНЫХ РАБОТ, ОПУБЛИКОВАННЫХ АВТОРОМ ПО ТЕМЕ ДИССЕРТАЦИИ:

1. Маханек М.М. Параллельная вычислительная система для высокоскоростной реализации логических операций,- Минск: ИТК АНБ, 1994,- 152 с.

2. Makhaniok М. Massively Parallel Distributed Processing of Logical Operations: PhD Dissertation.- Mannheim: University of Mannheim, Germany, 1994,- 129 p.

3. Маханек M.M., Анищенко B.B., Шаренков A.B., Маннер Р., Хаузер P. Мультимикропроцессорная система NERV для моделирования эволюционных процессов,- Минск: ИТК АНБ, 1994,- 132 с.

4. Makhaniok М, High-Speed Realization of the Median Search Operation H International Conference on Computer-Aided Design of Discrete Devices.- Minsk, 1995.-Vol.2.-P. 103-104.

5. Makhaniok M. Logical Operations and Processors // International Conference on Computer-Aided Design of Discrete Devices.- Minsk, 1995,-Vol. 2,-P. 105-108.

6. Маханек М.М. Принципы построения параллельного распределенного процессора для скоростной реализации логических операций // Препринт N Э.Минск: ИТК АНБ, 1994.- 10 с.

7. Маханек М.М. Реализация генетических алгоритмов оптимизации на многопроцессорной системе NERV // Моделирование интеллектуальных процессов проектирования и производства.-Минск, 1996,-С. 19-20.

8. Маханек М.М. Многопроцессорная система для моделирования интеллектуальных процессов проектирования с использованием нейро-компьютинга // Моделирование интеллектуальных процессов проектирования и производства.-Минск, 1996,-С. 10-11.

9. Маханек М.М. Параллельная реализация стандартного генетического алгоритма // Известия АН Беларуси, сер. физ.-техн. паук.- 1997.- N 1,- С. 92-103.

10. Makhaniok М., Manner R. Synchronization of Parallel Processes in Distributed Systems // Lecture Notes in Computer Science - 1992,- Vol. 634.- P. 157-162.

11. Makhaniok M., Manner R. Duration of Operations in Distributed System, Proceedings 4th PASA Workshop.- World Scientific Publishing, Juellich.- 1996,- P. 109-124.

12.Маханек M.M., Мэннер P., Хаузер P. Нейрокомпьютерная система NERV для решения прикладных задач обработки информации сложной структуры // Известия АН Беларуси, сер. физ.-техн. наук.- 1993.- N 2,- С. 67-84.

13. Makhaniok М„ Cherniavsky V., Manner R., Stucky О. Massively Parallel Realization of Logical Operations in Distributed Parallel Systems // Lecture Notes in Computer Science - 1990,- Vol. 457,- P. 796-805.

14. Makhaniok M., Cherniavsky V., Manner R., Stucky O. Effective Implementation of Distributed Arbitration in Multiprocessor Systems // Lecture Notes in Computer Science - 1991,- Vol. 565, Springer, Berlin -. P. 148-156.

15.Hauser R., Horner H., Manner R., Makhaniok M. Architectural Considerations for NERV - a General Purpose Neural Network Simulaton System // Lecture Notes in Artificial Itellgence.-1991,- Vol. 565,- P. 183-195.

16. Makhaniok M., Cherniavsky V., Manner R., Noffz K.-H. Extremal Codes for Speedup of Distributed Parallel Arbitration// Parallel Algorithms and Applications.- 1995,-Vol. 6,- P. 1-16.

17.Makhaniok M.M., Cherniavsky V., Marte C., Manner R. Data Representation for Median Search Operation // Computer and Information Science.- 1991.- Vol VI. - N.2.-P. 1011-1017.

18. Makhaniok M., Cherniavsky V., Manner R., Stucky O. Binomial Coding in Distributed Arbitration Systems // Electr. Letters. -1989,-Vol. 25, N 20.- P. 1343-1344.

19. Makhaniok M., Cherniavsky V., Manner R., Stucky O. Reduced Bus Acquisition Time in Distributed Arbitration Systems // Electronic Letters- 1989,- Vol. 25, N 23,-P. 1593-1594.

20. Hauser R_, Manner R., Makhaniok M. Parallel Execution of Sequentially Coded Standard Genetic Algorithms on the NERV Multiprocessor // 9th International Parallel Processing Symposium.- Santa Barbara, 1995,- P. 782-789.

21.Tuzikov A., Makhaniok M., Manner R. Biciiterion Scheduling of Identical Processing Time Jobs by Uniform Processors // 9th International Parallel Processing Symposium. -Santa Barbara, 1995.- P. 276-279.

22. Ярусов А.Г., Маханек M.M. Реализация параллельного алгоритма в системе с произвольным числом процессоров // Известия АН БССР. Сер. физ.-тех. наук.-1984,- N 3,- С. 70-75.

23.Ярусов А.Г., Маханек М.М., Чернявский В.Е, Управление взаимодействием параллельных процессов с динамическими приоритетами при доступе к одиночному ресурсу // Изв. АН БССР. Сер. физ.-тех. наук.- 1986,- N 2,- С. 73-77.

24. Маханек М.М., Чернявский В.Е., Ярусов А.Г. Оптимальное приоритетное назначение программ на процессоры в системе реального времени // Известия АН БССР. Сер. физ.-тех. наук,- 1986,- N4,- С. 108-113.

25. Ярусов А.Г., МаханекМ.М., Чернявский В.Е. Архитектура многопроцессорной вычислительной системы реального времени // 2-я Всесоюзная конф. "Информатика-87": Тез. докл. конф.- Ереван, 1987,- С. 8-9.

26.Маханек М.М., Ярусов А.Г., Чернявский В.Е. Аппаратная реализация функций исполнительной программы многопроцессорной системы И 2-я Всесоюзная конф, "Информатика-87": Тез. докл. конф,-Ереван, 1987,- С. 6-8.

27.Чернявский В.Е., Маханек М.М. Устройства приоритета в базисе ПЛМ -компактность и быстродействие // Микропроцессорные средства и системы. -1988,-N6,- С. 45-48.

28.Ярусов А.Г., Маханек М.М., Чернявский В.Е. Архитектура многопроцессорной вычислительной системы реального времени // Известия АН БССР. Сер. физ.-тех. наук.- 1989.- N 1,- С. 100-105.

29. Маханек М.М., Чернявский В.Е. Биномиальное кодирование в распределенных системах арбитража // Изв. АН БССР. Сер. физ.-тсх. наук,- 1990,- N 3.- С. 81-85.

30. Makhaniok М., Manner R. Dominant Operations in Distributed Arbitration Process // Proceedings WOPPLOT 92,- Tutzing, Germany, 1992,- P. 85-97.

31. Makhaniok M., Hesser J., Noehte S„ Manner R. Stable Attractors of Two-Dimensional Dynamical Systems // Proceedings WOPPLOT 92,- Tutzing, Germany.- 1992. -P. 98-123.

32. Makhaniok M., Manner R. (Ed.) High-Performance Parallel Architectures Design.-Minsk: Inst, of Engineering Cybernetics, Acad, of Sci. of Belarus, 1992.- 204 c.

33. Маханек M.M., Вальчевская Г.Ю. Координационная деятельность по нейрокомпьютерам в европейской стратегической программе развития информационных технологий И Разработка высокопроизводительных параллельных архитектур,-Минск: АН Беларуси, 1992.- С. 6-23.

34.Hauser R., Stotzka R., Manner R., Makhaniok M. Multiprocessor Neural Network Simulation System NERV // High-Performance Parallel Architectures Design.- Minsk: Inst, of Engineering Cybernetics, Acad, of Sci. of Belarus, 1992.- P. 24-41.

35.Noffz K.-H., Manner R., Makhaniok M., Cheraiavsky V. A Reconfigurable Test System for Distributed Logical Operations // High-Performance Parallel Architectures Design- Minsk: Inst, of Eng. Cybernetics, Acad, of Sci. of Belarus, 1992.- P. 42-49.

36. Маханек M.M., Павленко И.А., Мэннер P. Скоростная реализация процесса поиска медианы // Разработка высоко-производительных параллельных архитектур,- Минск: ИТКАНБ, 1992,- С. 50-59.

37. Вальчевская Г.Ю., Маханек М.М., Чернявский В.Е. Программное моделирование логических операций в распределенном параллельном процессоре // Разработка высоко-производительных параллельных архитектур.-Минск: ИТК АНБ, 1992,- С. 60-70.

38. Hauser R, Manner R., Makhaniok M. Sequentially Coded Parallel Genetic Algorithms on NERV // PaCT-93.- Moscow, 1993.- Vol. 2,- P. 26-37.

39.Маханек М.М., Вальчевская Г.Ю., Мэннер Р., Ноффц К.-Х. Синхроншация логических операций в однородных параллельных структурах // Препринт N 9,-Минск: НТК АНБ, 1993,- 58 с.

40.Маханек М.М., Хаузер Р., Маннер Р., Вальчевская Г.Ю. Архитектура многопроцессорной системы для эффективной реализации генетических алгоритмов // ПрепринтИ 6.- Минск: ИТК АНБ, 1994,- 30 с.

41. Вальчевская Г.Ю., Маханек М.М. Перепрограммируемый комплекс (ЬРЬАУ для моделирования логических операций // Автоматизация проектирования дискретных систем.- Минск, 1995,- Том 1,- С. 28.

42. Маханек М.М., Вальчевская Г.Ю., Мэннер Р. Синхронизация параллельных операций в распределенных многопроцессорных системах. Известия АН Беларуси, сер. физ.-тех наук, N 2, 1995,- С. 70-79.

43. Маханек М.М., Вальчевская Г.Ю., Маннер Р. Минимизация верхней оценки продолжительности параллельной операции // Известия АН Беларуси, сер. физ.-тех. наук.- 1995,-N 3,- С. 48-53.

44. Маханек М.М., Вальчевская Г.Ю. Перепрограммируемая система для моделирования параллельных логических операций // Известия АН Беларуси, сер. физ.-тех. наук.- 1996,- N 4,- С. 58-63.

45.1168944. Устройство для обслуживания запросов с переменными приоритетами /М.М. Маханек, А.Г. Ярусов (СССР).-N 3700643/24-24; Заявл. 14.02.84; Опубл.

23.07.85, Бюл. N 27.-3 с.

46.1190382. Многоканальное устройство приоритетного обслуживания / М.М.Маханек, А.Г.Ярусов, Н.Н.Новик (СССР).- N 3751007/24-24; Заявл. 29.05.84; Опубл. 07.11.85, Бтол. N41.-3 с. 47.1211717. Устройство для определения среднего из ш чисел / Г.А.Буткин, М.М.Маханек, А.Г.Ярусов (СССР).- N 3772080/24-24; Заявл. 16.07.84; Опубл.

15.02.86, Бюл. N 6.-5 с.

48.1211719. Устройство для выбора наименьшего из п чисел / А.Г.Ярусов, М.М.Маханек, Н.Н.Новик (СССР).- N 3773691/24-24; Заявл. 16.07.84; Опубл. 15.02.86, Бюл. N 6.-3 с. 49.1252777. Устройство для приоритетного распределения заданий процессором / М.М.Маханек, А.Г.Ярусов (СССР).-N 3727173/24-24; Заявл. 06.04.84; Опубл. 23.08.86, Бюл. N31.-6 с. 50.1282127. Многоканальное устройство приоритетного обслуживания / А.Г.Ярусов, М.М.Маханек, В.Е.Чернявский (СССР).- N 3906354/24-24; Заявл. 07.06.85; Опубл. 07.01.87, Бюл. N 1.-4 с. 51.1290297. Устройство для определения локальных экстремумов функции / Г.А.Бужин, М.М.Маханек, А.Г.Ярусов (СССР).- N 3902145/24-24; Заявл. 27.05.85; Опубл. 15.02.87, Бюл. N 6.-4 с.

52.1291983. Устройство для распределения заданий процессорам / А.Г.Ярусов, М.М.Маханек, В.Е.Червдвский (СССР).- N 3947570/24-24; Заявл. 14.08.85; Опубл. 23.02.87, Бюл. N 7.-7 с. 53.1304025. Приоритетное устройство / Г.А.Буткин, М.М.Маханек, А.Г.Ярусов, В.Е.Чернявский (СССР).- N 3961095/24-24; Заявл. 04.10.85; Опубл. 15.04.87, Бюл. N 14.-8 с.

54.1307458. Устройство для выбора запросов по приоритетам / М.М.Маханек, А.Г.

Ярусов (СССР).-N867584/24-24; Заявл. 06.03.85; Опубл. 30.4.87, Бюл. N16.-4 с. 55.1327122. Устройство для выделения выборочной медианы из ш чисел / М.М.Маханек, В.Е.Чернявский, А.Г.Ярусов, П.Н.Бибило (СССР).- N 4026297/24-24; Заявл. 21.02.86; Опубл. 30.07.87, Бюл. N 28.-5 с.

56.1377855. Устройство приоритета / А.Г.Ярусов, М.М.Маханек, В.Е.Чернявский (СССР).-Я 4081947/24-24; Заявл. 26.06.86; Опубл. 29.02.88, Бюл. N8.-5 с.

57.1377856. Устройство приоритета / А.Г.Ярусов, М.М.Маханек, В.Е.Чернявский (СССР).- N4081950/24-24; Заявл. 26.06.86; Опубл. 29.02.88, Бюл. N 8.-4 с.

58.1401450. Устройство для определения экстремального кода / М.М.Маханек, В.Е.Чернявский, А.Г.Ярусов, Г.А.Буткин (СССР).- N 4161925/24-24; Заявл. 10.12.86; Опубл. 07.06.88, Бюл. N 21.-3 с. 59.1410020. Устройство для сравнения двоичных чисел / М.М.Маханек, В.Е.Чернявский (СССР).- N 4138565/24-24; Заявл. 20.10.86; Опубл. 15.07.88, Бюл. N 26,- 4 с.

60.1411746. Устройство циклического приоритета / М.М.Маханек, В.Е Чернявский,

A.Г.Ярусов (СССР).-N 4138554/24-24; Заявл. 20.11.86; Опубл. 23.07.88, Бюл. N 27.-Ю с.

61.1445521. Мажоритарное устройство / Г.А.Буткин, М.М.Маханек, В.Е.Чернявский, А.Г.Ярусов (СССР).-N 4161987/24-21; Заявл. 16.12.86; дх.п. - 7 с. 62.1455341. Устройство для выделения выборочной медианы из т чисел /

B.А.Головко, М.М.Маханек, А.Г.Ярусов, В.Е.Чернявский (СССР).- N 4265742/24-24; Заявл. 22.06.87; Опубл. 30.01.89, Бюл. N 4.-4 с.

63.1462310. Устройство для приоритетного обслуживания запросов / В.Е.Чернявский, М.М.Маханек, А.Г.Ярусов (СССР).- N 4225463/24-24; Заявл. 07.04.87; Опубл. 28.02.89, Бюл. N 8.-4 с. 64.1488798. Устройство для обслуживания запросов с приоритетами / А.Г.Ярусов, М.М.Маханек, В.Е.Чернявский (СССР).- N 4165201/24-24; Заявл. 22.12.86; Опубл. 23.06.89, Бюл. N 24,- 3 с. 65.1509896. Приоритетное устройство / Г.А.Буткин, М.М.Маханек, В.Е.Чернявский (СССР).- N 4400119/24-24; Заявл. 29.03.88; Опубл. 23.09.89, Бюл. N 35.-4с. 66.1534459. Устройство для обслуживания запросов с приоритетами / М.М.Маханек, В.Е.Чернявский, А.Г.Ярусов, П.Н.Бибило (СССР).- N 4278019/24-24; Заявл. 27.05.87; Опубл. 07.01.90, Бюл. N 1.-3 с.

67.1532930. Устройство для обслуживания запросов / В.Е.Чернявский, М.М. Ма-ханек (СССР).- N 4431747/24-24; Заяви 26.05.88; Опубл. 30.12.89, Бюл. Ы48.-Зс. 68.1536382. Устройство приоритета / В.Е.Чернявский, М.М.Маханек (СССР).- N

4403443/24-24; Заявл. 04.04.88; Опубл. 15.01.90, Бюл. N2.-3 с. 69.1539777. Устройство переменного приоритета / В.Е.Чернявский, М.М.Маханек,

A.Г.Ярусов (СССР).-N 4060925/24-24; Заявл. 28.04.86; Опубл. 30.01.90, Бюл. N 4.-4 с.

70.1619249. Устройство для выбора максимального числа из множеста п двоичных чисел / М.М.Маханек, В.ЕЛернявский (СССР).- N 4431751/24; Заявл. 26.05.88; Опубл. 07.01.91, Бюл. N 1.-3 с.

71.1619266. Устройство для приоритетного обслуживания запросов / М.М.Маханек, В.Е.Чернявский, А.Г.Ярусов (СССР).- N 4319657/24; Заявл. 22.10.87; Опубл. 07.01.91, Бюл. N 1.-4 с.

72.1619267. Устройство приоритета / М.М.Маханек, В.Е.Чернявский (СССР).- N 4431746/24; Заявл. 26.05.88; Опубл. 07.01.91, Бюл. N 1,-4 с.

73.1622883. Многоканальное устройство приоритета / М.М.Маханек,

B.Е.Чернявский, А.Г.Ярусов (СССР).- N 4345361/24; Заявл. 30.09.87; Опубл. 23.01.91, Бюл. N3.-3 с.

74.1624439. Устройство для определения среднего из т чисел / В.Е.Чернявскпн, М. М.Маханек (СССР).- N4648947/24; Заявл. 06.02.89; Опубл. 30.01.91, Бюл.№.-3 с.

75.1642468. Многоканальное устройство приоритета / М.М.Маханек,

. В.Е.Чернявский (СССР).- N4648946/24; Заявл. 06.02.89; д.с.п.-З с. 76.1226458. Устройство для приоритетного обслуживания / А.Г. Ярусов, М.М.Маханек, Н.Н.Новик (СССР).- N 3748469/24-24; Заявл. 05.06.84; Опубл. 23.04.86, Бюл. N 15.-3 с. 77.1241227. Устройство для определения локальных экстремумов / Г.А.Буткин, М.М.Маханек, А.Г.Ярусов (СССР).- N 3824272/24-24; Заявл. 17.12.84; Опубл. 30.06.86, Бюл. N 24.-4 с. 78.1275424. Устройство для выделения экстремального из и чисел / Г.А.Буткин, М.М.Маханек, А.Г.Ярусов (СССР).- N 3811399/24-24; Заявл. 05.11.84; Опубл.

07.12.86, Бюл. N45.-4 с.

79.1282128. Многоканальное устройство приоритета / А.Г.Ярусов, В.Е.Чернявский, М.М.Маханек (СССР).- N 3927659/24-24; Заявл. 11.07.85; Опубл. 07.01.87, Бюл. N 1.-4 с.

80.1283765. Многоканальное устройство приоритета / В.Е.Чернявский, МММаханек, А.Г.Ярусов (СССР).- N 3905863/24-24; Заявл. 04.06.85; Опубл.

15.01.87, Бюл. N2.-6 с.

81.1295394. Устройство для выбора запросов по приоритетам / А.Г.Ярусов, В.Е.Чернявский, М.М.Маханек (СССР).- N 3867057/24-24; Заявл. 06.03.85; Опубл. 07.03.87, Бюл. N 9.-3 с.

82.1305660. Устройство для определения локальных экстремумов функции / Г.А.Буткин, Е.Д.Забелло, М.М.Маханек, А.Г.Ярусов (СССР).- N 3934414/24-24; Заявл. 23.07.85; Опубл. 23.04.87, Бюл. N 15.-4 с.

РЭЗЮМЕ

дысертацыйнай працы Маханька Mixaina Мгхайлав1ча "Метады аргапизацьи сктэм паралельнай апрацоую на аснове хуткаснай рэагпзацьц базавых лапчных аперацый"

Юпочавыя словы:. пшатлрацэсарныя астэмы, размеркаваная апрацоука, нейракамп'ютэрныя астэмы, генетычныя алгарытмы, лапчныя аперацьп пошуку, нараунання, сартавання; аптымальнае надзираванне, апаратная спгхрашзацыя працэсарау, вызначэнне ярацягласш размеркаванай паралельнай аперацьп.

Распрацаваны прынцыпы арганизацы! астэмы паралельнай апрацоую для рэал1зацьн нейрасеткавых i генетычных алтарытмау, а таксама архиэктура размеркаванага паралельнага працэсара (РПП) класа SIMD для хуткаснага выканашм у шматпрацэсарных сютэмах класа MIMD паралельных аперацый лапчнага характару тылу пошуку, параунання, сартавання, анхратзацьп, i паралельнага абмену данымк Прапанаваны метады кадаравання, ягая абмяжоуваюць зададзенай вел!чынёй працягласць аперацый, ужываемых падчас мадэл1раваш1я эвалюцыйных працэсау, што забяспечыла стварэнне РПП з зададзеным1 характарыстыкам! прадукцыйнасщ пры мппмальных затратах абсталявання.

Распрацаваны метад вызначэння працягласщ лапчных аперацый (ЛА) у aciHxpoHHEix паралельных размеркаваных сютэмах як пры зададзеных абмежаваннях на прадукцыйнасць ПЭ, так i пры адвольных характарыстыках ix прадукцыйнасщ, што дазваляе выключыць адраснае узаемадзеянне пам1ж працэсарам1 пры рэал1зацьп JIA i мппЧпзаваць верхнюю мяжу працягласщ паралельнай ЛА. Даказаны неабходныя i дастатковыя умовы, яюя забяспе^гваюць пачасава-карэктнае выкапанне паралельных аперацый у РПП у выпадку, капц ПЭ не валодаюць шфармацыяй аб тых ПЭ, што удзельшчаюць у аперацьп, а таксама аб ix прадукцыйнасщ i выкарыстоуваемых даных. Прапанаваны метад ¡дэнтыфшацьй працягласщ J1A у дынамщы працы РПП як пры наяунасщ, так i адсутнасщ абмежаванняу на прадукцыйнасць я го ПЭ. Вызначаны верхняя мяжа працягласщ паралельнай аперацый i аптымальныя ве.тчыщ загрымак чакання заканчэння аперацьц для ПЭ у залежнасщ ад ix прадукцыйнасщ. Распрацаваныя метады пакладзены у аснову стварэнпя праграмна-тэхшчнага забеспячэння шматпрацэсарнага комплексу NERV для рэалгзацьи нейронных сетак i генетычных алтарытмау аптымшацьц i ажыццяуляюць збалансаванае фушсцыянаванне яго асноуных кампанентау.

РЕЗЮМЕ

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

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

Разработаны принципы организации системы параллельной обработки для реализации нейросетевых и генетических алгоритмов, а также архитектура распределенного параллельного процессора (РПП) класса SIMD для скоростного выполнения в многопроцессорных системах класса MJMD параллельных операций логического характера типа поиска, сравнения, сортировки, синхронизации и параллельного обмена данными. Предложены методы кодирования, ограничивающие заданной величиной длительность операций, встречающихся при моделировании эволюционных процессов, что обеспечило создание РПП с заданными характеристиками производительности при минимальных затратах оборудования.

Разработан метод определения длительности логических операций (JIO) в асинхронных параллельных распределенных системах как при заданных ограничениях на производительность ПЭ, так и при произвольных характеристиках их производительности, позволяющий исключить адресное взаимодействие между процессорами при реализации JIO и минимизировать верхнюю границу длительности параллельной J10. Доказаны необходимые и достаточные условия, обеспечивающие корректное по времени выполнение параллельных операций в РПП в случае, когда ПЭ не обладают информацией о ПЭ участвующих в операции, их производительности и используемых данных, Предложен метод идентификации длительности JIO в динамике работы РПП как при наличии, так и при отсутствии ограничений на производительность его ПЭ. Определена верхняя граница длительности параллельной операции и определены оптимальные величины задержек ожидания окончания операции для ПЭ в зависимости от их производительности. Разработанные методы легли в основу создания программно-технического обеспечения многопроцессорного комплекса NERV для реализации нейронных сетей и генетических алгоритмов и обеспечивают сбалансированное функционирование его основных компонентов.

RESUME

of the dissertation thesis "The methods of parallel processing system organization based on high-speed realization of basic logical operations" by Makhaniok Mikhail Mikhailovich

Key words: multiprocessor systems, distributed processing, neurocomputers, genetic algorithms, logical operations, search, comparison, sorting, hardware synchronisation, duration of distributed parallel operations.

The principles of massively parallel processing system organization for genetic and neurocomputing algorithms realization are elaborated. The architecture of a distributed parallel processor (DPP) of the SIMD class is proposed. DPP is implemented in multiprocessor systems of the MIMD class for high-speed execution of logical operations (LO), e.g., search, comparison, sorting, synchronization and parallel data exchange.

The methods for data coding are developed, which allow to increase the inherent parallelism of DPP and to minimize duration of parallel LO. These opeations are critical for multiprocessor systems during realization of genetic and neurocomputing algorithms. Application of the methods provide design of effective DPP having predetermined performance characteristics and minimal equipment costs.

The problem of minimization of an upper limit for duration of parallel LO without addressed data exchange between processors is solved. The method is proposed to determine duration of LO in asynchronous parallel distributed systems both for arbitrary and for the given boundary values for processing elements' performance. The necessary and sufficient conditions, providing time-correct execution of parallel operations by PEs in DPP, are proved. Implementation of these methods allow to exclude information exchange between PEs on their performance and data used for LO execution.

The method is proposed for dynamic identification of logical operations' duration in DPP both with and without limitations on the rate of PEs' performance. The upper bound of parallel operation duration and the optimal values of waiting delays of PEs are determined for termination of LO.

The elaborated methods were used for software and hardware design of the multiprocessor system NERV for neurocomputing and genetic parallel algorithms realization. The methods provide balanced functioning of the main components of the system.