Applications of and techniques for quickly computing a modulo operation by a Mersenne or a Fermat number

Patent metadata

Field	Value
Publication number	US-11455145-B2
Application number	US-202016941409-A
Country	US
Kind code	B2
Filing date	Jul 28, 2020
Priority date	Jul 28, 2020
Publication date	Sep 27, 2022
Grant date	Sep 27, 2022

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 distributes input data values among the slices in a cache memory even when the number of slices is not a power of two.

First claim

What is claimed is:

1. A computer-implemented method for performing a modulo operation, the method comprising:
performing, via an accumulation circuit, a first set of summations on an input value associated with the modulo operation to generate a first sum;
accessing, via a lookup and correction circuit, a correction value associated with a first portion of the first sum;
performing, via the lookup and correction circuit, a second set of summations on the correction value and a second portion of the first sum to generate a second sum; and
generating, via a test and correction circuit, a result of the modulo operation based on the second sum.

2. The computer-implemented method of claim 1 , wherein a divisor of the modulo operation is a Mersenne number, and wherein performing the first set of summations on the input value comprises:
dividing the input value into a set of coefficients; and
adding a first coefficient included in the set of coefficients to a second coefficient included in the set of coefficients.

3. The computer-implemented method of claim 1 , wherein a divisor of the modulo operation is a Mersenne number, and wherein accessing the correction value comprises retrieving the correction value from a lookup table, wherein the correction value represents a number to add to the second portion of the first sum.

4. The computer-implemented method of claim 1 , wherein a divisor of the modulo operation is a Mersenne number, and wherein performing the second set of summations on the correction value and the second portion of the first sum comprises adding the correction value to the second portion of the first sum.

5. The computer-implemented method of claim 1 , wherein a divisor of the modulo operation is a Fermat number, and wherein performing the first set of summations on the input value comprises:
dividing the input value into a first set of coefficients corresponding to even powers of two and a second set of the coefficients corresponding to odd powers of two; and
subtracting a first coefficient included in the second set of coefficients from a second coefficient included in the first set of coefficients.

6. The computer-implemented method of claim 1 , wherein a divisor of the modulo operation is a Fermat number, and wherein accessing the correction value comprises retrieving the correction value from a lookup table, wherein the correction value represents a number to subtract from the second portion of the first sum.

7. The computer-implemented method of claim 1 , wherein a divisor of the modulo operation is a Fermat number, and wherein performing the second set of summations on the correction value and the second portion of the first sum comprises subtracting the correction value from the second portion of the first sum.

8. The computer-implemented method of claim 1 , wherein generating the result of the modulo operation comprises:
determining that the second sum is less than a divisor of the modulo operation; and
setting the result to the second sum.

9. The computer-implemented method of claim 1 , wherein generating the result of the modulo operation comprises:
determining that the second sum is greater than or equal to a divisor of the modulo operation;
computing a difference by subtracting the divisor from the second sum; and
setting the result of the modulo operation to the difference.

10. A modulo operation generator, comprising:
an accumulation circuit that:
performs a first set of summations on an input value to generate a first sum;

a lookup and correction circuit that:
accesses a correction value associated with a first portion of the first sum, and
performs a second set of summations on the correction value and a second portion of the first sum to generate a second sum; and

a test and correct circuit that:
generates a result of a modulo operation based on the second sum.

11. The modulo operation generator of claim 10 , further comprising:
receiving a selection of a first divisor included in a plurality of divisors; and
configuring at least one of the accumulation circuit, the lookup and correction circuit, or the test and correct circuit to perform the modulo operation based on the first divisor.

12. The modulo operation generator of claim 11 , wherein the first divisor and a second divisor included in the plurality of divisors are Mersenne numbers.

13. The modulo operation generator of claim 11 , wherein the first divisor and a second divisor included in the plurality of divisors are Fermat numbers.

14. The modulo operation generator of claim 11 , wherein the first divisor is a Mersenne number and a second divisor included in the plurality of divisors is a Fermat number.

15. The modulo operation generator of claim 10 , wherein a divisor of the modulo operation is a Mersenne number, and wherein performing the first set of summations on the input value comprises:
dividing the input value into a set of coefficients; and
adding a first coefficient included in the set of coefficients to a second coefficient included in the set of coefficients.

16. The modulo operation generator of claim 10 , wherein a divisor of the modulo operation is a Mersenne number, and wherein accessing the correction value comprises retrieving the correction value from a lookup table, wherein the correction value represents a number to add to the second portion of the first sum.

17. The modulo operation generator of claim 10 , wherein a divisor of the modulo operation is a Mersenne number, and wherein performing the second set of summations on the correction value and the second portion of the first sum comprises adding the correction value to the second portion of the first sum.

18. The modulo operation generator of claim 10 , wherein a divisor of the modulo operation is a Fermat number, and wherein performing the first set of summations on the input value comprises:
dividing the input value into a first set of coefficients corresponding to even powers of two and a second set of the coefficients corresponding to odd powers of two; and
subtracting a first coefficient included in the second set of coefficients from a second coefficient included in the first set of coefficients.

19. The modulo operation generator of claim 10 , wherein a divisor of the modulo operation is a Fermat number, and wherein accessing the correction value comprises retrieving the correction value from a lookup table, wherein the correction value represents a number to subtract from the second portion of the first sum.

20. A system, comprising:
a processor that transmits a memory address and a data value to a memory management unit (MMU);
a cache memory that comprises a plurality of cache memory slices; and
the MMU that:
receives the memory address and the data value from the processor,
performs a first set of summations on the memory address to generate a first sum,
accesses a correction value associated with a first portion of the first sum,
performs a second set of summations on the correction value and a second portion of the first sum to generate a second sum,
generates a result of a modulo operation based on the second sum, wherein the result of the modulo operation identifies a first cache memory slice in the plurality of cache memory slices; and
stores the data value in the first cache memory slice.

Assignees

• Nvidia Corp

Inventors

• Chang Xiaofei
• Gautho Manuel

Classifications

• G06F7/50

  Adding; Subtracting (G06F7/483 - G06F7/491, G06F7/544 - G06F7/556 take precedence) · CPC title

• G06F7/727 Primary

  Modulo N arithmetic, with N being either (2**n)-1,2**n or (2**n)+1, e.g. mod 3, mod 4 or mod 5 (G06F7/728 takes precedence) · CPC title

• G06F7/535

  Dividing only · CPC title

• G06F7/729

  using representation by a residue number system · CPC title

• G06F15/781 Primary

  On-chip cache; Off-chip memory · CPC title