*111975*

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

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

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

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

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

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

В работе предлагается новый подход к организации высокоточных параллельных вычислений с плавающей точкой – смешанный модулярно-позиционный формат, в котором для представления мантисс операндов используется многомодульная система остаточных классов (СОК) с основаниями 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 модулярных мантисс взаимно независимы, обеспечивается возможность реализации глубоко параллельных высокоточных алгоритмов выполнения арифметических операций. Так же решается задача минимизации зависимости времени выполнения операций от точности (при добавлении дополнительных оснований СОК для увеличения точности, в случае, если их число превышает число вычислительных устройств, время выполнения операций увеличивается линейно, а не экспоненциально, как в позиционных библиотеках, таких как GMP и MPFR). Ко всему прочему, модулярно-позиционные структуры данных более компактны, относительно структур, построенных на основе длинной позиционной арифметики. Это позволяет существенно снизить расход памяти при выполнении высокоточных вычислений над большими массивами данных.

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

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

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

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

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