Prefetch prediction

Details Prefetch prediction Prefetch prediction

2004-06-17

2008-10-07

Bragdon, Reginald G. (Department: 2189)

Electrical computers and digital processing systems: memory

Storage accessing and control

Hierarchical memories

C711S204000, C711S213000, C712S226000, C717S157000

Reexamination Certificate

active

07434004

ABSTRACT:
Predicting prefetch data sources for runahead execution triggering read operations eliminates the latency penalties of missing read operations that typically are not addressed by runahead execution mechanisms. Read operations that most likely trigger runahead execution are identified. The code unit that includes those triggering read operations is modified so that the code unit branches to a prefetch predictor. The prefetch predictor observes sequence patterns of data sources of triggering read operations and develops prefetch predictions based on the observed data source sequence patterns. After a prefetch prediction gains reliability, the prefetch predictor supplies a predicted data source to a prefetcher coincident with triggering of runahead execution.

REFERENCES:
patent: 6560693 (2003-05-01), Puzak et al.
patent: 6799263 (2004-09-01), Morris et al.
patent: 7089399 (2006-08-01), Tetrick
patent: 2004/0128489 (2004-07-01), Wang et al.
patent: 2004/0154011 (2004-08-01), Wang et al.
patent: 2005/0027941 (2005-02-01), Wang et al.
patent: 2005/0149697 (2005-07-01), Enright et al.
Michel Dubois et al., “Assisted Execution,” CENG Technical Report 98-25, Oct. 1998, pp. 1-25.
Jonas Skeppstedt et al., “Hybrid Compiler/Hardware Prefetching for Multiprocessors Using Low-Overhead Cache Miss Trapps,” 8 pages, (pp. 298-305 ICPP 1997, Intl. Conference on Parallel Processing), Aug. 11-15, 1997.
Mark Horowitz et al., “Informing Memory Operations: Memory Performance Feedback Mechanisms and Their Applications,” ACM Transactions on Computer Systems, vol. 16, No. 2, May 1998, pp. 170-205.
Jamison D. Collins et al., “Dynamic Speculative Precomputation,” In the Proceedings of the 34thInternational Symposium on Microarchitecture, Dec. 2001, 12 pages.
Jamison D. Collins et al., “Speculative Precomputation: Long-range Prefetching of Delinquent Loads,” In the Proceedings of the 28thInternational Symposium on Computer Architecture, Jul. 2001, 12 pages.
James Dundas et al., “Improving Data Cache Performance by Pre-executing Instructions Under a Cache Miss,” Proc. 1997 ACM Int. Conf. on Supercomputing, Jul. 1997, 9 pages.
Murali Annavaram et al., “Data Prefetching by Dependence Graph Precomputation,” 28thIntl. Symposium on Computer Architecture (ISCA 2001), Jul. 2001, 10 pages.
Dongkeun Kim et al., “Design and Evaluation of Compiler Algorithms for Pre-Execution,” Appears in Proceedings of the Tenth International Conference on Architectural Support for Programming Languages and Operations Systems (ASPLOS-X), Oct. 2002, San Jose, CA, 12 pages.
Steve S.W. Liao et al., “Post-Pass Binary Adaptation for Software-Based Speculative Precomputation,” PLDI, Jun. 17-19, 2002, Berlin, Germany, pp. 117-128.
Martin Burtscher et al., “Static Load Classification for Improving the Value Predictability of Data-Cache Misses,” PLDI, Jun. 17-19, 2002, Berlin, Germany, pp. 222-233.
Trishul M. Chilimbi et al., “Dynamic Hot Data Stream Prefetching for General-Purpose Programs,” PLDI, Jun. 17-19, 2002, Berlin, Germany, pp. 199-209.
Onur Mutlu et al., “Runahead Execution: An Alternative to Very Large Instruction Windows for Out-of-order Processors,” Ninth Intl. Symposium on High Performance Computer Architecture, Feb. 2003, 12 pages.
Ron Dreslinski et al., “RunaPred: A Hybrid Runahead/Value Prediction Approach,” Apr. 18, 2003, 8 pages.
S. Vander Wiel et al., “A Survey of Data Prefetching Techniques,” Technical Report No.: HPPC-96-05, Oct. 1996, pp. 1-26.
Suleyman Sair et al., “A Decoupled Predictor-Directed Stream Prefetching Architecture,” pp. 1-32 (pp. 260-276, vol. 52, No. 3, in IEEE Transactions on Computers), Mar. 2003.
Doug Joseph et al., “Prefetching Using Markov Predictors,” pp. 1-11 (pp. 252-263, in International Conference on Computer Architecture, Preceedings of the 24thAnnual Intl. Symposium on Computer Architecture), Jun. 1-4, 1997.

Affiliated with

Also associated with

Rating

Prefetch prediction does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Prefetch prediction, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Prefetch prediction will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3988951