Parallel dasturlash

Masalaning qoʻyilishi. mxn oʻlchamli A matritsani va n ta elementdan iborat b vektorni koʻpaytirish natijasida har bir i-element ning i-qatorini skalyar koʻpaytirish natijasi boʻlgan m oʻlchamli c vektorni olamiz. A matritsasi (bu chiziqni a_i bilan belgilang) va b vektori:
.
Shunday qilib, natijada c vektorni olish A matritsa va b vektorining qatorlarini koʻpaytirish uchun bir xil turdagi m amallarni takrorlashni nazarda tutadi. Har bir bunday amal matritsa qatori va b vektorining elementlarini koʻpaytirishni (n ta amal) va natijada olingan koʻpaytmalarning keyingi yigʻindisini (n-1 amal) oʻz ichiga oladi. Kerakli skalyar operatsiyalarning umumiy soni - miqdor

Algoritmning ketma-ketligi. Matritsa-vektorni ketma-ket koʻpaytirish algoritmini quyidagicha ifodalash mumkin.
1-misol. Matritsani vektorga ketma-ket koʻpaytirish algoritmi


for (i = 0; i < m; i++)
{
c[i] = 0;
for (j = 0; j < n; j++)
{
c[i] += A[i][j]*b[j]
}
}
Matritsa-vektorlarni koʻpaytirish - skalyar koʻpaytmalarni hisoblash ketma-ketligidir. Uzunligi n boʻlgan vektorlarning nuqta koʻpaytmasini har bir hisoblash n ta koʻpaytirish va n-1 qoʻshish amallarini talab qilganligi sababli, uning murakkabligi O (n) tartibida boʻladi. Matritsa-vektorni koʻpaytirishni amalga oshirish uchun skalyar koʻpaytmani hisoblashning m ta amalini bajarish kerak, shuning uchun algoritm O (mn) tartibli murakkablikka ega.
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.