Parallel dasturlash

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 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.
16-rasm. 4 ta protsessor uchun Shell algoritmining ishlashiga misol

Shell algoritmining parallel variantining taqdim etilgan tavsifini hisobga olgan holda, parallel hisoblashlarni tashkil qilishning asosiy kichik muammosi, avvalgidek "taqqoslash va boʻlish" operatsiyasi asosida aniqlanishi mumkin. Natijada, pastki vazifalar soni har doim mavjud protsessorlar soniga toʻgʻri keladi (pastki vazifalardagi ma’lumotlar bloklari hajmi n / p) va masshtablash muammosi yoʻq. Tartiblangan ma’lumotlar toʻplami bloklarini protsessorlar oʻrtasida taqsimlash ma’lumotlarni uzatish tarmogʻining topologiyasi giperkub shaklida taqdim etilganda "taqqoslash va boʻlish" operatsiyalarini samarali bajarish imkoniyatini hisobga olgan holda tanlanishi kerak.