A fractal in the real world


Of course, real world fractals do exist, but it is interesting to appear to have “discovered” one, or at least a pattern which certainly shows many fractal-like properties.

I am plotting the relative efficiency of different page replacement algorithms – and here I am looking at Belady’s OPT (or MIN), or as it is sometimes called, the clairvoyant page replacement algorithm.

Here I am measuring the proportion of time a page stands idle (including its loading time). So a page with a ratio of 1.0 is loaded but never used, a page with a ratio of 0.999 is used one-thousandth of the time it is in the system and a page with a ratio of 0.99 is used one-hundredth of the time it’s in the system and so on.

So, here’s the “full” plot for my data:

Full OPT plot

Not much to see – except most pages are idle most of the time: so we go closer:

90%

And closer…

0.999%

And closer…

0.9999%

That’s about the limit of the precision of the data, but it looks pretty fractal like to me…

(Should add, other page replacement policies studied don’t appear to show this fractal-like pattern, exhibiting only one peak/modal frequency.)

OPT and LRU compared for multithreaded code


Here is the fruit of many months labour:

simulationInterestingly, the two series are very close to isomorphic (i.e., they have essentially the same shape if one scales the x-plot appropriately).

This is based on running a short piece of code to decode 32 frames of video – the memory model used was 4k pages with a pooled 512k on chip (each chip can access any part of the pool at the cost of 1 tick) and unlimited memory 100 ticks away per 128 bits of read-in (so for a 4k page it takes 25,600 ticks to fault the page in).

This is a bit of a crude simplification of the memory model seen on, say, a Tilera TILE64 system, but it’s close enough (though this simulation had 16 cores).

Enhanced by Zemanta