Parallel algorithms

Keyingi uchta mavzu masshtablilik va ko'p ma'lumotlar bilan ishlash haqida. Qadimgi davrlarda kompyuterlar tobora tezlashib borardi. Agar siz algoritmingizni tezroq qilishni xohlasangiz, bir necha oy kutishingiz mumkin va kompyuterlarning o'zlari tezroq bo'ladi. Ammo biz bu davrning oxiriga yaqinmiz. Buning o'rniga, noutbuklar va kompyuterlar bir nechta yadrolarga ega. Algoritmlaringizni tezroq qilish uchun ularni bir vaqtning o'zida barcha yadrolar bo'ylab parallel ravishda ishlashi uchun o'zgartirishingiz kerak!

Mana oddiy misol. Saralash algoritmi bilan qila oladigan eng yaxshi narsa taxminan O(n log n). Ma'lumki, siz massivni O (n) vaqtida tartiblay olmaysiz - agar siz parallel algoritmdan foydalanmasangiz! Tez tartiblashning parallel versiyasi mavjud bo'lib, u massivni O (n) vaqtida saralaydi.

Parallel algoritmlarni loyihalash qiyin. Va ularning to'g'ri ishlashiga ishonch hosil qilish va siz qanday tezlikni oshirishni ko'rishingizni aniqlash qiyin. Bir narsa aniq - vaqt daromadlari chiziqli emas. Shunday qilib, agar tizza kompyuteringizda bitta o'rniga ikkita yadro bo'lsa, bu sizning algoritmingiz sehrli tarzda ikki baravar tez ishlashini anglatmaydi. Buning bir nechta sabablari bor:

• Parallelizmni boshqarish bo'yicha qo'shimcha xarajatlar — deylik, siz 1000 ta elementdan iborat massivni saralashingiz kerak. Ushbu vazifani ikkita yadro o'rtasida qanday taqsimlaysiz? Har bir yadroga saralash uchun 500 ta element berasiz va keyin ikkalasini birlashtirasiz orted massivlarni bitta katta tartiblangan massivga aylantirasizmi? Ikki massivni birlashtirish vaqt talab etadi.

• Yuklarni muvozanatlash — deylik, sizda 10 ta vazifa bor, shuning uchun siz har bir asosiy vazifani 5 tadan topshirasiz. Ammo A yadrosi barcha oson vazifalarni oladi, shuning uchun u 10 soniyada bajariladi, B yadrosi esa barcha qiyin vazifalarni oladi, shuning uchun bir daqiqa davom etadi. Bu shuni anglatadiki, A yadrosi 50 soniya davomida bo'sh o'tirgan, B yadrosi esa barcha ishlarni bajargan! Ikkala yadro ham bir xil darajada ishlashi uchun ishni qanday qilib teng taqsimlaysiz?

Agar siz ishlash va kengayishning nazariy tomoniga qiziqsangiz, parallel algoritmlar siz uchun bo'lishi mumkin!