Wednesday, February 2, 2011

Cache-oblivious Algorithms

Hi!

This time it's about Parallel Computations, and the first real article in the section is titled Cache-oblivious Algorithms. It introduces the problem of memory bandwidth, the concept of cache hierarchy in modern computers; then describes the underlying idea of cache-oblivious algorithms, and proceeds with an example of how to design a cache-oblivious algorithm for a simple problem.Presented benchmark results show unconditional superiority of the approach.

38 comments:

  1. Thanks, but how that example show "how to design a cache-oblivious algorithm for a simple problem"

    I mean, given a machine that I know how many cores, cache and memory, how that affecting the design of the algorithm? Is that mean I need to keep all the data of a function fit in the L2 cache??

    ReplyDelete
  2. > I mean, given a machine that I know how many cores, cache and memory, how that affecting the design of the algorithm?

    The idea of cache-oblivious algorithms is that particular core/cache characteristics do not affect algorithm design. It has both positive and negative implications. The positive side is that one does not need to re-tune an algorithm for each machine (since one needs to accommodate for L1, L2, L3 and memory, it becomes quite tricky, and one machine may have L3 while other is not). The negative side is that performance suffers somewhat, however cache complexity (number of "memory" transfers) is usually optimal (within a constant factor of theoretical minimum).

    > Is that mean I need to keep all the data of a function fit in the L2 cache?

    I am not sure I get your question. But, well, if you can fit data into lower level cache, it is definitely a good thing for performance. Developers try to at least fit dataset into main memory, because disk accesses make things much more problematic. But as I shown fitting data into caches makes significant difference as well.

    ReplyDelete
  3. Hi Dmitry,
    According to this presentation on modern processors we already have 95% cache hit. Does this mean that we are optimizing our code to get the last 5%?

    Thank you.

    ReplyDelete
  4. Hi,

    According to what presentation?
    Anyway, in this particular algorithm (and some others) we have -> 0 cache hit rate if we do not do the optimization.

    ReplyDelete
  5. This is great! Thanks so much for both the blog posts and then the videos. I've had ideas like this floating around my head, but haven't had a good mental framework to fit them in. It's great that much of my ideas fit into this nice theory (and more importantly that others have done the legwork to actually study what's going on :p ). Great site!

    ReplyDelete
  6. I’m really impressed with your article, such great & usefull knowledge you mentioned here.
    HBS Case Study Solution

    ReplyDelete
  7. I appreciate your efforts in preparing this post. I really like your blog articles.
    Mechanical Engineering Project Help

    ReplyDelete
  8. This is really great work. Thank you for sharing such a good and useful information here in the blog for students.
    PM Homework Help

    ReplyDelete
  9. Awesome work you have done here, I am very happy to read this nice post. You are a great writer and give us much information.
    do my computer science homework

    ReplyDelete
  10. Science Channel’s are giving a complete knowledge to its viewers about every thing students write done dissertation on this subjects and show its importance.
    SAS Tutor

    ReplyDelete
  11. Awesome work you have done here, I am very happy to read this nice post. You are a great writer and give us much information.
    Matlab Project Help

    ReplyDelete
  12. Well thanks for posting such an outstanding idea. I like this blog & I like the topic and thinking of making it right.
    Computer Network Homework Help

    ReplyDelete
  13. AMERICAN GREETINGS casesolution
    No doubt! It will be truly hard enrolling! I wish you good fortunes!

    ReplyDelete
  14. E Tuition Pakistan
    I genuinely appreciated understanding it. Sitting tight for some more incredible articles like this from you in the nearing days

    ReplyDelete
  15. Case Studies Solutions
    No doubt! It will be truly hard enrolling! I wish you good fortunes!

    ReplyDelete
  16. Bandwidth is never enough, I always had a hard time with low Internet connections. Maybe I'll get something more decent next time, cheap bicycles.

    ReplyDelete
  17. Struggle to attempt the academic assignments is real for the students. However, there is a solution to every problem. You could find the solution for your coursework with our Assignment Help and can get a well-written assignment from us.

    ReplyDelete
  18. This a good way to appreciate the teacher as they put their efforts to train students. UK dissertation Writers appreciates the teachers.
    MBA Assignment Help

    ReplyDelete
  19. Get the best assignment help from MakeMyAssignments.co.nz at affordable prices. Assignment help | Need Assignment help

    ReplyDelete
  20. Great site and a great topic as well I really get amazed to read this. It’s really good. I like viewing web sites which comprehend the price of delivering the excellent useful resource free of charge. candid photographers | Freelance jobs | freelance web designer |

    ReplyDelete
  21. Students who are in USA can now get a good quality essay help paper from MyAssignmenthelp.com. It is guaranteed to customers that the papers that they give meet the high university standards.

    ReplyDelete
  22. Thank you so much for this informative post!!
    USAAssignment Help deals into essay help online with the help of assignment expert. We aimed at making cheap essay writing service simple and reduce the burden of students. Visit Link: https://goo.gl/yqAmKR

    ReplyDelete
  23. Thanks for uploading this blog.I really appreciate your work on this blog.We are Service Provider for Antivirus.If you have any query related to Antivirus then you can Contact us. Just Call Our Toll-Free: 1-800-463-5163 or visit:https://www.globaltechsquadinc.com

    ReplyDelete
  24. USAassignment has set up a standard for writing assignments. We make students realize their potential by mentoring them proper guidance through the process of imparting Accounting assignment help and accounting homework help.

    ReplyDelete
  25. USAassignment provide best MBA assignment help for the student. Our expert provide best research based help for assignment. Get 100% Plagiarism free homework at affordable price. Our services come with 24/7 availability of assignment experts over chat and phone. Contact Us: Toll Free: 1-844-752-3111 Visit Link: http://www.usaassignment.com/mba-assignment-help.html

    ReplyDelete
  26. Thank you so much for this post that is informative for me. Global Tech Squad Inc providing best technical support team of Canon Printer. If you have any query or problem’s regarding these services then you can contact also here by our toll-free number. USA/Canada : 1-800-463-5163.
    Visit Link : https://globaltechsquadinc.com/support-for-canon-printer.html

    ReplyDelete
  27. Visit our website to know the reviews of assignment writing service providers.
    allassignmenthelp reviews

    ReplyDelete
  28. Very good article thanks for sharing.I visit this website every day.
    farsiha
    tekrariha

    ReplyDelete
  29. Do visit our website to get best essay writing servicefrom our experts.

    ReplyDelete
  30. It is nice to read such high-quality content. It is a good article that discusses the topic at hand quite well. I am looking forward to read more articles from your site. Keep up the good work. Our assignment help experts could address students' academic topics quite well. Thus, they can opt for our service if they have difficulty in writing the academic task.
    assignment help

    ReplyDelete