This article is part of the article series "MIT Introduction to Algorithms."
<- previous article next article ->
MIT Algorithms

This is a happy and sad moment at the same time - I have finally reached the last two lectures of MIT's undergraduate algorithms course. These last two lectures are on a fairly new area of algorithm research called "cache oblivious algorithms."

Cache-oblivious algorithms take into account something that has been ignored in all the lectures so far, particularly, the multilevel memory hierarchy of modern computers. Retrieving items from various levels of memory and cache make up a dominant factor of running time, so for speed it is crucial to minimize these costs. The main idea of cache-oblivious algorithms is to achieve optimal use of caches on all levels of a memory hierarchy without knowledge of their size.

Cache-oblivious algorithms should not be confused with cache-aware algorithms. Cache-aware algorithms and data structures explicitly depend on various hardware configuration parameters, such as the cache size. Cache-oblivious algorithms do not depend on any hardware parameters. An example of cache-aware (not cache-oblivious) data structure is a B-Tree that has the explicit parameter B, the size of a node. The main disadvantage of cache-aware algorithms is that they are based on the knowledge of the memory structure and size, which makes it difficult to move implementations from one architecture to another. Another problem is that it is very difficult, if not impossible, to adapt some of these algorithms to work with multiple levels in the memory hierarchy. Cache-oblivious algorithms solve both problems.

Lecture twenty-two introduces the terminology and notation used in cache-oblivious algorithms, explains the difference between cache-oblivious and cache-aware algorithms, does a simple memory analysis of several simple algorithms and culminates with a cache-oblivious algorithm for matrix multiplication.

The final lecture twenty-three is the most difficult in the whole course and shows cache-oblivious binary search trees and cache-oblivious sorting called funnel sort.

Use this supplementary reading material by professor Demaine to understand the material better: Cache-oblivious algorithms and data structures (.pdf).

Lecture 22: Cache Oblivious Algorithms I

Lecture twenty-two starts with an introduction to the modern memory hierarchy (CPU cache L1, L2, L3, main memory, disk cache, etc.) and with the notation and core concepts used in cache-oblivious algorithms.

A powerful result in cache-oblivious algorithm design is that if an algorithm is efficient on two levels of cache, then it's efficient on any number of levels. Thus the study of cache-obliviousness can be simplified to two-level memory hierarchy, say the CPU cache and main memory, where the accesses to cache are instant but are orders of magnitude slower to main memory. Therefore the main question cache-oblivious algorithm analysis tries to address is how many memory transfers (MTs) does a problem of size N take. The notation used for this is MT(N). For an algorithm to be efficient, the number of memory transfers should be as small as possible.

Next the lecture analysis the number of memory transfers for basic array scanning and array reverse algorithms. Since array scanning is consequential, N elements can be processed with O(N/B) accesses, where B is the block size - number of elements that are automatically fetched as N-th element is accessed. That is MT(N) = O(N/B) for array scanning. The same bound holds for reversing an array, since it can be viewed two scans - one from the beginning and one from the end.

Next it's shown that the classical binary search (covered in lecture 3) is not cache efficient, but order statistics problem (covered in lecture 6) is cache efficient.

Finally the lecture describes a cache efficient way to multiply matrices by storing them block-wise in memory.

You're welcome to watch lecture twenty-two:

Topics covered in lecture twenty-two:

  • [00:10] Introduction and history of cache-oblivious algorithms.
  • [02:00] Modern memory hierarchy in computers: Caches L1, L2, L3, main memory, disk cache.
  • [06:15] Formula for calculating the cost to access a block of memory.
  • [08:18] Amortized cost to access one element in memory.
  • [11:00] Spatial and temporal locality of algorithms.
  • [13:45] Two-level memory model.
  • [16:30] Notation: total cache size M, block size B, number of blocks M/B.
  • [20:40] Notation: MT(N) - number of memory transfers of a problem of size N.
  • [21:45] Cache-aware algorithms.
  • [22:50] Cache-oblivious algorithms.
  • [28:35] Blocking of memory.
  • [32:45] Cache-oblivious scanning algorithm (visitor pattern).
  • [36:20] Cache-oblivious Array-Reverse algorithm.
  • [39:05] Memory transfers in classical binary search algorithm.
  • [43:45] Divide and conquer algorithms.
  • [45:50] Analysis of memory transfers in order statistics algorithm.
  • [01:00:50] Analysis of classical matrix multiplication (with row major, column major memory layout).
  • [01:07:30] Cache oblivious matrix multiplication.

