Monday, January 11, 2016

Improve cache performance: matrix multiplication as an example


It is surprising to see mul1() is 10 times slower than mul2().

Mul2: By using j as the inner loop, C[i][j] & B[k][j] have good cache hits, while A[i][k] is a constant during the inner loop.

Mul1: In the inner loop, C[i][j] has a constant address, and A[i][k] has good cache hits; however B[k][j] is doomed to cache misses.

There are other methods to optimize matrix multiplication, but this one should be the most significant.


reference slide: https://www.cs.duke.edu/courses/fall06/cps220/lectures/PPT/lect12.pdf

 #include <iostream>  
 #include <stdlib.h>  
 #include <time.h>  
 using namespace std;  
 const int N = 2000;  
 double A[N][N], B[N][N], C[N][N];  
 void fill()  
 {  
  for (int i=0; i<N; i++)  
   for (int j=0; j<N; j++) {  
    A[i][j] = (double)rand() / RAND_MAX;  
    C[i][j] = 0;  
   }  
 }  
 void mul1()  
 {  
  for (int i=0; i<N; i++)   
   for (int j=0; j<N; j++)  
    for (int k=0; k<N; k++)  
      C[i][j] += A[i][k] * B[k][j];  
 }  
 void mul2()  
 {  
  for (int i=0; i<N; i++)  
   for (int k=0; k<N; k++)  
    for (int j=0; j<N; j++)  
      C[i][j] += A[i][k] * B[k][j];  
 }  
 int main()  
 {  
  fill();  
  clock_t startTime;  
  startTime = clock();  
  mul1();  
  cout << (clock() - startTime)/(double) CLOCKS_PER_SEC << endl;  
  startTime = clock();  
  mul2();  
  cout << (clock() - startTime)/(double) CLOCKS_PER_SEC << endl;  
  return 0;  
 }  
 /*  
 > g++ mul.cpp -O2  
 > a.exe  
 87.64  
 7.584  
 */  

11 comments:

  1. Great Job.!! I really gained more knowledge by reading your unique post. Thanks a lot for offering this content for our vision.

    SAS Training in Chennai

    ReplyDelete
  2. Very interesting to read, thanks for sharing that wonderful useful information, given programming coding was very excellent and easily observe all provided information.


    SEO Training in Chennai

    ReplyDelete
  3. Wow amazing i saw the article with execution models you had posted. It was such informative. Really its a wonderful article. Thank you for sharing and please keep update like this type of article because i want to learn more relevant to this topic.

    Dotnet Training in Chennai

    ReplyDelete
  4. I have definitely picked up anything new from right here. I did however expertise a few technical points using this site, since I experienced to reload the web site a lot of times previous to I could get it to load correctly.

    Online Training in Chennai

    ReplyDelete
  5. It is really very excellent,I find all articles was amazing.Awesome way to get exert tips from everyone,not only i like that post all peoples like that post.Because of all given information was wonderful and it's very helpful for me.

    PPC Services in Chennai

    ReplyDelete
  6. Wow amazing i saw the article with execution models you had posted. It was such informative. Really its a wonderful article. Thank you for sharing and please keep update like this type of article because i want to learn more relevant to this topic.

    Digital Marketing For Small Business in Chennai

    ReplyDelete
  7. this is really too useful and have more ideas from yours. keep sharing many techniques. eagerly waiting for your new blog and useful information. keep doing more.

    Java Training in Chennai

    ReplyDelete
  8. thus your information are really nice and very much implementive and useful too. it is really awesome and very much exclusive too.Thanks for sharing those valuable information.

    Informatica Training in Chennai

    ReplyDelete
  9. This post is really nice and informative. The explanation given is really comprehensive and informative..
    PHP Training in Chennai

    ReplyDelete
  10. Learning new technolgy would help oneself at hard part of their career. And staying updated is the only way to survive in current position. Your content tells the same. Thanks for sharing this information in here. Keep blogging like this. Android App Development Company in Chennai

    ReplyDelete
  11. Thank you for sharing such a nice and interesting blog with us. I have seen that all will say the same thing repeatedly. But in your blog, I had a chance to get some useful and unique information. I would like to suggest your blog in my dude circle.
    Isoft Innovations Company Address
    Isoft Innovations Adyar
    Isoft Innovations Reviews
    Isoft Innovation Chennai
    Isoft Innovation

    ReplyDelete