Cache system

Claim 1

A cache memory system comprising: (a) a main computer memory for storing addressable data; (b) a computer processor having a primary memory addresser; (c) a high-speed cache memory for storing subsets of the data of the main computer memory for fast access by the processor; and (d) a cache controller for retrieving addressed data from the cache memory when present therein and duplicating other data in the main computer memory and the cache memory, the system being programmed for maintaining an ordered list of cache items, each item being one subset of the data and having a score and a size associated therewith, items having lowest scores being selectively removed from the list for accommodation of freshly addressed subsets of the data, and wherein each score is positively correlated to a frequency of access of the item and negatively correlated with the size of the item, the size being proportional to a number of memory addresses required for holding that subset of the data.

Claim 8

A method for rapidly accessing repetitively accessed addressable data and other addressable data from a main memory and a smaller and faster cache memory, comprising the steps of: (a) forming an index of previously accessed items of data; (b) selectively adding items corresponding to newly addressed data to the index; (c) copying the newly addressed data of the added items from the main memory into the cache memory; (d) determining an item score being positively correlated with a frequency of access of the item and negatively correlated with a size of the corresponding item; (e) selectively deleting from the index items having lowest scores for accommodating the added items of newly addressed data; and (f) accessing addressed data from the cache memory when the addressed data corresponds to items present in the index.

Claim 9

A method for rapidly accessing repetitively accessed addressable data and other addressable data from a main memory and a smaller and faster cache memory, comprising the steps of: (a) forming an index of previously accessed items of data; (b) selectively adding items corresponding to newly addressed data to the index; (c) copying the newly addressed data of the added items from the main memory into the cache memory; (d) determining an item score being positively correlated with a frequency of access of the item and negatively correlated with a size of the corresponding item; (e) selectively deleting from the index items having lowest scores for accommodating the added items of newly addressed data; and (f) accessing addressed data from the cache memory when the addressed data corresponds to items present in the index.

Claim 13

A method for rapidly accessing repetitively accessed addressable data and other addressable data from a main memory and a smaller and faster cache memory, comprising the steps of: (a) forming a linked list of previously accessed items of data; (b) selectively adding items corresponding to newly addressed data to the linked list; (c) copying the newly accessed data of the added items from the main memory into the cache memory; (d) determining a total item size as a sum of a number of memory locations occupied by the requested data and a number of memory locations associated with the linked list for the requested data; (e) determining a frequency of access of the item by incrementing a frequency count upon each request for the item; (f) scaling the frequency count; (g) dividing the scaled frequency count by the total size to form a score; (h) ordering the linked list by locating items having higher scores ahead of items having lower scores; (i) selectively deleting from the list items having lowest scores for accommodating the added items of newly addressed data; and (j) accessing addressed data from the cache memory when the addressed data corresponds to items present in the list.

Claim 14

A method for rapidly accessing repetitively accessed addressable data and other addressable data from a main memory and a smaller and faster cache memory, comprising the steps of: (a) forming a linked list of previously accessed items of data; (b) selectively adding items corresponding to newly addressed data to the linked list; (c) copying the newly accessed data of the added items from the main memory into the cache memory; (d) determining a total item size as a sum of a number of memory locations occupied by the requested data and a number of memory locations associated with the linked list for the requested data; (e) determining a frequency of access of the item by incrementing a frequency count upon each request for the item; (f) scaling the frequency count; (g) dividing the scaled frequency count by the total size to form a score; (h) ordering the linked list by locating items having higher scores ahead of items having lower scores; (i) selectively deleting from the list items having lowest scores for accommodating the added items of newly addressed data; and (j) accessing addressed data from the cache memory when the addressed data corresponds to items present in the list.