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

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

Динь Туан Лонг

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

Специальность 05.13.18 - математическое моделирование, численные методы и комплексы программ

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

Москва-2014 I ОКТ

005552970

Работа выполнена в ФБГОУ ВПО «МАТИ - Российский государственный технологический университет имени К.Э. Циолковского»

Научный руководитель:

Официальные оппоненты:

доктор технических наук, профессор Колосков Василий Александрович

доктор физико-математических наук, профессор, заведующий отделом Центра визуализации и спутниковых информационных технологий Научно-исследовательского института системных исследований РАН (НИИСИ РАН) Михайлюк Михаил Васильевич

Ведущая организация:

кандидат технических наук, доцент кафедры «Вычислительные системы и сети» Московского государственного университета путей сообщения (МИИТ)

Желенков Борис Владимирович

федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Санкт-Петербургский государственный электротехнический университет «ЛЭТИ» им. В.И. Ульянова (Ленина)»

Защита состоится « 20 » ноября 2014 г. в 16 ч. 00 мин. на заседании диссертационного совета Д 212.110.08 при ФБГОУ ВПО «МАТИ -Российский государственный технологический университет имени К.Э. Циолковского» по адресу: 121552, Москва, ул. Оршанская, д. 3, ауд. 612А.

С диссертацией можно ознакомиться в библиотеке и на сайте ФБГОУ ВПО «МАТИ - Российский государственный технологический университет имени К.Э. Циолковского» http://www.mati.ru.

Автореферат разослан « 18 » сентября 2014 г.

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

кандидат физико-математических наук

Мокряков А.В.

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

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

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

В настоящее время в России и за рубежом ведутся интенсивные исследования по разработке методов и алгоритмов восстановления работоспособности отказоустойчивых МПС. Проблемы обеспечения отказоустойчивости МПС рассмотрены во многих работах Пархоменко П.П., Хорошевского В.Г., Каравая М.Ф., Авижениса А., Сами М., Лапри, Ву Дж., Таканами и др. авторов.

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

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

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

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

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

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

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

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

2. Разработка композиционной модели клеточного автомата реконфигурации.

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

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

5. Разработка стратегий поиска решений по реконфигурированию на базе естественно-подобной модели среды реконфигурации.

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

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

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

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

Соответствие паспорту научной специальности. Содержание диссертации соответствует п. 3 «Разработка, обоснование и тестирование эффективных вычислительных методов с применением современных компьютерных технологий», п. 5 «Комплексные исследования научных и технических проблем с применением современной технологии математического моделирования и вычислительного эксперимента» и п. 8 «Разработка систем компьютерного и имитационного моделирования» паспорта специальности 05.13.18 - Математическое моделирование, численные методы и комплексы программ.

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

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

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

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

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

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

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

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

Результаты работы использованы: в учебном процессе ФГБОУ ВПО «МАТИ — Российский государственный технологический университет имени К.Э. Циолковского» при обучении студентов по направлению магистерской подготовки 230100 «Информатика и вычислительная техника» в дисциплине «Надежность проектных решений» и в научно-исследовательской работе кафедры по теме «Разработка и исследование распределенных моделей и алгоритмов реконфигурируемых многопроцессорных систем», что подтверждено соответствующими актами.

Апробация работы. Основные положения диссертационной работы докладывались, обсуждались и получили положительную оценку на научно-технических конференциях: XI Международной научно-технической конференции «Проблемы информатики в образовании, управлении, экономике и технике» (Пенза, 2011 г.); IX Всероссийской научной конференции «Информационные технологии, системный анализ и управление» (Таганрог, 2011 г.); конференции с международным участием «Технические и программные средства систем управления, контроля и измерения» УКИ' 12 (Москва, 2012 г.); международной конференции «Информационные технологии в науке, образовании, телекоммуникации и бизнесе» 1Т + ЭЕ' 2012 (Москва, 2012 г.); международной конференции «Параллельные вычисления и задачи управления» РАСО' 12 (Москва, 2012 г. ), X Всероссийской школе-конференции молодых ученых «Управление большими системами» (Уфа, 2013 г.).

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

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

