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

• Автор: Оцоков, Шамиль Алиевич
• Шифр специальности: 05.13.15, 05.13.05
• Научная степень: Кандидатская
• Год защиты: 2003
• Место защиты: Москва
• Количество страниц: 264 с. : ил.

ВВЕДЕНИЕ

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

ВЫСОКОПРОИЗВОДИТЕЛЬНЫХ ЭВМ.

1.1. Классы задач, определяющие необходимость перехода к

безошибочным вычислениям .

1.2. Модель безошибочных вычислений на основе системы остаточных классов.

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

1.4. Цели и задачи диссертационного исследования

. 1.5. Выводы

ГЛАВА 2. РАЗРАБОТКА БАЗОВЫХ АЛГОРИТМОВ, ОБЕСПЕЧИВАЮЩИХ ВЫПОЛНЕНИЕ БЕЗОШИБОЧНЫХ ВЫЧИСЛЕНИЙ

2.1. Алгоритмы целочисленной обработки в системе

остаточных классов
2.1.1. Преобразование целых чисел из позиционной системы счисления в систему остаточных классов
2.1.2. Преобразование целых чисел из системы остаточных классов в позиционную систему счисления.
2.1.3. Целочисленная арифметика в системе остаточных классов
2.2. Алгоритмы обработки чисел с фиксированной запятой в системе
остаточных классов
2.2.1.Преобразование чисел с фиксированной запятой в
одномодульную систему остаточных классов
2.2.2. Преобразование чисел одномодульной системы остаточных классов в числа с фиксированной запятой в позиционной системе счисления.
2.2.3. Преобразование чисел с фиксированной запятой в многомодульную систему остаточных классов.
2.2.4. Преобразование чисел многомодульной системы остаточных классов в числа с фиксированной запятой в позиционной системе счисления
2.2.5. Арифметика чисел с фиксированнойзапятой в многомодульной системе остаточных классов
2.3. Выводы.
ГЛАВА 3. СТРУКТУРНАЯ ОРГАНИЗАЦИЯ УЗЛОВ ПРОЦЕССОРА ДЛЯ ОБРАБОТКИ ЧИСЕЛ ПО СХЕМЕ БЕЗОШИБОЧНЫХ ВЫЧИСЛЕНИЙ
3.1. Структурная организация устройств целочисленной арифметики в системе остаточных классов.
3.2. Принципы структурной организации основных узлов процессора, обеспечивающих безошибочную обработку чисел с фиксированной запятой
3.3. Выводы
ГЛАВА 4. ЭКСПЕРИМЕНТАЛЬНАЯ РЕАЛИЗАЦИЯ И ОЦЕНКА
ЭФФЕКТИВНОСТИ АЛГОРИТМОВ БЕЗОШИБОЧНЫХ ВЫЧИСЛЕНИЙ И СТРУКТУРНЫХ СХЕМ УСТРОЙСТВ.
4.1. Сравнительные оценки временных и аппаратурных затрат разработанных структурных схем с известными.
4.2. Разработка программного модуля безошибочной обработки чисел
в одномодульной системе остаточных классов.
4.3. Разработка программного модуля безошибочной обработки чисел
в многомодульной системе остаточных классов с использованием параллельной мультикомпыотерной сети КУРС
4.4. Применение разработанных алгоритмов для безошибочного решения системы линейных уравнений методом Гаусса.
4.5. Оценки аппаратной и программной реализации алгоритмов безошибочных вычислений в системе остаточных классов.
4.6. Опытное применение программы безошибочных вычислений для
оптимизации суточных режимов каскада Сулакских ГЭС.
4.7. Выводы .
ЗАКЛЮЧЕНИЕ.
СПИСОК ЛИТЕРАТУРЫ


На рис 1. СОК. В соответствии с этой моделью, процесс . Определение порядка дроби Фарея и соответствующего модуля системы остаточных классоб. Преобразование рациональных чисел в целые числа СОК. Проведение арифметических операций в СОК. Преобразование результатов из СОК в соответствующие несократимые дроби Фарея. Вывод точных результатов. Из теории чисел известно, что любое целое число можно представить последовательностью его наименьших неотрицательных вычетов а,,. О, Р, где
Р Р,, если модули попарно взаимно простые. Рис 1. Наоборот, каждой последовательности указанных вычетов а,,. Рассмотрим два сравнения. Существует ровно одно решение системы по 2 . X X р,, 1,. X Х0 Р 1. Р Р,. I i
а числа т, выбираются так, что iii 1 i. Таким образом, X принадлежит классу чисел по модулю Р, наименьший неотрицательный вычет этого класса меньше Р, другие вычеты отличаются на величину, кратной Р. Такую систему называют системой остаточных классов СОК, а систему попарно взаимно простых модулей называют основаниями этой системы счисления 3,,,,,,, , . А ,. А есть наименьший положительный остаток от деления А на р,. Р РГРт П Р1
Результаты арифметических операций сложения, вычитания дополнения до модуля, умножения с операндами А а В ,,. У и , по основаниям р, 3,,,,, , т. А В ,. А Р, В Р, АВ Р, АВР, АВ Р. Г, в р,. Р,
р8,а,Р,
. Если в ходе вычислений получен результат,. Операция деления в системе остаточных классов состоит из двух операций 1 нахождение обратного делителя 2 умножение делимого на обратное делителя. В работе доказывается, что каждое целое число СОК классов является образом бесконечного множества рациональных чисел. Но существует теорема, согласно которой отображение целых на некоторое подмножество рациональных дробей взаимно однозначно, если оно состоит из дробей Фарся . Пусть множество тех рациональных чисел, которые допускают отображение в г и т. Фарея . Если в ходе вычислений получены величины, не принадлежащие Рп, то это называется псевдопереполненисм . Если пссвдопсреполнение возникло в промежуточном результате вычислений, но не в конечном , то . Из 1. ПСС, за исключением деления . ПСС 6,0. Отыскание обратного числа для операции деления занимает наибольшую часть времени деления. Известен расширенный алгоритм Евклида для нахождения обратного числа. Ьу , 1. СОК с основанием т. Ы акх Ьку . Для нахождения целых х, у в 1. О Ьй, 7, 7,ь. Г, г,г . Г,. Ьу . Эти вычисления можно записать в виде таблицы 1. В работе доказывается, что вычислительная схема 1. Таблица 1. Вычисление г п , х и у. Последовательность пар чисел 1. Я 0 . Таблица 1. Ьз

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