Efficient explicit data prefetching analysis and code generation

Details Efficient explicit data prefetching analysis and code generation Efficient explicit data prefetching analysis and code generation

1995-05-18

1997-12-30

Lee, Thomas C.

Textiles: manufacturing

395705, G06F 945

Patent

active

057040532

ABSTRACT:
A compiler that facilitates efficient insertion of explicit data prefetch instructions into loop structures within applications uses simple address expression analysis to determine data prefetching requirements. Analysis and explicit data cache prefetch instruction insertion are performed by the compiler in a machine-instruction level optimizer to provide access to more accurate expected loop iteration latency information. Such prefetch instruction insertion strategy tolerates worst-case alignment of user data structures relative to data cache lines. Execution profiles from previous runs of an application are exploited in the insertion of prefetch instructions into loops with internal control flow. Cache line reuse patterns across loop iterations are recognized to eliminate unnecessary prefetch instructions. The prefetch insertion algorithm is integrated with other low-level optimization phases, such as loop unrolling, register reassociation, and instruction scheduling. An alternative embodiment of the compiler limits the insertion of explicit prefetch instructions to those situations where the lower bound on the achievable loop iteration latency is unlikely to be increased as a result of the insertion.

REFERENCES:
patent: 5193167 (1993-03-01), Sites et al.
patent: 5214766 (1993-05-01), Liu
patent: 5377336 (1994-12-01), Eickemeyer et al.
patent: 5396604 (1995-03-01), DeLano et al.
patent: 5537620 (1996-07-01), Breternitz, Jr.
Chen, T-F, et al., A Performance Study Of Software & Hardware Data Prefetching Schemes, Apr. 1, 1994, Computer Architecture News, vol. 22, No. 2, pp. 223-232.
Abraham, S G, et al., Predictability Of Load/Store Instruction Latencies, Dec. 1-3, 1993, Proceedings Of The Annual International Symposium On MicroArchitect, Austin, pp. 139-152.
Chi, C-H, et al., Compiler Driven Data Cache Prefetching for High Performance Computers, Proceedings of the regional 10 Annual International Conference, Tenco, Singapore, Aug. 22-26, 1994, vol. 2, No. Conf. 9, pp. 274-278.
Callahan, ., et al., Software Prefetching, ACM Sigplan Notices, vol. 26, No. 4, Apr. 8, 1991, pp. 40-52.
Mowry, T C, et al., Design and Evaluation of a Compiler Algorithm for Prefetching, ACM Sigplan Notices, vol. 27, No. 9, Sep. 1, 1992, pp. 62-73.
Callahan, David, et al., "Software Prefetching", 1991, Association for Computing Machinery.
Klaiber, Alexander C., et al., "An Architecture for Software-Controlled Data Prefetching", May 1991, Int'l Symposium on Computer Architecture.
Chen, William Y., et al., "Data Access Microarchitectures for Superscalar Processors with Compiler-Assisted Data Prefetching", Proceedings of the 24th Int'l Symposium on Microarchitecture.
Mowry, Todd C., et al., "Design and Evaluation of a Compiler Algorithm for Prefetching", 1992, Association for Computing Machinery.
Johnson, Eric E., "Working Set Prefetching for Cache Memories".
Gornish, Edward H., et al., "Compiler-Directed Data Prefetching in Multiprocessors with Memory Hierarchies", 1990, Association for Computing Machinery.
Gupta, Anoop, et al., "Comparative Evaluation of Latency Reducing and Tolerating Techniques", 1991, Association for Computing Machinery.
Fu, John W. C., et al., "Data Prefetching in Multiprocessor Vector Cache Memories", 1991, Association for Computing Machinery.
Chen, Tien-Fu, et al., "Reducing Memory Latency via Non-blocking and Prefetching Cahces", 1992, Association for Computing Machinery.

Affiliated with

Also associated with

Rating

Efficient explicit data prefetching analysis and code generation does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Efficient explicit data prefetching analysis and code generation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient explicit data prefetching analysis and code generation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-212888