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

• Автор: Инютин, Сергей Арнольдович
• Шифр специальности: 05.13.01
• Научная степень: Докторская
• Год защиты: 2001
• Место защиты: Москва
• Количество страниц: 270 с. : ил

Оглавление Стр

Введение.

Глава 1. Модулярная арифметика квадратичного диапазона.

Модульные операции.

1.1 Модулярный способ представления числовых данных.

1.2 Вычислительная сложность алгоритмов и компьютерные арифметики.

1.3 Настройка модулярной арифметики на проблемную область.

1.4 Модель модулярной арифметики с квадратичным диапазоном.

1.5 Модулярные диапазоны и базисные операции.

1.6 Каноническое представление, сопряженные модулярные величины.

1.7 Модульные аддитивные операции.

1.8 Модульные мультипликативные операции.
1.9 Вычисление модулярной величины, обратной по модулям диапазона.
Выводы.
Глава 2. Модулярная арифметика квадратичного диапазона. Немодульные операции.
2.1 Характеристики отношения порядка для модулярных величин.
2.2 Методы вычисления характеристик отношения порядка.
2.3 Немодульные операции модулярной арифметики
2.4 Деление в модулярной арифметике.
2.5 Расширение модулярного диапазона.
2.6 Вычет модулярной величины по большому модулю.
Выводы.
Глава 3. Контроль модулярных вычислений.
3.1 Метрики и типы ошибок в модулярных кодах.
3.2 Помехозащитные модулярные коды.
3.3 Метод вложенных диапазонов.
3.4 Методы декодирования помехозащитных модулярных кодов.
3.5 Синдромные и совмещенные алгоритмы декодирования.
3.6 Методы контроля модулярного вычислительного процесса.
Выводы.
Глава 4. Вычисления в больших и сверхбольших компьютерных диапазонах
4.1 Вычислительные задачи большой сложности и модулярная арифметика
4.2 Компьютерная арифметика сверхбольших диапазонов.
4.3 Модулярная арифметика для вычислений в больших диапазонах.
4.4 Вычетный алгоритм тестирования на простоту чисел Ферма.
4.5 Системы линейных сравнений и разложение модулярной величины.
4.6 Математические конструкции в модулярных системах.
4.7 Вычислительные приложения модулярной арифметики.
Выводы.
Глава 5. Применение модулярной арифметики и особенности параллельных модулярных процессов.
5.1 Особенности аппаратурных и программных модулярных процессов.
5.2 Структура прораммного комплекса модулярных вычислений в 7 больших компьютерных диапазонах.
5.3 Тестирования на простоту чисел Ферма.
5.4 Тестирование на простоту чисел Мерсенна.
5.5 Вычислительные процессы в сверхбольших диапазонах
5.6 Программные модулярные процессы для тестирования чисел 8 специального вида.
5.7 Модулярный контроль технологической информации.
Выводы.
Заключение.
Библиография


Внутренняя организация модулярного процессора не определяется на данном уровне рассмотрения, она возможна на позиционных или модулярных принципах. Память оценивается в ячейках памяти М(п) под числа, значением не более максимума машинного диапазона. Это позволяет при необходимости перейти к оценке памяти в битах, байтах. Временная сложность оценивается в модульных тактах - Т(п). Определим модульный аддитивный (мультипликативный) такт - временной интервал выполнения аддитивной (мультипликативной) операции. Временные сложности независимых модульных аддитивных (мультипликативных) операций по всем основаниям полагаются равными 1А - одному аддитивному (1М - мультипликативному) модульному такту. Временная сложность алгоритмов оценивается суммой аддитивных и мультипликативных модульных тактов. Временными затратами на поразрядное (двоичное) сравнение, суммирование единиц переноса пренебрегаем. В очевидных случаях затраты операционного оборудования и памяти не оцениваются. Временная сложность алгоритмов выполнения модулярных операций и проблемных вычислительных алгоритмов сравнивается между собой по отдельным совокупностям операций: аддитивных и мультипликативных. Для оценки временной сложности в модульных тактах вычисляется сумма модульных тактов, необходимая для выполнение всех операций. Для точной оценки учитывается факт превышения на порядок временной сложности поразрядных мультипликативных операций над аддитивными [,,]. При необходимости дать единую оценку временной сложности длительности обоих временных тактов предполагаются равными, учитывая, что Р» р1 . При операциях с многоразрядными числами в позиционной системе счисления затраты времени на поразрядное сложение, умножение полагаются равными. МС(Р ) или в двойное машинное слово для МС(Р ), что эквивалентно модулярному варианту при п - парных модулярных процессорах. МВ - вычислительная система содержит п -пар модулярных процессорных элементов или Ъп -модулярных процессоров, два процессора на каждый из п -квадратичных модулей. Не тривиальной проблемой в алгоритмике является компактная и понятная при анализе запись алгоритма. Учитывая современные подходы к записи алгоритмов, развитые в работах Нодена П. Китте К. Ада, отличной от стандарта, но обладающей свойством легкости чтения алгоритма, совмещающей строгость математических соотношений со спецификой их программных реализаций. Для модулярного варианта приводятся оценки для максимального распараллеливания на необходимое число модулярных процессорных элементов (неограниченный параллелизм). Методика расчета эффективности модулярных вычислительных средств для модели неограниченного параллелизма и реальных мультипроцессорных систем с ограниченным количеством процессоров дана в § 5. Она позволяет получить оценки сложности вычислительных алгоритмов для реальных многопроцессорных системах при меньшем числе процессоров и учесть затраты на организацию последовательного потока заданий на выполнение параллельных модулярных вычислений. В Приложении 7 приведен перечень Ада -программ, алгоритмов и производных типов модулярных данных. Центральной операцией для ряда вычислительных проблем в сверхбольших диапазонах является операция вычисления вычета по некоторому большому модулю от степени входной числовой величины. Эта операция должна быть базисной в конструируемой компьютерной арифметике. Это накладывает требования на выбор и алгоритмы модульных и немодульных операций арифметики, которые должны обеспечивать максимальную простоту операции вычисления вычета по большому модулю от некоторой степени большого числа. Алгоритм для этой операции разработан в главе 2. Отображение проблемного алгоритма в вычетную форму для выполнения на модулярной вычислительной базе является настройкой проблемных алгоритмов на вычислительную базу. Взаимная настройка компьютерной арифметики на проблему позволяет получить оптимальные по быстродействию, затратам операционных ресурсов и машинной памяти вычислительные алгоритмы. Основной является задача выбора диапазона модулярной системы, соответствующего вычислительной проблеме.