Является ли инфраструктура MapReduce типом BSP?

11

Правильно ли называть инфраструктуру mapReduce типом структуры объемного синхронного параллельного программирования без сохранения локальной памяти в процессорах между синхронизациями? Если нет, то какая модель параллельного программирования наиболее точно инкапсулирует каркас mapReduce?

Джефф Кубина
источник
1
это хороший вопрос!
Суреш Венкат
спасибо Суреш, что ты думаешь, согласен?
Джефф Кубина
Тяжелый выбор при выборе лучшего ответа, так как я думаю, что все они помогли мне получить больше знаний о mapreduce и о том, как его видят другие Я выбрал ответ Сашо, так как он привел меня к статье, в которой мой вопрос является лучшим. всем спасибо.
Джефф Кубина

Ответы:

11

В разделе 2 http://arxiv.org/abs/1101.1902 авторы определяют модель MapReduce, которая намеренно структурирована как BSP. Они также доказывают теоремы моделирования. Может быть, хорошее место для начала.

Сашо Николов
источник
5

Да, я считаю, что классический MapReduce - это модель BSP (и, следовательно, имеет свои ограничения на максимально возможную параллельную производительность, которая может быть достигнута). Тем не менее, новая работа над MapReduce, кажется, сосредоточена на более слабых понятиях синхронизации, что вывело бы этот «обобщенный MapReduce» из строгой структуры BSP. В частности, если реплицировать некоторые данные, структура синхронизации может быть ослаблена, что приведет к повышению производительности.

См., Например, работу Foto Afrati и Джеффа Уллмана: Оптимизация объединений в среде сокращения карт , EDBT 2010. ( препринт )

Андраш Саламон
источник
2

Поскольку в MapReduce существует простой и структурированный граф, лежащий в основе вычислений, это может быть ИМХО классифицировано как модель потока данных.

Массимо Кафаро
источник
Я согласен, MapReduce имеет ту же вычислительную стратегию, что и машина с теговыми данными. Язык Pig от Yahoo даже создает язык потоков данных поверх MapReduce.
говядина