NVIDIA Corporation
APPLICATIONS OF AND TECHNIQUES FOR QUICKLY COMPUTING A MODULO OPERATION BY A MERSENNE OR A FERMAT NUMBER

Abstract:

Various embodiments include a modulo operation generator associated with a cache memory in a computer-based system. The modulo operation generator generates a first sum by performing an addition and/or a subtraction function on an input address. A first portion of the first sum is applied to a lookup table that generates a correction value. The correction value is then added to a second portion of the first sum to generate a second sum. The second sum is adjusted, as needed, to be less than the divisor. The adjusted second sum forms a residue value that identifies a cache memory slice in which the input data value corresponding to the input address is stored. By generating the residue value in this manner, the cache memory efficiently distributes input data values among the slices in a cache memory even when the number of slices is not a power of two.