Complexity analysis of multidigit multiplication operation for implementtation in parallel computational model

It is analyzed on computing operation of multidigit multiplication of N-digit values based on standard method in parallel computational model the complexity of number of operations of simple additions and multiplications for two cases: when number of available processors is unlimited, and when numbe...

Full description

Saved in:

Bibliographic Details
Date:	2017
Main Author:	Tereshchenko, A.N.
Format:	Article
Language:	Ukrainian
Published:	PROBLEMS IN PROGRAMMING 2017
Subjects:	UDC 519.6
Online Access:	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/133
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Problems in programming
Download file:

Institution

Problems in programming

id	pp_isofts_kiev_ua-article-133
record_format	ojs
resource_txt_mv	ppisoftskievua/93/2544838948752eb3a4dcccbd180b4b93.pdf
spelling	pp_isofts_kiev_ua-article-1332018-07-23T13:46:01Z Complexity analysis of multidigit multiplication operation for implementtation in parallel computational model Анализ сложности операции умножения многоразрядных чисел при реализации в параллельной модели вычислений Аналіз складності операції множення багаторозрядних чисел при реалізації у паралельній моделі обчислень Tereshchenko, A.N. UDC 519.6 УДК 519.6 УДК 519.6 It is analyzed on computing operation of multidigit multiplication of N-digit values based on standard method in parallel computational model the complexity of number of operations of simple additions and multiplications for two cases: when number of available processors is unlimited, and when number of available processors is limited and multiply N. В данной работе при вычислении операции многоразрядного умножения чисел длины N стандартным методом «в столбик» в параллельной модели вычислений изучается сложность по числу одноразрядных операций сложения и умножения целых чисел, выполненных одним параллельным процессором, для двух случаев, когда число параллельных процессоров неограниченно, и когда число доступных процессоров ограничено и кратно N. В даній роботі при обчисленні операції багаторозрядного множення чисел довжини N стандартним методом «у стовпчик» в паралельній моделі обчислень аналізується складність за кількістю операцій додавання та множення цілих однорозрядних чисел, виконаних одним паралельним процесором, для двох випадків, коли кількість паралельних процесорів необмежена, та коли кількість процесорів обмежена та кратна N. PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2017-06-13 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/133 PROBLEMS IN PROGRAMMING; No 1 (2015) ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 1 (2015) ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 1 (2015) 1727-4907 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/133/126 Copyright (c) 2017 ПРОБЛЕМИ ПРОГРАМУВАННЯ
institution	Problems in programming
baseUrl_str	https://pp.isofts.kiev.ua/index.php/ojs1/oai
datestamp_date	2018-07-23T13:46:01Z
collection	OJS
language	Ukrainian
topic	UDC 519.6
spellingShingle	UDC 519.6 Tereshchenko, A.N. Complexity analysis of multidigit multiplication operation for implementtation in parallel computational model
topic_facet	UDC 519.6 УДК 519.6 УДК 519.6
format	Article
author	Tereshchenko, A.N.
author_facet	Tereshchenko, A.N.
author_sort	Tereshchenko, A.N.
title	Complexity analysis of multidigit multiplication operation for implementtation in parallel computational model
title_short	Complexity analysis of multidigit multiplication operation for implementtation in parallel computational model
title_full	Complexity analysis of multidigit multiplication operation for implementtation in parallel computational model
title_fullStr	Complexity analysis of multidigit multiplication operation for implementtation in parallel computational model
title_full_unstemmed	Complexity analysis of multidigit multiplication operation for implementtation in parallel computational model
title_sort	complexity analysis of multidigit multiplication operation for implementtation in parallel computational model
title_alt	Анализ сложности операции умножения многоразрядных чисел при реализации в параллельной модели вычислений Аналіз складності операції множення багаторозрядних чисел при реалізації у паралельній моделі обчислень
description	It is analyzed on computing operation of multidigit multiplication of N-digit values based on standard method in parallel computational model the complexity of number of operations of simple additions and multiplications for two cases: when number of available processors is unlimited, and when number of available processors is limited and multiply N.
publisher	PROBLEMS IN PROGRAMMING
publishDate	2017
url	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/133
work_keys_str_mv	AT tereshchenkoan complexityanalysisofmultidigitmultiplicationoperationforimplementtationinparallelcomputationalmodel AT tereshchenkoan analizsložnostioperaciiumnoženiâmnogorazrâdnyhčiselprirealizaciivparallelʹnojmodelivyčislenij AT tereshchenkoan analízskladnostíoperacíímnožennâbagatorozrâdnihčiselprirealízacííuparalelʹníjmodelíobčislenʹ
first_indexed	2025-07-17T09:48:50Z
last_indexed	2025-07-17T09:48:50Z
_version_	1850410189995376640
fulltext	Прикладні засоби програмування та програмне забезпечення © А.М. Терещенко, 2015 ISSN 1727-4907. Проблеми програмування. 2015. № 1 91 УДК: 519.6 А.М. Терещенко АНАЛІЗ СКЛАДНОСТІ ОПЕРАЦІЇ МНОЖЕННЯ БАГАТОРОЗРЯДНИХ ЧИСЕЛ ПРИ РЕАЛІЗАЦІЇ У ПАРАЛЕЛЬНІЙ МОДЕЛІ ОБЧИСЛЕНЬ В даній роботі при обчисленні операції багаторозрядного множення чисел довжини N стандартним методом «у стовпчик» в пара- лельній моделі обчислень аналізується складність за кількістю операцій додавання та множення цілих однорозрядних чисел, ви- конаних одним паралельним процесором, для двох випадків, коли кількість паралельних процесорів необмежена, та коли кіль- кість процесорів обмежена та кратна N. Вступ На даний час мікропроцесорна тех- ніка розвивається дуже швидко. Якщо де- кілька десятиліть назад кластери з вели- кою кількістю процесорів були доступні тільки потужним фінансовим організаціям для проведення надобчислень, то нині кла- стери з кількістю процесорів більше ніж 2000 можливі в домашніх умовах на пер- сональних комп’ютерах на основі графіч- них прискорювачів. Поряд з подальшим розвитком алгоритмів у послідовній мо- делі обчислень [1–6], необхідних для енер- гоекономних нешвидких пристроїв, таких як смарткарти, є потреба в розробці нових методів ефективних у паралельній моделі обчислень. При розробці та вдосконаленні алгоритмів у паралельній моделі обчис- лень, дуже важливо мати методи для оцін- ки складності алгоритмів для порівняння з існуючими та знаходження ефективних діапазонів їх використання. При розробці алгоритмів багатороз- рядного множення в паралельній моделі обчислень необхідно завжди мати на увазі наступні пункти, які мають значний вплив на загальний час виконання:  кількість доступних процесорів;  кількість операцій (ітерацій), ви- конуваних кожним з паралельних проце- сорів;  тип операцій (цілі або комплекс- ні числа, числа з плаваючою комою і т. д.);  врахування знаку переносу;  кількість тісно пов’язаних кро- ків;  обсяг використовуваної пам’яті. Даний перелік не є вичерпним. В даній роботі основна увага приділяється першим двом пунктам. Перед тим, як розглядати більш складні алгоритми, розглянемо спочатку самий простий алгоритм, який знаходить суму цілих чисел у паралельній моделі об- числень. Алгоритм 1. Знаходження суми N цілих чисел     1 0 N i ixr у паралельній моделі обчислень при задіяні P паралельних процесорів (  2NP  ) (без урахування знаків переносу). Вхід: N , ix , 1,0  Ni . Вихід: r . 1.  Nn 2log . 2. 0ir , 12,0  ni . // Ініціалізація. 3. ii xr  , 1,0  Ni . // Завантаження. 4. Для j від 1 до n // Кількість ітерацій. 5. jnI  2 . 6. Для i від 0 до 1I // Одночасне вико- нання на I процесорах. 7. )( Iiiii rrrP  . // Виконується пара- лельно кожним з iP процесорів. 8. Кінець по i . 9. Кінець по j . Після виконання алгоритму 0r буде мати результат додавання цілих чисел. Розглянемо на прикладі 7N . )( kii rrP  позначає, що iP про- цесор при паралельному виконанні додає Прикладні засоби програмування та програмне забезпечення 92 значення з комірки kr до значення, яке зберігається в комірці ir . З табл. 1 видно, що кожний з чоти- рьох процесорів виконає не більше трьох операцій додавання (   )37log2  . Схематично кількість комірок для додавання на кожній ітерації показана на рис. 1, де значення комірок білого кольору додаються до комірок сірого кольору на кожній ітерації 3,2,1j . 6x 5x 4x 3x 3x 2x 2x 1x 1x 1x 0x 0x 0x 0x 1j 2j 3j Рис. 1. Ітераційне додавання значень при сумуванні 7N Алгоритм 1 не є оптимальним, бо операція )( 733 rrP  не є обов’язковою для випадку 7N . Алгоритм 1 є загаль- ним для випадків 85  N і основна мета його опису – це знаходження найбільшої кількості операцій додавань, виконаних одним з процесорів. З Алгоритму 1 видно, що процесор 0P завжди задіяний. Лема 1. При виконанні Алгоритму 1 на кожній ітерації j кількість задіяних паралельних процесорів дорівнює             2 2 j N , та залишається підсумувати       j N 2 комірок після виконання кожної іте- рації j . Доведення. Розглядаючи додавання двох чисел 0x та 1x ( 2N ) досить задіяти один процесор. При додаванні трьох чисел 0x , 1x та 2x ( 3N ) другий процесор буде чекати поки одне із значень 1x або 2x бу- де додане до 0x , щоб додати інше, тобто другий процесор буде зайвий. Так само при отримані суми з п’яти чисел 0x , 1x , 3x , 4x та 5x ( 5N ) не має сенсу задіяти більше двох процесорів. Можна стверджу- вати, що максимальна кількість процесорів буде задіяна на першій ітерації 1j , коли  2N значень додається до значень в  2N комірках. Зрозуміло, що необхідно задіяти  2N процесорів для виконання всіх додавань одночасно. Кількість комі- рок, які залишаються та які необхідно до- опрацювати, дорівнює    22 NNN  , при 2N . (1) При 2j значення з             2 2 N ко- мірок будуть додані до             2 2 N комірок Таблиця 1. Покрокове виконання Алгоритму 1 при 7N   7,012,0,;3log2  n i irNn Крок 0r 1r 2r 3r 4r 5r 6r 7r 2 0 0 0 0 0 0 0 0 3 0x 1x 2x 3x 4x 5x 6x 0 7 )( 400 rrP  )( 511 rrP  )( 622 rrP  )( 733 rrP  7 )( 200 rrP  )( 311 rrP  7 )( 100 rrP  Прикладні засоби програмування та програмне забезпечення 93 при задіянні             2 2 N паралельних про- цесорів для виконання цієї ітерації за один крок, де  2N – кількість комірок, які залишилися після виконання першої іте- рації. Після завершення ітерації 2j маємо кількість значень, які залишилося додати, буде                2 2 2 N N . Згідно фо- рмули (1) можна записати.                            2 2 2 2 2 NN N , при 4N . Попередній вираз можна спростити.    42 2 2 N N N              , при 4N . Аналогічно отримуємо, що після ітерації 3j залишається  8N комірок.    82 4 4 N N N              , при 8N . При виконанні останньої ітерації j кількість комірок, які залишаються для до- давання, виражається.    jj j N N N 22 2 2 1              , при jN 2 . З попереднього виразу видно, що кількість задіяних процесорів (або комі- рок, які додаються) дорівнює             2 2 j N на ітерації j . Лема доведена. Лема 2. При виконанні Алгоритму 1 кожний з паралельних процесорів P ви- конає не більше  N2log операцій дода- вання N цілих чисел при  2NP  . Доведення. Згідно умови леми мо- жемо вважати, що кількість паралельних процесорів достатня на кожному кроці при  2NP  . Згідно Леми 1 кількість комі- рок, які залишаються після виконання іте- рації j , дорівнює       j N 2 . Після виконання Алгоритму 1 сума всіх значень записують- ся в одну комірку 1 2       j N , тобто кількість ітерацій дорівнює  Nj 2log . Лема до- ведена. Наступна лема розглядає загальний випадок, коли кількість задіяних процесо- рів не завжди достатня для виконання всіх додавань одночасно на кожній ітерації. Лема 3. При виконанні Алгоритму 1 кожний з паралельних процесорів P ви- конає не більше               N j jj P NN2log 0 122 операцій додавання цілих чисел при  2NP  . Доведення. При виконані Алгори- тму 1 кількість задіяних процесорів зме- ншується і дорівнює одному задіяному на останній ітерації. На кожній ітерації ...,2,1j кількість задіяних процесорів дорівнює             2 2 j N (або              jj NN 22 1 ), для одночасного виконання всіх додавань, як було показано в Лемі 1. Якщо кількість процесорів P менше              jj NN 22 1 на іте- рації j , то кожен з паралельних процесо- рів виконає не більше            P NN jj 22 1 операцій додавання на ітерації j , при за- гальній кількості ітерацій  N2log . Лема доведена. Примітка 1. Робиться припущення, що наступна ітерація 1j не починається поки всі значення на ітерації j не додані. Інакше можна вважати, що Лема 2 може бути використана для знаходження ниж- ньої обчислювальної оцінки. Прикладні засоби програмування та програмне забезпечення 94 Примітка 2. Основна увага приді- ляється знаходженню величини складнос- ті, де можна стверджувати, що будь-який задіяний паралельний процесор виконає кількість операцій «не більше» визначе- ного значення. Алгоритм 2. Множення двох N - розрядних чисел NNN YXR 2 стандарт- ним методом «у стовпчик» у паралельній моделі обчислень (без врахування знаків переносу). 1. Поелементне множення розрядів чисел jiji yxz , , 1,0,  Nji . 2. Знаходження розрядів результату множення    jik jik zr , , 22,0  Nk . Розглянемо виконання алгоритму на прикладі множення двох 2-розрядних чисел ( 01 2 xxX   , 01 2 yyY   , 2N , 4P ). Обчислення кожного роз- ряду результату можна представити насту- пним чином (рис. 2): jijiji lhyx ,, 2   , де )(, jiji yxLl  , )(, jiji yxHh  ( l – Low , h – High ) 1y 0y 1x 0x 0,0h 0,0l 1,0h 1,0l 0,1h 0,1l 1,1h 1,1l 3r 2r 1r 0r Рис. 2. Множення двох 2-розрядних чисел на основі Алгоритму 2 З рис. 2 видно, що кожний старший розряд результату однорозрядних множень додається до наступного розряду результа- ту множення. Обчислення ir , 3,0i , можна вира- зити наступним чином: 0,00 lr  , 0,00,11,01 )( hllr  , 1,10,11,02 )( lhhr  , 1,13 hr  . Для обчислення 1r та 2r викону- ється послідовно дві операції додавання при задіяні двох процесорів. При задіяні чотирьох паралельних процесорів кожний з них виконає наступну кількість операцій (табл. 2). З табл. 2 видно, що кожний з iP процесорів виконає не більше трьох операцій над цілими однорозрядними числами. Таблиця 2. Кількість операцій над цілими числами при множенні двох 2-розрядних чисел, виконаних кожним процесором 3,0iP iP Мно- ження Додавання Кількість операцій 0P 00 yx  1 1P 10 yx  0,00,11,0 )( hll  3 2P 01 yx  1,10,11,0 )( lhh  3 3P 11 yx  1 Лема 4. Обчислення результату множення двох N -розрядних чисел k N k kNNN rYXR 2 12 0 2     ,    jik jii yxr )( , може бути представлено у наступному ви- гляді: 0,00 lr  ;    jik ji jik jik lhr , 1 , , 22,1  Nk ; 1,112   NNN hr , де )(, jiji yxLl  , )(, jiji yxHh  . Прикладні засоби програмування та програмне забезпечення 95 Доведення. Розглянемо на прикладі множенні двох 4-розрядних чисел. 7P 6P 5P 4P 3P 2P 1P 0P 3,3h 3,3l 0,0h 0,0l 3,2h 3,2l 1,0h 1,0l 2,3h 2,3l 0,1h 0,1l 3,1h 3,1l 2,0h 2,0l 2,2h 2,2l 1,1h 1,1l 1,3h 1,3l 0,2h 0,2l 3,0h 3,0l 2,1h 2,1l 1,2h 1,2l 0,3h 0,3l 7r 6r 5r 4r 3r 2r 1r 0r Рис. 3. Обчислення ir , 7,0i Обчислення ir , 7,0i , може вико- нати при задіяні iP , 7,0i , процесорів, кожний з яких знайде суму всіх елементів у своїй колонці, як показано на рис. 3. На основі рис. 3 обчислення ir , 7,0i , можна представити наступним чи- ном: 0,00 lr  , 0,11,00,01 llhr  , 0,21,12,01,0,1,02 lllhhr  , 0,31,22,13,00,21,12,03 llllhhhr  , 1,32,23,10,31,22,13,04 lllhhhhr  , 2,33,21,32,23,15 llhhhr  , 3,32,33,26 lhhr  , 3,37 hr  . З використанням знаків сум насту- пні вирази можна записати наступним чином: 0,00 lr  ,    ji ji ji ji lhr 1 , 0 ,1 ,    ji ji ji ji lhr 2 , 1 ,2 ,    ji ji ji ji lhr 3 , 2 ,3 ,    ji ji ji ji lhr 4 , 3 ,4 ,    ji ji ji ji lhr 5 , 4 ,5 ,    ji ji ji ji lhr 6 , 5 ,6 , 3,37 hr  . Розглядаючи випадок для N , отримуємо необхідні вирази. Лема дове- дена. Примітка 3. Так як кількість одно- розрядних доданків jil , та jih , дорівнює по 2N , то зрозуміло, що, загалом, необхідно опрацювати 22N однорозрядних значень при додаванні. Примітка 4. Найбільшу кількість доданків 12 N необхідно опрацювати для комірок результату Nr та 1Nr . В паралельній моделі обчислення операцій множення та додавання відріз- няються тим, що всі операції множення можуть бути обчисленні одночасно при задіяні 2N процесорів, а при додаванні це неможливе, так як технічно можна додава- ти тільки одне значення до однієї комірки пам’яті за одну операцію. На основі попередньої леми 3 Алго- ритм 2 може бути покращений за рахунок виконання Алгоритму 1 кожним з парале- льних потоків. Алгоритм 3. Множення двох N - розрядних чисел NNN YXR 2 стандарт- ним методом «у стовпчик» у паралельній моделі обчислень (без врахування знаків переносу). 1. )(, jiji yxHh  , )(, jiji yxLl  , 1,0,  Nji . // Поелементне множення. 2. 0,00 lr  , 1,112   NNN hr . // Два па- ралельних потоки обчислення. 3. Для i від 1 до 1N // 1N паралель- них потоків обчислення. 4. }),0,{ ,1(1_ , ijl iАлгоритмr jij i    . // Додавання l -розрядів. Прикладні засоби програмування та програмне забезпечення 96 5. })1,0,{ ,(1_ 1,    ijh iАлгоритмrr jij ii . // Додавання h -розрядів. 6. Кінець по i . 7. Для i від 1 до 1N // 1N паралель- них потоків обчислення. 8. })1,,{ ,(1_ 1,    Nijl iNАлгоритмr jiNj i . // Додаван- ня l -розрядів. 9. })1,1,{ ,1(1_ 1,    Nijh iNАлгоритмrr jiNj ii . // До- давання h -розрядів. 10. Кінець по i . Аналізуючи рис. 3, бачимо, що для представлення старших та молодших роз- рядів ( jil , та jih , , 3,0, ji ) необхідно використовувати матрицю 810 . Наступ- на лема 5 доводить, що матриця розмі- ром 87 достатня для розміщення всіх елементів, що більш ефективне при до- даванні. Лема 5. При виконані Алгоритму 2 кількість однорозрядних доданків для обчислення кожного розряду результату множення ir , 12,0  Ni , не перевищує 12 N . Доведення. Розглянемо на прикладі 4N . Далі в табл. 3 на основі рис. 3 наве- дена кількість операцій додавання, необ- хідних для обчислення кожного з тимчасо- вих результатів ir , 7,0i , в паралельній моделі. З табл. 3 видно, що кількість дода- нків jil , збільшується до 1 Ni по- чинаючи з 1, а потім зменшується до нуля, та, що кількість доданків jih , збі- льшується до Ni  починаючи з 0, а по- тім зменшується до 1. Загальна кількість доданків може бути виражена наступним чином у загальному випадку для будь- якого N : 10 O , 112 NO . 12  iOi , 1221  iNO iN , 1,1  Ni . Аналізуючи попередні співвідно- шення видно, що 12  NOi . Лема дове- дена. Лема 6. При виконанні Алгоритму 2 загальна кількість однорозрядних дода- вань дорівнює NN 22 2  . Доведення. Розглянемо на прикла- ді 4N . На першій ітерації можливо до- дати 12 доданків (білого кольору) до зна- чень 12 комірок (світло сірого кольору) при задіяні 12 процесорів (рис. 4). 7r 6r 5r 4r 3r 2r 1r 0r Рис. 4. Додавання значень на 1-й ітерації при множенні двох 4-разрядних чисел Таблиця 3. Кількість доданків для обчислення кожного розряду результату ir , 7,0i , при 4N ir 0r 1r 2r 3r 4r 5r 6r 7r Доданків jil , 1 2 3 4 3 2 1 0 Доданків jih , 0 1 2 3 4 3 2 1 Доданків 1 3 5 7 7 5 3 1 Ітерацій 0 2 3 3 3 3 2 0 Прикладні засоби програмування та програмне забезпечення 97 На другій ітерації можливо додати 8 доданків (білого кольору) до значень 8 комірок (сірого кольору) при задіяні 8 процесорів (рис. 5). 7r 6r 5r 4r 3r 2r 1r 0r Рис. 5. Додавання значень на 2-й ітерації при множенні двох 4-разрядних чисел На останній ітерації можливо дода- ти 4 доданків (білого кольору) до значень 4 комірок (світло сірого кольору) при задіяні 4 процесорів (рис. 6). 7r 6r 5r 4r 3r 2r 1r 0r Рис. 6. Додавання значень на 3-й ітерації при множенні двох 4-разрядних чисел Загалом необхідно виконати 24=12+ +8+4 операції додавання з 32 однорозряд- них значень, бо 8 комірок залишається під результат. 32 значення отримано при об- численні 16 однорозрядних множень, що дають 16 дворозрядних чисел при мно- ження двох 4-розрядних чисел. Бачимо, що загальна кількість додавань буде 2442)44(2  , тобто NN 22 2  . Лема доведена. Примітка 5. Попередня лема пока- зує, що всі операції додавання неможливо виконати одночасно за одну операцію тех- нічно, навіть якщо кількість паралельних процесорів необмежена. Рис. 3 можна представити аналогіч- но рис. 4 після заміни значень l , h зна- ченнями t де )( ,, baji ht , позначає, що зна- чення bah , знаходиться в комірці jit , на рис. 7. Наданий далі Алгоритм 4 дозволяє працювати з усіма значеннями без розді- лення на молодші та старші розряди. Ви- користовуючи рис. 7, побудований для ви- падку 4N , можна перевірити корект- ність кроків 3, 4, 5, 6 Алгоритму 4. Алгоритм 4. Множення двох N - розрядних чисел NNN YXR 2 стандарт- ним методом «у стовпчик» у паралельній моделі обчислень (без врахування знаків переносу) при необмеженій кількості про- цесорів. 1. )(, jiji yxHh  , )(, jiji yxLl  , 1,0,  Nji . // Поелементне множення. 2. 0,00 lr  , 1,112   NNN hr . // Два па- ралельних потоки обчислення. 3. Для i від 1 до 1N . // Індексація. 4. jijji lt  ,, , jNjiNjiiN ht   1,1,12 , ij ,0 . 7P 6P 5P 4P 3P 2P 1P 0P )( 0,36,4 ht )( 0,26,3 ht )( 1,25,4 ht )( 1,15,3 ht )( 1,34,5 ht )( 2,14,4 ht )( 2,04,3 ht )( 0,14,2 ht )( 2,23,5 ht )( 3,03,4 ht )( 0,33,3 lt )( 1,03,2 ht )( 2,32,6 ht )( 3,12,5 ht )( 1,32,4 lt )( 1,22,3 lt )( 0,22,2 lt )( 0,02,1 ht )( 3,21,6 ht )( 2,31,5 lt )( 2,21,4 lt )( 2,11,3 lt )( 1,11,2 lt )( 0,11,1 lt )( 3,30,7 ht )( 3,30,6 lt )( 3,20,5 lt )( 3,10,4 lt )( 3,00,3 lt )( 2,00,2 lt )( 1,00,1 lt )( 0,00,0 lt 7r 6r 5r 4r 3r 2r 1r 0r Рис. 7. Заміна значень l , h значеннями t Прикладні засоби програмування та програмне забезпечення 98 5. jijjii ht   1,1, , jNjiNjiN lt   1,,12 , 1,0  ij . 6. Кінець по i . 7.  )12(log2  Nn . 8. Для j від 1 до n // Ітерації. 9. Для i від 1 до 1N 10.         12 12 j i T ,         j i M 2 12 , iNI  12 . 11. kMikiki ttt  ,,, , MTk  ,0 . // Паралельне виконання в MT  потоках. 12. kMIkIkI ttt  ,,, , MTk  ,0 . // Паралельне виконання в MT  потоках. 13. Кінець по i . 14. Кінець по j . Алгоритм 4 розрахований на випа- док, коли кількість процесорів 2NP  до- статня на кожному кроці алгоритму. На- ступний алгоритм враховує кількість дос- тупних процесорів при додаванні. Алгоритм 5. Множення двох N - розрядних чисел NNN YXR 2 стандар- тним методом «у стовпчик» у парале- льній моделі обчислень (без врахування знаків переносу) при задіяні P процесо- рів ( 2NP  ). 1. )(, jiji yxHh  , )(, jiji yxLl  , 1,0,  Nji . // Поелементне множення. 2. 0,00 lr  , 1,112   NNN hr . // Два па- ралельних потоки обчислення. 3. Для i від 1 до 1N // Індексація. 4. jijji lt  ,, , jNjiNjiiN ht   1,1,12 , ij ,0 . 5. jijjii ht   1,1, , jNjiNjiN lt   1,,12 , 1,0  ij . 6. Кінець по i . 7.  )12(log2  Nn . 8. Для j від 1 до n // Ітерацій. 9. mkPMimkPimkPi ttt   ,,, , mkPMImkPImkPI ttt   ,,, ,          1, 1, ,0 PKk kPDKk m , Kk ,0 ,        P D K , M i D j         12 12 ,         j i M 2 12 , iNI  12 , 1,1  Ni . 10. Кінець по j . Враховуючи всі попередні леми, наступна лема надає можливість знайти кількість операцій, не більше якої виконає кожен паралельній процесор, при обчис- ленні результату багаторозрядного мно- ження на основі методу «у стовпчик» у па- ралельній моделі обчислень. Лема 7. При виконанні Алгоритму 5 при задіяні P паралельних процесорів, кожний з процесорів виконає операцій з цілими числами не більше: ),(),(),( *, PNOPNOPNO   . (2)          P N PNO 2 ),( ,  ),( PNO                                          )12(log 0 1 0 12 2 12 2 12 2 N j N i jj P ii . Доведення. Розглянемо спочатку випадок, коли 2NP  . При обмеженій кі- лькості задіяних процесорів число ітерацій для знаходження всіх однорозрядних мно- жень виражається як          P N PNO 2 * ),( . Прикладні засоби програмування та програмне забезпечення 99 Зрозуміло, що кількість ітерацій, необхідних для знаходження всіх сум ir , 12,0  Ni , буде залежати від самої дов- гої послідовності. З рис. 4 бачимо, що присутня симетрія, де ліва половина схе- ми обчислення дзеркально відповідає правій половині, так як для будь-якого N довжина результату множення завжди є парною. Для ітерації 1j обчислимо за- гальну кількість значень (білі комірки на рис. 1), які додаються (до світло сірих ко- мірок). Враховуючи, що кількість додан- ків для обчислення ir , 1,0  Ni , вира- жається 12  iAi (див. рис. 4, Лема 6), загальна кількість може бути виражена                   1 0 1 2 12 122 N i j i iA . В попередньому виразі множник 2 показує, що присутня симетрія, що дає можливість спрощення.      1 0 1 2 N i j iA . Кількість задіяних процесорів дорі- внює кількості значень, які додаються. Тобто кожен з процесорів здійснює одну операцію додавання. Для ітерації 2j кількість значень, які додаються, може бути представлена наступним чином.                          1 0 2 4 12 2 12 2 N i j ii A . Узагальнюючи попередній вираз для ітерації j , отримуємо.                          1 0 1 2 12 2 12 2 N i jjj ii A . Якщо кількість процесорів менша кількості значень, які додаються, то кіль- кість операцій додавань, виконаних кож- ним з процесорів може бути представле- на.                                P ii S N i jjj 1 0 1 2 12 2 12 2 . Тоді загальна кількість додавань, виконана кожним з процесорів, на всіх іте- раціях  )12(log2 N не буде більша на- ступного значення.  ),( PNO                                          )12(log 1 1 0 12 2 12 2 12 2 N j N i jj P ii . Враховуючи кількість операцій множення кожним з процесорів, отримує- мо необхідне співвідношення. Лема до- ведена. Примітка 6. При достатній кілько- сті паралельних процесорів PN 2 , фор- мула (2) приймає вигляд  12log1 2  N , що показує кількість операцій, виконану кожним з паралельних процесорів, при ви- конані Алгоритму 1. На основі формули (2) можна побу- дувати табл. 4, на основі якої отримуємо графік залежності кількості операцій від P , N (рис. 8). Найбільш цікавою буде залежність кількості операцій від кількості доступних процесорів, яка кратна N (див. табл. 5). З рис. 9 та табл. 5 видно, що графі- ки 64P та 4NP  , 128P та 2NP  , 256P та NP  , 512P та NP 2 , 1024P та NP 4 , 2048P та NP 8 сходяться в однакових точках при 256N . Графік 8NP  співпадав би з графіком 32P , якщо би він був присут- ній на рис. 8. Аналізуючи колонки 8N , 4N . 2N . N , N2 , N4 , N8 для кожного N табл. 5 можна зробити висновок, залеж- ність між кількістю операцій, виконаних одним процесором, та кількістю таких процесорів, є дуже близькою до лінійної. Тобто, збільшуючи в iK 2 , i – ціле, разів кількість задіяних процесорів можна стверджувати, що кількість операцій, ви- конаних кожним з процесорів, зменшиться приблизно в K разів при виконанні Алго- ритму 5. Прикладні засоби програмування та програмне забезпечення 100 Таблиця 4. Кількість операцій (додавання та множення) над цілими однорозрядними числами, не більше якої виконає кожен з паралельних процесорів P , при виконанні Алгоритму 5 для 322  N N P 32 64 128 256 512 1024 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 6 6 5 5 5 5 5 7 7 5 5 5 5 5 8 7 5 5 5 5 5 9 11 8 6 6 6 6 10 12 8 6 6 6 6 11 13 8 6 6 6 6 12 17 11 8 6 6 6 13 18 11 8 6 6 6 14 21 12 8 6 6 6 N P 32 64 128 256 512 1024 15 23 13 8 6 6 6 16 24 13 8 6 6 6 17 31 18 12 9 7 7 18 34 19 12 9 7 7 19 36 20 12 9 7 7 20 40 22 13 9 7 7 21 43 23 14 9 7 7 22 47 25 14 9 7 7 23 52 29 17 11 8 7 24 55 30 18 12 9 7 25 60 32 18 12 9 7 26 66 35 20 12 9 7 27 69 36 20 12 9 7 28 75 40 22 13 9 7 29 81 42 23 14 9 7 30 86 45 24 14 9 7 31 91 47 25 14 9 7 32 94 48 25 14 9 7 Рис. 8. Залежність кількості операцій над цілими однорозрядними числами, виконаних одним процесором, від кількості доступних процесорів P для 322  N при виконанні Алгоритму 5 Прикладні засоби програмування та програмне забезпечення 101 Таблиця 5. Кількість операцій (додавання та множення) над цілими однорозрядними числа- ми, не більше якої виконає кожен з паралельних процесорів jP 2 , 11,6j , та jNP 2 , 3,3j , при виконанні Алгоритму 5 для iN 8 , 16,1i N 64 128 256 512 1024 2048 N/8 N/4 N/2 N 2N 4N 8N 16 13 8 6 6 6 6 368 184 92 46 24 13 8 32 48 25 14 9 7 7 752 376 188 94 48 25 14 48 109 57 31 19 13 10 1137 569 285 143 73 38 21 64 190 96 49 26 15 10 1520 760 380 190 96 49 26 80 300 153 79 43 25 16 1906 953 477 240 122 63 34 96 430 217 111 58 32 20 2289 1145 573 287 145 74 39 112 587 296 151 79 43 25 2673 1337 669 335 169 86 45 128 764 382 192 97 50 27 3056 1528 764 382 192 97 50 144 970 488 248 128 68 38 3441 1721 862 433 219 112 59 160 1196 600 303 154 80 44 3826 1913 957 480 242 123 64 176 1450 727 366 186 96 51 4210 2106 1054 528 266 135 70 192 1722 862 433 219 112 59 4593 2297 1149 575 289 146 75 208 2024 1016 511 259 133 70 4978 2490 1246 624 314 159 82 224 2346 1175 590 298 152 80 5361 2681 1341 671 337 170 87 240 2695 1350 678 343 175 91 5745 2873 1437 719 361 182 93 256 3064 1532 766 384 193 98 6128 3064 1532 766 384 193 98 Рис. 9. Залежність кількості операцій над цілими однорозрядними числами, виконаних од- ним процесором, від кількості доступних процесорів P для iN 8 , 16,1i , при виконанні Алгоритму 5 Прикладні засоби програмування та програмне забезпечення 102 Найбільш цікавими для досліджен- ня та вибору кількості процесорів є зна- чення розрядністю 12531  N (з 32 біта- ми в кожному розряді), тобто бітові дов- жини від 1000 до 4000, які відповідають найбільш поширеним на даний час довжи- нам електронних ключів. Сучасні графічні прискорювачі такі, як AMD Radeon HD 7990 Graphics та GeForce GTX TITAN, які мають 4096 та 2688 процесорів відповідно, дозволяють виконувати потужні обчис- лення на персональних комп’ютерах без використання дорогого серверного облад- нання. Використовуючи формулу (2), див. Лему 7, можна знайти складність за кількі- стю операцій над цілими числами, викона- них одним з паралельних процесорів гра- фічних прискорювачів AMD Radeon та GeForce GTX, при виконанні Алгоритму 5 (табл. 6 і 7). Таблиця 6. Кількість операцій (додавання та множення) над цілими однорозрядними числами, не більше якої виконає кожен з паралельних процесорів ,4096,2688P 2048,1536 компаній AMD та NVIDIA при виконанні Алгоритму 5 для iN 8 , 16,1i N 2688 4096 1536 2048 16 6 6 6 6 32 7 7 7 7 48 8 8 10 10 64 10 8 13 10 80 14 11 20 16 96 16 14 22 20 112 20 16 32 25 128 25 16 37 27 144 28 23 46 38 160 35 26 57 44 176 40 28 68 51 192 46 33 75 59 208 57 38 91 70 224 62 44 105 80 240 70 49 118 91 256 80 51 133 98 Таблиця 7. Характеристики графічних прискорювачів за кількістю процесорів Виробник Модель Процесорів NVIDIA GTX TITAN 2688 AMD RADEON 7990 4096 NVIDIA GTX 770 1536 AMD RADEON 7970 2048 Висновок В даній роботі при виконанні бага- торозрядного множення чисел довжини N стандартним методом «у стовпчик» в па- ралельній моделі обчислень проаналізова- но складність за кількістю операцій дода- вання та множення над цілими однорозря- дними числами, виконаних одним парале- льним процесором, для двох випадків, ко- ли кількість паралельних процесорів не- обмежена, та коли кількість процесорів обмежена і кратна N . Для випадку, коли кількість паралельних процесорів необме- жна, запропоновано використання Алгори- тму 4, для іншого випадку ефективніше використовувати Алгоритм 5 в паралель- ній моделі обчислень. Для Алгоритмів 4 та 5 доведені співвідношення для обчислення складності за кількістю операцій, викона- них одним паралельним процесором. По- казано, що кількість операцій виконаних одним процесором обернено пропорційна кількості задіяних паралельних процесорів та має майже лінійну залежність, для ви- падку, коли кількість процесорів обмеже- на. В роботі доведено 7 лем, надані таб- лиці, на основі яких побудовані два графі- ки, які показують залежність кількості опе- рацій від кількості задіяних паралельних процесорів для різних довжин N . Розроб- лена програма paraNP на мові програму- вання APL, яка підтверджує теоретичні ре- зультати отриманні для оцінки складності за кількістю операцій, виконаних одним процесором. Наведені результати можуть бути використані для обчислення складно- сті при отримані порівняльних характерис- тик нових алгоритмів (або модифікованих) багаторозрядного множення та існуючих алгоритмів для знаходження ефективних діапазонів їх використання у паралельній моделі обчислень. Прикладні засоби програмування та програмне забезпечення 103 1. Задірака В., Олексюк О. Комп’ютерна арифметика багаторозрядних чисел. – К.: Наук. думка, 2003. – 263 с. 2. Schonhage A., Strassen V. Schnelle Multiplikation grossen Zahnel // Computing. – 1971. – 7, N 3–4. – P. 281–292. 3. Шенхаге А., Шрассен В. Быстрое умноже- ние больших чисел // Кибернетика. – 1972. – Вып. 2. – С. 87–98. 4. Cooley J.W., Tukey J.W. An algorithm for the machine calculation of complex Fourier Series // Math Compt. – 1965. Apr. – P. 257–301. 5. Березовский А.И., Задирака В.К., Шевчук Л.Б. О тестировании быстродействия ал- горитмов и программ выполнения основ- ных операций для асимметричной крипто- графии // Кибернетика и системный ана- лиз. – 1999. – № 5. – С. 61–68. 6. Терещенко А.Н. Умножение больших N- разрядных чисел с вычислением только N-разрядных ДПФ // Компьютерная мате- матика. – 2008. – № 1. – С. 122–130. Одержано 26.08.2014 Про автора: Терещенко Андрій Миколайович, кандидат фізико-математичних наук, старший інженер-програміст. Місце роботи автора: ТОВ «Сімкорп Україна», м. Київ, вул. В. Стуса 35/37. Е-mail: teramidi@ukr.net mailto:teramidi@ukr.net

Complexity analysis of multidigit multiplication operation for implementtation in parallel computational model

Institution

Similar Items