The Measurement of Locality and the Behaviour of Programs

Abstract
Although the phenomenon of locality has long been recognized as the single most important characteristic of program behaviour, little work has been done in attempting to measure it. Such a measure has potential application in the validation of program behaviour models, in the evaluation of program restructuring methods (manual and automatic), in performance prediction, and in the analysis of locality-sensitive experiments such as those involving page replacement algorithms. An approach to measuring the intrinsic locality of a program is proposed. Underlying principles of this locality measure are discussed and validation experiments are described. The results obtained demonstrate that measures derived independently of any execution environment can be valid measures of program locality. A detailed analysis of the proposed measure of locality is carried out and the results add to the growing knowledge of the behaviour of programs.