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

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

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

Он кивнул.

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

— Может, вы знаете, что здесь произошло? Где все?

— Ушли на запад. Уже несколько недель. Кажется, какой-то тип из Нью-Йорка получил эту землю от Конгресса. Видимо, там решили, что согласие тех, кто всегда жил на этой земле, не требуется.

— Как? — сказал я.

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

— Как это случилось? — я оглядывался по сторонам и видел лишь пустоту там, где когда-то были знакомые лица — моего родного народа.

— Мы теперь сами по себе, — продолжил он. — Больше никаких англичан. За все отвечаем. И платим тоже. Продать землю легко и просто. И с налогами возиться не надо. Говорят, вся война из-за налогов, вот и не торопятся их вводить.

Он хрипло засмеялся.

— Смышленые парни эти наши новые правители. Не торопятся. Знают, что слишком рано. Слишком… по-английски. — Он смотрел на огонь. — Но ведь вернут. Как всегда.

Я поблагодарил его и пошел к большому дому и по дороге думал: я не сумел. Мой народ ушел — его выжили те, о ком я думал, что они защитят его.

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

Я стоял на лесной опушке, и в одной руке у меня было мамино ожерелье, а в другой — амулет отца.

Мысленно я говорил: «Мама. Отец. Я виноват. Я подвел вас обоих. Я хотел защитить наш народ, Мама. Я думал, что если остановить тамплиеров, если уберечь революционную свободу от их влияния, то те, кому я помог, устроят всё правильно. И они устроили правильно — правильно для них. Отец, я думал, что смогу объединить нас, что мы забудем прошлое и создадим лучшее будущее. Тогда я верил, что ты можешь видеть мир таким, каким его вижу я. Но это была лишь мечта. Мне следовало это понять. Неужели нам не дано было жить в мире? Почему? Неужели мы родились, чтобы спорить? Враждовать? Столько вопросов.

Тогда было тяжело, но сегодня труднее. Видеть свои труды извращенными, отвергнутыми, забытыми. Ты скажешь, я сочинил целую историю, Отец. Ты улыбаешься? Надеешься, что я произнесу слова, которые ты жаждал услышать? Соглашусь с тобой? Скажу, что ты был во всем прав? Нет. Даже теперь, когда я стою лицом к лицу с истиной твоих нелестных слов, даже теперь я не соглашусь. Потому что я верю — всё меняется.

Может быть, я не достигну цели. Ассасины могут еще тысячу лет бороться напрасно. Но мы не остановимся».

Я принялся копать.

«Компромисс. Вот чего все требовали. И я узнал, что это такое. Но в отличие от большинства, я думал. Теперь я знаю, что потребуется время, что путь предстоит долгий, и идти придется во тьме. Иногда мне захочется свернуть с пути, и я сомневаюсь, что мне хватит всей жизни, чтобы осилить его. И все-таки я буду идти».

Я копал и копал, пока не счел, что довольно: яма была теперь глубже, чем требуется для могилы, и достаточная, чтобы я мог из нее выбраться.

— У меня остается надежда. Перед лицом всех, кто настаивает, чтобы я отступился, я повторяю: вот он, мой компромисс.

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

Полный надежд на будущее, я возвращался к своему народу, к ассасинам.

Пришло время новой крови.

LIST OF CHARACTERS

Achilles:Assassin

al-Azm, As’ad Pasha:Ottoman governor, d. 1758

Amherst, Jeffrey:British commander, 1717–97

Barrett, Tom:youngest son of the Barretts

The Barretts:neighbors to the Kenways

Betty:nursemaid, assistant to Edith

Birch, Reginald:senior property manager for Edward Kenway

Braddock, Edward:British soldier, 1695–1755

Church, Benjamin:doctor, 1734–78

Connor:Assassin

Cutter:torturer

Miss Davy:Tessa Kenway’s lady’s maid

The Dawsons:neighbors to the Kenways

Digweed, Jack:Edward Kenway’s gentleman

Douglass, Cornelius and Catherine Kerr:owners of the Green Dragon

Edith:nursemaid

Emily:chambermaid

Fairweather, James:ship passenger

Mr. Fayling:tutor

Harrison, John:Knight of the Order

Hickey, Thomas:associate of William Johnson’s, d. 1776

Holden, Jim:soldier and Haytham’s gentleman

Johnson, William:official, 1715–74

Kaniehtí:io (also Ziio):Mohawk woman

