Учебное пособие москва мади 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
Сравнение пар