Bajardi: kis102 19-guruh talabasi Begaliyev S. I

O`ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI


MUHAMMAD AL-XORAZMIY NOMIDAGI
TOSHKENT AXBOROT TEXNOLOGIYALARI
UNIVERSITETI SAMARQAND FILIALI

"Kompyuter injiniring" fakulteti

"Kompyuter tizimlari" kafedrasi
" Kompyuter arxitekturasi” fanidan

Mavzu: Parallelashtirish algoritmlarning samaradorlik ko’rsatkichlari

Bajardi: KIS102_19-guruh talabasi Begaliyev S.I.

Qabul qildi: _____________________________


SAMARQAND – 2022
Parallelashtirish algoritmlarning samaradorlik ko’rsatkichlari
Reja:

1. 
   Parallel hisoblashlarni modellashtirish
   
2. 
   Parallel algoritmik texnikalar
   
3. 
   Ketma-ketliklar, ro'yxatlar va daraxtlar ustidagi asosiy amallar
   
4. 
   Grafiklar
   
5. 
   Saralash
   
6. 
   Hisoblash geometriyasi
   

Parallel hisoblashlarni modellashtirish
Ketma-ket algoritmni yaratuvchisi odatda algoritmni tasodifiy kirish mashinasi (RAM) deb ataladigan mavhum hisoblash modelidan foydalangan holda tuzadi [2, 1-bob]. Ushbu modelda mashina xotira tizimiga ulangan bitta protsessordan iborat. Har bir asosiy CPU operatsiyasi, arifmetik amallar, mantiqiy amallar va xotiraga kirishni o'z ichiga olgan holda, bir vaqt qadamini talab qiladi. Dizaynerning maqsadi oddiy vaqt va xotira talablari bilan algoritm ishlab chiqishdir.
Tasodifiy kirish mashinasi modeli algoritm dizayneriga ko'pgina tafsilotlarni e'tiborsiz qoldirishga imkon beradi Algoritm oxir-oqibat bajariladigan kompyuter, lekin u yetarlicha tafsilotlarni yozib oladi.
Dizayner algoritm qanday ishlashini o'rtacha aniqlik bilan bashorat qilishi mumkin.
Parallel hisoblashlarni modellashtirish ketma-ket hisoblashlarni modellashtirishga qaraganda ancha murakkab chunki amalda parallel kompyuterlar ketma-ket com ga qaraganda tashkiliy jihatdan ko'proq farqlanadi qo'yuvchilar. Natijada, parallel algoritmlar bo'yicha tadqiqotlarning katta qismi modellashtirish masalasi va ko'plab bahs-munozaralar "to'g'ri" model nima yoki qanday ekanligi haqida davom etmoqda amaliy turli modellar mavjud. To'g'ri model bo'yicha konsensus mavjud bo'lmasa-da, bu qayta
qidiruv modellar o'rtasidagi munosabatlarni yaxshiroq tushunish imkonini berdi. Har qanday muhokama parallel algoritmlar turli modellar va ularning o'zaro bog'liqligini tushunishni talab qiladi ular.
Ushbu bobda biz parallel modellarni ikkita sinfga ajratamiz: ko'p protsessorli modellar va ish chuqurlik modellari. Ushbu bo'limning qolgan qismida biz ushbu ikki sinfni va ular qanday ekanligini muhokama qilamiz bog'liq.
Ko'p protsessorli modellar
Ko'p protsessorli model ketma-ket RAM modelining umumlashtirilishi bo'lib, unda ko'proq narsa mavjud bitta protsessordan ko'ra. Ko'p protsessorli modellarni uchta asosiy turga bo'lish mumkin: mahalliy xotira mashina modellari, modulli xotira mashinasi modellari va parallel tasodifiy kirish mashinasi (PRAM) modellari. 1- rasmda ushbu mashina modellarining tuzilishi ko'rsatilgan. Mahalliy xotira mashinasi modeli har biri o'zining mahalliy xotirasiga ega bo'lgan n ta protsessor to'plamidan iborat. Ushbu protsessorlar biriktirilgan umumiy aloqa tarmog'iga. Modulli xotira mashinasi modeli m xotiradan iborat modullar va n protsessorlar umumiy tarmoqqa ulangan. N-protsessorli PRAM modelidan iborat umumiy umumiy xotiraga ulangan n protsessor to'plami [32, 37, 38, 77].
Ko'p protsessorlarning uch turi xotiraga kirish usullari bilan farqlanadi. Mahalliy joyda xotira mashinasi modeli, har bir protsessor o'z mahalliy xotirasiga to'g'ridan-to'g'ri kirishi mumkin, lekin kirishi mumkin boshqa protsessordagi xotirani faqat tarmoq orqali xotira so'rovini yuborish orqali. In RAM modeli, barcha mahalliy operatsiyalar, jumladan, mahalliy xotiraga kirish, birlik vaqtini oladi. Vaqt boshqa protsessorda xotiraga kirish uchun qabul qilingan, ammo ikkala imkoniyatlariga bog'liq bo'ladi aloqa tarmog'i va boshqa protsessorlar tomonidan amalga oshiriladigan xotiraga kirish naqshlari, chunki bu boshqa kirishlar tarmoqni tiqilib qolishi mumkin. Modulli xotira mashinasi modelida protsessor tarmoq orqali xotira so'rovini yuborish orqali xotira modulidagi xotiraga kiradi.
Odatda protsessorlar va xotira modullari har qanday protsessor uchun vaqt ajratadigan tarzda joylashtirilgan har qanday xotira moduliga kirish taxminan bir xil. Mahalliy xotira mashinasi modelida bo'lgani kabi, aniq vaqt miqdori aloqa tarmog'iga va xotiraga kirish tartibiga bog'liq. a.da
PRAM modeli, protsessor xotiraning istalgan so'ziga bir qadamda kirishi mumkin. Bundan tashqari, bular kirishlar parallel ravishda sodir bo'lishi mumkin, ya'ni bir qadamda har bir protsessor umumiy xotiraga kirishi mumkin.
PRAM modellari munozarali, chunki hech qanday haqiqiy mashina vaqt birligi idealiga mos kelmaydi umumiy xotiraga kirish. Shuni ta'kidlash kerakki, mavhumning asosiy maqsadi model haqiqiy mashinani to'g'ridan-to'g'ri modellashtirish emas, balki algoritm dizayneriga samarali algoritmlarni ishlab chiqarishda yordam berishdir. Shunday qilib, agar PRAM modeli (yoki boshqa har qanday model) uchun mo'ljallangan algoritm bo'lishi mum haqiqiy kompyuterda samarali ishlaydigan algoritmga tarjima qilingan, keyin model muvaffaqiyatga erishdi.
1.4-bo'limda biz bitta parallel mashina modeli uchun mo'ljallangan algoritmni qanday tarjima qilish mumkinligini ko'rsatamiz Shunday qilib, u boshqa modelda samarali ishlaydi.
Biz aniqlagan uch turdagi ko'p protsessorli modellar keng va ko'pchilikka imkon beradi o'zgarishlar. Mahalliy xotira mashinasi modellari va modulli xotira mashinasi modellari farq qilishi mumkin

1-rasm: Ko'p protsessorli mashinalar modellarining uch turi. (a) Mahalliy xotira mashinasi modeli.

(b) modulli xotira mashinasi modeli. (c) parallel tasodifiy kirish mashinasi (PRAM) modeli tarmoq topologiyalariga ko'ra. Bundan tashqari, har uch turdagi modellarda ham bo'lishi mumkin protsessorlar va tarmoqlar bajarishga ruxsat berilgan operatsiyalardagi farqlar. In Ushbu bo'limning qolgan qismida biz ba'zi imkoniyatlarni muhokama qilamiz.
Tarmoq topologiyasi
Tarmoq - bu aloqa kanallari orqali ulangan kommutatorlar yig'indisidir. Protsessor yoki xotira modulda ushbu kalitlarga aloqa orqali ulangan bir yoki bir nechta aloqa portlari mavjud ion kanallari. Kommutatorlarning o'zaro bog'lanish sxemasi tarmoq topologiyasi deb ataladi. The Tarmoq topologiyasi ishlashga, shuningdek, xarajat va qiyinchilikka katta ta'sir ko'rsatadi tarmoqni qurish. 2-rasmda bir nechta turli topologiyalar tasvirlangan.
Eng oddiy tarmoq topologiyasi bu shinadir. Ushbu tarmoq ikkala mahalliy xotirada ham ishlatilishi mumkin mashina modellari va modulli xotira mashinasi modellari. Ikkala holatda ham barcha protsessorlar va xotira modullar odatda bitta avtobusga ulanadi. Har bir bosqichda ko'pi bilan bitta ma'lumot bo'lishi mumkin avtobusga yozilgan. Bu ma'lumotlar protsessordan xotirani o'qish yoki yozish uchun so'rov bo'lishi mumkin qiymat yoki qiymatni ushlab turadigan protsessor yoki xotira modulining javobi bo'lishi mumkin. In amaliyot, avtobus foydalanish afzalliklari, u qurish uchun oddiy, va, chunki barcha protsessorlar va xotira modullari avtobusdagi trafikni kuzatishi mumkin, protokollarni ishlab chiqish nisbatan oson protsessorlarga xotira qiymatlarini lokal ravishda keshlash imkonini beradi. Avtobusdan foydalanishning kamchiligi shundaki protsessorlar avtobusga navbat bilan kirishlari kerak. Shunday qilib, avtobusga ko'proq protsessorlar qo'shilsa, xotiraga kirishning o'rtacha vaqti mutanosib ravishda oshadi.
2 o'lchovli to'r to'rtburchaklar shaklida yotqizilishi mumkin bo'lgan tarmoqdir. Har bir kalit to'rda aniq belgi (x, y) mavjud, bu erda 0 у x у X - 1 va 0 у y у Y - 1. X va Y qiymatlari to'rning yon tomonlari uzunligini aniqlaydi. To'rdagi kalitlar soni shunday X • Y. To'rning yon tomonlaridagilardan tashqari har bir kalit to'rtta qo'shniga ulangan: biriga shimolga, biri janubga, biri sharqqa va biri g'arbga. Shunday qilib, (x, y) etiketli kalit, bu erda 0 < x < X - 1 va 0 < y < Y - 1 kalitlarga (x, y + 1), (x, y - 1), (x +) ulangan. 1, y) va (x - 1, y). Ushbu tarmoq odatda mahalliy xotira mashinasi modelida paydo bo'ladi, ya'ni protsessor mahalliy xotirasi bilan birga har bir kalitga ulanadi va masofaviy xotiraga kirishlar tomonidan amalga oshiriladi. tarmoq orqali xabarlarni yo'naltirish. Shakl 2 (b) 8 x 8 mash misolini ko'rsatadi.
To'rlarning bir nechta o'zgarishlari ham mashhur, jumladan 3 o'lchovli to'rlar, toruslar va giperkublar. Torus - yon tomonlardagi kalitlarning kalitlarga ulanishi bo'lgan to'r qarama-qarshi tomonlarda. Shunday qilib, har bir kalit (x, y) to'rtta boshqa kalitlarga ulangan: (x, y+1 mod Y ), (x, yy1 mod Y ), (x+1 mod X, y) va (xy1 mod X, y). Giperkub - bu 2n kalitli tarmoq bo'lib , unda har bir kalitda alohida n-bit yorlig'i mavjud. Ikki kalit aloqa orqali ulanadi
Giperkubdagi kanal, agar kalitlarning teglari aniq bir bit holatida farq qilsa.
16 ta kalitli giperkub 2 (c)-rasmda ko'rsatilgan.
Ko'p bosqichli tarmoq kirish kalitlari deb ataladigan bir qator kalitlarga ulanish uchun ishlatiladi kalitlarning bosqichlari ketma-ketligi orqali chiqish kalitlari deb ataladigan boshqa to'plam. Bunday tarmoqlar dastlab telefon tarmoqlari uchun mo'ljallangan edi [15]. Ko'p bosqichli tarmoqning bosqichlari raqamlangan 1 dan L gacha, bu erda L - tarmoqning chuqurligi. 1-bosqichdagi kalitlar kirish kalitlari, va L bosqichidagilar chiqish kalitlari. Ko'pgina ko'p bosqichli tarmoqlarda yuborish mumkin bosqichlarini kesib o'tuvchi yo'l bo'ylab har qanday kirish kalitidan istalgan chiqish kalitiga xabar tarmoq 1 dan L gacha bo'lgan tartibda. Ko'p bosqichli tarmoqlar modulli xotirada tez-tez ishlatiladi kompyuterlar; odatda protsessorlar kirish kalitlariga, xotira modullari esa chiqishga ulanadi kalitlari. Protsessor xotiraga kirish so'rovi xabarini yuborish orqali xotira so'ziga kiradi tarmoqqa. Keyin ushbu xabar tarmoq bo'ylab tegishli xotira rejimiga o'tadi ule. Agar so'rov xotira so'zini o'qish uchun bo'lsa, xotira moduli ma'lumotlarni qaytarib yuboradi so'rovchi protsessorga tarmoq orqali. Turli xil ko'p bosqichli tarmoqlar mavjud topologiyalar. Masalan, 1.1.1 (a) rasmda 4 ta protsessorni 16 xotira moduliga ulaydigan 2 bosqichli tarmoq ko'rsatilgan. Ushbu tarmoqdagi har bir kalitning pastki qismida ikkita kanal va to'rtta kanal mavjud yuqorida. Ushbu misoldagi protsessorlarning xotira modullariga nisbati haqiqatni aks ettirish uchun tanlangan bu amalda protsessor xotiradan tezroq xotiraga kirish so'rovlarini yaratishga qodir modul ularga xizmat ko'rsatishga qodir.
Yog 'daraxt - bu daraxt kabi tuzilgan tarmoqdir [56]. Biroq, daraxtning har bir chekkasi ko'plab aloqa kanallarini ifodalashi mumkin va har bir tugun ko'plab tarmoq kalitlarini ifodalashi mumkin (shuning uchun "yog'" nomi). Shakl 1.1.1(b) ikkilik daraxtning umumiy tuzilishiga ega bo'lgan yog'li daraxtni ko'rsatadi. Odatda, daraxtning ildizi yaqinidagi qirralarning sig'imlari daraxt yaqinidagi sig'imlardan ancha katta. barglari. Misol uchun, bu daraxtda ildizga tushgan ikkita chekka har biri 8 ta kanalni ifodalaydi barglarga tushgan qirralarning har biri faqat 1 kanalni ifodalaydi. Mahalliy qurishning tabiiy usuli xotira mashinasi modeli protsessorni mahalliy xotirasi bilan birga har bir bargga ulashdir yog'li daraxt. Ushbu sxemada bir protsessordan ikkinchisiga xabar avval daraxt bo'ylab yuqoriga ko'tariladi ikkita protsessorning eng kam umumiy ajdodi, keyin esa daraxtdan pastga.
Ko'pgina algoritmlar muayyan tarmoq topologiyalarida samarali ishlash uchun ishlab chiqilgan to'r yoki giperkub kabi. Bunday algoritmlarni batafsil ko'rib chiqish uchun [55, 67, 73, 80] ga qarang. Garchi bu yondashuv juda nozik sozlangan algoritmlarga olib kelishi mumkin bo'lsa-da, uning ba'zi kamchiliklari bor. Birinchidan, bir tarmoq uchun ishlab chiqilgan algoritmlar boshqa tarmoqlarda yaxshi ishlamasligi mumkin. Demak, qilish uchun yangi mashinada muammoni hal qilish uchun noldan yangi algoritmni loyihalash kerak bo'lishi mumkin. Ikkinchidan, ma'lum bir tarmoqdan foydalanadigan algoritmlar odatdagidan ko'ra murakkabroq

PRAM modellari kabi mavhum modellar uchun mo'ljallangan algoritmlar, chunki ular o'z ichiga olishi kerak tarmoqning ba'zi tafsilotlari. Shunga qaramay, bajariladigan operatsiyalar mavjud

Shu qadar tez-tez parallel mashina tomonidan, u nozik sozlangan tarmoq xos dizayn uchun mantiqiy algoritm. Masalan, xabarlarni yoki xotiraga kirish so'rovlarini yo'naltiruvchi algoritm tarmoq tarmoq topologiyasidan foydalanishi kerak. Boshqa misollar eshittirish uchun algoritmlarni o'z ichiga oladi bir protsessordan ko'plab boshqa protsessorlarga xabar, ko'pchilikda hisoblangan natijalarni to'plash uchun protsessorlar bitta protsessorda va protsessorlarni sinxronlashtirish uchun.
Tarmoq topologiyasini modellashtirishga alternativa uning marshrutlash imkoniyatlarini umumlashtirish hisoblanadi ikkita parametr bo'yicha, uning kechikishi va tarmoqli kengligi. Tarmoqning kechikish vaqti L - bu vaqt tarmoq bo'ylab o'tish uchun xabar oladi. Haqiqiy tarmoqlarda bu topologiyaga bog'liq bo'ladi tarmoq, xabar qaysi portlar o'rtasida o'tayotgani va xabarlarning tiqilib qolishi tarmoqda. Kechikish ko'pincha eng yomon vaqtni hisobga olgan holda modellashtiriladi tarmoq qattiq tirband emas. Tarmoqning har bir portidagi tarmoqli kengligi tezligi hisoblanadi protsessor tarmoqqa ma'lumotlarni kiritishi mumkin. Haqiqiy tarmoqlarda bu bog'liq bo'ladi tarmoq topologiyasi, tarmoqning alohida aloqa kanallarining o'tkazish qobiliyati va, yana tarmoqdagi xabarlarning tiqilib qolishi. Tarmoqli kengligi ko'pincha foydali tarzda modellashtirilishi mumkin protsessorlar xabarlarni tarmoqqa sababsiz kiritishi mumkin bo'lgan maksimal tezlik xabar manzillarining bir xil taqsimlanishini nazarda tutgan holda, qattiq tiqilib qoladi. Ushbu holatda, tarmoqli kengligi xabarlarning ketma-ket kiritilishi orasidagi minimal bo'shliq g sifatida ifodalanishi mumkin tarmoqqa.
Tarmoqni kechikish va o'tkazish qobiliyati bo'yicha tavsiflovchi uchta model Pochta hisoblanadi modeli [14], Bulk-Synchronous Parallel (BSP) modeli [85] va LogP modeli [29]. Pochta modelida tarmoq bitta L parametri, uning kechikishi bilan tavsiflanadi. Ommaviy-sinxron parallel model ikkinchi parametrni qo'shadi g, hisoblash bosqichlarining aloqa bosqichlariga minimal nisbati, ya'ni bo'shliq. LogP modeli ushbu ikkala parametrni o'z ichiga oladi va uchinchi parametrni o'z ichiga oladi, protsessor xabarni jo'natish yoki qabul qilishda sarflagan qo'shimcha xarajatlar yoki behuda vaqt.
Primitiv amallar
Mashina modeli, shuningdek, protsessorlar va tarmoq operatsiyalari turlarini ham ko'rsatishi kerak bajarishga ruxsat berilgan. Biz barcha protsessorlarga bir xil mahalliy ishni bajarishga ruxsat berilgan deb taxmin qilamiz buyruqlar standart ketma-ket RAM modelida yagona protsessor sifatida. Bundan tashqari, protsessorlar mahalliy bo'lmagan xotira so'rovlarini berish, boshqasiga xabar yuborish uchun maxsus ko'rsatmalarga ega bo'lishi mumkin protsessorlar va sinxronizatsiya kabi turli global operatsiyalarni bajarish uchun. Shuningdek bo'lishi mumkin protsessorlar bir vaqtning o'zida mahalliy bo'lmagan operani o'z ichiga olgan ko'rsatmalarni chiqarishi mumkin bo'lgan cheklovlar bo'lishi mumkin lar. Masalan, model ikkita protsessorga bir xil xotira joyiga yozishga ruxsat bermasligi mumkin xuddi shu paytni o'zida. Ushbu cheklashlar algoritmni teng ravishda bajarishni imkonsiz qilishi mumkin Tikulyar model yoki algoritmni bajarish narxini juda qimmatga soling. Shunday ekan parni loyihalash yoki tahlil qilishdan oldin qanday ko'rsatmalar qo'llab-quvvatlanishini tushunish muhimdir allel algoritmi. Ushbu bo'limda biz mahalliy bo'lmagan operatsiyalarni bajaradigan ko'rsatmalarning uchta sinfini ko'rib chiqamiz: (1) bir xil umumiy xotira joyiga bir vaqtning o'zida kirishni amalga oshiradigan ko'rsatmalar, (2) sinxronlash uchun ko'rsatmalar va (3) ma'lumotlar ustida global operatsiyalarni bajaradigan ko'rsatmalar.
Bir vaqtning o'zida bir nechta protsessorlar bir xil resursga o'qish yoki yozish uchun so'rov yuborsa - protsessor, xotira moduli yoki xotira joylashuvi kabi - bir nechta mumkin bo'lgan natijalar mavjud.
Ba'zi mashina modellari oddiygina bunday operatsiyalarni taqiqlaydi va agar undan ko'p bo'lsa, bu xato ekanligini e'lon qiladi protsessor bir vaqtning o'zida resursga kirishga harakat qiladi. Bunday holda, biz model faqat ruxsat berishini aytamiz resursga eksklyuziv kirish. Misol uchun, PRAM modeli faqat eksklyuziv o'qishga ruxsat berishi mumkin yoki har bir xotira joyiga yozish uchun ruxsat. Ushbu turdagi PRAM modeli eksklyuziv o'qish deb ataladi eksklyuziv yozish (EREW) PRAM modeli. Boshqa mashina modellari umumiy manbaga cheksiz kirish imkonini berishi mumkin. Bunday holda, biz model resursga bir vaqtning o'zida kirish imkonini beradi, deb aytamiz. Uchun Misol uchun, bir vaqtning o'zida o'qish va yozish (CRCW) PRAM modeli xotira joylariga bir vaqtda o'qish va yozishga ruxsat beradi va CREW PRAM modeli bir vaqtning o'zida o'qish imkonini beradi, lekin faqat eksklyuziv yozadi. Xotira joyi kabi resursga bir vaqtda yozishni amalga oshirayotganda ziddiyatni hal qilishning ko'plab usullari mavjud. Imkoniyatlar ixtiyoriy qiymatni tanlashni o'z ichiga oladi yozilganlardan (o'zboshimchalik bilan bir vaqtda yozish), eng past indeksli protsessordan qiymatni tanlash (bir vaqtning o'zida ustuvor yozish) va mantiqiy yoki yozilgan qiymatlarni olish. Yakuniy tanlov navbatdagi kirishga ruxsat berishdir. Bunday holda, bir vaqtning o'zida kirishga ruxsat beriladi, ammo qadam uchun vaqt har qanday resursga kirishning maksimal soniga mutanosibdir. Navbat-o'qish navbat-yozish
(QRQW) PRAM modeli bunday kirishlarga ruxsat beradi [36].
Lokal bo'lmagan xotira yoki boshqa protsessorlarga o'qish va yozishdan tashqari, boshqa importlar ham mavjud model taqdim etishi mumkin bo'lgan ibtidoiy narsalar. Bunday ibtidoiylarning bir sinfi sinxronlashni qo'llab-quvvatlaydi. Sinxronizatsiya operatsiyalarining turli xil turlari va bu operaning narxi mavjud modeldan modelga farq qiladi. PRAM modelida, masalan, barcha protsessorlar deb taxmin qilinadi yashirin sinxronizatsiyani ta'minlaydigan qulflash bosqichida ishlaydi. Mahalliy xotirali mashina modelida sinxronizatsiya narxi muayyan tarmoq topologiyasining funktsiyasi bo'lishi mumkin. Tegishli op eration, translyatsiya, bitta protsessorga barcha boshqa protsessorlarga umumiy xabar yuborish imkonini beradi. Ba'zi mashina modellari arifmetik operatsiyalarni birlashtirgan kuchliroq primitivlarni taqdim etadi aloqa. Bunday amallarga prefiks va multiprefiks amallari kiradi, ular aniqlangan
Ish chuqurligi modellari
Chunki parallel kompyuterlarni tashkil qilish va demak, modellashtirishning turli usullari mavjud ular uchun barcha mashinalar uchun mos bo'lgan bitta ko'p protsessorli modelni tanlash qiyin. The Mashinaga e'tibor qaratishga alternativa algoritmga e'tibor qaratishdir. Ushbu bo'limda biz taqdim etamiz ish chuqurligi modellari deb ataladigan modellar sinfi. Ish chuqurligi modelida algoritmning narxi bajaradigan operatsiyalarning umumiy sonini va bu operatsiyalar orasidagi bog'liqlikni o'rganish orqali aniqlanadi. Algoritmning ishi W - u bajaradigan amallarning umumiy soni;
uning chuqurligi D - uning operatsiyalari orasida eng uzun bog'liqlik zanjiri. Biz nisbatni P = W / D deb ataymiz algoritmning parallelligi.
Ish chuqurligi modellari ko'p protsessorli modellarga qaraganda mavhumroqdir. Ko'rib turganimizdek
ammo, ish chuqurligi modellarida samarali bo'lgan algoritmlarni ko'pincha algoritmlarga tarjima qilish mumkin. ko'p protsessorli modellarda samarali bo'lgan va u erdan haqiqiy parallel kompyuterlarga. The
Ish chuqurligi modelidan foydalanishning afzalligi shundaki, murakkablashtiradigan mashinaga bog'liq tafsilotlar mavjud emas algoritmlarni loyihalash va tahlil qilish. Bu erda biz ish chuqurligi modellarining uchta sinfini ko'rib chiqamiz: sxema modellar, vektorli mashina modellari va tilga asoslangan modellar. Biz tilga asoslangan holda foydalanamiz
Ushbu bobdagi model, shuning uchun biz 1.5-bo'limda ushbu modellarga qaytamiz. Eng mavhum ish chuqurlik modeli - sxema modeli. Sxema tugunlar va yo'naltirilgan yoylardan iborat. Tugun ifodalaydi ikkita qiymat qo'shish kabi asosiy operatsiya. Operatsiya uchun har bir kirish qiymati ga keladi kiruvchi yoy orqali mos keladigan tugun. Operatsiya natijasi tugundan keyin amalga oshiriladi bir yoki bir nechta chiquvchi yoylar orqali. Ushbu chiquvchi yoylar boshqa tugunlarga kirishlarni ta'minlashi mumkin. Raqam Tugunga kiruvchi yoylar soni tugunning fan kirishi va chiquvchi yoylar soni deb ataladi.
fan-out deb ataladi. Yoylarning ikkita maxsus sinfi mavjud. Kirish yoylari to'plami kirishni ta'minlaydi butun davr uchun qiymatlar. Bu yoylar tugunlardan kelib chiqmaydi. Chiqish yoylari ni qaytaradi sxema tomonidan ishlab chiqarilgan yakuniy chiqish qiymatlari. Bu yoylar tugunlarda tugamaydi. Ta'rifiga ko'ra, sxemaga yo'naltirilgan siklni o'z ichiga olishiga ruxsat berilmaydi. Ushbu modelda algoritm a sifatida modellashtirilgan yo'naltirilgan asiklik sxemalar oilasi. Kirishning har bir mumkin bo'lgan o'lchami uchun sxema mavjud.
4-rasmda 16 ta raqamni qo'shish sxemasi ko'rsatilgan. Bu rasmda barcha yoylar tomon yo'naltirilgan pastki. Kirish yoylari rasmning yuqori qismida joylashgan. Har bir + tugun keladigan ikkita qiymatni qo'shadi uning ikkita kiruvchi yoyiga va natijani uning chiquvchi yoyiga joylashtiradi. Barcha kiritilgan ma'lumotlarning yig'indisi sxemasi pastki qismidagi yagona chiqish yoyi bo'yicha qaytariladi.
Devrenning ishi va chuqurligi quyidagicha o'lchanadi. Ish tugunlarning umumiy soni.
Masalan, 4-rasmdagi ish 15. (Ish sxemaning o'lchami deb ham ataladi.)
chuqurlik - kirish yoyi va chiqish yoyidan eng uzun yo'naltirilgan yo'lda tugunlar soni. In

4- rasm: Daraxtdagi 16 ta raqamni jamlash. Umumiy chuqurlik (eng uzun bog'liqlik zanjiri) 4 ta va umumiy ish (operatsiyalar soni) 15 ta.
4- rasm, chuqurlik 4. Sxemalar oilasi uchun ish va chuqurlik odatda parametrlangan. kirishlar soni bo'yicha. Masalan, 4-rasmdagi sxemani osongina umumlashtirish mumkin ikkining kuchi bo'lgan har qanday n uchun n ta kirish qiymatini qo'shing. Ushbu sxemalar oilasi uchun ish va chuqurlik Bu W(n) = n - 1 va D(n) = log2 n.
Sxema modellari ko'p yillar davomida parallelizmning turli nazariy jihatlarini o'rganish uchun ishlatilgan. masalan, ayrim masalalarni parallel ravishda hal qilish qiyinligini isbotlash. Umumiy koyrinish uchun [48] ga qarang.
Vektorli modelda algoritm qadamlar ketma-ketligi sifatida ifodalanadi, ularning har biri o'z vazifasini bajaradi kirish qiymatlari vektorida (ya'ni, ketma-ketlikda) operatsiya va vektor natijasini beradi [19, 69]. Har bir qadamning ishi uning kirish (yoki chiqish) vektorining uzunligiga teng. Algoritmning ishi uning bosqichlari ishining yig'indisidir. Algoritmning chuqurligi - vektor qadamlar soni.
Til modelida ish chuqurligi narxi har bir dasturlash tili konstruktsiyasi bilan bog'lanadi [20, 22]. Masalan, ikkita funktsiyani parallel chaqirish bo'yicha ish yig'indisiga teng ikkita qo'ng'iroqning ishi. Chuqurlik, bu holda, ikkalasining chuqurligining maksimaliga teng
qo'ng'iroqlar.
1.3 Algoritmlarga xarajatlarni belgilash
Ish chuqurligi modellarida algoritmning narxi uning ishi va chuqurligi bilan belgilanadi.
Ko'p protsessorli modellar uchun ish va chuqurlik tushunchalari ham aniqlanishi mumkin. Ish W algoritm tomonidan bajarilgan protsessorlar soni uchun zarur bo'lgan vaqtga ko'paytiriladi bajarishni yakunlash uchun algoritm. Chuqurlik D bajarish uchun zarur bo'lgan umumiy vaqtga teng algoritm.
Algoritmning chuqurligi muhim ahamiyatga ega, chunki vaqt talab qiladigan ba'zi ilovalar mavjud hisoblashni amalga oshirish juda muhimdir. Masalan, ob-havoni bashorat qilish dasturining natijalari Agar dastur ob-havodan oldin bajarilishini tugatsagina foydali bo'ladi!
Umuman olganda, algoritm narxining eng muhim o'lchovi ishdir. Bu quyidagicha bahslashish mumkin. Kompyuterning narxi protsessorlar soniga taxminan proportsionaldir kompyuterda. Kompyuterda vaqtni sotib olish narxi kompyuterning narxiga mutanosib kompyuter ishlatilgan vaqtga ko'paytiriladi. Hisoblashning umumiy qiymati, shuning uchun kompyuterdagi protsessorlar sonining ko'paytmasiga taxminan proportsionaldir vaqt miqdori, ya'ni ish.
Ko'pgina hollarda, parallel kompyuterda hisoblash uchun talab qilinadigan ish (xarajat) ketma-ket kompyuterda bir xil hisoblash uchun talab qilinadigan ishlardan biroz kattaroq bo'lishi mumkin. Agar tugatish vaqti etarlicha yaxshilangan, ammo bu qo'shimcha ishni ko'pincha oqlash mumkin. Biz kabi ko'rish kerak, ammo ko'pincha tugallanish vaqti va bajarilgan umumiy ish o'rtasida uzilish mavjud. Parallel algoritmlar ish nuqtai nazaridan qanchalik samarali ekanligini aniqlash uchun biz parallel algoritm deb aytamiz. Agar asimptotik tarzda (muammo hajmi oshgani sayin) ma'lum bo'lgan eng yaxshi ketma-ket algoritmga qaraganda ko'proq doimiy omilni talab qilsa, samarali ishlaydi.
Modellar orasidagi emulyatsiyalar
Garchi ko'p parallellarning har biri uchun boshqa algoritm ishlab chiqilishi kerak bo'lsa-da modellar uchun mo'ljallangan algoritmlarni tarjima qilish uchun ko'pincha avtomatik va samarali usullar mavjud bir modelni boshqasi uchun mo'ljallangan algoritmlarga aylantiradi. Bu tarjimalar ma'noda asarni saqlaydi har ikkala algoritm tomonidan bajariladigan ish doimiy omil doirasida bir xil ekanligini. Masalan, Brent teoremasi [24] deb nomlanuvchi quyidagi teorema shuni ko'rsatadiki, algoritm sxema modeli ishni saqlovchi uslubda PRAM modeli algoritmiga tarjima qilinishi mumkin.
Teorema 1.1 (Brent teoremasi) O'lchamdagi (ya'ni, ish) V, chuqurlik D va sxema modelidagi doimiy fan-kirish tugunlari bo'lgan sxema sifatida ifodalanishi mumkin bo'lgan har qanday algoritm O(W/P + D) bosqichlarida bajarilishi mumkin. CREW PRAM modelida.
Isbot: Asosiy g'oya PRAM ning kontaktlarning zanglashiga olib kelgan hisoblashni taqlid qilishidir bosqichma-bosqich moda. Tugun darajasi quyidagicha aniqlanadi. Agar tugun hammasi bo'lsa, 1-darajada kirishlar ham sxemaga kirishlardir. Induktiv ravishda, har qanday boshqa tugunning darajasi bir kattaroqdir uning kirishlarini ta'minlovchi tugunlar darajasining maksimali. Tugunlar sonini li belgilayliki darajasida. Keyin PRAMdagi P protsessorlarining har biriga yli/Py amallarni belgilash orqali i darajali amallarni O(yli/Py) bosqichlarida bajarish mumkin. Bir vaqtning o'zida o'qish talab qilinishi mumkin. Chunki bir darajadagi ko'plab operatsiyalar oldingi darajadagi bir xil natijani o'qishi mumkin. Xulosa qilish barcha D darajalari ustida vaqt, biz bor

Oxirgi qadam W = PD ekanligini kuzatish orqali olinadi i=1 li , ya'ni ishning jamiga teng ekanligi sxemaning barcha darajalaridagi tugunlar soni. □