Cache optimization for programming loops

Details Cache optimization for programming loops Cache optimization for programming loops

1998-02-10

2001-08-28

Trammell, James P. (Department: 2722)

Data processing: software development, installation, and managem

Software program development tool

Translation of code

C717S152000, C717S152000, C711S100000, C703S006000, C703S016000

Reexamination Certificate

active

06282706

ABSTRACT:

CROSS-REFERENCE TO RELATED APPLICATIONS
This application is related U.S. Ser. No. 08/995,600 entitled “Mobile Communication System with Cross Compiler and Cross Linker” to Woolsey et al, U.S. Ser. No. 08/995,597, entitled Method and Apparatus for Providing Downloadable Functionality to an Embedded Coprocessor“to Brewer, U.S. Ser. No. 08/995,603, entitled Method and Apparatus for Extending Security Model to Native Code” to Brewer, and U.S. Ser. No. 08/995,606, entitled “Mobile Information Services Platform” to McMahon et al, all filed on Dec. 22,1997 and incorporated by reference herein.
STATEMENT OF FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT
Not Applicable
BACKGROUND OF THE INVENTION
1. Technical Field
This invention relates in general to electronic devices and, more particularly, to a method and apparatus for increasing the efficiency of a cache memory.
2. Description of the Related Art
Most modern day processing devices utilize a cache memory to increase processing speed. A cache memory acts as an intermediary between a processing circuit, such as a general purpose processor or a digital signal processor, and a memory bank, typically a dynamic random access memory (DRAM). The cache memory, typically a static random access memory (SRAM), is generally significantly smaller than the main memory bank (in terms of storage capacity), but significantly faster. The cache memory retains a portion of the data in the memory bank. When the processor accesses data, the cache memory is checked first to see if the data resides in the cache; if so, a “cache hit” ensues and data is taken from the cache memory which can supply the data at high speed responsive to the memory access request. On the other hand, if the data does not reside in the cache; if so, a “cache miss” ensues and data is taken from the memory bank. After a cache miss, the processor will generally be forced to wait for several clock cycles while the data is retrieved from the memory bank.
Cache architectures often have hit rates in the 90-95% rates, depending upon the application. The actual efficiency depends upon a number of factors, including the caching scheme employed, the size of the cache, and the application being run by the processor. Cache memories thus allow slower, less expensive, memory to store a large amount of data, while storing the portion of the data most likely to be accessed in the high speed cache memory.
While caches have significantly increased the speed at which data can be retrieved from the memory bank, cache architectures themselves can be slow relative to the capabilities of high speed processors. Further, a cache memory dissipates significant amounts of power, which is a particular concern to mobile electronic devices. Therefore, a need has arisen for a high speed, low power, cache architecture.
BRIEF SUMMARY OF THE INVENTION
In the present invention, a method and apparatus for executing a program in a processing circuit is shown, where the processing circuit includes a main memory and a cache memory and the cache memory comprises a plurality of data lines, each data line storing a plurality of data words. One or more programming loops are identified within the program. The loops are linked to the main memory such that a minimum number of cache lines are used to store the programming loops.
The present invention provides significant advantages over the prior art. First, significant amounts of energy can be saved by reducing tag searches and data array accesses by minimizing cache lines. Second, the speed can be significantly enhanced by reducing memory accesses. Third, cache misses can be reduced.


