Клеточные алгоритмы маршрутизации в реконфигурируемых многопроцессорных системах тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат наук Павлюченко, Данила Владимирович

• Павлюченко, Данила Владимирович
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Павлюченко, Данила Владимирович

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

ГЛАВА 1. МЕТОДЫ И АЛГОРИТМЫ МАРШРУТИЗАЦИИ В РЕКОНФИГУРИРУЕМЫХ МНОГОПРОЦЕССОРНЫХ СИСТЕМАХ

1.1. Модели реконфигурации многопроцессорных систем

1.2. Алгоритмы маршрутизации в многопроцессорных системах с отказами

1.3. Концепция клеточной маршрутизации в реконфигурируемых многопроцессорных системах

1.4. Выводы к главе

ГЛАВА 2. КЛЕТОЧНЫЙ АЛГОРИТМ ОТКАЗОУСТОЙЧИВОЙ

МАРШРУТИЗАЦИИ В МНОГОПРОЦЕССОРНЫХ СИСТЕМАХ

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

2.2. Клеточный алгоритм локализации приемника

2.3. Клеточный алгоритм определения доступности приемника

2.4. Клеточный алгоритм поиска минимального маршрута

2.5. Выводы к главе

ГЛАВА 3. КЛЕТОЧНЫЙ АЛГОРИТМ АДАПТИВНОГО УПРАВЛЕНИЯ МАРШРУТИЗАЦИЕЙ В РЕКОНФИГУРИРУЕМОЙ СИСТЕМЕ

3.1. Подход к передаче сообщений при перемещении абонентов

3.2. Клеточный алгоритм коррекции смещений источника в реконфигурируемой структуре

3.3. Клеточный алгоритм поиска приемника в реконфигурируемой структуре

3.4. Примеры вычисления маршрутов при перемещении абонентов

3.5. Выводы к главе

ГЛАВА 4. ИССЛЕДОВАНИЕ КЛЕТОЧНЫХ АЛГОРИТМОВ

МАРШРУТИЗАЦИИ РЕКОНФИГУРИРУЕМЫХ СИСТЕМ

4.1. Описание программы моделирования клеточных алгоритмов маршрутизации

4.2. Исследование алгоритма маршрутизации при фиксированном расположении абонентов

4.3. Исследование алгоритма маршрутизации при перемещении абонентов

1 " '11

4.4. Сравнительный анализ алгоритмов маршрутизации

4.5. Выводы к главе

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

ПРИЛОЖЕНИЕ 1. Клеточные массивы

Введение диссертации (часть автореферата) на тему «Клеточные алгоритмы маршрутизации в реконфигурируемых многопроцессорных системах»

ВВЕДЕНИЕ

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

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

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

1 и*

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

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

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

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

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

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

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

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

Для достижения поставленной цели в диссертационной работе решались следующие задачи:

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

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

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

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

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

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

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

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

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

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

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

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

Апробация работы. Основные результаты диссертационной работы обсуждались на: X Международной научно-методическая конференция «Информатика: проблемы, методология, технологии» (Воронеж, 2010 г.), XXXVI Международной молодежной научной конференции «Гагаринские чтения» (Москва, 2010 г.), XXXVII Международной молодежной научной конференции «Гагаринские чтения» (Москва, 2011 г.), XI Международной научно-технической конференции «Проблемы информатики в образовании, управлении, экономике и технике» (Пенза, 2011 г.), IX Всероссийской научной конференции молодых ученых, аспирантов и студентов «Информационные технологии, системный анализ и управление» (Таганрог, 2011 г.), X Международной конференции молодых ученых «Информационные технологии в науке, образовании, телекоммуникации и бизнесе 1Т + 8Е'2012». (Украина Ялта-Гурзуф, 2012 г.), 3-ей Российской конференции с международным участием «Технические и программные средства систем управления, контроля и измерения» (Москва, 2012

г.), Международной конференции «Параллельные вычисления и задачи управления» РАСО'12 ИПУ РАН (Москва, 2012 г.), X Всероссийской школа-конференция молодых ученых «Управление большими системами» (Уфа, 2013 г.) ХЬ Международной молодежной научной конференции «Гагаринские чтения» (Москва, 2014 г.).

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

Научные положения, выносимые на защиту:

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

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

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

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

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения и списка литературы включающего, 87 источников, а также одного приложения. Работа изложена на 144 страницах, включая приложение, содержит 71 рисунок и 1 таблицу.

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

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

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

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

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

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

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

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

ГЛАВА 1. МЕТОДЫ И АЛГОРИТМЫ МАРШРУТИЗАЦИИ В РЕКОНФИГУРИРУЕМЫХ МНОГОПРОЦЕССОРНЫХ СИСТЕМАХ

1.1. Модели реконфигурации многопроцессорных систем

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

