System, method and apparatus for error correction in multi-processor systems

• US 8,930,753 B2
• Filed: 10/28/2011
• Issued: 01/06/2015
• Est. Priority Date: 10/28/2010
• Status: Expired due to Fees

• Current Assignee: Data Device Corporation (Transdigm Group Incorporated)
• Original Assignee: Maxwell Technologies Incorporated (Tesla Inc.)
• Inventors: Hillman, Robert, Williamson, Gale
• Primary Examiner(s): GUYTON, PHILIP A
• Application Number:
  US13/284,647
• Publication Number:
  US 20120117419A1
• Time in Patent Office: 1,166 Days
• Field of Search: 714 10- 13, 714/42
• US Class Current: 714/12
• CPC Class Codes: G06F 11/0724 in a multiprocessor or a multi-core unit multiprocessors per se G06F15/80
• CPC Class Codes: G06F 11/073 in a memory management context, e.g. virtual memory or cache management memory management G06F12/00; testing of static memory units G11C29/00
• CPC Class Codes: G06F 11/0763 by bit configuration check, e.g. of formats or tags
• CPC Class Codes: G06F 11/1658 Data re-synchronization of a redundant component, or initial sync of replacement, additional or spare unit
• CPC Class Codes: G06F 11/184 where the redundant components implement processing functionality
• CPC Class Codes: G06F 2201/83 the solution involving signatures

Abstract

This disclosure provides apparatus, methods and systems for error correction in multi processor systems. Some implementations include a plurality of computing modules, each computing module including a processor. Each processor may include processing state. In some other implementations, each computing module may also include a memory. Upon receiving a signal to perform a partial re-synchronization, a hash of each processor'"'"'s state data may be performed. In some embodiments, a hash of at least a portion of each computing module'"'"'s memory data may also be performed. The hashes for each processor are then compared to determine majority hashes and possible minority hashes. Upon identifying a minority hash, the computing module that produced the minority hash may receive new processing state data from one of the computing modules that produced a majority hash.

Claims

1. A method of synchronizing the state of a plurality of computing modules in an electronic system, each computing module having a processor, comprising:

saving at least a portion of processor state data for each of the plurality of computing modules;

hashing at least the portion of the saved processor state data for each of the plurality of computing modules;

comparing the processor hashes for the processor state data;

determining a majority of computing modules having the same processor state data and at least one minority of computing modules having different processor state data;

re-synchronizing the plurality of computing modules if the majority of computing modules are determined to have the same processor state data, and the minority of computing modules are determined to have different processor state data, wherein re-synchronizing comprises;

sending the saved processor state data from a first majority computing module to a first minority computing module;

confirming that the state data of a second majority computing module is the same as the saved state data from the first majority computing module or the saved state data of the first minority computing module after sending the saved processor state data from the first majority computing module to the minority computing module;

flagging an error if the state data is not the same; and

restoring the processor state data of a majority computing module based on the majority computing module'"'"'s saved processor state data in response to completion of the resynchronization.

2. The method of claim 1, further comprising:

hashing memory state data for each of the plurality of computing modules;

comparing the memory hashes for the memory state data; and

re-synchronizing the plurality of computing modules based at least on the compared memory hashes.

3. The method of claim 1, wherein hashing the processor state data comprises calculating a checksum of the processor state data.

4. The method of claim 2, wherein hashing the memory state data comprises calculating a checksum of the memory state data.

5. The method of claim 1, wherein the re-synchronizing comprises sending processor state data from a first computing module to a second computing module.

6. The method of claim 5, wherein sending the processor state data comprises sending the processor state data over a data bus directly connecting the first computing module to the second computing module.

7. The method of claim 2, wherein hashing memory state data for each of the plurality of computing modules comprises hashing a portion of the memory state data for each of the plurality of computing modules.

8. The method of claim 2, wherein the method is performed at regular intervals during operation of the electronic system.

9. The method of claim 7, wherein during each regular interval, the method creates hash values for only a predetermined portion of the memory state data in each computing module.

10. The method of claim 9, wherein the memory state data is divided into at least a first memory portion and a second memory portion and during sequential regular intervals, the method hashes the first memory portion for each computing module and then hashes the second memory portion for each computing module.

11. The method of claim 10, wherein the method sequentially compares hash values for all of the memory state data over a plurality of sequential regular intervals.

12. The method of claim 1, wherein each of the computing modules comprises a processor core of a multi-core processor.

13. The method of claim 1, further comprising:

identifying a computing module that has become unresponsive; and

resetting the unresponsive computing module.

14. The method of claim 9, the method further comprises:

during each regular interval;

determining whether the hash values of the predetermined portions of each computing module are equivalent, and

creating additional hash values for a second portion of the memory state data in each computing module if the hash values of the predetermined portions are not equivalent.

15. A fault tolerant computing apparatus, comprising:

