Parallel algoritmlarni tahlil qilish - Analysis of parallel algorithms

Ushbu maqolada tahlil ning parallel algoritmlar. "Oddiy", ketma-ketlik, algoritmlarni tahlil qilish kabi, odatda, odam qiziqtiradi asimptotik resurslarni iste'mol qilish chegaralari (asosan hisoblash uchun sarflangan vaqt), ammo tahlil hisoblashlarni amalga oshirishda hamkorlik qiladigan ko'plab protsessor birliklari ishtirokida amalga oshiriladi. Shunday qilib, hisoblashning qancha "qadam" bosishini emas, balki protsessorlar sonining ko'payishi bilan qanchalik tezlashishini ham aniqlash mumkin. Tahlil yondashuvi birinchi navbatda protsessorlar sonini bostirish (yoki mavhumlashtirish) orqali ishlaydi. Keyingi fon paragrafida protsessorlar sonining mavhumligi qanday paydo bo'lganligi tushuntiriladi.

Dastlab Shiloach va Vishkin tomonidan ish vaqti (WT) (ba'zan ish chuqurligi yoki ish vaqti deb ataladigan) ramka kiritilgan. ^[1]parallel algoritmlarni kontseptsiyalash va tavsiflash uchun. WT ramkasida avval parallel algoritm parallel dumaloqlar bo'yicha tavsiflanadi. Har bir tur uchun bajariladigan operatsiyalar tavsiflanadi, ammo bir nechta masalalarni bostirish mumkin. Masalan, har bir turda bajariladigan operatsiyalar soni aniq bo'lmasligi kerak, protsessorlar haqida so'z yuritilmasligi kerak va protsessorlarni ish joylariga tayinlashda yordam beradigan har qanday ma'lumotni hisobga olish kerak emas. Ikkinchidan, bostirilgan ma'lumotlar taqdim etiladi. Bostirilgan ma'lumotni kiritish, aslida, Brent tufayli rejalashtirish teoremasining isboti asosida amalga oshiriladi,^[2] ushbu maqolada keyinroq tushuntirilgan. WT ramkasi foydalidir, chunki u parallel algoritmning dastlabki tavsifini ancha soddalashtirishi mumkin, shu bilan dastlabki tavsif bilan bosilgan tafsilotlarni kiritish juda qiyin emas. Masalan, WT ramkasi parallel algoritmlar kitoblarida asosiy taqdimot doirasi sifatida qabul qilingan (uchun Parallel tasodifiy kirish mashinasi PRAM modeli) ^[3]va,^[4] shuningdek, sinf yozuvlarida.^[5] Quyidagi umumiy ma'lumot, WT ramkasida WT ramkasida ularning tavsifi mavjud bo'lmaganda ham ko'proq umumiy parallel algoritmlarni tahlil qilish uchun qanday foydalanish mumkinligini tushuntiradi.

Umumiy nuqtai

Aytaylik, hisoblash mashinalari mavjud bo'lgan mashinada bajariladi $p$ protsessorlar. Ruxsat bering $T p$ hisoblashning boshlanishi va oxirigacha tugaydigan vaqtni belgilang. Hisoblashni tahlil qilish ish vaqti quyidagi tushunchalarga e'tibor qaratadi:

The ish tomonidan bajarilgan hisoblash $p$ protsessorlar - bu protsessorlar bajaradigan ibtidoiy operatsiyalarning umumiy soni.^[6] Protsessorlarni sinxronizatsiya qilishda aloqa xarajatlariga e'tibor bermaslik, bu hisoblashni bitta protsessorda ishlatish uchun sarflangan vaqtga teng $T 1$ .
The chuqurlik yoki oraliq tufayli ketma-ket bajarilishi kerak bo'lgan eng uzun operatsiyalar seriyasining uzunligi ma'lumotlar bog'liqliklari (the tanqidiy yo'l). Chuqurlikni "." Deb ham atash mumkin muhim yo'l uzunligi hisoblash.^[7] Parallel algoritmlarni loyihalashda chuqurlik / oraliqni minimallashtirish muhim ahamiyatga ega, chunki chuqurlik / oraliq bajarilishning eng qisqa vaqtini belgilaydi.^[8] Shu bilan bir qatorda, vaqt oralig'i sifatida belgilanishi mumkin $T \infty$ cheksiz ko'p protsessorga ega bo'lgan ideallashtirilgan mashinadan foydalangan holda hisoblash uchun sarflangan.^[9]
The xarajat hisoblash miqdori $pT p$ . Bu barcha protsessorlar tomonidan hisoblashda ham, kutishda ham sarf qilingan umumiy vaqtni ifodalaydi.^[6]