Высокая производительность МПС во многом достигается благодаря применяемым архитектурным решениям, разнообразие которых порождается методами распределения программ и данных между множеством процессоров и способами соединений процессоров друг с другом. Одной из наиболее распространенных классификаций архитектур МПС является таксономия Флинна, представленная в 1966 году [5], в рамках которой основное внимание уделяется способам взаимодействия последовательностей выполняемых команд и обрабатываемых данных. При таком подходе различают четыре основных типа архитектур многопроцессорных систем [6-8]: БКБ, 81МГ), М1БО и М1МЕ).

ОКОД (ЭКБ) - многопроцессорная система с одиночным потоком команд и одиночным потоком данных. Этот класс представлен компьютерными системами с классической фон-Неймановской архитектурой, которые имеют один центральный процессор, способный обрабатывать только один поток последовательно исполняемых команд.

ОКМД (81МО) - многопроцессорная система с одиночным потоком команд и множественным потоком данных. Как правило, эти МПС состоят из большого количества ПЭ, в пределах от 1024 до 16384, которые могут выполнять одну и ту же инструкцию над разными данными в жесткой конфигурации. Такая МПС может обеспечить очень высокую производительность только при решении большого количества одинаковых задач. *

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

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

Поскольку класс М1МЕ) в свою очередь включает различные архитектуры МПС, классификация Флинна была детализирована Р. Хокни [9], в соответствии с которой внутри МГМБ-класса выделены три подкласса: переключаемые (с общей памятью; с распределенной памятью), конвейерные и сетевые (регулярные решетки; гиперкубы; иерархические структуры; с изменяемой конфигурацией).

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

Для современных областей применения таких систем решаются все более ответственные задачи, и ущерб от их отказа может быть очень значительным, что выдвигает в качестве первоочередных (или делает актуальной) разработку моделей и алгоритмов восстановления работоспособности и отказоустойчивой передачи сообщений в отказоустойчивых МПС [10-15].

Базовыми требованиями к используемым подходам к реконфигурированию является поддержка длительного функционирования МПС без прерывания

вычислений при появлении отказов ПЭ и масштабируемости системы независимо

(

от ее размеров, числа и расположения отказавших и резервных элементов [16-27].

4

V*1 л

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

Решение этой задачи возможно различными путями. Так, модель реконфигурации на основе инвариантно-группового анализа [28-30] позволяет создавать избыточную структуру (объемлющий отказоустойчивый граф) системы, сохраняющую заданную структуру МПС для определенного числа отказов элементов.

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

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

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

выполняется центральным органом реконфигурации на основании глобальных

* <

данных о размещении резервных и отказавших узлов.

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

Требованиям масштабируемости и оперативности соответствуют клеточные модели реконфигурации МПС [33-39], основанные на распределенном поиске отображения логических адресов решаемой задачи на множество работоспособных узлов МПС. Клеточные модели реконфигурации основаны на использовании только локальных данных о состоянии элементов МПС и соседнем резервировании исполняемых функций. При соседнем резервировании (¿,/)-ый ПЭ является элементом замены для соседних элементов с номерами: (1 — 1,/), (1 + 1,;), (¿,; — 1), (¿,у + 1). Хранение в ПЭ копий ПМ соседних элементов позволяет оперативно без задержек на перезагрузку ПМ в реконфигурируемой МПС восстанавливать функции элементов. Механизм реконфигурации базируется на вычислении кратчайших непересекающихся маршрутов от отказавших элементов к резервным узлам. Множество элементов маршрутов определяет минимальное подмножество ПЭ, изменяющих логические адреса. Конечные пункты маршрутов соответствуют ближайшим к местам отказов резервным элементам и обеспечивают восстановление исходного числа работоспособных ПЭ. Распределение логических адресов реализуется настройкой каждого ПЭ маршрута на функцию своего предшественника, что заменяет перезагрузку системы автоматической перенастройкой подмножества ПЭ на исполняемые

резервные копии ПМ. Перечисленные функции реализуются клеточной средой реконфигурации МПС.

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

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

1.2. Алгоритмы маршрутизации в многопроцессорных системах с отказами

Под маршрутизацией в общем случае понимается передача сообщения от одного ПЭ другому с максимальной производительностью, согласно заданному методу или алгоритму [40]. Алгоритм маршрутизации реализуется в программно-аппаратной части маршрутизатора — устройства, отвечающего за формирование адресата, которому должен быть передано сообщение [41]. Для поддержки масштабируемости реконфигурируемой МПС алгоритмы маршрутизации должны быть распределенными и решать следующие задачи:

• сбор и распределение информации о состоянии элементов и коммуникационной среды МПС;

• локализация приемника сообщений с учетом его перемещения на этапе реконфигурации;

• формирование оптимальных маршрутов передачи сообщений;

• передача сообщения по выбранному маршруту.

Ключевой характеристикой для распределенных алгоритмов маршрутизации является способ построения маршрута передачи сообщения. Выделяют три основных класса алгоритмов маршрутизации [42-44]:

1. алгоритмы фиксированной и статической маршрутизации;

2. алгоритмы простой маршрутизации;

3. алгоритмы адаптивной маршрутизации.

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

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

Наиболее простой при описанной топологии является локальная маршрутизация с передачей от источника через ПЭ по оси абсцисс пока до достижения столбца, содержащего приемник, затем направление меняется на перпендикулярное, и сообщение передается по оси ординат, пока не достигнет приемника - ХУ-маршрутизация (рис. 1.3.) [45, 46]. При таком подходе нет необходимости формировать таблицы маршрутизации, поскольку в каждом узле в любой момент времени всегда можно вычислить направление передачи сообщения из координат источника и приемника.

Рис. 1.3. Локальная маршрутизация в матричной структуре

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

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

В МПС с решетчатой структурой возможны возникновения двух типов отказов: отказ элемента и отказ каналов связи. В связи с этим существует два подхода к маршрутизации в отказоустойчивых МПС: использование коммутации отказавшего узла и полное исключение отказавшего узла из маршрута (рис. 1.4.).

а) б)

