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

• Автор: Калмыков, Игорь Анатольевич
• Шифр специальности: 05.13.17, 05.13.15
• Научная степень: Докторская
• Год защиты: 2006
• Место защиты: Ставрополь
• Количество страниц: 397 с. : ил.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ
1 АНАЛИТИЧЕСКИЙ ОБЗОР ОБЕСПЕЧЕНИЯ УСТОЙЧИВОСТИ К ОТКАЗАМ В ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ ОБРАБОТКИ ДАННЫХ.

1.1 Анализ основных тенденций развития и применения вычислительных систем

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

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

1.4 Постановка проблемы исследований.

Выводы.

2 МАТЕМАТИЧЕСКИЕ ОСНОВЫ ПОЛИНОМИАЛЬНОЙ СИСТЕМЫ КЛАССОВ ВЫЧЕТОВ ПОЛЕЙ ГАЛУА

2.1 Реализация модульных операций в полиномиальной системе классов вычетов в полях Галуа ОРру.
2.2 Прямое преобразование из двоичного кода в код полиномиальной системы классов вычетов.
2.3 Перевод из полиномиальной системы классов вычетов поля огр в позиционный код из
2.3.1 Перевод непозиционного кода на основе китайской теоремы об остатках
2.3.2 Реализация преобразований из полиномиальной системы классов вычетов в обобщенную полиадическую систему
2.4 Алгоритмы вычисления ранга полинома, представленного в полиномиальной системе классов вычетов
2.5 Реализация операций по расширению системы оснований в полиномиальной системе классов вычетов
2.6 Основы построения многоступенчатой полиномиальной системы
классов вычетов в расширенных полях Галуа.
Выводы
3 КОНЦЕПЦИЯ ПОСТРОЕНИЯ КОРРЕКТИРУЮЩИХ МОДУЛЯРНЫХ КОДОВ ПОЛИНОМИАЛЬНОЙ СИСИТЕМЫ КЛАССОВ ВЫЧЕТОВ.
3.1 Связь между ошибками в коде полиномиальной системы классов вычетов и распределением полиномов по диапазону.
3.2 Корректирующие коды полиномиальной системы классов вычетов с одним контрольным основанием
3.3 Корректирующие модулярные коды с двумя контрольными основаниями.
3.4 Обнаружение и коррекция ошибок на основе реализации процедур проекций
3.5 Оценка корректирующих способностей кодов полиномиальной
системы классов вычетов.
Выводы
ГЛАВА 4 МЕТОДЫ И АЛГОРИТМЫ КОНТРОЛЯ И КОРРЕКЦИИ ОШИБОК В КОДАХ ПОЛИНОМИАЛЬНОЙ СИСТЕМЫ КЛАССОВ 8 ВЫЧЕТОВ
4.1 Методы и алгоритмы коррекции ошибок на основе вычисление позиционных характеристик во временной области
4.1.1 Метод параллельной нулсвизации полинома, представленного в полиномиальной системе классов вычетов
4.1.2 Контроль и коррекция ошибки на основе вычисления интервального номера
4.1.3 Поиск и коррекция ошибок на основе вычисления коэффициентов обобщенной полиадической системы
4.1.4 Поиск и локализация ошибок в кодах полиномиальной системы
классов вычетов на основе вычисления синдрома ошибки
4.2 Обнаружение и коррекция ошибок в частотной области
4.2.1 Математические основы спектрального метода обнаружения и коррекции ошибок в кодах полиномиальной системы классов вычетов
4.2.2 Спектральный метод контроля и коррекции ошибок в кодах полиномиальной системы классов вычетов
4.3 Сравнительная оценка методов контроля и коррекции ошибок в
кодах полиномиальной системе классов вычетов
Выводы
ГЛАВА 5 РЕКОНФИГУРАЦИЯ СТРУКТУРЫ ПРОЦЕССОРА ПОЛИНОМИАЛЬНОЙ СИСТЕМЫ КЛАССОВ ВЫЧЕТОВ ПРИ ВОЗНИКНОВЕНИИ ОТКАЗОВ.
5.1 Определение местоположения и глубины ошибок при деградации структуры модулярного процессора
5.2 Разработка метода пересчета ортогональных базисов при деградации структуры нспозиционных процессоров
5.3 Метод пересчета коэффициентов обобщенной полиадической
системы для процессоров с деградируемой структурой
Выводы
ГЛАВА 6 МЕТОДОЛОГИЧЕСКИЕ ОСНОВЫ И ПРИНЦИПЫ ПОСТРОЕНИЯ НЕПОЗИЦИОННЫХ ПРОЦЕССОРОВ УСТОЙЧИВЫХ К ОТКАЗАМ.
6.1 Разработка методики построения отказоустойчивых процессоров, функционирующих в полиномиальной системе классов вычетов
6.2 Построение отказоустойчивого непозиционного спецпроцессора цифровой обработки сигналов.
6.3 Оценивание пригодности методики в инженерной практике
Выводы
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА


