Accumulators corresponding to bins in memory

Patent metadata

Field	Value
Publication number	US-11768772-B2
Application number	US-202117644352-A
Country	US
Kind code	B2
Filing date	Dec 15, 2021
Priority date	Dec 15, 2021
Publication date	Sep 26, 2023
Grant date	Sep 26, 2023

Abstract

In some examples, a system includes a processing entity and a memory to store data arranged in a plurality of bins associated with respective key values of a key. The system includes a cache to store cached data elements for respective accumulators that are updatable to represent occurrences of the respective key values of the key, where each accumulator corresponds to a different bin of the plurality of bins, and each cached data element has a range that is less than a range of a corresponding bin of the plurality of bins. Responsive to a value of a given cached data element as updated by a given accumulator satisfying a criterion, the processing entity is to cause an aggregation of the value of the given cached data element with a bin value in a respective bin.

First claim

What is claimed is:

1. A system comprising:
one or more hardware processors;
a plurality of processing entities comprising a first processing entity and a second processing entity executable on the one or more hardware processors;
a memory to store data arranged in a plurality of bins associated with respective key values of a key, wherein the plurality of bins of the data in the memory are partitioned into a plurality of partitions of bins, the first processing entity owns a first partition of the plurality of partitions of bins, and the second processing entity owns a second partition of the plurality of partitions of bins; and
a cache to store first cached data elements for respective first accumulators, and second cached data elements for respective second accumulators, wherein the first cached data elements are part of a first accumulator structure associated with the first processing entity, and the second cached data elements are part of a second accumulator structure associated with the second processing entity,
wherein the first and second cached data elements are updatable to represent occurrences of the respective key values of the key, wherein each accumulator of the first and second accumulators corresponds to a different bin of the plurality of bins, and each cached data element of the first and second cached data elements has a range that is less than a range of a corresponding bin of the plurality of bins, and
wherein responsive to a value of a given cached data element as updated by a given accumulator of the first and second accumulators satisfying a criterion, a respective processing entity of the plurality of processing entities is to cause an aggregation of the value of the given cached data element with a bin value in a respective bin of the plurality of bins.

2. The system of claim 1 , wherein the given accumulator is to incrementally update the given cached data element as data records are received that contain a given key value corresponding to the given accumulator.

3. The system of claim 2 , wherein until the criterion is satisfied, the given accumulator is to incrementally update the given cached data element in the cache as the data records are received without accessing the respective bin in the memory.

4. The system of claim 1 , wherein the first and second accumulators are counters, and the first and second cached data elements are cached count values.

5. The system of claim 1 , wherein the respective processing entity is to:
map collections of key values of the key to respective sets, each set of the sets comprising a plurality of accumulators.

6. The system of claim 5 , wherein the plurality of accumulators of each set fit within a respective cache line of the cache.

7. The system of claim 5 , wherein the mapping of the collections of key values to the respective sets is based on applying a hash function to the key values in the collections of key values.

8. The system of claim 1 , wherein the cache is to further store tags associated with corresponding accumulators, each tag of the tags comprising an index referencing a bin of the plurality of bins.

9. The system of claim 1 , wherein the plurality of processing entities are to independently update respective accumulator structures in parallel.

10. The system of claim 1 , wherein the respective processing entity is to evict a collection of cached data elements in the cache to the data in the memory, according to an eviction criterion.

11. The system of claim 1 , wherein the aggregation of the value of the given cached data element with the bin value in the respective bin is performed without using any atomic operation to write to the memory.

12. A system comprising:
one or more hardware processors;
a plurality of processing entities comprising a first processing entity and a second processing entity executable on the one or more hardware processors;
a memory to store data arranged in a plurality of bins associated with respective key values of a key; and
a cache to store first cached data elements for respective first accumulators, and second cached data elements for respective second accumulators, wherein the first cached data elements are part of a first accumulator structure associated with the first processing entity, and the second cached data elements are part of a second accumulator structure associated with the second processing entity, wherein the first and second cached data elements are updatable to represent occurrences of the respective key values of the key, wherein each accumulator of the first and second accumulators corresponds to a different bin of the plurality of bins, and each cached data element of the first and second cached data elements has a range that is less than a range of a corresponding bin of the plurality of bins,
wherein the plurality of processing entities are to apply data analytics on input data records in parallel with one another, and the plurality of processing entities are to use respective accumulator structures that are private to respective processing entities of the plurality of processing entities so that the plurality of processing entities do not contend for access of any of the accumulator structures, wherein the accumulator structures include the first accumulator structure and the second accumulator structure, and
wherein responsive to a value of a given cached data element as updated by a given accumulator of the first and second accumulators satisfying a criterion, a respective processing entity of the plurality of processing entities is to cause an aggregation of the value of the given cached data element with a bin value in a respective bin of the plurality of bins.

13. The system of claim 12 , wherein the plurality of bins of the data in the memory are partitioned into a plurality of partitions of bins, wherein the first processing entity owns a first partition of the plurality of partitions of bins, and the second processing entity owns a second partition of the plurality of partitions of bins.

14. The system of claim 13 , wherein if the respective bin is in the second partition, the respective processing entity is to send the value of the given cached data element to the second processing entity to cause the second processing entity to aggregate the value of the given cached data element with the bin value in the respective bin.

15. A non-transitory machine-readable storage medium comprising instructions that upon execution cause a system to:
store a shared data structure in a memory, the shared data structure being shared by a plurality of processing entities and being arranged in a plurality of bins associated with respective key values of a key;
store, in a cache, accumulator structures for respective processing entities of the plurality of processing entities, wherein each accumulator structure of the accumulator structures includes cached data elements for respective accumulators, the cached data elements being updatable to represent occurrences of respective key values of the key, wherein each accumulator of the accumulators corresponds to a different bin of the plurality of bins in the shared data structure; and
responsive to a value of a given cached data element as updated by a given accumulator in a first accumulator structure of the accumulator structures satisfying a criterion, initiate, by a first processing entity of the plurality of processing entities, an addition of the value of the given cached data element to a respective bin of the plurality of bins in the memory without using any atomic write operation.

16. The non-transitory machin

Assignees

• Hewlett Packard Entpr Dev Lp

Inventors

• Menhusen Ryan D
• Emmot Darel Neal

Classifications

• G06F12/0848 Primary

  Partitioned cache, e.g. separate instruction and operand caches · CPC title

• G06F2212/608

  Details relating to cache mapping · CPC title

• G06F12/0864 Primary

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

• G06F2212/1024

  Latency reduction · CPC title

• G06F12/0895

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