Help! Computing power or better algorithm required

Peter Denning, Image via Wikipedia

I have a serious problem with my MSc project.

For the first part of this I am seeking to demonstrate/investigate the underlying assumptions about locality, phases of locality and so on that underlie the working set method of VM management.

The graphs on other blogs here are some of the output of the test cases I have been using and they seem to work well.

In addition, though, I want to show what Peter Denning refers to as a “lifetime curve” for a process – essentially showing how increasing the size of the resident set (or in my case increasing the time for which pages remain resident) changes the time between page faults.

This should not (and early results of mine show) it isn’t linear (though it is monotonic). But to calculate this seems, under the algorithm I am using, to require vast amounts of computing power.

My algorithm (in Groovy) is essentially this:

1. Set time (if we are plotting 600 points then first time would be 1/600th of the process lifetime) for page expiry

2. Reading the lackeyml file and using a groovy/java map, store the page number and the reference time -if the page wasn’t referred to in the map, increase the fault count

3. Look through the map to see if there are any pages which are older than the page expiry times, and evict them from the map

4. Move to the next record in the lackeyml file and return to 2

5. Get to the end of the file and count the total faults.

The problem with all this is (2) above – typically it is being called millions of times and iterating through a map in this way is extremely slow. I think on a dual AMD64 box here with the 48 million instruction count for xterm (pretty much a ‘toy’ application in this context) – this will take 20 days to run, even with a decent bit of parallelization in the code.

Hence I need a better algorithm or massive (and affordable) computing power. Anyone have a cluster they could lend me for a few hours?

Related articles

• Introducing the lackeyml format (cartesianproduct.wordpress.com)
• Eighteen million lines of XML! (cartesianproduct.wordpress.com)
• Patterns of locality in xterm (cartesianproduct.wordpress.com)
• Bob Morris and stream algorithms (geomblog.blogspot.com)
• When is an algorithm not an algorithm? (jrvarma.wordpress.com)
• Simple algorithms, illustrated (sathyasays.com)
• Optimizing the A* algorithm (takinginitiative.net)