Crossed Cubes

Matrix x Matrix

Crossed-cube and hypercube computation schedules

Matrix computation views only. This matrix-matrix page shows the exact per-cycle schedule derived from the computation model. Use the schedule selector to compare the non-pipelined baseline with the pipelined extension.
CQ Matrix x MatrixExact model cycle -1Idle / pre-startr0r1r2r3c0c1c2c30000000100110010010001010111011011001101111111101000100110111010
Q Matrix x MatrixExact model cycle -1Idle / pre-startr0r1r2r3c0c1c2c30000000100110010010001010111011011001101111111101000100110111010

Timings

MM schedule = non-pipelined row schedule CQ row broadcast depth = 2 CQ column broadcast depth = 2 CQ stages = 4 CQ overall completion = 20 Q row broadcast depth = 3 Q column broadcast depth = 3 Q stages = 4 Q overall completion = 28

Speedup

CQ vs Q Running TimesDimensions 4 through 20, using the row-broadcast and column-reduce trees of our algorithm.Vector x Matrix Overall Time0612182546810121416182056678991110131115121713191421CQQMatrix x Matrix Overall Time05500110001650022000468101214161820202448561281442883526408321408192030724352665697281433621504CQQ