🔒 Locked

Optimizing

Started by peter86 Jan 5, 2003 at 10:50 AM 9 replies 350+ views

Original Post

Jan 5, 2003 at 10:50 AM

Can this matrix multiplication algorithm really be optimized? If yes, then how?

  
  m_iWidth = A.GetWidth();
  m_iHeight = B.GetHeight();

  // for each row in the new matrix

  for (int x = 0; x < m_iWidth; x++) {
    // for each column in the new matrix

    for (int y = 0; y < m_iHeight; y++) {
      // our "answer" for this element is initially 0

      double f = 0;
      // loop through the rows and columns (the sigma of the equation)

      for (int k=0; k < B.GetWidth(); k++) {
        // add to our answer the product of A''s row and B''s column

        f += A.GetAt(k,x) * B.GetAt(y,k);
      }
      // our answer for this element is the sum.

      SetAt(x,y,(float)f);
    }
  }

thedo

Jan 5, 2003 at 10:56 AM

quote:

double f = 0;
(float)f

Seems pretty poor to me.

Also I hope the Get/Set methods are inline

Neil

WHATCHA GONNA DO WHEN THE LARGEST ARMS IN THE WORLD RUN WILD ON YOU?!?!

Ready4Dis

Jan 5, 2003 at 11:03 AM

This might speed it up a VERY little.

  
float f;
m_iWidth = A.GetWidth();
m_iHeight = A.GetHeight();
m_iWidthB = B.GetWidth();
for (int x= 0; x != m_iWidth; ++x)
 for (int y = 0; y != m_iHeight; ++y)
 {
  f=0;
  for (int k =0; k != m_iWidthB; ++k)
  {
   f+= A.GetAt(k,x) * B.GetAt(y,k);
  }
  SetAt(x,y,(float)f);
 }

MindCode

Jan 5, 2003 at 11:04 AM

You could "unroll" the loop. However you might just leave it as it is and tell the compile to unroll it for you. That is if your using an optimizing compiler (gcc has this unroll feature).

peter86

Author

peter86

Jan 5, 2003 at 11:11 AM

quote:
Original post by MindCode
You could "unroll" the loop. However you might just leave it as it is and tell the compile to unroll it for you. That is if your using an optimizing compiler (gcc has this unroll feature).

How does "unrolling" work then?

civguy

Jan 5, 2003 at 11:26 AM

quote:
Original post by MindCode
However you might just leave it as it is and tell the compile to unroll it for you. That is if your using an optimizing compiler (gcc has this unroll feature).

But since B.GetWidth() doesn''t return a constant, gcc can''t possibly unroll that loop.

For more info about loop unrolling, use google.

walkingcarcass

Jan 5, 2003 at 11:29 AM

i would write special-case code if you are expecting certain matrix sizes (eg if 4x3 is used 70% of the time)

with superscalar processors, such math-intensive code can be almost doubled in speed if re-written in crafty assembly. use fxchg (a zero-cost instruction) to do math on other values while waiting for the first to finish. some math operations can be done in paralell.

********

A Problem Worthy of Attack
Proves It''s Worth by Fighting Back

Jan Wassenberg

105

Jan Wassenberg

Jan 5, 2003 at 1:26 PM

Using the 4 Russians'' algorithm (boolean matrices, O(n^3 / log n)) or Strassen''s (O(n^2.7); newer research algos have large constant factors, but a smaller exponent) nets you asymptotic speed gains.

Why is matrix multiplication a bottleneck? If you can, let your 3d API do it; if they''re big, there are better ways than the standard O(n^3) method

quote:
i would write special-case code if you are expecting certain matrix sizes (eg if 4x3 is used 70% of the time)

Amen.

quote:
with superscalar processors, such math-intensive code can be almost doubled in speed if re-written in crafty assembly.

In fact, you can do significantly better with your favorite SIMD instruction set (google for SSE, 3DNow!). Hard data: 3DNow: 16 clocks, SSE: 20 clocks, C++: 100 clocks (4x4 matrix; from Hugi 25).

quote:
use fxchg (a zero-cost instruction) to do math on other values while waiting for the first to finish. some math operations can be done in paralell.

This is getting pretty low level - you should be fairly good before you try writing / scheduling your own asm code (and expecting it to be faster

).

If you want to speed up your code a bit, use pointers to eliminate the multiplies in GetAt / SetAt.

Hairybudda

Jan 5, 2003 at 3:11 PM

quote:
Original post by MindCode
You could "unroll" the loop. However you might just leave it as it is and tell the compile to unroll it for you. That is if your using an optimizing compiler (gcc has this unroll feature).

It depends how far you unroll it, if you unroll it too large, theres a chance that the function wont fit in the cache, thus reducing its performance.

djsteffey

165

djsteffey

Jan 5, 2003 at 3:17 PM

you cant unroll that loop since the number of times to loop are not constant and are determined at run time.

"I pity the fool, thug, or soul who tries to take over the world, then goes home crying to his momma."
- Mr. T

Alan Kemp

Jan 5, 2003 at 4:28 PM

quote:
Original post by ncsu121978
you cant unroll that loop since the number of times to loop are not constant and are determined at run time.

Not strictly true. You could probably come up with something that would leave software purists blind if you used a form of Duff''s Device for the inner loop at least (and ommiting the while, just using it to compensate for now knowing how many columns there were going to be).

Alan

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.