Czy środowisko MapReduce jest rodzajem BSP?

11

Czy nazywanie frameworku mapReduce jest rodzajem masowego synchronicznego frameworku programowania równoległego bez przechowywania pamięci lokalnej w procesorach między synchronizacjami? Jeśli nie, to jaki model programowania równoległego najdokładniej ujmuje strukturę mapReduce?

dc.parallel-comp machine-models Jeff Kubina
źródło
1
to miłe pytanie!
Suresh Venkat
dzięki Suresh, co myślisz, zgadzasz się?
Jeff Kubina
trudny wybór najlepszej odpowiedzi, ponieważ myślę, że wszystkie pomogły mi zdobyć więcej wiedzy na temat mapreduce i tego, jak inni ją postrzegają. wybrałem odpowiedź Sasho, ponieważ doprowadziło mnie to do opracowania, które najlepiej odpowiada na moje pytanie. Dziękuję wszystkim.
Jeff Kubina

Odpowiedzi:

11

W sekcji 2 http://arxiv.org/abs/1101.1902 autorzy definiują model MapReduce, który jest celowo skonstruowany jak BSP. Dowodzą również twierdzeń symulacyjnych. Może być dobrym miejscem do rozpoczęcia.

Sasho Nikolov
źródło
5

Tak, moim zdaniem jest to, że klasyczny MapReduce jest modelem BSP (i dlatego ma swoje nieodłączne ograniczenia maksymalnej możliwej wydajności równoległej, którą można osiągnąć). Jednak nowsze prace nad MapReduce wydają się koncentrować na luźniejszych pojęciach synchronizacji, co pozwoliłoby usunąć to „uogólnione MapReduce” ze ścisłych ram BSP. W szczególności, jeśli powiela się niektóre dane, wówczas struktura synchronizacji może być rozluźniona, co powoduje wzrost wydajności.

Zobacz na przykład prace Foto Afrati i Jeffa Ullmana: Optymalizacja połączeń w środowisku zmniejszania mapy , EDBT 2010. ( preprint )

András Salamon
źródło
2

Ponieważ w MapReduce jest prosty i ustrukturyzowany wykres leżący u podstaw obliczeń, można to IMHO sklasyfikować jako model przepływu danych.

Massimo Cafaro
źródło
Zgadzam się, MapReduce ma tę samą strategię obliczeniową, co maszyna do oznaczania przepływu danych. Język Pig Yahoo buduje nawet język przepływu danych na MapReduce.
Wołowina