Рис. 1.4. Способы обхода отказов а) обход отказавшего ПЭ б) обход отказавшего ПЭ и его связей

Естественным подходом к организации отказоустойчивой маршрутизации является перенастройка таблиц маршрутизации при возникновении отказов [47, 48]. Для повышения надежности маршрутизации некоторыми авторами предлагается перенастройка таблиц маршрутизации в оффлайн режиме [49]. Этот подход позволяет достигать надежность в 99.99% при возникновении до 10% отказов узлов в системе. Подход, предложенный в статье [49], реализует поиск всех возможных маршрутов с учетом отказов в оффлайн режиме с последующим выбором оптимального из них. Существенным недостатком таких подход является необходимость использования центрального маршрутизатора, а также перезагрузка системы при перенастройке таблиц маршрутизации, что не позволяет добиться безостановочной работы МПС.

Список литературы диссертационного исследования кандидат наук Павлюченко, Данила Владимирович, 2014 год

СПИСОК ИСПОЛЬЗОВАННЫХ источников

1. Chen C.L., Chiu G.M. A fault-tolerant routing scheme for meshes with nonconvex faults // IEEE Transactions on Parallel and Distributed Systems. 2001. Vol. 12(5). P. 467-475.

2. Wu J. A fault-tolerant and deadlock-free routing protocol in 2D meshes based on odd-even turn model // IEEE Transactions on Computers. 2003. Vol. 52(9). P. 1154-1169.

3. Khan G.N., Wei G. Fault-tolerant wormhole routing using a variation of distributed recovery block approach // IEE Proceeding Computers and Digital Techniques. 2000. Vol. 147(6). P. 397-402.

4. Suh Y.J., Dao B.V., Duato J. Software-based rerouting for fault-tolerant pipelined communication // IEEE Transactions on Parallel and Distributed Systems. 2000. Vol. 11(3). P. 193-211.

5. Flynn M.F. Very high speed computing systems // Proc. IEEE 54, 1966. P. 1901-1909.

6. Ларионов A.M., Майоров C.A., Новиков Г.И. Вычислительные комплексы, системы и сети. JL: Энергоатомиздат, 1987.

7. Бикташев Р. А., Князьков B.C. Многопроцессорные системы. Архитектура, топология, анализ производительности: Учебное пособие. Пенза: Пенз. гос. ун-т, 2003.

8. Воеводин В.В., Воеводин В.В. Параллельные вычисления. Серия Научное издание. СПб.: BHV-Санкт-Петербург, 2002.

9. Хокни Р., Джесехоуп К. Параллельные ЭВМ: Архитектура, программирование, алгоритмы. М.: Радио и связь, 1986.

10. Евреинов Э.В. Однородные вычислительные системы, структуры и среды. М: Радио и связь. 1981.

И. Giefers Н., Platzner М. A many-core implementation based on the reconfigurable mesh model I I IEEE Xplore digital library. 2010.

12. Каляев A.B., Каляев И.Л., Левин И.И. Многопроцессорные вычислительные системы с программируемой архитектурой на основе ПЛИС // Вестник ЮНЦ РАН. 2004. С. 24-33.

13. Каляев A.B., Левин И.И. Модульнонаращиваемые многопроцессорные системы со структурно-процедурной организацией вычислений. М.: ООО Янус-К, 2003.

14. Каляев И. А., Левин И.И, Семерников Е.А., Шмойлов В.И. Реконфигурируемые мультиконвейерные вычислительные структуры. Ростов-на-Дону: ЮНЦ РАН, 2008.

15. Коломейко В.В. Проблемы адаптации и реконфигурации многопроцессорных систем повышенной живучести // Штучний штелект. Киев, 2005. №4. С. 217-223.

