Strassen algorithm in vhdl

hi all
I am currently struggling trying to write Strassens Algorithm for
matrix multiplication in VHDL. I have written the code for 2x2
matrices, but now have to develop it to implement 4x4 matrices or
larger.
Can anyone help please.
Thank You

 

[RCIngham]

hi all
I am currently struggling trying to write Strassens Algorithm for
matrix multiplication in VHDL. I have written the code for 2x2
matrices, but now have to develop it to implement 4x4 matrices or
larger.
Can anyone help please.
Thank You

Unless you have reached the limit of on-FPGA multipliers, the extra contro
complexity makes such an algorithm unattractive for real-worl
applications.

Is this an educational assignment?


---------------------------------------
Posted through http://www.FPGARelated.com

 

[Tim Wescott]

On Sun, 26 Feb 2012 09:28:49 -0800, rsr1991 wrote:

hi all
I am currently struggling trying to write Strassens Algorithm for matrix
multiplication in VHDL. I have written the code for 2x2 matrices, but
now have to develop it to implement 4x4 matrices or larger.
Can anyone help please.
Thank You

Why don't you do a practical implementation of Strassen's Algorithm, per
the Wikipedia page:

"Practical implementations of Strassen's algorithm switch to standard
methods of matrix multiplication for small enough submatrices, for which
those algorithms are more efficient. The particular crossover point for
which Strassen's algorithm is more efficient depends on the specific
implementation and hardware."

My feeling on this is that you are only going to benefit from this
algorithm if you have a pretty darn big matrix (32 by 32 is probably
still "small"), a processor for which addition, subtraction, _and general-
purpose ALU_ instructions are significantly cheaper than multiplication,
and either a lot of engineering time to spend freely, or a desperate need
to cut just a little bit (less than 14%) off of the time to do a matrix
multiply.

Note that you are replacing eight (matrix) multiplies and four additions
with seven multiplies -- and _eight_ additions or subtractions. On a
processor, with IEEE floating point, I'm not sure that Strassen's
Algorithm wouldn't take _more_ computational resources to complete that a
bog-standard matrix multiply.

I could see incorporating this (or one of the more optimal algorithms)
into a general-purpose math package (if it actually worked), but the
notion of going to so much trouble for so little gain kind of boggles my
mind -- wouldn't you get more speedup by hand-flogging your timing, and
increasing your clock rate a bit, or otherwise tuning the rest of your
algorithm?

--
My liberal friends think I'm a conservative kook.
My conservative friends think I'm a liberal kook.
Why am I not happy that they have found common ground?

Tim Wescott, Communications, Control, Circuits & Software
http://www.wescottdesign.com