ПОБУДОВА ПАРАЛЕЛЬНИХ АЛГОРИТМІВ

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

2.1 Теоретичні відомості

Два цілих числа й називаються порівняними за модулем ( – натуральне), якщо їх різниця ділитися на без залишку. Число називають модулем порівняння. Це записується так:

. (2.1)

Приклади:

, тому що ділиться на ;

, тому що ділиться на .

Запис означає, що саме число ділиться на , тобто .

Якщо зафіксувати деякий модуль порівняння , то всяке натуральне число можна єдиним образом представити у вигляді

, (2.2)

де – частка від ділення на , а – залишок, що збігається з одним із чисел .

Залишок називають лишком числа за модулем . Запис виду (2.2), де , допускає не тільки натуральні, але й будь-які цілі числа. З рівності (2.2) випливає, що , тобто всяке число порівнянне зі своїм лишком за модулем .

Обчислення називається модульним піднесенням до степені.

Нехай представлено в двійковому вигляді , де , тобто . Тоді

. (2.3)

Однак обчислення по формулі (2.3) не є ефективним, особливо для великих чисел, які використовуються, наприклад, у криптографії. Існує велика кількість більш ефективних алгоритмів, у тому числі паралельних, для виконання цієї операцїї. Деякі з них наведені нижче.

Алгоритм 2.1 Бінарний метод

Вхід: показник степені n ¹0 довжиною N біт, основа a, модуль m.

Вихід: .

1. Якщо n =1, то y:= a (mod m); закінчити роботу алгоритму.

2. k:= N –2; y:= a (mod m).

3. Для i, що приймає значення від k до 0, виконати кроки 4-5.

4. y:= y ² (mod m).

5. Якщо i- й біт n дорівнює 1, то y:= y• a (mod m).

6. Повернення y.

7. Закінчити роботу алгоритму.

Алгоритм 2.2 Спуск Монтгомері

Вхід: показник степені n ¹0 довжиною N біт, основа a, модуль m..

Вихід: .

1. y1=a (mod m), y2=a² (mod m).

2. Для i від N-2 до 0

Якщо i- й біт n дорівнює 1 то

y1=y1•y2 (mod m)

y2=y2² (mod m)

Інакше

y2=y1•y2 (mod m)

y1=y1² (mod m)

3. Повернення y 1.

4. Закінчити роботу алгоритму.

Приклад паралельної реалізації алгоритму Монтгомери на двухпроцесорному комп'ютері.

_{Таблиця 2.1 – Паралельне обчислення Y=a741 (74110=10111001012)}

Алгоритм 2.3 Метод гребеня

Нехай у нашім розпорядженні є процесорів. Розділимо двійковій вигляд показника степені на блоків по двійкових цифр кожний таким чином, що для -го блоку встановлюються в 0 всі цифри, крім -ой. При цьому - кількість двійкових цифр показника степені. А -а цифра приймає значення відповідної цифри у вхідному вигляді множника. Мовою формул це виглядає в такий спосіб:

або, у загальному виді:

,

де – кількість двійкових цифр;

– кількість блоків;

– кількість процесорів, рівна кількості двійкових цифр у кожному блоці;

– часткові множники, число яких дорівнює кількості процесорів;

.

Значення можуть бути легко отримані з n шляхом накладення по XOR відповідної маски. Тоді , де всі обчислюються кожна на своєму процесорі. Збільшення швидкості досягається за рахунок того, що часткові показники мають ваги Хеммінга (кількість одиничних битів у числі) менші, ніж вага Хеммінга вхідного показника n.

2.2 Хід роботи

2.2.1 Реалізувати бінарний метод модульного піднесення до степені.

2.2.2 Реалізувати двухпоточний варіант алгоритму Монтгомері.

2.2.3 Реалізувати метод гребеня модульного піднесення до степені. Для методу гребеня число потоків повинне вводитися із клавіатури під час виконання програми.

2.2.4 Порівняти час виконання операції модульного піднесення до степені трьома реалізованими методами.

2.3 Зміст звіту

2.3.1 Мета лабораторної роботи.

2.3.2 Графи алгоритмів.

2.3.3 Тексти розроблених програм.

2.3.4 Результати роботи програм.

2.3.5 Гістограма порівняння часу виконання розроблених програм.

2.3.6 Відповіді на контрольні питання.

2.4 Контрольні питання

2.4.1 Методи побудови паралельних алгоритмів. Послідовна та паралельна моделі програмування.

2.4.2 Парадигми паралельного програмування. Паралелізм даних. Паралелізм задач.

2.4.3 Як побудувати граф алгоритму?

2.4.4 З яких кроків складаеться розробка паралельного алгоритму? В чому сутність кожного кроку?

ЛАБОРАТОРНА РОБОТА № 3

ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования...

Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам...

ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры...

Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: