Electrical computers and digital processing systems: memory – Address formation – Slip control – misaligning – boundary alignment
Reexamination Certificate
2000-04-19
2002-01-29
Yoo, Do Hyun (Department: 2185)
Electrical computers and digital processing systems: memory
Address formation
Slip control, misaligning, boundary alignment
C711S001000, C711S003000
Reexamination Certificate
active
06343354
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to data compression, and more particularly, to a data compression for a microprocessor system having a cache.
BACKGROUND OF THE INVENTION
Many modem technologies that use microprocessors or microcontrollers, such as hand-held electronic applications, require high performance processing power combined with highly efficient implementations to reduce system costs and space requirements. The use of instruction caches and data caches in order to improve performance is well known in the industry. In an effort to further reduce system size and cost, it is known to compress instruction data to minimize the amount of memory a system will need. Before an instruction contained in a compressed memory can be used, the information contained within that memory must be decompressed in order for the target data processor to execute.
A prior art method of handling the compression of data for use in a data processor system and the decompression of data for use by that data processor system uses the following steps: dividing the uncompressed program into separate cache blocks; compressing each cache block; and, compacting the individual compressed blocks into a memory. By breaking the program into individual cache blocks, where a cache block represents the number of words in each cache line, it is possible to efficiently compress the data associated with each cache block. Since modem data processing systems generally load an entire cache line at a time, it is possible to fill an entire cache line efficiently by knowing the starting address of a compressed cache block.
The prior art method requires the generation of a look-aside table (LAT). The look-aside table keeps track of which compressed address relates to which cache tag of the data processor. When the instruction pointer of the data processing system requires an address which is not resident within the instruction cache, it is necessary for the data processor system to determine where in compressed memory the required information resides. This information is maintained in the look-aside table stored in the system memory. When a cache miss occurs, the data processor system utilizes a cache refill engine to provide the appropriate information to the next available cache line. The cache refill engine parses the LAT to correlate the new cache tag to the compressed memory. This correlation describes the cache block address, in compressed memory, where the requested instruction resides. Once determined, the compressed memory is accessed, decompressed, and used to fill the appropriate cache line. The cache line containing the newly stored information maintains the original address tag as determined by the instruction pointer for its cache tag. The next time the instruction pointer requests information having the same address tag, a cache hit will occur, indicating the data is in the cache, and processing will continue in a normal fashion, provided the cache line has not been cleared.
In order to reduce the overhead of the cache refill engine having to search through the look-aside table in system memory, it is common for data processor systems to use a compressed cache look-aside buffer CLB.
The CLB maintains a list of recently translated address tags and their corresponding address information in compressed memory. By maintaining an on-chip CLB, overhead associated with parsing the LAT is avoided.
A disadvantage of the prior art system is that it requires a translation of the address tag into the appropriate compressed address location. This is accomplished at the expense of providing and maintaining a CLB, and increasing the complexity of the cache refill engine, which must search a LAT in order to determine the appropriate compressed memory location to access. In addition, it is necessary to perform these functions each time a cache miss occurs. As a result, each cache tag will be re-translated every time it is cleared out of the cache. Therefore, a method, and a data processor, that allows for execution of compressed programs while limiting physical overhead and execution time associated with translation is needed.
REFERENCES:
patent: 5235697 (1993-08-01), Steely, Jr. et al.
patent: 5574953 (1996-11-01), Rust et al.
patent: 5604909 (1997-02-01), Joshi et al.
patent: 5632024 (1997-05-01), Yajima et al.
patent: 5636352 (1997-06-01), Bealkowski et al.
patent: 5652852 (1997-07-01), Yokota
patent: 5787302 (1998-07-01), Hampapuram et al.
patent: 5826054 (1998-10-01), Jacobs et al.
Mauricio Breternitz Jr. et al., “Enhanced Compression Techniques to Simplify Progam Decompression and Execution”, 1997 IEEE, pp. 170-176.
Andrew Wolfe et al., “Executing Compressed Programs on An Embeded RISC Architecture”, 1992 IEEE, pp. 81-91.
Mark Taunton, “Compressed Executables: and Exercise in Thinking Small”, USENIX 1991 Conf., email address:mark@acorn.co.uk, pp. 385-403.
Fred Douglis, “The Compression Cache: Using On-line Compression to Extend Physical Memory”, 1993 USENIX Conf., pp. 1-16.
Stan Y. Liao et al., “Code Density Optimization for Embedded DSP Processors Using Data Compression Techniques”, Revised Version for Paper in ARVLSI 1995, 14 pgs.
Michael Kozuch et al., “Compression of Embedded System Programs”, 1994 IEEE, pp. 270-277.
Richard Aplin, “Improving External to Internal Cache Bandwidth Com”, email address: RichAp@codemast.demon.co.uk, 2 pgs.
Joseph H. Allen, “Improving External to Internal Cache Bandwidth With Com”, email address:jhallen@world.std.com, 2 pgs.
Breternitz, Jr. Mauricio
Smith Roger A.
Encarnacion Yamir
Motorola Inc.
Yoo Do Hyun
LandOfFree
Method and apparatus for compression, decompression, and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for compression, decompression, and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for compression, decompression, and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2828366