Cache with access to a moving two-dimensional window

Details Cache with access to a moving two-dimensional window Cache with access to a moving two-dimensional window

1999-12-21

2002-04-23

Kim, Matthew (Department: 2186)

Electrical computers and digital processing systems: memory

Storage accessing and control

Hierarchical memories

C711S134000

Reexamination Certificate

active

06378046

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of The Invention
The invention relates to a method of caching data-items for access in a sliding window. The invention also relates to a device for applying said method.
2. Description of The Related Art
U.S. Pat. No. 5,602,984 discloses a device with a cache memory for caching pixel data from a camera image. The device contains a main memory for storing the entire image and a cache memory that stores a small subset of the image. A processor addresses the cache memory with row and column (X,Y) addresses of pixels. The cache memory translates the (X,Y) address to an address inside the cache and accesses the addressed data. If data is read for a (X,Y) location that is not in the cache, the data is retrieved from memory before it is returned to the processor.
In one example, the translation of (X,Y) addresses into cache addresses involves taking the X address and compounding it with a least significant part of the Y address. The check whether the addressed data is present in the cache is performed by comparing the most significant part of the Y address with a tag stored for the X address and the least significant part of the Y address.
During image processing, access to pixels of the image is often restricted to a sliding window of pixels in the image. Such a window is scanned a number of times, step by step, along a row (X) direction, each scan for a different column (Y) position. The cache stores pixel data for a number of rows of pixels. When the window moves along a number of X positions in the row direction, only pixel data at those X positions for the latest row is not in the cache memory. This data is retrieved and replaces the data at the same X positions for the earliest row in the cache memory. Thus, it is not necessary to retrieve all data freshly from the main memory in each scan along the row direction.
SUMMARY OF THE INVENTION
Among others, it is an object of the invention to reduce the amount of cache memory that is needed for storing data when access is restricted to a moving window in the image.
The method according to the invention comprises successively scanning of the window along a row direction, each scan at a successive position along a column direction; caching data-items from a bundle of rows of data-items in a cache memory; when the window moves along the row direction, making a location used for a first data-item from an earliest cached row of the bundle available for reuse; and retrieving a second data item for a latest cached row into the cache memory, characterized in that the earliest and the latest row are the earliest and latest row of the window, the position of the first data-item along the row direction of the matrix trailing the position of the second data-item along the row direction of the matrix. By making cache addresses available for reuse at a first X position in an earliest row, when data from a second X position in a latest row is retrieved into the cache, where the first position trails the second X position, the earliest and latest row may both be in the same window. This is in contrast to U.S. Pat. No. 5,602,984, where the earliest row should be outside the window, because data is replaced at an X-position for which new data is retrieved, so that this X-position is still part of the X-position range of the window.
In one embodiment, the data for the second X position is stored at the cache address used for the data at the first X position. Thus, a minimum of cache storage is affected by the window. However, this direct replacement is not necessary: if the cache is also used for caching other data besides the data for the window, making locations available for reuse provides room for these other purposes. In this case, the invention ensures that the data needed for the window occupies a minimal part of the cache. An associative cache, a set-associative cache or a direct mapped cache may be used for this purpose. In the case of a direct mapped cache, there may, of course, still be cache conflicts with the other purposes, but the invention minimizes these conflicts.
In an embodiment of the invention, the window advances by a block of at least two rows between successive scans along rows. In this case, a first group of data-items extending over a first group of rows, is made available for reuse and a second group of data-items extending over a second group of rows is retrieved, where the first and second groups have the size of a block and extend towards each other starting from the top and bottom of the window, respectively.
When the window does not extend for an integer number of blocks in the column (Y) direction, the data-items from the first group will have been retrieved at different times as part of different second groups.


REFERENCES:
patent: 5539873 (1996-07-01), Yoshimori et al.
patent: 5696698 (1997-12-01), Herluison et al.
patent: 6247084 (2001-06-01), Apostol, Jr. et al.
patent: 0877338 (1998-11-01), None

Affiliated with

Also associated with

Rating

Cache with access to a moving two-dimensional window 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 with access to a moving two-dimensional window, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cache with access to a moving two-dimensional window will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2864699