Method and apparatus for detecting and correcting anomalies in field-programmable gate arrays using CRCs for anomaly detection and parity for anomaly correction

• US 6,101,624 A
• Filed: 07/20/1998
• Issued: 08/08/2000
• Est. Priority Date: 01/21/1998
• Status: Expired due to Term

• Current Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Cheng, Joe-Ming, Singh, Shanker
• Primary Examiner(s): Chung, Phung M.
• Application Number:
  US09/119,705
• Time in Patent Office: 750 Days
• Field of Search: 714/736, 714/724, 714/758, 714/752, 714/746, 714/48
• US Class Current: 714/736
• CPC Class Codes: G06F 11/1008 in individual solid state devices G06F11/1004 takes precedence

Abstract

A method and means for detecting and correcting anomalies in a RAM-based FPGA by comparing CRC residues over portions of the RAM-stored connection bitmap with prestored residues derived from uncorrupted copies of the same bitmap portions. A mismatch selectively invokes either error reporting to the chip only, error reporting and immediate verification testing of counterpart FPGA chip functions, or error reporting, parity-based correction of the words in error, reprogramming of the chip functions with the corrected words, and verification testing.

Claims

1. A method for detecting and correcting anomalies in a field-programmable gate array (FPGA), said FPGA having a memory for storing a word-organized directed graph of networked logic functions;

a configurable chip including logic functions, paths, and connection elements; and

an arrangement coupling the memory and the chip for programming the connection elements to constitute a physically realizable image of the directed graph, the method comprising the steps of;

(a) forming parity images of groups of words of the graph in the memory and storing said parity images in a failure-independent part of the same or other memory;

(b) accessing a set of words from the memory, calculating an ECC residue, and comparing the ECC residue with an ECC signature previously derived from an error-free copy of the same set of words;

(c) in the event of a comparison match, either repeating steps (b)-(d) over another set of words or terminating the test; and

(d) in the event of a comparison mismatch, invoking a step selected from a set of steps consisting of (1) notification only of error, (2) error notification and immediate verification testing of counterpart logic chip functions, and (3) error notification, parity image correction of the words in error, reprogramming of the chip functions utilizing the corrected graph, and verification testing of the counterpart logic chip functions.

2. In a field-programmable gate array (FPGA) having a word-organized memory for storing indicia of a directed graph of input, output, and logical functions;

a configurable chip including logic functions, input and output ports, and connectable routers thereamong; and

an arrangement for writing path connections on the configurable chip as a physically realized image of the directed graph, a method for ascertaining graph error and correcting the configurable chip on said FPGA comprising the steps of;

(a) forming parity images of counterpart groups of N words of indicia and storing said parity images in a failure-independent portion of the same or other memory;

(b) reading selected indicia from the memory, computing a first linear block error correction code (ECC) residue over the indicia, and comparing the first residue with a first signature ECC residue, said first signature residue being previously derived from an error-free copy of the selected indicia;

(c) in the event of a comparison match between the first ECC residue and the first signature, either repeating step (b) with respect to other selected indicia from the memory or terminating the test; and

(d) in the event of a comparison mismatch between the first ECC residue and the first signature, correcting said graph in memory including said selected indicia utilizing the parity images, and rewriting at least the corrected selected indicia associated with the mismatch on the configurable chip.

3. The method according to claim 2, wherein step (d) further comprises the steps of:

(d1) logically combining the parity image with N-1 error-free words of an N word identified parity group or groups; and

(d2) applying the logically combined indicia to the chip and causing the chip to be reconfigured accordingly.

4. The method according to claim 2, wherein the method further comprises the steps subsequent to rewriting the chip of:

(e) applying a predetermined data pattern to selected ones of the chip functions inclusive of the path connections physically realized from the rewritten indicia, and computing a second ECC residue over the selected function output;

(f) comparing the second residue with a second signature residue, said second signature residue being derived from an error-free copy of the same chip functions subject to the same data pattern; and

(g) in the event of a mismatch between the second residue and second signature in step (f), isolating any nested subinterval of time to a predetermined resolution within which an error, erasure, or fault would occur by recursively repeating steps (e)-(g) over subsets of the same data pattern.

5. The method according to claim 2, wherein the linear block error detection code in ascertaining and comparing residues and signatures is one selected from a set consisting of a cyclic redundancy check (CRC) code, a Reed-Solomon code, and a BCH code.

6. In a field-programmable gate array (FPGA) having a memory for storing indicia of a directed graph of input, output, and logical functions;

a configurable chip including logic functions, input and output ports, and connectable routers thereamong; and

an arrangement for writing path connections on the configurable chip as a physically realized image of the directed graph, a method for performing function checks and isolating detected anomalies within a nested time interval on said FPGA comprising the steps of;

(a) reading selected indicia from the memory, computing a first linear block error correction code (ECC) residue over the indicia, and comparing the first residue with a first signature ECC residue, said first residue previously derived from an error-free copy of the indicia;

(b) in the event of a comparison match between the first ECC residue and the first signature, either repeating step (a) with respect to other selected indicia or terminating the test;

(c) in the event of a comparison mismatch between the first ECC residue and the first signature, ascertaining function on said chip operative as an image counterpart to the selected indicia of the graph, applying a predetermined data pattern to the ascertained function, computing a second ECC residue over the ascertained function output, and comparing the second ECC residue with a second signature ECC residue, said second signature residue being derived from the output of an error-free copy of the ascertained function subject to the same data pattern; and