мулированы правила выполнения клеточных операций в ячейке адаптивного маршрутизатора; в [2] предложена имитационная модель управляемой континуальной среды реконфигурации и разработаны клеточные правила вычисления параметров среды; в [3] разработана структура узла токопрово-дящей решетки и клеточные правила вычисления потенциалов и токов на ее основе; в [4] разработан клеточный алгоритм реструктуризации матричной структуры, обеспечивающий поиск решения на основе локальных данных; в [5] рассмотрены варианты клеточных алгоритмов реконфигурации на базе естественно-подобной среды; в [6] выполнены исследования и представлены результаты сравнительного анализа корректирующей способности континуальных, дискретных и логических алгоритмов реконфигурации; в [7] разработаны варианты управления моделью токопроводящей решетки при реализации режимов реконфигурации и маршрутизации в отказоустойчивой многопроцессорной системе; в [8] представлены результаты синтеза асинхронного клеточного автомата реконфигурации; в [9] разработаны дискретные клеточные операции реконфигурации и локализации абонентов в ре-конфигурируемой многопроцессорной структуре; в [10] предложен универсальный подход к поиску решений на основе построения кратчайших путей от источников к приемнику и разработаны клеточные алгоритмы поиска решений на его основе; в [11] представлена структура естественно-подобной модели среды реконфигурации и принципы управления моделью, в [12] рассмотрены результаты моделирования и анализа континуальных клеточных алгоритмов реконфигурации.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, библиографического списка из 89 наименований и двух приложений. Работа изложена на 154 страницах машинописного текста, содержит 61 рисунок и 2 таблицы.

Положения, выносимые на защиту

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

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

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

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

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

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

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

Кратко изложено содержание глав диссертации, апробации и реализации результатов.

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

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

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

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

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

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

структуру МПС настройкой рекон-фигурируемых элементов на новые функции.

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

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

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

Рис.1. Структура самореконфигурируемой МПС

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

Распределенный поиск решений основан на клеточной обработке локальных данных о текущем состоянии элементов {/,/'} (/-1,2,...,т;у'=1,2,...,«) МПС, определяемых переменными х^ 6 {1,0} — отказ/работоспособность узла (/',/) и х1т' е {1,0} - резервный/основной элемент и данных о текущем состоянии клеточного пространства (среды реконфигурации).

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

• Удаленность элемента (/',/) - относительная величина с1ч, характеризующая меру удаленности данного элемента от множества резервных элементов.

• Приращение удапенности элемента (/',_/') - величина и^ (к £ 1,4), соответствующая изменению удаленности элемента (г,у) при перемещении к смежному узлу (р,д) в направлении к.

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

Клетка среды реконфш'ураци

Рис. 2. Композиционная модель клеточного автомата

ю

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

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

В данном разделе рассмотрена клеточная реализация автомата KACq-С целью упрощения вычислений и снижения сложности реализации клетки реконфигурации в качестве автомата /iAcc разработана естественно-подобная идеализированная модель управляемой токопроводящей решетки (ТПР), закономерности функционирования которой позволили получать континуальные значения характеристик dL> и wlkJ.

Узел управляемой решетки в каждом направлении к = 1,4 включает резистор R и ключ связи с соседним узлом, состоянием которого (замкнуто/разомкнуто) управляет переменная у^. Общая точка узла связывает резисторы R с потенциалами Е и 0 через ключи, управляемые переменными Xq1 ,xlr'. Если процессорный элемент отказал (х„ = 1), то узел получает потенциал Е, если процессор используется в качестве резервного (хlr' = 1), то узел подключается к нулевому потенциалу. Получение значений dl> и \уЦ сводится к подключению потенциалов £ и 0 к соответствующим узлам токопроводящей решетки и снятию параллельно установившихся значений потенциалов ср'; и токов во всех узлах.

При проектировании клеточного автомата КАСС, имитирующего модель ТПР, были определены: множество М имен, которое для трех автоматов иерархической композиции (/04УР, КАСС, КАШ) представляется координатами узлов клеточного пространства М = {< i,j >: i = 1,т, j = 1 ,n}; ограничения на структуру связей клетки, которые для автоматов КАУР, КАСС, Опм задаются единым шаблоном соседства T(i,j) = {(/,у),(/',/-/),(;'+ I,j),(i-l,j),(ij+1)}. Алфавит для описания состояний клеток и правила смены состояний зависят от специфики решаемых задач и определялись для каждого подавтомата отдельно.

Алфавит слова состояния Sly автомата КАСС включает множество

описанных выше переменных Sli;- = [xlJ .х]! ,ц>1', I1', Y1'}, а система клеточных операций © = [01; 02} имеет вид:

®1: фи =

Е, О,

4

если Хд Л х1г' = 1,

если х0 А хг — 1,

, 4

(1)

У к * У5-к) / 2_, ^ * ' если ИНаЧе'

