Modeling program predictability
Date
1998Author
Sazeides, YiannakisSmith, James E.
Publisher
IEEE Comp SocSource
Conference Proceedings - Annual International Symposium on Computer Architecture, ISCAProceedings of the 1998 25th Annual International Symposium on Computer Architecture
Pages
73-84Google Scholar check
Keyword(s):
Metadata
Show full item recordAbstract
Basic properties of program predictability - for both values and control - are defined and studied. We take the view that program predictability originates at certain points during a program's execution, flows through subsequent instructions, and then ends at other points in the program. These key components of predictability: generation, propagation, and termination are defined in terms of a model. The model is based on a graph derived from dynamic data dependences and a predictor. Using the SPEC95 benchmarks, we analyze the predictability phenomena both separately and in combination. Examples are provided to illustrate relationships between model-based characteristics and program constructs. It is shown that most predictability derives from program control structure and immediate values, not program input data. Furthermore, most predictability originates from a relatively small number of generate points. The analysis of obtained results suggests a number of ramifications regarding predictability and its use.