автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.15, диссертация на тему:Концепция и методы совмещения вычислений и передачи данных в мультипроцессорных системах и локальных сетях

РОССИЙСКАЯ АКАДЕМИЯ НАУК

Институт проблем управления им. В.А Трапезникова

На правах рукописи

Стецюра Геннадий Георгиевич

КОНЦЕПЦИЯ И МЕТОДЫ СОВМЕЩЕНИЯ ВЫЧИСЛЕНИЙ И ПЕРЕДАЧИ ДАННЫХ В МУЛЬТИПРОЦЕССОРНЫХ СИСТЕМАХ И ЛОКАЛЬНЫХ СЕТЯХ

Специальность 05.13.15 "Вычислительные машины и системы"

Диссертация в виде научного доклада на соискание ученой степени доктора технических наук

Москва 2004

Работа выполнена в Институте проблем управления им. В.А. Трапезникова РАН

Официальные оппоненты: доктор технических наук, профессор Г.В. Росс доктор технических наук, профессор А.В. Шмид доктор технических наук, профессор А.А. Амбарцумян

Ведущая организация: Институт проблем передачи информации РАН

Защита состоится часов

на заседании Диссертационного Совета Д 002.226.03 Института проблем управления им. В.А. Трапезникова РАН по адресу: г. Москва, ГСП-7, 117997, ул. Профсоюзная, 65. Телефон Совета: (095) 335-93-29.

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

Диссертация в виде научного доклада разослана "" "_2004г.

Ученый секретарь Диссертационного Совета д.т.н.

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

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

Актуальность темы

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

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

Так как средства обмена данными не порождают новых данных, то они воспринимаются как неизбежные "накладные расходы".

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

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

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

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

- средства обмена данными участвуют в получении новых данных;

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

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

В дополнение к сказанному важно обеспечить независимость времени выполнения вычисления от количества участвующих I?' нем1 опе^а^дйй ? |

Все это направлено на ускорение выполнения основных функций рассматриваемых систем.

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

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

Объект исследования и решаемые задачи

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

- организацию приоритетного доступа к ресурсам систем обработки данных;

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

- управление взаимодействием устройств системы и контроль ее работоспособности;

- моделирование неоднородных систем на клеточных автоматах;

- параллельное выполнение эволюционных алгоритмов.

Основная составляющая разработанных в диссертации методов

Основу всех методов, рассмотренных в докладе, составили разработанные

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

Научная новизна

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

- управления доступом к ресурсам в распределенных системах;

- построения ряда важных компонентов распределенных операционных систем для АСУ ТП;

- построения локальных сетей для систем жесткого реального времени;

- организации параллельных алгоритмов.

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

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

Получено новое расширение клеточных автоматов - клеточные автоматы с дальними связями для моделирования неоднородных задач.

Все научные результаты диссертации получены впервые.

Прикладное значение

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

- существенного повышения скорости и гибкости доступа вычислительных устройств к каналу связи;

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

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

- Для АСУ ТП "КУРС, спроектированной совместно ИПУ и Грозненским НПО Промавтоматика, разработаны средства взаимодействия устройств системы, включая локальные сети, протоколы взаимодействия и распределенную операционную систему. Система "КУРС" была подготовлена НПО к серийному выпуску.

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

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

Публикации

По теме с 1967 по 2003 год опубликовано 89 научных работ общим объемом около 87 печатных листов, в том числе 2 монографии, 1 учебное пособие, 3 публикации в зарубежных изданиях, 27 статей в журналах из перечня ВАК (включая 3 изобретения). Из защищенных под руководством автора кандидатских диссертаций три относятся к тематике данной работы [С28 - СЗО].

Апробация работы.

Результаты работы докладывались в течение 32 лет на 37 отечественных, международных и зарубежных конференциях и семинарах. В том числе на следующих: Пятое всесоюзное совещание по проблемам управления, М, 1971; П-ASA Conference on Computer Communications Networks, Вена, 1974; 10-th World Congress on Automatic Control IFAC, Мюнхен, 1987; Международная конф. "Автоматизация производства", 1999; Международная конф. "Параллельные вычисления и задачи управления (РАСО 2001)", М. 2001; Вторая международная конференция по проблемам управления, М., 2003.

Структура работы.

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

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

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

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

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

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

СОДЕРЖАНИЕ ДОКЛАДА

Общая характеристика работы 1

Введение 7

ЧАСТЬ 1 Теоретические основы групповых операций 9

1.1 Приоритетный множественный доступ к общему каналу 9

1.1.1 Алгоритмы децентрализованного кодового управления доступом 10

1.1.2 Ускоренное ДКУ 12

1.1.3 Децентрализованное пространственно-временное управление 13

1.1.4 ДПВУ с гарантированным доступом 14

1.1.5 Алгоритмы типа "Система с бегущей волной" 15

1.2 Вычисление в общем канале (ВОК) 17

1.2.1 Организация ВОК для двоичной системы счисления 17

1.2.2 ВОК-сложение для системы счисления

с основанием т > 2 20

1.2.3 Оценка эффективности ВОК в вычислительных задачах 22

1.3 Структуры связи для групповых операций 25

1.3.1 Структура связей на основе плоских фрактальных линий 25

1.3.2 Многослойный канал Серпинского 28

1.3.3 Шинные линии дальней связи 29

1.3.4 Беспроводные связи 29

1.3.5 Канал "скрепка", неоднородные системы 30

1.4 Групповые команды и распределенные программы 32 ЧАСТЬ 2 Работа групповых операций в приложениях 38

2.1 Групповые операции для управления ресурсами распределенных систем жесткого реального времени 3 8

2.1.1 Гарантия доставки широковещательных и групповых сообщений 38

2.1.2 Групповые операции в канальных протоколах систем ЖРВ 39

2.1.3 Групповые операции в распределенных операционных системах 40 2.1.3.1 Снижение несбалансированности нагрузки абонентов 40 2.1.3.2. Устранение конфликтов на стороне приемника 41

2.1.3.3 Распределенная общая память (РОП) 42

2.1.3.4 Взаимное распределенное программирование 43

2.1.3.5 Диагностика и восстановление работоспособности системы, обнаружение искаженных сообщений 44

2.1.3.6 Групповые операции для управления порядком обслуживания в распределенных системах 45

2.2 Приложения с интенсивным взаимодействием распределенных данных 48

2.2.1 Клеточные автоматы с групповыми операциями и

дальними связями 48

2.2.2 Групповые операции в эволюционных алгоритмах 49

2.2.3 Групповые операции для ЭВМ, управляемых потоком данных 52

2.2.4 Использование групповых операций в комплексах GRID 53

2.2.5 Групповые команды в сетях мобильных датчиков 54 2.3 Реализованные технические средства с групповыми операциями 57

2.3.1 Применение групповых операций в системе АСУ ТП КУРС 57

2.3.1.1 Общая характеристика системы КУРС 57

2.3.1.2 Техническая реализация технологической сети 59

2.3.1.3 Техническая поддержка и особенности протокола канального уровня 61

2.3.1.4 Распределенная операционная система АСУ ТП КУРС. 62

2.3.2 Локальные сети с ГО, разработанные для других заказчиков 63

2.3.2.1 Локальная управляющая сеть промышленного

применения "Приоритет 1" 63

2.3.2.2 Локальные сети "АПЛС-1", "Лаура", 64

2.3.3 Локальные сети 12С и D2B фирмы Philips. 64 Заключение 64 Публикации по теме диссертации 68 Дополнительный список публикаций 75 Список сокращений 77

б

Введение

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

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

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

Получаемое в результате ускорение взаимодействия позволяет по-новому решить важные задачи:

- организацию доступа технических устройств к средствам связи;

- проведение распределенных вычислений;

- организацию распределенных программ;

- репликацию данных;

- повышение отказоустойчивости процессов обработки данных и ряд других задач.

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

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

Направлением разработок относящихся к тематике настоящей работы, которое не отражено в указанных выше публикациях, но очень актуально в настоящее время и хорошо отражено в периодике последних лет, является создание локальных сетей GRID [C21]. В таких GRID требуются операции, которые обеспечили бы как быструю координацию действий компонентов GRID, так и быструю обработку данных, распределенных в сети. Групповые операции существенно упрощают и ускоряют решение всех указанных задач.

В связи с актуальностью рассматриваемой тематики в Институте проблем управления РАН был выполнен цикл НИР, которые проводил автор и руководимый им научный коллектив. Центральное место в этих работах заняли иссле-

дование и разработка многих видов групповых операций.

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

Совокупность проведенных исследований складывалась из следующих этапов. В конце 60-х годов были начаты работы по созданию способов доступа компьютеров и процессоров (далее "абонентов") к общему для них каналу связи в распределенных управляющих системах жесткого реального времени. Стало ясно, что для этих работ полезно развить групповые операции, примененные в разработанных ранее автором ассоциативном запоминающем устройстве и ассоциативном процессоре. [СП - С16].

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

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

- существенно ускорить взаимодействие абонентов в распределенных системах реального времени;

-повысить отказоустойчивость таких систем;

— упростить и ускорить работу распределенных операционных систем АСУ ТП;

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

Полученные результаты позволили во второй половине 80-х и в начале 90-х годов выполнить работы по практическому применению ГО при создании АСУ ТП "КУРС" - типовой АСУ ТП с сетевой архитектурой для непрерывных производств.

Во второй половине 90-х годов и по настоящее время были выполнены следующие работы.

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

- Разработаны групповые команды и принципы построения распределенных программ на их основе.

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

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

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

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

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

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

Первая часть состоит из следующих четырех глав.

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

В главе 1.2 рассмотрены групповые операции для проведения вычислений.

В главе 1.3 рассмотрены структуры связи, ориентированные на выполнение групповых операций.

В главе 1.4 рассмотрены использующие групповые операции групповые команды и распределенные программы с применением таких команд.

Содержание второй части следующее.

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

В главе 2.2 рассмотрены групповые операции в приложениях с интенсивным взаимодействием распределенных данных.

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

ЧАСТЬ 1 Теоретические основы групповых операции 1.1 Приоритетный множественный доступ к общему каналу

Основные источники: [4,9,20,21,23,27,30,38,39,40,43,46,52,70,72]

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

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

Было разработано около 30 различных алгоритмов множественного доступа (ДКУ, ДПВУ и др.), их общее название - децентрализованное приоритетное управление доступом. Здесь будут приведены только ключевые алгоритмы, служащие родоначальниками нескольких близких по структуре алгоритмов.

1.1.1 Алгоритмы децентрализованного кодового управления доступом

(ДКУ)

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

Децентрализованное кодовое управление (ДКУ)

Принцип действия

Время Тх Т2 Т3

10 1 код источника А 110 код источника В

сигналы в линии 1

Доступ дм источника В 110

Рис. 1 ДКУ

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

В интервале времени, когда разрешено проводить борьбу, источники передают последовательно разряды своих кодов приоритетов, начиная со старшего разряда. Сигналы, представляющие двоичные 1 и 0 кода приоритета, должны быть такими, чтобы обнаруживалось наличие в линии сигнала 1 при наличии в ней сигнала 0. Источник передает сигналы с интервалом времени Тр. Сигнал передается в течение времени В течение времениисточник

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

точно, чтобы выполнялось соотношение Тр 2: 2т / (1 — Q). Здесь т - время прохождения сигнала по каналу [52].

В частном случае код приоритета - это адрес или индивидуальное имя источника данных. Именно такой вариант алгоритма ДКУ был впоследствии использован фирмой Philips (раздел 2.3.6). Но область применения метода расширяется, если в область старших разрядов кодов приоритета помещать числовые данные, характеризующие состояние системы. Например, так удается учитывать время ожидания обслуживания источника или срочность сообщения. ДКУ с помощью регулирования значений приоритетов позволяет достигнуть очень гибкого управления работой распределенных систем и обеспечивает гарантированный доступ источников данных к ресурсам системы различного вида.

Существенно быстрее этот алгоритм работает на линиях с направленной передачей сигналов и вычислением max при помощи ВОК (разделы 1.2.1,1.4)

ДКУ

Срташмвсрга -W «*vB;S*UI; В-антшмтмпя модоь M/D/I S-HfmnmwM нгамжп;

■ - *аею рюрча» • UJMC*

• М М «Л м »

Рис. 2 ДКУ, средняя задержка передачи данных

Рассмотрим характеристики ДКУ в симметричной системе М/О/1. В ней источники передают сообщения в виде пакетов постоянной длительности В. Все источники генерируют одинаковые пуассоновские потоки пакетов и суммарный поток от всех абонентов имеет интенсивность X. Характеристики способов

множественного доступа слабо зависят от распределения длин пакетов [С 18] и поэтому везде далее используется модель М/D/l вместо более сложной M/G/1.

На рис. 2 показана средняя задержка для ДКУ. Здесь W(S) - нормализованная средняя задержка пакета, выраженная в единицах длительности пакетов, S - нормализованная интенсивность: S = ХВ. Параметр дальнодействия а = т/В , где В - длительность пакета. Число источников - N. Число n = flog2 N1. Кривая при а = 0,001 достаточно близка к идеальной и практически не зависит от N; при характеристики деградируют.

Емкость канала (часть пропускной способности канала, занятая полезной передачей данных) С 0,98 при а = 0,001 для числа и с т о ч н р и а £ 0,1 С<0,5.

Таким образом, ДКУ эффективно работает на коротких сетях или же в режимах, когда борьбу за право передачи надо проводить достаточно редко.