к=1

02. ¡ч = | Фк7 - ф?!к, если у^Лу5р_Чк = 1, О, если иначе,

(2)

где е {(у-/),(/',у+/)} - номера смежных узлов для (/',у)-

Клеточные правила 01( 02 позволили на основе локальных данных распределенно вычислять параметры ТПР, соответствующие характеристикам для произвольных комбинаций отказавших и резервных вершин. Примеры реализаций 01; 02 представлены на графовых решетках в виде весов вершин (ср17) и дуг (||) (рис.3).

- резерв / - отказ

Рис.3. Примеры выполнения операций 01;02

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

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

12

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

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

Маршруты фиксируются в автомате КАШ формированием значений маршрутной переменной М^ е {1,0}, отмечающей наличие (М^ — 1) или отсутствие (М= 0) маршрута из узла (/,/) в направлениях к Е (1,2,3,4). Клеточный асинхронный алгоритм реконфигурации представляется системой параллельных клеточных операций 0 = {03,04}, где 03 обеспечивает выбор направления маршрута, 04 управляет состоянием ключей токопрово-дящей решетки при столкновениях маршрутов:

В соответствии с 03 направление следования маршрута (М= 1) выбирается по максимальному исходящему току. Устранение столкновений маршрутов (операция 04) обеспечивается выбором входного маршрута с отрицательным минимальным током и размыканием ключей токопро-водящей среды (у^ — 0) для остальных маршрутов. При однократном запуске композиции (КАСС, КАШ) за одну глобальную итерацию асинхронного алгоритма вычисляются: а) характеристики среды (операции 01;02); б) значения переменных маршрутов (операция 03); в) значения переменных управления ключами (операция 04).

Число инициации работы (КАСС, КАпм) для асинхронного КАПМ определяется числом конфликтов пересечений маршрутов.

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

Маршруты реконфигурации формируются изоляцией соответствующих цепей от остальных узлов ТПР путем разрыва лишних связей сначала на выходах, затем на входах всех узлов клеточного пространства в соответствии с клеточными операциями (05. 06):

®6: Ук

1, если = тах{#})Л(# > 0)

0, если (/'у * тах{/^})Л(и > 0)

5=1,4

¡4 + тс, „пЧ\ллпЧ , если /1к' < О, 1, если {11> = тт(/;;))Л(/У < 0)

5=1,4

О, если (¡и * тт{/;/))А(^ < 0) \.Ук> еСЛИ 7к > °<

(6)

В соответствии с 05 выбор последователя на маршруте выполняется путем разрыва связей с не максимальными вытекающими токами > 0). Выбор предшественника на маршруте (операция 06) осуществляется путем разрыва связей узла с не максимальными и нулевыми втекающими < 0) токами. Глобальная итерация композиции (КАсс,КАим) включает: а) вычисление в КАСс характеристик среды (операции 01;02); б) выбор последователя на маршруте (операция 05 в КАпму, в) корректировку характеристик среды в КАСС по результатам выбора последователя (операции 0г, 02); г) выбор предшественника на маршруте (операция 06 в КАПМ); д) корректировку характеристик среды в КАСС по результатам выбора предшественника (операции 01; 02).

При отсутствии пересечений успешный поиск всех маршрутов выполняется за 2 итерации работы автомата КАПМ и двукратной инициации работы КАСС в ответ на коррекцию связей в ТПР. При появлении пересечений маршрутов под управлением /С4УР инициируется продолжение поиска маршрутов на ограниченном пространстве решетки, которое является дополнением области полученных маршрутов до исходных размеров решетки. Роль маршрутной переменной в итоговом состоянии клеточной решетки выполняет переменная тока, что позволило снизить коммутационную сложность клеточного автомата реконфигурации.

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

Слово состояния автомата КАУР кроме общих для трех подавтоматов переменных ,х1г1, , К'7 включает внутренние локальные переменные, обеспечивающие определение изменения состояния переключателей, выявление изолированных отказавших узлов и завершенности процесса построения маршрутов. Для реализации перечисленных выше функций КАУ? разработаны клеточные операции (07 ч- 015), выполняемые в каждом цикле запуска КАУ? в следующем порядке:

