Содержание к диссертации
Введение
1. Коммуникационные процессы и устройства в современной вычислительной технике и системах управления 10
1.1. Значение и виды коммуникационных процессов 10
1.2. Организация коммуникационных устройств и систем 16
1.3. Реализация коммуникационных процессов в условиях наличия отказов и дефектов 21
Выводы 30
2. Принципы организации и алгоритм распределенного отказоустойчивого вещания сообщений 31
2.1.Особенности класса рассматриваемых многопроцессорных систем 31
2.2. Организация межмодульного информационного обмена в рассматриваемых системах. Вещание сообщений 33
2.3. Процедура отказоустойчивого вещания с групповой индексацией приемников сообщения 35
2.3.1. Содержательная характеристика процедуры вещания. Принцип групповой индексации приемников сообщения 35і
2.3.2. Формализованное представление процедуры вещания 39
2.3.3. Структура широковещательного сообщения 41
2.4. Алгоритм отказоустойчивого вещания. Правила обхода отказов 43'
Выводы 49
3. Организация устройства отказоустойчивого вещания-сообщений' 50
3.1. Принципы организации и архитектура устройства вещания
3.2. Структурная организация устройства вещания 52
3.2.1. Организация входного тракта устройства 65
3.2.2. Организация блока анализа ситуаций 69
3.2.3; Организация блока модификации маршрутных кодов 78
3.2.4. Синхронизация работы блоков устройства 86
3.3. Процесс функционирования устройства вещания 88
3.3.1. Исходное состояние 88
3.3.2'. Запуск устройства 90
3.3.3. Вещание сообщений при отсутствии отказов 93
3.3.4. Фаза отклонения 95
3.3.5. Фаза компенсации 97
3.3.6. Фаза возврата 99
3.3.7. Иллюстративный пример 101'
Выводы 112
4. Исследование функциональной эффективности алгоритма и устройства отказоустойчивого вещания 113
4.1. Задачи и методика исследования функциональной эффективности 113
4.1.1. Задачи исследования функциональной эффективности 113
4.1.2. Методика оценки среднего времени передачи сообщений 114
4.1.3. Методика оценки вероятности успешной маршрутизации сообщений 116
4.1.4. Методика оценки аппаратной сложности устройства 117
4.2. Организация и результаты имитационного моделирования 118
4.2.1. Архитектура инструментальных программных средств имитационного моделирования 118
4.2.2. Организация вычислительного эксперимента. Синтез имитационной модели 126
4.2.3. Результаты оценки среднего времени передачи сообщений 129
4.2.4. Результаты оценки вероятности успешной маршрутизации сообщения 131
4.3. Результаты оценки аппаратной сложности устройства 133
Выводы 137
Заключение 138
Библиографический список 140
- Организация коммуникационных устройств и систем
- Организация межмодульного информационного обмена в рассматриваемых системах. Вещание сообщений
- Структурная организация устройства вещания
- Задачи исследования функциональной эффективности
Введение к работе
Актуальность темы. Одним из направлений развития современной вычислительной техники является обеспечение устойчивости вычислительных систем к отказам отдельных устройств, (такие отказы часто называют локальными). Разработаны методы (и средства) быстрого восстановления работоспособности систем при появлении локальных отказов, позволяющие существенно повысить их надежность. Подобные методы особенно широко используются в модульных многопроцессорных системах, имеющих регулярную структурную организацию, в частности, в матричных мультипроцессорах.
Успешное применение методов восстановления работоспособности систем невозможно без соответствующей поддержки на уровне коммуникационных средств, организующих межмодульный обмен информацией, представленной в формате сообщений. Поскольку локальные отказы физически не удаляются из структуры мультипроцессора, эти средства должны обеспечивать возможность их обхода непосредственно при движении сообщений. Для реализации такой возможности разработаны специальные алгоритмы отказоустойчивой маршрутизации, позволяющие передавать сообщения по динамически меняющимся маршрутам, которые перестраиваются при обнаружении новых отказов.
Известно широкое разнообразие подобных алгоритмов маршрутизации (Л.А. Закревский, А.В. Тимофеев, R.V. Boppana, S. Chalasani, J. Duato, D.K. Panda, J. Wu и др.). Они ориентируются на различные классы и топологические структуры систем, используют специфические правила обхода отказов и позволяют реализовать межпроцессорный обмен информацией для разных видов комбинаций отказов. Известные алгоритмы маршрутизации, применяемые в мультипроцессорах, предполагают только попарный обмен сообщениями (uni-cast), в то время как на практике часто возникает необходимость организации так называемых вещательных режимов обмена. К ним относится, в частности, передача сообщения от одного источника нескольким приемникам (broadcast).
Реализация таких режимов известными алгоритмами маршрутизации требует многократной выдачи одного и того же сообщения, что приводит к росту среднего времени передачи сообщений и снижает вероятность их успешной маршрутизации. Преодоление указанного недостатка возможно при условии применения алгоритмов отказоустойчивой- маршрутизации, приспособленных к реализации вещательных режимов обмена сообщениями, и воплощение этих алгоритмов на аппаратном уровне в соответствующих коммуникационных устройствах. Исходя из сказанного, снижение времени широковещательной передачи сообщений при одновременном повышении вероятности их успешной маршрутизации в отказоустойчивых матричных мультипроцессорах является актуальной научно-технической задачей.
Объект исследования: распределенные коммуникационные средства в составе процессорных модулей матричных мультипроцессоров.
Предмет исследования: алгоритмы и устройства отказоустойчивого вещания сообщений в составе указанных коммуникационных средств. '
Диссертационная работа выполнена при поддержке гранта «Столетов-ские фанты — 2003» Министерства образования РФ, а также в рамках плана НИР Курского государственного технического университета по единому заказ-наряду Министерства образования РФ в 2003-2007 годах, утвержденному начальником управления планирования и финансирования научных исследований.
Цель диссертации: снижение среднего времени передачи сообщений и повышение вероятности их успешной маршрутизации в матричных мультипроцессорах при осуществлении вещательных режимов обмена информацией на. основе разработки алгоритма распределенного отказоустойчивого вещания сообщений с групповой индексацией приемников и устройства для его реализации.
Задачи исследований:
Сравнительный анализ известных алгоритмов отказоустойчивой маршрутизации сообщений с точки зрения среднего времени передачи и вероятности успешной маршрутизации в вещательных режимах обмена сообщениями.
Создание алгоритма распределенного отказоустойчивого вещания на основе принципа групповой индексации приемников сообщений.
Определение структурно-функциональной организации и разработка функциональных схем устройства распределенного отказоустойчивого вещания сообщений, реализующего созданный алгоритм.
Исследование зависимостей среднего времени передачи сообщений при реализации вещательных режимов обмена от интенсивности потоков сообщений при фиксированном числе приемников и интенсивности локальных отказов.
Анализ зависимостей числа потерянных сообщений, а также отношения числа потерянных к числу доставленных сообщений при реализации вещательных режимов обмена от интенсивности потоков сообщений при фиксированном числе приемников и интенсивности локальных отказов.
Оценка аппаратной сложности устройства распределенного отказоустойчивого вещания сообщений.
Научная новизна результатов исследований:
Создан алгоритм распределенного отказоустойчивого вещания сообщений в матричных мультипроцессорах, отличающийся использованием упрощённой групповой индексации приёмников и позволяющий снизить среднее время передачи сообщений при одновременном сокращении числа потерянных сообщений в вещательных режимах обмена информацией.
Разработаны структурные и функциональные схемы блоков устройства отказоустойчивого вещания сообщений, отличающиеся применением узлов диспетчеризации и избыточного множества шин, связывающих подмножества логических соседних модулей, и обеспечивающие возможность широковеща-
тельной передачи сообщений с учётом фактического соответствия логических и физических адресов модулей мультипроцессора.
3. На основе расширенного аппарата Q-схем разработана имитационная модель процедуры отказоустойчивого вещания, позволившая получить зависимости среднего времени передачи от интенсивности потоков сообщений; подтверждающие возможность снижения указанного времени широковещательной передачи в 2 и более раз. Установлено, что созданный алгоритм сокращает число потерянных сообщений в вещательных режимах обмена информацией» примерно на 20% при сохранении соотношения числа потерянных и доставленных^ сообщений, не превышающего 0,017.
Достоверность результатов диссертации обеспечивается корректным и обоснованным применением положений и методов математической логики, теории множеств и графов, теории вероятностей, математической статистики теории систем и сетей массового обслуживания, а также подтверждается имитационным моделированием с использованием зарегистрированных в установленном порядке программных средств.
Практическая ценность результатов исследований:
Разработанные алгоритм и устройство отказоустойчивого вещанияхо-общений позволяют строить логически распределенные коммуникационные средства, обеспечивающие снижение среднего времени передачи сообщений и повышение вероятности их успешной маршрутизации при реализации вещательных режимов обмена информацией в матричных мультипроцессорах.
Созданный алгоритм распределенного отказоустойчивого вещания сообщений и реализующее его устройство-не уступают известным аналогам по быстродействию и вероятности успешной маршрутизации в режиме попарного обмена сообщениями.
Аппаратная сложность разработанного устройства отказоустойчивого вещания сообщений соизмерима (по числу вентилей) с аппаратной сложностью известных коммуникационных устройств матричных мультипроцессоров.
На защиту выносятся следующие научные результаты:
Алгоритм распределенного отказоустойчивого вещания, основанный на групповой индексации приемников сообщений и позволяющий снизить среднее время передачи сообщений при одновременном сокращении числа потерянных сообщений в вещательных режимах обмена информацией.
Структурно-функциональные схемы основных узлов устройства, реализующего созданный алгоритм распределенного отказоустойчивого вещания, отличающиеся использованием блоков диспетчеризации сообщений и избыточной системы параллельно работающих шин, объединяющих подмножества логических соседних модулей мультипроцессора.
Имитационная- модель процедуры отказоустойчивого вещания на основе расширенного аппарата Q-схем, позволяющая исследовать зависимости среднего времени передачи сообщений, числа потерянных сообщений; а также отношения числа потерянных к числу доставленных сообщений в вещательных режимах обмена информацией от интенсивности потоков сообщений при фиксированном числе приемников и интенсивности локальных отказов.
Практическое использование результатов работы. Основные научные результаты и выводы диссертационной работы внедрены в ООО «Сайнер-Курск» (г. Курск) и ООО «Пробизнес» (г. Курск), а также используются в учебном процессе на кафедре вычислительной техники КурскГТУ в рамках дисциплин «Теоретические основы проектирования-отказоустойчивых мультимикро-процессоров» и «Моделирование».
Апробация работы. Основные результаты, положения и выводы диссертации обсуждались на Международной научно-технической конференции «Information and telecommunication technologies in intelligent systems» (Spain, Mal-lorca, 2005; Italy, Katania, 2006), на Всероссийской конференции по проблемам математики, информатики, физики и химии (Москва, 2005), на Международной научно-технической конференции «Распознавание-2005» (Курск, 2005), на Международной научно-технической конференции «Медико-экологические ин-
формационные технологии» (Курск, 2005; Курск, 2007), а также на научных семинарах кафедры вычислительной техники КурскГТУ в период с 2003 по 2007 год.
Публикации по теме диссертации. Содержание диссертации опубликовано в 9 работах, среди которых имеется статья в научном издании, входящем в перечень ВАК, а также решение о выдаче патента на изобретение.
Личный вклад соискателя. Все выносимые на защиту научные результаты получены соискателем лично. В опубликованных работах по теме диссертации личный вклад соискателя сводится к следующему: в [8, 23, 25, 53] разработаны различные фазы алгоритма распределенного отказоустойчивого вещания сообщений, а также принципы структурно-функциональной организации и функциональные схемы узлов устройства вещания, в [24] описана методика проведения имитационного моделирования аппаратных средств отказоустойчивой маршрутизации и вещания сообщений на основе аппарата Q-схем, в [15] предложены правила выбора направления выдачи сообщения коммуникационным устройством, в [43] разработан ряд программных модулей визуальной среды для поддержки имитационного моделирования устройств отказоустойчивого вещания, в [41] предложен вариант реализации коммуникационных блоков.
Структура и объем диссертации. Работа состоит из введения, четырех глав, заключения, приложений и списка литературы, включающего 88 наименований. Диссертация содержит 195 страниц текста (включая три приложения) и поясняется 30 рисунками и 5 таблицами.
Организация коммуникационных устройств и систем
Как было показано выше, выполнение программ в многопроцессорных; системах сопряжено с интенсивным.обменом информацией меледу процессорами (на уровне процессов или потоков), что определяет важность выбора рациональной организации коммуникационной: среды, (КС). Основная задача. КС - поддержка высокоскоростного- надежного обмена информацией между любыми модулями [45]. Для этого, необходимо, с одной стороны, грамотное построение отдельных модулей КС, с другой стороны, обоснованный выбор/ее топологии. МодулшКС должны обеспечивать достаточную пропускную способность, при ограниченной: аппаратно-программной сложности. В; настоящее время они строятся основе перекрестных коммутаторов (crossbar), многокаскадных динамических переключателей и статических коммутирующих устройств [46]. Топология КС должна минимизировать расстояние между парами взаимодействующих модулей; и обеспечивать, множество альтернативных маршрутовв целях повышения, потенциальной; отказоустойчивости системы [10].
В зависимости от пространственной организации принято выделять простые и сложные топологии КС [45]. Простые КС (одномерные и двумерные), как правило, представляются плоскими графами и характеризуются ограниченной наращиваемостыо (до 100 узлов). Сложные топологии КС ориентированы на применение в системах с большим числом модулей-(более 100), обеспечивают широкое множество альтернативных маршрутов и простой механизм наращивания в теоретически произвольных пределах. Учитывая постоянный рост числа модулей-в современных системах.при ограниченности числа коммуникационных выводов модуля, интерес представляют КС с многомерной регулярной; (или «почти» регулярной) топологией, включая деревья, матрицы гиперкубы, кубы циклов и т.щ
Распространенным вариантом регулярной топологической: структуры- КС является древовидная, топология (рис. 1.1,а) [10]: Среда строится по схеме двоичного дерева, где каждый узел более высокого уровня связан с двумя узлами следующего j более низкого уровня; Узел, находящийся на более высоком уровне, принято называть родительским, а два подключенных к нему нижерасположенных узла - дочерними. В свою очередь,. каждый дочерний узел выступает в. качестве родительского для двух узлов следующего уровняг
При большой интенсивности обменов между несмежными узлами:древовидная топология оказываетсяшедостаточно эффективной, поскольку сообщения должны проходить через один или несколько промежуточных узлов. Очевидно, что на более высоких уровнях дерева вероятность «затора» из-за недостаточно высокой пропускной способности линий связи выше..Этот недостаток может быть устранен применением топологии так называемого «толстого» дерева (fat tree) (рис. 1.1,6) [46]. Идея топологии «толстого» дерева состоит в увеличении пропускной способности коммуникационных линий на близких к корню уровнях. С этой целью на верхних уровнях родительские и дочерние узлы связывают не одним, а несколькими каналами, причем чем выше уровень, тем больше число каналов.
Принципиально иной топологией, отличающейся от дерева большим числом альтернативных маршрутов, является:матрица (решётка) [11]. Каждый.узел матрицы соединяется только с ближайшими соседями, число которых варьируется. Например, возможно соединение только с четырьмя соседями или с восемью (рис. 1.2,а). Иногда узлы матрицы соединяются с шестью ближайшими соседями.
Узлы крайних строк и/или столбцов могут не соединяться с соседями (в этом случае получается матричная топология с незамкнутыми границами) или, напротив, соединяться с ними в одном или двух измерениях (получается матрица с замкнутыми границами).
Построчное соединение узлов крайних столбцов дает топологию цилиндра (рис. Г.2,б). В топологии цилиндра каждая строка матрицы представляет собой кольцо. Соединение соответствующих узлов крайних столбцов и узлов крайних строк дает тороидальную топологию (рис. 1.2,в).
Примерами вычислительных систем, где реализованы различные варианты матричных топологий, могут служить ILLIACIV, МРР, DAP, СМ-2, Paragon и др. Известны матричные СБИС-мультипроцессоры, например, TTLE64 фирмы Tilera.
При построении систем с очень большим числом процессоров (более 1000) весьма популярна топология гиперкуба, показанная на рис. 1.3. Использование такой топологии позволяет уменьшить диаметр КС и следовательно, среднее время обмена сообщениями. Один из вариантов топологии КС, реализованный.в архитектуре суперЭВМ Cray T3D [21], представляет собой трехмерный тор, образованный объединением процессорных модулей в кольца по трем координатам: х,у и; z. Аналогичная топология используется и в более современных системах, наприт мер, Cray ХТ4 и ЮМ Blue Gene. На рис. 1.3,а изображена КС с топологией четырехмерного гиперкуба (известная как булев гиперкуб).
Гиперкуб, имеющий п измерений, каждое из которых содержит к узлов (N = к"), называется Ь-ичным я-кубом [81]. Каждому узлу назначается п разрядный номер в системе счисления с основанием к, и данный узел связывается с узлом, номер которого отличается только в одной цифре и только на единицу. Этичный и-куб может быть построен путем объединения к экземпляров «Аг-ичных (п -1) -кубов в кольцо.
Организация межмодульного информационного обмена в рассматриваемых системах. Вещание сообщений
Межмодульное взаимодействие в мультипроцессорах рассматриваемого класса обеспечивается путем обмена сообщениями в параллельном коде. Допускается разбиение сообщений на пакеты ограниченной разрядности и их передача за несколько тактов. Каждое сообщение содержит информационную и управляющую (адресную) части. Первая включает данные для передачи приёмнику или множеству приёмников. Вторая содержит адрес приёмника (или адреса приёмников) этих данных, используемый для построения маршрута сообщение в матричной структуре. Дополнительно в сообщение могут включаться и иные поля, например, поля адреса источника сообщения или контрольной суммы.
Основными видами информационного взаимодействия в мультипроцессорах рассматриваемого класса являются попарный обмен сообщениями (uni-cast) и вещание одного сообщения на множество приёмников (broadcast). Поскольку попарный обмен может быть представлен как вещание на- группу из одного модуля, в работе рассматривается только режим вещания. Множество приёмников широковещательного сообщения (область вещания) может иметь произвольную конфигурацию в матричной структуре. Простейший случай — линейная» конфигурация. Размер области вещания ограничивается только размерами матричной структуры.
Поскольку в процессе работы мультипроцессора вероятно появление отказов (а в случае СБИС-систем не исключено наличие производственных дефектов кристалла), процедура вещания должна выполняться с учётом присутствия неоднородностей в физической матричной структуре. Кроме того, вещание необходимо осуществлять в пространстве логических приёмников, отличающемся от исходного пространства физических модулей. Независимо от текущего соответствия логических и физических адресов в матрице (которое изменяется всякий раз, когда обнаруживается новый отказ и производится перестройка логической структуры мультипроцессора) сообщение должно передаваться всем приёмникам, ожидающим широковещательное сообщение. Если сообщение не будет доставлено хотя бы одному приёмнику, вещание считается не выполненным.
Разработанная процедура вещания, предполагает разбиение процесса передачи сообщения на два этапа. На первом этапе осуществляется доставка сообщения от источника до ближайшего (логического) начального модуля области вещания. На втором этапе выполняется широковещательная передача сообщения в пределах логической области вещания. Рассматриваются только линейные области вещания. Если необходима передача сообщения на более сложную по конфигурации область, то она предварительно разбивается на минимальное число непересекающихся линейных областей и для каждой из них выполняется отдельная широковещательная передача.
На первом этапе вещания сообщение движется по фиксированному базовому маршруту. Каждый такой маршрут разбивается-на множество-участков ограниченной длины h , которая зависит от разрядности пакетов. Передача сообщения в пределах участка может выполняться только «по прямой», в одном из восьми возможных направлений: восток, северо-восток, север, северо-запад, запад, юго-запад, юг, юго-восток. Направления идентифицируются целыми числами в возрастающем порядке, от 0 для востока до 7 для юго-востока (восток условно считается базовым направлением).
Участки маршрутов сообщений кодируются в локальных таблицах маршрутизации, которые модифицируются при загрузке выполняемой параллельной программы. Каждый модуль содержит одну такую таблицу. В ней хранится-набор слов с информацией обо всех участках, которые начинаютсяданным модулем. Каждое слово включает три поля: поле направления текущего участка (Rot), поле длины текущего участка (Len), указатель на следующий участок (Next). Поле Rot может принимать одно из восьми возможных значений, от 0 до 7, в зависимости от направления передачи сообщения для данного участка. Длина участка Len определяется соответствующим числом шагов передачи сообщения (трансляций). Указатель Next представляет собой адрес ячейки таблицы маршрутизации конечного модуля текущего участка, в которой размещено слово, представляющее очередной участок, данного маршрута (при отсутствии следующего участка данный указатель нулевой). Таким образом, маршрут любой длины фактически задается в виде распределенного односвязного списка.
При движении сообщения по некоторому маршруту оно последовательно проходит по всем его»участкам пока не поступит в начальный модуль области вещания. При переходе от участка к участку происходит обращение к таблицам маршрутизации, в результате чего в сообщение включаются новые значения полей Rot, Len и Next, соответствующие очередному участку. При отсутствии отказавших модулей на пути следования сообщения направление его движения не меняется на протяжениивсего участка; сообщение движется по прямой, ориентация которой определяется направлением Rot. Bl случае наличия отказов маршрут сообщения- динамически модифицируется согласно сформулированным ниже правилам обхода отказов. Обход отказов при этом выполняется в пространстве физических адресов (логические адреса не учитываются).
Основу второго этапа процедуры вещания составляет принцип групповой индексации приемников, определяющий способ задания областей вещания в -формате сообщений. В соответствии с этим принципом область вещания ( задается тройкой (Cd,Xd,Rd), где Cd -логический адрес ближайшего к источнику начального модуля области d, Xd - линейный размер области d (выраженный числом трансляций),. Rd — направление передачи сообщения при вещании (см. рис.2.3). После каждого шага вещания адрес Cd пересчитывается в зависимости от значения Rd, позволяя идентифицировать следующий модуль-приемник.
Структурная организация устройства вещания
Изображённая на рис.3.2 схема даёт детальное представление реализации первого этапа веи{ания (см. главу 2), являющегося наиболее сложным. Устройство вещания предназначено для работы в составе матричной системы, каждый модуль которой имеет не более восьми непосредственных связей с соседями. Топологическая структура такой системы изображена на рис.3.3. Квадратами.показаны модули (каждый из них включает разработанное устройство вещания), через Ми iV обозначено число соответственно строк и столбцов матрицы.
Устройство отказоустойчивого вещания (рис.3.2) содержит первый 1.1, второй 1.2, третий 1.3, четвертый 1.4, пятый 1.5, шестой 1.6, седьмой 1.7, восьмой 1.8 и девятый 1.9 блоки организации очереди сообщений (БООС), мультиплексор 2, блок 3 анализа очередей сообщений (БАОС), блок 4 анализа ситуаций (БАС), блок 5 модификации маршрутных кодов (БММК), первый 6, второй 7 и третий 8 буферные регистры, дешифратор 9, блок 10 синхронизации (БС), триггер 11 запуска, мультиплексор 12 отказа, демультиплексор 13, первый 14, второй 15, третий 16, четвертый 17 коммутаторы, триггер 18 отказа, первый 19.1 и второй 19.2 блоки элементов И, четвертый элемент ИЛИ 20, первый 21 и второй 22 элементы Щ первый 23, второй 24 итретий 25 элементы ИЛИ; первый 26:1; и второй 26.2 одновибраторы, пятый 27, шестой-28, седьмой 29-и восьмой»30 коммутаторы, третий элемент ИЗ 1.
Назначение элементов и блоков устройства вещания (рис.3;2); состоит в следующем.. Блоки 1.1-1.9 организации очереди сообщений предназначены для приема сообщений с входов 32.1-32.9 модуля:соответственно, временного.хранения и., выдачи сообщений в порядке,их поступления на соответствующие:информационные входы мультиплексора 2, а также ддяиндикации текущей: длины очереди.: сообщений.
Мультиплексор 2 служит для выбора одного из БООС К1-1.9 с целью считывания и передачи на дальнейшую обработку очередного сообщения.
Блок 3 анализа очередей сообщений служит для?формирования кода номера? БООС, содержащего: наибольшую очередь сообщений. Функционирование, БАОС 3 описывается.табл.3.1, в которой: через ІС. обозначена текущая? длина: очереди сообщений в БООС Г./, j є {1,2,...,9}.
Буферный регистр 8 используется для хранения текущих значений полей адресной части сообщения во время его обработки (структура адресной части обсуждалась в предыдущей главе). Регистр 8 имеет выходы 8.1-8.7 и группу выхо-дов-8.8, приэтом выход 8.1 обеспечивает вьщачу значения поля Phase, на выход 8.2 выдается значение nana«Rot," выход 8.3 используется для передачи-значения поля Next, выход 8.4 обеспечивает выдачу значения поля Len, на выходе 8.5 формируется значение поля Step, выход 8.6 обеспечивает вьщачу значения поля Sign, выход 8.7 служит для выдачи значения поля Dev, а через группу выходов 8.8 вьщаютсяфазрядылполя RC (метки-признаки аг выдаются через одноразрядные выходы 8.8.1.г, а коды Z -через трехразрядные выходы 8.8.2.Г (г = 1,/z)).
Дешифратор 9 служит для преобразования кода номера БООС, зафиксированного в регистре 6, в соответствующий унитарный код выбора БООС. Блок 10 синхронизации предназначен для формирования пяти последовательностей импульсов ґ,, t2, Д}, t4 и t5, синхронизирующих работу различных узлов модуля. Формируемые последовательности имеют один и тот же период следования и сдвинуты друг относительно друга на j/i часть периода. Формирование импульсов на выходах БС 10 разрешено при наличии на его входе единичного сигнала. При нулевом сигнале на входе работа БС 10 запрещена. Первый импульс t{ выдается блоком 10 с задержкой, At} относительно момента подачи единичного сигнала на его вход, наименьшее значение которой определяется, длительностью промежутка от момента возникновения единичного сигнала на втором выходе БАОС 3 до момента поступления обрабатываемого сообщения на информационные входы регистров 7,8.
Триггер 11 запуска служит для хранения признака активности текущего модуля (его единичное значение соответствует активному состоянию модуля, а нулевое пассивному). Сигнал с прямого выхода триггера 11 через элемент И 31 управляет включением блока 10 синхронизации.
Мультиплексор 12 отказа используется для передачи- сигнала состояния соседнего модуля с одного из входов 35.1-35.8 модуля на вход 4.14 блока 4 в зависимости от кода на выходе 5.8 блока 5. Передача указанного сигнала состояния на выход мультиплексора 12 возможна только при наличии единичного сигнала на его управляющем входе. Если на управляющем входе мультиплексора 12 присутствует нулевой сигнал, то на его выходе также будет присутствовать нулевой сигнал.
Демультиплексор 13 предназначен для передачи обработанного сообщения на один из выходов 34.1-34.8 модуля и далее одному из соседних модулей в зависимости от кода на выходе 5.8 блока 5.
Коммутаторы 14) 15, 16, 27, 28, 17, 29, 30 обеспечивают передачу полей Phase, Rot, Next, Len, Step, Sign, Dev, RC текущего сообщения на соответствующие информационные входы регистра 8 с выхода мультиплексора 2 или из блока 5 в зависимости от кода управления Хна выходе 4.15 блока 4.
Триггер 18 отказа служит для индикации состояния текущего модуля. Нулевое состояние триггера 18 индицирует работоспособность модуля, единичное состояние указывает на его отказ. Контроль работоспособности модуля и, соответственно, переключение триггера 18 в единичное состояние обеспечивается внешними средствами контроля, воздействующими на этот триггер через вход 37 модуля.
Задачи исследования функциональной эффективности
Основными показателями функциональной эффективности алгоритмов и устройств отказоустойчивого вещания сообщений являются скоростные и надежностные показатели. Для аппаратно реализуемых алгоритмов важным показателем представляется также аппаратная сложность устройства. Однако его значимость для отказоустойчивых систем намного ниже других показателей, в связи с чем аппаратные затраты чаще рассматриваются в качестве ограничения (например: аппаратная сложность отказоустойчивой системы не должна превышать 150% сложности исходной системы).
Вайнейший скоростной показатель- время передачи сообщения. Поскольку указанное время представляет собой случайную величину, зависящую от большого числа факторов (например, от количества передаваемых сообщений, длины маршрутов, числа приемников, распределения отказов на пути следования), целесообразно оценивать его среднее значение с последующим расчетом доверительного интервала для достаточно высокой доверительной вероятности.
Ключевым надежностным показателем является вероятность успешной доставки сообщения, или вероятность успешной маршрутизации. В вещательных режимах обмена сообщение считается доставленным, если оно поступило в каждый приемник области вещания. Для приближенной оценки вероятности успеха достаточно найти отношение числа доставленных сообщений к общему их числу. Не менее информативным показателем является доля потерянных сообщений (т.е. отношение числа потерянных сообщений к числу доставленных), которая косвенно характеризует вероятность неудачи при маршрутизации. Вероятность успешной маршрутизации в наибольшей степени зависит от количества и распределения отказов в мультипроцессоре.
Оценку среднего времени передачи сообщений будем выполнять путем организации вычислительных экспериментов на имитационной модели матричного мультипроцессора, реализующего разработанный алгоритм вещания и аналогичные алгоритмы (построение имитационной модели детально рассматривается в п.4.2.2).
Эксперимент условимся проводить для мультипроцессора с фиксированным числом процессорных модулей, чтобы исключить влияние эффекта размерности. Число модулей установим таким, чтобы обеспечить возможность срабатывания всех ветвей алгоритма вещания (и правил обхода отказов) и в то же время не превысить допустимую длительность процесса моделирования (не более часа на один цикл моделирования). Как показали предварительные исследования, обоим указанным условиям в наибольшей степени соответствует мультипроцессор с организацией 8x8.
Будем считать, что модули мультипроцессора отказывают независимо друг от друга с некоторой постоянной интенсивностью. Интенсивность отказов выберем таким образом, чтобы число отказов;, возникающих за время моделирования, не превышало объема резерва (до 8 отказов). Анализ показывает, что при длительности цикла моделирования порядка 1 часа (что примерно соответствует 2000 тактов на ПЭВМ с процессором Intel Celeron D; работающим на частоте 3,3 ГГц) это условие выполняется при интенсивности отказов 77=1/50000 отказ/тактов. При моделировании следует учитывать вероятность отказа мультипроцессора при небольшом числе отказов (менее 8), что определяется корректирующей способностью выбранного алгоритма реконфигурации логической структуры. Подобные случаи условимся исключать издальнейшей обработки. .
Предположим, что каждый процессорный модуль генерирует пуассонов-ский поток сообщений независимо от других модулей. Интенсивность потока сообщений варьируется и одинакова для всех модулей. Допустим, что модули мультипроцессора вырабатывают только широковещательные сообщения (тем самым можно исключить влияние точечных обменов). Пусть при ЭТОМ ЧИСЛО: приемников сообщения.г одинаково для всех сообщений: Очевидно; что достаточно рассмотреть только случай г = 2, поскольку он является наихудшим для алгоритмов вещания с точки зрения количества передаваемых сообщений (требуется выдача максимального числа сообщений в расчете на. одну пару «передатчик-приемник») и, как следствие, по времени передачи.
Выбор относительного расположения источника и области вещания будем осуществлять случайно. Конфигурации базовых маршрутов вещания также выбираем случайно, исключая избыточные маршруты (содержащие циклы и возвраты). Анализ разработанного алгоритма вещания и правил обхода отказов показывает, что достаточно ограничиться рассмотрением маршрутов, содержащих оті до 3 участков (реализация маршрутов четырьмя и более участками принципиально не отличается от реализации маршрутов, состоящих из трех участков).
Для оценки среднего времени передачи сообщений организуем серию циклов моделирования в соответствии1 с установленными выше условиями и допущениями. В ходе моделирования будем менять интенсивность потока сообщений, а интенсивность отказов оставим постоянной 77=1/50000 отказ/тактов. Для каждого значения интенсивности потока сообщений вьшолним 100 циклов моделирования длительностью по 2000 тактов,и зарегистрируем время пребывания доставленных сообщений в коммутационной среде мультипроцессора. По совокупности полученных значений вычислим среднее и доверительный интервал. Аналогичным образом проведем моделирование известных алгоритмов (аналогов).
Оценку вероятности! успешной маршрутизации-сообщения будем также проводить путем организации вычислительных экспериментов при тех же условиях, которые описаны в п.4.1.2. В ходе моделирования будем менять интенсивность .потока сообщений, интенсивность отказов оставим равной / =1/50000 отказ/тактов. Для каждого значения интенсивности потока сообщений вьшолним 100 циклов моделирования длительностью по 2000 тактов и зарегистрируем число доставленных (d0) и потерянных (/0) сообщений. По совокупности полученных значений вычислим среднее число сообщений./, которые теряются за цикл моделирования, среднее число доставленных сообщений d, а также отношение числа потерянных сообщений к числу доставленных jA. Кроме того, определим процент циклов моделированиям, в которых- не было зарегистрировано потерянных сообщений (величина s отражает относительную частоту появления потерянных сообщений). Аналогичным образом проведем моделирование известных аналогов.
