Selecting hash values based on matrix rank

• US 9,690,715 B2
• Filed: 09/03/2014
• Issued: 06/27/2017
• Est. Priority Date: 09/03/2014
• Status: Active Grant

• Current Assignee: NVIDIA Corporation
• Original Assignee: NVIDIA Corporation
• Inventors: Van Dyke, James M.
• Primary Examiner(s): Bataille, Pierre-Michel
• Application Number:
  US14/475,951
• Publication Number:
  US 20160062910A1
• Time in Patent Office: 1,028 Days
• CPC Class Codes: G06F 12/0207 with multidimensional access, e.g. row/column, matrix
• CPC Class Codes: G06F 12/0864 using pseudo-associative means, e.g. set-associative or hashing
• CPC Class Codes: G06F 12/0875 with dedicated cache, e.g. instruction or stack
• CPC Class Codes: G06F 12/1018 involving hashing techniques, e.g. inverted page tables
• CPC Class Codes: G06F 12/1408 by using cryptography for digital transmission H04L9/00
• CPC Class Codes: G06F 2212/1016 Performance improvement
• CPC Class Codes: G06F 2212/452 Instruction code
• CPC Class Codes: G06F 2212/455 Image or video data
• CPC Class Codes: G06F 2212/601 Reconfiguration of cache memory
• CPC Class Codes: G06F 2212/651 Multi-level translation tables

Abstract

One embodiment of the present invention includes a hash selector that facilitates performing effective hashing operations. In operation, the hash selector creates a transformation matrix that reflects specific optimization criteria. For each hash value, the hash selector generates a potential hash value and then computes the rank of a submatrix included in the transformation matrix. Based on this rank in conjunction with the optimization criteria, the hash selector either re-generates the potential hash value or accepts the potential hash value. Advantageously, the optimization criteria may be tailored to create desired correlations between input patterns and the results of performing hashing operations based on the transformation matrix. Notably, the hash selector may be configured to efficiently and reliably incrementally generate a transformation matrix that, when applied to certain strides of memory addresses, produces a more uniform distribution of accesses across caches lines than previous approaches to memory addressing.

Claims

1. A computer-implemented method for performing hashing operations in connection with one or more memory addressing operations, the method comprising:

generating a first potential hash value;

assigning a first set of entries included in a transformation matrix to the first potential hash value;

computing a first rank of a first sub-matrix included in the transformation matrix, wherein the first sub-matrix includes the first set of entries included in the transformation matrix;

based on the first rank, determining that the first potential hash value does not satisfy a first optimization criterion;

generating a second potential hash value;

re-assigning the first set of entries included in the transformation matrix to the second potential hash value;

re-computing the first rank of the first sub-matrix included in the transformation matrix, wherein the first sub-matrix further includes the reassigned first set of entries included in the transformation matrix;

based on the first rank, determining that the second potential hash value satisfies the first optimization criterion; and

performing one or more hashing operations in connection with at least one memory addressing operation based on the transformation matrix to map a first multi-bit value to a second multi-bit value.

2. The method of claim 1, wherein determining that the first potential hash value does not satisfy the first optimization criterion comprises determining that the first rank is less than a minimum rank.

3. The method of claim 2, wherein at least one of the number of rows and the number of columns included in the first sub-matrix is equal to the minimum rank.

4. The method of claim 1, further comprising determining that the second potential hash value satisfies the first optimization criterion.

5. The method of claim 1, further comprising:

generating a third potential hash value;

assigning a second set of entries included in the transformation matrix to the third potential hash value;

computing a second rank of a second sub-matrix included in the transformation matrix, wherein the second sub-matrix includes the first and second set of entries included in the transformation matrix;

based on the second rank, determining that the third potential hash value does not satisfy the first optimization criteria;

generating a fourth potential hash value; and

re-assigning the second set of entries included in the transformation matrix to the fourth potential hash value.

6. The method of claim 1, wherein generating the first potential hash value comprises randomly generating the first potential hash value.

7. The method of claim 1, further comprising:

generating a third potential hash value;

determining that the third potential hash value does not satisfy a second optimization criterion; and

discarding the third potential hash value without determining the rank of any sub-matrix that includes the third potential hash value.

8. The method of claim 1, wherein the first multi-bit value comprises an input memory address, and the second multi-bit value comprises a swizzled memory address.

9. The method of claim 8, further comprising identifying a cache line included in a memory cache and an offset within the cache line based on the swizzled memory address.