16. Estrin G. Organization of computer system: the fixed plus variable structure computer // Proc. Western Joint Computer Conf. 1960. №5. P. 33-40.

17. Кузъо M.H., Русин Б.П., Шмойлов В.И. Пульсирующие информационные решетки - новое поколение однородных вычислительных сред // Управляющие системы и машины. Клев, 2004. № 2. С. 23-35.

18. Кочерга М.С., Шмойлов В.И. Построение реконфигурируемых вычислительных систем на однородных вычислительных средах // Вестник Южного научного центра РАН. 2008. Том 4, №2. С. 1-26.

19. Палагин A.B., Опанасенко В.Н. Реконфигурируемые вычислительные системы. Киев: Просвета, 2006.

20. Русин Б.П., Кузъо М.Н., Шмойлов В.И. Реконфигурируемые высокопроизводительные системы на однородных средах // Автоматика и вычислительная техника. Рига, 2000. № 3. С. 72-81.

21. Miller R., Prasanna V.K., Reisis D. I., Stout Q. F. Parallel Computations on Reconfigurable Meshes // IEEE Trans. Comput. 1993. Vol. 42 (6).

22. Ben-Asher Y., Peleg D., Ramaswami R., Schuster A. The Power of Reconfiguration // ШЕЕ Trans. Parallel Distrib. Syst. 1991. Vol. 13(2).

23. Bondalapati K.K.B., Prasanna V.K. Reconfigurable Meshes: Theory and Practice 11 Reconfigurable Architectures Workshop. RAW97.1997.

24. Jang J. W., Park H., Prasanna V.K. An optimal multiplication algorithm on reconfigurable mesh // IEEE Trans. Parallel Distrib. Syst. 1997. Vol. 8(5).

25. Kissler D., Hannig F., Kupriyanov A., Teich J. A highly parameterizable parallel processor array architecture // Proc. of the Int. Conf. on Field Programmable Technology. FPT '06.2006.

26. Fukushi M., Horiguchi S. A self-reconfigurable hardware architecture for mesh arrays using single/double vertical track switches // IEEE Transactions on instrumentation and measurement. 2004. Vol. 53(2).

27. Fukushi M., Horiguchi S. Self-reconfigurable mesh array system on FPGA 11 Proc. of the 15th IEEE Int. Symposium on Defect and Fault-Tolerance in VLSI Systems. DFT'00. 2000.

28. Каравай М.Ф. Минимизированное вложение произвольных гамильтоновых графов в отказоустойчивый граф и реконфигурация при отказах. II. Решетки и k-отказоустойчивость // Автоматика и телемеханика. 2005. №2. С. 175-189.

29. Каравай М.Ф. Минимизированное вложение произвольных гамильтоновых графов в отказоустойчивый граф и реконфигурация при отказах. I. Одно-отказоустойчивые структуры // Автоматика и телемеханика. 2004. №12. С. 159-178.

30. Strano A., Bertozzi D., Trivino F., Sanchez J. L., Alfaro F. J., Flich J. Osr-lite: Fast and deadlock-free noc reconfiguration framework // Proceedings of the International Conference on Embedded Computer Systems: Architectures, Modelling and Simulation. 2012.

31. Хорошевский ВТ. Распределенные вычислительные системы с программируемой структурой // Вестник Сиб. ГУТИ. 2010. №2. С. 3-11.

32. Катаев О.В. Об одном подходе к построению отказоустойчивых бортовых многопроцессорных вычислительных управляющих систем // Искусственный интеллект. 2008. №4. С. 538-544.

33. Колосков В. А., Динь Туан Лонг, Павлюченко Д.В. Самоорганизующаяся среда реконфигурации отказоустойчивого мультиконтроллера // Труды XI Международной научно-технической конференции «Проблемы информатики в образовании, управлении, экономике и технике». Пенза, 2011. С. 26-28.

34. Колосков В.А., Динь Туан Лонг, Павлюченко Д.В. Самореконфигурация в решетчатых структурах многопроцессорных систем // Труды конференции с международным участием «Технические и программные средства систем управления, контроля и измерения» УКИ' 12. М. ИПУ РАН. 2012.

35. Колосков В.А., Динь Туан Лонг, Павлюченко Д.В. Клеточные модели самореконфигурации отказоустойчивых многопроцессорных систем // Труды международной конференции «Информационные технологии в науке, образовании, телекоммуникации и бизнесе» 1Т + БЕ' 2012. Приложение к журналу «Открытое образование». 2012.

36. Колосков В.А., Динь Туан Лонг, Павлюченко Д.В. Клеточные алгоритмы реконфигурации и маршрутизации на базе естественно-подобной среды // Труды международной конференции «Параллельные вычисления и задачи управления» РАСО'12. М. ИПУ РАН. 2012.

