Abstract-Vi anser att problemet med att beräkna en matrisvektor produkt Ax med hjälp av en uppsättning P parallella eller distribuerade processnoder benägna att "straggling", dvs oförutsägbara förseningar. Varje processnod kan endast komma åt ett bråk (s/N) av N-längdvektorn x, och alla processnoder beräknar ett lika stort antal punktprodukter. Vi föreslår en ny felkorrigering kod-som vi kallar "Short-Dot"-som introducerar redundanta, kortare punkt produkter så att endast en delmängd av nodernas utgångar är tillräckliga för att beräkna Ax. För att ta itu med problemet med strypning i dator matris-vektor produkter, använder tidigare arbete replikering eller radering kodning för att koda delar av matrisen A, men längden på de punktprodukter som beräknas vid varje bearbetning nod är fortfarande N. Den viktigaste nyheten i vårt arbete är att i stället för att beräkna de långa punkt produkter som krävs i den ursprungliga matris-vektor produkt, vi konstruera ett större antal redundanta och korta punkt produkter som bara kräver en bråkdel av x för att nås under beräkningen. Short-Dot är därför användbart i ett kommunikations-konstruerat scenario eftersom det gör det möjligt för endast en bråkdel av x att nås av varje process nod. Dessutom visar vi att i det särskilda systemet där antalet tillgängliga processnoder är större än det totala antalet punktprodukter, Short-Dot har lägre förväntad beräkningstid under stregling under en exponentiell modell jämfört med befintliga strategier, t.ex. Replikering, i skalande bemärkelse. Vi har också grundläggande gränser för avvägningen mellan punktprodukternas längd och återvinningströskeln, dvs. det antal processnoder som krävs, vilket visar att Short-Dot är nästan optimalt.
Författare i REF föreslår en teknik som kallas kort punkt som gör det möjligt för enskilda arbetarnoder att utföra ett stort antal av de mer effektiva korta produkter samtidigt som endast kräver en delmängd av dem vid fusionsnoden för att avkoda/återfinna den sista långa pricken produkten, medan något kompromissande straggler tolerans.
“Short-Dot”: Computing Large Linear Transforms Distributedly Using Coded Short Dot Products
{'venue': 'IEEE Transactions on Information Theory', 'journal': 'IEEE Transactions on Information Theory', 'mag_field_of_study': ['Mathematics', 'Computer Science']}