Lecture twenty-two notes:

MIT Algorithms Lecture 22 Notes Thumbnail. Page 1 of 2.
Lecture 22, page 1 of 2: modern memory hierarchy, spacial and temporal locality, two-level memory model, blocking of memory, basic algorithms: parallel scan.

MIT Algorithms Lecture 22 Notes Thumbnail. Page 2 of 2.
Lecture 22, page 2 of 2: basic algorithms: binary search, divide and conquer algorithms, order statistics, matrix multiplication, block algorithms.

Lecture 23: Cache Oblivious Algorithms II

This was probably the most complicated lecture in the whole course. The whole lecture is devoted to two subjects - cache-oblivious search trees and cache-oblivious sorting.

While it's relatively easy to understand the design of cache-oblivious way of storing search trees in memory, it's amazingly difficult to understand the cache-efficient sorting. It's called funnel sort which is basically an n-way merge sort (covered in lecture 1) with special cache-oblivious merging function called k-funnel.

You're welcome to watch lecture twenty-three:

Topics covered in lecture twenty-three:

  • [01:00] Cache-oblivious static search trees (binary search trees).
  • [09:35] Analysis of static search trees.
  • [18:15] Cache-aware sorting.
  • [19:00] Sorting by repeated insertion in binary tree.
  • [21:40] Sorting by binary merge sort.
  • [31:20] Sorting by N-way mergesort.
  • [36:20] Sorting bound for cache-oblivious sorting algorithms.
  • [38:30] Cache-oblivious sorting.
  • [41:40] Definition of K-Funnel (cache-oblivious merging).
  • [43:35] Funnel sort.
  • [54:05] Construction of K-Funnel.
  • [01:03:10] How to fill buffer in k-funnel.
  • [01:07:30] Analysis of fill buffer.

Lecture twenty-three notes:

MIT Algorithms Lecture 23 Notes Thumbnail. Page 1 of 2.
Lecture 23, page 1 of 2: static search trees, cache aware sorting.

MIT Algorithms Lecture 23 Notes Thumbnail. Page 2 of 2.
Lecture 23, page 2 of 2: cache oblivious sorting, k-funnels, funnel sort, fill-buffer algorithm and analysis.


Have fun with the cache oblivious algorithms! I'll do a few more posts that will summarize all these lectures and highlight key ideas.

If you loved this, please subscribe to my blog!

This article is part of the article series "MIT Introduction to Algorithms."
<- previous article next article ->

Comments

July 13, 2009, 09:57

Is there any lecture on complexity analysis of algorithms ?

August 12, 2014, 14:01

I really love your blog.I wanted to thank you for this great read!! I definitely enjoying each and every little bit of the article and I have you bookmarked your site to check out new stuff you post.

independence day images
happy independence day images.

FIBA Permalink
August 22, 2014, 12:47

I really love your blog.I wanted to thank you for this great read!! I definitely enjoying each and every little bit of the article and I have you bookmarked your site to check out new stuff you post.

fiba 2014
fiba world cup
fiba world cup 2014
Basketball world cup 2014
fiba world cup schedule
fiba world cup 2014 teams
fiba world cup 2014 groups
fiba live streaming,

August 22, 2014, 14:12

According to predictions from a reputable dealer M88, CR7 will pass "rivalry" for the 2nd consecutive winning Pichichi with 11/8 rate (ate 11 left 8). But, in every attack, experts predict the evaluation m88asia
Barcelona Real marginally better. Specifically, the "trident" Suarez, Messi and Neymar is listed at 5/4 ratio, while Bale, Benzema and Ronaldo is 11/10.

In M88 ratio La Liga champions this season, respectively Real (6/5), Barcelona (5/6) and Atletico (1/14) is for believe.

October 16, 2014, 12:15

The tips which you have shared in this post are just awesome. These tips are really helpful to me and I think it should must helpful to others. I really like the style of writing this article. Your articles are always helps me a lot. Thanks for sharing this wonderful article with us.