37. Павлюченко Д.В. Самонастраиваемая среда управления реконфигурацией мультиконтроллеров // Тезисы докладов XXXVII Международной молодежной научной конференции «Гагаринские чтения». М.: МАТИ, 2011.

38. Римский Д.С, Павлюченко Д.В., Колосков В.А. Построение среды самовосстановления автономной системы // Труды X Международной научно-методической конференции «Информатика: проблемы, методология, технологии», Воронеж, 2010.1

39. Римский Д.С., Павлюченко Д.В. Моделирование клеточной реконфигурации мультиконтроллера // Тезисы докладов XXXVI Международной молодежной научной конференции «Гагаринские чтения». М.: МАТИ, 2010.

40. Столингс В. Современные компьютерные сети. СПб.: Питер, 2003.

41. Тимофеев А.В. Проблемы и методы адаптивного управления потоками данных в телекоммуникационных системах // Информатизация и связь. 2003. №12. С. 68-73.

42. Апраксин Ю.К., Запевалин А.А., Кирюхин В.В. Алгоритмы маршрутизации для сетей с коммутацией сообщений // А и ВТ. 1982. №2. С. 8792.

43. Клейнрок Л. Вычислительные системы с очередями. М.: Мир, 1979.

44. Palagin А. V., Opanasenko V.N. Reconfigurable computing technology // Cybernetics and Systems Analysis. Springer New York, 2007. Vol. 43(5). P. 675-686.

45. Bolotin E., Cidon I., Ginosar R., Kolodny A. QoS architecture and design process for cost effective Network on Chip // CCIT Report №424, Elec. Dept, Technion. 2003.

46. Daneshtalab M., Sobhani A., Mottaghi M.D., Kusha A.A., Navabi Z, Fatemi O. Ant colony based routing architecture for minimizing hot spots in NOCs // Proceedings of the 19th annual symposium on Integrated circuits and systems design. 2006. P. 56-61.

47. Casado R, Bermudez A., Duato J., Quiles F., Sanchez J. A protocol for deadlock-free dynamic reconfiguration in highspeed local area networks // IEEE Transactions on Parallel and Distributed Systems. 2001. Vol. 12(2). P. 115-132.

48. Zhang Z, Greiner A., Taktak S. A reconfigurable routing algorithm for a fault-tolerant 2D-mesh Network-on-Chip // Design Automation Conference. DAC'08. 45th АСМ/ IEEE. 2008. P. 441-446.

49. Fick D., DeOrio A., Chen G., Bertacco V, Sylvester D., Blaauw D. A highly resilient routing algorithm for fault-tolerant NoCs // Proceedings of the Conference on Design, Automation and Test in Europe. DATE'09.2009. P. 21-26.

50. Rantala V., Lehtonen T., Plosila J. Network on Chip Routing Algorithms // TUCS Technical Report. 2006. №779.

51. Dally W.J., Towles B. Principles and practices of interconnection networks // Morgan Kaufman Publishers. New York, 2004.

52. Gomez M.E., Duato J., Flich J., Lopez P., Robles A., Nordbotten N.A., Skeie T., Lysne O. A new adaptive fault-tolerant routing methodology for direct networks. // HiPC 2004, LNCS 3296.2004. P. 462-473.

53. Glass C.J., Ni L.M. The turn model for adaptive routing // J. ACM. 1994. Vol. 41(5). P. 874-902.

54. Ekka A.A., Sahoo B. Fault tolerant real time heterogeneous distributed system: Analysis and design of dynamic scheduling algorithms // LAP LAMBERT Academic Publishing. 2011.

55. Sahoo B., Ekka A.A. Distributed recovery block based fault-tolerant dynamic scheduling scheme for real time heterogeneous distributed system // PDPTA -2007. P. 200-206.

56. Khan G.N., Hura G.S., Wei G. Distributed recovery block based fault-tolerant multicasting // IEEE Canadian Conf. on Electrical and Computer Engineering. 2003. P. 1043-1046.

57. Khan G.N., Hura G.S., Wei G. Distributed recovery block based fault-tolerant routing in hypercube networks // Proc. Canadian Conf. on Electrical and Computer Engineering. Winnipeg, 2002. P. 603-608.

58. Nordbotten N., Gomez M, Flich J., Lopez P., Robles A., Skeie T., Lysne O., Duato J. A fully adaptive fault-tolerant routing methodology based on intermediate nodes // Network and Parallel Computing. Vol. 3222 of Lecture Notes in Computer Science. Heidelberg, 2004. P. 341-356.

59. Ho C.T., Stocbneyer L. A new approach to fault-tolerant wormhole routing for mesh-connected parallel computers // IEEE Transactions on Computers. 2004. Vol. 53(4). P. 427-438.

60. Duato J. A theory of fault-tolerant routing in wormhole networks // Parallel and Distributed Systems, IEEE Transactions. 1997. Vol. 8(8). P. 790-802.

