Метод, алгоритмы и аппаратные средства оперативного переразмещения программ в отказоустойчивых мультикомпьютерных системах тема диссертации и автореферата по ВАК РФ 05.13.05, кандидат наук Борисенко, Юлия Васильевна

• Борисенко, Юлия Васильевна
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Борисенко, Юлия Васильевна

СОДЕРЖАНИЕ

Введение

1 Анализ методов и средств обеспечения отказоустойчивости мультикомпыотерных систем

1.1 Методы, модели и алгоритмы обеспечения отказоустойчивости в

мультикомпютерных системах

1.2 Модели отказоустойчивых мультикомпьютеров

1.3 Методы и алгоритмы размещение задач в параллельных системах

24

1.3.2 Методы и алгоритмы размещения подпрограмм в мультипроцессорных системах

1.4 Анализ путей аппаратной реализации размещения подпрограмм в

мультикомпыотерных системах

1.5 Выводы

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

2.1 Обобщенная постановка задачи переразмещения подпрограмм в

отказоустойчивых мультикомпьютерах

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

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

2.3.1 Алгоритм замены отказавшего процессора резервным

2.3.2 Алгоритм переразмещения с учётом отказа процессора

2.4 Выводы

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

3.1 Принцип аппаратной реализации переразмещения подпрограмм в

отказоустойчивых мультикомпьютерах

3.2 Структурная организация акселератора переразмещения

3.3 Алгоритмы функционирования акселератора

3.4 Устройство замены отказавшего модуля резервным

3.5 Оценка производительности и быстродействия акселератора

3.6 Устройство поиска кратчайшего пути обхода межпроцессорной связи

67

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

3.8 Выводы

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

4.1 Программная модель процедур переразмещения с учётом отказа

процессора и/или отказа линка

4.2 Результаты исследования эффективности алгоритма планирования размещения

4.3 Результаты исследования эффективности алгоритма переразмещения с учётом отказа процессора и/или отказа линка

4.4 Выводы

Заключение

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

Приложение 1

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

Введение

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

Теория отказоустойчивой организации мультикомпьютерных систем достаточно хорошо разработана. Большой вклад в эту область внесли работы отечественных ученых: С.И. Баранова, Вл.В. Воеводина, В.В. Воеводина, Ю.Ю. Громова, A.B. Каляева, И.А. Каляева, И.И. Левина, В.Г. Хорошевского, И.В. Зотова, а также зарубежных ученых: М. Флинна, К. Ванга, Р. Лонг-боттома, Д. Скилликорна и др. Однако вопросы, связанные с распределением резервных ресурсов в структуре системы, локализации отказов модулей и связей, а также перераспределения множества выполняемых подпрограмм в поле работоспособных модулей в этих работах рассмотрены недостаточно.

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

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

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

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

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

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

Объект исследования: отказоустойчивые мультикомпыотерные системы.

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

Работа выполнена по плану инициативных НИР 2009-2013 г.г. кафедры информационных систем и технологий Юго-Западного государственного университета.

Задачи исследований:

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

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

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

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

Результаты, выносимые на защиту, и их научная новизна:

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

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

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

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

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

Практическая ценность результатов исследований:

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

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

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

3. Аппаратная сложность разработанного устройства для всех практически значимых случаев не превышает 106 эквивалентных вентилей (ЭВ), что позволяет использовать его как в существующих, так и в перспективных мультикомпьютерных системах, содержащих десятки-сотни тысяч процессорных модулей (Titan Cray ХК7, IBM BlueGene/Q и т.п.).

1 Анализ методов и средств обеспечения отказоустойчивости мультикомпыотерных систем

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

1.1 Методы, модели и алгоритмы обеспечения отказоустойчивости в

мультикомпютерных системах

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

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

Под с1-отказоустойчивым устройством понимается устройство, которое способно противостоять (парировать) отказам с! элементов.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

10.применение в каждом из процессоров мультиконтроллера многофункционального (многоалгоритмического) динамического автомата (микроконтроллера).

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

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

