Abstract-In storskaliga distribuerade datorkluster, såsom Amazon EC2, det finns flera typer av "systembuller" som kan resultera i betydande försämring av prestanda: systemfel, flaskhalsar på grund av begränsad kommunikationsbandbredd, latens på grund av straggler noder, och så vidare. Det har nyligen gjorts resultat som visar effekterna av kodning för ett effektivt utnyttjande av beräknings- och lagrings redundans för att lindra effekten av flaskhalsar i stragglers och kommunikation i homogena kluster. I detta dokument fokuserar vi på allmänna heterogena distribuerade datorkluster som består av en mängd olika datormaskiner med olika kapacitet. Vi föreslår en kodningsram för att påskynda distribuerad databehandling i heterogena kluster genom att handla med redundans för att minska beräkningslatensen. I synnerhet föreslår vi heterogen kodad matris multiplikation (HCMM) algoritm för att utföra distribuerad matris multiplikation över heterogena kluster som är bevisligen asymptotiskt optimala för en bred klass av processtidsfördelningar. Dessutom visar vi att HCMM är obundet snabbare än något okodat system som delar upp den totala arbetsbördan bland arbetstagarna. För att visa hur det föreslagna HCMM-systemet kan tillämpas i praktiken, ger vi resultat från numeriska studier och Amazon EC2-experiment som jämför HCMM med tre referenssystem för lastfördelning – enhetliga okodade, lastbalanserade okodade och enhetliga kodade. I våra numeriska studier uppnår HCMM i synnerhet en hastighetsökning på upp till 73 %, 56 % respektive 42 % jämfört med de tre referenssystem som nämndes tidigare. Dessutom utför vi experiment över Amazon EC2 kluster och visar hur HCMM kan kombineras med hastighetslösa koder med nästan linjär avkodning komplexitet. I synnerhet visar vi att HCMM i kombination med Lubytransform-koderna avsevärt kan minska den totala verkställighetstiden. HCMM anses vara upp till 61 %, 46 % respektive 36 % snabbare än de tre ovannämnda referenssystemen. Dessutom ger vi en generalisering av problemet med optimal lastfördelning i heterogena miljöer, där vi tar hänsyn till de monetära kostnaderna i samband med distribuerade datorkluster. Vi hävdar att HCMM är asymptotiskt optimalt även för budgetkonstruerade scenarier. I synnerhet karakteriserar vi minsta möjliga förväntade A. Reisizadeh och R. Pedarsani är med Institutionen för el- och datateknik, University of California i Santa Barbara, Santa Barbara, CA 93106 USA (e-post: reisizadeh@ucsb.edu; ramtin@ece.ucsb.edu). S. kostnad i samband med en beräkning uppgift över en given kluster av maskiner. Dessutom utvecklar vi en heuristisk algoritm för (HCMM) belastningstilldelning för distribuerat genomförande av budgetbegränsade beräkningsuppgifter.
Upphovsmän till REF föreslår en kodningsram för att påskynda distribuerade datorer med heterogena kluster i molnet som innehåller strypande servrar.
Coded Computation Over Heterogeneous Clusters
{'venue': 'IEEE Transactions on Information Theory', 'journal': 'IEEE Transactions on Information Theory', 'mag_field_of_study': ['Computer Science']}