Data store and method of allocating data to the data store

A data store for storing data comprising:

• data array means for storing data, comprising a plurality of data entry means for storing data values;
• tag array means for storing tags, comprising a plurality of tag entry means for storing tag values for tracking which data values are stored in the data array means;
• and
• control means for controlling allocation of a data value to said data array means and a corresponding tag value to said tag array means to:
• (a) allocate said data value to a selected data entry means of a corresponding data set of N data entry means of said data array means, where N is an integer which is less than the total number of data entry means of said data array means, said corresponding data set selected based on an address of said data value, wherein said data value cannot be allocated to a data entry means not in said corresponding data set;
• (b) allocate said corresponding tag value to a selected tag entry means of a corresponding tag set of M tag entry means of said tag array means, where M is an integer and M<N, said corresponding tag set selected based on said address of said data value, wherein said tag value cannot be allocated to a tag entry means not in said corresponding tag set;
• and
• (c) store in said selected tag entry means a pointer identifying which data entry means of said corresponding data set is said selected data entry means,
• wherein in response to an access request for accessing from said data array means a target data value identified by a target address, said control means is configured to perform a first tag lookup for reading the tag values from each of the corresponding tag set of M tag entry means selected based on said target address, and to determine whether the data array means stores said target data value by comparing a tag portion of the target address with each of said read tag values,
• when none of the read tag values corresponds to said tag portion of said target address, then said control means is configured to perform said allocation for allocating said target data value to said data array means and said tag portion of said target address to said tag array means, and
• said selected data entry means already stores a data value which needs to be written back to memory and the tag entry means corresponding to the data value already stored in said selected data entry is from a different tag set to the tag set read in said first tag lookup, then said control means is configured perform a second tag lookup for said different tag set to read the tag value corresponding to said data value already stored in said selected data entry means.

A method of allocating a data value to a data store comprising a data array comprising a plurality of data entries for storing data values and a tag array comprising a plurality of tag entries for storing tag values for tracking which data values are stored in the data array;

• the method comprising:
• in response to an access request for accessing from said data array a target data value identified by a target address, performing a first tag lookup for reading the tag values from each of a corresponding tag set of M tag entries selected based on said target address, where M is an integer, and determining whether the data array stores said target data value by comparing a tag portion of the target address with each of said read tag values, and
• when none of the read tag values corresponds to said tag portion of said target address:
• allocating said target data value to a selected data entry of a corresponding data set of N data entries of said data array, where N is an integer which is less than the total number of data entries of said data array and M<N, and said corresponding data set is selected based on said target address of said target data value, wherein said target data value cannot be allocated to a data entry not in said corresponding data set;
• allocating said tag portion of the target address to a selected tag entry of the corresponding tag set of M tag entries of said tag array, where said corresponding tag set is selected based on said target address of said target data value, wherein said tag value cannot be allocated to a tag entry not in said corresponding tag set;
• and
• storing in said selected tag entry a pointer identifying which data entry of said corresponding data set is said selected data entry,
• wherein when said selected data entry already stores a data value which needs to be written back to memory and the tag entry corresponding to the data value already stored in said selected data entry is from a different tag set to the tag set read in said first tag lookup, a second tag lookup is performed for said different tag set to read the tag value corresponding to said data value already stored in said selected data entry.