10. A non-transitory computer-readable storage medium including instructions that, when executed by a processing unit, cause the processing unit to map multi-bit values in connection with one or more memory addressing operations, by performing the steps of:

generating a first potential hash value;

assigning a first set of entries included in a transformation matrix to the first potential hash value;

computing a first rank of a first sub-matrix included in the transformation matrix, wherein the first sub-matrix includes the first set of entries included in the transformation matrix;

based on the first rank, determining that the first potential hash value does not satisfy a first optimization criterion;

generating a second potential hash value;

re-assigning the first set of entries included in the transformation matrix to the second potential hash value; and

re-computing the first rank of the first sub-matrix included in the transformation matrix, wherein the first sub-matrix further includes the reassigned first set of entries included in the transformation matrix;

based on the first rank, determining that the second potential hash value satisfies the first optimization criterion; and

performing one or more hashing operations in connection with at least one memory addressing operation based on the transformation matrix to map a first multi-bit value to a second multi-bit value.

11. The non-transitory computer-readable storage medium of claim 10, wherein determining that the first potential hash value does not satisfy the first optimization criterion comprises determining that the first rank is less than a minimum rank.

12. The non-transitory computer-readable storage medium of claim 11, wherein at least one of the number of rows and the number of columns included in the first sub-matrix is equal to the minimum rank.

13. The non-transitory computer-readable storage medium of claim 10, further comprising determining that the second potential hash value satisfies the first optimization criterion.

14. The non-transitory computer-readable storage medium of claim 10, further comprising:

generating a third potential hash value;

assigning a second set of entries included in the transformation matrix to the third potential hash value;

computing a second rank of a second sub-matrix included in the transformation matrix, wherein the second sub-matrix includes the first and second set of entries included in the transformation matrix;

based on the second rank, determining that the third potential hash value does not satisfy the first optimization criteria;

generating a fourth potential hash value; and

re-assigning the second set of entries included in the transformation matrix to the fourth potential hash value.

15. The non-transitory computer-readable storage medium of claim 10, wherein generating the first potential hash value comprises randomly generating the first potential hash value.

16. The non-transitory computer-readable storage medium of claim 10, further comprising:

generating a third potential hash value;

determining that the third potential hash value does not satisfy a second optimization criterion; and

discarding the third potential hash value without determining the rank of any sub-matrix that includes the third potential hash value.

17. The non-transitory computer-readable storage medium of claim 10, wherein the first multi-bit value comprises an input memory address, and the second multi-bit value comprises a swizzled memory address.

18. The non-transitory computer-readable storage medium of claim 17, further comprising identifying a cache line included in a memory cache and an offset within the cache line based on the swizzled memory address.

19. A system configured to perform hashing operations in connection with one or more memory addressing operations, the system comprising:

a first memory that includes a first transformation matrix;

a hash selector unit coupled to the first memory and configured to;

generate a first potential hash value;

assign a first set of entries included in the transformation matrix to the first potential hash value;

compute a first rank of a first sub-matrix included in the transformation matrix, wherein the first sub-matrix includes the first set of entries included in the transformation matrix;

based on the first rank, determine that the first potential hash value does not satisfy a first optimization criterion;

generate a second potential hash value; and

re-assign the first set of entries included in the transformation matrix to the second potential hash value; and

re-compute the first rank of the first sub-matrix included in the transformation matrix, wherein the first sub-matrix further includes the reassigned first set of entries included in the transformation matrix;

based on the first rank, determine that the second potential hash value satisfies the first optimization criterion; and

an address swizzling unit coupled to the first memory and configured to;

perform one or more hashing operations in connection with at least one memory addressing operation based on the transformation matrix to map a first multi-bit value to a second multi-bit value.

20. The system of claim 19, wherein determining that the first potential hash value does not satisfy the first optimization criterion comprises determining that the first rank is less than a minimum rank.

21. A system configured to perform swizzling operations based on a transformation matrix in connection with one or more memory addressing operations, the system comprising:

a first memory that includes the transformation matrix, wherein the transformation matrix includes a first sub-matrix, the rank of the first sub-matrix is at least a minimum rank, and the minimum rank corresponds to swizzling operations that generate outputs that exhibit a desired uniformity across a plurality of resources;

a plurality of resources that are coupled to the first memory; and

a swizzling unit that applies the transformation matrix to the plurality of resources in connection with at least one memory addressing operation.