Высокоточные вычисления с динамической длиной операндов в многопроцессорных системах

• Автор: Морозов, Виталий Александрович
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 1999
• Место защиты: Новосибирск
• Количество страниц: 228 с.

ОГЛАВЛЕНИЕ

1 ДИНАМИЧЕСКАЯ ДЛИНА ОПЕРАНДОВ КАК СРЕДСТВО ПОВЫШЕНИЯ ТОЧНОСТИ ВЫЧИСЛЕНИЙ
1.1 Способы устранения ошибок округления
1.1.1 Системы аналитических преобразований
1.1.2 Учет и оценка погрешности округления
1.1.3 Арифметика многократной точности
1.2 Анализ применяемых вычислительных алгоритмов
1.2.1 Матричные вычисления
Умножение матриц
Итерационные вычисления
Прямые методы решения СЛАУ
1.2.2 Проблемы вычислительной геометрии
1.3 Организация вычислений с динамической длиной операндов
1.3.1 Последовательные вычисления- г*>.и
Пакет программ АСЫТН
Пакет со строковым представлением
Пакет ИК-арифметики
1.3.2 Распараллеливание операций многоразрядной арифметики
Конвейерные ЭВМ
Вычислительные среды и нейронные сети
Мультипроиесорные системы
1.4 СПАРФ-ЭШГО вычисления
Высокоточные векторные операции
1.5 Выводы
2 АЛГОРИТМИЧЕСКОЕ ОБЕСПЕЧЕНИЕ СПАРФ-ВЫЧИСЛЕНИЙ
2.1 М1МБ-системы. работающие в режиме передачи сообщений
2.2 Топология коммуникационной сети
2.3 Критерии опенки и вычислительная сложность алгоритмов
2.4 Способы оценки коммуникационных затрат

2.5 Модель передачи сообщений
2.5.1 Точечные взаимодействия
Операции блокирующего типа
Операции неблокирующего типа
2.5.2 У паковка/распаковка данных
2.6 Групповое движение данных
2.6.1 Распространение
2.6.2 Сбор и распределение
2.6.3 Групповые арифметические операции
2.6.4 Скалярное произведения двух векторов
2.6.5 Сложные типы обменов
2.7 Организация многоразрядной арифметики с динамической длиной операндов
2.7.1 Алгоритмы сложения/вычитания
2.7.2 Алгоритмы логических сдвигов
2.7.3 Алгоритмы умножения
2.7.4 Вычисление обратной величины
2.8 Анализ точности вычисления арифметических операций
2.8.1 Вычисление сложения и вычитания
2.8.2 Вычисление логических сдвигов
2.9 Алгоритмы ускоренного умножения/деления
2.9.1 Построение и анализ алгоритмов
Умножение
Деление
2.9.2 Точность вычисления операций
2.10 Элементарные функции
2.10.1 Обзор основных методов
2.10.2 Вычисление функции у
2.10.3 Вычисление функции у = cos х
2.10.4 Вычисление функций у = tg х и у = ctg х
2.10.5 Вычисление функции у
2.10.6 Вычисление функции у
2.10.7 Вычисление функции у

2.11 Выводы
3 ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ
СПАРФ-ВЫЧИСЛЕНИЙ
3.1 Вычислительная система Intel iPSC/860
3.1.1 Аппаратное обеспечение .*
Хост-машина
Стандартный блок
3.1.2 Программное обеспечение
3.1.3 Организация коммуникационных процедур
3.2 Вычислительная система Parsytec PowerXplorer
3.2.1 Аппаратное обеспечение
3.2.2 Программное обеспечение
3.2.3 Организация коммуникационных процедур
3.3 Форматы СПАРФ-чисел и способы организации вычислений
3.4 СПАРФ-библиотека для MIMD-вычислений
3.4.1 Арифметические операции
3.4.2 Арифметико-логические операции
3.4.3 Функции преобразования форматов данных
3.4.4 Функции управления ресурсами
3.4.5 Функции управления разрядностью
3.4.6 Операции межпроцессорных взаимодействий
3.4.7 Сервисные функции
3.5 Базовые коммуникационные процедуры
3.5.1 Точечные взаимодействия
3.5.2 Распространение
3.5.3 Сбор
3.5.4 Групповая арифметическая операция
3.5.5 Распределенное скалярное произведение
3.6 FORTRAN СПАРФ-MIMD
3.6.1 Unix Fortran
3.6.2 Microsoft Fortran
3.6.3 Intel iPSC/860 Fortran

возможным обрабатывать данные произвольной и динамической разрядности. Округления обуславливают тот факт, что время выполнения арифметических операций пропорционально точности вычислений. Сократить задержки и повысить эффективность вычислений позволяет возможность совмещения выполнения разных операций. Управление разрядностью осуществляется параметрически, т.е. заданием длины пакета (число разрядов), обрабатываемого одновременно узлами сети.
Мультипроцессорные системы. Как уже отмечалось, задача параллельной обработки заключается в ослаблении эффекта замедления скорости вычислений при росте длины операндов. В [12, 13] предложен способ организации вычислений с динамически изменяемой длиной операндов на параллельной системе, состоящей из достаточно большого числа модулей, называемых элементарными машинами (ЭМ) и объединенных между собой программно перестраиваемой системой связи. В минимальном варианте каждый модуль представляет собой “память с процессором”. Процессор имеет доступ к памяти других модулей. Архитектурные особенности таких систем позволяют трактовать полную оперативную память всей системы как двумерную, рассматривая адресацию в каждой ЭМ в качестве одной координаты, а адресацию самих ЭМ - в качестве другой. Программа хранится в базовой ЭМ, которая посылает команды остальным ЭМ в синхронно-программном режиме, подобно тому как это делается в параллельных БШБ-системах. Каждый операнд рассматривается как число следующего вида
£ а£_г-+1Сг_1 + Ъ{с~1
%—1 г
где основание с — 2 , а / - размер в битах стандартного слова в ЭМ; |ау | < с, |6г| < с, значения и Ьi могут быть как положительными, так и отрицательными; причем в одном слове коэффициенты разложения могут иметь разные знаки. Индекс при коэффициенте равен относительному в подсистеме номеру ЭМ, в которой этот коэффициент расположен. Ь - размер подсистемы, который определяется максимальной суммой 1 и /2. На Рис. 4а приведен пример расположения в памяти системы (в ячейках х)