Software-assisted data prefetching algorithms.

by Chi-sum, Ho.Thesis (M.Phil.)--Chinese University of Hong Kong, 1995.Includes bibliographical references (leaves 110-113).Abstract --- p.iAcknowledgement --- p.iiiChapter 1 --- Introduction --- p.1Chapter 1.1 --- Overview --- p.1Chapter 1.2 --- Cache Memories --- p.1Chapter 1.3 --- Improving Cache Performance --- p.3Chapter 1.4 --- Improving System Performance --- p.4Chapter 1.5 --- Organization of the dissertation --- p.6Chapter 2 --- Related Work --- p.8Chapter 2.1 --- Cache Performance --- p.8Chapter 2.2 --- Non-Blocking Cache --- p.9Chapter 2.3 --- Cache Prefetching --- p.10Chapter 2.3.1 --- Hardware Prefetching --- p.10Chapter 2.3.2 --- Software-assisted Prefetching --- p.13Chapter 2.3.3 --- Improving Cache Effectiveness --- p.22Chapter 2.4 --- Other Techniques to Reduce and Hide Memory Latencies --- p.25Chapter 2.4.1 --- Register Preloading --- p.25Chapter 2.4.2 --- Write Policies --- p.26Chapter 2.4.3 --- Small Specialized Cache --- p.26Chapter 2.4.4 --- Program Transformation --- p.27Chapter 3 --- Stride CAM Prefetching --- p.30Chapter 3.1 --- Introduction --- p.30Chapter 3.2 --- Architectural Model --- p.32Chapter 3.2.1 --- Compiler Support --- p.33Chapter 3.2.2 --- Hardware Support --- p.35Chapter 3.2.3 --- Model Details --- p.39Chapter 3.3 --- Optimization Issues --- p.39Chapter 3.3.1 --- Eliminating Reductant Prefetching --- p.40Chapter 3.3.2 --- Code Motion --- p.40Chapter 3.3.3 --- Burst Mode --- p.44Chapter 3.3.4 --- Stride CAM Overflow --- p.45Chapter 3.3.5 --- Effects of Loop Optimizations --- p.46Chapter 3.4 --- Practicability --- p.50Chapter 3.4.1 --- Evaluation Methodology --- p.51Chapter 3.4.2 --- Prefetch Accuracy --- p.54Chapter 3.4.3 --- Stride CAM Size --- p.56Chapter 3.4.4 --- Software Overhead --- p.60Chapter 4 --- Stride Register Prefetching --- p.67Chapter 4.1 --- Motivation --- p.67Chapter 4.2 --- Architectural Model --- p.67Chapter 4.2.1 --- Stride Register --- p.69Chapter 4.2.2 --- Compiler Support --- p.70Chapter 4.2.3 --- Prefetch Bits --- p.72Chapter 4.2.4 --- Operation Details --- p.77Chapter 4.3 --- Practicability and Optimizations --- p.78Chapter 4.3.1 --- Practicability on NASA7 Benchmark Programs --- p.78Chapter 4.3.2 --- Optimization Issues --- p.81Chapter 4.4 --- Comparison Between Stride CAM and Stride Register Models --- p.84Chapter 5 --- Small Software-Driven Array Cache --- p.87Chapter 5.1 --- Introduction --- p.87Chapter 5.2 --- Cache Pollution in MXM --- p.88Chapter 5.3 --- Architectural Model --- p.89Chapter 5.3.1 --- Operation Details --- p.91Chapter 5.4 --- Effectiveness of Array Cache --- p.92Chapter 6 --- Conclusion --- p.96Chapter 6.1 --- Conclusion --- p.96Chapter 6.2 --- Future Research: An Extension of the Stride CAM Model --- p.97Chapter 6.2.1 --- Background --- p.97Chapter 6.2.2 --- Reference Address Series --- p.98Chapter 6.2.3 --- Extending the Stride CAM Model --- p.100Chapter 6.2.4 --- Prefetch Overhead --- p.109Bibliography --- p.110Appendix --- p.114Chapter A --- Simulation Results - Stride CAM Model --- p.114Chapter A.l --- Execution Time --- p.114Chapter A.1.1 --- BTRIX --- p.114Chapter A.1.2 --- CFFT2D --- p.115Chapter A.1.3 --- CHOLSKY --- p.116Chapter A.1.4 --- EMIT --- p.117Chapter A.1.5 --- GMTRY --- p.118Chapter A.1.6 --- MXM --- p.119Chapter A.1.7 --- VPENTA --- p.120Chapter A.2 --- Memory Delay --- p.122Chapter A.2.1 --- BTRIX --- p.122Chapter A.2.2 --- CFFT2D --- p.123Chapter A.2.3 --- CHOLSKY --- p.124Chapter A.2.4 --- EMIT --- p.125Chapter A.2.5 --- GMTRY --- p.126Chapter A.2.6 --- MXM --- p.127Chapter A.2.7 --- VPENTA --- p.128Chapter A.3 --- Overhead --- p.129Chapter A.3.1 --- BTRIX --- p.129Chapter A.3.2 --- CFFT2D --- p.130Chapter A.3.3 --- CHOLSKY --- p.131Chapter A.3.4 --- EMIT --- p.132Chapter A.3.5 --- GMTRY --- p.133Chapter A.3.6 --- MXM --- p.134Chapter A.3.7 --- VPENTA --- p.135Chapter A.4 --- Hit Ratio --- p.136Chapter A.4.1 --- BTRIX --- p.136Chapter A.4.2 --- CFFT2D --- p.137Chapter A.4.3 --- CHOLSKY --- p.137Chapter A.4.4 --- EMIT --- p.138Chapter A.4.5 --- GMTRY --- p.139Chapter A.4.6 --- MXM --- p.139Chapter A.4.7 --- VPENTA --- p.140Chapter B --- Simulation Results - Array Cache --- p.141Chapter C --- NASA7 Benchmark --- p.145Chapter C.1 --- BTRIX --- p.145Chapter C.2 --- CFFT2D --- p.161Chapter C.2.1 --- cfft2dl --- p.161Chapter C.2.2 --- cfft2d2 --- p.169Chapter C.3 --- CHOLSKY --- p.179Chapter C.4 --- EMIT --- p.192Chapter C.5 --- GMTRY --- p.205Chapter C.6 --- MXM --- p.217Chapter C.7 --- VPENTA --- p.22