System and method for calculating a checksum address while maintaining error correction information

• US 8,370,705 B1
• Filed: 09/23/2009
• Issued: 02/05/2013
• Est. Priority Date: 09/23/2009
• Status: Active Grant

• Current Assignee: NVIDIA Corporation
• Original Assignee: NVIDIA Corporation
• Inventors: Yu, Shu-Yi, Cameron, Kevin
• Primary Examiner(s): Bhatia, Ajay
• Assistant Examiner(s): MCMAHON, DANIEL F
• Application Number:
  US12/565,169
• Time in Patent Office: 1,231 Days
• Field of Search: None
• US Class Current: 714/758
• CPC Class Codes: H03M 13/09 Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit

Abstract

One or more embodiments of the invention set forth techniques to perform integer division using addition operations in order to provide address translation capabilities to a processor. The processor supports a memory that maintains checksum information such that address requests received by the processor need to be translated to a checksum address and an actual data address that accounts for use of portions of the memory to store checksum information. Once the checksum address and the actual data address are computed, the processor can confirm the integrity of the data stored in the actual data address and correct any errors if need be, based on the checksum information stored in the checksum address.

Claims

1. A computer-implemented method for calculating a checksum address in a computer system memory configured to maintain error correction information, the method comprising:

receiving a data request from a processor that includes a memory address associated with the requested data;

subdividing the memory address into a plurality of coefficients in a polynomial equation, wherein the polynomial equation expresses the memory address in an X-based number system;

calculating a quotient value based on a summation of concatenated coefficient values, wherein each concatenated coefficient value comprises a concatenation of a different coefficient included in the plurality of coefficients and corresponds to a position of the different coefficient in the polynomial equation;

computing the checksum address based on the quotient value and a value of X;

requesting error correction information from the computer system memory at a location corresponding to the checksum address; and

confirming an integrity of the requested data by analyzing error correction information stored at the checksum address.

2. The method of claim 1, wherein the polynomial equation is Σ

(A_iXⁱ), where i=0 to n and A_i represents one of the plurality of coefficients, the summation is (A₁)_X+(A₂A₂)_X+(A₃A₃A₃)_X+ . . . +(A_n . . . A_nA_n)_X, and the checksum address is computed by adding the value of (X−

1) to the product of the quotient value and the value of X.

3. The method of claim 2, wherein the X-based number system is a binary number system, wherein X is equal to 2^N.

4. The method of claim 3, wherein the computer system memory comprises a plurality of memory blocks, and the checksum information is stored in an X^th memory block for every (X−

1) memory blocks.

5. The method of claim 1, further comprising the steps of:

calculating a remainder value based on a summation of the plurality of coefficients;

computing a data address corresponding to the memory address based on the calculated remainder value;

requesting data from the computer system memory at a location corresponding to the data address; and

transmitting the data to the processor.

6. The method of claim 5, wherein the summation of the plurality of coefficients is (A₀)_X+(A₁)_X+ . . . +(A_n)_X and the data address is computed by adding the remainder value to the product of the quotient value and the value of X.

7. The method of claim 6, further comprising the step of re-computing the quotient value and the remainder value if the remainder value is greater than or equal to (X−

1).

8. A non-transitory computer-readable medium including instructions that, when executed by a processing unit, causes the processing unit to calculate a checksum address in a computer system memory configured to maintain error correction information by performing the steps of:

receiving a data request from a processor that includes a memory address associated with the requested data;

subdividing the memory address into a plurality of coefficients in a polynomial equation, wherein the polynomial equation expresses the memory address in an X-based number system;

calculating a quotient value based on a summation of concatenated coefficient values, wherein each concatenated coefficient value comprises a concatenation of a different coefficient included in the plurality of coefficients and corresponds to a position of the different coefficient in the polynomial equation;

computing the checksum address based on the quotient value and the value of X;

requesting error correction information from the computer system memory at a location corresponding to the checksum address; and

confirming an integrity of the requested data by analyzing error correction information stored at the checksum address.

9. The computer-readable medium of claim 8, wherein the polynomial equation is Σ

(A_iXⁱ), where i=0 to n and A_i represents one of the plurality of coefficients, the summation is (A₁)_X+(A₂A₂)_X+(A₃A₃A₃)_X+ . . . +(A_n . . . A_nA_n)_X, and the checksum address is computed by adding the value of (X−

1) to the product of the quotient value and the value of X.

10. The computer-readable medium of claim 9, wherein the X-based number system is a binary number system where X is 2^N.

11. The computer-readable medium of claim 10, wherein the computer system memory comprises a plurality of memory blocks and the checksum information is stored in an X^th memory block for every (X−

1) memory blocks.

12. The computer-readable medium of claim 9, wherein the processing unit further performs the steps:

calculating a remainder value based on a summation of the plurality of coefficients;

computing a data address corresponding to the memory address based on the calculated remainder value;

requesting data from the computer system memory at a location corresponding to the data address; and

transmitting the data to the processor.

13. The computer-readable medium of claim 12, wherein the summation of the plurality of coefficients is (A₀)_X+(A₁)_X+ . . . +(A_n)_X and the data address is computed by adding the remainder value to the product of the quotient value and the value of X.

14. An error correction code integrated circuit designed to calculate a checksum address in a computer system memory maintaining error correction information, the error correction code integrated circuit configured to:

receive a data request from a processor that includes a memory address associated with the requested data;

subdivide the memory address into a plurality of coefficients in a polynomial equation, wherein the polynomial equation expresses the memory address in an X-based number system;

calculate a quotient value based on a summation of concatenated coefficient values, wherein each concatenated coefficient value comprises a concatenation of a different coefficient included in the plurality of coefficients and corresponds to a position of the different coefficient in the polynomial equation;

compute the checksum address based on the quotient value and the value of X;

request error correction information from the computer system memory at a location corresponding to the checksum address; and

confirm an integrity of the requested data by analyzing error correction information stored at the checksum address.

15. The error correction code integrated circuit of claim 14, wherein the polynomial equation is Σ

(A_iXⁱ), where i=0 to n and A represents one of the plurality of coefficients, the summation is (A₁)_X+(A₂A₂)_X+(A₃A₃A₃)_X+ . . . +(A_n . . . A_nA_n)_X, and the checksum address is computed by adding the value of (X−

1) to the product of the quotient value and the value of X.

16. The error correction code integrated circuit of claim 15, wherein the X-based number system is a binary number system where X is 2^N.

17. The error correction code integrated circuit of claim 16, wherein the computer system memory comprises a plurality of memory blocks and the checksum information is stored in an X^th memory block for every (X−

1) memory blocks.

18. The error correction code integrated circuit of claim 14, further configured to:

calculate a remainder value based on summation of the plurality of coefficients;

compute a data address corresponding to the memory address based on the calculated remainder value;

request data from the computer system memory at a location corresponding to the data address; and

transmit the data to the GPU.

19. The error correction code integrated circuit of claim 18, wherein the summation of the plurality of coefficients is (A₀)_X+(A₁)_X+ . . . +(A_n)_X and the data address is computed by adding the remainder value to the product of the quotient value and the value of X.

20. The error correction code integrated circuit of claim 19, further configured to re-computing Q and R if R is greater than or equal to (X−

1).