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

80 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. 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
  5. 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
  6. 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
  7. 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
  8. Great effort! You have given an informative news about cache performance. Thanks for sharing this useful details with us.

    ReplyDelete
  9. I am really enjoying reading your well written articles. It looks like you spend a lot of effort and time on your blog. I have bookmarked it and I am looking forward to reading new articles. Keep up the good work..
    Logistic ERP
    CCTV Camera Dealers in Chennai
    Transport ERP
    Athletic Management Software
    CCTV Camera Installation in Chennai

    ReplyDelete
  10. Fertility is the natural capability to produce offspring. As a measure, fertility rate is the number of offspring born per mating pair, individual or population.Human fertility depends on factors of nutrition, sexual behavior, consanguinity, culture, instinct, endocrinology, timing, economics, way of life, and emotions.Greate thinks of a fertility center for humans.

    Fertility Center in OMR

    ReplyDelete
  11. hi, nice information is given in this blog. Thanks for sharing this type of information, it is so useful for me. nice work keep it up.
    Travel visa provider in Delhi

    ReplyDelete
  12. This comment has been removed by the author.

    ReplyDelete
  13. This comment has been removed by the author.

    ReplyDelete
  14. Thank you for benefiting from time to focus on this kind of, I feel firmly about it and also really like comprehending far more with this particular subject matter. In case doable, when you get know-how, is it possible to thoughts modernizing your site together with far more details? It’s extremely useful to me.
    Data Science course in rajaji nagar | Data Science with Python course in chenni
    Data Science course in electronic city | Data Science course in USA
    Data science course in pune | Data science course in kalyan nagar

    ReplyDelete
  15. This blog is the general information for the feature. You got a good work for these blog.We have a developing our creative content of this mind.Thank you for this blog. This for very interesting and useful.
    java training in chennai

    java training in marathahalli | java training in btm layout

    ReplyDelete
  16. Wonderful blog.. Thanks for sharing informative Post. Its very useful to me.

    dailyconsumerlife
    Article submission sites

    ReplyDelete
  17. Outstanding blog thanks for sharing such wonderful blog with us ,after long time came across such knowlegeble blog. keep sharing such informative blog with us.

    machine learning training in chennai
    best training insitute for machine learning
    Android training in Chennai
    PMP training in chennai

    ReplyDelete
  18. I recently came across your blog and have been reading along. I thought I would leave my first comment.
    Selenium training in Chennai

    Selenium training in Bangalore

    ReplyDelete
  19. I found your blog while searching for the updates, I am happy to be here. Very useful content and also easily understandable providing..
    Believe me I did wrote an post about tutorials for beginners with reference of your blog. 




    Selenium training in bangalore
    Selenium training in Chennai
    Selenium training in Bangalore
    Selenium training in Pune
    Selenium Online training

    ReplyDelete
  20. Outstanding blog thanks for sharing such wonderful blog with us ,after long time came across such knowlegeble blog. keep sharing such informative blog with us.

    Check out : machine learning tution in chennai
    artificial intelligence and machine learning course in chennai
    best training insitute for machine learning

    ReplyDelete
  21. I Regreat For Sharing The information The InFormation shared Is Very Valuable Please Keep Updating Us Time Just Went On Reading The Article Python Online Training AWS Online Training Hadoop Online Training Data Science Online Training

    ReplyDelete

  22. Thank you for such a sweet tutorial - all this time later, I've found it and love the end result. I appreciate the time you spent sharing your skills.
    Deer Hunting Tips Camping Trips Guide DEER HUNTING TIPS travel touring tips

    ReplyDelete

  23. You need to kill time, you need entertainment. Refer to our website. hope you get the most comfort.
    Thanks you for sharing!
    Still Hunting Method
    Hunting psych tips Survival Tips Travel Touring Tips

    ReplyDelete
  24. Thanks for posting the information I liked it
    Sanjary Kids is one of the best play school and preschool in Hyderabad,India. Give your child the best preschool experience by choosing the best playschool of Hyderabad in Abids. we provide programs like Play group,Nursery,Junior KG,Senior KG,and provides Teacher Training Program.
    early childhood teacher training course in hyderabad

    ReplyDelete
  25. Great blog information of the author

    Sanjary Academy is the best Piping Design institute in Hyderabad, Telangana. It is the best Piping design Course in India and we have offer professional Engineering Courses like Piping design Course, QA/QC Course, document controller course, Pressure Vessel Design Course, Welding Inspector Course, Quality Management Course and Safety Officer Course.
    Piping Design Course
    Piping Design Course in Hyderabad ­
    Piping Design Course in India­

    ReplyDelete
  26. Great blog posting of the topic

    Pressure Vessel Design Course is one of the courses offered by Sanjary Academy in Hyderabad. We have offer professional Engineering Course like Piping Design Course,QA/QC Course,document Controller course,pressure Vessel Design Course,Welding Inspector Course, Quality Management Course, #Safety officer course.
    Welding Inspector Course
    Safety officer course
    Quality Management Course
    Quality Management Course in India

    ReplyDelete
  27. Thank you for sharing amazing information.
    Yaaron Studios is one of the rapidly growing editing studios in Hyderabad. We are the best Video Editing services in Hyderabad. We provides best graphic works like logo reveals, corporate presentation Etc. And also we gives the best Outdoor/Indoor shoots and Ad Making services.
    video editors studio in hyderabad
    short film editors in hyderabad
    corporate video editing studio in hyderabad
    ad making company in hyderabad

    ReplyDelete
  28. Thank you for sharing such a nice post!

    Upgrade your career Learn Oracle Training from industry experts gets complete hands on Training, Interview preparation, and Job Assistance at Softgen Infotech.

    ReplyDelete
  29. Amazing article useful information.

    Web designing trends in 2020

    When we look into the trends, everything which is ruling today’s world was once a start up and slowly begun getting into. But Now they have literally transformed our lives on a tremendous note. To name a few, Facebook, Whats App, Twitter can be a promising proof for such a transformation and have a true impact on the digital world.

    we have offered to the advanced syllabus course web design and developing for available join now.

    https://www.webdschool.com/web-development-course-in-chennai.html

    ReplyDelete
  30. I would like to thank you for the efforts you have made in writing this article. I am hoping the same best work from you in the future as well. Thanks for sharing wonderful information..
    Salesforce Training in Chennai

    Salesforce Online Training in Chennai

    Salesforce Training in Bangalore

    Salesforce Training in Hyderabad

    Salesforce training in ameerpet

    Salesforce Training in Pune

    Salesforce Online Training

    Salesforce Training

    ReplyDelete
  31. I am really happy to say it’s an interesting post to read. I learn new information from your article; you are doing a great job. Keep it up…

    Python Training in Gurgaon
    Advanced Excel /VBA training in Gurgaon

    ReplyDelete
  32. Thanks for sharing such wonderful information with us. Indian Restaurant Elk Grove CA

    ReplyDelete
  33. Excellent article and this helps to enhance your knowledge regarding new things. Waiting for more updates.
    Angular 11 New Features
    Versions Of Angular

    ReplyDelete
  34. Really nice blog. thanks for sharing such a useful information.
    Kotlin Online Course

    ReplyDelete
  35. I truly like you're composing style, incredible data, thankyou for posting. business analytics course in kanpur

    ReplyDelete

  36. This post is so interactive and informative.keep update more information...
    Tally Course in Tambaram
    Tally course in Chennai

    ReplyDelete
  37. This post is so interactive and informative.keep update more information...
    dot net training in Tambaram
    Dot net training in Chennai


    ReplyDelete
  38. React JS Training in Hyderabad

    ReplyDelete
  39. Hey! Nicely written , Intresting to read

    ReplyDelete
  40. A-Class Marble offers an exclusive range of timeless Marble for Home. Our range of marbles is reputed for giving perfect elegance and style to your walls and floor.

    ReplyDelete
  41. Thanks For Sharing Your Valuable Information On This Blog

    ReplyDelete
  42. Really interesting content which is unique which provided me the required information.

    ReplyDelete
  43. Gain a superior understanding of the digital marketing domain with our Advanced Digital Marketing Training in Hyderabad. This program has been meticulously designed to empower individuals with core marketing concepts and strategies used in the digital framework. By offering pragmatic insights into digital marketing with real-time projects, and internships, we aspire to mold proficient digital marketers who can spearhead online marketing campaigns.
    Advanced Digital Marketing Training in hyderabad

    ReplyDelete
  44. Elevate your educational journey with F1 Visa Consultants in Hyderabad. Our expert team offers tailored guidance, ensuring a smooth path to obtaining your student visa for the USA. Trust our experience for a successful transition to American universities and a bright academic future.
    F1 Visa Consultants in Hyderabad

    ReplyDelete
  45. Are you looking to enhance your skills in cloud computing? Join our Google Cloud Platform Online training in Hyderabad and unlock a world of opportunities in the tech industry. With our comprehensive curriculum and expert instructors, you'll gain in-depth knowledge of the Google Cloud Platform and its various services. From cloud storage and databases to machine learning and big data analytics, our training covers it all. Be equipped with the skills to design, deploy, and manage applications and infrastructure on the Google Cloud Platform. Enroll now and take your career to new heights!
    Google Cloud Platform Online training in Hyderabad

    ReplyDelete
  46. Good explanation about "how to improve cache performance" Thanks for sharing this information.
    Data science training institute in JNTU

    ReplyDelete
  47. Business analyst job support provides assistance to professionals in the field, offering guidance on tasks like requirement gathering, data analysis, process modeling, and stakeholder management. This support aids in problem-solving, skill development, and overcoming challenges encountered in business analysis roles. It may include mentorship, coaching, training, and access to resources for career advancement.

    ReplyDelete