Ускорение работы ДКУ дает применение совмещенного ДКУ (СДКУ). В СДКУ используются два подканала, в одном из которых идет обмен данными, а во втором борьба за канал. Исследование характеристик СДКУ приведено в [52].

1.1.2 Ускоренное ДКУ (УДКУ)

В этом способе для представления битов кодов приоритетов используются группы сигналов, которые при одновременном появлении в канале битов 1 и 0 позволяют определить в канале наличие более одного бита 0 и подсчитать количество битов 1. Скорость передачи сигналов в указанных группах не связана с временем прохода сигнала по каналу и может быть выбрана достаточно высокой, чтобы не влиять на время доступа. В результате процедура доступа ускоряется следующим образом. Если источник при передаче очередного разряда кода приоритета обнаруживает, что у него нет конкурентов, то он передает свои данные. Если конфликт есть и источник передал 1, то он переходит к передаче следующего разряда кода приоритета. Если же при конфликте источник передавал 0 и в канале есть 1, то он далее не передает сигналы, но подсчитывает количество находящихся в это время в канале единиц. Если конфликтовали только коды 0, то источник передает следующий разряд кола приоритета. Имея такие данные, источник обнаруживает момент, когда все источники, продолжавшие борьбу после его отключения, передадут данные. После этого он продолжит борьбу с источниками, отключившимися вместе с ним. При таком способе борьбы источникам приходится передавать значительно меньше разрядов кода приоритета. В среднем каждый источник передает не более 2,5 разрядов кода приоритета. Этот способ был развит далее в минимальном ДКУ (МДКУ).

Заметим, что родоначальником распределенных способов доступа считается Aloha (1970 г.), ставшая прообразом широко распространенной сети Ethernet. Однако способ доступа ДКУ был опубликован в печати также в 1970 г., но авторское свидетельство на ДКУ имеет приоритет от 1968 г.

Достоинства ДКУ

1. Высокая емкость канала в близкодействующих сетях.

2. Гарантированное время доступа.

3. Работа с индивидуальными динамическими приоритетами (гибкость управления).

4. Независимость характеристик сети от числа ее абонентов. Недостаток - вырождение характеристик в дальнодействующих сетях (а51).

1.1.3 Децентрализованное пространственно-временное управление

(ДПВУ)

Принцип работы ДПВУ демонстрирует рис. 3. Здесь 1 - шинный канал (кабель с отводами), 2 -подканал с направленной передачей сигналов.

1 к 1 1 / 1 к

4 1 * г ' 1 1

А1 А2 Ал

Рис. 3 Структура канала ДПВУ

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

Источник Аь желающий занять канал, следит за каналом 1 и, обнаружив в нем паузу, начинает передавать постоянный сигнал (несущую) в канал 1 и подканал 2. Через время Т после начала передачи источник проверяет наличие несущей на входе из подканала. Если сигнал есть, то источник прекращает борьбу. Иначе он прекращает передачу несущей и передает пакет данных в канал. Канал занимает единственный источник, если - время

прохождения сигнала по каналу и подканалу; ЛТ- максимальное время обнаружения паузы любым источником.

Работа изложенного алгоритма ускорена в следующем алгоритме. Источник ожидает наступления пары ^„в канале. При ее обнаружении он передает в канал и подканал несущую и через время проверяет наличие несущей на входе из подканала. Если несущей нет, то источник перестает передавать несущую в подканал и передает в канал данные. Если несущая есть, то источник ожидает ее исчезновения, исчезновения сигнала в канале и после этого прекращает передачу несущей в подканал и начинает передавать данные в канал.

Здесь ускорение доступа достигается за счет того, что возможность занятия канала определяется при исчезновении бита данных в канале в месте подключения данного источника. Емкость канала С для него: С = 1/(1+4а/Ы). Через два года после опубликования алгоритма подобный алгоритм был разработан в ЮМ [СЗ].

Ненаправленный канал в рассмотренных алгоритмах может быть заменен направленным [52]. Такой вариант был реализован в экспериментальной сети Института проблем управления и в системе управления КУРС (см. раздел 2.3.1).

1.1.4 ДПВУ с гарантированным доступом.

В рассмотренном алгоритме ДПВУ приоритет жестко задается местом подключения источника к подканалу. Задание приоритетов временем реакции на наступление паузы позволяет реализовать многоуровневые приоритеты [ 52]. Был предложен ряд таких алгоритмов.

В наиболее простом случае для п уровней приоритета вводится п времен задержки в обнаружении паузы: ^¿"'»Г+иСг^ + г^ + ДГ) Здесь Т- задержка, указанная выше для одноуровневого приоритета.

Этот способ, однако, не обеспечивает гарантированного времени доступа. Для гарантированности надо изначально запретить источникам использование уровня п = 0. Пусть источники делятся на две группы: требующие и не требующие гарантированного доступа. Первые будут начинать борьбу с и = 1, а вторые с п > 1. Если требующие гарантию доступа источники не получают доступ при п = 1, то они используют п = 0. Все источники, находящиеся на уровне п = 0, получают право передачи в порядке их подключения к линии. Так как до исчерпания заявок этих источников не возникает пауза, достаточно длительная

ДПВУ

Средняя задержкаа-1/В;8-1В; В - длительность пакета; модель МФ/1 8 - аормишшшяа интенсивность;

я - число разрядов I адресе а - нормализов. задержка I ретрансляторе

« II ».4 М 1.1 3

Рис. 4. ДПВУ Средняя задержка передачи данных

для начала передачи на других уровнях, то очередь с п - 0 не пополняется. Это гарантирует обслуживание всех срочных заявок. Емкость такого канала

С =11 (1+2л-Нх), где а = г*/В, а+а = Ъл/В, а - нормализованная задержка сигнала в ретрансляторах направленного канала. [52, стр 62]. Если положить, что а на порядок меньше длительности такта передачи данных в канале (а = 0,Ш/Ь, где Ь - длительность пакета в битах), то временные характеристики этого алгоритма для системы М/ОД имеют вид, приведенный на рис. 4

1.1.5 Алгоритмы типа "Система с бегущей волной" (СБВ) В этих алгоритмах [21, 27, 39, 43, 52, 70] источник без задержки проходящего мимо него в канале сообщения выясняет допустимость его замены своим сообщением.

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

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

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

— заменять без задержки старый адрес приемника новым.

Рис. 5. Система с бегущей волной

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

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

Этот способ имеет несколько разновидностей. В частности вариант СБВ -"кольцо со скользящей границей" (КСГ) [70] устраняет недостаток СБВ, заключающийся в том, что источники, расположенные ближе к концу линии имеют меньшую вероятность передать сообщение.

На рис. б приведено сравнение средних задержек для вариантов алгоритмов ДПВУ, СБВ и ряда других опубликованных в печати алгоритмов множественного доступа.

Рис. б. Средние задержки: CSMA-CD, жезл, ДПВУ, СБВ

СБВ позволяет проводить без задержки в канале указанные ниже способы обработки данных.

1. Логическое сложение. Пусть наличию сигнала соответствует 1, отсутствию сигнала - 0. Тогда, очевидно, выполняется 0 + 0 = 0,1 + 0 = 1,1 + 1 = 1.

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

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

Итоги исследований, изложенных в главе 1.1

1. Разработаны алгоритмы типа децентрализованного кодового управления (ДКУ). Они позволяют без наличия управляющего центра обеспечивать доступ источников в канал связи с учетом их приоритетов, выполняя операцию тах. ДКУ - детерминированный способ доступа. Он обеспечивает необходимую для систем управления гарантированность доступа. ДКУ ориентирован на канал типа "шина" или беспроводной канал.

2. Разработаны алгоритмы типа децентрализованного пространственно-временного управления (ДПВУ). Эти алгоритмы обладают меньшей гибкостью, чем ДКУ, но более просты в реализации и могут иметь большее быстродействие.

3. Разработаны децентрализованные алгоритмы типа "система с бегущей волной" (СБВ) - наиболее скоростные из двух перечисленных алгоритмов. Они обеспечивают проверку разрешения доступа без задержки проходящих в канале сообщений. СБВ позволяет проводить несколько видов обработки данных в канале без их задержки на обработку. СБВ требует использования канала с направленной передачей сигналов.

1.2 Вычисление в общем канале (ВОК)

Основные источники [45,49,52,72].

В разделе излагается способ совмещения процесса передачи данных по каналу связи и проведения вычислений над передаваемыми данными без задержки на вычисление. Этот способ, названный "Вычисление в общем канале" (ВОК), служит основой для выполнения многих групповых операций и команд. ВОК работает в каналах с направленной передачей сигналов.

1.2.1 Организация ВОК для двоичной системы счисления

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

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

Рис. 7. ВОК, общая схема

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

Операция "отрицание". Инвертируется значение х, если у = 1.

Операция "исключающее ИЛИ". Если у — 0, то х пропускается далее в канал без изменений. Если у = 1, то значениех инвертируется.

Операция "логическое И". Если у = 1, то х пропускается в канал. Еслиу = О, то вместо х далее в канал передается сигнал 0.

Операция "логическое ИЛИ". Если у = 0, то х пропускается в канал. Если у - 1, то вместо х в канал передается сигнал 1.

Счет. Каждый разряд числа обрабатывается операцией "исключающее ИЛИ". Разряды обрабатываются, начиная с младшего. Для проверки наличия переноса в старший разряд имеется время до прихода следующего разряда. Аналогично выполняется сложение и вычитание в дополнительном коде [45,52].

Умножение ВОК [49]. Требуется получить произведение M=XY, двоичное число X поступает из линии, а двоичное число Г- от абонента. Для выполнения умножения используем два включенных один за другим переключателя ВОК. Покажем их работу на примере. Обычное умножение выполняется так:

Здесь для вычисления М1 надо выполнить логическое умножение Х/лу» и произвести сложение с цифрой, которая вычислена до прихода л* Например, Мз=ХзУо + (хр! + хф>2). Выражение в скобках вычисляется до прихода хг, так как X! и Хд поступили из канала к абоненту раньше. Причем в каждом такте произ-

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

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

Операция max (x,y). Требуется сравнить значения х и у. Для каждого разряда выполняется операция "логическое ИЛИ" и если у = 0 и х = 1, то х > у. Иначе надо проверять остальные разряда: операндов. Разряды обрабатываются, начиная со старшего разряда.

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

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

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

Для выполнения приведенных выше операций ВОК переключатель сигналов на рис. 8а получает сигналы управления от процессора абонента.

Для передачи значения двоичного разряда используются две линии "1" и "О". Значение разряда, равное 1, представлено сигналом в линии 1.

Рис. 8. ВОК, действие переключателей линий канала

Значите 0 - сигналом в линии 0. Сигнал всегда присутствует в одной из линий. Если разряд не передается, то сигналы в линиях отсутствуют. Операнд у переключает сигналы в линиях для выполнения указанных выше операций. Рис. 8Ь - значение х передается без изменения. Рис. 8с соответствует выполнению инверсии. Рис. 8d - превращение значения х в 1. Рис. 8е - х переводится в 0. Все необходимые переключения выполняются до прихода значения х и не вносят задержку в передачу сигнала через переключатель сигналов.

Второй способ реализации ВОК использует одну линию. Инверсия здесь осуществляется путем вращения плоскости поляризации сигнала.

Пусть сигнал 0 поляризован в некоторой плоскости. Сигнал 1 получается из сигнала 0 вращением плоскости поляризации сигнала 0 на угол 6 = 180°. Если продолжить поворот на 9, то из сигнала 1 вновь получим сигнал 0 и т.д. В общем случае угол 0 = Зб0о/п, где п - четное число и делитель числа 360.

с d

Рис. 9. Вращение плоскости поляризации

На рис. 9 показано выполнение таким способом тех же операций, что и на рис. 8. На рис. 9а показано выполнение инверсии. Сигнал проходит через узел вращения плоскости поляризации на угол в. На рис. 9b прохождение сигнала х запрещено и вместо него передается в линию сигнал 1. На рис. 9с прохождение сигнала х запрещено и вместо него передается в линию сигнал 0. На рис. 9d сигнал х походит без изменения.

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

В 2004 г. в фирме Intel создан кремниевый оптический модулятор со скоростью модуляции свыше 1 Ггц [С22, С23]. На его основе могут быть созданы оба рассмотренных логических элемента ВОК.

1.2.2 ВОК-сложение для системы счисления с основанием m > 2

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

Рассмотрим ВОК-сложение в системе счисления с основанием m > 2 для канала, содержащего m линий передачи сигналов, пронумерованных от 0 по m-1.

Линия с номером, соответствующим значению разряда числа, содержит 1. Остальные линии содержат 0. Для цифры 0 единица передается по линии 0.

Для выполнения сложения в месте подключения абонента в канал включается переключатель линий. Переключатель выполняет сложение двух т-разрядных цифр и перенос в следующий старший разряд. На рис. 10 показана организация т-ичного переключателя. Здесь показано переключение только одной линии к, остальные линии, передающие код цифры, переключаются аналогично. В переключатель входит m входных линий и из него выходит m выходных линий. Переключатель содержит m дополнительных линий, объединенных на входе триггера Тг. Кроме этого каждая дополнительная линия подключается к одноименной выходной линии. В зависимости от значения хранящегося в процессоре абонента, переключатель соединяет входную линию к с выходной линии со сдвигом в сторону увеличения номера выходной линии на величину уь Так делается одновременно для всех входных линий.

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