61. Boppana R. V., Chalasani S. Fault-tolerant wormhole routing algorithms for mesh networks // Computers, IEEE Transactions. 1995. Vol. 44(7) P. 848-864.

62. Verbeek F., Schmaltz J. Automatic verification for deadlock in Networks-on-Chips with adaptive routing and wormhole switching // Proceedings of Networks-on-Chips Symposium. NOCS' 11. 2011.

63. Ладыженский Ю.В., Мирецкая В.А. Моделирование алгоритмов маршрутизации в сетях на кристалле // HayKOBi пращ Донецького нацюнального техшчного ушверситету, cepia «1нформатика, юбернетика та обчислювальна техшка». Донецк: ДонНТУ, 2008. Вып. 9(132). С.79-86.

64. Jovanovic S., Tanougast С., Weber S., Bobda С. A new deadlock-free fault-tolerant routing algorithm for NoC interconnections // International Conference on Field Programmable Logic and Applications. FPL'09.2009. P. 326-331.

65. Dally W.J., Seitz C.L. The torus routing chip // Distriduted Computing. 1986. Vol. 1(3). P. 187-196.

66. Glass C.J., Ni L.M. Fault-tolerant wormhole muting in meshes // Int'l Symp. Fault-Tolerant computing. 1993. P. 240-249.

67. Duato J. A Necessary and sufficient condition for deadlockfree adaptive routing in wormhole networks // IEEE Trans. Parallel and Distributed Systems. 1995. Vol. 6. P. 1055-1067.

68. Duato J., Yalamanchili S., Ni L.M. Interconnection networks: An engineering approach // CA: Morgan Kauf-mann Publishers. San Francisco, 2003.

69. Duato J., Lysne O., Pang R., Pinkston T. Part I: A theory for deadlock-free dynamic network reconfiguration // IEEE Trans. Parallel Distrib. Syst. 2005. Vol. 16(5). P. 412-427.

70. Lysne O., Pinkston Т., Duato J. Part H: A methodology for developing deadlock-free dynamic network reconfiguration processes // IEEE Trans. Parallel Distrib. Syst. 2005. Vol. 16(5). P. 428-443.

71. Wu J. Fault-tolerant adaptive and minimal routing in mesh-connected multicomputer^ using extended safety levels // IEEE Transactions on Parallel and Distributed Systems. 2000. Vol. 11(2). P. 149-159.

72. Zhou J.P., Lau F.C.M. Adaptive fault-tolerant wormhole routing in 2D meshes // 15th Annual International Parallel and Distributed Processing Symposium. San Francisco, 2001. P. 56-61.

73. Sui P.H., Wnag S. D. An improved algorithm for faulttolerant wormhole routing in meshes // IEEE Trans. Comput. 1997. Vol. 46(9). P. 1040-1042.

74. Kim S.P., Han T. Fault-tolerant adaptive wormhole routing in 2D mesh // IEICE Trans. Inform. Syst.E81-D(10). 1998. P. 1064-1072.

75. Boppana R. V., Chalasani S. Fault-tolerant wormhole routing algorithms for mesh networks // IEEE Trans. Comput. 1995. Vol. 44(7). P. 848-864.

76. Chalasani S., Boppana R.V. Communication in multicomputers with nonconvex faults // IEEE Trans. Comput. 1997. Vol. 46(5). P. 616-622.

77. Gu H., Zhang L., Wang K., Liu Z., Kang G. Enhanced fault tolerant routing algorithms using a concept of "balanced ring" I I Journal of Systems Architecture. 2007. №53. P. 902-912.

78. Shih J.D. Fault-tolerant wormhole routing in torus networks with overlapped block faults // IEEE Proc. Comput. Digit. Tech. 2003. Vol. 150(1). P. 29-37.

79. Shih J.D. A fault-tolerant wormhole routing scheme for torus networks with nonconvex faults // Inform. Process. Lett. 2003. Vol. 88(6). P. 271-278.

80. Sudhanshu K.J., Prasanta K.J. A new distributed approach for building balanced ring for fault tolerance in mesh architecture // International Conference on Methods and Models in Computer Science. 2009.

81. Di Caro G., Dorigo M. AntNet: Distributed stigmergetic control for communications networks // Journal of Artificial Intelligence Research. 1998. №9. P. 317-365.

82. Ладыженский Ю.В., Мирецкая B.A. Исследование муравьиных алгоритмов маршрутизации в компьютерных сетях // 1нтернет-Ос1вта-Наука-2006,

п'ята \ижнародна конференцш ЮН-2006. Зб1рник матер1ал1в конференцп. Том 2. Вшниця: УНГВЕРСУМ-Вшниця. 2006. С. 375-377.

83. Малышев А.В. Адаптационный алгоритм самоорганизации обменных взаимодействий в мультимикроконтроллерной сети // Тез. докл. Международной научной конференции «XXVIII Гагаринские чтения». М., 2002.