(d) responsive to a comparison mismatch between the second residue and second signature in step (c), isolating any nested subinterval of time to a predetermined resolution within which an error, erasure, or fault would occur by recursively repeating steps (c)-(d) over subsets of the same data pattern.

7. The method according to claim 6, wherein the linear block error detection code in ascertaining and comparing residues and signatures is one selected from a set consisting of a cyclic redundancy check (CRC) code, a Reed-Solomon code, and a BCH code.

8. The method according to claim 6, wherein the memory-stored indicia are word organized, the method further comprising the steps of:

(e) forming parity images of counterpart groups of N words of indicia and storing said parity images in a failure-independent portion of the same or other memory; and

(f) in the event of a comparison mismatch between the first residue and the first signature, logically combining the parity image with N-1 error-free words of an N word identified parity group or groups, applying the logically combined indicia to the chip, and causing the chip to be reconfigured accordingly.

9. The method according to claim 8, wherein the polynomial for CRC determination is one selected from the set expressed in Galois field arithmetic consisting of (x¹⁶ +x¹² +x⁵ +1) and (x³² +x²⁶ +x²³ +x²² +x¹⁶ +x¹² +x¹¹ +x¹⁰ +x⁸ +x⁷ +x⁵ +x⁴ +x² +1).

10. The method according to claim 8, wherein the nested subinterval size and predetermined resolution is determined by the degree of the highest term in the CRC polynomial, and further wherein the recursively repeating steps (c)-(d) constitute a recursive binary search to locate the error, erasure, or fault within the nested subinterval of predetermined resolution.

11. In a field-programmable gate array (FPGA) having a memory for storing indicia of a directed graph of input, output, and logical functions;

a configurable chip including logic functions, input and output ports, and connectable routers thereamong; and

an arrangement for writing path connections on the configurable chip as a physically realized image of the directed graph, a method for performing function checks and isolating detected anomalies within a nested time interval on said FPGA, comprising the steps of;

(a) reading selected indicia from the memory, computing a first cyclic redundancy code (CRC) residue over the indicia, and comparing the first residue with a first signature CRC residue previously derived from an error-free copy of the indicia;

(b) in the event of a comparison match between the first CRC residue and the first CRC signature, either repeating step (a) with respect to other selected indicia or terminating the test;

(c) in the event of a comparison mismatch between the first CRC residue and the first CRC signature,

(1) ascertaining such function on said chip operative as an image counterpart to the selected indicia of the graph,

(2) applying a predetermined data pattern to the ascertained function,

(3) computing a second CRC residue over the ascertained function output, and

(4) comparing the second CRC residue with a second signature CRC residue, said second signature CRC residue being derived from the output of an error-free copy of the same functions subject to the same data pattern; and

(d) responsive to a comparison mismatch between the second residue and second signature in step (c), isolating any nested subinterval of time to a predetermined resolution within which an error, erasure, or fault would occur by recursively repeating steps (c)-(d) over subsets of the same data pattern.

12. A field-programmable gate array (FPGA) comprising:

a memory for storing word-organized indicia of a directed graph of input, output, and logical functions and for storing linear block error correction code (ECC) signature residues over counterpart ones of the indicia previously derived from an error-free copy of counterpart ones of the indicia;

a configurable chip including logic functions, input and output ports, and connectable routers thereamong;

an arrangement for programming (writing) path connections on the configurable chip, said path connections being a physically realized image of the directed graph; and

a logic arrangement including a finite state machine (FSM) for reading selected indicia from the memory, for computing a first ECC residue over the selected indicia, for comparing the first ECC residue with the memory-stored counterpart signature residue, and

(1) responsive to a comparison match for either selecting other indicia for processing or terminating the test, and

(2) responsive to a comparison mismatch for selecting a remedial response from a set consisting of (a) providing signal indication to said writing arrangement and chip to isolate or suspend such functions on said chip operative as an image counterpart to the selected indicia of the graph;

(b) providing said signal indication and for performing verification testing on said counterpart functions;

or (c) providing signal indication, correcting said words in error, reprogramming said chip with the corrected words of the graph, and verification testing of the reprogrammed chip.

13. An article of manufacture comprising a machine-readable memory having stored therein a plurality of processor-executable control program steps for ascertaining graph error in indicia of a directed graph of input, output, and logical functions normally stored in the memory portion of a field-programmable gate array (FPGA) and for correcting a configurable chip on said FPGA including logic functions, input and output ports, and connectable routers thereamong, the FPGA further including the arrangement for writing path connections on the configurable chip as a physically realized image of the directed graph, said control program steps include:

(a) a control program step for forming parity images of counterpart groups of N words of indicia and for storing said parity images in a failure-independent portion of this angle or other memory;

(b) a control program step for reading selected indicia from the memory, for computing a first linear block error correction code (ECC) residue over the indicia, and for comparing the first residue with a first signature of ECC residue, said first signature residue being previously derived from an error-free copy of the selected indicia;

(c) a control program step operative in the event of a comparison match between the first ECC residue and the first signature for either repeating execution of the control program step (b) or for terminating the test; and

(d) a control program step operative in the event of a comparison mismatch between the first ECC residue and the first signature for correcting the graph in memory including the selected indicia utilizing the parity images, and writing at least the corrected selected indicia associated with the mismatch on the configurable chip.