REFERENCES:
patent: 4701844 (1987-10-01), Thompson et al.
patent: 5303377 (1994-04-01), Gupta et al.
patent: 5452457 (1995-09-01), Alpert et al.
patent: 5530964 (1996-06-01), Alpert et al.
patent: 5546559 (1996-08-01), Kyushima et al.
patent: 5704053 (1997-12-01), Santhanam
patent: 5875464 (1999-02-01), Kirk
patent: 5889996 (2000-01-01), Adams
patent: 5892940 (1999-04-01), Mangelsdorf
patent: 5910900 (1999-06-01), Mangelsdorf
patent: 5920485 (1999-07-01), Mangelsdorf
patent: 5926395 (1999-07-01), Mangelsdorf
patent: 5949990 (1999-09-01), Mangelsdorf
patent: 5953531 (1999-09-01), Megiddo et al.
patent: 5956498 (1999-09-01), Mangelsdorf
patent: 6012836 (2000-01-01), Mangelsdorf
patent: 6129458 (2000-10-01), Waters et al.
Li, W.; “Compiler Cache Optimizations for Banded Matrix Problems”. ACM Digital Library[online]. Proceedings of the 9th ACM International Conference on Supercomputing, pp 21-30, Jul. 1995.*
Kennedy et al.; “Optimizing for Parallelism and Data Locality”. Proceedings of the 1992 International Conference on Supercomputing, pp 323-334, Jul. 1995.*
Yamada et al.; “Data Relocation and Prefetching for Programs with Large Data Sets”. IEEE/IEE Electronic Library[online], Proceedings of the 27th Annual International Symposium on Microarchitecture, pp. 118-127, Nov. 1994.*
Temam et al.; “Software assistance for data caches”. IEEE/IEE Electronic Library[onlin], Proceedings from the First IEEE Symposium on High-Performance Computer Architecture, pp. 154-163, Jan. 1995.*
Stolberg et al.; “Code positioning to reduce instruction cache misses in signal processing applications on multimedia RISC processors”. IEEE/IEE Electronic Library[online], International Conference on Acoustics, Speech, and Signal Processing, pp. 699-702, Apr. 1997.*
Gosmann et al.; “Code Reorganization for Instruction Caches”. IEEE/IEE Electronic Library[online], Proceedings of the Twenty-Sixth Hawaii International Conference on System Sciences, vol. 1, pp. 214-223, Jan. 1993.*
Kandemir, et al.; “A Compiler Algorithm for Optimizing Locality in Loop Nests”. ACM Digital Library[online], ICS 97, pp. 269-276, May 1997.*
Xia et al.,; “Instruction Prefetching of Systems Codes With Layout Optimized for Reduced Cache Misses”. Proceedings of the 23rd annual ISCA, pp. 271-282, May 1996.*
Carr et al.; “Compiler Optimizations for Improving Data Locality”. ACM Digital Library[online], vol. 29, No. 11, pp. 252-262, Nov. 1994.*
Lo et al,; “Improving Balanced Scheduling with Compiler Optimizations that Increase Instruction-Level Parallelism”. ACM Digital Library[online], Proceedings of the 1995 PLDI, vol. 30, No. 6, pp. 151-162, Jun. 1995.*
Nanri et al.; “Using Cache Optimizing Compiler for Managing Software Cache on Distributed Shared Memory System”. IEEE/IEE Electronic Library[online], 1997 Conference on High Performance Computing on the Information SuperHighway, pp. 312-318, Apr. 1997.*
Goto et al.; “Design and Performance of a Coherent Cache for Parallel Logic Programming Architectures”. ACM Digital Library[online], The 16th Annual ISCA, pp. 25-33, May 1989.*
Muchnick, S.; Advanced Compiler Design and Implementation. San Francisco, CA, Morgan Kaufmann Publishers, chapter 20, Nov. 1997.*
Kuroda et al.; “A Knowledge-Based Retargetable Compiler for Aplication Specific Signal Processors”. IEEE/IEE Electronic Library[online], 1989 IEEE ISCS, vol. 1, pp. 631-634, May 1989.*
Kuroda et al.; “A Knowledge-Based Compiler Enhancing DSP Internal Parallelism”. IEEE/IEE Electronic Library, 1991 IEEE ISCS, vol. 1, pp. 236-239, Jun. 1991.

Affiliated with

Also associated with

Rating

Cache optimization for programming loops does not yet have a rating. At this time, there are no reviews or comments for this patent.

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

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2505630