автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Высокоточные вычисления с динамической длиной операндов в многопроцессорных системах

Н ¡Г, ) /'

/ //'./■ '.у'' / '

РОССИЙСКАЯ АКАДЕМИЯ НАУК

Сибирское отделение

Институт Вычислительной Математики и Математической Геофизики

на правах рукописи

Морозов Виталий Александрович

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

05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей

Диссертация на соискание ученой степени кандидата технических наук

\

\ \

Л. \

V < / ,

* ¡Л'

Научный руководитель доктор технических наук, профессор В.Э. Малышкин

Научный консультант кандидат технических наук А.П. Важенин

Новосибирск - 1999

ОГЛАВЛЕНИЕ

1 ДИНАМИЧЕСКАЯ ДЛИНА ОПЕРАНДОВ КАК СРЕДСТВО

ПОВЫШЕНИЯ ТОЧНОСТИ ВЫЧИСЛЕНИЙ 17

1.1 Способы устранения ошибок округления........................18

1.1.1 Системы аналитических преобразований................18

1.1.2 Учет и оценка погрешности округления ................19

1.1.3 Арифметика многократной точности....................20

1.2 Анализ применяемых вычислительных алгоритмов............20

1.2.1 Матричные вычисления....................................21

Умножение матриц..........................................21

Итерационные вычисления..................................23

Прямые методы решения СЛАУ..........................24

1.2.2 Проблемы вычислительной геометрии....................25

1.3 Организация вычислений с динамической длиной операндов . 26

1.3.1 Последовательные вычисления .у** у ..................27

Пакет программ АСЫТН. ...........................27

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

Пакет ЫМ-арифметики......................................30

1.3.2 Распараллеливание операций многоразрядной арифметики ..........................................................30

Конвейерные ЭВМ..........................................31

Вычислительные среды и нейронные сети................33

Мультипроцесорные системы..............................35

1.4 СПАРО-БШИ) вычисления........................................37

Высокоточные векторные операции........................40

1.5 Выводы..............................................................42

2 АЛГОРИТМИЧЕСКОЕ ОБЕСПЕЧЕНИЕ

СПАРФ-ВЫЧИСЛЕНИЙ 44

2.1 М1МБ-системы. работающие в режиме передачи сообщений . 44

2.2 Топология коммуникационной сети..............................45

2.3 Критерии оценки и вычислительная сложность алгоритмов . 46

2.4 Способы оценки коммуникационных затрат....................49

- 32.5 Модель передачи сообщений......................................51

2.5.1 Точечные взаимодействия ................................53

Операции блокирующего типа..............................53

Операции неблокирующего типа..........................53

2.5.2 Упаковка/распаковка данных............................54

2.6 Групповое движение данных......................................55

2.6.1 Распространение............................................56

2.6.2 Сбор и распределение......................................56

2.6.3 Групповые арифметические операции....................58

2.6.4 Скалярное произведения двух векторов..................61

2.6.5 Сложные типы обменов....................................61

2.7 Организация многоразрядной арифметики с динамической длиной операндов ......................................................63

2.7.1 Алгоритмы сложения/вычитания........................64

2.7.2 Алгоритмы логических сдвигов..........................66

2.7.3 Алгоритмы умножения....................................67

2.7.4 Вычисление обратной величины..........................68

2.8 Анализ точности вычисления арифметических операций ... 70

2.8.1 Вычисление сложения и вычитания......................71

2.8.2 Вычисление логических сдвигов..........................72

2.9 Алгоритмы ускоренного умножения/деления....................73

2.9.1 Построение и анализ алгоритмов........................74

Умножение....................................................74

Деление........................................................80

2.9.2 Точность вычисления операций..........................81

2.10 Элементарные функции............................................86

2.10.1 Обзор основных методов ..................................86

2.10.2 Вычисление функции у = sin х............................91

2.10.3 Вычисление функции у = cos х............................92

2.10.4 Вычисление функций у = tg х и у = ctg х ..............93

2.10.5 Вычисление функции у = Inх ............................93

2.10.6 Вычисление функции у = ..............................95

2.10.7 Вычисление функции у = ех..............................98

