To take advantage of the blocking algorithm, matrix
multiplication is implemented using Fast Fourier Transforms (FFT).
The optimized FFT routine executes a length 512 FFT in
approximately 7200 cycles. I am using a property of the FFT to do
two real valued FFTs in one FFT operation (with some overhead). The
number of FFTs per block is 
where M is
the number of microphones. The block size is length 256. So for a
sample rate of 8khz, the total computation for the FFT code alone
is approximately
or about 12 million
cycles for 8 microphones. At first this seems pretty good. But
after you consider the matrix inverse update code, the FFT
overhead, and correcting the filter output, it turns out to be more
than 5 or 6 times as much computation. And this doesn't even
include beamforming.
Ok, so it still runs in under 150 million cycles, right? Not quite. The memory requirements exceed the 64k on the processor. And even the L2 cache runs considerably slower than the L1 cache. At a minimum we need to try to keep memory in the L2 cache as much as possible. Unfortunately, the algorithm runs through more than 64k of memory 8000 times a second. So just using cache may not be very efficient. Another solution is to use memory overlays. This gives the programmer more control over where the memory is at all times. And this is what I'm currently working on.