Matrix Multiplication

This is a discussion on Matrix Multiplication within the C Programming forums, part of the General Programming Boards category; I'm writting some functions that need to multiply large matrices together. This is what I have so far for it. ...

  1. #1
    Registered User
    Join Date
    Oct 2002
    Posts
    27

    Matrix Multiplication

    I'm writting some functions that need to multiply large matrices together. This is what I have so far for it. It works fine, but it runs to slow. I need to run this function a lot so it needs to run fast. What could I do to the following code to make it run faster, other than loop unrolling, cause I know how to do that I just didn't want to type it all out here.




    Code:
    void mm(void)
    {
    
            int i,j,k;
            unsigned long sum;
    
    	
            /* Multiply the two arrays and store the result in a third array  */
            for ( j=0; j<512; j++)
                    for ( i=0; i<512; i++)
                    {
                            sum = 0;
                            for ( k=0; k<128; k++ )
                                    sum += ARRAY_4A[i][k] * ARRAY_4B[k][j];
                            ARRAY_RES[i][j] = sum;
                    } 
    	
    }

  2. #2
    Registered User
    Join Date
    Oct 2002
    Posts
    27
    I'm using gcc and running on linux. pentium III

  3. #3
    Registered User
    Join Date
    Oct 2002
    Posts
    27
    thanks for your response.
    I was able to reduce the operation time to about 10% of the original time by manualy unrolling the loops in steps of three for the middle loop and steps of 16 for the inner loop. I also set gcc to optimization level 3, but I haven't tried just using fun loops yet( I don't know gcc that well).

    I know of another algothrim (strasson or something like that), that is suppose to be really fast, but I don't know how to implement it.

    There are also a few different way to format the loop that will make have less cache misses, but you have to do another store instuction in the inner loop, depending on the machine this can make it faster or slower. I did some simple test and found that it seems to make it faster for the pentium III.

    Code:
    for(i = 0; i<512; i++){
    
         for(k = 0; k<512; k++){
    
              r = a[i][k];
    
              for(j = 0; j<512; j++)
    
                   c[i][j] += r * b[k][j];
    
         }
    }
    Last edited by samps005; 12-04-2002 at 08:39 PM.

  4. #4
    Visionary Philosopher Sayeh's Avatar
    Join Date
    Aug 2002
    Posts
    212
    do a search on the web for c programming gems or algorithms... this has already been done and reduced for graphics work...
    It is not the spoon that bends, it is you who bends around the spoon.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C - access violation
    By uber in forum C Programming
    Replies: 2
    Last Post: 07-08-2009, 01:30 PM
  2. *operator overloading: scalar matrix multiplication
    By gemini_shooter in forum C++ Programming
    Replies: 4
    Last Post: 06-08-2009, 01:14 PM
  3. Matrix Multiplication ( Accessing data from a file ) HELP
    By six_degreez in forum C Programming
    Replies: 2
    Last Post: 07-24-2008, 05:21 PM
  4. Matrix Help
    By HelpmeMark in forum C++ Programming
    Replies: 27
    Last Post: 03-06-2008, 04:57 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21