Введение к работе
Актуальность проблемы: Меньше чем за одно поколение информационная революция и внедрение компьютерных технологий фактически в каждую область жизни общества привели к принципиально новым достижениям в сфере управления экономикой и обеспечения национальной безопасности РФ. Одним из наиболее важных направлений развития научно-технического прогресса в сфере информатизации в настоящее время является микропроцессорная революция, для которой характерно широкое использование в системах обработки информации вычислительных систем (ВС), персональных компьютеров, микропроцессоров универсального и специального назначения. Основным направлением развития и совершенствования вычислительных устройств является неуклонный рост производительности и точности вычислений.
Применение SlSD-архитектуры обеспечивает доминирующее положение классической фон-неймановской архитектуры. Возрастание требований к технико-экономическим характеристикам современных вычислительных систем, расширение областей их применения привели к активизации работ по разработке вычислительных устройств с предельными для существующего уровня технологии значениями технических характеристик. Существующая в последние годы в вычислительной технике тенденция к распараллеливанию вычислений связана с непрерывным ростом требований к производительности вычислительных средств. Качественным скачком в обеспечении реального масштаба времени и высокой точности вычислений является применение полиномиальной системы классов вычетов (ПСКВ), определяемой в расширенных полях Га-луа GF(2V). Внутренний параллелизм, присущий арифметике ПСКВ, независимость обработки данных в вычислительных трактах, распараллеливание на уровне арифметических операций позволяют широко использовать перспективные принципы организации вычислительных систем.
Однако процессоры, составляющие значительную часть аппаратной реализации вычислительной техники, относятся к числу наименее надежных устройств, доля отказов и сбоев которых составляет более 50 процентов от общего числа отказов и сбоев аппаратуры. При этом среднее время ликвидации последствий последних, как правило, на 6-8 порядков превышает среднюю продолжительность выполнения одной задачи.
Таким образом, очевидна следующая проблема: с одной стороны, постоянный рост требований к скоростным характеристикам вычислительных устройств приводит к необходимости организации параллельных вычислений, а с другой стороны, при этом увеличивается частота возникновения отказов, и возрастает время простоя, вызванное трудностью отыскания неисправности.
Наиболее перспективным путем разрешения данной проблемы является придание процессорам свойства устойчивости к отказам в процессе функционирования. Вычислительная система является отказоустойчивой (Fault-tolerant system), если при возникновении отказа сохраняет свои функциональные возможности в полном (fail-safe) или уменьшенном (fail-soft) объеме. При этом fail-safe устойчивость к отказам (с амортизацией отказов) характеризует способность ПС обеспечивать обслуживание, несмотря на возникновение отказа, хотя и с понижением качества, то сеть, находясь в состоянии постепенного снижения эффективности. Именно в таком контексте рассматривается понятие отказоустойчивость и устойчивость к отказам вычислительных устройств.
Качественным скачком в обеспечении отказоустойчивости вычислительных систем является широкое применение кодов, способных обнаруживать и корректировать ошибки, возникающие в результате отказов элементов в процессе функционирования процессоров. Независимость обработки информации в вычислительных трактах, невозможность распространения ошибок от одного основания к другому, а так же арифметичность кодов ПСКВ стали базой для разработки концепции построения корректирующих кодов полиномиальной системы классов вычетов.
Таким образом, целью данной диссертационной работы является обоснование и разработка концепции построения корректирующих кодов полиномиальной системы классов вычетов, ориентированных на применение в отказоустойчивых вычислительных системах.
Объектом диссертационного исследования являются методы и алгоритмы построения корректирующих кодов ПСКВ, а так же их практические реализации в отказоустойчивых вычислительных устройствах. Предметы исследования:
1. Методы, алгоритмы и аппаратная реализация модульных и немодульных операций в полиномиальной системе классов вычетов.
-
Корректирующие коды полиномиальной системы классов вычетов.
-
Методы и алгоритмы поиска и локализации ошибки в кодах ПСКВ и их схемная реализация.
4. Методы реконфигурации структуры пспозициошюго процессора
ПСКВ, позволяющие сохранять работоспособное состояние при возникновении
отказов за счёт снижения в допустимых пределах основных показателей каче
ства функционирования.
Научная проблема, решение которой содержится в диссертационной работе, - теоретическое обоснование и развитие основ построения корректирующих кодов полиномиальной системы классов вычетов для обеспечения отказоустойчивости вычислительных систем.
В интересах решения научная проблема разбита на пять частных проблем:
-
Разработка математических основ модульных и немодульных процедур полиномиальной системы классов вычетов, а так же их схемная реализация.
-
Разработка концепции построения корректирующих кодов ПСКВ для реализации отказоустойчивых непозиционных процессоров.
-
Разработка методов и алгоритмов контроля и коррекции ошибок с использованием корректирующих кодов полиномиальной системы классов вычетов и их схемная реализация.
-
Разработка метода реконфигурации структуры процессора классов вычетов, базирующегося на обменных операциях ПСКВ, которые позволяют сохранять работоспособное состояние вычислительного устройства при возникновении отказов за счет снижения в допустимых пределах основных показателей качества функционирования
-
Разработка методологии построения устойчивых к отказам процессоров, функционирующих в полиномиальной системе классов вычетов.
Научную новизну работы составляют:
-
Методы и алгоритмы выполнения модульных и нсмодульных операций ПСКВ, характеризующиеся меньшими схемными и временными затратами по сравнению с ранее известными реализациями.
-
Теоретические основы построения корректирующих кодов ПСКВ, доказанные теоремы и следствия, определяющие информационную надежность и избыточность модулярных кодов классов вычетов, применение которых по-
зволяет осуществлять обнаружение и коррекцию ошибок в процессе функционирования вычислительной системы.
-
Методы и алгоритмы поиска и коррекции ошибок в непозиционных кодах ПСКВ, реализованные на основе вычисления позиционных характеристик во временной области, которые, в отличие от ранее известных, характеризуются минимальными аппаратными и временными затратами.
-
Впервые предложен метод обнаружения и исправления ошибок в кодах ПСКВ, базирующийся на вычислении спектральных составляющих кода классов вычетов, а так же предложена его реализация. Применение последнего позволяет осуществлять контроль работы самого устройства поиска и коррекции ошибок
-
Метод реконфигурации структуры непозиционного процессора при возникновении отказов, который отличается от известных применением методов пересчета ортогональных базисов и коэффициентов обобщенной полиадической системы (ОПС), реализация которого позволяет обнаруживать и локализовать ошибки при деградации структуры процессора ПСКВ.
-
Методология синтеза устойчивого к отказам нспозиционного процессора, функционирующего в полиномиальной системе классов вычетов.
Методы исследования базируются на использовании математического аппарата теории кодирования, теории полей Галуа, теории чисел, теории вероятности.
Достоверность и обоснованность проведенных исследований подтверждается физической аргументированностью и математической корректностью исследуемых вопросов, строгостью принятия допущений и введенных ограничений, использованием апробированного математического аппарата, сходимостью результатов расчета с известными из литературных источников, полученными на основе эвристических соображений.
Практическая ценность работы:
- разработаны методы и алгоритмы модульных и немодульных операций ПСКВ, которые позволяют реализовывать вычислительные устройства, обладающие более высокой надежностью и производительностью по сравнению с ранее известными;
разработаны методы и алгоритмы поиска и локализации ошибки, а так же их схемные реализации, применение которых позволит повысить надежность функционирования вычислительных систем полиномиальной системы классов вычетов;
разработан метод реконфигурации процессора, применение которого позволяет повысить надежность работы вычислительного устройства ПСКВ;
разработан методологический аппарат построения непозиционного процессора, функционирующего в ПСКВ, который позволяет повысить эффективность работы вычислительных систем реального масштаба времени, за счет способности выполнять поставленные задачи при постепенной деградации структуры, вызванной возникающими отказами трактов.
Основные положения, выносимые на защиту.
-
Методы и алгоритмы выполнения модульных и немодульных операций в полиномиальной системе классов вычетов и их схемные реализации, применение которых позволяет повысить надежность и скорость осуществления данных операций по сравнению с ранее известными.
-
Концепция построения корректирующих кодов полиномиальной системы классов вычетов, применение которых позволит осуществлять контроль и коррекцию ошибок в процессе функционирования вычислительного устройства
-
Методы и алгоритмы поиска и локализации ошибок в процессе функционирования вычислительных систем ПСКВ, которые позволяют осуществить данные процедуры при минимальных аппаратурных и временных затратах.
-
Метод обнаружения и исправления ошибок в кодах ПСКВ с использованием частотной области, реализация которого позволяет обнаруживать отказы при работе самого устройства поиска и коррекции ошибок.
-
Метод реконфигурации структуры непозиционного процессора ПСКВ, позволяющий сохранять работоспособное состояние вычислительного устройства за счет перераспределения ресурсов при большем количестве возникающих отказов по сравнению с ранее известными методами обеспечения отказоустойчивости вычислительных систем.
-
Метод пересчета значений ортогональных базисов при постепенной деградации структуры вычислительного устройства класса вычетов, который в отличие от ранее известных не требует использование перестраиваемого мо-
дульного сумматора по величине рабочего диапазона, что позволяет сократить аппаратурные затраты и повысить надежность функционирования процессора.
-
Метод пересчета значений коэффициентов ОПС при деградации структуры непозиционного процессора ПСКВ, применение которого позволяет осуществлять процедуры поиска местоположения ошибок, вызванных отказами вычислительных трактов.
-
Методологический аппарат построения устойчивых к отказам процессоров, функционирующих в полиномиальной системе классов вычетов.
Реализация результатов работы.
-
Основные результаты диссертационной работы использованы в Управлении начальника войск связи и военно-научным комитетом РВСН, в научно-производственном объединении «Импульс», ФГУП (г. Санкт-Петербург) при выполнении научно-исследовательских работ, при разработке ЛРМ «Оператор» в ООО «Моби», что подтверждается актами реализации.
-
Основные результаты диссертационной работы использованы в учебном процессе:
на кафедре «Информатики и информационных технологий в системах управления» Ставропольского военного института связи РВ, что подтверждается актом реализации
на кафедре «Защиты информации» Северо-Кавказского государственного технического университета, что подтверждается актом реализации.
Апробация работы:
Результаты работы обсуждались на конференциях: Международная конференция «Нейрокомпьютеры и их применение - 2002», Москва 2002; V Международная научно-практическая конференция, Таганрог, 2003; II Международная научно-техническая конференция «Физика и технические приложения волновых процессов», Самара, 2003; III Санкт-Петербургская межрегиональная конференция «Информационная безопасность регионов России», Санкт-Петербург, 2003; II Международный Форум по проблемам науки, техники и образования, Москва, 2003; VI Международная научно-практическая конференция, Таганрог, 2004; III Международный Форум по проблемам науки, техники и образования, Москва, 2004; I Международная научно-практическая конференция Ставрополь, 2004; IV Международная научно-техническая конфе-
ренция «Проблемы информатики и моделирования», Харьков, 2004; VII Международная научно-практическая конференция «Информационная безопасность», Таганрог, 2005; Международная конференция Российской академии естествознания «Новые информационные технологии и системы», Москва, 2005.
Публикация. Основные результаты работы представлены в 56 печатных работах, двух монографиях, получено пять патентов и два положительных решения на выдачу патента.
Структура и объем диссертации. Диссертационная работа изложена на 346 страницах машинописного текста, иллюстрируется 36 рисунками и 31 таблицей и состоит из введения, 6 разделов, списка используемых источников из 212 наименований.
