Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
2000-12-11
2004-11-02
Bataille, Pierre (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S167000
Reexamination Certificate
active
06813693
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to computer-executable software applications and, more particularly, to improving the performance of computer-executable software applications.
BACKGROUND
As processor speeds continue to increase, memories providing data to the processor have become more and more of a bottleneck. In an effort to speed memory access, high speed caches were created to deliver data to processors. Generally, a cache only stores a fraction of the data stored in main memory. A cache “hit” occurs when the cache contains data the processor is requesting. A cache “miss” occurs when the cache does not contain data the processor is requesting. When a cache miss occurs, the data must be retrieved from main memory or disk. The time to fetch the data when a cache miss occurs, even from main memory, can be much greater than when a cache hit occurs. Increasing the percentage of cache hits and decreasing the number of cache misses, therefore, increases the overall performance of a computer system.
SUMMARY
The present invention provides a system and method for analyzing data access sequences of computer-executable software programs to determine data accessing patterns. Data address accesses of a software program are traced and compiled into Whole Program Data Accesses (WPDAs). The WPDAs are small compared to the raw data address traces and permit analysis without decompression. The WPDAs can then be used to efficiently discover higher-level data abstractions, such as hot data blocks. Hot data blocks may be viewed as frequently repeated sequences of consecutive data accesses. They serve as an effective abstraction for understanding and analyzing a program's dynamic data access behavior as well as exposing reference locality in a data address stream.
In one aspect, hot data blocks are used to perform memory layout optimizations dynamically by collocating in memory data that is frequently accessed sequentially. For example, data is often structured such that one data element is associated with another data element. An array of indexes, for example, may index an array of employee records. A program may retrieve an index and then retrieve the employee record associated with the index. By collocating the index array and the employee array, a memory allocator could, for example, place information such that an index and an employee record are located close to each other. By grouping data in this way, the memory allocator can increase cache hits and/or decrease the time needed to access the data.
In another aspect, hot data blocks are used to provide feedback to programmers. A software developer may see, for example, a frequently repeated pattern of data accesses. Based on this information, the software developer may make design and coding changes to group the data frequently accessed such that cache hits increase and/or memory performance improves.
In another aspect, hot data blocks are used during program execution by a pre-fetching mechanism. Based on the temporal data access information available from the WPDAs, the pre-fetching mechanism more effectively pre-fetches data to overcome certain access latencies which make some pre-fetches less helpful to the processor.
There are several advantages to the present invention. For example, it does not rely on system architecture to provide useful information. In other words, the invention can be practiced on various types of computers and operating systems, including personal computers, hand-held devices, multiprocessor systems, microprocessor-based or programmable consumer electronics, network PCs, minicomputers, mainframe computers, and the like. Embodiments of the invention are used to increase cache hits and memory performance with static tools such as compilers or dynamically as a program executes. The invention provides an efficient and useful way to represent large, hard to manage data access traces that would otherwise occupy gigabytes of storage.
REFERENCES:
patent: 5623608 (1997-04-01), Ng
patent: 5761718 (1998-06-01), Lin et al.
patent: 6098064 (2000-08-01), Pirolli et al.
patent: 6098154 (2000-08-01), Lopez-Aguado et al.
patent: 6170044 (2001-01-01), McLaughlin et al.
patent: 6282542 (2001-08-01), Carneal et al.
patent: 6360361 (2002-03-01), Larus et al.
Joon-Seo Yim et al, “Single Cycle Access Cache for the Misaligned Data and Instruction Prefetch”, IEEE, pp. 677-678, 1997.*
Majumdar et al., “Measurement and Analysis of Locality Phases in File Referencing Behaviour,”Proc. of the Joint Conference on Computer Performance Modelling, Measurement and Evaluation, 1986, pp. 180-192.
Callahan et al., “Data Cache Performance of Supercomputer Applications,”Pro. On Supercomputing '90, 1990, pp. 564-572.
Hall, “Call Path Profiling,”Proc. Of the 14thInt'l. Conference on Software Engineering, 1992, pp. 296-306.
Abraham et al., “Predictability of Load/Store Instruction Latencies,”Proc. Of the 26thAnnual Int'l Symposium on Microarchitecture, 1993, pp. 139-152.
Topham et al., “The Design and Performance of a Conflict-avoiding Cache,”Proc. Of the 30thAnnual IEEE/ACM Int'l. Symposium on Microarchitecture, 1997, pp. 71-80.
Mowry et al., “Predicting Data Cache Misses in Non-Numeric Applications Through Correlation Profiling,”Proc. of the 30thAnnual IEEE/ACM Int'l. Symposium on Microarchitecture, 1997, pp. 314-320.
Cheng et al., “Compiler-Directed Early Load-Address Generation,”Proc. of the 31stAnnual ACM/IEEE Int'l. Symposium on Microarchitecture, 1998, pp. 138-147.
Larus, “Whole Program Paths,”Proc. of the SIGPLAN '99 Conference on Programming Languages Design and Implementation(PLDI '99), 1999, 11 pages.
Bataille Pierre
Merchant & Gould P.C.
Microsoft Corporation
LandOfFree
System and method for the discovery and use of repetitively... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for the discovery and use of repetitively..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for the discovery and use of repetitively... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3291134