1.2 Модели отказоустойчивых мультикомпьютеров

Объектом обеспечения отказоустойчивости является мультиконтроллер (МК), представляющий собой композицию набора микроконтроллеров, pea-

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

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

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

Представим структурную модель отказоустойчивого мультиконтроллера (рис. 1.1).

Рис. 1.1. Структурная модель отказоустойчивого мультиконтроллера Ядром отказоустойчивого мультиконтроллера является избыточный МК (ИМК). Для реализации динамического, статического или комбинированного резервирования используется аппаратурная избыточность — избыточное число микроконтроллеров и модулей памяти МК. Условно будем счи-

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

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

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

Для регулярных структур указанные методы могут применяться на уровне как каждого микроконтроллера (рис. 1.3а), так и всего мультиконтроллера в целом (рис. 1.36).

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

а) б)

Рис. 1.3 Уровни резервирования МК при статическом методе: а) для каждого микроконтроллера; б) для всего микроконтроллера

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

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

Мажорирование на уровне мультиконтроллера в сравнении с пассивным резервированием на уровне МК практически не имеет никаких преиму-

ществ. Использование меньшего числа мажоритарных элементов при пассивном резервировании на уровне МК несущественно, так как аппаратурные затраты на указанные элементы несоизмеримы с затратами на микроконтроллеры.

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

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

к

Рис. 1.4. Модель общего скользящего аппаратного и программного резервирований

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

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

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

V

Рис. 1.5. Модель взаимного скользящего резервирования элементов и

программ

