Введение к работе
Актуальность темы исследования определяется перспективностью применения в вычислительной технике сверхбольших интегральных схем (СБИС), объединяющих на одном кристалле или пластине большое количество идентичных процессоров. Неразрезная технология исключает замену отдельных неисправных процессоров. Поэтому обеспечение достаточно высокого выхода годных СБИС требует отказоустойчивости вычислительной системы, т.е. сохранения работоспособности системы при множественных отказах элементов. Общепризнанным путем обеспечения отказоустойчивости является введение в систему избыточных элементов и связей и реконфигурация системы путем замещения неисправных процессоров резервными. Возникает необходимость разработки практических алгоритмов реконфигурации, их сравнительного анализа, а также конкретных методов ігх применения.
Данная работа выполнена в рамках концепции однородных вычислительных систем (ОВС) с программируемой структурой, занимающей ведущее место в развитии вычислительной техники с массовым параллелизмом.
Целью диссертационной работы является анализ и разработка методов обеспечения реконфіпу рации отказоустойчивой неразрезной процессорной матрицы на СБИС.
В соответствии с поставленной целью в диссертационной работе решаются следующие задачи:
- разработка алгоритмов реконфигурации избыточной ОВС,
сохраняющей структуру связей;
-моделирование процесса реконфигурации микропрограммными клеточными автоматами;
разработка программной реализации алгоритмов реконфигурации избыточных однородных вычислительных структур, сохраняющих структуру связей;
проверка с использованием этой системы ранее известных и модифицированных нами алгоритмов реконфигурации ОВС.
Методы исследования.
При проведении исследований использовался следующий аппарат: теория микропрофаммных клеточных автоматов, теория вероятностей, теория просачивания, вычисления и имитационное моделирование на ЭВМ.
Научная новизна результатов работы определяется следующими основными результатами, впервые полученными автором диссертации.
Разработан алгоритм диагонального захвата для реконфигурации процессорной матрицы, позволяющий повысить отказоустойчивость процессорной матрицы с сохранением исходной структуры квадратной решетки. Предложены формулы для вычисления логических координат процессорных элементов после реконфигурации матрицы по алгоритму диагонального захвата. Доказана корректность этого алгоритма.
Получены логические выражения для сигналов перестройки и формулы для вычисления логических координат процессорных элементов при реконфигурации по алгоритмам непосредственной перестройки, ограниченного и свободного захвата.
Построена модель процесса реконфигурации в виде параллельного комбинационного микропрограммного клеточного автомата, представляющего собой сеть из элементарных автоматов (блоков управления процессорных элементов), расположенных в узлах двумерной квадратной решетки.
Предложены средства и методы программной реализации параллельных клеточных алгоритмов.
Практическая значимость работы.
Описание алгоритмов реконфигурации в виде систем булевых функций и программная система для реконфигурации процессорной матрицы представляют собой новое математическое и программное обеспечение и могут быть использованы непосредственно при проектировании и производстве отказоустойчивых ОВС.
Система, моделирующая процесс реконфигурации избыточных однородных вычислительных структур, сохраняющих структуру связей, может применяться как для вычисления функций реконфигурации процессорной матрицы в управляющей ЭВМ и отладки новых алгоритмов реконфигурации структуры, так и с целью разработки и моделирования микропрограммных клеточных автоматов для иных приложений, например, для самодиагностики матрицы. Так, с использованием данного программного обеспечения были отлажены алгоритмы непосредственной перестройки, ограниченного и свободного захвата и разработан алгоритм диагональной перестройки.
Достоверность результатов проведенных исследований и обоснованность научных положений и выводов, сформулированных в диссертации, обусловлена использованием аппарата дискретной математики при доказательстве корректности предложенных алгоритмов и подтверждается результатами имитационного моделирования на ЭВМ.
Основные положения, выносимые на защиту.
-
Алгоритм диагонального захвата, позволяющий полнее использовать введенную избыточность и тем самым повысить надежность схемы.
-
Алгоритм адресации для перестройки по диагональному захвату.
-
Логические выражения для вычисления сигналов перестройки и формулы для вычисления логических координат процессорных элемента по алгоритмам непосредственной перестройки, ограниченного и свободного захвата.
-
Программная система ЛОГИКА, обеспечивающая реализацию метода программной реконфигурации неразрезной процессорной матрицы, разработку и моделирование микропрограммных клеточных автоматов для реконфигурации матрицы и иных приложений.
Реализация результатов работы.
Работа выполнена в соответствии с планом научно-исследовательских работ кафедры информационных технологий Томского государственного педагогического университета.
Результаты диссертационной работы были использованы в учебном процессе на кафедре информационных технологий Томского государственного педагогического университета, на кафедре программирования Томского государственного университета, что подтверждается соответствующими актами.
Личный вклад автора.
Основные результаты диссертационной работы получены автором лично.
Апробация работы.
Основные результаты диссертации докладывались и обсуждались на Всероссийской конференции "Новые информационные технологии в исследовании дискретных структур" (Екатеринбург, 1996), на региональной научно-технической конференции молодых специалистов "Радиотехнические и информационные системы и устройства" (Томск, 1994), на Международном конгрессе студентов, аспирантов и молодых ученых (Томск, 1999), на семинарах кафедр математической логики и проектирования (радиофизический факультет) и программирования (факультет прикладной математики и кибернетики) Томского государственного университета (Томск, 1994; 2000).
Публикации.
Результаты исследований по диссертационной работе опубликованы в виде 4 статей в научных журналах, 2 докладов, 2 тезисов выступлений на конференциях (всего 8 печатных работ).
Струюура и объем работы.
Диссертация состоит из введения, трех глав, заключения и библиографии. Она изложена на 128 страницах, содержит 24 иллюстрации, 7 таблиц. Библиографический список литературы цитированной литературы включает 76 наименований. Диссертация имеет 10 приложений на 72 страницах.