Diwali 2014
Diwali wishes
Diwali sms
Diwali images
Diwali quotes
Diwali greetings
Diwali pictures
Happy Diwali pictures
happy Diwali 2014
Happy Diwali Images
happy Diwali
happy Diwali wishes
happy Diwali sms
happy Diwali quotes
Diwali Rangoli
Happy Diwali Rangoli
Diwali messages
Happy Diwali messages
Diwali Greetings
Happy Diwali Greetings
Diwali poems
Happy Diwali poems
Diwali Wallpapers
Happy Diwali Wallpapers.

Wolter Permalink
July 14, 2009, 02:08

I'm curious... Why not have the application query the hardware to find out its capabilities, and then tweak the cache-aware algorithms accordingly?

Joseph Garvin Permalink
July 14, 2009, 04:05

@Wolter: I can think of two reasons.

1. The immediately practical reason: You'd need to recompile the code to achieve best performance (treating the cache size as a constant and not something that varies at run time). You could do this though and there might even exist a sufficiently advanced JIT somewhere.

2. The real reason: Because you can write a cache oblivious algorithm and have it perform best all the time without having to worry about that. The cache-aware-with-adjusting actually requires more complexity. The cache oblivious way "just works."

Wolter Permalink
July 14, 2009, 15:10

> You’d need to recompile the code to achieve best performance (treating the cache size as a constant and not something that varies at run time).

But how significant would the performance impact be? I'm wondering whether a dynamic cache-aware algorithm would give better performance than a cache-oblivious one. It would seem reasonable that a cache-aware algorithm would be capable of making more intelligent decisions.

> Because you can write a cache oblivious algorithm and have it perform best all the time without having to worry about that. The cache-aware-with-adjusting actually requires more complexity. The cache oblivious way “just works.”

But is that in fact true? Do cache-oblivious algorithms actually outperform cache-aware algorithms? Or are they just a compromise?

October 22, 2009, 20:17

Fairly advanced stuff... I am fascinated by Open Course Ware.

tony d Permalink
October 31, 2009, 23:31

Are there any lectures covering branch and bound algorithms?

Sapping Permalink
December 18, 2009, 19:33

On the first page of your lecture notes for Lecture 23, in the analysis of static search trees, you have that the triangle (subtree) ≤ B is ≥ than log B. I think it should be the triangle ≤ B is ≥ than 1/2 log B. But other than that, thank you again for posting these, they really help when combined with the blackboard notes.

December 18, 2009, 20:29

Sapping, oh yes, 1/2 log B. I somehow missed the 1/2 fraction. Thanks for spotting that!

Bharathan Balaji Permalink
November 27, 2012, 10:21

It looks like the videos have been made private. Can you please put it back to the public domain? Thanks!

July 21, 2013, 15:38

where are the videos?

asew Permalink
May 23, 2014, 17:39
asew Permalink
May 23, 2014, 17:39
June 03, 2014, 21:34

Fairly advanced stuff... I am fascinated by Open Course Ware.

tot Permalink
June 28, 2014, 10:16

clear and informative. I just feel your blog is my worth. thanks a lot!

Fast Income Club Fast Income Club Review Fast Income Club Fast Income Club Review Fast Income Club Fast Income Club Fast Income Club Review Fast Income Club Fast Income Club Review Fast Income Club Fast Income Club Fast Income Club Review Fast Income Club Fast Income Club Review Fast Income Club Fast Income Club Fast Income Club Review Fast Income Club Fast Income Club Review Fast Income Club Fast Income Club Fast Income Club Review Fast Income Club Fast Income Club Review Fast Income Club Fast Income Club Fast Income Club Review Fast Income Club Fast Income Club Review Fast Income Club Fast Income Club Fast Income Club Review Fast Income Club Fast Income Club Review Fast Income Club Fast Income Club Fast Income Club Review Fast Income Club Fast Income Club Review Fast Income Club Fast Income Club Fast Income Club Review Fast Income Club Fast Income Club Review Fast Income Club Fast Income Club Fast Income Club Review Fast Income Club Fast Income Club Review Fast Income Club Fast Income Club Fast Income Club Review Fast Income Club Fast Income Club Review Fast Income Club.

clear and informative. I just feel your blog is my worth. thanks a lot!

