Technical Reports

The ICICS/CS Reading Room

UBC CS TR-81-09 Summary

Strategy-Independent Program Restructuring Based on Bounded Locality Intervals, August 1981 Samuel T. Chanson and Bernard Law

A new program restructuring algorithm based on the phase/transition model of program behaviour is presented. The scheme places much more emphasis on those blocks in the transition phases in the construction of the connectivity matrix than the existing algorithms. This arises from the observation that the page fault rate during the transition phases is several orders of magnitude higher than that during the major phases. The strategy is found, for our reference strings, to outperform the critical working set strategy (considered to be the current best), by non-negligible amounts. Furthermore, the overhead involved is lower than that of CWS and not much higher than that of the Nearness method which is the simplest scheme known. Being strategy-independent, it also seems to respond better than CWS when the memory management strategy used is not the working set policy.

If you have any questions or comments regarding this page please send mail to