A study of sampling, granularity and localities in program restructuring

Program restructuring is a method to reduce the cost of program execution by improving the locality of the program\u27s reference behavior. Three aspects of program restructuring (sampling, granularity, localities) are studied in this research. The study of first aspect, sampling, shows that the high cost of a posteriori restructuring can be reduced considerably by a program restructuring method based on sampled reference strings rather than on complete reference string;The second aspect is granularity. Based on the studies of two different block sizes (the basic-block and the procedure block), it is found that the performance of restructuring using smaller blocks is not necessarily better;Finally, a new strategy-independent restructuring method, using both the critical and locality principles, is found to be more effective than any other existing restructuring methods;Results of measurements of paging performance obtained in the experiments are discussed. Both fixed-space and variable-space paging policies are considered