1. Определение изменения состояния переключателей в решетке для текущего состояния композиции {КАСС, КАпм) (операции 07, 08).

2. Сохранение текущего состояния переключателей (операция 09).

3. Выявление завершенности построения маршрутов (операция 012).

4. Выявление изолированных узлов и фатальной комбинации в решетке (операции 01О, 0г1).

5. Формирование решения (операция 014 - для асинхронного алгоритма, операции 013, 015 - для синхронного алгоритма).

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

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

Примеры решений по реконфигурации МПС, полученные в КАУР, представлены на графовых решетках в виде новых логических адресов вершин, принадлежащих маршрутам (рис.4).

Рис. 4. Результаты работы КАУР

Устойчивые состояния клеточных массивов, задающих итоговые значения переменных для асинхронного и синхронного вариантов построения маршрутов, иллюстрирует рис.5. Для каждой клетки представлены: состояние узла (ХО - отказ, Хг -резерв), потенциал (¿/), токи (Н\-Н4) по направлениям (->, Т, А, <-), состояния ключей (51У) по направлениям (-», Т, 4-, «-) и значение переменной маршрута реконфигурации (символ О). Клетки маршрутов выделены цветом.

Х0:00 ХГ 00 хо 01 Хг : 00

и: 39 ,04 50,00

Н1: -10 ,96 17,32

Н?: 0 ,00 0,00

НЗ: 2 ,35 14,19

Н4: 8 ,61 10,96

эк: 01 01 01 01 01 01 01 01

о: 00 00 00 00 01 00 00 00

ХО 00 ХГ 00

32 68

2

12 01.

3 Ой

-17 32

01 01 01 01

00 01 00 00

Х0:00 хг :00 30,43 -8,61 30,43 -19, 57 -2,25 01 01 01 01 00 00 00 00

Х0:00 хг.-ОО

и: 36,69

Н1: 0,88

Н2: -2,35

НЗ: 14,79

Н4: -13,31

БИ: 01 01 01 01

О: 00 00 00 00

Х0:00 хг:00 и: 21,89

Н1: -5,03

Н2: -14,79

НЗ: 21,89

Н4: -2,07

зк: 01 01 01 01 00 00 00 00

Х0:00 хг:00 35,81 6,19 -14,19 8,88 -0,88

о:

ХО 00 хг: 01

и: 0,00

Н1 -50,00

Н2 -21,89

НЗ 0,00

Н4 0,00

5М 01 01 00 01

о: 00 00 00 00

01 01 01 01

00 00 00 00

ХО 00 хг :00

26,93

26,93

-8,88

-23,07

5,03

01 01 01 01

00 00 00 00

ХО 01 ХГ :00

50,00

29,33

23,07

0,00

50,00

01 01 01 01

00 00 00 01

Х0:00 хг:00 29,62 -20,38 -3,06 29,62 -6,19 01 01 01 01 00 00 00 00 ХО:01 ХГ:00 50,00 13,31 19,57 26,04 20,38 01 01 01 01 00 00 01 00

Х0:00 хг:01 0,00 0,00 -29,62 -20,67 -26,93 00 01 01 01 00 00 00 00 Х0:00 хг:00 23,96 2,07 -26,04 23,96 0,00 01 01 01 01 00 00 01 00

хо 00 ХГ 00 хо 00 хг 01

20 67 0 00

20 67 0 00

20 67 -23 9Ь

-12 01 -30 43

-29 33 -20 67

01 01 01 01 01 01 01 01

00 01 00 00 00 00 00 00

1 хо 00 хг 00 ХО 01 хг 00 хо 00 хг 00 ХО 00 хг 00

и: 50,00 50 00 33,33 50 00

от: 01 01 01 01 01 00 00 00 00 01 00 01 01 01 01 01

Н1: 0 00 16 67 0 00 0 00

н7: 0 00 0 00 16,67 0 00

НЗ: 0 00 0 00 0 00 0 00

Н4 ' 0 00 0 00 -16 67 0 00

хо 00 ХГ 00 хо 00 ХГ 00 хо 00 ХГ 00 ХО 01 ХГ 00

и: 50 00 50 00 50 00 50 00

и ЭЙ: Н1 : 01 01 01 0 01 00 01 01 01 0 01 00 01 01 01 0 01 00 00 00 01 0 ои 00

Н2: 0 00 0 00 0 00 0 00

