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