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  
 */  

22 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
  12. Wonderful bloggers like yourself who would positively reply encouraged me to be more open and engaging in commenting. So know it's helpful..

    Informatica Training in Chennai

    Dataware Housing Training in Chennai

    ReplyDelete
  13. Here i had read the content you had posted. It is much interesting so please keep update like this. Infact it will be useful for the beginners to develop their knowledge along with . I am expecting much more posts from you

    Painless Dental Treatment In Chennai

    Best Dental Clinic In Adyar

    ReplyDelete
  14. Great site for these post and i am seeing the most of contents have useful for my Carrier.Thanks to such a useful information.Any information are commands like to share him.
    Security Services in Chennai

    ReplyDelete
  15. Great Article… I love to read your articles because your writing style is too good, its is very very helpful for all of us and I never get bored while reading your article because, they are becomes a more and more interesting from the starting lines until the end.

    Digital Marketing Company in Chennai

    ReplyDelete
  16. I am not sure the place you are getting your information, however good topic.I needs to spend some time studying more or understanding more.Thank you for wonderful information I was in search of this info for my mission.

    HR Consultancy in Chennai
    Recruitment Consultancy in Chennai
    Manpower Consultancy in Chennai

    ReplyDelete
  17. What you have written in this post is exactly what I have experience when I first started my blog.I’m happy that I came across with your site this article is on point,thanks again and have a great day.Keep update more information.
    Architectural Firms in Chennai
    Architects in Chennai

    ReplyDelete
  18. This is very valuable for multiple peoples.Nice it. We'll have to share it marvelous posting.I like that your reasonable helpful article.I read all your blog is reduced excellent blogger discussing.
    Digital Marketing Training in Chennai
    Digital Marketing Course in Chennai

    ReplyDelete

  19. You have provided an nice article, Thank you very much for this one. And i hope this will be useful for many people.. and i am waiting for your next post keep on updating these kinds of knowledgeable things...

    Android App Development Company

    ReplyDelete
  20. Being new to the blogging world I feel like there is still so much to learn. Your tips helped to clarify a few things for me as well iOS App Development Company
    iOS App Development Company

    ReplyDelete
  21. Nice it seems to be good post... It will get readers engagement on the article since readers engagement plays an vital role in every blog.. i am expecting more updated posts from your hands.
    Fitness SMS
    Fitness Text
    Salon SMS
    Salon Text
    Investor Relation SMS
    Investor Relation Text
    Mobile Marketing Services
    mobile marketing companies
    Sms API

    ReplyDelete