Вычитание в таком устройстве заменяется сложением, при котором ко всем отрицательным числам прибавляется константа "а", превращающая их в положительные числа. После проведения сложения внутри процессоров — потребителей результата должно быть вычтено число па, где n - количество отрицательных чисел, участвующих в операции. Необходимое значение для "а" быстро определяется ГО max, a п определяет операция "счет", подсчитывающая число отрицательных операндов.

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

линия 0

Рис. 10. Переключатель на m линий

Отметим следующие результаты, полученные при разработке ВОК.

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

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

В ряде случаев достаточно гибкую обработку данных без задержки выполняют алгоритмы СБВ.

1.2.3 Оценка эффективности ВОК в вычислительных задачах

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

Схема сдваивания. Одной из наиболее эффективных схем выполнения ассоциативных операций на мультипроцессорных компьютерах является схема сдваивания [С2]. По этой схеме вычисление суммы mi + ni2 + П1з + гщ + mj + m« + m7 + mg

выполняется зя тпи сттетлптттих тттягя

Шаг 1: (mi + m2); (ш3 + пц); (ш5 + m«); (т7 + ш8) Шаг 2: ((mi + т2) + (т3 + пм)); ((т3+т«) + (т7 + mg)) Шаг 3: ((mi + т2) + (т3 + тО) + ((т5 + те) (т7 + т8»

Время выполнения такой операции для п слагаемых h = Гlogj nl (tn + 'сд)» где t„ - время пересылки промежуточного результата, fra— время сложения. При этом предполагается, что средства обмена данными допускают одновременное выполнение необходимых пересылок. Если традиционное устройство выполняет параллельную обработку данных при последовательной их передаче, то временем сложения можно пренебречь.

Время выполнения этой операции с применением ВОК-сложения равно f„. Видно существенное преимущество ВОК. Кроме этого средства связи при использовании ВОК имеют простую организацию.

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

Аргументы операции сложения представим в следующем виде, использующем систему счисления с основанием т. По т линиям будем передавать цифру со значением от 0 до ш - 1, представленную как показано в разделе 1.2.2. Для представления числа N = 2к потребуется передать г цифр в системе с основанием m:

= т, отсюда г = k/log-pi.

За г временных тактов с помощью ВОК будет выполнено сложение любого количества чисел разрядности г.

По схеме сдваивания на сложение п чисел потребуется время

и =2 \log2 и! 'п-

ВОК будет иметь преимущество перед схемой сдваивания, когда превысит число тактов г.

При наиболее часто применяемой разрядности к = 32, совпадающей с т, указанный вариант ВОК получает преимущество перед схемой сдваивания при N>16.

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

Вычисление определенного интеграла. Воспользуемся формулой прямоугольника:

}/«<&« £л«+<*-1)—1-—

; ы п п

Пусть каждый процессор Р1 содержит у себя значение п п

тогда за один проход по каналу получается искомое приближение и поэтому время выполнения операции равно /„. При выполнении этой операции на п-процессорной системе и использовании схемы сдваивания получаем указанное выше время ^ = \log2 и! (Гп + /«).

Вычисление скалярного произведения двух векторов. Пусть даны векторы компоненты которых хранятся в процессоре р,. С использованием ВОК операция выполняется за два шага по формуле в процессорах получаем парные произведения компонент, а в канале проводим их суммирование. Время вычисления равно 1/мх +

где ¡ум, - время умножения в процессоре. Та же операция на п-процессорной системе выполняется за время ^ = + \logi п\ (Гп + /сд).

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

В работах [45,49, 52] приведен ряд широко применяемых вычислительных алгоритмов, для которых также достигается существенное ускорите вычислений. В частности приведены следующие результаты.

Решение системы линейных уравнении методом последовательных приближений. При использовании в вычислительной системе п процессоров одна итерация выполняется за (Зп + 2) шага [С20]. При использовании ВОК итерация выполняется за (2п + 2) шага. При совмещении операции ВОК-сложения с умножением в процессорах число шагов уменьшается до п + 2.

Обращение матриц методом пополнения. В [С20] показано, что для выполнения к- ой итерации обращения матрицы на п2 процессорах системы требуется И (к) = б + 1о$2 (к -1) шагов. Применение ВОК дает И(к)= 7.

В работе [С 17], выполненной в Институте прикладной математики РАН, была проанализирована организация вычисления задач математической физики

на ЭВМ типа Cray и выделен типичный фрагмент вычислений, представляющий наибольшую трудоемкость. В [49] показан способ существенного ускорения вычисления этого фрагмента с применением ВОК.

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

Попытки избавиться от многократных пересылок распределенных данных в центральный процессор приводят, например, к структуре, в которой модули распределенной памяти снабжаются элементарными процессорами, объединенными в цепочку каналом связи [С24]. Простая предварительная обработка (например, суммирование) проводится в этой цепочке процессоров, а ее результат направляется в центральный процессор. Так как здесь ВОК не используется, то задержки на вычисление получаются большими.

В заключение сделаем ДВА ЗАМЕЧАНИЯ.

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

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

Итоги исследований, изложенных в главе 1.2

1. Существует устоявшееся мнение, что обмен дашшми между процессорами - это неизбежные "накладные расходы", ограничивающие производительность мультипроцессорных систем [С4, С5]. Однако, здесь показано, что ВОК позволяет создавать "полезные" обмены данными и выполняет широкий спектр операций над передаваемыми в канале данными без задержки их на обработку. Это ведет к ускорению выполнения вычислительных и управляющих алгоритмов.

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

1.3 Структуры связи для групповых операций

Основные источники [39,52,80,81, 84].

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

Фрактальные структуры связей строятся из фрактальных линий, которые здесь названы фрактальными линиями Серпинского (флС), так как они имеют структуру фрактальных кривых Серпинского [Сб].

Из флС создается фрактальный канал Серпинского (фкС). Он может состоять из нескольких флС с включенными в них средствами проведения вычислений.

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

1.3.1 Структура связей на основе плоских фрактальных линии

Фрактальные линии связи, как и фрактальные кривые Серпинского строятся итерациями.

На рис. 11 (а ё) приведены флС, полученные в результате последовательности итераций 0, 1, 2, 3 с применением L-системы Лиденмауэра [С6] (см. ниже). Отрезки линии - ребра, соединяющие узлы. В каждой итерации к флС, построенной в предыдущей итерации, добавляются ответвления. Для выполнения

« б « 1 □О

Рис. 11. Построение линий Серпинского

итерации 1 (рис. 1 1Ь) в флС, полученной в итерации 0 (рис. Па), каждое го четырех ребер разделяется на три части. Средняя часть ребра удаляется и заменяется ответвлением - квадратом итерации 0 с удаленным одним ребром. Для получения терации 2 (рис. 11с) в линии итерации 1 выделяются 4 ребра, которые удаляются и в места разрыва включаются линии итерации 1 и т.д. Размер ребер в каждой итерации не зависит от их размеров в других итерациях. Точное определение мест разрыва и процедура построения каждой итерации задаются L-системой следующим способом.

L-система состоит из алфавита, строки символов алфавита (аксиомы), порождающих правил и двух параметров а и 9, требуемых для построения линии Серпинского.

Алфавит состоит из четырех символов — F, X, +, -

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

X - служебный символ, используется только указанным ниже правилом new X.

' + ' определяет поворот ребра на угол 9 от направления предшествующего ребра

'-' определяет поворот ребра на угол -9 от направления предшествующего ребра.

Значение 9 выбирается произвольно.

Начальное направление движения для F определяет а. Значение а также выбирается произвольно.

Здесь а = 0 и 0 = тс/2.

Аксиома имеет вид:

axiom = F+XF+F+XF.

Порождающие правила имеют вид:

newF=F,

new X = XF-F+F-XF+F+XF-F+F-X

Символы X и F аксиомы заменяются на строки символов, указанные в правой части правил new F и new X. Итерационное применение правил приводит к построению указанных выше флС.

В каждой новой итерации появляется центральная часть - линия итерации О и четыре ответвления (квадранты) - линии предыдущей итерации.

В фкС к узлам подключается абонентская аппаратура (абоненты). На рис. 11а они обозначены жирными точками Количество абонентов и узлы, к которым они подключены, определяются требованиями конкретной реализации. Если к узлу не подключен абонент, то такой узел - просто изгиб линии фкС, позволяющий расположить фкС требуемым образом на плоскости. Каждый абонент имеет в фкС переключатель. Узлы фкС соединены дополнительными линиями связи, показанными на рис.12 пунктиром и штрих-пунктиром Пунктирные линии введены для разбиения системы на независимо функционирующие участки. Замыкая пунктирную линию, переключатель отключает связанное с ней ответвление от остальной части фкС. Система связи при этом разбивается на участки, в которых допускается независимый обмен данными. В оставшейся части системы отключенный участок заменяет соответствующая ему штрих-пунктирная линия.

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

с!

Чг

I

Рис. 12. Способ разделения фкС на изолированные участки

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

На рис. 12 показан фкС, полученный на втором шаге итерации. Место начала построения канала отмечено стрелкой. Движение осуществляется против часовой стрелки.

В работе дан формальный способ определения мест подключения указанных на рис. 12 дополнительных линий. Он сводится к следующему.

На фкС имеются внешние П-образные выступы. Начальный и конечный узел выступов целесообразно объединять вспомогательными линиями. П-образному выступу кривой и только ему соответствует в Ь-записи последовательность выбора углов в ¡1 = - + +. Эта последовательность позволяет найти узлы, которые надо соединить вспомогательными линиями.

Вспомогательными линиями целесообразно также объединять узлы, располо-жеииые на входе и выходе каждого нового квадранта. Входу и выходу из квадранта и только им в L-записи соответствует последовательность 0 Ь = Н---.

Для введения пунктирных и штрих-пунктирных линий надо для П-образного выступа в последовательности ребер, соответствующей последовательности 1) - - + +, соединять переключателем начало ребра "-" с концом второго ребра "+". Для объединения входа и выхода в квадрант необходимо в 12 соединить узел на стыке 0 = + —, расположенный на входе в квадрант, с узлом на стыке 0 = — , расположенным на выходе из этого квадранта. Дополнительно требуется установить, что соединяемые узлы находятся в непосредственной близости. Это достигается двумя путями - определением координат узлов на плоскости, либо отслеживанием "истории" построения фкС с учетом того, что только для квадранта не имеющего ответвлений характерна последовательность углов в

Последовательность Это позволяет

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

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

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

1.3.2 Многослойный канал Серпинского

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

Линия 1

Линия 2

Рис. 13. Объединение группы фрактальных каналов

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

1.3.3 Шинные линии дальней связи Если обратиться к рис. 11, то видны две особенности структуры обмена данными. Любые две вершины можно соединить двумя линиями связи, которые не будут пересекаться как с фкС, так и друг с другом. Так как фкС делит плоскость на внутреннюю часть, расположенную внутри этой линии, и внешнюю по отношению к ней, то одну из указанных линий надо проложить во внутренней части плоскости, а другую - во внешней. Заполним внутреннюю часть

Рис. 14. Объединение фрактальных линий с шинами

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

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

На рис. 14 показана часть внутренних и внешних шинных линий. Переключатели позволяют разделить шинные линии на параллельно работающие части.

Так сочетаются принципиально разные способы связи: направленная передача сообщений по цепочке от узла к узлу фкС и ненаправленная передача по шине.

1.3.4 Беспроводные связи.

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

устройств сигналом и, поэтому, нельзя эффективно реализовать групповые арифметические операции. Но групповые операции, не использующие промежуточные результаты, выполнимы с ненаправленными сигналами даже быстрее, чем с направленными сигналами. Это операции логическое И, логическое ИЛИ, max, min. Будем двоичный 0 представлять парой сигналов 01, а двоичную 1 - парой сигналов 10. Если группа источников передает одновременно сигналы, то в результате наложения сигналов возможно появление комбинации 11. Для операции логическое ИЛИ ее надо интерпретировать как 1. Для операции логическое И - как 0. Для операций max и min все источники должны одноименные разряды также передавать одновременно. При этом источник, передавший 0 и обнаруживший, что есть передача единицы, должен прекратить выполнение операции.

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

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

1.3.5 Канал "скрепка", неоднородные системы

В приложениях, приведенных в части 2 доклада, используются также структуры связи, которые уже рассмотрены в главах 1.1 и 1.2 доклада: две линии со встречным направлением передачи сигналов, кольцо. Весьма эффективен канал "скрепка" [52], разработанный специально для использования с групповыми операциями (рис 15). В скрепке источник посылает сообщение в линию 1, оно

Рис.15. Скрепка

переходит в линию 2 и затем в линию 3. Используя линии 1 и 2, все абоненты вносят изменения в сообщение. Наблюдая за линией 3, все абоненты видят результат внесенных изменений.

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

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

В прошлые годы в распределенных системах и локальных сетях широко использовался общий для всех абонентов канал связи (с направленной или ненаправленной передачей сигналов).

Рис. 16. Операции ВОК + серверы

Теперь в таких системах наиболее распространено подключение удаленных абонентов к центральному оборудованию (серверу). Центр может быть создан с применением излагаемых в докладе решений, и поддерживать групповые операции, включая ВОК.

На рис. 16 показан вариант такой структуры. В двух центрах использованы фкС, которые могут быть дополнены другими структурами коммутации. Находящиеся в центрах фкС имеют разрыв в ребре и две линии объединяют фкС центров в единую систему. Такое соединение позволяет использовать ВОК.

Итоги исследований, изложенных в главе 1.3

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

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

1.4 Групповые команды и распределенные программы.

Основные источники [39,72,82,85].

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

Групповые команды (ПС) строятся на основе групповых операций. ГС одинаково работают как с близко расположенными, так и с удаленными группами абонентов.

В данном разделе рассмотрены структура и способы выполнения ПС распределенной программы. ГС передаются по каналам связи совокупностью битов, называемой пакетом.

Структура наиболее сложной ПС переменной длины показана на рис. 17.

код операции! аргументы 11] результат^!! результат |0| нет результата |

