Арифметика надвеликих натуральних чисел в паралельних обчислювальних системах

АРИФМЕТИКА Надвеликі натуральних чисел у ПАРАЛЕЛЬНИХ ОБЧИСЛЮВАЛЬНИХ СИСТЕМАХ
Макоха О.М., Зуй Б. Ю.
В даний час існує необхідність проводити обчислення з дуже великими цілими числами (тобто з числами, що не поміщаються у розрядну сітку регістрів АЛУ процесора) в таких областях як кодування інформації, криптографія, фізика, астрономія і т. д.
Архітектура 32-х розрядних систем дозволяє обробляти числа в максимальному діапазоні 0 .. 4294967295. Але це занадто вузький діапазон натуральних чисел для вирішення багатьох прикладних завдань. Для розширення діапазону розробники програмного забезпечення пропонують різноманітні методи вирішення даної задачі. Засоби для роботи з великими цілими числами є в таких програмних пакетах як Java, Сі, Perl. Ефективним способом виконання операцій над надвеликими цілими числами є їхнє уявлення в системі залишкових класів, де немає переносів з молодших розрядів до старших [3]. Однак тут виникає своя проблема перебування залишків від ділення надвеликого числа на основи системи залишкових класів.
Діапазон подання натуральних чисел можна значно розширити, реалізувавши нескладні алгоритми операцій над даними на мові Асемблера [1], збільшивши при цьому довжину слова в десятки разів. Розроблено алгоритми подання та зберігання в пам'яті ЕОМ великих цілих чисел у вигляді пов'язаних списків [2]. Нехай ( ) - Список загального вигляду. Комп'ютерне подання списку складається з n осередків, пов'язаних через їх поля посилань, разом з передбачуваними вже даними уявленнями кожного із значень x _i , Що є у свою чергу списками.   
У даній роботі пропонуються алгоритми виконання арифметичних операцій над надвеликими натуральними числами, представленими у вигляді списків (послідовності біт або послідовності десяткових знаків), за допомогою відносного розпаралелювання цих операцій на багатопроцесорних системах. Нехай , , - Надвеликі натуральні числа. Розіб'ємо ці числа на слова по підставі , Де - Довжина слова:
,
,
,
при цьому коефіцієнти . Оскільки будуть розглядатися числа без знака, то для всіх міркувань будемо припускати, що . Тоді
а) при додаванні
, ;
б) при вирахуванні
, ;
в) при множенні
, .
Приступимо до безпосереднього опису алгоритмів перерахованих операцій.
Нехай є паралельна обчислювальна система: схема процесорів або локальна мережа. Назвемо елемент системи (процесор, комп'ютер) пристроєм. Є загальний простір осередків пам'яті. З усіх пристроїв системи виділяється управляє (УУ), що виконує функції ініціалізації системи, аналізу даних.
Ініціалізація системи
УУ аналізує наявність пристроїв системи і кожного пристрою присвоює порядковий номер, виділяє комірки пам'яті для кожного пристрою, а також необхідну кількість біт для зберігання двох слів (для зберігання ). Після ініціалізації всі пристрої працюють з відведеними для них комірками пам'яті.
А. Складання
Система ініціалізує подвійних слів; -Е подвійне слово відповідає -Ому пристрою ( ), . У молодші байти слів УУ записує , В старші - , Причому . Потім УУ дає команду на початок роботи, після чого всі пристрої працюють одночасно за наступним алгоритмом: пристрій
А1. Зчитує дані з відведених для нього осередків пам'яті.
А2. Виконує складання (Додавання даних з молодших і старших байтів слів).
А3. Записує в молодші байти слова, відповідного пристрою : .
А4. Записує в старші байти свого ж слова:
.
А5. Повідомляє УУ про завершення роботи.
Далі УУ аналізує перший біт старших байтів слів, наприклад, за допомогою логічної операції диз'юнкції і, якщо результат цієї операції дорівнює 0, формує результат з молодших байтів слів. Якщо результат цієї операції дорівнює 1, то повертаємося до кроку А1.
Таким чином, розглянутий алгоритм, в залежності від чисел і , Може видати результат не більше ніж через n + 1 кроків, тоді як послідовні алгоритми видають результат строго через n + 1 кроків для таких же чисел.
Б. Віднімання
Система ініціалізує подвійних слів, при цьому -Е подвійне слово відповідає -Ому пристрою ( ), . У молодші байти слів УУ записує , В старші - , Причому для . Потім УУ дає команду на початок роботи, після чого всі пристрої працюють одночасно за наступним алгоритмом: пристрій
Б1. Зчитує дані з комірок пам'яті.
Б2. Виконує віднімання .
Б3. Записує в молодші байти слова відповідне пристрою значення

Б4. Записує в старші байти слова значення :

Б5. Повідомляє УУ про завершення роботи.
Далі УУ аналізує перший біт старших байтів слів, наприклад, логічною операцією диз'юнкції і, якщо результат цієї операції дорівнює 0, то формує результат з молодших байтів слів. Якщо ж результат цієї операції дорівнює 1, то повертаємося до кроку Б1.
Аналогічно додаванню кількість кроків варіюється від 1 до n + 1.
В. Множення
Алгоритм множення дещо складніше в реалізації, але нагадує собою множення в стовпчик.
Система ініціалізує подвійних слів. При цьому розподіл елементів пам'яті при ініціалізації можна представити у вигляді таблиці 1:
Таблиця 1. - Розподіл елементів пам'яті при ініціалізації

	...		0	...		...		0	0
	...		0	...		...		0	0
осередків				...	осередків
осередків

Спочатку обчислюються одночасно числа , Що представляють собою множення на число , За наступним алгоритмом: пристрій
В1. Зчитує дані з комірок пам'яті.
В2. Виконує множення ( , J ).
В3. Записує в молодші байти слів: , .
В4. Записує в старші байти слів: .
В5. Для кожної -Ки відбувається складання за алгоритмом А.
Після кроку В5 в старших байтах слів будуть міститися (Таблиця 2):
Таблиця 2. - Розподіл елементів пам'яті після операції множення

	...			...		...			...	0
осередків				...	осередків
				...

Результат множення формуємо з складанням із зсувом на розрядів.
Кількість кроків варіюється від 1 до , У той час як послідовне обчислення твори займе кроків.
Пропоновані алгоритми можуть бути реалізовані на однорідних обчислювальних середовищах, систолічних структурах, нейронних мережах.

Література
1. Юров В. Assembler. - СПб.: Видавництво «Пітер», 2000.
2. Акрітас А. Основи комп'ютерної алгебри з додатками. - М: Світ, 1994.
3. Макоха А.Н., Іонісян А.С. Комп'ютерна емуляція арифметичних операцій над цілими і раціональними числами в СОК. / / Вісник СГУ. - Ставрополь: Вид-во СГУ, вип. 20, 1999.