84. Савенков Н.А., Колосков В.А. Алгоритм адаптивной маршрутизации в многопроцессорных управляющих сетях // Труды V Междунар. конф. «Идентификация систем и задачи управления» БГСРЯО'Об. М., Институт проблем управления им. В.А. Трапезникова РАН. 2006. С. 1312-1329.

85. Павлюченко Д.В., Динь Туан Лонг, Колосова Г.П. Клеточные модели поиска непесекающихся подсеток в многопроцессорных системах // Труды IX Всероссийской научной конференции «Информационные технологии, системный анализ и управление». Таганрог, 2011. Т.1. С. 207-215.

86. Павлюченко Д.В., Динь Туан Лонг, Колосков В.А. Клеточные модели оптимальной маршрутизации в многопроцессорных системах с отказами // Труды IX Всероссийской научной конференции «Информационные технологии, системный анализ и управление». Таганрог, 2011. Т.1. С. 196-207.

87. Колосков В.А., Колоскова Г.П., Лонг Динь Т. Управляемая клеточная непрерывная среда самореконфигурации многопроцессорных систем // Информационные технологии. 2012. №9. С. 22-27.

ПРИЛОЖЕНИЕ 1. Клеточные массивы

Клеточные массивы к рис. 4.19.

0 гезиУод ]

1 1 0 1 э 1 э 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

2 5 5 5 5 6 6 6 6 7 7 7 7 6 6 6 6 5 5 5 5 4 4 4 4

3 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

5 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0

6 4 4 4 4 0 0 0 0 6 6 6 6 5 5 5 5 4 4 4 4 3 3 3 3

7 р 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

9 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0

10 0 0 0 0 4 4 4 4 0 0 0 0 4 4 4 4 3 3 3 3 2 2 2 2

11 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1

14 2 2 2 2 3 3 3 3 4 4 4 4 3 3 3 3 2 2 2 2 1 1 1 1

15 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

16

17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

18 3 3 3 3 4 4 4 4 5 5 5 5 4 4 4 4 3 3 3 3 2 2 2 2

19 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

20

21 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

22 4 4 4 4 5 5 5 5 6 6 6 6 5 5 5 5 4 4 4 4 3 3 3 3

23 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 result Jog

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

2 5 5 5 5 4 4 4 4 5 5 5 5 6 6 6 6 7 7 7 7 6 6 6 6

3 A 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

T 5 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0

6 4 4 4 4 3 3 3 3 4 4 4 4 0 0 0 0 6 6 6 6 5 5 5 5

7 o 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0

9 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0

10 3 3 3 3 2 2 2 2 0 0 0 0 6 6 6 6 5 5 5 5 4 4 4 4

11 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

12

13 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0

14 2 2 2 2 1 1 1 1 0 0 0 0 5 5 5 5 4 4 4 4 3 3 3 3

15 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

16

17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

18 3 3 3 3 2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 4 4 4 4

19 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

20

21 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

22 4 4 4 4 3 3 3 3 4 4 4 4 5 5 5 5 6 6 6 6 5 5 5 5

23 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 result Jog

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

2 6 6 6 6 7 7 7 7 6 e 6 6 5 s 5 5 4 4 4 4 5 5 5 5

3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

1 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

6 5 5 5 5 6 6 6 6 7 7 7 7 6 6 6 6 5 5 5 5 4 4 4 4

7 o 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

o 9 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0

10 4 4 4 4 s 5 5 s 6 6 6 6 7 7 7 7 0 0 0 0 3 3 3 3

11 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

12

13 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0

14 3 3 3 3 0 0 0 0 5 5 5 5 0 0 0 0 1 1 1 1 2 2 2 2

15 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1

16

17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

18 4 4 4 4 5 5 5 5 4 4 4 4 3 3 3 3 2 2 2 2 3 3 3 3

19 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

20

21 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

22 5 5 S 5 6 6 6 6 5 5 5 5 4 4 4 4 3 3 3 3 4 4 4 4

23 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

KjieTOHHBiíi MaccHB k pnc. 4.21.

B resultJog |

1 0 0 0 0 0 0

2 3 3 3 3 2 2 2

3 0 0 0 0 0 0 0

4

5 0 0 0 0 0 1

6 2 2 2 2 1 1 1

7 o 0 0 0 0 0 0 0

9 0 0 0 0 0 0

10 3 3 3 3 2 2 2

11 0 0 0 0 0 1 0

12

13 0 0 0 0 0 0

14 4 4 4 4 3 3 3

15 1 0 0 0 0 1 0

16

17 0 0 0 0 0 0

1S 5 5 s 5 4 4 4

19 0 0 0 0 0 0 0

20

21 0 0 0 0 0 0

22 4 4 4 4 3 3 3

23 0 0 0 0 0 0 0

000 000 000 000

2 3333 4444 5555 4444