Рис. 17. Групповая команда переменной длины

В пакете ПС имеется заголовок, который полностью определяет реакцию абонентов на поступающую к ним ПС. Те абоненты, которые не способны его расшифровать, не реагируют на ПС. Для остальных заголовок определяет вид требуемых от абонентов действий и адреса или имена приемников результата. Остальная часть ПС определяется видом групповой операции, указанной в заголовке. Групповая команда определяет способ обработки операндов, место расположения данных, их значение, место расположения результата. Помимо этого может быть задан способ завершения операции, формирования и передачи квитанции источнику и способ передачи прав мастера другим абонептам. Если ПС работает с фиксированным количеством операндов, то размер ПС фиксирован. При заранее неопределенной длине пакета, которая зависит от числа участвующих в операции абонентов, необходимы ПС переменной длины. Нужны также ПС - инициаторы порождения другими абонентами последовательности ПС в пределах одного сеанса связи [72,82,86].

Введем нотацию для представления ГС. ГС в пакете представлена блоком вида <С: код операции ПС.классификатор о...о>>. Код операции определяет действия абонентов. Классификатор может отсутствовать. При его наличии код операции определяет класс операции, а классификатор задает конкретную операцию класса. В блоке ПС задается цепочка блоков операндов и блоков результата операции, заключенных в ограничители Процессор абонента, получив из ПС код операции, выполняет его в виде последовательности обычных или групповых операций.

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

Блок операнда имеет вид <Ак имя.имя.....имя==значение>, ¡=0,1. Здесь

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

1) = значение;

2) имя.имя.....имя;

3) имя.имя.....имя = значение.

Первый вариант - значение применяется в качестве операнда в операции, указанной в ГК. Второй вариант- значение операнда извлекается по указанному в ГК имени. Третий вариант - в зависимости от вида ГК имеются два подва-рианта 3.1 и 3.2. В 3.1 как и в варианте 1 значение применяется в качестве операнда, а имя уточняет операцию, если она допускает разные действия для разных типов операндов. В подварианте 3.2 в зависимости от вида ГК либо значение направляется по указанному адресу, либо оно сравнивается со значением, хранящимся по указанному адресу, например, при выполнении ветвления в распределенной программе. Разрешается изменять значение в блоке операнда, если это не ведет к задержке пакета с ГК.

В ГК допускается применение маскирования, которое обозначается буквой т. Маскируются компоненты идентификатора и отдельные разряды в значении операнда. Замаскированный объект не определен, т.е. принимает любое значение из допустимой для данного объекта области значений. Маскирование компоненты идентификатора означает, что задается обращение к группе объектов.

Блок результата возможен трех видов: <Яй: имя.имя . . . имя >, <Яе1:

имя.имя.....имя = > или <гк£ >. Здесь 1 и цепочка имен имеют такой же

смысл, как в операнде. В первом случае результат должен быть помещен по указанному адресу вне ГК. Во втором случае единственное или общее для всех членов группы значение результата помещается в блок результата ГК под указанным именем. В третьем случае имя не указывается, его определяет источник результата, и результат вычисления должен быть помещен в блок результата ГК. В блоке к принимает значение 0 или 1. При к=0 блок свободен для помещения в него результата вычисления. В зависимости от вида ГК этот результат снабжается именем или нет. Чтобы поместить результат процессор без задержки переводит к в блоке результата в состояние 1, означающее, что блок занят. При этом он также без задержки проверяет, не был ли блок уже занят. Если блок занят, то передача результата запрещена. После передачи результата процессор добавляет новый, свободный блок результата с к = 0. Последнее необходимо для групповых команд переменной длины,-которые получают от других абонентов неопределенное количество

если блок прочитан приемником. Иначе t равно 0. Параметр t используется в ряде ПС.

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

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

Последовательность передаваемых по каналу связи ПС и есть распределенная программа.

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

шаг 1

Г

О

шаг 2

п х

лучший

шагЗ

Л А А А I

/

новый мастер

Рис. 18. Ветвление в распределенной программе (новый мастер)

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

1 I I

мястер

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

Третий тип ветвления: периодически (или постоянно с использованием отдельного канала связи) лидер предоставляет право отнять у него лидерство другим абонентам с учетом их приоритетов.

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

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

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

- последовательная обработка многими абонентами результата, находящегося в пакете ПС;

- отбор данных из пакета ПС многими абонентами;

- загрузка в пакет ПС результатов работы многих абонентов;

- работа с пакетом заранее неизвестной длины;

- маскирование разрядов кода;

- смена лидера, имеющего право передачи команд распределенной программы.

Приведем в качестве примера ПС "максимум" - типичную групповую команду, использующую ВОК.

<С: "максимум"<АО: имя.имя . . . имя> <АО:имя.имя . . . .имя=0><ЯеЬ>. Если абонент имеет нулевое значение флага, указанного в первом блоке операнда, то ВОК определяет, что больше, значение в блоке результата Я в пакете ПС или значение операнда в абоненте по адресу, указанному во втором блоке операнда. Если операнд в абоненте больше, то операнд помещается в блок результата, заменяя его предыдущее содержимое.

Эта ПС в частности позволяет получить малое время доступа к каналу связи при высокой интенсивности заявок. Если в канале нет сигналов (пауза) и поступает заявка на доступ, то применяется ДКУ. Каждый сеанс связи источник завершает посылкой ПС "максимум". После обхода этой командой всех абонен-

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

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

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

Пусть требуется провести при помощи ВОК операцию алгебраического сложения без перевода отрицательных чисел в дополнительный код. Для этого в ГК введем два блока результата. В одном блоке (Я*) формируется сумма положительных операндов. Во втором блоке (Я") формируется сумма модулей отрицательных операндов. Окончательный результат формируется из содержимого этих блоков внутренними средствами процессора.

Метод позволяет в пределах одной ГК выполнять сложные вычисления. Так в пределах одной команды без задержки вычисляется значений двух полиномов с тем, чтобы в процессоре получить часто требуемое отношение этих значений.

Покажем пример такого вычисления.

Пусть в ГК содержится следующая информация: «Найти отношение двух полиномов?<5схНх>9х<Нх><|)2<К+>,,)1<Я>|,,1<К+>ф2

<к>,2>.

Предварительно с помощью флагов <р1 = 1 и ф2 = 1 выделены две группы процессоров, удовлетворяющих некоторым условиям иср2.

Рассмотрим операции с компонентами, имеющими индекс Источник команды посылает в ней следующие данные: значение х, значение <Кх>ф1 = 1 И в зависимости от знака числа

Первый процессор с находящийся на пути перемещения ГК, делает

следующее:

— При помощи ВОК у м н жа и результат помещает в

Теперь <Ях>,Р1 = х.

— Внутри процессора выполняется умножение х на хранящееся в процессоре значение а1. Умножение должно быть завершено до прихода из линии блоков <К.+><р1 и

— При помощи ВОК в зависимости от знака а)Х это число или его модуль прибавляется соответственно к <Я+>,1 или к <Я">Ф1.

Следующий процессор с ср1 = 1 умножит <х> на <Ях>ф1 и теперь значение <Кх>,р1 = х*. Далее в этом процессоре будет вычислено агХг и при помощи ВОК прибавлено к <11+>ф1 или к <Ю>Ф1 и т.д.

После обхода ГК всех процессоров, имеющих <р1 = 1, в двух блоках -<11+>ф1 и <К"><(11 будут находиться данные, достаточные для вычисления в любом процессоре значения суммы

Совершенно аналогично на группе процессоров с <р2 = 1 будет вычислен другой полином Ь0 + ЬгХ2 + ... + Ьгах„,. Наконец, в процессоре, получившем

выполняется деление.

Здесь целесообразно сделать замечание по поводу сложившейся практики оценки производительности систем обработки данных. Имеются публикации, где даются верхние оценки скорости выполнения задач на многопроцессорных системах. Полученные оценки предлагаются как универсальные, однако в них не учитывается возможность использования средств передачи для выполнения вычислений. Это приводит к занижению оценок. Например, в часто цитируемой статье [С25] отмечено, что ряд операций, в частности вычисление х", плохо распараллеливается и требует многих циклов работы системы. Такое умножение выполняется аналогично сдваиванию, приведенному в разделе 1.2.3. Но выше показано, что х" с помощью ВОК вычисляется за время обхода всех процессоров единственной групповой командой.

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

В публикациях [82,86] приведены компактные распределенные программы с групповыми командами, выполняющие сложную обработку данных.

Итоги исследований, изложенных в главе 1.4

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

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

3. Групповые команды и распределенные программы служат средством повышения скорости обработки данных в распределенной системе.

Основные результаты, полученные в части 1

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

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

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

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

- в канале операнд замещается на результат его преобразования;

— передача управления предваряется быстрым процессом борьбы между претендентами на получения права взять на себя выполнение программы.

Часть 2. Работа групповых операций в приложениях.

В этой части рассмотрено применение ГО и ГК в широком спектре приложений и проведена ориентированная на эти приложения детализация ГК. В каждом из таких приложений использование ГО существенно улучшает его характеристики и демонстрирует способы создания специализированных технических средств поддержки приложения. Приложения разделены на три группы. В главе 2.1 показано применение ГО в задачах управления ресурсами систем жесткого реального времени. В главе 2.2 ГО применены в приложениях с интенсивным взаимодействием распределенных данных. В главе 2.3 приведены технические системы с групповыми операциями, реализованные с участием автора настоящей работы.

2.1 Групповые операции в задачах управления ресурсами распределенных систем жесткого реального времени

2.1.1. Гарантия доставки широковещательных и групповых сообщений

Основные источники [52,55,72].

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

при этом, во-первых, указанные действия должны выполняться в пределах одного неделимого сеанса, так как иначе могут появиться другие заявки, усложняющие ситуацию. Во-вторых, должна быть уверенность в том, что все адресаты получили сообщение. Еще один вопрос - проверка неискаженной доставки сообщения, будет рассмотрен ниже. Необходимую неделимость проще всего обеспечивает распределенная программа, которая начинается с команды запроса сеанса группового взаимодействия и заканчивается командой завершения сеанса. Между ними с временной задержкой, достаточной для решения абонентами вопроса о взаимодействии, посылается команда сбора ответов от абонентов. Эта команда содержит два блока результата. В первый из них каждый получивший адресованную ему команду абонент прибавляет единицу, используя ВОК-сложение. Во второй блок прибавляют единицу абоненты, согласившиеся на запрашиваемое взаимодействие. Анализ содержимого этих блоков позволяет решить задачу гарантированной доставки сообщений. Одновременно обеспечивается высокая скорость определения реакции абонентов на запрос. Другой способ решения рассмотренной задачи обеспечивает применение СБВ.

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

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

2.1.2 Групповые операции в канальных протоколах систем ЖРВ

Основные источники [55,72].

Протокол канального уровня в значительной степени определяет скорость реакции системы устройств, объединенных сетью, помехоустойчивость сети и другие важные параметры. Групповые операции позволяют создать протоколы канального уровня с хорошими временными и надежностными показателями. Рассмотрим общую схему канального протокола с групповыми операциями. Главными в ней являются вопросы форматного оформления, запуска, выполнения ГО, завершения и контроля правильности выполнения групповых операций. Будем считать, что приемники посылают источнику квитанцию в том же сеансе связи, который содержит сообщение источника. Во время сеанса каналом владеет один источник (мастер), который передает ГО в составе активного пакета (интеракции), содержащего данные, в общем случае формируемые более чем одним источником. Такой пакет является групповой командой (ГК). Как указано в разделе 1.4, ГК содержит заголовок, который полностью определяет реакцию абонентов на поступающую к ним ГК. Он определяет вид требуемых от абонентов действий и адреса или имена приемников результата. Остальная часть ГК определяется видом групповой операции, указанной в заголовке.

Основные функции ПС в рассматриваемых канальных протоколах следующие.

1. Детерминированное управление доступом абонентов к средствам обмена данными.

2. Быстрая проверка источником сообщения работоспособности отдельного приемника или группы приемников.

3. Быстрый сбор сведений о состоянии ресурсов системы с применением ВОК.

Характерный пример применения ГК в протоколе канального уровня для систем управления (систем ЖРВ) - использование ГК типа "СБОР". В этой ГК абоненты формируют результат их совместной деятельности и помещают его в пакет ГК в область хранения результатов ГК. Существуют два основных вида получения результата. Первый - абоненты используют ВОК и формирует единый для всех абонентов общий результат, например сумму чисел, хранящихся у абонентов. Второй - в блок результата пакета абоненты помещают свои результаты независимо друг от друга. Количество этих результатов заранее неизвестно и такие ГК не имеют фиксированной длины и завершаются признаком конца команды. Результаты ГК, находящиеся в пакете, становятся доступными всем абонентам системы.

Вариант канального протокола, использующего групповые операции, был применен в АСУ ТП КУРС, рассмотренной в разделе 2.3.

