Вычислительная модель PRAM

Вычислительная модель PRAM (Parallel Random Access Machine (PRAM)) - вычислительная модель, состоящая из некоторого числа синхронизованных процессоров, имеющих доступ к общей памяти. В модели предусмотрены режимы Exclusive, когда одновременный доступ к ячейке памяти разрешается только одному процессору, и Concurrent, когда одновременный доступ к ячейке памяти разрешается нескольким процессорам. В силу этого различают следующие модели:

EREW-PRAM --- только один процессор может читать содержимое ячейки памяти и только один процессор может писать в эту ячейку.

CREW-PRAM --- произвольно много процессоров могут одновременно читать содержимое одной и той же ячейки памяти, но писать может только один.

CRCW-PRAM --- произвольно много процессоров могут одновременно читать содержимое одной и той же ячейки памяти и произвольно много процессоров могут обращаться для записи в одну и ту же ячейку памяти.

Данная модель разделяется на следующие подвиды в зависимости от способа разрешения конфликтов записи:

1) COMMON(CRCW)PRAM, в которой должны быть идентичными все значения, записываемые одновременно;

2) ARBITRARY(CRCW)PRAM, в которой срабатывает любой один из конкурирующих в записи процессоров;

3) PRIORITY(CRCW)PRAM, в которой процессоры линейно упорядочены в соответствии с их приоритетами и выбирается тот из конфликтующих, который имеет наивысший приоритет;

4) COMBINING(CRCW)PRAM, в которой записывается линейная комбинация вычисленных значений, например их сумма. Значения могут комбинироваться с помощью любой ассоциативной и коммутативной операции, которая вычислима за константное время на РАМ.

Литература

[WG'93]