Value prediction is a speculative technique to break true data dependencies by predicting uncomputed values based on history. Previous research focused on exploiting two types of value locality (computation-based and context-based) in the local value history, which is the value sequence produced by the same instruction that is being predicted. Besides local value history, value locality also exists in global value history, which is the value sequence produced by all dynamic instructions according to their execution order. In this thesis, a new type of value locality, computational locality in global value history is studied. A prediction scheme, called gDiff, is designed to exploit one special and most common case of this computational model, the stride-based computation, in global value history. Experiments show that there exists very strong stride type of locality in global value sequences and ideally the gDiff predictor can achieve 73% prediction accuracy for all value producing instructions without any hybrid scheme, much higher than local stride and local context prediction schemes. However, the ability to realistically exploit locality in global value history is greatly challenged by the value delay issue, i.e., the correlated value may not be available when the prediction is being made. The value delay issue is studied in an out-of-order (OOO) execution pipeline model and the gDiff predictor is improved by maintaining an order in the value queue and utilizing local stride predictions when global values are unavailable to avoid the value delay problem. This improved predictor, called hgDiff, demonstrates 88% accuracy and 69% prediction coverage on average, outperforming a local stride predictor by 2% higher accuracy and 13% higher coverage.
| Identifer | oai:union.ndltd.org:NCSU/oai:NCSU:etd-05122002-121743 |
| Date | 24 May 2002 |
| Creators | Bodine, Jill T. |
| Contributors | Dr. Eric Rotenberg, Dr. Greg Byrd, Dr. Thomas Conte |
| Publisher | NCSU |
| Source Sets | North Carolina State University |
| Language | English |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | http://www.lib.ncsu.edu/theses/available/etd-05122002-121743/ |
| Rights | unrestricted, I hereby certify that, if appropriate, I have obtained and attached hereto a written permission statement from the owner(s) of each third party copyrighted matter to be included in my thesis, dissertation, or project report, allowing distribution as specified below. I certify that the version I submitted is the same as that approved by my advisory committee. I hereby grant to NC State University or its agents the non-exclusive license to archive and make accessible, under the conditions specified below, my thesis, dissertation, or project report in whole or in part in all forms of media, now or hereafter known. I retain all other ownership rights to the copyright of the thesis, dissertation or project report. I also retain the right to use in future works (such as articles or books) all or part of this thesis, dissertation, or project report. |
Page generated in 0.0025 seconds