2.1.3 Групповые операции в распределенных операционных

системах

Основные источники [53,56,57,62,63].

В разделе рассмотрены механизмы распределенной операционной системы (РОС) жесткого реального времени, использующей групповые операции. Эти механизмы легли в основу РОС, разработанной для системы управления технологическими процессами КУРС, которая описана в разделе 2.3.

2.1.3.1 Снижение несбалансированности нагрузки абонентов.

Задача заключается в сглаживании неравномерности нагрузки на абонентов. Пусть объединяющий абонентов канал связи имеет вид скрепки (раздел 1.3.5). Пусть также имеется заранее неизвестное число N работающих абонентов. У абонента с номером 1 есть очередь заданий, создающая нагрузку О,. Алгоритм начинает работать, когда один из абонентов А, обнаруживает, что превышается предельная для этого абонента нагрузка и возможна потеря заявок. Алгоритм состоит из следующих групповых команд.

1. Абонент Аг занимает канал и передает в канал групповую команду вычисления средней нагрузки в системе М и величин Д и Я/, определенных ниже.

При помощи ВОК-сложения в линии формируется пара величин- суммарная нагрузка Эти величины все абоненты получают из линии 3 скрепки.

Параллельно, не обращаясь к линии, абоненты выполняют следующие действия.

- Каждый абонент вычисляет среднюю нагрузку М = ЬИУ.!.

- Каждый абонент, у которого вычисляет (абонент - донор).

- Каждый абонент, у которого вычисляет (абонент - акцептор).

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

- В команде каждый абонент с Л/ > 0 из первого по порядку члена Dj■Ф■ О списка Б без задержки вычитает свое значени формируя в команде новое Т)}

Если старое значение то акцепторам разрешено передать доно-

ру часть своей нагрузки. Акцептор с сможет передать донору весь свой

избыток нагрузки. Иначе будет передана часть избытка нагрузки

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

Если то алгоритм полностью балансирует нагрузку.

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

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

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

2.1.3.2. Устранение конфликтов на стороне приемника

Если к некоторым донорам одновременно обратятся за ресурсом несколько абонентов, то возникнет конфликт на стороне приемника. Конфликты устранятся следующим способом. Каждый Ц, снабжается счетчиком, который с помощью ВОК увеличивается на 1 при использовании Dj акцептором. Значение счетчика используется для разделения всех обращений к приемнику на временные такты, в каждом из которых конфликт отсутствует.

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

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

кого имени нет, то источник помещает в команду имя приемника и 1 в качестве номера своего запроса. Если же имя приемника есть в команде, то источник, используя ВОК-сложеиие, увеличивает номер запроса к этому приемнику на 1. После обхода командой всех источников, все они будут знать порядковый номер своего запроса. Этот порядок и определяет распределение во времени обращений к приемникам, исключающее конфликты. Альтернативой такому решению является использование ДКУ.

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

Рйс. 19. Обновление многих копий распределенной общей памяти (КРОП)

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

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

рый каждый держатель прибавляет по 1. Если после обхода командой всех абонентов полученная сумма совпадает с заранее известным числом держателей, КРОП, то разрешено обновление КРОП. В противном случае после разрешенного числа попыток обновления начинается процедура проверки работоспособности абонентов. Для корректности процедуры подключение нового держателя КРОП и его отключение должны регистрироваться в системе.

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

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

2.1.3.4 Взаимное распределенное программирование (РПг) Этот механизм был разработан для использования в АСУТП с высокоскоростными связями и абонентами, имеющими небольшой объем запоминающих устройств.

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

Рис. 20. Взаимное распределенное программирование (РПг)

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

Групповые команды здесь, во-первых, позволяют получать квитанцию в пределах одного неделимого сеанса Во-вторых, как и в случае РОП работу серверу

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

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

2.1.3.5 Диагностика и восстановление работоспособности системы, обнаружение искаженных сообщений

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

Обнаружение вышедших из строя абонентских устройств

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

Скользящее резервирование

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

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

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

Обнаружение искаженных сообщений и команд

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

2.1.3.6 Групповые операции для управления порядком обслуживания в распределенных системах

Основные источники [8, 9,16,17].

Задача состоит в следующем. Имеется одноканальная система обслуживания с прерыванием (с абсолютными приоритетами обслуживания), в которой моменты прихода в систему любой заявки и продолжительность ее полного обслуживания не зависят от порядка обслуживания. Заявки от задач, поступающие к абонентам системы разбиты на N групп. Каждой группе заявок 1 (1 = 1 ... К) присвоен приоритетный параметр и,. Дисциплина обслуживания описывается 1М-мерным вектором й = О1!... и^). Заявки группы 1 имеют приоритет по отношению к заявкам группы если и, < г^. Т.е. приоритет увеличивается при уменьшении приоритетного параметра. Заявки групп, имеющие одинаковые значения приоритетных параметров, обслуживаются в порядке поступления. Приоритет заявки не меняется до конца ее обслуживания.

Обслуживание характеризуется критерием 0, определяющим качество обслуживания по отношению к каждой группе заявок. При заданной дисциплине обслуживания критерий © определяет действительные величины 61(0),..., 6к(а) - характеристики обслуживания заявок. Существуют внешние ограничения Ф1 ... , Ф№ определяющие максимально допустимые значения 8,(0).

допустимая при заданных характеристиках дисциплина обслуживания.

Ограничения могут быть заданы для нескольких критериев ©1, ©г, ©г одновременно.

Характеристика монотонна, если при уменьшении и,юа значение О*,(О) не увеличивается, а значения 0к,(А) не уменьшаются. Т.е. попытка

улучшить обслуживание заявок одного абонента не улучшает обслуживание

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

Требуется найти допустимую дисциплину обслуживания и*.

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

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

Процесс простейшего спуска состоит из следующих шагов.

1. Определяется абонент ш', для заявок которого на предыдущем шаге процесса не выполняется, по крайней мере, одно из ограничений 0:

ект<й')>Фт'(15к<г).

2. Дисциплина обслуживания п' заменяется дисциплиной обслуживания О", определяемой соотношениями:

и т = и'т (т = 1,2,..., И; ш т'), и"т.=и"т.-1 •

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

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

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

Момент времени завершения переходного процесса определяется следующим условием [9]. Пусть корректировка приоритета осуществлена для группы заявок 1. В системе не должно остаться заявок, поступивших в систему до момента корректировки приоритета заявки из группы 1, и принадлежащих следующим группам заявок:

-группе 1;

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

Введем флаг Р, который имеет значение 1, если абонент имеет заявки из приведенных двух групп, и значение 0 если таких заявок нет.

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

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

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

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

Итоги исследований, изложенных в главе 2.1

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

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

- быстрое обеспечение гарантированности доставки широковещательного и группового сообщений;

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

- быстрое распределение копий в распределенной общей памяти;

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

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

2.2 Приложения с интенсивным взаимодействием распределенных

данных

2.2.1 Клеточные автоматы с групповыми операциями и дальними связями

Основные источники [82,85, 86].

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

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

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

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

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

Для организации связей в КА-ДС использованы фрактальные каналы Сер-пинского (фкС), рассмотренные выше в разделе 1.3. Клетки КА-ДС расположены в узлах решетки, заполняющей квадрат на плоскости. На параллельной ей плоскости размещен фкС.

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

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

По фкС осуществляется направленная передача сигналов. Однако, в разделе 1.3 показано, что дополнительно к фкС можно добавить две линии с ненаправленной передачей сигналов. Эти линии подключаются ко всем узлам, что дополнительно увеличивает пропускную способность связей в КА-ДС. Такова общая структура связей КА-ДС.

Для осуществления взаимодействия клеток в КА-ДС применяются групповые команды (ГК), что позволяет в пределах одной неделимой команды получить результат взаимодействия многих клеток КА-ДС. Как показано в части 1, время получения результата практически не зависит от количества клеток. Последовательность ГК является распределенной программой, которая управляет работой КА-ДС.

Возможны реализации КА-ДС, где нельзя использовать проводные связи, подобные фкС. Например, распределенные КА-ДС с мобильными клетками. В разделе 1.3.4 показаны способы проведения вычислений типа ВОК и для такого случая.

Таким образом, КА-ДС имеет следующие дополнительные возможности по сравнению с КА.

1. Непосредственными соседями клетки может быть любая группа клеток. Для разных клеток соседи могут определяться по разным правилам.

2. Среда, содержащая клетки КА-ДС может быть неоднородна: правило изменения состояния клетки зависит от ее расположения.

3. Клетки могут изменять не только свое состояние, но и правила изменения состояния в других клетках.

4. Для оценки и изменения состояния клеток и изменения правил применяются групповые команды.

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

2.2.2 Групповые операции в эволюционных алгоритмах

Основные источники [74,75,76,78,79,80,81].

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

ляции идет "борьба за существование", с течением времени объекты совершенствуются и выживают объекты лучшего качества. Имеются существенно различающиеся между собой направления создания таких алгоритмов [75] Тем не менее, все эволюционные алгоритмы характеризуются высоким параллелизмом, популяции объектов могут разбиваться на группы, расположенные на разных процессорах. В каждом процессоре, содержащем часть популяции, производится оценка качества объектов, поиск подходящих объектов для их модификации и собственно модификация. Для ускорения таких действий в составе блоков процессора желательно иметь ассоциативный процессор или, в крайнем случае, ассоциативную память [75, 80]. Для быстрого взаимодействия группы процессоров надо использовать групповые операции из части 1. Они здесь выполняют следующие действия.

1. Оповещение процессоров системы о наилучшем результате, полученном в одном из процессоров системы. Проводится приоритетное занятие канала связи. Приоритет в занятии определяется качеством полученного решения. После этого широковещательно передается полученное решение.

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

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

В качестве конкретного варианта распределенного эволюционного алгоритма, использующего групповые операции, ниже рассмотрена задача, близкая к методу анализа иерархий (МАИ) Т. Саати [С8].

Задача состоит в настройке иерархической системы связей:

Задан набор объектов, который располагается на нижнем уровне многоуровневой структуры. Над этим уровнем находятся уровни промежуточных узлов (рис. 21).

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

А В с Р

Рис. 21. Настройка связей в иерархической системе

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

Для уменьшения перебора при решении сформулированной задачи были разработаны вариант генетического алгоритма, программа для ЭВМ и структура многопроцессорной системы, использующие групповые операции [76,77, 78, 81]. Решение состоит в следующем. Из заданных интервалов для парных сравнений случайно выбирается набор чисел. Это задает значения парных связей и использование алгоритмов МАИ дает быстрый способ вычисления приоритетов . В результате получаем решение, которое не противоречит ограничениям, но скорее всего не обеспечивает требуемого ранжирования объектов по приоритетам. Получаем группу таких решений. Используя набор допустимых решений, следует построить решение, обеспечивающее требуемое ранжирование объектов и наибольший приоритет для заданного объекта. На этом этапе начинает работать генетический алгоритм.

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

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

решения с высоким значением качества. Алгоритм прекращает работу, если получено достаточно хорошее решение, или исчерпано выделенное алгоритму время. Алгоритм легко распараллеливается и при наличии многопроцессорной системы популяция разбивается на части, размещенные в разных процессорах. Процессоры должны взаимодействовать между собой: те из них, которые получили достаточно хорошее решение, должны сообщить о нем остальным процессорам. Последние пополняют ими свои популяции и полученный "распределенный опыт" используется для ускорения вычислений. Для быстрого выполнения указанного взаимодействия применяются групповые операции. Изложенными в разделах 1.1 и 1.2 способами выполняется ГО max, определяющая наилучший результат в распределенной системе. Всем процессорам задается допустимое процентное отклонение от наилучшего результата. Если результат процессора находится в указанном диапазоне, то процессор должен сообщить о нем всем процессорам системы. Для такого сообщения применяется ПС сбора данных. Она имеет переменную длину, и в нее заносятся данные от многих процессоров. Таким образом, достаточно выполнить две групповые команды, чтобы скорректировать распределенную популяцию. Так как в процессе решения потребуется выполнить много таких корректировок, то использование ГО существенно ускоряет выполнение алгоритма.

2.2.3 Групповые операции для ЭВМ, управляемых потоком данных

Основной источник [44].

В ЭВМ, управляемых потоком данных, в отличие от ЭВМ, управляемых потоком команд, не задается порядок выполнения команд. Команда может выполняться при наличии всех ее аргументов. В этом случае программы получаются менее громоздкими и более простыми в отладке, однако, их реализация сталкивается с рядом трудностей [44, С9]. Для таких машин характерны в частности следующие особенности.

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

О полученном результате процессор должен известить все процессоры или задашгую группу процессоров.

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

2.2.4 Использование групповых операций в комплексах GRID

Основные источники [84,88,89].

Существует два типа сетей GRID- глобальные, с выходом в сети дальней связи, например, в Internet, и локальные, в которых компьютеры объединены локальной сетью. В реализованных локальных GRID [C21] нет принципиальных функциональных отличий от глобальных GRID. Однако, локальные сети GRID могли бы предоставлять сервис, существенно отличающийся от того, который дают глобальные GRID, например, для решения задач жесткого реального времени (ЖРВ). К таким задачам относятся управление работой технических средств или вычислительные задачи, в которых требуется выдерживать временную согласованность выполнения частей задачи на разных компьютерах сети. Назовем системы, способные решать такие задачи, комплексами GRID. Прежде всего, отметим режимы работы, в которых локальная сеть GRID может функционировать как комплекс GRID. Это, во-первых, режим отсутствия основных пользователей распределенных компьютеров комплекса. Так как комплекс локален, то в конце рабочего дня практически все компьютеры освобождаются для выполнения единой задачи. Во-вторых, даже при наличии пользователей целесообразно периодически выделять высокоприоритетный квант времени, отнимаемый у пользователей для проведения вычислений в режиме ЖРВ.

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