п НЗ: 0 00 0 00 0 00 25 00

Н4: 0 00 0 00 0 00 0 00

X хо 00 хг 00 хо 00 ХГ 00 хо 00 Хг 01 ХО 00 хг 00

и: 50 00 50 00 0 00 25 00

5К: 01 01 01 01 01 01 01 01 01 00 00 00 00 01 00 01

Н1: 0 00 0 00 -2 5 00 и 00

и Н2: 0 00 0 00 0 00 -25 00

НЗ: 0 00 0 00 0 00 0 00

0 00 II 00 0.00

хо 00 Хг. 01 хо 01 ХГ 00 хо 00 Хг 00 ХО 00 хг 01

и: 0 00 50 00 16 67 0 00

5И: 01 00 00 00 00 00 00 01 01 00 01 00 00 00 00 01

Н1: -50 00 0 00 16 67 0 00

Н2: 0 00 0 00 0 00 0 00

НЗ: 0 00 0 00 -16 67 0 00

Н4: 0 00 50 00 0 00 16 67

Рис.5. Устойчивые состояния клеточных массивов

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

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

При исследовании корректирующей способности К(1:~) (относительной доли исправляемых комбинаций из ? отказавших элементов относительно общего числа экспериментов) разработанных континуальных алгоритмов выполнено сравнение с тремя модификациями известных дискретных алгоритмов и двумя вариантами логических алгоритмов реконфигурации. Моделирование выполнялось при варьировании размерности решеток, числа резервных узлов - Ыг, вариантов размещения резервных узлов, числа испытаний для фиксированного количества ; отказов. Величина / изменялась от 1 до предельно допустимой величины, равной числу резервных элементов.

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

Для сравнительного анализа по результатам моделирования выполнен отбор наилучшего известного базового варианта: дискретного алгоритма (03) с устранением конфликтов по числу разрешенных направлений маршрутов. Рис.6 представляет графики зависимости К({) от г для трех вариантов алгоритмов реконфигурации тора 7x7 с семью равномерно размещенными резервными элементами: континуального с асинхронным поиском (К^, континуального с синхронным поиском (К2) и дискретного алгоритма (1>з).

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

1 2 3 4 5 6

Рис.6. Графики корректирующей способности алгоритмов Кг,К2,03

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

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

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

В диссертационной работе получены следующие основные результаты:

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

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

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

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

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

6. Проведено моделирование континуальных клеточных алгоритмов реконфигурации, подтвердившее их корректность и эффективность по сравнению с известными аналогами: снижение вероятности фатального отказа в 8-10 раз; сокращение числа итераций поиска решения в 4 и 2 раза для синхронной и асинхронной стратегий соответственно; уменьшение мощности межклеточных связей в 4 и 1,3 раза для синхронной и асинхронной стратегий соответственно.

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

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

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

информатики в образовании, управлении, экономике и технике». Пенза,

2011.-С. 26-28.

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

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

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

2012.

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

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

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

9. Колосков В.А., Колоскова Г. П., Динь Туан Лонг, Павлюченко Д.В. Адаптивное сетевое управление маршрутизацией в реконфигурируе-мых системах // Мехатроника, автоматизация, управление. 2013. № 8. С. 39-46.

10. Колосков В.А., Павлюченко Д.В., Динь Туан Лонг. Передача сообщений в реконфигурируемой отказоустойчивой многопроцессорной системе // Информационные технологии. 2013, №10. С. 29-35.

11. Павлюченко Д.В., Динь Туан Лонг. Самонастройка функций и связей в отказоустойчивой многопроцессорной системе // Управление большими системами: материалы X Всероссийской школы-конференции молодых ученых. Том 3/ Уфимск. гос. авиац. тех . ун-т. - Уфа:УГАТУ, 2013. С.228-232.

12. Динь Туан Лонг. Моделирование клеточных алгоритмов континуальной среды реконфигурации // ХЬ ГАГАРИНСКИЕ ЧТЕНИЯ. Научные труды Международной молодежной научной конференции в 9 томах. Том 4. М.: МАТИ, 2014. Т. 4, с. 118-120.

Подписано в печать: 05.09.2014

Объем: 1,0 п.л. Тираж: 100 экз. Заказ № 2022 Отпечатано в типографии «Реглет» 119526, г. Москва, Мясницкие Ворота д.1, стр. 3 (495)971-22-77; www.reglet.ru