Selecting hash values based on matrix rank

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.