a plurality of computing modules, wherein each computing module comprises a hardware processor having processor state data;

a re-synchronization module configured to save at least a portion of processor state data for each of the plurality of computing modules;

a hashing module configured to generate hash values of at least the saved processor state data;

a fault tolerant checking unit configured to receive the plurality of hash values and

re-synchronizing the plurality of computing modules if a majority of computing modules are determined to have the same processor state data, and a minority of computing modules are determined to have different processor state data, and

wherein the re-synchronization module is further configured to;

send the saved processor state data from a first majority computing module to a first minority computing module;

confirm that the state data of a second majority computing module is the same as the saved state data from the first majority computing module or the saved state data of the first minority computing module after sending the saved processor state data from the first majority computing module to the minority computing module;

flag an error if the state data is not the same; and

restore the processor state data of a majority computing module based on the majority computing module'"'"'s saved processor state data in response to completion of the resynchronization.

16. The fault tolerant computing apparatus of claim 15, further comprising a memory coherency checking unit, configured to check the coherency of a plurality of memories included in the plurality of computing modules.

17. The fault tolerant computing apparatus of claim 15, wherein the processors of the plurality of computing modules each have memory state data, and

the hashing module is further configured to generate hash values for the memory state data;

and

the plurality of hash values read by the fault tolerant checking unit include the hash values for the memory state data.

18. The fault tolerant computing apparatus of claim 17, wherein the hashing module is further configured to select only a predetermined portion of the memory to hash for each computing module.

19. The fault tolerant computing apparatus of claim 17, comprising a timer configured to start generating hash values of the memory state data at regular intervals.

20. The fault tolerant computing apparatus of claim 19, wherein the regular intervals are set to be at 2, 5, 10, 20 or 30 milliseconds.

21. The fault tolerant computing apparatus of claim 19, wherein the hashing module is configured to select only a portion of the memory from each computing module to hash at each regular interval.

22. The fault tolerant computing apparatus of claim 19, wherein the memory of each computing module has at least a first memory portion and a second memory portion and the hashing module is configured to sequentially hash the first memory portion and then the second memory portion from each computing module at sequential regular intervals.

23. The fault tolerant computing apparatus of claim 15, wherein each of the plurality of computing modules is operatively coupled to at least one other computing module in the plurality of computing modules by one or more buses.

24. The fault tolerant computing apparatus of claim 15, wherein the fault tolerant checking unit is further configured to identify a computing module that has become unresponsive, and reset the unresponsive computing module.

25. A fault tolerant computing apparatus, comprising:

a plurality of computing modules, wherein each computing module comprises a processor having processor state data;

means for saving at least a portion of processor state data for each of the plurality of computing modules;

means for hashing configured to generate hash values of at least the saved processor state data;

means for comparing the plurality of hash values;

means for determining a majority of computing modules having the same processor state data and at least one minority of computing modules having different processor state data; and

means for resynchronizing the plurality of computing modules based on the determining, wherein the means for resynchronizing is configured to;

send the saved processor state data from a first majority computing module to a first minority computing module;

confirm that the state data of a second majority computing module is the same as the saved state data from the first majority computing module or the saved state data of the first minority computing module after sending the saved processor state data from the first majority computing module to the minority computing module, and

flag an error if the state data is not the same; and

means for restoring the processor state data of a majority computing module based on the majority computing module'"'"'s saved processor state data in response to completion of the resynchronization.

26. The fault tolerant computing apparatus of claim 25, wherein the means for comparing comprises a field programmable gate array (FPGA) programmed to compare hash values from the processor state data.

27. The fault tolerant computing apparatus of claim 25, wherein the means for comparing includes a fault tolerant checking unit.

28. The fault tolerant computing apparatus of claim 25, wherein the means for determining includes one or more re-synchronizing modules.

29. A non-transitory, computer readable storage medium having instructions stored thereon that cause a processing circuit to perform a method comprising:

saving at least a portion of processor state data for each of the plurality of computing modules;

hashing at least the saved processor state data for each of a plurality of computing modules;

comparing the processor hashes for the processor state data; and

determining a majority of computing modules having the same processor state data and at least one minority of computing modules having different processor state data;

re-synchronizing the plurality of computing modules based at least on the determining wherein re-synchronizing comprises;

sending processor state data from a first majority computing module to a first minority computing module;

confirming that the state data of a second majority computing module is the same as the saved state data from the first majority computing module or the saved state data of the first minority computing module after sending the saved processor state data from the first majority computing module to the minority computing module, and

flagging an error if the state data is not the same; and

restoring the processor state data of a majority computing module based on the majority computing module'"'"'s saved processor state data in response to completion of the resynchronization.

30. The computer readable storage medium of claim 29, further including instructions that cause a processing circuit to:

hash memory state data for each of the plurality of computing modules;

compare the memory hashes for the memory state data; and

re-synchronize the plurality of computing modules based at least on the compared memory hashes.