Массивно-параллельные вычисления ⇐ Васина Википедия

[wiki_en]

При изучении параллельных алгоритмов модель «массово-параллельных вычислений» или «модель MPC» представляет собой теоретическую модель вычислений, задуманную как абстракцию для параллельных вычислительных систем, которые используют такие среды, как MapReduce, и часто применяется к алгоритмическим задачам теории графов.
В этой модели дана система, состоящая из машин M, каждая из которых имеет локальную память, состоящую из слов памяти S. Входные данные для вычислительной задачи в этой модели распределяются произвольно по всем машинам и предполагается, что их размер N не более чем пропорционален MS. Обычно предполагается, что S=N^{1-\varepsilon для некоторого параметра \varepsilon>0, так что каждая машина может видеть только небольшую часть входных данных. и для решения данной задачи потребуется некоторый нетривиальный уровень параллелизма.
При такой настройке вычисления выполняются в последовательность раундов. В каждом раунде каждая машина выполняет некоторые локальные вычисления с информацией, хранящейся в ее памяти, а затем обменивается сообщениями с другими машинами. Общий объем информации, отправленный или полученный одной машиной за один раунд связи, должен составлять O(S). Целью разработки алгоритмов для этой модели является достижение очень малого количества раундов, например, постоянного числа или числа, логарифмического по размеру входных данных.
Первоначальная версия этой модели была представлена ​​под названием MapReduce в статье 2010 года Говарда Карлоффа, Сиддхарта Сури и Сергея Васильвицкого.





Модели вычислений
Анализ параллельных алгоритмов

Подробнее: https://en.wikipedia.org/wiki/Massively ... omputation