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

 
7.3. 
Простые параллельные операции
 
Рассмотрим две элементарные операции: 
- 
распределение входных данных по процессорам
- 
поиск минимального или максимального элемента списка. 
Пусть 
Р
i
 - i-
й
процессор; 
р
 -
число процессоров
, 
N
 
- 
число элементов во 
входном списке, 
M
j
 
- 
j-
ая
ячейка памяти через. Параллельно операции 
записываются в скобках 
Parallel Start
и 
Parallel
 
End.
Если сначала 
параллельно выполняется один блок операций, а затем другой, то они 
заключаются в отдельные пары скобок. 

---

77 
Распределение данных в модели 
CREW PRAM
В модели CREW одну и ту же ячейку памяти могут читать 
одновременно несколько процессоров. Таким образом
, 
запись значения в 
процессоры происходит достаточно быстро. Значение записывается в память, 
затем все процессоры читают его. Такая модель называется –
конкурентное
чтение.
Р[1] записывает значение в М[1] 
Parallel Start
for k = 2 to p do
P[k] читает значение из М[1] 
end for
Parallel End
Распределение данных в модели EREW PRAM 
Значение, записанное процессором P
i
, может прочитать только один 
процессор. Если использовать цикл чтение / обработка / запись на втором 
процессоре для записи значения в другую ячейку памяти, то на следующем 
шаге уже два процессора смогут прочитать это значение. Далее записав 
значение еще в две ячейки, можно использовать четыре процессора. Это 
- 
модель с исключительным чтением.
Р[1] записывает значение в ячейку М[1] 
procLoc = l
for j = l to log p do
Parallel Start
for k = procLoc + l to 2 * procLoc do
P[k] 
читает
M[k ­ procLoc] 
P[k] записывает в М[k] 
end for k
Parallel End
procLoc = procLoc * 2
end for j

---

78