Sorting memory address requests for parallel memory access using input address match masks
Apparatus identifies a set of M output memory addresses from a larger set of N input memory addresses containing at least one non-unique memory address. A comparator block performs comparisons of memory addresses from a set of N input memory addresses to generate a binary classification dataset that identifies a subset of addresses from the set of input addresses, where each address in the subset identified by the binary classification dataset is unique within that subset. Combination logic units receive a predetermined selection of bits of the binary classification dataset and sort its received predetermined selection of bits into an intermediary binary string in which the bits are ordered into a first group identifying addresses belonging to the identified subset, and a second group identifying addresses not belonging to the identified subset. Output generating logic selects between bits belonging to different intermediary binary strings to generate a binary output identifying a set of output memory addresses containing at least one address in the identified subset.
1. An apparatus configured to identify a set of M output memory addresses from a larger set of N input memory addresses, the apparatus comprising:
a comparator block configured to perform comparisons of memory addresses from a set of N input memory addresses to generate a classification dataset that identifies a subset of unique addresses from the set of input addresses;
a plurality of combination logic units, each configured to: receive a subset of data from the classification dataset and order the subset of data into two groups, wherein a first group identifies addresses belonging to the subset of unique addresses, and a second group identifies addresses not belonging to the subset of unique addresses; and
output generating logic configured to select between data belonging to different subsets of data to generate an output identifying at least one address in the subset of unique addresses.
2. An apparatus as claimed in claim 1 , wherein the classification dataset is a binary classification dataset, and wherein the subset of data from the classification data is a predetermined selection of bits.
3. An apparatus as claimed in claim 2 , wherein ordering the subset of data into two groups comprises sorting the predetermined selection of bits into an intermediary binary string.
4. An apparatus as claimed in claim 3 , in which the bits of the intermediary binary string are ordered such that the first group is formed of bits identifying addresses belonging to the subset of unique addresses, and the second group is formed of bits identifying addresses not belonging to the subset of unique addresses.
5. An apparatus as claimed in claim 2 , wherein the output generating logic is configured to generate a binary output identifying a set of output memory addresses containing at least one address in the subset of unique addresses.
6. An apparatus as claimed in claim 2 , wherein the binary classification dataset comprises N bits, each bit corresponding to a respective input memory address, the value of each bit indicating whether or not the corresponding memory address forms part of the subset of unique addresses.
7. An apparatus as claimed in claim 5 , wherein bit(s) of the binary output identifying the at least one address in the subset of unique addresses are unordered within the output.
8. An apparatus as claimed in claim 1 , wherein each address in the set of input addresses is associated with a validity identifier indicating whether the address is valid or invalid.
9. An apparatus as claimed in claim 1 , wherein each address in the set of input addresses that is not in the subset of unique addresses is at least one of: an invalid address; or equal to one of the addresses in the subset of unique addresses.
10. An apparatus as claimed in claim 1 , wherein the set of input memory addresses contains N addresses, and the comparator block is configured to: perform the comparison of input addresses by comparing each address a i in the set of input memory addresses with each subsequent address a j in the set of input memory addresses; or
perform the comparison of input addresses by comparing each address a i in the set of input memory addresses with each previous address a j in the set of input memory address.
11. An apparatus as claimed in claim 1 , wherein the comparator block is further configured to generate from the comparison of input addresses a match mask indicating, for each input address, which of the other input addresses match that input address, wherein the apparatus further comprises address matching logic configured to identify, using the match mask, each input address that matches the at least one address in the subset of unique addresses that is identified by the output.
12. An apparatus as claimed in claim 5 , wherein the binary output is an M-bit output, and the output generating logic is configured to select between bits belonging to different subsets of data to generate an M-bit binary output that identifies M addresses in the subset of unique addresses when the number of addresses in the subset of unique addresses is greater than or equal to M.
13. An apparatus as claimed in claim 3 , wherein each combination logic unit is configured to sort its received predetermined selection of bits into an intermediary binary string containing fewer bits than the number of the predetermined selection of bits received by that combination logic unit.
14. An apparatus as claimed in claim 3 , wherein each combination logic unit comprises:
a plurality of sort units each configured to:
receive a portion of the received predetermined selection of bits; and
sort the received portion of bits to group together the bits identifying addresses belonging to the identified subset to generate a preliminary binary string; and
one or more merge units, each of the one or more merge units being configured to receive a plurality of preliminary binary strings and to merge those preliminary binary strings to group together the bits from each received preliminary binary string that identify addresses belonging to the identified subset.
15. An apparatus as claimed in claim 5 , wherein the output generating logic comprises a plurality of selecting units, each configured to generate a respective bit of the binary output and each selecting unit is configured to select between a pair of bits from respective subsets of data to generate a bit of the binary output.
16. An apparatus as claimed in claim 15 , wherein each selecting unit is configured to output a bit that does not identify an address in the subset of unique addresses only in response to receiving a pair of bits that both do not identify an address in the subset of unique addresses.
17. An apparatus as claimed in claim 15 , wherein each selecting unit is associated with a pair of combination logic units and is configured to select between a pair of bits from respective subsets of data formed by those pair of combination logic units.
18. An apparatus as claimed in claim 3 , wherein each combination logic unit is configured to sort its received predetermined selection of bits into an intermediary binary string of M bits, wherein each selecting unit n is configured to select between a bit b n from a first intermediary binary string, and a bit b m from a second intermediary binary string, where n=1, . . . M, and m=M+1−n.
19. A method of identifying a set of M output memory addresses from a larger set of N input memory addresses comprising:
performing a comparison of memory addresses from a set of N input memory addresses to generate a classification dataset that identifies a subset of addresses from the set of unique input addresses;
at each of a plurality of combination logic units: receiving a subset of data from the classification dataset and order the subset of data into two groups wherein a first group identifies addresses belonging to the subset of unique addresses, and a second group identifies addresses not belonging to the subset of unique addresses; and
selecting between data belonging to different subsets of data to generate an output identifying at least one address in the subset of unique addresses.
20. A non-transitory computer readable storage medium having stored thereon a computer readable dataset description of an integrated circuit that, when processed in an integrated circuit manufacturing system, causes the integrated circuit manufacturing system to manufacture an apparatus configured to identify a set of M output memory addresses from a larger set of N input memory addresses, the apparatus comprising:
a comparator block configured to perform comparisons of memory addresses from a set of N input memory addresses to generate a classification dataset that identifies a subset of unique addresses from the set of input addresses;
a plurality of combination logic units, each configured to: receive a subset of data from the classification dataset and order the subset of data into two groups, wherein a first group identifies addresses belonging to the subset of unique addresses, and a second group identifies addresses not belonging to the subset of unique addresses; and
output generating logic configured to select between data belonging to different subsets of data to generate an output identifying at least one address in the subset of unique addresses.