Учебное пособие москва мади 2020 ббк 32. 81 В 683 Волосова, А. В. В683

P
1
. Значение, которое оказывается 
большим записывается в 
М
2
.
Шаг С – происходит запись в М
1
третьего элемента списка. Происходит 
сравнение этого элемента с содержимым процессора 
P
1
. Происходит 
считывание значения из М
2
, которое осуществляет процессор 
Р
2
.
Шаг D - выполнение операции сравнения процессорами 
Р
1
и 
Р
2
.
1-й, 3-й, 5-й и т.д. шаги – чтение 
2-й, 4-й, 6-й и т.д. шаги – сравнение, в котором участвуют все 
процессоры.
Алгоритм сортировки выполняет вычисления за 16 шагов + 1 ( запись 
результата. 
Для 
N
процессоров - 
2 * (N - 1) + 1
действий. Вычислительная 
сложность - 
O(N).
Стоимость алгоритма - 
O(N
2
).
Рис. 32 а. Алгоритм сортировки на линейных сетях 

---

99 
Рис. 32 б. 
Алгоритм сортировки на линейных сетях

---

100 
Четно-нечетная сортировка перестановками
Выше нам удавалось снизить стоимость алгоритмов за счет сокращения 
числа процессоров. Необходимое число процессоров можно уменьшить 
вдвое, воспользовавшись следующим способом сортировки, который 
сравнивает соседние значения и при необходимости переставляет их [2].
for j = 1 to N / 2 do
Parallel Start
for k = l to N / 2 do
P[k] сравнивает M[2k ­ l] и M[2k]
if их порядок неправильный then
переставить их
end if
end for k
Parallel End
Parallel Start
for k = l to N / 2 ­ 1 do
P[k] сравнивает M[2k] и M[2k + 1]
if их порядок неправильный then
переставить их
end if
end for k
Parallel End
end for j
Сравнение пар