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

М
1
 
до 
M
N
. Поэтому на одном процессоре этот алгоритм сводится к 
последовательному двоичному поиску. Значит его стоимость равна 
O(log N),
а время выполнения тоже 
O(log N).
При использовании 
N
процессоров мы возвращаемся к первому 
параллельному варианту со стоимостью 
O(N) 
и временем выполнения 
O(1).
В промежуточных вариантах, для р списков, содержащих 
N / p
элементов 
каждый, время выполнения равно 
O(log(N /p))
, а его стоимость 
O(p log(N /

---

96 
p)). Если 
р = log N, то log (N / log N) = log N ­ log (log N)

log N.
Время 
выполнения равно 
О(log N)
при стоимости 
О((log N) * (log N)) = О(log2 N).
Порядок времени выполнения параллельного алгоритма совпадает с 
порядком последовательного двоичного поиска, однако константа в оценке 
оказывается меньше, поэтому параллельный алгоритм будет выполняться 
быстрее. Стоимость 
O(log2 N)
превышает стоимость 
O(log N)
оптимального 
последовательного поиска, однако не настолько, чтобы сделать 
параллельный алгоритм бессмысленным.
10.2. Сортировка на линейных сетях
Начнем с метода сортировки, основанного на линейной конфигурации 
сети. Если число процессоров равно числу сортируемых значений, то сорти-
ровку можно осуществить, передавая сети в каждом цикле одно значение.
Первый процессор читает поданное значение, сравнивает его с 
текущим и передает большее значение своему соседу. Остальные процессоры 
делают то же самое: сохраняют меньшее из двух значений и пересылают 
большее следующему звену в цепочке. Получаем следующий алгоритм:
for i = l to N ­ 1 do
занести следующее значение в М[1]
Parallel Start
P[j] читает M[j] в Current
for k = l to j ­ 1 do
P[k] читает M[k] в New
if Current > New then
P[k] пишет Current в M[k + l]
Current = New
else
P[k] пишет New в M[k + l]
end if
end for k
Parallel End

---

97 
занести следующее значение в М[1]
Parallel Start
P[j] читает M[j] в Current
for k = l to j ­ 1 do
P[k] читает M[k] в New
if Current > New then
P[k] пишет Current в M[k + l]
Current = New
else
P[k] пишет New в M[k + l]
end if
end for k
Parallel End
Parallel Start
for j = l to N ­ 1 do
P[j] пишет Current в M[j]
end for j
Parallel End
На первых этапах выполнения вычислений первый процессор 
считывает значение элемента списка в переменную 
New
. Далее, в процессе 
работы алгоритма, очередному параллельному проходу предшествует запись 
значения текущего элемента списка, при его наличии, в начальную ячейку 
памяти 
Current
. Процессу соответствует цикл 
for
, который содержит 
параллельные блоки. Первый из этих блоков отвечает за чтение первого 
значения списка, а второй блок – за сравнение элементов. Элементы 
записываются в память по окончании вычислений. 
На рис. 32 а и 32 б [2] представлена работа этого алгоритма на входном 
списке 15, 18, 13, 12, 17, 11, 19, 16, 14.

---

98 
Шаг А – происходит запись в память 1-го элемента списка, который 
считывается процессором 1.
Шаг В – происходит запись в память 2-го элемента, который 
сравнивается со значением в процессоре