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

• Автор: Абуджахал Асаад Абдаллах
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Курск
• Количество страниц: 137 с. : ил.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ.

1. ОБЕСПЕЧЕНИЕ ДЕФЕКТОУСТОЙЧИВ ОСТИ МНОГОПРОЦЕССОРНЫХ СИСТЕМ.

1.1. Структурная организация многопроцессорных

систем

1.2. Обеспечение отказоустойчивости процессорных матриц.

1.3. Анализ способности систем к реконфигурированию и основные задачи исследований

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

2. АЛГОРИТМ ВЫДЕЛЕНИЯ ПОДСЕТОК НА ОСНОВЕ ТЕОРЕТИКОМНОЖЕСТВЕННОГО ПОДХОДА.

2.1. Характеристика теоретикомножественного подхода

к решению задачи.

2.2. Определение узлаантипода .
2.3. Построение пассивной области.
2.4. Определение активной области.
2.4. Алгоритм локализации подсеток в активной
области.
2.5. Выводы к главе.
3. РАЗРАБОТКА КЛЕТОЧНОГО АЛГОРИТМА ОПРЕДЕЛЕНИЯ
МАКСИМАЛЬНЫХ РАБОТОСПОСОБНЫХ ОБЛАСТЕЙ
3.1. Характеристика клеточноавтоматного подхода к решению задачи поиска подсеток .
3.2. Содержательная формулировка клеточного
алгоритма.
3.3. Построение клеточного алгоритма поиска подсеток
3.4. Примеры реализации алгоритма
3.5. Выводы к главе
4. ИССЛЕДОВАНИЕ АЛГОРИТМОВ ПОИСКА ПОДСЕТОК
4.1. Инструментальная среда моделирования алгоритмов поиска посеток.
4.2. Структурнофункциональная организация среды поиска максимальной подсетки
4.3. Исследование алгоритмов поиска максимальных посеток
4.4. Выводы к главе.
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ


III Межвузовской конференции по научному программному обеспечению «Практика применения научного программного обеспечения в образовании и научных исследованиях» (Санкт-Петербург, ). Публикации. Основные результаты диссертационной работы опубликованы в работах, в том числе в 7 статьях, в 1 тезисах докладов, в 2 материалах конференций. Основные научные положения. Принципы обеспечении дефектоустойчивости матричных процессоров, позволяющие создать параллельные распределенные алгоритмы выделения работоспособных областей в матричных процессорах с фатальными отказами при минимальной деградации их свойств. Алгоритм параллельного распределенного вычисления максимальных бездефектных областей решетки/тора, позволяющий путем логико-алгебраических преобразований глобальной информации об отказах в каждом из узлов выделять неизбыточные множества работоспособных подсеток и упростить получение решения. Композиция правил вычисления максимальной бездефектной области для произвольного узла, позволяющих без сбора информации о состоянии всех узлов матричного процессора параллельно и распределено строить максимальную работоспособную область. Клеточный алгоритм реализации правил вычисления максимальной бездефектной области, позволяющий строить однородную среду определения максимальной субрешетки/субтора в матричном процессоре с минимальной деградацией его свойств. Личный вклад автора. В работах [2, 3], опубликованных в соавторстве, лично автором введена система операций над подматрицами решетки/тора и дана их теоретико-множественная интерпретация. В работах [4, 5] автором разработан алгоритм реструктуризации матричных процессоров методом объединения подматриц, в работе [] автор лично разработал систему параллельных подстановок для аналитической записи клеточного алгоритма. Объем и структура работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка использованных источников. Общий объем диссертации составляет 7 страниц, содержащих рисунков и графиков, 8 страниц - список литературы из использованных источников. Во введении к диссертации обоснована ее актуальность, сформулированы цель и задача исследований, научная новизна, практическая ценность, основные научные положения, выносимые на защиту, и приведено краткое содержание каждой из глав. В первой главе рассмотрена архитектура современных матричных процессорных систем, дан сравнительный анализ методов обеспечения отказоустойчивости процессорных матриц, рассмотрены особенности алгоритмов реконфигурации матричных процессоров. Показано, что продолжение функционирования в фатальных ситуациях возможно в матричных структурах с деградацией путем их реструктуризации, обеспечивающей исключение фатальных фрагментов из физических массивов при уменьшении их размерности. На основании выполненного анализа были сформулированы задачи исследований по разработке параллельных, распределенных алгоритмов обеспечения дефектоустойчивости матричных процессоров путем выделения максимальных работоспособных областей при сохранении способности системы к реконфигурации. Вторая глава посвящена разработке теоретикомножественного подхода к распределенному определению максимальных работоспособных областей в торе/решетке с произвольными комбинациями отказов и алгоритма генерации подобластей для отдельных узлов процессорной матрицы, обеспечивающих сохранение работоспособности матрицы при максимальном числе рабочих элементов. Реализация рассматриваемого подхода основана на интерпретации прямоугольных выпуклых подобластей пространства МП с топологией решетка/тор выражениями, использующими операции объединения, пересечения и дополнения подмножеств элементов исходной структуры. Решение задачи сохранения максимального числа работающих элементов в прямоугольной выпуклой области отказавшего МП базируется на определении области деактивации, содержащей все отказавшие и минимальное число работоспособных узлов. В разделе сформулированы и доказаны утверждения, обосновавшие правила определения минимального состава элементов области деактивации отказавшей ПМ, а также правила локализации прямоугольных подобластей в активной области узла.