Fast Income Club Fast Income Club Review Fast Income Club Fast Income Club Review Fast Income Club Fast Income Club Fast Income Club Review Fast Income Club Fast Income Club Review Fast Income Club Fast Income Club Fast Income Club Review Fast Income Club Fast Income Club Review Fast Income Club Fast Income Club Fast Income Club Review Fast Income Club Fast Income Club Review Fast Income Club Fast Income Club Fast Income Club Review Fast Income Club Fast Income Club Review Fast Income Club Fast Income Club Fast Income Club Review Fast Income Club Fast Income Club Review Fast Income Club Fast Income Club Fast Income Club Review Fast Income Club Fast Income Club Review Fast Income Club Fast Income Club Fast Income Club Review Fast Income Club Fast Income Club Review Fast Income Club Fast Income Club Fast Income Club Review Fast Income Club Fast Income Club Review Fast Income Club Fast Income Club Fast Income Club Review Fast Income Club Fast Income Club Review Fast Income Club Fast Income Club Fast Income Club Review Fast Income Club Fast Income Club Review Fast Income Club.

yeshwanth Permalink
July 10, 2014, 08:42
July 20, 2014, 18:06

Actually this post is about my personal interest and the mid of the post is truly informative and I love and elaboration quality of writer. I always try to find this type of info regarding this topic now here I got this thanks Happy Friendship Day SMS Friendship Day SMS Independence Day Images Happy Independence Day Images Independence Day Images India India Independence Day independence day speech independence day sms independence day wallpaper independence day message independence day songs again thanks for this great blog.

mahendher Permalink
July 23, 2014, 12:10

After read a couple of the articles on your website these few days, and I truly like your style of blogging.
I tag it to my favorites internet site list and will be checking back soon.
Please check out my web site also and let me know what you think.
ramadan mubarak messages
ramadan mubarak message
ramadan quotes
ramadan mubarak images
ramadan pictures.

sanchit Permalink
July 25, 2014, 21:23

Hey its great post really enjoyed this one i found this on google ,i think there are still websmasters who provide quality contents to the reader and hope to come back soon and by the way Eid Mubarak Wishes
Eid Mubarak Sms in Hindi
Eid Mubarak sms In English
Eid Mubarak sms in Urdu
Eid Mubarak Wallpapers
Eid Mubarak Greetings
Eid Mubarak cardsto all of you also you can check Happy eid Mubarak 2014
really a great stuff

ttfg Permalink
July 27, 2014, 09:04

Hi this post is very nice, really enjoyed it. Umbrella wisdom is the enfinity of kindom, place internet, lets see how it all goes to get its wisomly, We insured profits to its arena of Insured Profits,Insured Profits Review,Free Cash Formula,Free Cash Formula Review,Friendship Day Quotes,Happy Friendship Day Quotes,Happy Friendship Day Messages,Friendship Day Quotes And Sayings,2K A DAY System,2K A DAY System Review,Daily Cash Creator,Daily Cash Creator Review,The $100K Club,The $100K Club Review,Cloud Cash Machine,Cloud Cash Machine Review,CPA Evolution Review,Cloud Pro Hosting Review,Cloud Pro Hosting,Friendship Day Quotes.Happy Friendship Day Quotes, CPA Evolution.Insured Profits,Insured Profits Review,Free Cash Formula,Free Cash Formula Review,Friendship Day Quotes,Happy Friendship Day Quotes,Happy Friendship Day Messages,Friendship Day Quotes And Sayings,2K A DAY System,2K A DAY System Review,Daily Cash Creator,Daily Cash Creator Review,The $100K Club,The $100K Club Review,Cloud Cash Machine,Cloud Cash Machine Review,CPA Evolution Review,Cloud Pro Hosting Review,Cloud Pro Hosting,Friendship Day Quotes.Happy Friendship Day Quotes, CPA Evolution.Insured Profits,Insured Profits Review,Free Cash Formula,Free Cash Formula Review,Friendship Day Quotes,Happy Friendship Day Quotes,Happy Friendship Day Messages,Friendship Day Quotes And Sayings,2K A DAY System,2K A DAY System Review,Daily Cash Creator,Daily Cash Creator Review,The $100K Club,The $100K Club Review,Cloud Cash Machine,Cloud Cash Machine Review,CPA Evolution Review,Cloud Pro Hosting Review,Cloud Pro Hosting,Friendship Day Quotes.Happy Friendship Day Quotes, CPA Evolution.Insured Profits,Insured Profits Review,Free Cash Formula,Free Cash Formula Review,Friendship Day Quotes,Happy Friendship Day Quotes,Happy Friendship Day Messages,Friendship Day Quotes And Sayings,2K A DAY System,2K A DAY System Review,Daily Cash Creator,Daily Cash Creator Review,The $100K Club,The $100K Club Review,Cloud Cash Machine,Cloud Cash Machine Review,CPA Evolution Review,Cloud Pro Hosting Review,Cloud Pro Hosting,Friendship Day Quotes.Happy Friendship Day Quotes, CPA Evolution.Insured Profits,Insured Profits Review,Free Cash Formula,Free Cash Formula Review,Friendship Day Quotes,Happy Friendship Day Quotes,Happy Friendship Day Messages,Friendship Day Quotes And Sayings,2K A DAY System,2K A DAY System Review,Daily Cash Creator,Daily Cash Creator Review,The $100K Club,The $100K Club Review,Cloud Cash Machine,Cloud Cash Machine Review,CPA Evolution Review,Cloud Pro Hosting Review,Cloud Pro Hosting,Friendship Day Quotes.Happy Friendship Day Quotes, CPA Evolution.
The arena will rule always with kingdom of speech.

