14. Parallel qidiruv

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 M_N tomonidan hujayralarga joylashtirilgan, kerakli qiymat M_N+1 katakchada joylashgan deb taxmin qilinadi. Topilgan hujayra raqami M_N+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, M_N+2 katakchasi nolga teng bo'ladi. Agar qiymat ro'yxatda topilsa, uni topadigan yagona odam protsessor M_N+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 (log² 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 (log² N) qiymati O (log TV) narxidan oshadi. maqbul ketma-ket qidiruv, ammo bu etarli emas parallel algoritmni ma'nosiz qiling.