В настоящем разделе показано, как изложенные в докладе решения позволяют организовать работу комплексов GRID. Комплекс GRID незначительно отличается от систем АСУ ТП с групповыми операциями, подробно рассмотренными в разделе 2.5, поэтому здесь будет дано лишь сжатое изложение темы.

Основой работы комплекса GRID служат способы приоритетного доступа к ресурсам, групповые операции и групповые команды, изложенные в предыдущих разделах.

Требуемый для комплексов GRID доступ к ресурсам в гарантированные сроки обеспечивает применение различных вариантов децентрализованного приоритетного доступа (раздел 1.1). Их необходимо использовать при начальном запуске комплекса или при отказах, требующих перезапуска комплекса и выделения при этом одного из многих узлов управления началом работы системы.

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

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

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

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

4. Требуется оперативно перераспределять нагрузки в системе с учетом доступности и работоспособности компьютеров комплекса.

Эти вопросы эффективно решаются с применением групповых команд (разделы 1.4, 2.1). В качестве примера приведем проверку достоверности принятых сообщений.

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

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

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

Перечисленные задачи относятся к управлению работой комплекса. Но и собственно обработка данных может быть распределена и быстро выполняться с применением вычисления в общем канале (раздел 1.2).

Наконец, полезно организовать фрактальную структуру связей в комплексе (раздел 1.3), подобную структуре, показанной на рис. 16.

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

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

Использование коллективного взаимодействия компьютеров при выполнении групповых операций — шаг в превращении локальных GRID в действительно распределенный компьютер.

2.2.5 Групповые команды в сетях мобильных датчиков

Основные источники [84,87].

Задачи организации синхронной работы датчиков

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

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

чике. Было предложено несколько решений этой задачи, действующих на разных уровнях протокола сетевого взаимодействия. Наиболее продвинутый способ, разработанный в Массачусетском Технологическом Институте, состоит в следующем [С19]. Датчики действуют подобно узлам Internet, и при необходимости передать сигнал удаленному объекту организуется цепочка посредников, через которых сигнал перемещается от источника к приемнику.

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

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

Формирование состава группы поддержки и ретрансляция

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

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

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

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

Формирование расширенной группы поддержки В дополнение к возможностям предыдущего раздела желательно формировать группу поддержки с привлечением датчиков, которые непосредственно не принимают сигнал источника. Требуется помимо синхронизации работы передатчиков группы уметь ограничивать размер группы. Для этого несколько усложним способ предыдущего раздела, сделав его одинаково приемлемым как для группы из предыдущего раздела, так и для указанной здесь более сложной группы. Пусть источник сообщения в команде ГК2 формирования группы помещает указатель и = 1, 2, .... к. Эта команда завершается передачей сообщения, которое требуется ретранслировать. Датчики, принявшие команду, запоминают сообщение и выполняют вычитание И = И-1. Если после этого И > 0, то все датчики передают команду ГК2 с новым, уменьшенным на 1, значением и, и кодом сообщения. Так будет продолжаться до тех пор, пока не будет передана команда К2 с И = 0. Дальнейшего роста группы происходить не будет. Все датчики — участники этого процесса теперь имеют информацию, достаточную для того, чтобы определить момент начала процесса ретрансляции, так как они знают длину сообщения.

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

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

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

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

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

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

Итоги исследований, изложенных в главе 2.2

1. Для моделирования задач с нерегулярной структурой предложен новый тип клеточных автоматов с групповыми операциями - клеточные автоматы с дальними связями (КА-ДС).

2. Показаны способы применения групповых команд для быстрого сбора данных о состоянии клеток КА-ДС и изменения их состояния.

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

4. Все предложенные решения допускают техническую реализацию КА-ДС, клетки которых выполняют операции параллельно.

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

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

7. Даны способы использования ГК в сетях GRID для повышения их реактивности.

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

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

Основные источники [50,51,54,55, 56,57,59,60,62,63,66,67,69].

В разделах 2.3.1 и 2.3.2 рассмотрены реализованные на практике системы, использующие изложенные в предыдущих разделах результаты. Они созданы при участии автора. В разделе 2.3.3 приведена широко известная практическая реализация способа доступа ДКУ, полученная без участия автора, но подтверждающая эффективность ДКУ.

2.3.1 Применение групповых операций в системе АСУ ТП КУРС 2.3.1.1 Общая характеристика системы КУРС

АСУ ТП КУРС разработана во второй половине 80-х г.г. Институтом проблем управления РАН и Грозненским НПО Промавтоматика. Эта система раз-

рабатывалась по постановлению Минприбора как типовая для управления широким классом непрерывных технологических производств. Концепция построения системы [55] прошла экспертизу ведущих НИИ Минприбора. Разработка системы была успешно завершена и в 1989 г. был подготовлен ее серийный выпуск [67]. Общая структура системы приведена на рис. 22. Основной комплекс системы, непосредственно управляющий технологическим процессом, состоит из станций контроля и управления технологическими процессами, устройств связи с объектом (У СО) и станций связи с оператором (терминальных станций).

Рис. 22. Структура АСУ ТП "КУРС"

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

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

Во время проектирования системы КУРС и ранее обычно применялись системы управления в которых сложная структура связей и управления ими сочеталась с низкой скоростью обмена. В КУРС использован принцип: "простая структура связей и высокая скорость обмена". Эффект такого подхода - умень-

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

Отдельная задача - включение в систему простых устройств связи с объектом (датчиков, исполнительных механизмов). Такие устройства обычно подключались через концентраторы. Из соображений надежности нежелательно подключение большой группы УСО через концентратор. Поэтому была поставлена цель, в пределах имеющихся технологических возможностей, уменьшить количество подключенных к концентратору устройств. В пределе каждое устройство должно иметь выход в сеть. Для повышения скорости реакции системы и уменьшения загрузки линий связи простые устройства должны быть активными. С этой целью была проведена разработка сети УСО [55]. Сети УСО подключаются к станциям контроля и управления непосредственно и через технологическую сеть. Для управления доступом устройств в оба вида сетей без привлечения центральных коммутирующих устройств был использован способ доступа ДПВУ, изложенный в разделе 1.1.3. Применение ДПВУ позволило получить хорошие временные характеристики средств связи системы КУРС.

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

2.3.1.2 Техническая реализация технологической сети

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

дача сигналов осуществляется в противоположных направлениях, Режим работы - дуплексный. Скорость передачи 2/4 Мбит/с. Ретрансляторы позволяют создавать магистраль, используя только двухточечные соединения. Это повы-

Рис. 23. Линейная структура сетей АСУ ТП "КУРС"

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

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

Рис. 24. Древовидная структура сетей АСУ ТП "КУРС"

Сетевой контроллер (СК) организует доступ в сеть на основе децентрализованного приоритетного пространственно-временного управления (ДПВУ). В СК и ретранслятор встроены аппаратные средства диагностики отказов аппаратуры и средства отключения отказавшей аппаратуры.

На рис. 25 приведено сравнение средней задержки в передаче данных W(S) в сети системы КУРС и сетях Ethernet и IBM Token Ring при числе абонентов, скорости, протяженности линий и длине типового пакета данных, типичных для АСУ ТП КУРС (см. раздел 1.1.4).

ХАРАКТЕРИСТИКИ

cm системы КУРСХ Ethernet, Token Ring

N- Wpn^V-It MIT^i L ■ 2 км. И ■ ЩИ «иг

О 02 М 0.6 0.8 S

Рис. 25. W(S) для сети системы КУРС, Ethernet, Token Ring

2.3.1.3 Техническая поддержка и особенности протокола канального

уровня

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

- гарантированная доставка пакетов в порядке их приоритетов;

- устойчивость к пакетным ошибкам высокой кратности;

- минимизация времени доставки пакетов с учетом времени ожидания подтверждения доставки;

- быстрый контроль правильности доставки пакетов при групповой адресации.

Приоритетная доставка пакетов обеспечивается за счет передачи пакетов данных по запросам и организации упорядоченных по приоритетам очередей запросов в приемниках. Для контроля правильности доставки пакетов приемнику применяется информационная обратная связь с возвратом источнику принятого от него пакета (ЭХО-контроль), которая охватывает тракт "память источника — память приемника". Квитанция посылается в одном сеансе с передачей пакета. Это резко снижает время доставки пакета. ЭХО-контроль обладает высокой устойчивостью к пакетным ошибкам высокой кратности за счет временного сдвига прямой и обратной передачи. Для квитирования передач данных группе приемников используется ВОК.

Управление взаимодействием на канальном уровне дает средства для построения распределенной операционной системы реального времени (РОС) и в

первую очередь помогает распределять ресурсы и координировать процессы в системе управления с учетом их приоритетов.

Разработанный для этого протокол является вариантом изложенной в разделе 1.3 распределенной программы, базирующейся на групповых командах. Особое внимание было уделено получению квитанций в групповых командах. Более подробное изложение этого вопроса содержится в работе [72].

2.3.1.4 Распределенная операционная система АСУ ТП КУРС.

Распределенная операционная система (РОС) управляет работой системы КУРС в целом. В ее основу положены общие принципы построения РОС, изложенные в разделе 2.1.3. Основные особенности РОС следующие.

- РОС обеспечивает поддержку протокола детерминированной передачи сообщений с динамическими приоритетами и гарантированным временем доставки.

- Управление распределенными вычислительными процессами (задачами) производится в соответствии с требованиями к операционным системам реального времени (ОС-РВ).

- Все обращения к РОС от программ пользователей стандартизованы.

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

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

Организационно РОС представляла собой набор модулей, распределенных по всей системе и имеющих доступ к локальным и глобальным управляющим данным. На каждой станции должен находиться одинаковый для всех станций системы модуль - ядро РОС. В совокупности ядро и распределенная общая память (РОП) образуют распределенный монитор. Распределенная память состоит из множества копий системных управляющих таблиц. Организация РОП соответствует разделу 2.1.3.3. Операция обновления содержимого общей памяти выполняется за одно занятие общего канала с использованием групповых операций.

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

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

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

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

2.3.2 Локальные сети с ГО, разработанные для других заказчиков

2.3.2.1 Локальная управляющая сеть промышленного применения.

"Приоритет 1"

Эта сеть - дальнейшее развитие ЛУС системы КУРС. Ниже приведены ее возможности и сравнение с появившемся во время разработки сети стандартом шш-МАР.

1. Множественный доступ по индивидуальным динамическим приоритетам источников. В шЫ-МАР нет доступа по индивидуальным динамическим приоритетам.

2. Гарантированное время доступа при любом канальном приоритете. В шЫ-МАР обеспечивается гарантированный доступ только при одном уровне приоритета.

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

4. Широкий спектр видов адресации с немедленным подтверждением: индивидуальная, групповая и широковещательная. Групповая адресация осуществляется и по адресу источника - вызываются приемники, которые ожидают активности данного источника. Это упрощает изменение структуры связей в сети, так как не требуется знать состав группы приемников. В шгш-МАР нет адресации по адресу источника.

5.Немедленное (без освобождения канала) подтверждение на канальном уровне приема пакетов всеми адресованными приемниками. В тгш-МАР отсут-, ствует быстрое широковещательное подтверждение, и надежное широковеща-

ние осуществляется только на основе длительных процедур "византийского соглашения".

6. Реализованы групповые операции СБОР, СМЕЩЕНИЕ, СУММА, МАКСИМУМ. В mini-MAP отсутствуют групповые операции.

7. Поддержка цепочечных сеансов. При индивидуальной адресации - это интерактивный сеанс, в котором источник и приемник меняются местами после доставки очередного пакета. При групповой адресации - это цепочки обычных групповых сеансов и групповых операций в любой последовательности. В miniMAP не поддерживается.

8. Быстрая распределенная диагностика сети на базе групповых операций и "надежного широковещания". Время диагностики - один короткий сеанс. В mini-MAP эта возможность отсутствует.

Сеть была установлена в НИИЯФ МГУ, г. Москва. Документация на сеть была передана также на завод "КАРАТ", г.Вышгород Киевской области и на завод КАМАЗ.

2.3.2.2 Локальные сети "АПЛС-1", "Лаура".

В сети АПЛС-1 в качестве метода доступа использовано ДПВУ. Документация на нее была передана во ВНИПИАСУ Легпрома. Сеть предназначалась для использования на прядильных и красильно-отделочных производствах.

Локальная управляющая сеть промышленного применения "Лаура" явилась модификацией, разработанной в Институте проблем управления сети "Приоритет 1". Разработка была выполнена совместно с малым предприятием "Проминформатика". Выпуск сети был начат в 1990 году.

2.3.3 Сети 12С и D2B фирмы Philips

