Improving performance by strategy-independent program restructuring using bounded locality intervals

An efficient strategy-independent program restructuring algorithm based on the empirical studies of phases and transitions in the symbolic reference strings of real programs is developed. The algorithm is formulated on the basis that the majority of the page faults occur during phase transitions. Thus emphasis is placed in grouping those relocatable blocks referenced during phase transitions in the same pages. Some parameters to characterize program behavior are also established. The purpose is to study the relationship between these parameters and the performance of the program. An experiment to compare the performance improvement of the proposed restructuring algorithm and other major existing algorithms is conducted. The performance indices chosen are the mean working set size and the page fault rate. The problem of data dependency, the cost as well as the portability of program restructuring procedures are discussed.Science, Faculty ofComputer Science, Department ofGraduat