2.11 Выводы..............................................................98

3 ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ

СПАРФ-ВЫЧИСЛЕНИЙ 100

3.1 Вычислительная система Intel iPSC/860 ........................100

3.1.1 Аппаратное обеспечение ..................100

Хост-машина........................100

Стандартный блок.....................101

3.1.2 Программное обеспечение ................101

3.1.3 Организация коммуникационных процедур.......102

3.2 Вычислительная система Parsytec PowerXplorer........103

3.2.1 Аппаратное обеспечение .................103

3.2.2 Программное обеспечение ................104

3.2.3 Организация коммуникационных процедур.......105

3.3 Форматы СПАРФ-чисел и способы организации вычислений . 106

3.4 СПАРФ-библиотека для MIMD-вычислений..........109

3.4.1 Арифметические операции................110

3.4.2 Арифметико-логические операции............110

3.4.3 Функции преобразования форматов данных......114

3.4.4 Функции управления ресурсами.............114

3.4.5 Функции управления разрядностью...........115

3.4.6 Операции межпроцессорных взаимодействий......116

3.4.7 Сервисные функции....................118

3.5 Базовые коммуникационные процедуры.............118

3.5.1 Точечные взаимодействия ................119

3.5.2 Распространение......................120

3.5.3 Сбор.............................122

3.5.4 Групповая арифметическая операция..........124

3.5.5 Распределенное скалярное произведение ........127

3.6 FORTRAN СПАРФ-MIMD....................129

3.6.1 Unix Fortran........................130

3.6.2 Microsoft Fortran......................131

3.6.3 Intel iPSC/860 Fortran...................132

3.6.4 Parsytec PowerXplorer Fortran ..............132

Последовательная FORTRAN-программа........132

Параллельная FORTRAN-программа...........133

3.7 Выводы...............................134

4 ОРГАНИЗАЦИЯ И ВЫПОЛНЕНИЕ

ВЫЧИСЛЕНИЙ С ИСПОЛЬЗОВАНИЕМ СПАРФ-MIMD 136

4.1 Скалярное произведение векторов................136

4.2 Вычисление полиномов......................140

4.3 Численное интегрирование....................142

4.4 Решение систем линейных алгебраических уравнений .... 143

4.4.1 Итерационные методы ..................146

Улучшение сходимости итерационных методов.....148

Параллельный алгоритм..................149

Использование стандартных типов данных.......152

Использование многоразрядных данных.........153

4.4.2 Прямые методы......................158

4.5 Произведение матриц.......................164

4.6 Выводы...............................170

5 ИСПОЛЬЗОВАНИЕ СП АРФ В ЗАДАЧЕ О РАВНОВЕСНОЙ ФОРМЕ СВОБОДНОЙ ПОВЕРХНОСТИ ЖИДКОСТИ

В ВИБРАЦИОННОМ ПОЛЕ 173

5.1 Постановка задачи, основные уравнения............173

Вариационная формулировка...............176

5.2 Вычислительная схема......................178

5.3 Основные результаты вычислительных экспериментов .... 181

5.4 Высокоточная проверка полученного результата .......184

5.5 Вывод................................186

6 ЗАКЛЮЧЕНИЕ 188

7 ПРИЛОЖЕНИЕ 197

ВВЕДЕНИЕ

Диссертация посвящена организации вычислений с динамической длиной операндов на базе многопроцессорных систем с передачей сообщений.

Актуальность темы. При обработке данных на ЭВМ полученный результат. как правило отличается от истинного. Это отклонение определяет погрешность вычислений. Различают три типа погрешностей: погрешности метода, погрешности в исходных данных и погрешности округления и представления. Если первые два типа погрешностей связаны с компьютером не так явно, то ошибки округления и представления появляются в связи с фиксированной и относительно малой длиной операндов в современных компьютерах. Для уменьшения влияния или проведения учета погрешностей округления и представления необходимо разрабатывать специальные алгоритмические или программные средства.

