Advanced Micro Devices Corporation

Alexander Dodd Breslow

Nuwan S Jayasena

John Kalamatianos

Dong Ping Zhang

Amin Farmahini-Farahani

Systems, apparatuses, and methods for implementing flexible dictionary sharing techniques for caches are disclosed. A set-associative cache includes a dictionary for each data array set. When a cache line is to be allocated in the cache, a cache controller determines to which set a base index of the cache line address maps. Then, a selector unit determines which dictionary of a group of dictionaries stored by those sets neighboring this set would achieve the most compression for the cache line. This dictionary is then selected to compress the cache line. An offset is added to the base index of the cache line to generate a full index in order to map the cache line to the set corresponding to this chosen dictionary. The compressed cache line is stored in this set with the chosen dictionary, and the offset is stored in the corresponding tag array entry.

Flexible dictionary sharing for compressed caches

A method of maintaining a probabilistic filter includes, in response to receiving a key Kfor adding to the probabilistic filter, generating a fingerprint Fbased on applying a fingerprint hash function Hto the key K, identifying an initial bucket Bby selecting between at least a first bucket Bdetermined based on a first bucket hash function Hof the key Kand a second bucket Bdetermined based on a second bucket hash function Hof the key K, and inserting the fingerprint Finto the initial bucket B; and resizing the probabilistic filter. Resizing the probabilistic filter includes incrementing a resize counter value, determining a bucket B' for the fingerprint Fbased on a value of the fingerprint Fand the resize counter value, and inserting the fingerprint Finto the bucket B′ in the probabilistic filter.

System and method for self-resizing associative probabilistic hash-based data structures

A method includes, for each key of a plurality of keys, identifying from a set of buckets a first bucket for the key based on a first hash function, and identifying from the set of buckets a second bucket for the key based on a second hash function. An entry for the key is stored in a bucket selected from one of the first bucket and the second bucket. The entry is inserted in a sequence of entries in a memory block. A position of the entry in the sequence of entries corresponds to the selected bucket. For each bucket in the set of buckets, an indication of a number of entries in the bucket is recorded.

Cuckoo filters and cuckoo hash tables with biasing, compression, and decoupled logical sparsity

A data processing platform, method, and program product perform compression and decompression of a set of data items. Suffix data and a prefix are selected for each respective data item in the set of data items based on data content of the respective data item. The set of data items is sorted based on the prefixes. The prefixes are encoded by querying multiple encoding tables to create a code word containing compressed information representing values of all prefixes for the set of data items. The code word and suffix data for each of the data items are stored in memory. The code word is decompressed to recover the prefixes. The recovered prefixes are paired with their respective suffix data.

Semi-sorting compression with encoding and decoding tables

A hybrid mechanism for operating on a data item in connection with an associative structure combines first-fit and K-choice. The hybrid mechanism leverages advantages of both approaches by choosing whether to insert, retrieve, delete, or modify a data item using either first-fit or K-choice. Based on the data item, a function of the data item, and/or other factors such as the load statistics of the associative structure, one of either first-fit or K-choice is used to improve operation on the associative structure across a variety of different load states of the associative structure.

Hybrid first-fit K-choice insertions for hash tables, hash sets, approximate set membership data structures, and caches

A compute unit includes single-instruction-multiple-data (SIMD) lanes that implement a pipeline. The compute unit also includes a scheduler to schedule the SIMD lanes to apply a binary associative operation to pairs of elements associated with ordered sets of elements. Subsets of the SIMD lanes concurrently apply the binary associative operation to pairs of elements at different levels of upsweep trees associated with the ordered sets of elements. Application of the binary associative operation is used to perform a reduction operation or a scan operation on the ordered sets of elements. In the case of a scan operation, the scheduler schedules the SIMD lanes to concurrently apply the binary associative operation to pairs of elements at different levels of downsweep trees associated with the ordered sets of elements subsequent to applying the binary associative operation at different levels of the upsweep trees.

Spatial pipelining of software reductions and scans

A method and device generates a slab identifier and a hash function identifier in response to a memory allocation request with a request identifier and allocation size from a memory allocation requestor. The slab identifier indicates a memory region associated with a base data size and the hash function identifier indicates a hash function. The method and device provides a bit string including the slab identifier and the hash function identifier to the memory allocation requestor.

Implementing scalable memory allocation using identifiers that return a succinct pointer representation

A device includes an address translation table to, in each node of a set of nodes in the address translation table, store a key value and a hash function identifier, a hash engine coupled with the address translation table to, for each node in the set of nodes, calculate a hash result for the key value by executing a hash function identified by the hash function identifier, and a processing unit coupled with the hash engine to, in response to a request to translate a virtual memory address to a physical memory address, identify a physical memory region corresponding to the virtual memory address based on the calculated hash result for each node in the set of nodes.

Replacing pointers with hashing in tree-based page table designs

A data storage system performs partial compression and decompression of a set of memory items. The memory items each include a data block and a tag with a prefix making up at least part of the tag. The memory items are ordered based on the prefixes. A code word is created containing compressed information representing values of the prefixes for the set of memory items. The code word and block data for each of the memory items are stored in a memory. The code word is decompressed to recover the prefixes.

Compressing tags in software and hardware semi-sorted caches

Methods and mechanisms for managing data in a hash table are disclosed. A computing system includes a hash table configured to store data and hash management logic. In response to receiving a request to insert data into the hash table, the hash management logic is configured to generate a first hash value by applying a first hash function to the key of the key-value pair, and identify a first bucket within the hash table that corresponds to the first hash table. If the first bucket has a slot available, store the key-value pair in the slot. If the first bucket does not have a slot available, select a first slot of the first bucket for conversion to a remap entry, store the key-value pair in a second bucket, and store information associating the key-value pair with the second bucket in the remap entry.

Bucketized hash tables with remap entries

Systems, apparatuses, and methods for determining preferred memory page management policies by software are disclosed. Software executing on one or more processing units generates a memory request. Software determines the preferred page management policy for the memory request based at least in part on the data access size and data access pattern of the memory request. Software conveys an indication of a preferred page management policy to a memory controller. Then, the memory controller accesses memory for the memory request using the preferred page management policy specified by software.

Growing community of inventors

Sunnyvale, CA, United States of America

Alexander Dodd Breslow