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

1. Кнут Д. Искусство программирования: Т. 2 Получисленные методы. – Массачусетс: Addison-Wesley, 1997. – С. 762.
2. Численное моделирование в маломодовой модели геодинамо с использованием пакетов вычислений произвольной точности / Чемарев А. С., Водинчар Г. М., Тристанов А, Б. // Вестник КРАУНЦ. Физ.-мат. науки. — Москва, 2011 — № 2(3). С. 80 – 88.
3. Arbitrary-precision arithmetic [Електронний ресурс].]. – Електрон. дан. – Режим доступу: http://en. wikipedia.org/wiki/Arbitrary-precision_arithmetic, вільний. – Назва з титул. екрану.
4. Multiprecision Integer and Rational Arithmetic C/C++ Library [Електронний ресурс]. – Електрон. дан. – Режим доступу: http://www.shamus.ie/, вільний. – Назва з титул. екрану.
5. GMP «Arithmetic without limitation» The GNU Multiple Precision Arithmetic Library [Електронний ресурс]. – Електрон. дан. – Режим доступу: http://gmplib.org/, вільний. – Назва з титул. екрану.
6. Plaszczak Pawel Grid Computing "The Savvy Manager's Guide" — Morgan Kaufmann Publishers. — ISBN ISBN 0-12-742503-9
7. Арифметика сверхбольших натуральных чисел в параллельных вычислительных системах / Макоха А. Н., Зуй Б. Ю. // Вестник СГУ. – Ставрополь: Изд-во СГУ, вып. 20, 1999.
8. Програмування у багатопроцесорних системах у стандарті MPI / Шпаковській Г. І., Сєрікова Н. В. – Мінськ: БГУ, 2002. – 323 с.
9. y-cruncher - A Multi-Threaded Pi-Program [Електронний ресурс]. – Електрон. дан. – Режим доступу: http://www.numberworld.org/y-cruncher/, вільний. – Назва з титул. екрану.

ПРИКЛАД РЕАЛІЗАЦІЇ АРИФМЕТИЧНИХ ОПЕРАЦІЙ ВЕЛИКОЇ ТОЧНОСТІ ДЛЯ МАСИВНО-ПАРАЛЕЛЬНИХ СИСТЕМ

Бувайло Д.П., Синєпольський І.В.

Багато сучасних математичних алгоритмів вимагають застосування арифметичних операцій над великими числами [1]. Розрядність таких чисел набагато перевищує довжину одного машинного слова ЕОМ, а в особливих випадках перевищує доступний об’єм оперативної пам’яті [2]. Крім того, інколи такі операції необхідно виконувати багатократно, наприклад, при піднесенні до степеня, або при організації масових обчислень.

У мовах програмування зазвичай немає вбудованих засобів для виконання розрахунків довільної точності. Для цього необхідно використовувати сторонні бібліотеки або вирішувати проблеми власноруч. На сьогоднішній день розроблено багато різних готових бібліотек для виконання подібних розрахунків таких, як IMSL, LiDIA [3], MIRACL [4], GMP [5], NTL [6], CLN, Imath та ін.

Серед безкоштовних бібліотек для наукового та навчального використання найбільш привабливою виглядає GMP (GNU Multi-Precision Library). Це вільна бібліотека довгої арифметики на мові програмування C, яка підтримує роботу зі знаковими цілими, раціональними числами, числами з плаваючою точкою. GMP на сьогоднішній день є однією з найшвидших бібліотек довгої арифметики. Перевагами GMP є практично не обмежена точність обчислення, окрім розміру оперативної пам’яті, багатий набір функцій і зручний інтерфейс, підтримка більшості сучасних операційних систем, використання найбільш ефективних алгоритмів і оптимізованого під різні сучасні процесорні системи асемблерного коду у всіх внутрішніх циклах.

Навіть незначне зменшення обчислюваної складності арифметичних операцій дає істотне зменшення часу обчислень. Іншим шляхом пришвидшення операцій є розробка алгоритмів для паралельних систем та суперкомп’ютерів. Бібліотека GMP не має вбудованих функцій для обчислень в багатопроцесорних та масивно-паралельних системах. Однак, маючи GMP за основу, можливо реалізувати паралельний алгоритм для обраного типу паралельних систем, використовуючи разом з GMP відповідний програмний інструментарій: OpenMP [8] для багатопроцесорних, MPI [8] для масивно-паралельних систем.

Щоб перебороти обмеження на об’єм оперативної пам’яті та використати загальне обладнання із персональних комп’ютерів, підходить тільки масивно-паралельні системи у вигляді кластера та специфікація бібліотеки передачі повідомлень MPI (Message passing interface) – програмний інтерфейс для передачі інформації, який забезпечує зв’язок між процесами паралельного додатку шляхом обміну міжпроцесними повідомленнями.

MPI – єдина бібліотека передачі повідомлень, яку можна розцінювати як стандарт для паралельних обчислювальних систем з розподіленою пам’яттю, включаючи масивно паралельні системи, SMP кластери, групи робочих станцій та гетерогенні мережі з персональних комп’ютерів. Вона підтримується фактично на всіх потужних комп’ютерах і локальних мережах. Перевагами MPI є мобільність, адаптованість до особливостей апаратної платформи, широкі функціональні можливості, доступність різноманітних комерційних та відкритих реалізацій.

Існує декілька реалізацій паралельних алгоритмів для розпаралелення арифметичних операцій для масивно-паралельних систем. Наприклад, алгоритми, запропоновані в роботі Макохи і Зуя [7] або паралельні алгоритми арифметичних операцій, запропоновані для обчислення константи [9]. Недоліками цих алгоритмів є недостатня увага на використання для локальних обчислень існуючих звичайних послідовних бібліотек, таких як GMP, недостатня увага щодо оцінок масштабування міжпроцесного обміну, а також їхні оцінки щодо масштабування обчислювань, які спираються на аналіз найгірших випадків.

Тому в даній роботі запропонований дещо інший підхід. Обов’язковою вимогою було масштабування обчислень за ліміти оперативної пам’яті одного обчислювального вузла паралельної системи. Додатковою вимогою була мінімізація міжвузлових переміщень даних. Щодо масштабування обчислювань, нас не стільки інтересував аналіз нечастих найгірших випадків, як добра поведінка у середньому. Покажемо як були втілені ці принципи.

По-перше, це схема подвійного зберігання, коли глобально розподілене число зберігається у десятковому форматі, і тільки його локальна порція для GMP зберігається у двійковому. Всі передачі даних здійснюються також у десятковому форматі. Це позбавляє нас від необхідності глобального перетворення формату при вводі-виводі, який є неприйнятним щодо об’ємів пам’яті, хоча й додає постійні локальні перетворення.

По-друге, це ітераційна «оптимістична» схема додавання, яка передбачає що ймовірність наявності переносу від сусіднього вузла при паралельному додаванні всіх частин числа – на першій ітерації дорівнює 0.5, а для усього колективу – за законом Бернуллі (P – кількість вузлів паралельного колективу), на другій стає , та на кожній наступній ітерації стає все менше й менше. Розуміється, існує можливість повного просування переносу через все число, але ймовірність цього дуже мала. В середньому можливо очікувати масштабування за часом та обсягом обчислень O(N/P), та деградації до O(N) у найгірших випадках, де N – кількість розрядів чисел.

За допомогою засобів MPI та GMP досить просто реалізувати паралельні арифметичні операції над довгими цілими числами. Кожне таке число зберігається в окремому файлі в десятковому форматі. Файл розподіляється порівну між вузлами паралельного колективу, з можливою нестачею на останньому вузлі. Також передбачена повністю паралельна схема зберігання с самого початку по частинам в окремих файлах на кожному вузлі.

Коли десяткове представлення числа вже розподілено поміж вузлами, локальний десятковий масив додатково за допомогою процедури GMP конвертується у спеціальну структуру даних цієї бібліотеки (mpz_t), яка представляє собою одне довге число разом із службовою інформацією про нього. Таким чином процеси готові для колективних арифметичних операцій. В якості прикладу розглянемо операцію додавання.

При виконання вказаних вище дій над двома вхідними файлами в локальній пам’яті кожного процесу знаходяться два блока представлених структурою GMP. Наступним кроком буде додавання цих чисел за допомогою процедури бібліотеки (mpz_add). При переповненні суми розмір результуючого блоку буде максимум на одиницю більше стандартного розміру блоку. У такій ситуації, керуючись стандартним алгоритмом додавання в стовпчик, необхідно до суми відповідних старших блоків додати одиницю, а поточне додавання робити по модулю бази. Цю потребу можна виконати, якщо скинути старшу значущу цифру переповненої суми (розмір блоку автоматично зменшиться на одиницю) і встановити одиницею спеціальну змінну – прапорець переносу, який в початковому стані дорівнює нулю.

Оскільки процеси виконуються незалежно один від одного, то треба сповістити, якому процесу потрібно до суми додавати одиницю. Для цього в локальній пам’яті кожного процесу створюємо масив з кількістю елементів, що дорівнює кількості процесів, і за допомогою колективної процедури бібліотеки MPI збираємо в цей масив значення вище вказаного прапорця кожного процесу, за виключенням останнього. Тоді кожний процес дізнається про необхідність додавання до суми одиниці. Однак внаслідок додавання одиниці знову може відбутись переповнення, тому вище вказану послідовність дій необхідно виконувати, доки останнє «зібрання» прапорців не покаже, що всі прапорці дорівнюють нулю. Слід зауважити, що ймовірність кожної наступної ітерації такого циклу значно зменшується. У найгіршому випадку цикл виконається P-1 раз, де P – кількість процесів.

Після цього зостається зробити «злиття» блоків кожного процесу, починаючи із старшого (кореневого), у результуючий файл, або продовжити інші обчислення. Це можна зробити користуючись вбудованими процедурами виведення GMP або конвертувати число із спеціальної структури даних у звичайний масив скалярних цілочисельних типів і вже потім вивести за допомогою стандартних процедур виведення.

Нижче у таблиці надано результати застосування розробленого алгоритму до тестових прикладів.

Кількість десяткових розрядів числа N	Кількість вузлів колективу P	Кількість комп’ютерів	Максимальний обсяг пам’яті для одного вузла
10млн			34МБ
100млн			175МБ
1млрд			1150МБ

Оскільки для обчислень використовувався звичайно один, та одного раз максимум два комп’ютера, дані щодо часу обчислень не наводяться, але масштабування за часом співпадає з очікуваним, також як масштабування за пам’яттю.