Strategy-Independent Program Restructuring Based on Bounded Locality Intervals

ID
TR-81-09
Authors
Samuel T. Chanson and Bernard Law
Publishing date
August 1981
Abstract
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.