3 ms·
Another approach is to start with the obvious 3 nested loops. Then replace with a single loop of n3 iterations. Take the bits of this single loop variable and d
by phkahler 9y ago
Another approach is to start with the obvious 3 nested loops. Then replace with a single loop of n3 iterations. Take the bits of this single loop variable and deinterleave them to obtain the 3 indicies of the nested loop variant. In other words treat the loop counter as if it's bits are a3b3c3a2b2c2a1b1c1a0b0c0 and so on. This is simpler with 2 interleaved values but still not bad. It produces a sort of 3 dimensional z-order traversal. The overhead can be minimized by looping with a stride of some power of 2 and unrolling the inner portion to do that many multiply-accumulates.
If you do this while also storing the matrix in z-order in memory the offsets in the unrolled part become constants independent of the matrix size.
This technique is applicable to anything using nested loops where the indicies take you to a lot of memory repeatedly.
I'm still waiting for a couple with bit interleave and deinterleave instructions, but those wouldn't be usable without intrinsics.