• Vi föreslår modeller för att samtidigt schemalägga karta och minska uppgifter i en MapReduce jobb. • Våra modeller utnyttjar mönstret i relationen mellan kartare och reducerare. • En två-konstraint formulering balanserar processorers belastningar i både karta och minska faser. • Våra modeller förbättrar parallella körtider för två nyckeloperationer inom MapReduce.  a r t i c l e i n f o Schemaläggning av uppgifter för MapReduce-jobb har varit ett aktivt forskningsområde i syfte att minska mängden data som överförs under shuffle-fasen genom att utnyttja datalokaliseringen. I litteraturen beaktas i allmänhet endast schemaläggningen av minskade uppgifter med antagandet att schemaläggningen av kartuppgifter redan bestäms av indataplaceringen. I moln- eller HPC-utplaceringar av MapReduce är dock inmatningsdata placerade i en fjärrlagring och schemaläggning kartuppgifter blir viktigt. Här föreslår vi modeller för samtidig schemaläggning av kartor och minskning av uppgifter för att förbättra datalokaliseringen och balansera processorns laster i både kart och minska faser. Vårt tillvägagångssätt är baserat på graf- och hypergrafmodeller som korrekt kodar för samspelet mellan kartan och minskar uppgifter. Partitioner som produceras av dessa modeller avkodas för att schemalägga karta och minska uppgifter. En tvåkonstraint formulering som används i dessa modeller möjliggör balansering processorer laster i både karta och minska faser. Partitioneringsmålet i hypergrafmodellerna inkapslar korrekt minimeringen av dataöverföringen när ett lokalt kombinationssteg utförs före shuffle, medan partitioneringsmålet i grafmodellerna uppnår samma bedrift när en lokal kombination inte utförs. Vi visar giltigheten av vår schemaläggning på MapReduce parallelliseringar av två viktiga kärnoperationer -sparse matrisvektorn multiplikation (SpMV) och generaliserade sparse matris-matris multiplikation (SpGEMM) -som är allmänt förekommande i big data analytics och vetenskapliga beräkningar. Jämfört med slumpmässig schemaläggning, våra modeller leder till enorma besparingar i dataöverföring genom att minska datatrafiken från flera hundratals megabyte till bara några megabyte i shuffle-fasen och därmed leda upp till 2,6x och 4,2x speedup för SpMV respektive SpGEMM, respektive.
Som exempel föreslogs en offline schemaläggningsalgoritm baserad på grafmodeller av Selvitopi et al. REF, som korrekt kodar interaktioner mellan karta och minska uppgifter.
Locality-aware and load-balanced static task scheduling for MapReduce
{'venue': 'Future Gener. Comput. Syst.', 'journal': 'Future Gener. Comput. Syst.', 'mag_field_of_study': ['Computer Science']}