Сдам Сам

ПОЛЕЗНОЕ


КАТЕГОРИИ







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





Мета роботи: одержати навички програмування багатопоточних додатків в 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 2 (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=a2 (mod m).

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

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

y1=y1•y2 (mod m)

y2=y22 (mod m)

Інакше

y2=y1•y2 (mod m)

y1=y12 (mod m)

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

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

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

 

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

Процесор І Процесор ІІ
  Y1=a Y2=a2
  Y1=a2 Y2=a3
  Y1=a5 Y2=a6
  Y1=a11 Y2=a12
  Y1=a23 Y2=a24
  Y1=a46 Y2=a47
  Y1=a92 Y2=a93
  Y1=a185 Y2=a186
  Y1=a370 Y2=a371
  Y1=a741  

Алгоритм 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 км? Что будет с Землей? - задался я вопросом...

ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала...





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


©2015- 2024 zdamsam.ru Размещенные материалы защищены законодательством РФ.