An Investigation of Structural Locality in the Memory Referencing Behavior of Computer Programs

Abstract

The nature of structural locality as defined by same stack distance access is investigated in this thesis. The question is whether structural locality can be characterized as an inherent type of behavior. The results revealed that structural locality is strongly influenced by a program's design and phase of execution. Entropy measurements revealed that the predictiveness of structural locality is also influenced by program design. A Markov model was refined to capture the characteristics of structural locality that were measured. Trace synthesis demonstrated some success in reproducing same stack distance run distributions when the model had enough states to encompass the entire distribution. Entropy measurements on the synthesized traces showed that the predictiveness of structural locality was not solely due to the same stack distance behavior. A similar investigation on first-time memory referencing behavior revealed the same types of results.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 1992
Accession Number
ADA258998

Entities

People

  • Michael E. Bletzinger

Organizations

  • Air Force Institute of Technology

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Artificial Intelligence
  • Central Processing Units
  • Chi Square Test
  • Classification
  • Compilers
  • Computer Programming
  • Computer Programs
  • Computers
  • Engineering
  • Expert Systems
  • Markov Chains
  • Markov Models
  • Measurement
  • Operating Systems
  • Probability
  • Standards

Readers

  • Computational Modeling and Simulation
  • Theoretical Analysis.