Содержание к диссертации
Введение
1. Задачи обработки сообщений в параллельных вычислительных системах
1.1. Архитектура современных вычислительных систем. 8
1.1.1. Классификация архитектур вычислительных систем . 9
1.1.2. Организация памяти вычислительных систем. 11
1.2. Организация коммуникационной сети вычислительных систем. 18
1.3. Задача и алгоритмы маршрутизации сообщений. 28
1.4. Отказоустойчивая маршрутизация сообщений. 35
1.5. Выводы по главе. 48
2. Отказоустойчивая маршрутизация сообщений и процедура ее реализации
2.1. Постановка задачи отказоустойчивой маршрутизации. 51
2.2. Процедура отказоустойчивой маршрутизации с поворотом «системы координат».
2.3. Примеры применения процедуры маршрутизации. 63
2.4. Выводы по главе. 80
3. Устройство отказоустойчивой маршрутизации сообщений
3.1. Структурно-функциональная организация устройства маршрутизации.
3.2. Анализ функционирования устройства маршрутизации . 98
3.3. Выводы по главе. 120
4. Сравнительная оценка созданного алгоритма маршрутизации
4.1. Экспериментальная оценка потерь сообщений и времени маршрутизации.
4.1.1. Экспериментальная оценка потерь сообщений и времени маршрутизации .
4.1.2. Особенности языка имитационного моделирования. 123
4.1.3. Архитектура инструментальных программных средств. 128
4.1.4. Модель разработанного устройства маршрутизации. 135
4.1.5. Результаты вычислительного эксперимента. 137
4.2. Оценка аппаратной сложности устройства маршрутизации 143
4.3. Оценка времени построения маршрутов. 147
4.4. Выводы по главе. 150
Заключение. 151
Список литературы. 153
Приложения 1 Листинг программы моделирования процедур маршрутизации.
- Классификация архитектур вычислительных систем
- Процедура отказоустойчивой маршрутизации с поворотом «системы координат».
- Анализ функционирования устройства маршрутизации
- Экспериментальная оценка потерь сообщений и времени маршрутизации
Введение к работе
Одной из ключевых задач современной вычислительной техники является обеспечение эффективного межпроцессорного взаимодействия в многопроцессорных системах (мультикомпьютерах). Применительно к-современным мультикомпьютерам (особенно реализуемым в базисе СБИС) эта задача должна решаться с учетом неоднородностей, обусловленных дефектами и отказами процессоров. При этом обмен информацией между работоспособными процессорами должен осуществляться в течение приемлемого времени с минимизацией потерь сообщений и исключением зацикливаний, а затраты на организацию обхода отказов должны удовлетворять заданным ограничениям.
Реализация межпроцессорного взаимодействия согласно указанным условиям требует разработки соответствующих алгоритмов отказоустойчивой маршрутизации сообщений. К настоящему моменту создан целый ряд подобных алгоритмов, ориентированных на мультикомпьютеры с различной топологией и отличающихся правилами обхода отказов (Л.А.Закревский, А.В. Тимофеев, J. Al-Sadi, R.V. Boppana, G.N. Khan, J. Wu, и др.). Основным недостатком большинства этих алгоритмов является значительный дополнительный трафик, возникающий из-за необходимости обновления информации о состоянии процессоров и допустимых направлениях маршрутизации и ведущий к росту потерь сообщений (Л.А.Закревский, А.В. Тимофеев, J. Al-Sadi, J. Wu). Известен алгоритм, не требующий подобных обменов (Е.Г. Анпилогов, И.В.Зотов). Однако его недостатком являются существенные затраты локальной памяти процессоров для хранения таблиц маршрутизации и заранее заданных альтернативных маршрутов обхода. Кроме того, ему свойственно значительное время построения (программирования) сети маршрутов. Многие алгоритмы отказоустойчивой маршрутизации допускают зацикливания сообщений без возможности их отслеживания и предупреждения.
Таким образом, актуальной научно-технической задачей является создание алгоритмов и устройств отказоустойчивой маршрутизации в мультикомпьютерах, обеспечивающих снижение потерь сообщений, не порождающих дополнительного трафика и удовлетворяющих ограничениям по объему памяти таблиц маршрутизации. Целесообразно стремление к разработке таких алгоритмов, которые позволяли бы снизить время программирования сети маршрутов.
Работа выполнена при поддержке гранта «Столетовские гранты -2003» Министерства образования РФ, а также в рамках плана НИР Курского государственного технического университета по единому заказ-наряду Министерства образования РФ в 2003-2006 годах, утвержденному начальником управления планирования и финансирования научных исследований.
Объектом исследования в диссертации являются коммуникационные средства процессорных модулей матричных мультикомпьютеров.
Предмет исследования составляют устройства маршрутизации сообщений в составе указанных коммуникационных средств,
Цель диссертации: снижение потерь сообщений в матричных мультикомпьютерах при одновременном уменьшении предельной емкости памяти таблиц маршрутизации и времени программирования сети маршрутов на основе создания алгоритма отказоустойчивой маршрутизации и реализующего его устройства, использующих новые правила динамического обхода отказов.
Задачи исследований:
Сравнительный анализ известных алгоритмов отказоустойчивой маршрутизации с точки зрения потерь сообщений, аппаратно-программных затрат и сложности построения маршрутов.
Создание алгоритма отказоустойчивой маршрутизации с динамической модификацией маршрутов сообщений на основе новых правил обхода отказов.
3. Разработка принципов функционирования и функциональных схем
устройства отказоустойчивой маршрутизации, реализующего созданный алгоритм.
Исследование на имитационной модели зависимостей коэффициента потерь сообщений и среднего времени их доставки от интенсивности потока сообщений и наработки процессоров на отказ.
Аналитическая оценка предельной емкости памяти таблиц маршрутизации и времени программирования сети маршрутов.
Научная новизна работы:
Разработан алгоритм отказоустойчивой маршрутизации сообщений в матричных мультикомпьютерах, позволяющий снизить потери сообщений при одновременном уменьшении предельной емкости памяти таблиц маршрутизации и времени построения маршрутов на основе использования новых правил отклонения, компенсации и возврата для обхода отказов.
Получены зависимости коэффициента потерь сообщений от интенсивности потока сообщений и наработки процессора на отказ, демонстрирующие как минимум двухкратное снижение потерь сообщений по сравнению с аналогами.
Выполнена аналитическая оценка времени программирования сети маршрутов и предельной емкости памяти таблиц маршрутизации, показывающие минимальное преимущество созданного алгоритма перед лучшими известными аналогами в 1,2 раза и в 4 раза соответственно.
Достоверность полученных результатов обеспечивается применением аппарата математической логики, комбинаторного анализа, методов теории множеств и теории графов, методов теории вероятностей и математической статистики, теории систем массового обслуживания, строгим обоснованием ключевых утверждений, а также результатами имитационного моделирования.
Практическая ценность работы:
Разработанные принципы функционирования устройств маршрутизации позволяют строить коммуникационные средства матричных мультикомпьютеров с более низкими потерями сообщений.
Динамическая модификация маршрутов на основе правил отклонения, компенсации и возврата в созданном устройстве обеспечивает снижение времени построения сети маршрутов минимум в 1,2 раза.
Созданное устройство характеризуется снижением предельной емкости таблиц маршрутизации (в битах) в 4 раза, что позволяет уменьшить аппаратную сложность процессора.
Реализация и внедрение. Результаты диссертационного исследования используются в учебном процессе в Курском государственном техническом университете в рамках дисциплины «Отказоустойчивые многопроцессорные платформы», а также внедрены в филиале ФГУП «Радиочастотный центр центрального федерального округа» в Орловской области и ООО «Кентавр Электронике» (г.Курск), что подтверждается соответствующими актами.
Апробация работы. Основные результаты диссертационной работы докладывались: трижды на Международной НТК «Information and telecommunication technologies - in; intelligent systems» (Barcelona, 2004, Mallorca, 2005, Katania, 2006), на XLI Всероссийской конференции по проблемам математики, информатики, физики и химии (Москва, 2005), на VII Международной НТК «Распознавание-2005» (Курск, 2005), на VIII Международной НТК «Медико-экологические информационные технологии» (Курск, 2005), на XXXIV вузовской НТК студентов и аспирантов «Молодежь и XXI век» (Курск, 2006).
Научные положения, выносимые на защиту: 1. Алгоритм отказоустойчивой маршрутизации сообщений в матричных мультикомпьютерах, основанный на новых аппаратно реализуемых правилах обхода отказавших процессоров и дефектов: отклонения, компенсации и возврата.
2. Принципы функционирования и функциональная схема устройства
отказоустойчивой маршрутизации, реализующего разработанный алгоритм.
Результаты исследования на имитационной модели зависимостей коэффициента потерь сообщений от интенсивности потока сообщений и наработки процессоров на отказ.
Аналитические оценки времени программирования сети маршрутов и предельной емкости памяти таблиц маршрутизации.
Публикации. Основные результаты диссертации опубликованы в 6 статьях, 6 тезисах докладов и защищены патентом на изобретение.
Личный вклад автора. В работах, опубликованных в соавторстве и приведенных в конце автореферата, лично соискателем выполнено следующее: в [1-5] разработаны правила обхода отказавших процессоров при маршрутизации; в [7] изложена методика имитационного моделирования алгоритмов отказоустойчивой маршрутизации; в [8-Ю] разработана процедура маршрутизации сообщений при реализации типовых информационных обменов в управляющих мультикомпьютерах; в [11] спроектированы блоки маршрутизации сообщений микроконтроллерной сети; в [12,13] предложена методика снижения межпроцессорного трафика при разбиении алгоритмов.
Объем и структура работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы, включающего 79 источника и приложений. Работа содержит 166 страниц текста, 45 рисунков и 6 таблицы. Приложения включают 66 страниц.
Области возможного использования. Результаты диссертационной работы могут быть использованы при создании коммуникационных процессоров для коммерческих систем с распределенной памятью, в абонентских системах, а также в системах сбора данных.
Классификация архитектур вычислительных систем
Попытки систематизировать все множество архитектур начались после опубликования М. Флинном первого варианта классификации вычислительных систем в конце 60-х годов [1,2]. Классификация базируется на понятии потока, под которым понимается последовательность команд или данных, обрабатываемая процессором. На основе числа потоков команд и потоков данных Флинн выделяет четыре класса архитектур: SISD, MISD, SIMD, MIMD.
SISD (single instruction stream I single data stream) - одиночный поток команд и одиночный поток данных. К этому классу относятся последовательные компьютерные системы, которые имеют один центральный процессор, способный обрабатывать только один поток последовательно исполняемых инструкций (рис. 1.1). Примерами компьютеров с архитектурой SISD являются большинство рабочих станций Compaq, Hewlett-Packard и Sun Microsystems.
SIMD (single instruction stream I multiple data stream) - одиночный поток команд и множественный поток данных (рис. 1.2). В архитектурах подобного рода сохраняется один поток команд, включающий, в отличие от предыдущего класса, векторные команды. Это позволяет выполнять одну арифметическую операцию сразу над многими данными - элементами вектора. Способ выполнения векторных операций не оговаривается, поэтому обработка элементов вектора может производится либо процессорной матрицей, как в ILLIAC IV, либо с помощью конвейера, как, например, в машине CRAY-1.
MISD (multiple instruction stream I single data stream) - множественный поток команд и одиночный поток данных (рис. 1.3). Теоретически в этом типе машин множество инструкций должно выполнятся над единственным потоком данных. Флинн не смог привести ни одного примера реально существующей системы, работающей на этом принципе. Некоторые авторы в
Попытки систематизировать все множество архитектур начались после опубликования М. Флинном первого варианта классификации вычислительных систем в конце 60-х годов [1,2]. Классификация базируется на понятии потока, под которым понимается последовательность команд или данных, обрабатываемая процессором. На основе числа потоков команд и потоков данных Флинн выделяет четыре класса архитектур: SISD, MISD, SIMD, MIMD.
SISD (single instruction stream I single data stream) - одиночный поток команд и одиночный поток данных. К этому классу относятся последовательные компьютерные системы, которые имеют один центральный процессор, способный обрабатывать только один поток последовательно исполняемых инструкций (рис. 1.1). Примерами компьютеров с архитектурой SISD являются большинство рабочих станций Compaq, Hewlett-Packard и Sun Microsystems.
SIMD (single instruction stream I multiple data stream) - одиночный поток команд и множественный поток данных (рис. 1.2). В архитектурах подобного рода сохраняется один поток команд, включающий, в отличие от предыдущего класса, векторные команды. Это позволяет выполнять одну арифметическую операцию сразу над многими данными - элементами вектора. Способ выполнения векторных операций не оговаривается, поэтому обработка элементов вектора может производится либо процессорной матрицей, как в ILLIAC IV, либо с помощью конвейера, как, например, в машине CRAY-1.
MISD (multiple instruction stream I single data stream) - множественный поток команд и одиночный поток данных (рис. 1.3). Теоретически в этом типе машин множество инструкций должно выполнятся над единственным потоком данных. Флинн не смог привести ни одного примера реально существующей системы, работающей на этом принципе.
Класс SISD разбивается на два подкласса: 1) архитектуры с единственным функциональным устройством, например, PDP-11; 2) архитектуры, имеющие в своем составе несколько функциональных устройств - CDC 6600, CRAY-1, FPS АР-120В, CDC Cyber 205, FACOM VP-200. В класс SIMD также вводится два подкласса: 1) архитектуры с пословно-последовательной обработкой информации - ILLIAC IV, РЕРЕ, BSP; 2) архитектуры с разрядно-последовательной обработкой - STARAN, ICL DAP.
В классе MIMD также вводится два подкласса: 1) вычислительные системы со слабой связью между процессорами (loosely coupled), к которым они относят все системы с распределенной памятью, например, Cosmic Cube, 2) вычислительные системы с сильной связью (системы с общей памятью ightly coupled), к числу которых относятся такие компьютеры, как C.mmp, BBN Butterfly, CRAY Y-MP, Denelcor HEP.
Процедура отказоустойчивой маршрутизации с поворотом «системы координат».
Звездообразная организация узлов и соединений редко используется для объединения процессоров в мультикомпьютерах, но хорошо работает, когда поток информации идет от нескольких вторичных узлов, соединенных с одним первичным узлом, например при подключении терминалов. Общая пропускная способность сети обычно ограничивается быстродействием концентратора, аналогично тому, как сдерживающим элементом в однотипной топологии выступает шина. По производительности эти топологии также идентичны. Основное преимущество звездообразной схемы в том, что конструктивное исполнение узлов на концах сети может быть очень простым.
Еще одним вариантом топологической структуры КС является древовидная топология (рис. 1.9,а). Сеть строится по схеме так называемого строго двоичного дерева, где каждый узел более высокого уровня связан с двумя узлами следующего по порядку более низкого уровня [13,14]. Узел, находящийся на более высоком уровне, принято называть родительским, а два подключенных к нему нижерасположенных узла — дочерними. В свою очередь, каждый дочерний узел выступает в качестве родительского для двух узлов следующего более низкого уровня. Отметим, что каждый узел связан только с двумя дочерними и одним родительским. Если h — высота дерева (количество уровней в древовидной сети), определяемая как max [log2vV] , то такую сеть можно охарактеризовать следующими параметрами: D = 2(h-l);d = 3;l = N-\.
При больших объемах пересылок между несмежными узлами древовидная топология оказывается недостаточно эффективной, поскольку сообщения должны проходить через один или несколько промежуточных звеньев. Очевидно, что на более высоких уровнях сети вероятность «затора» из-за недостаточно высокой пропускной способности линий связи выше. Этот недостаток устраняют с помощью топологии, называемой «толстым» деревом (рис. 1.9,6) [15].
Идея «толстого» дерева состоит в увеличении пропускной способности коммуникационных линий на «прикорневых» уровнях сети. С этой целью на верхних уровнях сети родительские и дочерние узлы связывают не одним, а Поскольку значительная часть научно-технических задач связана с обработкой массивов, вполне естественным представляется стремление учесть это и В топологии ВС, ориентированных на подобные задачи. Такие топологии относят к решетчатым или матричным (mesh), а их конфигурация определяется видом и размерностью массива.
Простейшими примерами для одномерных массивов могут служить цепочка и кольцо. Для двумерных массивов данных наиболее подходит топология плоской прямоугольной матрицы узлов, каждый из которых соединен с ближайшим соседом (рис. 1.10,а). Такая сеть размерности тхт (т = л/Лч имеет характеристики: D = 2(т-1); d = 4;I= 2N- 2т.
Если провести операцию свертывания (wraparound) плоской матрицы, соединив информационными трактами одноименные узлы левого и правого столбцов или одноименные узлы верхней и нижней строк плоской матрицы, то из плоской конструкции получаем топологию цилиндра (рис. 1.10,6). В топологии цилиндра каждый ряд (или столбец) матрицы представляет собой кольцо. Если одновременно произвести свертывание плоской матрицы в обоих направлениях, получим тороидальную топологию сети (рис. 1.10,в). Двумерный тор на базе решетки тхт обладает следующими параметрами:
Создание гиперкуба при большом числе процессоров требует увеличения порядка узлов, что сопряжено с большими техническими проблемами. Компромиссное решение, несколько увеличивающее диаметр сети при сохранении базовой структуры, представляет собой куб из циклически соединенных узлов - куб циклов (рис. 1.11,д) [17]. Здесь порядок узла равен трем при любом размере сети.
Анализ функционирования устройства маршрутизации
Рассмотрим процесс функционирования разработанного устройства. Поскольку устройство предназначено для включения в состав коммуникационной сети мультикомпьютера, его работу будем рассматривать во взаимосвязи с другими аналогичными устройствами (модулями) сети.
Исходное состояние всех регистров, триггеров и счетчиков модуля и всех входящих в его состав блоков является нулевым. В БПМК 148 (рис.3.5) в ячейках с ненулевыми адресами размещены подтаблицы маршрутизации для всех участков, начинающихся данным модулем. Формат слов, хранимых в блоке 128, описан в предыдущей главе.
Поскольку регистры 31.1-31.К БООС 1.1-1.5 (рис.3.2) находятся в нулевом состоянии, на выходах элементов И 35.1-35.К присутствуют сигналы логической единицы, что, в свою очередь, обусловливает наличие нулевого сигнала на выходе элемента НЕ 41, индицирующего отсутствие сообщений в соответствующем БООС. Нулевые сигналы с выходов элементов НЕ 41 БООС 1.1-1.5 обеспечивают нулевой уровень сигнала на втором выходе БАОС 3 (рис.3.1). Нулевой сигнал с прямого выхода триггера 10 запуска блокирует работу БС 9, запрещая формирование на его выходах импульсов синхронизации. Единичный сигнал с инверсного выхода триггера 18 отказа (признак работоспособности текущего модуля) через выходы 28.1-28.8 модуля передается соседним модулям сети и сообщает им о работоспособном состоянии текущего модуля. Аналогичные сигналы поступают на входы 27.1-27.8 модуля с инверсных выходов триггеров 18 отказа соседних модулей. Нулевое состояние регистра 7 обусловливает наличие нулевого уровня сигнала на выходе элемента ИЛИ 17, что, в свою очередь, приводит к блокировке мультиплексора 12. На выходе мультиплексора 12 присутствует сигнал логического нуля (F- О") независимо от сигналов на его первом-восьмом входах.
Так как на всех выходах регистра 7 и на выходе мультиплексора 12 присутствуют сигналы логического нуля, на всех входов блока 4 БММК присутствуют сигналы логического нуля и на его выходах присутствуют сигналы логического нуля.
Единичный сигнал с выхода 4.14.9 (рис.3.1,3.4) настраивает коммутаторы 14.1-14.10 на прием соответствующих полей адресной части сообщения с выхода мультиплексора 2. (Действие остальных сигналов с выходов блока 4 в исходном состоянии несущественно.).
Описанное выше исходное состояние характерно для каждого модуля коммуникационной сети.
Работа коммуникационной сети в целом начинается с момента подачи сообщения на вход 24.1 одного из модулей от обслуживаемого этим модулем процессора. Структура сообщения определена в предыдущей главе (см. выражение (2.5)).
Со входа 24.1 модуля сообщение подается на информационный вход БООС 1.1 (рис.3.1), с которого поступает на информационный вход демультиплексора 32 (рис.3.2). Так как на адресном входе демультиплексора 32 находится единичный код с выходов элементов И 35.1-35.К, сообщение проходит на первый выход демультиплексора 32, откуда через блок элементов ИЛИ 34.1 передается на информационный вход регистра 31.1.
Одновременно с сообщением на вход 24.1 модуля (рис.3.1) и, следовательно, на информационный вход БООС 1.1 поступает импульс синхронизации. Этот импульс проходит (рис.3.2) через элементы И 36.1-36.К, открытые единичными сигналами с выходов соответствующих элементов И 35.1-35.К, и далее через элементы ИЛИ 37.1-37.К поступает на входы синхронизации регистров 31.1-31.К соответственно. В результате задний фронт импульса фиксирует поступившее сообщение в регистре 31.1, подтверждая нулевое состояние регистров 31.2-31 .К.
После записи сообщения в регистр 31.1 на выходе элемента И 35.1 появляется сигнал логического нуля. Этот сигнал совместно с единичными сигналами с выходов элементов И 35.2-35.К поступает на адресный вход демультиплексора 32 и коммутирует его информационный вход со вторым выходом, обеспечивая тем самым возможность записи очередного сообщения в регистр 31.2. Одновременно сигналы с выходов элементов И 35.1-35.К подаются на информационный вход регистра 33 и в виде кода длины очереди сообщений фиксируются в этом регистре по заднему фронту импульса синхронизации, проходящего с информационного входа БООС через элемент ИЛИ 40 и элемент 42 задержки. Кроме того, сигналы с выходов элементов 35.1-35.К поступают на вход элемента И 39, формируют на его выходе нулевой сигнал, который, в свою очередь, устанавливает единичный сигнал на выходе элемента НЕ 41.
Единичный сигнал с выхода элемента 41 БООС 1.1 через второй выход этого блока подается на первый вход БАОС 3 (рис.3.1,3), откуда, в свою очередь, поступает на вход элемента ИЛИ 45 и формирует на его выходе сигнал логической единицы. Тем самым индицируется наличие сообщений по меньшей мере в одном из БООС. Получаемый сигнал через второй выход БАОС 3 (рис.3.1) передается на вход установки триггера 10 запуска и переключает его в единичное состояние. Единичный сигнал с прямого выхода триггера 10 включает БС 9 и на выходах последнего спустя время Дії начинается формирование четырех сдвинутых друг относительно друга последовательностей импульсов синхронизации tb t , t3 и 14. Одновременно код длины очереди сообщений с выхода регистра 33 БООС 1.1 (рис.3.1,3.2) совместно с нулевыми кодами с выходов регистров 33 БООС 1.2-1.9 поступают на соответствующие входы БАОС 3 и формируют на его первом выходе код выбора БООС (код номера БООС, содержащего наибольшую очередь сообщений). Формирование указанного кода происходит путем попарного сравнения кодов длин очередей сообщений L, L2, L3 L9, соответствующих БООС 1.1, 1.2, 1.3 1.9, на элементах сравнения 43.1-43.36 (рис.3.3) и преобразования кодов с выходов указанных элементов с помощью узла 44 постоянной памяти в соответствии с табл.3.1. В рассматриваемом случае наибольшая очередь сообщений имеется в БООС 1.1 (Li=l, Ьг=0, Ьз=0, L4=0, L5=0, Ьб=0, L7=0, Lg=0,L9=0), поэтому на первом выходе БАОС 3 в соответствии со строкой 1 табл.3.1 образуется код "0001".
В то же самое время переход уровня сигнала на инверсном выходе триггера 10 (рис.3.1) из единичного в нулевой воздействует на одновибратор 23, в результате чего на выходе последнего спустя время Ат2 образуется импульс. Этот импульс через элемент ИЛИ 22.2 проходит на вход синхронизации регистра 6.2 и передним фронтом фиксирует в нем сформированный код выбора БООС с первого выхода БАОС 3.
Код выбора БООС "0001" с выхода регистра 6.2 поступает на адресный вход мультиплексора 2 и коммутирует его выход с первым информационным входом, обеспечивая тем самым возможность считывания сообщения из БООС 1.1. Сообщение из регистра 31.1 БООС 1.1 (рис.3.1, 3.2) проходит через мультиплексор 2. С выхода мультиплексора 2, информационное поле I сообщения поступает на информационный вход регистра 6.1, а поля Rot, Next, h, RC, stage, r, F,r , a, Sign адресной части через коммутаторы 14.1-14.10 передаются на первый, второй,..., десятый информационные входы регистра 7. Одновременно код с выхода регистра 6.2 подается на вход дешифратора 8 и преобразуется в соответствующий ему унитарный код (в данном случае в код "000000001", соответствующий БООС 1.1), позволяя в дальнейшем произвести сдвиг очереди сообщений в выбранном БООС.
Экспериментальная оценка потерь сообщений и времени маршрутизации
Сравнение созданного алгоритма с аналогами на предмет потерь сообщений и времени маршрутизации осуществлялось на имитационных моделях массового обслуживания путем проведения вычислительного эксперимента. Эксперимент выполнялся с использованием библиотеки классов и визуальной среды имитационного моделирования на основе аппарата Q-схем, разработанной на кафедре ВТ КурскГТУ под руководством доцента Зотова И.В.
Ниже перечислены основные условия проведения вычислительного эксперимента: 1) мультикомпьютер включает 8x8 процессоров; 2) каждый процессор генерирует пуассоновский экспоненциально распределенный поток сообщений (заявок) с интенсивностью 1/20,1/30, 1/40, 1/50 (1/такт); 3) источник и приемник сообщения, а также его маршрут (если требуется) выбираются случайно с исключением «нереальных» вариантов (например, исключаются маршруты с циклами); 4) процессоры отказывают независимо друг от друга, поток отказов пуассоновский; 5) средняя наработка процессора на отказ составляет 1000, 2000, 3000, 4000, 5000,6000 тактов; 6) предельная длина входных буферов не ограничена.
В ходе моделирования регистрировалось число успешно доставленных сообщений (d), число сообщений, потерянных вследствие фатальной ситуации в алгоритме маршрутизации (/), а также среднее время пребывания сообщения в КС мультикомпьютера (Q). Оценивались следующие алгоритмы маршрутизации: разработанный; алгоритм Е.Г.Аппилогова и И.В.Зотова (квазидинамический алгоритм) [48,43]; алгоритм расширенных уровней безопасности Wu [36,37]; алгоритм распределенного блока восстановления [34]; простой «жадный» алгоритм [20].
Моделирование осуществлялось в предположении, что каждый модуль представляет собой систему массового обслуживания, а их совокупность объединена в сеть. Функционирование каждого модуля описывается моделью на языке Q-схем (Q-схемой), в которой объекты обслуживания (обработки) - сообщения или пакеты - представляются заявками. Сообщения поступают в массовом порядке, моменты их поступления образуют поток, удовлетворяющий свойствам потока Пуассона (простейшего потока). Язык Q-схем - полуформальный графический язык имитационного моделирования. Он прост, универсален и позволяет описывать системы широкого класса [74]. Q-схема - это граф, вершины которого отображают элементы системы (реальные или вспомогательные абстракции), а дуги связывают элементы между собой [75, 59]. Все вершины разделяются на 4 вида в зависимости от того, какой элемент они моделируют. Связи делятся на 2 вида. Графическое изображение используемых базовых элементов для построения Q-схем дано на рис.4.1,а-г.
Элемент, представленный на рис.4.1 ,а, называется генератором заявок. Его функция - моделирование поступления заявок в систему извне в соответствии с некоторым законом распределения. Параметр X определяется законом распределения. Если закон экспоненциальный, то X - это интенсивность потока заявок. При равномерном законе А, - это интервал возможных значений.
Элемент, изображенный на рис.4.1,6, - канал. Его функция - имитация обработки заявки в течение времени, определяемого некоторым законом распределения времени обслуживания заявок.
Элемент, представленный на рис.4.1,в, - накопитель (иногда его называют очередью). Он отображает возможные скопления заявок в схеме. Накопитель характеризуется предельной длиной - L. Она может быть бесконечной (накопитель без потерь) или ограниченной (накопитель с потерей заявок). Также накопитель характеризуется дисциплиной обслуживания заявок. Типовые дисциплины - FIFO (первым пришел -первым ушел) и LIFO (первым пришел - последним ушел), но возможны и иные дисциплины обслуживания, например, случайный выбор заявок или выбор заявок по времени ожидания в очереди.
Элемент, изображенный на рис.4.1,г, - клапан. Он имитирует управление потоками заявок. Например, он может блокировать (или, наоборот, разрешать) прохождение заявок в зависимости от значений некоторых управляющих сигналов, которые поступают от других элементов по управляющим связям.
Связи в Q-схемах делятся на два вида. Информационные связи -изображаются сплошными стрелками (см. рис.4.1) - отображают пути прохождения заявок в системе. Управляющие связи - изображаются пунктирными стрелками - передают управляющее воздействие на элементы Q-схем. На связи накладывается ряд синтаксических и семантических ограничений. Так, генератор (если он не является управляемым) не может иметь входящих связей и должен иметь хотя бы одну выходную информационную связь (для выдачи заявок). Входящие управляющие связи допускаются только у клапанов (минимум - одна связь, максимум не ограничивается). Выходящие управляющие связи допустимы только у каналов и очередей. Число таких связей произвольно.
Базовый набор элементов Q-схем, приведенный на рис.4.1, недостаточно эффективен при построении моделей процедур маршрутизации. Например, только базовыми элементами трудно отобразить случайный выбор накопителей или выборку заявок из очереди по времени их пребывания. Найдется большое число и других подобных ситуаций. В связи с этим в используемой библиотеке [77] было предложено ввести ряд дополнительных элементов с четко определенным синтаксисом и семантикой.
