Простые параллельные операции

Рассмотрим теперь две элементарные операции: распределение входных данных по процессорам и поиск минимального или максимального элемента списка. Ниже мы обозначаем /*-й процессор через Ph число процессоров через р, число элементов во входном списке через N, а у-ю ячейку памяти через М7. Выполняемые параллельно операции записываются в скобках Parallel Start и Parallel End. Если сначала параллельно выполняется один блок операций, а затем другой, то они заключаются в отдельные пары скобок.

Распределение данных в модели CREW PRAM

Напомним, что в модели CREW одну и ту же ячейку памяти могут читать одновременно несколько процессоров. В результате значение можно занести во все процессоры очень быстро:

/>[1] записывает значение в М[1]

Parallel Start

for k = 2topdo

РЩ читает значение из М[]

endfor Parallel End

Распределение совершается в два этапа. На первом значение записывается в память, на втором - все процессоры читают его. Такая скорость возможна только благодаря конкурентному чтению. Посмотрим теперь, как должна выглядеть эта процедура для модели с исключительным чтением.

Распределение данных в модели EREWPRAM

В модели с исключительным чтением значение, записанное процессором Ph может прочитать лишь один процессор. Если просто организовать цикл поочередного чтения остальными процессорами, то получим последовательный алгоритм, нивелирующий все преимущества параллелизма. Однако если воспользоваться циклом чтение / обработка / запись на втором процессоре для записи значения в другую ячейку памяти, то на следующем шаге уже два процессора смогут прочитать это значение. Записав его затем еще в две ячейки, мы сможем воспользоваться уже четырьмя процессорами. В результате получается следующий алгоритм.

/>[1] записывает значение в ячейку М[ 1]

procLoc = 1

for j = to log p do Parallel Start

for к = procLoc + 1/02* procLoc do P[k читает M[k - procLoc]

P[k] записывает в M[k] endfor к Parallel End procLoc = procLoc * 2

end for j

Сначала алгоритм записывает значение в ячейку М. При первом проходе внешнего цикла процессор Р2 читает это значение и записывает его в М2, а переменная procLoc принимает значение 2. На втором проходе процессоры Р3 и Р4 читают содержимое ячеек М и М2 и записывают его в ячейки М3 и М, а переменная procLoc принимает значение 4. На третьем проходе процессоры с Р5 до Р$ читают содержимое ячеек с М до М4 и записывают его в ячейки с М5 до Л/8. Ясно, что (в предположении, что р является степенью двойки) на предпоследнем шаге половина процессоров прочитает нужное значение и запишет его в ячейки с М до Мр / 2, после чего оставшаяся половина процессоров сможет его прочитать. Поскольку шаги чтения и записи можно выполнять в одном цикле, как это было сделано в начале п. 9.2, параллельный блок выполняет один цикл, а внешний цикл производит log р итераций. Поэтому этот параллельный алгоритм распределения выполняет <9(log р) операций.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >