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

 
Глава 10. Типы параллельных алгоритмов
 
Рассмотрим такие типы параллельных алгоритмов, как поиск и 
сортировка [4].
 
10.1.
Параллельный поиск
 
Рассмотрим задачу поиска элемента в списке. Пусть число процессоров 
равно числу элементов списка.
В следующем алгоритме предполагается, что список расположен в 
ячейках с 
М
1
 
по 
М
N
, искомое значение ­ в ячейке 
M
N
 
+ 1
,
a номер ячейки, в 
которой оно
обнаружено, должен быть записан в 
М
N + 2.
for j = l to N do
P[ j ] читает M[ j ] в Х и M[ N + 1 ] в target 

---

95 
if X = target then
записать
j 
в
M[ N + 2 ]
end if
end for
Все пустые ячейки памяти инициированы нулевым значением, 
следовательно по окончании работы алгоритма в ячейке 
M
N + 2
 
будет нуль, 
если искомое значение в списке не обнаружено. Если значение в списке 
найдено, то обнаруживший его процессор запишет в 
M
N + 2
номер 
содержащей его ячейки. На каждом из 
N
процессоров этот алгоритм 
выполняет один цикл чтение 
/
обработка / запись, поэтому общее время 
работы равно 
O(1)
, а стоимость (время работы, умноженное на число 
используемых процессоров) равна 
O(N).
Оптимальный последовательный 
алгоритм поиска, двоичный поиск, имеет стоимость 
O(log N).
Если уменьшить стоимость за счет уменьшения числа процессоров, 
получим следующий алгоритм
При наличии p <= N процессоров 
for j = l to p do
P[ j ] выполняет последовательный двоичный поиск 
в ячейках с M[ (j ­ l) * (N / p) + l ] по M[ j * (N / p) ] 
и записывает номер ячейки, содержащей X, в M[ N + 2 ] 
end for
При наличии одного процессора он будет вести поиск в ячейках с