Parallel dasturlash algoritmlari

1-bosqich. Dekompozitsiya (segmentlash, bo’laklash).

Ma’lumotlarni dekompozitsiyalash, bu- ma’lumotlarni va algoritmlarni qayta ishlov berish uchun segmentlarga bo’lishdir.

Ma’lumotlar taxminan bir xil hajmdagi qismlarga (fragmentlarga) bo’linadi, qismlar ularni qayta ishlash operatorlari bilan bog’lanadi, undan so’ng keying vazifalar hosil qilinadi. So’ngra uzatish zarur bo’lgan ma’lumotlar belgilanadi, zarur bo’lmaganlari olib tashlanadi.
Boshlanishida eng ko’p murojaat qilinayotgan kichik hajmdagi axborotlar tahlil qilib chiqiladi. Ma’lumotlar strukturasini dekompozitsiya qilishda statik yoki dinamik dekompozitsiya qilish sxemalaridan foydalanish mumkin.
Jarayonning boshida, funksional dekompozitsiya amalga oshiriladi. Hisoblash algoritmlari segmentlanadi, so’ng shu sxema asosida dekompozitsiyalangan ma’lumotlar jo’natiladi. Bu uslub parallellashtiriladigan ma’lumotlar strukturasi uchun to’g’ri keladi. Quyidagi tafsiyalar bajarilsa dekompozitsiyaning samaradorligiga erishiladi:
Dekompozitsiyalangandan so’ng buyruqlar soni protsessorlar soniga mos kelishi kerak.
Buyruqlar deyarli bir xil hajmda bo’lishi kerak.
Topshiriqning hajmi oshishi bilan buyruqlar soni ham bir topshiriqdagi buyruqlar soniga proporsional ravishda oshishi kerak.
Buyruqlar hajmi algoritm asosida aniqlanadi. Bu asos bir blokdagi operatsiyalar soniga mos ravishda olinadi:
Kichik asosli parallellashtirish – buyruq darajasida: 20 dan 1000 tagacha buyruqlar parallel bajariladi, bir blokdagi o’rtacha buyruqlar soni 5 tani tashkil qiladi.
O’rta blokli parallellashtirish – protsedura darajasida: blokdagi buyruqlar 2000 tagacha bo’ladi. Protseduralar orasidagi bog’liqlikni amalga oshirirsh murakkab. Kommunikatsiyadagi talablar keyingilarda ko’ra pastroq.
Yirik blokli parallellashtirish – topshiriq darajasida: Mos ravishda, mustaqil dasturlarni parallel kompyuterlarda bajarishdir. Yirikblokli parallellashtirshni OT qo’llab quvvatlashi talab etiladi.