Введение
Абстрактный компьютер для разработки параллельных алгоритмов
В информатике параллельная машина с произвольным доступом к памяти (параллельная ОП или PRAM) является абстрактной машиной с общей памятью. Как следует из названия, PRAM предназначена как параллельная вычислительная аналогия машине с произвольным доступом к памяти (RAM) (не следует путать с памятью с произвольным доступом). Подобно тому, как RAM используется разработчиками последовательных алгоритмов для моделирования производительности алгоритмов (например, временной сложности), PRAM используется разработчиками параллельных алгоритмов для моделирования производительности параллельных алгоритмов (например, временной сложности, при этом обычно также указывается предполагаемое количество процессоров). Аналогично тому, как модель RAM не учитывает практические вопросы, такие как время доступа к кэш-памяти по сравнению с основной памятью, модель PRAM не учитывает такие вопросы, как синхронизация и связь, но предоставляет любое (зависящее от размера задачи) количество процессоров. Стоимость алгоритма, например, оценивается с использованием двух параметров: O(время) и O(время × количество процессоров).
Реализация
Алгоритмы PRAM не могут быть параллелизованы при использовании комбинации центрального процессора и динамической памяти с произвольным доступом (DRAM), поскольку DRAM не допускает одновременного доступа к одному банку (даже к разным адресам в этом банке). Однако их можно реализовать аппаратно или читать/записывать во внутренние блоки статической памяти с произвольным доступом (SRAM) в программируемой пользователем вентильной матрице (FPGA) с использованием алгоритма CRCW. Тем не менее, проверка практической значимости алгоритмов PRAM (или RAM) зависит от того, обеспечивает ли их модель стоимости эффективную абстракцию для какого-либо компьютера; структура этого компьютера может существенно отличаться от абстрактной модели. Знание слоев программного и аппаратного обеспечения, которые необходимо внедрить, выходит за рамки данной статьи. Однако, в статьях, таких как [название статьи], показано, как абстракция типа PRAM может быть поддержана парадигмой явной многопоточности (XMT), а в статьях, таких как [название статьи], продемонстрировано, что алгоритм PRAM для задачи о максимальном потоке может обеспечить значительное ускорение по сравнению с самым быстрым последовательным алгоритмом для той же задачи. В статье [название статьи] было показано, что алгоритмы PRAM могут достигать конкурентоспособной производительности даже без дополнительных усилий по преобразованию их в многопоточные программы для XMT.