Kenway, Edward:Haytham’s father

Kenway, Haytham:writer of these journals

Kenway, Jenny:Haytham’s sister

Kenway, Tessa née Stephenson-Oakley:Haytham’s mother

Lee, Charles:soldier, 1732–82

Pasha, Raghib:grand vizier in Istanbul

Pitcairn, John:soldier, 1722–75

Scott, Caroline:Jenny’s mother

Mrs. Searle:the Kenway’s housekeeper

Mr. Simpkin:estate executor

Slater:Braddock’s lieutenant

Thatcher, Silas:slaver

Twitch:informant

Varela:Spanish cheesemaker

Vedomir, Juan:Spanish investor

Violet:neighbor

Washington, George:soldier, later commander in chief of the Continental Army, 1732–99

[1] Пэл-мэл — старинная игра в шары, вроде крокета. (Здесь и далее, если не оговорено особо, примечания переводчика).

[2] Шоколадный Дом Уайта или White's Chocolate House или Mrs. White's Chocolate House — популярный в Лондоне джентльменский клуб.

[3] Мистер Панч — персонаж народного английского кукольного театра. Известен язвительностью, злым характером и уродливой внешностью.

[4] Война за австрийское наследство — война Австрии против Баварии, Пруссии, Испании, Швеции и Франции, которые оспаривали права императрицы Марии Терезии на австрийский престол. Длилась с 1740 по 1748 г. Англия в этой войне выступала, в числе прочих, союзницей Австрии.

[5] Румаль (румал) — шелковый платок или шарф с завязанной на конце монетой. Использовался индийскими тхагами для ритуального удушения жертвы в честь богини Кали.

[6] Фраза на испанском языке.

[7] Уздечка сплетницы(англ. scold’s bridle) — средневековое орудие пытки для женщин, представлявшее собой железную маску с зазубренным нагубником.

[8] Royal Opera House — Королевский оперный театр в лондонском Ковент-Гардене.

[9] От начала главы до сноски фрагмент перевел Pawel. Дальнейший перевод — Астроном.

[10] Главу перевел PiLeSoS.

[11] В оригинале stocked — сооружение в виде обнесенной частоколом площадки и примыкающего здания, иногда использовавшегося для содержания арестантов.

[12] Главу перевел PiLeSoS.

[13] В оригинале автор описывает морозную погоду, хотя битва при Мононгахеле происходила 9 июля, как и указано в заголовке. Ни в одном доступном источнике мороз не отмечен. Поэтому упоминания о морозе и снеге изъяты из текста переводчиком.

[14] Скаут — разведчик.

[15] Харамлик (арабск. харам – запретное место) — в странах Ближнего и Среднего Востока женская половина дома, недоступная для посторонних. Так же — гарем.

[16] Саламлик — мужская часть дома, доступная и для чужих.

[17] В оригинале prickless – т.е. буквально: лишенные «мужского достоинства».

[18] В оригинале: against one of His Majesty’s men.

[19] В оригинале: Begging your pardon, sir, but it’s my cock and balls they took off me, not my gumption.

[20] Слово «деревни» в предыдущей реплике Чарльза добавлено переводчиком. В оригинале его монолог выглядит так: “There was a boy at…” …. “Your Mohawk woman”.

[21] В оригинале: I gave a start, but he didn’t notice: New York was freezing, our breath hung in clouds, and he was far too preoccupied with keeping warm.

[22] Межеумок — ни то, ни сё, человек, который не может быть отнесен к определенному сорту, разряду.

[23] В оригинале каламбур: A church to find a Church.

[24] Янки — прозвище жителей Новой Англии, позднее — жителей США в целом. Во время Войны за независимость (1775-1783) английские солдаты называли так восставших колонистов.

[25] В оригинале: It seems to me your tongue has tasted sour grapes. — «Мне кажется, ты просто говоришь, что зелен виноград», т.е. просто не можешь дотянуться до вожделенного предмета.

[26] В оригинале: But my enemy is a notion, not a nation.

[27] От слов «Ты присвоил себе право судить…» до этой сноски монологи Хэйтема и Коннора даны в переводе русской локализации игры «Assassin’s Creed III».

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

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

Багато сучасних математичних алгоритмів вимагають застосування арифметичних операцій над великими числами [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 або конвертувати число із спеціальної структури даних у звичайний масив скалярних цілочисельних типів і вже потім вивести за допомогою стандартних процедур виведення.

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

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