0 0000 0000 0000 0000

000 100 000 000

1 2222 0000 4444 3333 0 0000 0000 0000 0000

100 000 000 100

2 0000 6 6 6 6 5555 0000 0 0000 0000 0000 0000

100 000 010 000

3 0000 7 7 7 7 6666 5555 0 0000 0000 1000 1000

000 000 000 000

4 5555 6666 7777 6666 0 0000 0000 0000 0000

000 000 000 000

3 4444 5555 6666 5555

0 0000 0000 0000 0000

3 геэЛ.к>д |

1 0 0 0

2 9 9 9

3 0 0 0

4

5 0 0 0

б 8 8 8

7 0 0 0

8 9 0 0 0

10 7 7 7

11 0 0 0

12

13 0 0 0

14 « б 6

15 0 0 0

16

17 0 0 0

18 5 5 5

19 0 0 0

20

21 0 0 0

22 б б б

23 0 0 0

24

25 0 0 0

26 7 7 7

27 0 0 0

28

29 0 0 0

30 8 8 8

31 0 0 0

32

33 0 0 0

34 9 9 9

35 0 0 0

36

37 0 0 0

38 10 10

39 0 0 0

О О 8 3 О О

0 1 7 7

1 О

ООО 6 6 6 6 0 0 0 0

ООО

5 5 5 5

0 0 0 0

ООО

4 4 4 4

0 0 0 0

ООО

5 5 5 5 0 0 0 0

ООО 8 8 9 8 0 0 0 0

ООО 5 5 5 5 0 0 10

ООО 4 4 4 4

10 0 0

ООО в 5 5 5 0 0 0 0

ООО

е в в в 0 0 0 0

0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ООО

8 8 8 8 0 0 0 0 8 8 8 8 9 9 9 9 8 8 8 8 9 9 9 9 10 10 10 10

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ООО 0

ООО 7 7 7 ООО

10 0

0 0 0 0

0 0 0 0

ООО

3 3 3 3

10 0 0

ООО

4 4 4 4 0 0 0 0

ООО

5 5 5 5 0 0 0 0

О О О О О О

О О 2 2 О 1

0 0 1 1111

0 0 0 0

ООО

2 2 2 2

0 0 0 0

ООО

3 3 3 3 0 0 0 0

ООО

4 4 4 4

0 0 0 0

ООО 9 9 9 ООО

О О 6 « о о

о о

7 7 0 0

ООО 8 8 8 8 0 0 0 0

10 0 0 0 0 0 О ООО

ООО

4 4 4 4 0 0 0 0

ООО

5 5 5 5 0 0 0 0

ООО

7 7 7 7

0 0 0 0

10 0

0 0 0 0

0 0 0 0

ООО

3 3 3 3 0 0 0 0

ООО

4 4 4 4 0 0 0 0

ООО

5 5 5 5 0 0 0 0

ООО

6 6 в « 0 0 0 0

ООО

6 6 6 6

0 0 0 0

ООО

5 5 5 5

0 0 0 0

ООО

4 4 4 4 0 0 0 0

ООО

5 5 5 5 0 0 0 0

ООО

8 8 8 8

0 0 0 0

ООО

7 7 7 7

0 0 0 0

ООО

6 6 6 €

0 0 0 0

ООО 5555

0 0 0 0

ООО

б б 6 б

0 0 0 0

ООО

7 7 7 7 0 0 0 0

ООО

8 8 8 3 0 0 0 0

ООО

9 9 9 9 0 0 0 0

ООО

9 9 9 9

0 0 0 0

ООО

8 8 8 8

0 0 0 0

ООО

7 7 7 7

0 0 0 0

ООО

6 6 6 6

0 0 0 0

ООО

7 7 7 7 0 0 0 0

ООО

8 8 8 8 0 0 0 0

ООО

9 9 9 9 0 0 0 0

ООО

10 10 10 10 0 0 0 0

10 10 10 10 11 11 11 11 0000 0000

В nantJofl I

1 0 0 0

2 10 10

3 0 0 0

4

5 0 0 0

б 9 9 9

7 0 0 0

8

9 1 0 0

10 0 0 0

11 0 0 0

12

13 1 0 0

14 0 0 0

15 0 0 0

16

17 0 0 0

18 6 6 6

19 0 0 0

20

21 0 0 0

22 7 7 7

23 0 0 0

24

25 0 0 0

26 8 8 8

27 0 0 0

28

29 0 0 0

30 9 9 9

31 0 0 0

32

33 0 0 0

34 10 10

3S 0 0 0

36

37 0 0 0

33 11 11

39 0 0 0

0 10 8 S 8 8 10 0 0

ООО 7 7 7 7 0 0 0 0

10 0 0 0 0 0 0 0 0 0

10 0 0 0 0 0 0 0 0 0

ООО

6 б е б 0 0 0 0

ООО