На рис. 1.5 стрелки Рь ..., Ра, ..., РА характеризуют настройку каждого из элементов на соответствующую программу из множества {711, ..., тг^, ...,

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

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

Отказоустойчивое устройство с взаимным скользящим резервированием элементов и программных модулей [45] можно представить следующей обобщенной схемой (рис. 1.6).

На рисунке 1.6 блок ОЭ соответствует основным элементам устройства, блок ДЭ - дополнительным, ШН - шине настройки элементов и формирования памяти адресов элементов с соответствующими номерами про-

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

Рис. 1.6. Обобщённая схема устройства с взаимным скользящим резервированием элементов и программных модулей В настоящее время предложен метод скользящего резервирования со сдвигом, позволяющий с некоторой потерей эффективности при распределении программных модулей, но со значительным снижением аппаратурных затрат на построение каждого элемента устройства и СОО реализовать отказоустойчивый МТС Структура избыточного МК для построения отказоустойчивого устройства указанным методом представляет исходную решетку элементов, дополненную столбцом и/или строкой дополнительных элементов. Модель скользящего резервирования со сдвигом заключается в следующем. Для каждого элемента устройства имеются элементы замены, являющегося его соседями. Так, элементами замены для каждого основного элемента могут быть элементы, расположенные справа, вверху и по диагонали вправо (рис. 1.7). Для каждого соседнего элемента аналогичное расположение элементов замены. Граничными элементами замены являются резервные.

Список литературы диссертационного исследования кандидат наук Борисенко, Юлия Васильевна, 2014 год

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

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

2. www.parallel.ru

3. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб.: БХВ-Петербург, 2002. 608 с.

4. Воеводин Вл.В., Капитонова А.П. Методы описания и классификации вычислительных систем. М.: Изд. МГУ, 1994. 103 с.

5. Амамия М., Танака 10. Архитектура ЭВМ и искусственный интеллект. М.: Мир, 1993. 400 с.Корнеев В.В., Киселев A.B. современные микропроцессоры. М.: НОЛИДЖ, 1998.240 с.

6. Корнеев В.В., Киселев A.B. Современные микропроцессоры. М.: НОЛИДЖ, 1998.240 с.

7. Высокоскоростные вычисления. Архитектура, производительность, прикладные алгоритмы и программы Супер ЭВМ / Под ред. Ковалика. -М.: Радио и связь, 1988. - 432 С.

8. Flynn M.J. Some computer organization and their effectivness // IEE-ETC. - 1972. - vol. C-21, №9. - PP. 296-304.

9. Борзов Д.Б. Модели и методы размещения задач в параллельных системах и устройства для их реализации / Д.Б. Борзов. - канд. дис., Курск, 2002

1 O.Virginia Lo, Wanqian Liu. Noncontiguous processor allocation algorithms for mesh-connected multicomputers // IEEE Transactions on parallel and dist. Systems. - 1997. - Vol. 8, №7. - PP. 712-725.

11.Коршунов Ю.М. Математические основы кибернетики. - М.: Энер-гоатомиздат, 1987. - 496 с.

12.Воеводин В.В. Математические модели и методы в параллельных процессах. - М.: Наука., 1986. - 296 с.

13.Anderson G.A., Jensen L.D. Computer interconnection structures, taxonomy, characteristics and examples // Computing Surveys of AC. - 1975. - Vol. 7, №4. -PP. 197-213.

14.Jafari H., Lewis T.G., Spragins J.D. Simulation of a class of ring structured networks // IEEE Transactions on Computers. - 1980. - Vol. C-29, №5. -PP. 385-392.

15.Arden B.W., Lee H. Analysis of chordial ring network // IEEETC. -1981. -Vol. C-30, №4. - PP. 291-295.

16.Reames C.C., Liu M. T. A loop network simultaneous transmission of variable length message // In: 2nd ASCA, Houston, Tex. - 1975. - PP. 7-12.

17.Siegel H.J., McMillen R.J., Mueller P.T. A survey of interconnection methods for reconfigurable parallel processing systems // In: AFIPS Conf. Proc., Washington, D.C. - 1979. - Vol. C-29, №2. - PP. 108-115.

18.Зотов И.В. и др. Организация и синтез микропрограммных мульти-микроконтроллеров. - Курск.: Изд-во «Курск», 1999. - 368 с.

19.Pfister, G. Sizing Up Parallel Architectures [Text] / G Pfister // DataBase Programming & Design OnLine. May 1998, Barak and O. La'adan. Performance of the MOSIX Parallel System for a Cluster of PC's. In Proceedings of HPCN -Europe conference, 1997

20.A.B. Гергель, P.B. Виноградов. Оценка сложности коммуникационных операций в кластерных вычислительных системах / Нижегор. гос. тех. ун-т им. Н.И. Лобачевского - С. 73-77

21. Wittie L.D. Communication structures for large networks of microcomputers // IEEE Transactions on Computers. - 1981. - Vol. C-30, №4. - PP. 264273.

22.K. Windisc, V.M. Lo, B. Bose. Contiguous and noncontiguous processor allocation algorithms for k-ary n-cubes // Proc. Int'l Conf. Parallel processing. -1995.

23.Ma P.R., Lee E.Y.S., Tsuchiya M. A task allocation model for distributed computing systems // IEEE Transactions on Computers. — 1982. — Vol. C-31, №1. — PP. 41-47.

24.Chu W.W., Holloway L.J., Lan M-T., Efe К. Task allocation in distributed data processing // IEEE Computer. — 1980. — №11. — PP. 57-69.

25.Lee Ch.-H., Lee D., Kim M. Optimal task assignment in linear array networks// IEEE Transactions on Computers.— 1992. — Vol. 41, №7. — PP. 877-880.

26.G.S. Rao, ILS. Stone, T.C. Hu. Assignment of tasks in a distributed processor system with limited memory // IEEE Trans. Comput. - C-28 (4), - 1979, -PP. 291 -299.

27.Jo B.-L. et al. Task assignment in homogeneous linear array networks // IEICE Trans. - 1991. - Vol. 74, №9. - PP. 2642-2648.

28.H.S. Stone, S.H. Bokhair. Control of distributed processes // Computer. -1978.-№6.-PP. 97-106.

29.L.M. Ni, К. Hwang. Optimal load balancing strategies for a multiply processor system // Proc. Inernat. Conf. Parallel. Proc. - 1981. - PP. 352 - 357.

30.poGottlieb A., Schawarts J.T. Networks and algorithms for very-large-scale parallel computation // Computer. - 1982. - Vol. 15, JVkl. - PP. 27-36.

31.Шоу А. Логическое проектирование операционных систем. - M.: Мир, 1981.

32.Bokhari Sh. H. On the mapping problem // IEEE Transactions on Computers. — 1981. — Vol. C-30, №3. — PP. 207-214.

33.Sadayappan P., Ercal F. Nearest-neighbor mapping of finite element graphs onto processor meshes // IEEE Transactions on Computers. — 1987. — Vol. C-36, №12. — PP. 1408-1424.

34.K. Efe. Heuristic models for task assignment scheduling in distributed systems // IEEE Comput. - 1982. - 15(6). - PP. 50-56.

35.В.W. Kerninghan, S. Lin. An efficient heuristic procedure for partitioning graph // Bell Syst. Tech J. - 1970. - №2, PP. 291-307.

36.H.S. Stone. Multiprocessor scheduling with the aid of network flow algorithms // IEEE Trans. Software Eng. - 1977. - Vol. SE-3. - PP. 85-93.

37.P. Chuang, N. Tseng. An efficient submesh allocation strategy for mesh computer systems // Proc. 1991 Int'l Conf. Distributed Computer Systems. - 1991. -PP. 256-263.

38.Y. Zhu. Efficient processor allocation strategies for mesh-connected parallel computers // Parallel and distributed computers. - 1992. - Vol. 16. - PP. 328337.

39.Борзов Д.Б., Зотов И.В., Титов B.C. О субоптимальном размещении процессов и данных в кольцевых сетях. - Известия вузов. Приборостроение. - Санкт-Петербург, - 2003, - Т46, №11, С. 48-54.

40.Борзов, Д.Б. Процедура размещения комплексов алгоритмов управления в микроконтроллерных сетях с кольцевой структурой / Д.Б. Борзов, И.В. Зотов // Сборник материалов 4-ой международной конференции «Распознавание^». - Курск, 1999,- С. 137-139.

41.Борзов Д.Б. Устройство поиска нижней оценки размещения в матричных системах / Патент РФ №2275681, БИ № 12; от 27.04.2006.

42.Борзов Д.Б., Зотов И.В., Титов B.C. Устройство для формирования субоптимального размещения и его оценки / Патент РФ №2193796, БИ №33, 2002.

43.Борзов Д.Б., Горощенков Д.С. Устройство планирования размещения задач в системах с кольцевой организацией при направленной передаче информации / Патент РФ №2285289, БИ №28, 2006.

44.Борзов Д.Б. Устройство поиска нижней оценки размещения в матричных системах / Патент РФ №2275681, БИ №12, 2006.

45. Genetic Algorithm Based Parallel Jobs Scheduling / S. Shapovalov, G. Tarasov // In Proceedings of First Russia and Pacific Conference on Computer

Technology and Applications (RPC 2010). - Vladivostok: IACP FEB RAS. - 2010. -P. 211-216.

46.Борзов Д.Б. Метод снижения коммуникационной задержки путем субоптимального размещения задач в матричных базовых блоках кластера // Телекоммуникации. 2008. №4. С. 21-25.

47.Борзов Д.Б., Типикин А.П. Метод ускорения выполнения процедуры планирования размещения задач в кластерных системах / Материалы девятого международного научно-практического семинара «Практика и перспективы развития партнерства в сфере высшей школы» Книга 1. - Таганрог-Донецк. 2008.-С. 31-35.

48.Tanenbaum A.S. Distributed Operation Systems // Prentice-Hall Enge-neering/Science/Mathematics; 1st edition. - 1994.-PP. 1-648.

49.Куперман М.Б., Аверьянов Д.Е. Резервный центр обработки данных. Оценка надежности // Электроника НТБ. 2010. №4. - С. 30-38.

50.George Candea, Shinichi Kawamoto, Yuichi Fujiki, Greg Friedman, Armando Fox. Microreboot - A Technique for Cheap Recovery / Conference «Operating Systems Design and Implementation - OSDI» - Los Angeles. 2004. pp. 31-44.

51.Ope О. Теория графов. — M.: Наука, 1968. — 352 с.

52.Соколова, Ю.В. Переразмещеиие подпрограмм в отказоустойчивых мультипроцессорных системах [Текст] / Ю.В. Соколова, Д.Б. Борзов, В.В. Минайлов // Известия вузов. Приборостроение. - Санкт-Петербург, - 2013, -№6, С. 39-44.

53.Борисенко, Ю.В. Метод и аппаратно-ориентированный алгоритм переразмещения подпрограмм в мультикомпьютерах при отказе процессоров и связей между ними [Текст] / Ю.В. Борисенко, Д.Б. Борзов, А.С. Сизов // Телекоммуникации. - Ежемесячный научно-технический, информационно-аналитический и учебно-методический журнал. - 2013, - №11. С.45-51.

54.Борисенко, Ю.В. Метод оперативного переразмещения подпрограмм в мультиконтроллерах с учетом отказов линков [Текст] / Ю.В. Бори-сенко, Д.Б. Борзов, A.C. Сизов // Известия ЮЗГУ, - 2012, - №6(45), С. 50-54.

55.Борисенко, Ю.В. Акселератор переразмещения подпрограмм в отказоустойчивых мультикомпыотерах [Текст] / Ю.В. Борисенко // Интернет-журнал «Науковедение», - 2013, - №5, С. 1-9.

56.Патент №2447485 Российская Федерация G06F7/76, G06F17/10. Устройство поиска нижней оценки размещения в матричных системах при двунаправленной передачи информации [Текст] /Ю.В. Соколова, Д.Б. Бор-зов, заявл. 11.09.2009; опубл. 10.04.2012, БИ №10, 2012.

57.Патент №2451334 Российская Федерация G06F17/50. Устройство для оценки степени загрузки каналов в системах с древовидной топологической организацией при направленной передаче информации [Текст] / Ю.В. Соколова и др., заявл. 15.03.2011; опубл. 20.05.2012, БИ №14, 2012.

58.Патент №2470357 Российская Федерация. Устройство поиска нижней оценки размещения в полносвязных матричных системах при однонаправленной передаче информации [Текст] / Ю.В. Соколова, Д.Б. Борзов // заявл. 27.12.2010; опубл. 20.12.2012, Бюл. №3.

59.Соколова, Ю.В. Алгоритм переразмещения подпрограмм в отказоустойчивых мультикомпыотерах [Текст] / Ю.В. Соколова, Д.Б. Борзов, И.И. Масюков // Сборник трудов XVIII Международной научно-технической конференции «Машиностроение и техносфера XXI века. Т1». - Донецк, 2012. -С. 101-103.

60.Соколова, Ю.В. Методика пеперазмещения подпрограмм в отказоустойчивых мультикомпьютерах [Текст] / Ю.В. Соколова, Д.Б. Борзов // Сборник трудов XVIII Международной научно-технической конференции «Машиностроение и техносфера XXI века. Т1». - Донецк, 2011. - С. 86-89.

61.Соколова, Ю.В. Организация акселератора вычисления минимального значения коммуникационной задержки в полносвязных матричных мультиконтроллерах [Текст] / Ю.В. Соколова, Д.Б. Борзов, В.В. Минайлов,

A.A. Родин // Сборник материалов XVII Российской научно-технической конференции с международным участием «Материалы и упрочняющие тех-нологии-2010». Часть 2 / Курск, гос. тех. ун-т. Курск, 2010. С. 195-199.

62.Соколова, Ю.В. Переразмещение подпрограмм в отказоустойчивых мультикомпыотерах при отказе связей [Текст] / Ю.В. Соколова, Д.Б. Борзов // Сборник материалов X Международной конференции «Оптико-электроиные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации». - Курск, 2012 - С. 238-240.

63.Соколова, Ю.В. Подход к обеспечению отказоустойчивости в муль-тикомпьютерных системах [Текст] / Ю.В. Соколова, Д.Б. Борзов // 1нженер. Студентський науково-техшчний журнал. - Донецыс: ДонНТУ, 2012. - № 13. -177 с.-С. 84 - 86.

64.Борисенко, Ю.В. Алгоритм оперативного переразмещения подпрограмм в системах логического управления [Текст] / Ю.В. Борисенко // Сборник материалов XI Международной конференции «Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации». - Курск, 2012 - С. 228-230.

65.Соколова, Ю.В. Подход к задаче отказоустойчивого размещения процессоров в мультипроцессорной системе [Текст] / Ю.В. Соколова // тезисы докладов Научно-технической международной молодёжной конференции «Системы, методы, техника и технологии обработки медиаконтента». -Москва, 2011. С. 93.

66.Борисенко, Ю.В. Программа для отказоустойчивого переразмещения подпрограмм в мультикомпыотерах [Текст] / Ю.В. Борисенко, Д.Б. Борзов, A.A. Поляков // Свидетельство о регистрации программы для ЭВМ №2013612984. заявл. 6.02.2013, опубл. 20.03.2013.

67.Борисенко, Ю.В. Программа для отказоустойчивого переразмещения подпрограмм с учетом отказов межпроцессорных связей [Текст] / Ю.В. Борисенко, Д.Б. Борзов, A.A. Поляков // Свидетельство о регистрации программы для ЭВМ №2013612985. заявл. 6.02.2013, опубл. 20.03.2013.

68.Гук М. Аппаратные интерфейсы ПК. - СПб.: Питер, 2003- 528 с.

69.Танэнбаум Э. Архитектура компьютера. 4-е издание. - СПб.: Питер, 2003.- 704 с.

70.Борзов, Д.Б. Интерфейсы периферийных устройств [Текст]: учеб. пособие для вузов / Д.Б. Борзов, И.Е. Чернецкая; Курск гос. тех. ун-т. Курск, 2007. 175 с.

71.Борзов, Д.Б., Аль-Мараят Б.И., Масолов A.C. Метод снижения коммуникационной задержки путем субоптимального размещения задач в матричных базовых блоках кластера / Телекоммуникации. - Ежемесячный научно-технический, информационно-аналитический и учебно-методический журнал.-2008,-№4. С. 21-25.

72.Борзов, Д.Б., Аль-Мараят Б.И., Типикин А.П. Акселератор планирования размещения задач в кластерных вычислительных системах высокой готовности / Известия вузов. Приборостроение. — Санкт-Петербург, — 2008, -№2, С. 29-33.

73.Е. W. Dijkstra. A note on two problems in connexion with graphs. // Numerische Mathematik. V. 1 (1959), P. 269-271

74.А. В. Левитин. Жадные методы: Алгоритм Дейкстры // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Algorithms. — M.: «Вильяме», 2006. — С. 189—195.

75.Шило В.Л. Популярные цифровые микросхемы: Справочник. - Металлургия, Челябинск, 1988. - 352 с.

76. Микросхемы и их применение / Батушев В.А., Вениаминов В.Н., Ковалев В. - М.: Энергия, 1978. - 248 с.

77.Интегральные микросхемы: Справочник / Тарабрин Б.В., Лунин Л.Ф., Смирнов Ю.Н.. - М.: Радио и связь, 1984. -528 с.

78.Петровский И.И. и др. Логические ИС KP 1533, KP 1554: Справочник в 2-х ч. -М.: ТОО «Бином», 1993.

79.Борзов Д.Б., Титов B.C. Параллельные вычислительные системы (архитектура, принципы размещения задач): Монография. - Курск, гос. техн. ун-т, 2008.- 156 с.

80.3отов, И.В. Теоретические основы синтеза схем быстродействующих устройств распределенной децентрализованной координации параллельных микропрограмм в мультиконтроллерах: дис. д-ра техн. наук: 05.13.05: защищена 07.12.2006: утв. 15.03.2007 / Зотов Игорь Валерьевич. -Курск, 2006. - 383 с.