Вычислительная модель PRAM: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
Строка 1: Строка 1:
'''Вычислительная модель PRAM''' (''[[Parallel Random Access Machine (PRAM)]]'') -
'''Вычислительная модель PRAM''' (''[[Parallel Random Access Machine (PRAM)]]'')
вычислительная модель, состоящая из некоторого числа синхронизованных
вычислительная модель, состоящая из некоторого числа синхронизованных
процессоров, имеющих доступ к общей памяти. В модели предусмотрены
процессоров, имеющих доступ к общей памяти. В модели предусмотрены
Строка 7: Строка 7:
процессорам. В силу этого различают следующие модели:
процессорам. В силу этого различают следующие модели:


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




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


CRCW-PRAM --- произвольно много процессоров могут одновременно читать
CRCW-PRAM произвольно много процессоров могут одновременно читать
содержимое одной и той же ячейки памяти и произвольно много
содержимое одной и той же ячейки памяти и произвольно много
процессоров могут обращаться для записи в одну и ту же ячейку памяти.
процессоров могут обращаться для записи в одну и ту же ячейку памяти.
Строка 37: Строка 37:
операции, которая вычислима за константное время на ''РАМ''.
операции, которая вычислима за константное время на ''РАМ''.
==Литература==
==Литература==
[WG'93]
* Workshop. Utrecht, 1993 // Lect. Notes Comp. Sci., 1994, vol. 790.

Текущая версия от 12:33, 2 декабря 2010

Вычислительная модель 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, в которой записывается линейная комбинация вычисленных значений, например их сумма. Значения могут комбинироваться с помощью любой ассоциативной и коммутативной операции, которая вычислима за константное время на РАМ.

Литература

  • Workshop. Utrecht, 1993 // Lect. Notes Comp. Sci., 1994, vol. 790.