Sedan den infördes 2004 har MapReduce-ramverket blivit en av standardmetoderna i massivt distribuerad och parallell beräkning. I motsats till dess intensiva användning i praktiken är den teoretiska grunden fortfarande begränsad och endast lite arbete har ännu gjorts för att sätta MapReduce på samma nivå som de stora beräkningsmodellerna. Efter pionjärarbete som relaterar MapReduce ramverket med PRAM och BSP i sin makroskopiska struktur fokuserar vi på funktionaliteten som tillhandahålls av själva ramverket, som beaktas i den parallella externa minnesmodellen (PEM). I detta presenterar vi övre och nedre gränser på den parallella I/O-komplexitet som matchar upp till konstanta faktorer för shuffle steg. Blandningssteget är den enda kommunikationsfasen där all information om en MapReduce-anrop överförs från kartarbetare för att minska antalet arbetstagare. Därför flyttar vi fokus mot det interna kommunikationssteget i motsats till tidigare arbete. Resultaten vi får vidare överföra till BSP * modellen. Å ena sidan visar detta hur mycket komplexitet som kan "dolas" för en algoritm som uttrycks i MapReduce jämfört med PEM. Å andra sidan band våra resultat den värsta prestandaförlusten i MapReduce-metoden när det gäller I/O-effektivitet.
Teoretiskt övervägande gavs i REF, där författarna presenterar övre och nedre gränser på den parallella I/O komplexiteten i shuffle-fasen.
The Efficiency of MapReduce in Parallel External Memory
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}