В принципе распараллеливание может быть осуществлено на нескольких уровнях на уровне построения физических моделей объектов или процессов, создания математических моделей, позволяющих организовать параллельную обработку информации, на уровне метода решения, на уровне алгоритмов известных методов, на уровне программ, на уровне арифметических операций, на уровне обменов информации в вычислительных системах, ввода и вывода данных. Рассмотрим некоторые из них. Так при исследовании статического напряженного объекта проводится разделение его конструкций на несколько подконструкций, учитывая геометрию данного объекта. В местах мысленного разделения конструкции формируются дополнительные краевые условия. Полученные таким образом математические модели исследуются на отдельных вычислительных устройствах одновременно. Таким образом осуществляется распараллеливание на уровне физических моделей прикладных задач . При решении задач в рамках моментальной теории упругости довольно часто используются системы уравнений в частных производных. Принятие гипотезы КирхгофаЛявы позволяет свести эту систему к системам обыкновенных дифференциальных уравнений с соответствующими краевыми условиями. Полученная система может быть решена одновременно на нескольких вычислительных устройствах. Данный пример иллюстрирует возможность распараллеливания на уровне математической модели ,. К созданию, за сравнительно короткое время, многих алгоритмов, реализующих параллельные вычисления, привели разработки новых алгоритмов на базе уже известных методов. Гаусса, метода отражений, метода квадратных корней, метода оргогонализации и др. Созданы алгоритмы параллельных вычислений решения задач Коши для систем обыкновенных дифференциальных уравнений . Распараллеливание на уровне программ успешно реализуется на хорошо структурированных программах, а так же программах, имеющих много циклов и гнезд циклов . Распараллеливание на уровне обменов информации между процессорами, процессорами и памятью определяется тем, что арифметические операции выполняются быстрее, чем операции обмена. Поэтому, исходя из объема оперативной памяти каждого процессорного элемента, его быстродействия и скорости обмена, необходимо сбалансировать количество каналов так, чтобы процессоры не простаивали изза ошибок при решении задач с большим объемом перерабатываемой информации. При этом значительный объем вводимой и выводимой информации требует параллельного ввода и вывода информации с контролем достоверности информации ,. Одним из наиболее перспективных направлений в разработке высокоскоростных вычислительных систем является переход к распараллеливанию на уровне арифметических операций. В современных и перспективных алгоритмах, использующих аппарат линейной алгебры, основными вычислительными процедурами являются операции типа перемножения векторов и матриц, обращение матриц, поиска собственных векторов и собственных значений матриц, решение систем линейных алгебраических уравнений СЛАУ ,5. Процедуры линейной алгебры обладают повышенной вычислительной сложностью. Так для реализации алгоритма быстрого преобразования Фурье БПФ требуется порядка арифметических операций, для умножения матрицы на вектор О, а для обращения матриц, решения систем линейных алгебраических уравнений порядка 0Ы3 операций М размерность задачи. Вычислительная сложность матричных процедур приведена в таблице 1. Таблица 1. Как показывает практика большинство алгоритмов линейной алгебры критичны к ошибкам округления, возникающим в процессе вычислений. Поэтому при решении задач линейной алгебры возникают проблемы, связанные с точностью вычислений. Это обусловлено прежде всего большим количеством последовательных операций, выполняемых над каждым элементом входных матриц. Так накопление ошибок происходит довольно быстро, то ошибки арифметических операций над элементами матрицы приводят к искажению конечного результата ,5. Однако увеличение размера разрядной сетки вычислительных устройств не позволяет в полной мере решить данные проблемы. Положение еще более усугубляется тем, что во многих алгоритмах линейной алгебры обрабатываются комплексные операнды.