*111976*

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

К.С. Исупов, В.С. Князьков, А.В. Логинов

Вятский государственный университет

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

Предлагается новый способ организации высокоточных параллельных вычислений с плавающей точкой, который основывается на модулярно-позиционном формате с плавающей точкой [1]. В модулярно-позиционном формате для представления мантисс чисел используется многомодульная система остаточных классов (СОК) с основаниями p₁,p₂,…,p_n [2], являющимися целыми попарно взаимно простыми положительными числами, не выходящими за пределы разрядности процессоров, а для представления порядков – позиционная система счисления. Мантиссы чисел в СОК (модулярные мантиссы) состоят из наборов взаимно независимых разрядов m₁,m₂,…,m_n, причем m_i<p_i для i=1,2,…,n и могут, в общем случае, изменяться в пределах интервала [0, P-1], где P - произведение p₁·p₂·…·p_n.

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

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

В качестве алгоритмической базы для экспериментов исследовался высокоточный параллельный алгоритм умножения матриц. Далее, путем серии численных расчетов, была установлена зависимость времени умножения матриц от точности вычислений, представленная на рисунке 1, где на оси абсцисс указаны значения разрядности мантисс. Эксперименты проводились на восьмиядерных вычислительных узлах высокопроизводительной вычислительной системы Enigma (HP Hewlett-Packard Cluster Platform 3000 BL460c, Intel EM64T Xeon 5345, 2,3 ГГц, Infiniband) Вятского государственного университета. В качестве аналога для исследования была выбрана библиотека GMP.

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

Рисунок 1 – Зависимость времени умножения матриц от разрядности

Список литературы

1. Князьков В. С., Исупов К. С. Модулярный формат со взвешенным порядком для высокоточной разрядно-параллельной аппроксимации вещественных чисел // «Общество, наука, инновации (НТК-2012)»: Сб. материалов. Статья № 1. Киров: ВятГУ, 2012. 13 с.

2. Акушский И. Я., Юдицкий Д. И. Машинная арифметика в остаточных классах. М.: Сов. Радио, 1968. 440 с.