В 1980 году фирма Philips разработала и опубликовала две локальных сети - 12С и D2B. В них применен аналог одного из вариантов способа доступа ДКУ, разработанного в ИЛУ и опубликованного значительно раньше. Способ 12С использует лишь адреса устройств для предоставления канала связи одному из них, имеющему наибольшее значение адреса, в то время как ДКУ учитывает приоритеты различных видов ресурсов. Сети 12С и D2B здесь упоминаются потому, что служат хорошей демонстрацией полезности групповых операций. Фирма Philips, и вслед за ней несколько других крупных фирм, применили 12С не только в промышленных сетях, но и в бытовой аппаратуре, в частности в телевизорах для объединения между собой их блоков. Соответствующие чипы выпускаются и используются в России и Белоруссии. В последние годы 12С применяется в мониторах ЭВМ и в модулях памяти для идентификации этих устройств [СЮ].

Итоги исследований, изложенных в главе 2.3

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

2. Разработаны и реализованы локальные сети системы КУРС и способы использования в них групповых операций для управления доступом и работы протокола канального уровня.

3. Разработаны и реализованы принципы организации распределенной операционной системы (РОС) системы АСУ ТП КУРС, организация в ней распределенной общей памяти и распределенного программирования.

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

Основные результаты, полученные в части 2

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

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

- разработан новый класс клеточных автоматов с неоднородными дальними связями;

- разработаны новые методы организации параллельных эволюционных алгоритмов;

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

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

Заключение

Полученные в работе результаты разделяются на следующие основные группы.

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

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

3. Для каналов обмена данными с направленной передачей сигналов на основе групповых операций теоретически разработан и реализован на практике метод ВОК - метод проведения вычислений над данными, передаваемыми по такому каналу без задержки на их обработку.

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

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

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

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

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

- обеспечение быстрой гарантированной доставки широковещательных и групповых сообщений;

- создание средств быстрого восстановления работоспособности системы с использованием скользящего резервирования ресурсов;

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

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

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

- повышение скорости реакции локальных комплексов GRID.

7. Групповые операции и многие из решений на их основе, указанных в предыдущих пунктах, были практически реализованы в распределенной системе управления непрерывными технологическими производствами КУРС и ряде управляющих локальных сетей, ориентированных на работу в системах жесткого реального времени.

Таким образом, поставленные в работе цели достигнуты.

Публикации по теме диссертации (указаны соавторы)

1. Организация структуры и оценка параметров автоматизированной системы управления (Нисневич Л.Б., Эпштейн В.Л.) //АиТ 1967. № 10.

2. Периферийное оборудование системы оперативной обработки информации на металлургических заводах и связь его с ЭВИ (Жарин Е.А., Рутков-ский И. П.) //Автоматизация металлургических объектов и процессов. М.:Институт проблем управления, 1970. с. 48-59.

3. Цифровая модель для оценки параметров АСОД (Котюжанский Г.А., Нисневич Л.Б.,Тинт Л.С., Эпштейн В.Л.) //АиТ. 1970. №1.

4. Децентрализованное приоритетное управление в одноканальной системе обмена данными (Котюжанский Г.А, Нисневич Л.Б.) //Известия АН СССР. Техническая кибернетика. 1970. №6.

5. Устройство для передачи информации для систем цифровых машин (Котюжанский ГА, Нисневич Л.Б., Эпштейн В.Л.) // Авт. свидет. № 291199 от 27.11.1968. Бюлл. изобр. 1971. №3.

6. Использование принципов децентрализованного приоритетного управления в интегральных системах обмена данными (Нисневич Л.Б.) //АиТ. 1971. №5.

7. Организация выбора статических приоритетов в системах с децентрализованным управлением 1(Нисневич Л.Б.) //АиТ. 1971. №6.

8. То же часть 11/АиТ. 1971. №7.

9. Многоканальная децентрализованная приоритетная система (Нисневич Л.Б.) //Известия АН СССР, Техническая кибернетика. 1971. № 2.

10. Организация порядка обслуживания в системах, работающих в реальном масштабе времени (Нисневич Л.Б.) (брошюра) М.: ИАТ, 1971.27 с.

11 .Децентрализованное управление взаимодействием объектов в сложных системах и его применение к задачам обмена данными (Нисневич Л.Б.) // Пятое всесоюзное совещание по проблемам управления. Тезисы докладов. М.: ИАТ, 1971.

12. Децентрализованное приоритетное управление взаимодействием ЗУ в вычислительных системах (Нисневич Л.Б.) //Научно-техническое совещание по развитию и совершенствованию запоминающих устройств для ЭВМ. Тезисы докладов. Ленинград: НТО радиотехники, электроники и связи, 1971.

13. Децентрализованное управление обменом данными в ОА-СУ//Всесоюзное совещание по ОАСУ. Тезисы докладов. Баку. 1971.

14. Имитационная модель системы обработки данных в реальном масштабе времени (методика) Ч. 1 (Котюжанский ГА, Нисневич Л.Б., Тинт Л.С., Эпштейн В.Л.) (брошюра) М.:ИАТ, 1971.

15. Децентрализованное управление взаимодействием потребителей в одноступенчатых системах распределения потока ресурса. I (Нисневич Л.Б.) //АиТ. 1972. №5.

16. Децентрализованное управление взаимодействием потребителей в одноступенчатых системах распределения потока pecypca.II (Нисневич Л.Б.) //АиТ. 1972. №6.

17. Децентрализованное управление с неточной информацией, использующее метод простейшего спуска (Нисневич Л.Б.) //АиТ. 1972. №9.

18. Сети обмена данными с децентрализованным приоритетным управлением (Подлазов B.C., Пучков В.В.) //Информационные сети и автоматическая коммутация (ВСИС-2) Тезисы докладов. М.: Наука, 1973.

19. Структура средств оперативного моделирования дискретного производства (Грузман В.А., Эпштейн В.Л.) //Некоторые вопросы математической теории управляемых процессов. М.: Институт проблем управления, 1973. с. 17-21.

20. Децентрализованное коалиционное управление в системах обработки данных//АиТ. 1973. №4.

21. Децентрализованное приоритетное управление в системе в передачи данных с бегущей волной //АиТ. 1974. №2.

22. Совершенствование управления обменом данными в АСУ( Подлазов B.C., Пучков В.В.) //Всесоюзный семинар по использованию ЕС ЭВМ в АСУ. М.: ЦЭМИ, НИЦВТ, 1974.

23. Decentralized Control in Communication and Data Processing Systems (Aven O.I.) Proceedings of a IIASA Conference on Computer Communications Networks. 1974. pp 173-184

24. Децентрализованное приоритетное управление обменом данными (ДПУ) (Подлазов B.C., Пучков В.В.)//Экспонат Выставки "Достижения советской науки и техники. София. 1974.

25. То же. Экспонат Выставки работ АН СССР ВДНХ. 1975 (бронз, медаль).

26. То же. Экспонат Выст. "250 лет АН СССР ВДНХ. 1975.

27. Расширение функций управления в системе обмена данными с бегущей волной (Подлазов B.C., Пучков В.В.) //АиТ. 1975. №8.

28. Децентрализованное приоритетное управление в сети ЭВИ (Подлазов B.C., Пучков В.В.) //Семаинар.Сети ЭВМ и системы передачи данных. Тезисы докладов. М.: МДНТП, 1976.

29. Децентрализованное приоритетное управление передачей данных в системах автоматизации научных исследований (Подлазов B.C., Пучков В.В.) //Научно-техническая конф. "Технические средства автоматизации научных исследований". Тезисы докладов. М.: МДНТП, 1977.

30. Простые алгоритмы децентрализованной коммутации для систем обработки данных (Подлазов B.C., Пучков В.В.) //Вычислительные машины и системы с перестраиваемой структурой. М.: Научный совет по комплексной проблеме "кибернетика", 1978. с. 121-129

31.0 требованиях к организации обмена данными в децентрализованных многопроцессорных системах. Всесоюзная научно-техническая конф. "Повышение эффективности и качества продукции на базе развития распределенных систем управления и применения микропроцессорных уст-

роиста". Тезисы доклада.. М.: НТО Приборостроительной промышленности, 1978.

32. Организация микроЭВМ с блочной структурой, ориентированной на работу в системе машин (Подлазов B.C., Пучков В.В.) //Тезисы доклада. Там же.

33. Устройство для приоритетного подключения источников к магистрали (Подлазов В С, Пучков В.В.) //Авт. свид. №599261, Бюлл. изобр. №11,1978.

34. Быстрый способ балансировки нагрузки РУВС. Материалы 6-го Всесоюзного семинара по модульным информационно-вычислительным системам "Микропроцессорные системы и локальные сети реального времени". Вильнюс: ИМиК АН Лит. ССР, 1987. с. 46-47.

35. Новый способ доступа со стохастическим уплотнением канала (Захарова Т.Н., Подлазов B.C., Смирнов АН.) Научно-техническая конференция "Проблемы космической радиосвязи". Тезисы докладов. М.: НТО радиотехники, радиоэлектроники и радиосвязи, 1979.

36. Обмен данными в мультипроцессорных системах (ММС) и его влияние на распараллеливание вычислений (Смирнов АН.) // Всесоюзная научно-техническая конференция: Применение интегральных микросхем, микропроцессоров, микро-эвм и микроэлектронной технологии в приборостроении. Орел. Тезисы доклада. М.:НТО Приборостроительной промышленности, 1979.

37. Вычисления в общем канале //Всесоюзное научно-техническое совещание "Проблемы создания и использования высокопроизводительных информационно-вычислительных машин. Тезисы доклада. Кишинев: Институт проблем управления, 1979.

38. Новые алгоритмы децентрализованного приоритетного управления обменом данными (Подлазов B.C., Пучков В.В.) //АиТ. 1979. №8.

39. Микропроцессорные системы (Прангишвили И.В.)М.: Наука, 1980. 237 с.

40. Ускоренный алгоритм децентрализованного приоритетного управления доступом к общему каналу (Захарова Т.Н., Подлазов B.C.) АиТ. 1980. №10.

41. Локальная сеть обработки данных с децентрализованным пространственно-временным управлением обменом информацией (Прангишвили И.В., Подлазов B.C.) // Тезисы доклада. Вторая всесоюзная конф. Вычислительные сети коммутации пакетов. Рига: ИЭВТ, 1981

42. Обработка данных в общем канале - дополнительная возможность распараллеливания вычислений.(Подлазов B.C., Смирнов АН.) Всесоюзное совещание "Высокопроизводительные вычислительные системы". Тезисы доклада. ч.1. Тбилиси. М.: Институт проблем управления, 1981.

43. Decentralized Control of Processor Interactions in Concentrated and Distributed Multi-microprocessor Systems (Prangishvili I. V., Podlazov V.S.) //Microprocessing and Microprogramming no. 4. 1981. pp 220-228. Publisher: Elsevier Sci. (новое название - Journal of Systems Architecture).

44. Современное состояние проблемы создания ЭВМ с нетрадиционной структурой и архитектурой, управляемых потоком данных (Прангишвили И.В.) //Измерения, контроль, автоматизация. 1981. № 1.

45. Вычисления в общем канале (Подлазов B.C., Смирнов А.Н.) //Многопроцессорные вычислительные системы с перестраиваемой структурой. М.: Научный совет по комплексной проблеме "кибернетика", 1981. с.97-106.

46. Организация обмена информацией в микропроцессорных системах. М.: Машиностроение, 1982. 56 с.

47.Три модели распределенных операционных систем (Илларионов Ю.А.) //Тезисы доклада. Программное обеспечение многопроцессорных систем, Всесоюзный научно-технический семинар. Калинин: НПО "Центрпро-граммсистем, 1985.

48. Использование сетевого подхода в сосредоточенных и распределенных мультипроцессорных вычислительных системах // V Всесоюзная школа Многопроцессорные вычислительные системы. Звенигород. М.: Институт проблем управления, 1983.

49. Решение вычислительных задач в общем канале (Подлазов B.C., Смирнов А.Н.) //АиТ. №5.1984.

50. Концептуальная модель локальной сети с распределенным управлением (Илларионов Ю.А., Подлазов B.C., Смирнов А.Н) //Микропроцессорные распределенные системы управления технологическими процессами и гибкими автоматизированными производствами. Тезисы докладов научно-технической конференции. М.: ИПУ, МИЭМ, 1984.

51. Распределенная микропроцессорная система для АСУТП химико-технологических производств (Белей В.М., Ицкович Э.Л., Опришко А.А., Пальчик К.Б., Прангишвили И.В.) Тезисы доклада. Там же.

52. Локальные микропроцессорные вычислительные сети (Прангишвили И.В., Подлазов B.C.) M.: Наука, 1984.176 с.

53. Одно решение проблемы общей памяти в распределенной вычислительной системе (Илларионов Ю.А, Подлазов B.C.)

//Высокопроизводительные вычислительные системы II всесоюзное совещание тезисы докл. Батуми М.: Институт проблем управления, 1984

54. Средства диагностики и реконфигурации для станций микропроцессорной локальной вычислительной сети (МЛВС) (Белей В.М., Подлазов B.C.) //Научно-техническая конф. "Микропроцессорные распределенные системы управления технологическими процессами и гибкими автоматизированными производствами. Тезисы докл. М.: ИПУ, МИЭМ, 1984.

55. Научно-техническая концепция построения распределенной микропроцессорной управляюще-вычислительной системы на базе малой локальной вычислительной сети с децентрализованным приоритетным управлением для АСУ ТП непрерывных и непрерывно-дискретных производств (коллектив авторов). М.: ИПУ, Союзпромавтоматика,1984.68 с.

56. Организация множественного доступа к файлам в локальной вычислительной сети (Илларионов Ю.А, Подлазов B.C.) В кн. Программное обес-

