14. Parallel qidiruv


Download 14.76 Kb.
Sana29.05.2020
Hajmi14.76 Kb.
#111582
Bog'liq
391 5 [1](1)I17 (2)(1)
sirpanish podshipniklarini tamirlash, Task 13,14 page 46, 401. Makhliyo Kholmuminova. sci-tech. 1, mojiza kitob 1 bolalar uchun unversal (2), mojiza kitob 1 bolalar uchun unversal (2), ozbek tilida badiiy tasvir vositalari , chiziqli15, chiziqli15, chiziqli15, boshlangich sinflarda matematikada og, 2 5274045889017546310, Til bo'yicha bilimlarni baxolash 7, 5 sinf adabiyot fanidan dars ishlanma, 5 sinf adabiyot fanidan dars ishlanma

14. Parallel qidiruv

Biz parallel qidiruv usullarini o'rganishni soddaligi bilan boshlaymiz, bunda protsessorlar soni ro'yxat elementlari soniga teng bo'ladi. Tahlil shuni ko'rsatadiki, bunday echim maqbul echimdan qanchalik arzon turadi. Keyin, hisoblashda bo'lgani kabi, protsessorlar sonini kamaytirish orqali xarajatlarni kamaytirishga harakat qilamiz maksimal. Ro'yxatda dubl mavjud emas deb taxmin qilamiz. Agar protsessorlar soni ro'yxat elementlari soniga teng bo'lsa (p = N), u holda har bir protsessor kerakli qiymatni ro'yxatidagi element bilan taqqoslashi mumkin. Agar mos kelsa, aniqlagan protsessor bu tasodif ba'zi bir hujayradagi raqamni qayd qilishi mumkin xotira joyi. Keyingi algoritmda ro'yxat M1 dan MN tomonidan hujayralarga joylashtirilgan, kerakli qiymat MN+1 katakchada joylashgan deb taxmin qilinadi. Topilgan hujayra raqami MN+2 - bilan yozilishi kerak.



Dastlab barcha bo'sh xotira hujayralarida mavjud deb taxmin qilamiz nol qiymat kiritiladi, shuning uchun algoritm oxirida, agar kerakli qiymat ro'yxatda topilmasa, MN+2 katakchasi nolga teng bo'ladi. Agar qiymat ro'yxatda topilsa, uni topadigan yagona odam protsessor MN+2-da uni o'z ichiga olgan hujayraning sonini yozadi. Har bir N protsessorda ushbu algoritm bitta tsiklni bajaradi. o'qish / qayta ishlash / yozish, shuning uchun umumiy ish vaqti O(1), qiymati esa O (N) dir. Quyida tavsiflangan alternativ parallel algoritm soniga qarab ish narxi va vaqtini o'zgartirishga imkon beradi mavjud protsessorlar.

Agar bitta protsessor bo'lsa, u hujayralarni qidiradi M1 dan MN gacha, ya'ni, butun ro'yxatda. Shuning uchun bitta protsessorda bu algoritm ketma-ket ikkilik izlashga tushadi. Vositalari uning qiymati O(log N) va ish vaqti ham O(log N). N protsessorlaridan foydalanganda birinchi parallelga qaytamiz muqobil variant O(N) va qo'rg'oshin vaqti O(1). Oraliq versiyalarda biz o'z ichiga olgan p ro'yxatlari bilan shug'ullanamiz N/P elementlarning har biri. Bunday imkoniyatning amal qilish vaqti O (log (N/P)) ga teng va uning qiymati O (plog (N/P)). Xususan eslatma p-log TV, bunda log(N/log TV) = log N – log (log N) va log(N). Bu holda, ish vaqti O (log N) narxda bo'ladi O ((log N) * (log N)) = O (log2 N). Parallel algoritmni bajarish vaqti tartibi bir xil izchil ikkilik qidirish tartibi bilan, lekin doimiy bo'lsin taxmin kichikroq, shuning uchun parallel algoritm tezroq bo'ladi. O (log2 N) qiymati O (log TV) narxidan oshadi. maqbul ketma-ket qidiruv, ammo bu etarli emas parallel algoritmni ma'nosiz qiling.
Download 14.76 Kb.

Do'stlaringiz bilan baham:




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2022
ma'muriyatiga murojaat qiling