Slide 26 : OT Efficiency (continued)
This slide illustrates the number of inclusion transformations required for a computer with a fan-in of f computers that have each generated and sent n operations. Therefore there are nf operations that need to be merged.
The most naive approach is to transform over all 2D faces on all hypercubes in f-dimensions, but that leads to a combinatorial explosion of transformations.
A better approach is to reduce the problem to a sequence of 2D reductions of the hypercube. However that leads to quadratic dependence on the traffic n.
CEDA uses an even better approach and is able to achieve merging with only about nf.f/2 inclusion transformations, so for a fixed and small fan-in factor f, this is within a small constant factor of the number of operations that need to be merged by that machine.
In a sense, CEDA treats the merging problem as a computational problem that is solved efficiently in a distributed manner. A large fan-in reduces the proportion of the computers that take part in the merging effort.
