Coded computation for multicore setups

摘要: Consider a distributed computing setup consisting of master node and n worker nodes, each equipped with p cores, function f (x) = g(f 1 (x), 2 (x),…, fk(x)), where i can be computed independently the rest. Assuming that computational times have exponential tails, what is minimum possible time for f? Can we use coding theory principles to speed up this computation? In [1], it shown linear functions expedited by applying erasure codes. However, not clear if codes computation ‘nonlinear’ as well. To resolve problem, propose sparse codes, exploiting modern multicore processing architecture. We show 1) our solution achieves order optimal runtime, 2) at least Θ(√log n) faster than any uncoded schemes number workers n.