ttttttt Permalink
July 29, 2014, 10:56

Binary umbrella coding is best, do you know about that? Your post is worth my time and I sincerly thank you for spreading and sharing your valuable knowledge and information, which many less people do these days! Free Cash Formula, Free Cash Formula, Free Cash Formula, Free Cash Formula, Free Cash Formula, Free Cash Formula, Free Cash Formula Review, Free Cash Formula Review, 2K A DAY System, 2K A DAY System, 2K A DAY System, 2K A DAY System, 2K A DAY System, 2K A DAY System, 2K A DAY System Review, 2K A DAY System Review, Friendship Day Quotes, Friendship Day Quotes, Friendship Day Quotes, Friendship Day Quotes, Friendship Day Quotes, Friendship Day Quotes, Friendship Day Quotes, Friendship Day Quotes, Friendship Day Quotes, Happy Friendship Day Quotes, Happy Friendship Day Quotes, Happy Friendship Day Quotes, Daily Cash Creator, Daily Cash Creator, Daily Cash Creator, Daily Cash Creator, Daily Cash Creator, Daily Cash Creator, Daily Cash Creator Review, Daily Cash Creator Review, The $100K Club, The $100K Club, The $100K Club, The $100K Club, The $100K Club, The $100K Club, The $100K Club, The $100K Club, The $100K Club, The $100K Club Review, Binary Predictor, Binary Predictor, Binary Predictor, Binary Predictor, Binary Predictor, Binary Predictor, Binary Predictor Review, Free Cash Formula, Free Cash Formula, Free Cash Formula, Free Cash Formula, Free Cash Formula, Free Cash Formula, Free Cash Formula Review, Free Cash Formula Review, 2K A DAY System, 2K A DAY System, 2K A DAY System, 2K A DAY System, 2K A DAY System, 2K A DAY System, 2K A DAY System Review, 2K A DAY System Review, Friendship Day Quotes, Friendship Day Quotes, Friendship Day Quotes, Friendship Day Quotes, Friendship Day Quotes, Friendship Day Quotes, Friendship Day Quotes, Friendship Day Quotes, Friendship Day Quotes, Happy Friendship Day Quotes, Happy Friendship Day Quotes, Happy Friendship Day Quotes, Daily Cash Creator, Daily Cash Creator, Daily Cash Creator, Daily Cash Creator, Daily Cash Creator, Daily Cash Creator, Daily Cash Creator Review, Daily Cash Creator Review, The $100K Club, The $100K Club, The $100K Club, The $100K Club, The $100K Club, The $100K Club, The $100K Club, The $100K Club, The $100K Club, The $100K Club Review, Binary Predictor, Binary Predictor, Binary Predictor, Binary Predictor, Binary Predictor, Binary Predictor, Binary Predictor Review, Free Cash Formula, Free Cash Formula, Free Cash Formula, Free Cash Formula, Free Cash Formula, Free Cash Formula, Free Cash Formula Review, Free Cash Formula Review, 2K A DAY System, 2K A DAY System, 2K A DAY System, 2K A DAY System, 2K A DAY System, 2K A DAY System, 2K A DAY System Review, 2K A DAY System Review, Friendship Day Quotes, Friendship Day Quotes, Friendship Day Quotes, Friendship Day Quotes, Friendship Day Quotes, Friendship Day Quotes, Friendship Day Quotes, Friendship Day Quotes, Friendship Day Quotes, Happy Friendship Day Quotes, Happy Friendship Day Quotes, Happy Friendship Day Quotes, Daily Cash Creator, Daily Cash Creator, Daily Cash Creator, Daily Cash Creator, Daily Cash Creator, Daily Cash Creator, Daily Cash Creator Review, Daily Cash Creator Review, The $100K Club, The $100K Club, The $100K Club, The $100K Club, The $100K Club, The $100K Club, The $100K Club, The $100K Club, The $100K Club, The $100K Club Review, Binary Predictor, Binary Predictor, Binary Predictor, Binary Predictor, Binary Predictor, Binary Predictor, Binary Predictor Review Thanks a lot! You rock! your bolg also rock, coding you provide is nowhere to be found.

