16-ma’ruza. Sodda parallel algoritmlar

Ma’lumot taqsimlash.
Matritsani vektorga koʻpaytirishning parallel 
algoritmlarini bajarishda A matritsadan tashqari b vektorini va c natija 
vektorini boʻlish kerak. Vektor elementlarini koʻpaytirish mumkin, ya’ni 
barcha vektor elementlari koʻp protsessorli hisoblash tizimini tashkil 
etuvchi barcha protsessorlarga koʻchirilishi yoki protsessorlar oʻrtasida 
taqsimlanishi mumkin. n ta elementdan iborat vektor bloklarga 
boʻlinganda, har bir protsessor vektorning k elementining uzluksiz ketma-

---

ketligini qayta ishlaydi (biz faraz qilamizki, n vektorning oʻlchami 
protsessorlar soniga boʻlinadi, ya’ni n = k x p). 
Nima uchun protsessorlar oʻrtasida b va c vektorlarining takrorlanishi 
mumkin boʻlgan yechim ekanligini tushuntiramiz (bundan keyin taqdim 
etishning soddaligi uchun biz m = n deb qabul qilamiz). b va c vektorlari 
n ta elementdan iborat, ya’ni matritsaning bitta satri yoki ustuni kabi koʻp 
ma’lumotlarni oʻz ichiga oladi. Agar protsessor matritsaning satri yoki 
ustunini hamda b va c vektorlarning yagona elementlarini saqlasa, u holda 
saqlangan elementlarning umumiy soni O (n) tartibli boʻladi. Agar 
protsessor matritsaning satrini (ustunini) va b va c vektorlarning barcha 
elementlarini saqlasa, u holda saqlangan elementlarning umumiy soni 
ham O (n) tartibli boʻladi. Shunday qilib, vektorlarni koʻpaytirish va 
boʻlishda xotira talablari bir xil murakkablik sinfidan.