Редукція паралельне програмування Ред укція це ситуація коли змінна всередині циклу використовується для складання значе
Редукція (паралельне програмування)
Ред́укція - це ситуація, коли змінна всередині циклу використовується для складання значень, отриманих в кожній ітерації. Наприклад, це відбувається в циклі, який підсумовує результати обчислень, щоб отримати одне підсумкове значення. Така ситуація часто виникає в паралельному програмуванні.
Редукція в паралельному програмуванніРедагувати
Редукція в OpenMPРедагувати
У OpenMP є оператор reduction:
reduction(+:sum)
Як і оператор private, він додається в конструкцію OpenMP, щоб повідомити компілятору, що слід очікувати редукції. Після цього створюється тимчасова закрита змінна, яка використовується для отримання проміжного результату операції підсумовування для кожного потоку. В кінці виконання конструкції значення цієї змінної для кожного потоку підсумовуються, щоб отримати кінцевий результат. Операція, яка використовується при редукції, також вказується в операторі. В даному випадку це операція "+". OpenMP визначає значення для закритої змінної, яка використовується в редукції, на основі відповідної математичної операції. Наприклад, для "+" це значення дорівнює нулю.
Редукція в CUDAРедагувати
Нехай заданий масив a0,a1,...,an-1 і деяка бінарна асоціативна операція. Без обмеження спільності як операції далі буде розглядатися додавання. Тоді редукцією масиву a0,a1,...,an-1 щодо додавання називається:
Розділимо весь вихідний масив на частини, і кожній з них поставимо у відповідність один блок сітки блоків. Оскільки в CUDA максимальна розмірність блоку невелика (зазвичай 65535), великі одномірні масиви можуть бути необхідні для представлення як дво- або тривимірних, щоб збільшити діапазон індексації. Якщо в кожному блоці підсумувати тільки відповідну частину елементів масиву, то вихідна задача перетворюється в набір незалежних підзадач по знаходженню часткових сум. Для розпаралелювання кожної підзадачі по окремих нитках всередині блоку аналогічним чином продовжимо ділити підмасив спочатку на пари елементів, потім на пари їх часткових сум і так далі аж до однієї пари, що підсумовує дві половини підмасиву. Таким чином на кожному кроці підсумовуване число елементів зменшуватиметься удвічі, наприклад, у випадку 512 елементів у блоці буде потрібно log 512 = 9 кроків. Описаний процес для масиву з 16 елементів показаний на першому рисунку. Підвищити ефективність доступу до пам`яті може попереднє копіювання відповідних елементів блоку в розділену пам`ять. У цьому випадку дані з повільної глобальної пам`яті будуть завантажені єдиний раз, і при знаходженні часткових сум буде використовуватися лише швидка розділена пам`ять. На другому рисунку показано відповідність потоків, елементів масиву і кроків підсумування для даного методу.
Недоліком попереднього варіанту є велика кількість ітерацій циклу по s, в яких нитки одного варпу переходять в різні гілки умовного оператора. У цьому випадку всі нитки варпу виконують всі гілки. Викликані цим ефектом надлишкові обчислення можна виключити, перерозподіливши дані та операції, як це показано на третьому рисунку.
У другому варіанті ядра на кожному кроці циклу по s буде не більше одного варпу з розгалуженням, причому це розгалуження буде мати місце тільки для декількох останніх ітерацій циклу, а в інших випадках - на кордоні між варпами. Другий варіант також має недолік: при s = 2 всі звернення до пам`яті, що відповідають банкам з парними номерами, призводять до конфлікту банків 2-го порядку. Аналогічно, при s = 4 всі звернення відповідних банків з номерами 0, 4, 8, 12 призводять до конфлікту 4-го порядку і т.д. Таким чином, дана реалізація буде постійно приводити до конфліктів по банках високого порядку. Позбутися від конфліктів можна просто змінивши порядок вибору пар: замість вибору пари сусідніх елементів з подвоєнням відстані на кожній наступній операції, слід почати з пар елементів, що знаходяться на відстані BLOCKJSIZE /2, і на кожному кроці зменшувати відстань вдвічі, що показано на четвертому рисунку
Глобальні і локальні операнди. Редукцію і сканування можна застосовувати до глобальних величин для отримання локально доступних результатів, наприклад: що призводить до отримання скалярного значення, що зберігається в локальній змінній least кожного потоку. Але редукція і сканування можуть також об'єднувати значення у множинних потоках. Операнди, тобто значення, що підлягають об'єднанню, можуть являти собою локальні змінні, а результат може бути присвоєно або локальній, або глобальній змінній. Таким чином, в операторі локальні змінні count, по одній в кожному потоці, об'єднуються, а один результат зберігається в локальній змінній total. Тобто кожен потік отримує копію результату.
Операції редукції і сканування. Використання в мові Peril-L похилої лінії і зворотньої похилої лінії, що розділяє оператор і операнд, для більшості програмістів незвично. У багатьох мовах використовується позначення у вигляді plus-reduce або min-scan, але таке позначення неможливо відрізнити від робочих викликів програмних функцій, воно затуманює важливість цих потужних абстракцій і знецінює їх роль. Ми спеціально вживаємо похилу риску, що бере початок в мові APL, щоб підкреслити важливість редукції і сканування.
Синхронізація редукції і сканування. Зверніть увагу, що оскільки операції редукції і сканування можуть працювати з множинними потоками, передбачається їх синхронізація, коли вони звертаються і привласнюють значення тільки до локальних змінних.
Для виконання підсумовування всі потоки повинні прибути до цього оператора, і жоден потік не може продовжувати роботу, поки привласнення не завершено. Тому привласнення або скороченої, або сканованою локальної величини локальної змінної має ефект бар'єрної синхронізації. Якщо результат зберігається в глобальній змінній, то як тільки потік внесе свою величину і виконає свою функцію в дереві операцій, він продовжить своє виконання.
Джерела та літератураРедагувати
Sanders J. CUDA by Example: An Introduction to General-Purpose GPU Programing /Jason Sanders, Edward Kandrot. - Addison-Wesley Professional, 2012. - 312p.
Погорілий С.Д. Методика вимірювання обчислюваної потужності відеоадаптера (платформа CUDA) /С.Д Погорілий, М.І. Трібрат, Ю.В. Бойко, Д.Б. Грязнов //Наукові праці Донецького національного технічного університету. Серія. - Донецьк: ДВНЗ "ДонНТУ", 2012. -№11(164). -С.94-98.
Струбицька І.П. Методичні рекомендації по виконанню лабораторних робіт з курсу "Програмування паралельних та розподілених обчислень" для студентів напрямку підготовки 6.050103 "Програмна інженерія" / І.П. Струбицька. – Тернопіль, 2014. – с.58.
Ця стаття потребує додаткових посилань на джерела для поліпшення її перевірності. Будь ласка, допоможіть удосконалити цю статтю, додавши посилання на надійні (авторитетні) джерела. Зверніться на сторінку обговорення за поясненнями та допоможіть виправити недоліки. Матеріал без джерел може бути піддано сумніву та вилучено.(березень 2017)
На цю статтю не посилаються інші статті Вікіпедії.
Будь ласка, скористайтеся підказкою та розставте посилання відповідно до прийнятих рекомендацій.
Ця стаття не має інтервікі-посилань. Ви можете допомогти проєкту, знайшовши та додавши їх до відповідного елементу Вікіданих.
Це незавершена стаття про програмування. Ви можете допомогти проєкту, виправивши або дописавши її.
Red ukciya ce situaciya koli zminna vseredini ciklu vikoristovuyetsya dlya skladannya znachen otrimanih v kozhnij iteraciyi Napriklad ce vidbuvayetsya v cikli yakij pidsumovuye rezultati obchislen shob otrimati odne pidsumkove znachennya Taka situaciya chasto vinikaye v paralelnomu programuvanni Zmist 1 Redukciya v paralelnomu programuvanni 1 1 Redukciya v OpenMP 1 2 Redukciya v CUDA 1 2 1 Varianti rozparalelennya redukciyi 1 3 Redukciya i skanuvannya 2 Dzherela ta literaturaRedukciya v paralelnomu programuvanni RedaguvatiRedukciya v OpenMP Redaguvati U OpenMP ye operator reduction reduction sum Yak i operator private vin dodayetsya v konstrukciyu OpenMP shob povidomiti kompilyatoru sho slid ochikuvati redukciyi Pislya cogo stvoryuyetsya timchasova zakrita zminna yaka vikoristovuyetsya dlya otrimannya promizhnogo rezultatu operaciyi pidsumovuvannya dlya kozhnogo potoku V kinci vikonannya konstrukciyi znachennya ciyeyi zminnoyi dlya kozhnogo potoku pidsumovuyutsya shob otrimati kincevij rezultat Operaciya yaka vikoristovuyetsya pri redukciyi takozh vkazuyetsya v operatori V danomu vipadku ce operaciya OpenMP viznachaye znachennya dlya zakritoyi zminnoyi yaka vikoristovuyetsya v redukciyi na osnovi vidpovidnoyi matematichnoyi operaciyi Napriklad dlya ce znachennya dorivnyuye nulyu Redukciya v CUDA Redaguvati Nehaj zadanij masiv a0 a1 an 1 i deyaka binarna asociativna operaciya Bez obmezhennya spilnosti yak operaciyi dali bude rozglyadatisya dodavannya Todi redukciyeyu masivu a0 a1 an 1 shodo dodavannya nazivayetsya A a sub 0 sub a sub 1 sub a sub 2 sub a sub n 1 sub Redukciya trivialno realizovuyetsya nastupnim poslidovnim kodom int sum 0 for int i 0 i lt n i sum a i Varianti rozparalelennya redukciyi Redaguvati nbsp Rozdilimo ves vihidnij masiv na chastini i kozhnij z nih postavimo u vidpovidnist odin blok sitki blokiv Oskilki v CUDA maksimalna rozmirnist bloku nevelika zazvichaj 65535 veliki odnomirni masivi mozhut buti neobhidni dlya predstavlennya yak dvo abo trivimirnih shob zbilshiti diapazon indeksaciyi Yaksho v kozhnomu bloci pidsumuvati tilki vidpovidnu chastinu elementiv masivu to vihidna zadacha peretvoryuyetsya v nabir nezalezhnih pidzadach po znahodzhennyu chastkovih sum Dlya rozparalelyuvannya kozhnoyi pidzadachi po okremih nitkah vseredini bloku analogichnim chinom prodovzhimo diliti pidmasiv spochatku na pari elementiv potim na pari yih chastkovih sum i tak dali azh do odniyeyi pari sho pidsumovuye dvi polovini pidmasivu Takim chinom na kozhnomu kroci pidsumovuvane chislo elementiv zmenshuvatimetsya udvichi napriklad u vipadku 512 elementiv u bloci bude potribno log 512 9 krokiv Opisanij proces dlya masivu z 16 elementiv pokazanij na pershomu risunku nbsp Pidvishiti efektivnist dostupu do pam yati mozhe poperednye kopiyuvannya vidpovidnih elementiv bloku v rozdilenu pam yat U comu vipadku dani z povilnoyi globalnoyi pam yati budut zavantazheni yedinij raz i pri znahodzhenni chastkovih sum bude vikoristovuvatisya lishe shvidka rozdilena pam yat Na drugomu risunku pokazano vidpovidnist potokiv elementiv masivu i krokiv pidsumuvannya dlya danogo metodu Priklad realizaciyi CUDA yadra na movi S global void reduce1 int inData int outData shared intdata BLOCK SIZE int tid threadIdx x int i blockIdx x blockDim x threadIdx x data tid inData i syncthreads for int s 1 s lt blockDim x s 2 if tid 2 s 0 data tid data tid s syncthreads if tid 0 outData blockIdx x data 0 nbsp Nedolikom poperednogo variantu ye velika kilkist iteracij ciklu po s v yakih nitki odnogo varpu perehodyat v rizni gilki umovnogo operatora U comu vipadku vsi nitki varpu vikonuyut vsi gilki Viklikani cim efektom nadlishkovi obchislennya mozhna viklyuchiti pererozpodilivshi dani ta operaciyi yak ce pokazano na tretomu risunku Kod pidpovidnogo CUDA yadra global void reduce2 int inData int outData shared intdata BLOCK SIZE Int tid threadIdx x inti blockIdx x blockDim x threadIdx x data tid inData i syncthreads for int s 1 s lt blockDim x s lt lt 1 int index 2 s tid if index lt blockDim x data index data index s syncthreads if tid 0 outData blockIdx x data 0 nbsp U drugomu varianti yadra na kozhnomu kroci ciklu po s bude ne bilshe odnogo varpu z rozgaluzhennyam prichomu ce rozgaluzhennya bude mati misce tilki dlya dekilkoh ostannih iteracij ciklu a v inshih vipadkah na kordoni mizh varpami Drugij variant takozh maye nedolik pri s 2 vsi zvernennya do pam yati sho vidpovidayut bankam z parnimi nomerami prizvodyat do konfliktu bankiv 2 go poryadku Analogichno pri s 4 vsi zvernennya vidpovidnih bankiv z nomerami 0 4 8 12 prizvodyat do konfliktu 4 go poryadku i t d Takim chinom dana realizaciya bude postijno privoditi do konfliktiv po bankah visokogo poryadku Pozbutisya vid konfliktiv mozhna prosto zminivshi poryadok viboru par zamist viboru pari susidnih elementiv z podvoyennyam vidstani na kozhnij nastupnij operaciyi slid pochati z par elementiv sho znahodyatsya na vidstani BLOCKJSIZE 2 i na kozhnomu kroci zmenshuvati vidstan vdvichi sho pokazano na chetvertomu risunkuNizhche privedenij kod vidpovidnogo CUDA yadra global void reduce3 int inData int outData shared intdata BLOCK SIZE inttid threadIdx x inti blockIdx x blockDim x threadIdx x data tid inData i syncthreads for int s blockDim x 2 s gt 0 s gt gt 1 if tid lt s data tid data tid s syncthreads if tid 0 outData blockIdx x data 0 Redukciya i skanuvannya Redaguvati Globalni i lokalni operandi Redukciyu i skanuvannya mozhna zastosovuvati do globalnih velichin dlya otrimannya lokalno dostupnih rezultativ napriklad sho prizvodit do otrimannya skalyarnogo znachennya sho zberigayetsya v lokalnij zminnij least kozhnogo potoku Ale redukciya i skanuvannya mozhut takozh ob yednuvati znachennya u mnozhinnih potokah Operandi tobto znachennya sho pidlyagayut ob yednannyu mozhut yavlyati soboyu lokalni zminni a rezultat mozhe buti prisvoyeno abo lokalnij abo globalnij zminnij Takim chinom v operatori lokalni zminni count po odnij v kozhnomu potoci ob yednuyutsya a odin rezultat zberigayetsya v lokalnij zminnij total Tobto kozhen potik otrimuye kopiyu rezultatu Operaciyi redukciyi i skanuvannya Vikoristannya v movi Peril L pohiloyi liniyi i zvorotnoyi pohiloyi liniyi sho rozdilyaye operator i operand dlya bilshosti programistiv nezvichno U bagatoh movah vikoristovuyetsya poznachennya u viglyadi plus reduce abo min scan ale take poznachennya nemozhlivo vidrizniti vid robochih viklikiv programnih funkcij vono zatumanyuye vazhlivist cih potuzhnih abstrakcij i znecinyuye yih rol Mi specialno vzhivayemo pohilu risku sho bere pochatok v movi APL shob pidkresliti vazhlivist redukciyi i skanuvannya Sinhronizaciya redukciyi i skanuvannya Zvernit uvagu sho oskilki operaciyi redukciyi i skanuvannya mozhut pracyuvati z mnozhinnimi potokami peredbachayetsya yih sinhronizaciya koli voni zvertayutsya i privlasnyuyut znachennya tilki do lokalnih zminnih Dlya vikonannya pidsumovuvannya vsi potoki povinni pributi do cogo operatora i zhoden potik ne mozhe prodovzhuvati robotu poki privlasnennya ne zaversheno Tomu privlasnennya abo skorochenoyi abo skanovanoyu lokalnoyi velichini lokalnoyi zminnoyi maye efekt bar yernoyi sinhronizaciyi Yaksho rezultat zberigayetsya v globalnij zminnij to yak tilki potik vnese svoyu velichinu i vikonaye svoyu funkciyu v derevi operacij vin prodovzhit svoye vikonannya Dzherela ta literatura RedaguvatiSanders J CUDA by Example An Introduction to General Purpose GPU Programing Jason Sanders Edward Kandrot Addison Wesley Professional 2012 312p Tesla resheniya dlya rabochih stancij Elektronnyj resurs rRezhim dostupa http www nvidia ru object tesla supercomputer workstations ru html NVIDIA CUDA dostupnyj bilet v mir bolshih vychislenij Elektronnyj resurs Rezhim dostupa http old computerra ru interactive 423392 NVIDIA CUDA graficheskie vychisleniya na graficheskih procesorah Elektronnyj resurs Rezhim dostupa http www ixbt com video3 cuda 1 shtml Pogorilij S D Metodika vimiryuvannya obchislyuvanoyi potuzhnosti videoadaptera platforma CUDA S D Pogorilij M I Tribrat Yu V Bojko D B Gryaznov Naukovi praci Doneckogo nacionalnogo tehnichnogo universitetu Seriya Doneck DVNZ DonNTU 2012 11 164 S 94 98 Strubicka I P Metodichni rekomendaciyi po vikonannyu laboratornih robit z kursu Programuvannya paralelnih ta rozpodilenih obchislen dlya studentiv napryamku pidgotovki 6 050103 Programna inzheneriya I P Strubicka Ternopil 2014 s 58 Cya stattya potrebuye dodatkovih posilan na dzherela dlya polipshennya yiyi perevirnosti Bud laska dopomozhit udoskonaliti cyu stattyu dodavshi posilannya na nadijni avtoritetni dzherela Zvernitsya na storinku obgovorennya za poyasnennyami ta dopomozhit vipraviti nedoliki Material bez dzherel mozhe buti piddano sumnivu ta vilucheno berezen 2017 Na cyu stattyu ne posilayutsya inshi statti Vikipediyi Bud laska skoristajtesya pidkazkoyu ta rozstavte posilannya vidpovidno do prijnyatih rekomendacij Cya stattya ne maye interviki posilan Vi mozhete dopomogti proyektu znajshovshi 1 ta dodavshi yih do vidpovidnogo elementu Vikidanih nbsp Ce nezavershena stattya pro programuvannya Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi Redukciya paralelne programuvannya u Google Otrimano z https uk wikipedia org w index php title Redukciya paralelne programuvannya amp oldid 34439046