Bir nechta foydali natijalar ish ta'rifidan, ish vaqti va narxidan kelib chiqadi:

Ish qonuni. Narxi har doim kamida ishdir: $pT p \geq T 1$ . Bu haqiqatdan kelib chiqadi $p$ protsessorlar maksimal darajada ishlashi mumkin $p$ parallel ravishda operatsiyalar.^[6]^[9]
Span qonun. Cheklangan raqam $p$ protsessorlari cheksiz sondan oshib keta olmaydi, shuning uchun $T p \geq T \infty$ .^[9]

Ushbu ta'riflar va qonunlardan foydalangan holda quyidagi ishlash ko'rsatkichlari berilishi mumkin:

Tezlikni oshirmoq bu ketma-ket bajarilish bilan taqqoslaganda parallel ijro etish orqali amalga oshiriladigan tezlikning o'sishi: $S p = T 1 ∕ T p$ . Tezlashtirish qachon $Ω (n)$ kirish hajmi uchun $n$ (foydalanib katta O yozuvlari ), tezlashtirish chiziqli, bu hisoblashning oddiy modellarida maqbuldir, chunki ish qonuni shuni nazarda tutadi $T 1 ∕ T p \leq p$ (super chiziqli tezlashtirish tufayli amalda yuz berishi mumkin xotira iyerarxiyasi effektlar). Vaziyat $T 1 ∕ T p = p$ mukammal chiziqli tezlashtirish deb nomlanadi.^[9] Lineer tezlikni namoyish qiluvchi algoritm deyiladi o'lchovli.^[6]
Samaradorlik har bir protsessor uchun tezlashtirish, $S p ∕ p$ .^[6]
Parallelizm bu nisbat $T 1 ∕ T \infty$ . Bu har qanday miqdordagi protsessorlarda mumkin bo'lgan maksimal tezlikni anglatadi. Parallellik tezlikni cheklaydi: agar $p > T 1 ∕ T \infty$ , keyin:

${ displaystyle { frac {T_ {1}} {T_ {p}}} leq { frac {T_ {1}} {T _ { infty}}}$ .^[9]

The sustlik bu $T 1 ∕ (pT \infty)$ . Bittadan kam sustlik (qonun bo'yicha) mukammal chiziqli tezlikni iloji yo'qligini nazarda tutadi $p$ protsessorlar.^[9]

Cheklangan miqdordagi protsessorlarda ijro etish

Parallel algoritmlarni tahlil qilish odatda cheksiz ko'p protsessorlar mavjud degan taxmin ostida amalga oshiriladi. Bu haqiqiy emas, ammo muammo emas, chunki parallel ravishda ishlashi mumkin bo'lgan har qanday hisoblash $N$ protsessorlar bajarilishi mumkin $p < N$ har bir protsessorga bir nechta ish birliklarini bajarishga ruxsat berish orqali protsessorlar. Natija chaqirildi Brent qonuni o'z vaqtida bunday "simulyatsiya" ni amalga oshirishi mumkinligini aytadi $T p$ bilan chegaralangan^[10]

{ displaystyle T_ {p} leq T_ {N} + { frac {T_ {1} -T_ {N}} {p}},}

yoki, aniqrog'i,^[6]

{ displaystyle T_ {p} = O chap (T_ {N} + { frac {T_ {1}} {p}} o'ng).}

Qonunning muqobil bayonoti chegaralanadi $T p$ yuqoridan va pastdan

{ displaystyle { frac {T_ {1}} {p}} leq T_ {p} leq { frac {T_ {1}} {p}} + T _ { infty}}

.

oralig'i (chuqurligi) $T \infty$ va ish $T 1$ birgalikda hisoblash vaqtiga tegishli chegaralarni taqdim etadi.^[2]

Adabiyotlar

^ Shiloach, Yossi; Vishkin, Uzi (1982). "An O(n² jurnaln) parallel maksimal oqim algoritmi ". Algoritmlar jurnali. 3 (2): 128–146. doi:10.1016 / 0196-6774 (82) 90013-X.
^ ^a ^b Brent, Richard P. (1974-04-01). "Umumiy arifmetik ifodalarni parallel baholash". ACM jurnali. 21 (2): 201–206. CiteSeerX 10.1.1.100.9361. doi:10.1145/321812.321815. ISSN 0004-5411. S2CID 16416106.
^ JaJa, Jozef (1992). Parallel algoritmlarga kirish. Addison-Uesli. ISBN 978-0-201-54856-3.
^ Keller, Yorg; Kessler, Kristof V.; Traeff, Jesper L. (2001). Amaliy PRAM dasturlash. Wiley-Intertersience. ISBN 978-0-471-35351-5.
^ Vishkin, Uzi (2009). Parallel fikrlash: ba'zi asosiy ma'lumotlar-parallel algoritmlar va usullar, 104 bet (PDF). 1992 yildan beri Merilend universiteti, Kollej parki, Tel-Aviv universiteti va Texnionda parallel algoritmlar bo'yicha o'qitilgan darslarning eslatmalari.
^ ^a ^b ^v ^d ^e ^f Casanova, Anri; Legrand, Arno; Robert, Iv (2008). Parallel algoritmlar. CRC Press. p. 10. CiteSeerX 10.1.1.466.8142.
^ Blelloch, Yigit (1996). "Parallel algoritmlarni dasturlash" (PDF). ACM aloqalari. 39 (3): 85–97. CiteSeerX 10.1.1.141.5884. doi:10.1145/227234.227246. S2CID 12118850.
^ Maykl Makkul; Jeyms Rayners; Arch Robison (2013). Strukturaviy parallel dasturlash: samarali hisoblash naqshlari. Elsevier. 4-5 bet.
^ ^a ^b ^v ^d ^e ^f Kormen, Tomas H.; Leyzerson, Charlz E.; Rivest, Ronald L.; Shteyn, Klifford (2009) [1990]. Algoritmlarga kirish (3-nashr). MIT Press va McGraw-Hill. 779-784-betlar. ISBN 0-262-03384-4.
^ Gustafson, Jon L. (2011). "Brent teoremasi". Parallel hisoblash entsiklopediyasi. 182–185 betlar. doi:10.1007/978-0-387-09766-4_80. ISBN 978-0-387-09765-7.

[shiloach-1] Shiloach, Yossi; Vishkin, Uzi (1982). "An O(n² jurnaln) parallel maksimal oqim algoritmi ". Algoritmlar jurnali. 3 (2): 128–146. doi:10.1016 / 0196-6774 (82) 90013-X.

[brent-2] Brent, Richard P. (1974-04-01). "Umumiy arifmetik ifodalarni parallel baholash". ACM jurnali. 21 (2): 201–206. CiteSeerX 10.1.1.100.9361. doi:10.1145/321812.321815. ISSN 0004-5411. S2CID 16416106.

[jaja-3] JaJa, Jozef (1992). Parallel algoritmlarga kirish. Addison-Uesli. ISBN 978-0-201-54856-3.

[kkt-4] Keller, Yorg; Kessler, Kristof V.; Traeff, Jesper L. (2001). Amaliy PRAM dasturlash. Wiley-Intertersience. ISBN 978-0-471-35351-5.

[uv-5] Vishkin, Uzi (2009). Parallel fikrlash: ba'zi asosiy ma'lumotlar-parallel algoritmlar va usullar, 104 bet (PDF). 1992 yildan beri Merilend universiteti, Kollej parki, Tel-Aviv universiteti va Texnionda parallel algoritmlar bo'yicha o'qitilgan darslarning eslatmalari.

[casanova-6] v ^d ^e ^f Casanova, Anri; Legrand, Arno; Robert, Iv (2008). Parallel algoritmlar. CRC Press. p. 10. CiteSeerX 10.1.1.466.8142.

[cacm-7] Blelloch, Yigit (1996). "Parallel algoritmlarni dasturlash" (PDF). ACM aloqalari. 39 (3): 85–97. CiteSeerX 10.1.1.141.5884. doi:10.1145/227234.227246. S2CID 12118850.

[spp-8] Maykl Makkul; Jeyms Rayners; Arch Robison (2013). Strukturaviy parallel dasturlash: samarali hisoblash naqshlari. Elsevier. 4-5 bet.

[clrs-9] v ^d ^e ^f Kormen, Tomas H.; Leyzerson, Charlz E.; Rivest, Ronald L.; Shteyn, Klifford (2009) [1990]. Algoritmlarga kirish (3-nashr). MIT Press va McGraw-Hill. 779-784-betlar. ISBN 0-262-03384-4.

[10] Gustafson, Jon L. (2011). "Brent teoremasi". Parallel hisoblash entsiklopediyasi. 182–185 betlar. doi:10.1007/978-0-387-09766-4_80. ISBN 978-0-387-09765-7.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

Parallel hisoblash
Umumiy	Tarqatilgan hisoblash Parallel hisoblash Katta darajada parallel Bulutli hisoblash Yuqori samarali hisoblash Ko'p ishlov berish Manycore protsessori GPGPU Kompyuter tarmog'i Sistolik qator
Darajalar	Bit Yo'riqnoma Ip Vazifa Ma'lumotlar Xotira Loop Quvur liniyasi
Ko'p ishlov berish	Vaqtinchalik Bir vaqtda (SMT) Spekulyativ (SpMT) Preventiv Kooperativ Klasterli ko'p tarmoqli (CMT) Uskuna skauti
Nazariya	PRAM modeli PEM modeli Parallel algoritmlarni tahlil qilish Amdahl qonuni Gustafson qonuni Iqtisodiy samaradorlik Karp-Flatt metrikasi O'zingni bos Tezlikni oshirmoq
Elementlar	Jarayon Ip Elyaf Ko'rsatmalar oynasi Array ma'lumotlar tuzilishi
Muvofiqlashtirish	Ko'p ishlov berish Xotira izchilligi Keshning izchilligi Keshni bekor qilish To'siq Sinxronizatsiya Ilovani tekshirish punkti
Dasturlash	Oqimni qayta ishlash Dataflow dasturlash Modellar Yashirin parallellik Aniq parallellik Muvofiqlik Blokirovka qilmaydigan algoritm
Uskuna	Flinn taksonomiyasi SISD SIMD SIMT Miss MIMD Dataflow arxitekturasi Quvurli protsessor Superscalar protsessori Vektorli protsessor Multiprotsessor nosimmetrik assimetrik Xotira birgalikda tarqatildi birgalikda tarqatildi UMA NUMA KOMA Katta hajmdagi parallel kompyuter Kompyuter klasteri Tarmoqli kompyuter Uskuna tezlashishi
API-lar	Ateji PX Boost Chapel HPX Jozibasi ++ Cilk Coarray Fortran CUDA Dryad C ++ AMP Global massivlar GPUOchiq MPI OpenMP OpenCL OpenHMPP OpenACC Parallel kengaytmalar PVM POSIX mavzular RaftLib UPC TBB ZPL
Muammolar	Avtomatik parallellashtirish Tugatish Deterministik algoritm Xijolat bilan parallel Parallel sekinlashuv Musobaqa holati Dasturni blokirovka qilish Miqyosi Ochlik
Kategoriya: Parallel hisoblash