Parallel izlash va uning samaradorligi



Annatotsiya. Izlashning parallel metodlarini o’rganishni biz eng oddiy, ya’ni protsessorlar soni ro’yxatning elementlari soniga teng bo’lgan ko’rinishidan boshlaymiz. Analiz bizga bu yechim qiymati bo’yicha optimal yechimdan qanchalik yiroqligini ko’rsatadi. Undan keyin biz maksimumni hisoblashda qo’llanilganiday, qiymatni protsessorlar sonini kamaytirish hisobiga kamaytirishga harakat qilamiz. Bunda faraz qilamizki, ro’yxatda dublikatlar yo’q.

Kalit so’zlar: parelell, protsessor, xotira, yacheyka.

Agar protsessorlar soni ro’yxatning elementlari soniga teng bo’lsa (p=N), unda har qaysi protsessor qidirilayotgan qiymatni ro’yxatdagi o’ziga tegishli element bilan taqqoslaydi. Agar o’xshashlik sodir bo’lsa, o’xshashlikni topgan protsessor, yacheyka nomerini xotiraning ba’zi maxsus joylariga yozishi mumkin. Keyingi algoritmda faraz qilamizki, ro’yxat M₁ dan M_N gacha yacheykalarda joylashgan, qidirilayotgan qiymat esa M_N+1 –yacheykada, u aniqlangan yacheyka nomeri esa, M_N+2 ga yozilgan bo’lishi kerak.

Parallel Sort

for j=1 to N do P[j] M[j] ni Х ga va M[N+1] ni target ga o’qiydi

if X=target then

j ni M[N+2] ga yozadi

end if

end for

Parallel End

Biz faraz qilamizki, barcha bo’sh xotira yacheykalariga boshlang’ich nolga

1- rasm. Parelell hisoblashning blok-sxemasi

teng qiymat kiritilgan, shuning uchun algoritm ishining yakunida agar qidirilayotgan qiymat ro’yxatda topilmasa, M_N+2 –yacheyka nolga teng bo’ladi. Lekin agar qiymat ro’yxatda topilsa, uni aniqlagan yagona protsessor u joylashgan yacheyka nomerini M_N+2 ga yozadi.

N ta M_N+2 ning har birida bu algoritm o’qish / qayta ishlash / yozishning bitta siklini bajaradi, shuning uchun umumiy ishlash vaqti O(1), qiymati esa O(N) ga teng. Eslaymizki, optimal ketma-ket izlash algoritmining qiymati O(log N) ga teng edi.

Quyida keltirilgan alternativ parallel algoritm qiymatni va ishlatiladigan protsessorlar soniga bog’liq ravishda ish vaqtini o’zgartirish imkonini beradi.

Protsessorlar soni p<=N bo’lganda

Parallel Start

for j=1 to p do

P [j] М[(j-l)*(N/p)+l] dan M[j*(N/p)] gacha bo’lgan yacheykalardaketma-ket ikkilangan izlashni bajaradi va X tarkib topgan yacheyka nomerini M[N+2] ga yozadi

end for

Parallel End

Agar protsessor bitta bo’lsa, u izlashni M₁ dan M_N gacha bo’lgan yacheykalarda, aniqrog’i butun ro’yxatda olib boradi. Shuning uchun bitta protsessorda bu algoritm ketma-ket ikkilangan izlashga kelib qoladi. Demak uning qiymati O(log N) ga teng, bajarilish vaqti ham O(log N) ga teng.

N ta protsessor ishlatilganda esa, biz qiymati O(N) va bajarilish vaqti O(1) bo’lgan birinchi parallel variantga qaytamiz. Oraliq variantlarda esa biz har biri N/p ta elementdan tarkib topgan p ta ro’yxat bilan ish ko’ramiz. Bu variantning bajarilish vaqti O(log (N/p)), qiymati esa O(p log (N/p)) ga teng. Lekin p – log TV bo’lgan holatni alohida qarash lozim, bunda log (N/log TV) = log N ⎯ log (log N). Bu holatda qiymat O((log N)*(log N)) = O(log² N) bo’lganda, bajarilish vaqti O(log N).

Xulosa. Parallel algoritmning bajarilish vaqti tartibi ketma-ket ikkilamchi izlash tartibiga to’g’ri keladi, lekin baholashdagi konstanta kamroq bo’ladi, shu sababdan parallel algoritm tezroq bajariladi. O(log² N) qiymat optimal ketma-ket izlashning O(log N) qiymatini oshirib yuboradi, lekin bu parallel algoritm ma’nosini yo’qotadigan darajaga bormaydi. Umuman olganda izlashda parallel usullardan foydalanish har doim vaqt bo’yicha samaraga olib keldi.

Adabiyotlar:

1. Новиков Ф.А Дискретная математика для программистов СПб.: Питер, 2001
2. Дж. Макконел Основы современных алгоритмов М: Москва. 2001