sanchit Permalink
August 11, 2014, 18:36

I am very happy to visit this site and hope to visit here again and again. I have bookmarked your site due to the interesting and relevant stuff found here. Also I have recommended the same to my other friends.
Independence day india
Independence Day Images

Independence Day Wallpapers

Independence Day Speech in English

Independence Day Quotes

Independence Day Songs

Independence Day Poems

Independence Day SMS

This is my site, you can visit it and leave your valuable feedback.

Rosy Permalink
August 22, 2014, 14:01

This article is quite helpful and informative too. I enjoyed a lot. Thanks for sharing such a great article.

Amazon Promotional Code 2014
Amazon Promotional Code
Amazon Promotional Code for August 2014

Thanks for sharing such a great article.

niman Permalink
August 26, 2014, 06:47

Interesting analysis & shows the (occasional) perils of abstraction. Thanks.
fotoselli kapı - garaj kapısı - kapı fiyatları - mantar bariyer - otomatik Kapı - otomatik kapı sistemleri - otomatik kepenk fiyatları - seksiyonel kapı .

niman Permalink
August 26, 2014, 06:48

Interesting analysis & shows the (occasional) perils of abstraction. Thanks.
fotoselli kapı - garaj kapısı - kapı fiyatları - mantar bariyer - otomatik Kapı - otomatik kapı sistemleri - otomatik kepenk fiyatları - seksiyonel kapı .

niman Permalink
August 26, 2014, 06:49

Interesting analysis & shows the (occasional) perils of abstraction. Thanks.
fotoselli kapı - garaj kapısı - kapı fiyatları - mantar bariyer - otomatik Kapı - otomatik kapı sistemleri - otomatik kepenk fiyatları - seksiyonel kapı .

niman Permalink
August 26, 2014, 06:49

Interesting analysis & shows the (occasional) perils of abstraction. Thanks.
fotoselli kapı - garaj kapısı - kapı fiyatları - mantar bariyer - otomatik Kapı - otomatik kapı sistemleri - otomatik kepenk fiyatları - seksiyonel kapı .

sanchit Permalink
September 21, 2014, 11:39

Asian Games Incheon 2014 Opening Ceremony Event Place : Hello every one. So if you are here to search for the Incheon Asian Games 2014 Venue or say Incheon Asian Games 2014 Event Place or say Asian Games 2014 Incheon Opening day Place or Live News of Asian games 2014 Live streaming or Incheon Asian Games 2014 Live Streaming then you are on the right website.

October 28, 2014, 06:07

Thanks for the post. Halloween 2014 Images

Keep up the good work.

Leave a new comment

(why do I need your e-mail?)

(Your twitter name, if you have one. (I'm @pkrumins, btw.))

Type the first letter of your name: (just to make sure you're a human)

Please preview the comment before submitting to make sure it's OK.

Advertisements