В настоящее время вычислитель часто сталкивается с задачами, которые невозможно решить без применения многоразрядных форматов. Примерами может служить задача, промежуточные результаты в которых невозможно представить в стандартном формате плавающей запятой (64 разряда). Задача обращения матрицы Гильберта часто появляется при переходе из цилиндрической системы координат в сферическую. Аналитическое решение получить затруднительно, а значения, составляющие обратную матрицу имеют очень большие абсолютные величины. Другим примером является вычислительный алгоритм, содержащий данные из большого диапазона. Постоянная Планка И = (6.626176 =Ь 0.000036) • Ю-27 эрг• с. отношение длины окружности к диаметру 7г « 3.1415926535897932. и масса Солнца М© = 1.99 • 1033г имеют различие 60 порядков. Использование в одном алгоритме таких величин может привести к непредсказуемым результатам.

Программная реализация или микропрограммная интерпретация арифметики с увеличенной длиной слова может сильно замедлить вычислительный процесс. Использование динамической длины операндов является одним из способов ускорения решения задачи. Ускорение вычислительного процесса достигается путем обработки каждый раз лишь такого количе-

ства разрядов, которое позволяет получить результат с гарантированной точностью.

Широкое распространение параллельных ЭВМ различного типа вновь поднимает вопрос точности вычислений. Помимо потенциальных источников появления ошибок при последовательной обработке, параллельная обработка содержит дополнительные возможности их возникновения в силу особенностей аппаратной реализации арифметических операций. Таким образом, как показано в работах Ратца, Хаммера. Миренкова, параллельные ЭВМ менее точны, чем последовательные.

Тем не менее, параллельная обработка открывает широкие возможности для организации вычислений с повышенной точностью. Традиционно, параллельные ЭВМ рассматриваются как ускорители последовательной обработки информации. Известно большое число научных и практических работ по созданию средств поддержки вычислений с программируемой разрядностью как на базе последовательных, так и параллельных ЭВМ. Большинство известных систем реализует последовательный высокоточный вычислитель с программируемой длиной слова, либо конвейеризует вычисления.

Системы с распределенной памятью являются одним из важнейших подклассов параллельных ЭВМ типа МШТ). Относительно низкая стоимость, но, в то же время, достаточно высокая производительность делает этот тип компьютеров привлекательным для решения различных вычислительных задач. Поэтому вопрос повышения точности параллельных ЭВМ с передачей сообщений является актуальным.

Целью диссертационной работы является создание алгоритмических и программных средств поддержки высокоточных вычислений с динамической длиной операндов на базе М1МБ-систем с распределенной памятью, а также разработка методики проектирования высокоточных алгоритмов с изменяемой длиной слова для этих систем. Достижение указанной цели связано с решением следующих задач:

• разработка и анализ формата высокоточных чисел, допускающего передачу по межпроцессорной сети и произвольное изменение длины;

• анализ выполнения арифметических операций и специальных (в том числе распределенных) процедур при обработки данных в этом формате;

• разработка переносимой системы программирования высокоточных вычислений с динамической длиной операндов для параллельных ЭВМ с передачей сообщений;

• разработка способов регулирования разрядности операндов при решении практических задач (прежде всего, задач линейной алгебры и матричного анализа);

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

В диссертации предлагается использовать многоразрядные данные в каждом вычислительном узле параллельной системы. Обработка длинных чисел проводится аналогично числам в традиционном формате представления. Такой подход позволяет получать ускорение путем параллельной обработки самих длинных операндов. Таким образом, появляется возможность комплексного использования высокоэффективных параллельных алгоритмов. наилучшим образом приспособленных к решению прикладной задачи на данной архитектуре; многоразрядной арифметики, позволяющей в принципе исключить ошибки округления и представления данных из вычислительного процесса; и динамической длины операндов, позволяющей на каждом этапе вычислений использовать только значащие разряды. Этот подход ведет к существенному ускорению обработки информации либо созданию иного способа ее обработки (иного метода).

Научная новизна заключается в разработке высокотехнологичной методики решения задач с требуемой точностью на параллельных ЭВМ с распределенной памятью, а также в проектировании программного обеспечения, необходимого для реализации этой методики. Научную новизну раскрывают следующие результаты:

Первое - Созданы теоретические предпосылки и методика проектирования высокоточных алгоритмов и программ для параллельных ЭВМ с распреде-

ленной памятью. Преодоление погрешностей округления и представления данных за приемлемое время осуществляется путем комплексного использования многоразрядной арифметики, динамической длины операндов и параллелизма базового компьютера. Показана практическая эффективность данных систем.

Второе - Обоснована возможность использования параллельных систем с распределенной памятью, обменивающихся информацией посредством приема/передачи сообщений, в качестве базы для создания средств программирования высокоточных вычислений с динамической длиной операндов. Показана целесообразность использования совмещенной оценки коммуникационных затрат, позволяющей учитывать коммуникационное замедление алгоритма.

Третье - Разработан специализированный формат данных. Изучены и разработаны способы выполнения арифметических операций, операций регулирования разрядности и процедур межпроцессорных взаимодействий. Предложен и исследован ряд высокоточных алгоритмов реализации стандартных арифметических и специальных сервисных функций (тригонометрических. логарифмической и т.п.) использующих динамическую длину операндов.

Четвертое - Разработана мобильная библиотека программ, поддерживающая вычисления с динамической длиной операндов как на последовательных ЭВМ с различными трансляторами, так и на ряде параллельных компьютеров с различной организацией межпроцессорных обменов. При этом, структура библиотеки позволяет учесть коммуникационные свойства конкретной системы, позволяя перенастраивать только процедуры межпроцессорных взаимодействий.

Пятое - На базе созданного пакета программ разработан ряд параллельных алгоритмов решения систем линейных алгебраических уравнений прямыми и итерационными методами и решения задач матричного анализа. Показан способ регулирования разрядности и автоматического выбора длины операндов для сходимости итерационного процесса. Разработанные алгоритмы проверены не только на тестовых примерах, но и при решении реальной физической задачи вибрационной конвекции.

Шестое - Получены опенки сложности алгоритмов групповых межпроцессорных взаимодействий и параллельных вычислительных алгоритмов с динамической длиной операндов, коэффициенты ускорения вычислений как за счет использования параллелизма вычислительной системы, так и за счет использования динамической длины операндов.

Практическая ценность полученных результатов состоит в том. что спроектирован метод программирования прикладных MIMD-систем, позволяющий комплексно использовать многоразрядную арифметику, динамическую длину операндов и естественный параллелизм многопроцессорного компьютера, а значит и алгоритмы, наилучшим образом приспособленные для этого класса систем.

Получены основные характеристики комплекса программ, разработана технология его использования, получены результаты численного решения ряда типовых задач для машин IBM PC, Power Xplorer фирмы Parsytec, Silicon Graphics Indy и Silicon Power Challenge фирмы Silicon Graphics Inc. гиперкуба Intel iPSC-860 (Intel) и созданной в НИИ "КВАНТ"на базе процессора i860 системы МВС-100, мультитранспьютерной системы Т800-20. Созданы С и FORTRAN версии программного обеспечения для названных ЭВМ. Проведенные в работе исследования позволили перенести пакет на целый ряд вычислительных систем как последовательного так и параллельного действия, а значит использовать его при решении научных и практических задач на этих системах.

На основании приобретенного опыта разработки, реализации и практического использования названных выше средств, делается вывод, что разработанные параллельные программы могут быть использованы при создании новых типов численных экспериментов и новых вычислительных алгоритмов. Использование методов автоматического выбора длины операндов и пошагового уточнения в итерационном алгоритме позволяет упростить проблему выбора метода при решении большого числа задач.

Полученные результаты могут быть использованы в учебном процессе для изучения новых типов параллельных архитектур и алгоритмов, как достаточно сильно устойчивых к влиянию погрешностей округлений, так и чрезвычайно неустойчивых к таким погрешностям.

Реализованная библиотека программ включена в состав системы Сверхточной Параллельной АРиФметики (системы СПАРФ-вычислений) и является составной частью системы высокоточных вычислений СПАРФ-MIMD.

Апробация работы Основные положения и результаты диссертационной работы докладывались и обсуждались на объединенном семинаре отдела Высокопроизводительных Выч