Bajardi: kis102 19-guruh talabasi Begaliyev S. I

Parallel algoritmik texnikalar
Ketma-ket algoritmlarni loyihalashda bo'lgani kabi, parallel algoritmlarni loyihalashda ham ko'plab umumiy texnikalar mavjud Bu turli xil muammoli sohalarda qo'llanilishi mumkin. Ulardan ba'zilari standart ketma-ketlikning variantlari texnikalar, boshqalari esa parallel algoritmlar uchun yangi. Ushbu bo'limda biz ulardan ba'zilari bilan tanishamiz Parallel bo'lish va zabt etish, tasodifiylashtirish va parallel ko'rsatkich manipulyatsiyasi kabi usullar tion. Keyingi bo'limlarda biz ushbu usullardan foydalanamiz.
Ketma-ketliklar, ro'yxatlar va daraxtlar ustidagi asosiy amallar
Biz parallel algoritmlar taqdimotini bajarish uchun algoritmlar to'plamidan boshlaymiz ketma-ketliklar, ro'yxatlar va daraxtlar ustidagi asosiy operatsiyalar. Ushbu operatsiyalar dasturda pastki dasturlar sifatida ishlatiladi keyingi bo'limlarda keltirilgan algoritmlar.
Ushbu bobning boshida tushuntirilganidek, hisoblash uchun oddiy rekursiv algoritm mavjud massivdagi elementlar yig'indisi.
ALGORITM: yig'indisi(A) 1
bo'lsa |A| = 1, keyin A[0] 2 qaytariladi,
aks holda summa qaytariladi ({A[2i] + A[2i + 1] : i у [0..|A|/2)})
Ushbu algoritm uchun ish va chuqurlik takrorlanishlar bilan beriladi
W(n) = W(n/2) + O(n)
D(n) = D(n/2) + O(1)
W(n) = O(n) va D(n) = O(log n) yechimlari bor. Bu algoritm rekursiyasiz ham ifodalanishi mumkin (vaqt sikli yordamida), lekin rekursiv versiya rekursiv algoritmga soya soladi. skanerlash funksiyasi uchun.
Yozilganidek, algoritm faqat uzunligi 2 ga teng bo'lgan ketma-ketliklar ustida ishlaydi. ushbu cheklovni olib tashlash ketma-ketlikning g'alati uzunlikda va alohida ekanligini tekshirish orqali qiyin emas agar mavjud bo'lsa, oxirgi elementni qo'shish. Ushbu algoritm "yig'indi" ni hisoblash uchun osongina o'zgartirilishi mumkin. + o'rniga boshqa har qanday ikkilik assotsiativ operatordan foydalanish. Masalan, max dan foydalanish qaytib keladi ning maksimal qiymati ketma-ketlikda.


Grafiklar
Grafik muammolarini parallellashtirish odatda qiyin, chunki ko'plab standart ketma-ket grafik texnikasi, chuqurlik-birinchi yoki ustuvor-birinchi qidiruv kabilar, yaxshi parallellashmang. Ba'zi muammolar uchun, masalan Minimal kenglikdagi daraxt va biconnected komponentlar, gen uchun yangi texnikalar ishlab chiqilgan samarali parallel algoritmlarni ishlab chiqish. Boshqa muammolar uchun, masalan, bitta manbali eng qisqa yo'llar, u erda ma'lum samarali parallel algoritmlar, hech bo'lmaganda umumiy holat uchun emas.
Biz allaqachon 2-bo'limda ba'zi parallel grafik texnikasini aytib o'tdik. Ushbu bo'limda biz
Kenglik-birinchi qidiruv, bog'langan komponentlar va minimal kenglikdagi daraxtlar uchun algoritmlarni tavsiflash. Ushbu algoritmlar ba'zi umumiy usullardan foydalanadi. Xususan, randomizatsiya va grafik qisqarish algoritmlarida muhim rol o'ynaydi. Ushbu bobda biz o'zimizni cheklaymiz siyrak yo'naltirilmagan grafiklardagi algoritmlar. Qo'shimcha ma'lumot olish uchun quyidagi manbalarni tavsiya qilamiz parallel grafik algoritmlari bo'yicha [75, 2-8-boblar], [45, 5-bob], [35, 2-bob].


Saralash
Saralash - bu turli xil parallel echimlarni qabul qiladigan muammo. Ushbu bo'limda biz suhbatimizni cheklaymiz ikkita parallel tartiblash algoritmiga, QuickSort va radix sortga. Bu ikkala algoritm ham oson dasturlash va ikkalasi ham amalda yaxshi ishlaydi. Boshqa ko'plab tartiblash algoritmlarini bo'limda topish mumkin adabiyot. To'liqroq yoritish uchun qiziqqan o'quvchi [3, 45, 55] ga murojaat qiladi.