обеспечение ЭВМ. Базовое программное обеспечение и программное обеспечение сетей и систем телеобработки. Материалы Международной научно-технической конференции "Программное обеспечение ЭВМ" Калинин: НПО "Центрпрограммсистем", 1984.

57. Новый подход к организации общей памяти в локальных вычислительных сетях (Илларионов Ю.А.) Всесоюзная конференция "Локальные вычислительные сети". Тезисы докладов. Рига: ИЭВТ, 1984.

58. Локальные управляющие сети: цели, задачи, решения //VI Всесоюзная школа многопроцессорные вычислительные системы. Звенигород. М.: Институт проблем управления, 1985

59. Принципы построения распределенной микропроцессорной системы управления "Курс" (Белей В.М., Опришко АА.) //X Всесоюзное совещание по проблемам управления. Тезисы докладов т. 2. Алма-Ата М.: Институт проблем управления, 198б.

60. Decentralized microprocessor-based chemical-process control system "RA-KURS"; Design Philosophy (Itskovich E.L., Ljubimov Yu. В., Prangishvili I.V. et. al.) //10-th World Congress on Automatic Control IFAC Preprints. Mu-nich.1987. vol. 4. pp. 125-129.

61. Принципы построения локальной управляющей сети для АСУ ТП (Илларионов Ю.А., Подлазов B.C., Смирнов А.Н.) //VIII международная конференция "Применение ЭВМ в технике и управлении производством" COMPCON' 87 Материалы конференции Часть II.2. М.: ВСНТО им. Попова, АН СССР, 1987. с. 116-119.

62. Взаимодействие процессов при разделении ресурсов в распределенных вычислительных системах (Илларионов Ю. А) //Измерения, контроль, автоматизация. 1987. Х°3.

63. Высокореактивная локальная управляющая сеть. (Подлазов B.C., Ватников В. И.) // Научно-технический семинар "Сетевая обработка информации". Тезисы доклада. М.: МДНТП, 1990.

64. Организация взаимодействия в распределенных вычислительных системах реального времени (лекция) /ЛИ всесоюзное совещание Высокопроизводительные вычислительные системы. Таллин: Институт проблем управления, 1988.

65.. Локальная управляющая сеть связи с объектом для АСУ ТП (Овчинников АЛ., Подлазов B.C.) //Опыт создания локальных сетей ЭВМ, Материалы семинара. М.: МДНТП, 1988. с.34-39.

66. Средства обеспечения отказоустойчивости локальной управляющей сети (Зрелова Т.И., Подлазов B.C., Смирнов А.Н.) //Отказоустойчивые многомашинные и многопроцессорные вычислительные системы. М.: 1989. с.60-82.

67. Программно-технический комплекс сетевой архитектуры НТК "КУРС" (технические средства) (коллектив авторов)Грозный:. Грозненское НПО Промавтоматика, Институт проблем управления, 1989. с. 48.

68. Устройство для вывода информации от абонента в сетевую шину (Нар-кович А.Ю., Овчинников А.Л., Подлазов B.C.) / авт. свид. №1464166, Бюлл. изобр. №9. 1989.

69. Семейство локальных сетей с расширенными функциональными возможностями (Подлазов B.C., Алленов А.В., Ватников В.И., Слободчук В.В., Смирнов А.Н., Юдицкий С.С.) //Всесоюзное научно-техническое совещание-семинар "Микропроцессорные системы управления технологическими процессами в ГПС". Тезисы докладов. Одесса: Одесский политехнический институт, 1990.

70. Надежность и пропускная способность кратного последовательного канала ЛВС на ВОЛС (Подлазов B.C., Слободчук В.В., Смирнов АН.) // Отказоустойчивые вычислительные системы реального времени. М.: Научный совет по комплексной проблеме "кибернетика", 1990.100-136.

71. Аппаратно-программная поддержка надежного широковещания в локальных управляющих сетях (Ватников В.И., Подлазов B.C., Смирнов А.Н.) //Отказоустойчивые параллельные вычислительные системы реального времени. М.: Научный совет по комплексной проблеме "кибернетика", 1990. с. 87-100.

72. Локальные управляющие сети для тесно связанных распределенных систем жесткого реального времени (Подлазов B.C., Смирнов А.Н., Алленов А.В., Слободчук В.В.) //Международный сборник "Вычислительная техника, системы управления", вып. 6. М.:МЦНТИ, 1991. с. 82-96.

73. Пропускная способность набора кольцевых каналов. I. Класс наборов колец. Наборы с простыми узлами (Алленов А.В., Подлазов B.C.) //АиТ. 1996. №3.

74. Прямая и обратная задача метода иерархий (МАИ) в задачах принятия решений (Подлазов B.C.) //Тезисы докладов. Пятая международная конф. "Проблемы управления безопасностью сложных систем. М.: Институт проблем управления, 1998.

75. Эволюционные методы в задачах управления, выбора, оптимизации //Приборы и системы управления. 1998. № 3.

76. Алгоритмы, программы и технические средства для решения двух задач выбора в системах управления //Труды Института проблем управления РАН. 1999. т.6. с. 81-90.

77. Пакет программ для оперативной поддержки принятия решений /VI международная конференция "Проблемы управления безопасностью сложных систем/М.: Институт проблем управления, 1999.

78. Технические средства для ускорения эволюционных вычисле-ний//Международ-ная конференция по проблемам управления, т. 3. Тезисы доклада. М.: Институт проблем управления. 1999.

79. Генетический алгоритм для обратной задачи метода анализа иерархий. //Международная конференция по проблемам управления. Тезисы доклада. М.: Институт проблем управления, 1999.

80. Фрактальные связи для систем параллельного вычисления эволюционных алгоритмов //Труды международной конференции Параллельные вы-

числения и задачи управления (РАСО' 2001) М.: Институт проблем управления, 2001. с. 183-187.

81. Специализированная структура связи для параллельного выполнения эволюционных алгоритмов //Труды института проблем управления РАН. 2002. ТОМ18.С.127-134.

82. Дальнодействие в клеточных автоматах //Вторая международная конференция по проблемам управления. Тезисы докладов, т.2. М.: Институт проблем управления. 2003.

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

84. Возможности применения фрактальных связей и групповых операций в многопроцессорных системах с перестраиваемой структурой для эволюционных вычислений //АиТ. №12.

85. Дальнодействие в клеточных автоматах //Вторая международная конференция по проблемам управления, избранные труды. М.: Институт проблем управления, 2003. с.152-158.

86. Возможности технической реализации клеточных автоматов с дальними связями и групповыми операциями //АиТ. № 8. 2004.

87. Групповые операции для сетей мобильных датчиков //Датчики и системы. 2004. №4.

88.Работа локальных комплексов GRID в режиме жесткого реального времени //Проблемы управления 2004. № 3.

89.Применение групповых операций в локальных системах GRID. //Сборник трудов международной конференции РАСО 2004. М.: Институт проблем управления, 2004.

В журналах из перечня ВАК опубликовано 27 статей: №№ 1,3,4,5,6,7,8, 9,

15,16,17,20,21,27,33,38,40, 44,49,62,68,73,75, 84,86,87, 88.

Личный вклад автора в совместные публикации

№№ 1,19 -участие в разработке структуры.

№ 2 - разработка основных принципов и структуры системы.

№ 3 — участие в разработке модели.

№№ 4, 6, 9, 23, 27, 38, 40, 43, 45, 49, 72 - разработка основ ГО, разработка конкретных алгоритмов.

№№ 7, 8, 10,15,16,17 - участие в постановке задачи, разработка применения

автоматов с ГО.

№ 14 — участие в разработке модели.

№ 30 - постановка задачи, разработка алгоритма.

№№ 39,52 - разработка основ ГО, разработка конкретных алгоритмов.

№ 44—применение ГО.

№ 55 - разработка концепции использования ГО в АСУ ТП.

№ 60 - разработка структуры связей в АСУ ТП с применением ГО.

№№ 62, 66, 70, 71 — постановка задачи, разработка общей структуры решения, разработка конкретных алгоритмов.

№ 67 - разработка структуры связей в системе, протоколов, структуры системных программ, схемотехники сетевых контроллеров. № 73 — участие в разработке способа оценки пропускной способности.

Дополнительный список публикаций

С1 Таненбаум Э, ван Стеен М. Распределенные системы, принципы и парадигмы. СпБ.: Питер, 2003. С2 В.Н. Фаддеева, Д.К. Фаддеев. Параллельные вычисления в линейной ал-

гебре//Кибернетика. 1977. №6. СЗ Eswaran K.P. and others. Collision-free access control for computer communication bus networks //IEEE Trans. Software Eng. 1981. vol. SE-7. № 6. C4 Schwartz. Ultracomputers //ACM Transactions on Programming Languages

and Systems. 1980. vol. 2. № 4. C5 Abelson H. Lower Bonds on Information Transfer in Distributed Computations //Journal ofthe ACM. 1980. vol. 27. № 2. C6 Кроновер P.M. Фракталы и хаос в динамических системах. М.: Постмар-кет,2000.

С7 Нестерова Т.Н., Нисневич Л.Б. О зависимости характеристик обслуживания источников одноканальной системой от дисциплины обслуживания //АиТ. 1971. №9.

С8 Саати Т. Принятие решений. Метод анализа иерархий. //М: Радио и связь, 1993.

С9 Майерс Г. Архитектура современных ЭВМ. т. 2. М.: Мир, 1985.

СЮ Гук М. Аппаратные интерфейсы ПК. СпБ.: Питер, 2002.

С11 Новый способ построения запоминающих устройств //ДАН СССР. 1960. т.

132. №6.

С12 Решающее устройство для переводческих задач //Труды конференции по обработке информации, машинному переводу и автоматическому чтению текста. М.: ИНИ АН СССР, 1961. С13 Автоматическое поисковое устройство с обратной связью/там же. С14 К вопросу о построении универсальных цифровых машин со многими решающими устройствами/соавт. Клейнерман Г.И., Косарев А.А., Нисневич Л.Б./там же.

С15 Способ поиска в запоминающем устройстве частично совпадающих со

словом-вопросом слов//Авт. свид. №137699,Бюлл. изобр. 1961. №8. С16 Некоторые методы и устройства для решения информационно-логических задач //Современная цифровая автоматика и вычислительная техника. Сборник 2 М.: МДНТП, 1962.

С17 Андрианов А.Н., Задыхайло И.Б. Некоторые способы программирования на ЭВМ Сгау-1. Препринт. М.: Ин-т прикладной математики АН СССР, 1982.

С18 Bux W. Local-area subnetworks: a performance comparison //IEEE Trans. Communs. 1981. vol. Com-29. № 10.

С19 Heinzelman W. R., Chandrakkasan A., Balakrishnan H. Energy-Efficient Communication Protocol for Wireless Microsensor Networks //Proceedings of the Hawaii International Conference on System Sciences. Maui. Hawaii, 2000.

C20 Евреинов Э.В., Косарев Ю.Г. Однородные универсальные вычислительные системы высокой производительности. Новосибирск: Наука, 1966.

С21 Thain D., Tannenbaum Т., Livny M "Condor and the Grid"// Berman F., Hey A.J.G., Fox G., editors, Grid Computing: Making The Global Infrastructure a Reality. John Wiley. 2003.

C22 Salib M., Liao L., Jones R., Morse M., Liu A, Samara-Rubio D., Aldmino D., Pannicia M. Silicon Photonics// Intel Technology Journal. 2004. V. 08. Issue 02.

C23 Пахомов С. Триумф кремниевой фотоники//КомпьютерПресс. 2004. № 3.

С24 Корнеев В. Будущее высокопроизводительных вычислительных систем// Открытые системы. 2003. №5.

С25 Schwartz J.T. Ultracomputers// ACM Transactions on Programming Languages and Systems. 1980. V. 2. No. 4.

C26 Французов Д. Оценка производительности вычислительных систем// Открытые системы. 1996. №2.

С27 Корнеев В. Архитектуры с распределенной разделяемой памятью// Открытые системы. 2001. №3.

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

С28 Илларионов Ю.А Разработка высокоскоростных алгоритмов и программно-аппаратурных средств разделения ресурсов для распределенных управляюще-вьгчислительных систем. Москва. ИЛУ. 1985.

С29 Подлазов B.C. Разработка и исследование методов и средств приоритетного множественного доступа в локальных сетях с общим каналом. Москва. ИЛУ. 1986.

СЗО Смирнов А.Н. Исследование и разработка средств сетевых взаимодействий абонентов в локальных управляющих сетях. Москва. ИПУ. 1991.

СПИСОК СОКРАЩЕНИЙ

1. ГО - групповая операция

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

3. СБВ - система с бегущей волной

4. ВОК - вычисление в общем канале

5. ДКУ -децентрализованное кодовое управление доступом

6. СДКУ - совмещенное децентрализованное кодовое управление

7. УДКУ - ускоренное децентрализованное кодовое управление

8. ДПВУ - децентрализованное пространственно-временное управление

9. флС - фрактальная линия Серпинского

10. фкС -фрактальный канал Серпинского

11. ГК - групповая команда

12. ЖРВ - режим жесткого реального времени

13. РОС - распределенная операционная система

14. РОП - распределенная общая память

15. КРОП - копия содержимого модуля РОП

16. РПг- взаимное распределенное программирование

17. КА - клеточный автомат

18. КА-ДС - клеточный автомат с дальними связями

19. МАИ - метод анализа иерархий

Зак. 66. Тир 100. ИПУ.

¿ 15 926

t»