# US 2022/0035599 A1 · Applications of and techniques for quickly computing a modulo operation by a mersenne or a fermat number > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2022/0035599 A1 - Document ID: US20220035599A1 - Status: Published application - Kind: A1 - Application number: 16/941,409 - Filed: 2020-07-28 - Published: 2022-02-03 - Earliest claimed: 2020-07-28 - Assignees: NVIDIA Corporation - Applicants: Nvidia Corporation - Inventors: XIAOFEI CHANG; MANUEL GAUTHO - Web page: https://patentgrep.com/patent/US20220035599A1 ## CPC - G06F 7/727: {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)} - G06F 7/50: Adding; Subtracting (G06F7/483 - G06F7/491, G06F7/544 - G06F7/556 take precedence) - G06F 7/535: Dividing only - G06F 7/729: {using representation by a residue number system} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## 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. ## Claims ### Claim 1 A computer-implemented method for performing a modulo operation, the method comprising: performing a first set of summations on an input value associated with the modulo operation to generate a first sum; accessing a correction value associated with a first portion of the first sum; performing a second set of summations on the correction value and a second portion of the first sum to generate a second sum; and generating a result of the modulo operation based on the second sum. ### Claim 2 (depends on 1) 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. ### Claim 3 (depends on 1) 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 correction value from a lookup table, wherein the correction value represents a number to add to the second portion of the first sum. ### Claim 4 (depends on 1) 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. ### Claim 5 (depends on 1) 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. ### Claim 6 (depends on 1) 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. ### Claim 7 (depends on 1) 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. ### Claim 8 (depends on 1) The computer-implemented method of claim 1, wherein performing the adjustment on the second sum comprises: determining that the second sum is less than a divisor of the modulo operation; and setting the residue value to the second sum. ### Claim 9 (depends on 1) The computer-implemented method of claim 1, wherein performing the adjustment on the second sum 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 residue value to the difference. ### Claim 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 the modulo operation based on the second sum. ### Claim 11 (depends on 10) 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. ### Claim 12 (depends on 10) The modulo operation generator of claim 10, wherein the first divisor and a second divisor included in the plurality of divisors are Mersenne numbers. ### Claim 13 (depends on 10) The modulo operation generator of claim 10, wherein the first divisor and a second divisor included in the plurality of divisors are Fermat numbers. ### Claim 14 (depends on 10) The modulo operation generator of claim 10, wherein the first divisor is a Mersenne number and a second divisor included in the plurality of divisors is a Fermat number. ### Claim 15 (depends on 10) 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. ### Claim 16 (depends on 10) 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 correction value from a lookup table, wherein the correction value represents a number to add to the second portion of the first sum. ### Claim 17 (depends on 10) 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. ### Claim 18 (depends on 10) 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. ### Claim 19 (depends on 10) 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. ### Claim 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 the 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.