16-ma’ruza. Sodda parallel algoritmlar

void ShellSort(double A[], int n) { 
int incr = n / 2; 
while (incr > 0) { 
for (int i = incr + 1; i < n; i++) { 
int j = i - incr;
while (j > 0) 
if (A[j] > A[j + incr]) {
swap(A[j], A[j + incr]); 
j = j - incr;
} 
else j = 0; 
} 
incr = incr/2;
} 
} 
 

---

Shell algoritmi uchun parallel hisoblashni tashkil etish. 
Shell 
algoritmi uchun usulning parallel analogini taklif qilish mumkin, agar 
aloqa tarmogʻi topologiyasi N oʻlchovli giperkub sifatida samarali taqdim 
etilishi mumkin boʻlsa (ya’ni, protsessorlar soni p = 2N ga teng). Bu holda 
saralashni ikkita ketma-ket bosqichga boʻlish mumkin. Birinchi 
bosqichda (N iteratsiya) giperkub tuzilishida qoʻshni boʻlgan 
protsessorlar oʻzaro ta’sir qiladi "Taqqoslash va boʻlish" operatsiyasini 
bajarishda bir-biri bilan oʻzaro ta’sir qiluvchi juft protsessorlarning 
shakllanishi quyidagi oddiy qoida yordamida ta’minlanishi mumkin - har 
bir iteratsiyada i, 0 <= i ularning raqamlari faqat N
i
holatida juftlashadi. 
Ikkinchi bosqich - parallel toq-juft almashtirish algoritmining odatiy 
iteratsiyasini amalga oshirish. Ushbu bosqichning takrorlashlari 
tartiblanadigan toʻplamning haqiqiy oʻzgarishi toʻxtaguncha bajariladi va 
shuning uchun bunday takrorlashlarning umumiy soni L 2 dan p gacha 
oʻzgarishi mumkin. 
16-rasmda koʻrib chiqilgan usul yordamida 16 elementdan iborat 
massivni saralash misolini koʻrsatadi (protsessorlar doiralar bilan 
koʻrsatilgan, protsessor raqamlari bit koʻrinishida berilgan). Shuni 
ta’kidlash kerakki, ma’lumotlar birinchi bosqichdan keyin allaqachon 

---

buyurtma qilingan va juft-toq almashtirishni amalga oshirishga hojat 
yoʻq.