Identifying information in an array of data storage elements arranged as multiple partitions using partition identifiers

Patent metadata

Field	Value
Publication number	US-10055151-B2
Application number	US-201615256942-A
Country	US
Kind code	B2
Filing date	Sep 6, 2016
Priority date	Sep 28, 2015
Publication date	Aug 21, 2018
Grant date	Aug 21, 2018

Abstract

A data storage device comprises an array of data storage elements arranged as multiple partitions each comprising two or more data storage elements, each data storage element being associated with a respective identifier which identifies a data item currently stored by that data storage element; a predictor configured to compare, for each partition, information derived from the identifiers associated with the data storage elements of that partition with information derived from an identifier associated with the required data item, to identify a subset of partitions that do not store the required data item; and a comparator configured to compare identifiers associated with data storage elements of one or more partitions with the identifier associated with the required data item, wherein any partitions in the subset of partitions are excluded from the test group of partitions.

First claim

The invention claimed is:

1. A data storage device comprising:
an array of data storage elements arranged as multiple partitions each comprising two or more data storage elements, each data storage element being associated with a respective identifier which identifies a data item currently stored by that data storage element;
a predictor configured to compare, for each partition, a partition hash value derived from the identifiers associated with the data storage elements of that partition with a hash value derived from an identifier associated with a required data item, to identify a subset of partitions that do not store the required data item; and
a comparator configured to compare identifiers associated with data storage elements of one or more partitions in a test group of partitions with the identifier associated with the required data item, wherein any partitions in the subset of partitions are excluded from the test group of partitions,
wherein the partition hash value derived from the identifiers associated with the data storage elements of a partition comprises a logical combination of respective hash values derived from each of the identifiers associated with the data storage elements of that partition.

2. A device according to claim 1 , in which the comparator is configured to compare identifiers associated with each of the test group of partitions in turn with the identifier associated with the required data item, until either all of the partitions' identifiers in the test group of partitions have been compared or a match has been detected between an identifier associated with a data storage element of one of the partitions in the test group of partitions and the identifier associated with the required data item.

3. A device according to claim 1 , in which:
the predictor is configured to detect those bits of the hash value derived from the required data item which have a particular bit value and to detect a match when corresponding bit positions of the partition hash value derived from the identifiers associated with the data storage elements of a partition under test have that particular bit value; and
the logical combination of the respective hash values is a combination such that when any bit position in any of the respective hash values has the particular bit value, that bit position of the partition hash value is assigned the particular bit value.

4. A device according to claim 1 , in which the predictor is configured to store the information derived from the identifiers associated with the data storage elements of each partition.

5. A device according to claim 4 , comprising control logic, responsive to a change in the data items stored by the data storage elements of a partition, to generate replacement information derived from the identifiers associated with the data storage elements of that partition, for storage by the predictor.

6. A device according to claim 1 , in which:
the data storage device is a cache memory; and
the identifier associated with a data item is a tag comprising a portion of that data item's memory address.

7. A device according to claim 6 , in which:
each data storage element comprises a group of data storage locations configured to store multiple data items having a most significant portion of their memory addresses in common; and
the tag comprises at least a part of the most significant portion of the memory addresses.

8. A device according to claim 6 , comprising control logic configured to obtain a required data item from a main memory or other level of cache hierarchy and to store that data item in one of the data storage elements in response to a detection by the comparator that none of the identifiers associated with partitions detected by the predictor match the identifier associated with the required data item.

9. A device according to claim 1 , in which the array of data storage elements is fully associative such that any data item can be stored by any of the data storage elements.

10. A data storage device comprising:
means for storing data as an array of data storage elements arranged as multiple partitions each comprising two or more data storage elements, each data storage element being associated with a respective identifier which identifies a data item currently stored by that data storage element;
means for comparing, for each partition, a partition hash value derived from the identifiers associated with the data storage elements of that partition with a hash value derived from an identifier associated with a required data item, to identify a subset of partitions that do not store the required data item; and
means for comparing identifiers associated with data storage elements of one or more partitions in a test group of partitions with the identifier associated with the required data item, wherein any partitions in the subset of partitions are excluded from the test group of partitions,
wherein the partition hash value derived from the identifiers associated with the data storage elements of a partition comprises a logical combination of respective hash values derived from each of the identifiers associated with the data storage elements of that partition.

11. A data storage method comprising:
storing data as an array of data storage elements arranged as multiple partitions each comprising two or more data storage elements, each data storage element being associated with a respective identifier which identifies a data item currently stored by that data storage element;
comparing, for each partition, a partition hash value derived from the identifiers associated with the data storage elements of that partition with a hash value derived from an identifier associated with a required data item, to identify a subset of partitions that do not store the required data item; and
comparing identifiers associated with data storage elements of one or more partitions in a test group of partitions with the identifier associated with the required data item, wherein any partitions in the subset of partitions are excluded from the test group of partitions,
wherein the partition hash value derived from the identifiers associated with the data storage elements of a partition comprises a logical combination of respective hash values derived from each of the identifiers associated with the data storage elements of that partition.

Assignees

• Advanced Risc Mach Ltd

Inventors

• Grubisic Roko
• PERSSON Häkan Lars-Göran
• Kouveli Georgia

Classifications

• G06F12/0895

  of parts of caches, e.g. directory or tag array · CPC title

• G06F12/0866

  for peripheral storage systems, e.g. disk cache · CPC title

• G06F12/0864 Primary

  using pseudo-associative means, e.g. set-associative or hashing · CPC title

• G06F12/0802

  Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches · CPC title

• G06F12/00 Primary

  Accessing, addressing or allocating within memory systems or architectures (digital input from, or digital output to record carriers, e.g. to disk storage units, G06F3/06) · CPC title