A data processing system includes a memory arrangement comprising a main memory, and a cache memory including a validity bit per storage location to indicate the validity of data stored therein. Cache performance is improved by a special read operation to eliminate storage of data otherwise purged by a replacement scheme. A special read removes cache data after it is read and does not write data read from the main memory into the cache. Additional operations include: normal read, where data is read from the cache memory if available, or, from main memory and written into cache; normal write, where data is written into main memory and the cache is interrogated, in the event of a hit, the data is either updated or effectively removed from the cache by invalidating its associated validity bit; and special write, where data is written both into main memory and the cache.
The present invention is an improved method and apparatus for selecting and replacing a block of a set of cache memory. The present invention provides for the weighted random replacement of blocks of cache memory by assigning indices to the memory blocks of a given set of cache memory. One of the assigned indices is then randomly selected by the present invention. The memory block of the given set to which the randomly selected index is assigned is replaced. The indices are assigned such that one or more blocks of the given set of cache memory have a high probability of replacement, whereas the other blocks of the given set of cache memory have significantly lower probabilities of replacement.
A parity checking arrangement for tag information in a cache memory. Parity generation is performed on the input tag in parallel with tag memory lookup and then compared with the parity stored in tag memory in order to speed operation. A single parity generator also may be used for writing into tag memory.
A two-level storage system selectively enables early discard of data from an upper level either immediately or at the end of a predetermined sequence of operation. A copy of data in such upper level is discarded immediately while altered copies of data are discarded at the end of the predetermined sequence of operations. Error conditions inhibit discarding altered data.
A prediction block address is generated from a current block address in accordance with a rule specified by a prediction mode signal. One of two cache memory banks is allocated as a current bank and the other is allocated as a prediction bank. When the current block address is stored in the prediction bank, the allocation of the current and prediction banks is reversed. When the prediction block address is not stored in the prediction bank, a data block specified by the prediction block address is block-read into the prediction bank.
Graphic data having a two-dimensional spread is divided into data blocks having a two-dimensional spread, for example, data blocks of 8.times.8 pixels, and with these data blocks as units, cache control is performed. A tag memory for making a decision as to the occurrence of a cache hit, stores therein a tag and a valid flag as well as a bank address in a cache memory at which the data block in question is stored. As a result, the relationship between each bank of the cache memory and the address in the tag memory is not fixed, which ensures efficient use of the cache memory even in situations where accesses concentrate in one particular memory area.
