SYSTEM, METHOD AND APPARATUS FOR ERROR CORRECTION IN MULTI-PROCESSOR SYSTEMS

• US 20120117419A1
• Filed: 10/28/2011
• Published: 05/10/2012
• Est. Priority Date: 10/28/2010
• Status: Active Grant

• Current Assignee: Data Device Corporation (Transdigm Group Incorporated)
• Original Assignee: Maxwell Technologies Incorporated (Tesla Inc.)
• Inventors: Hillman, Robert, Williamson, Gale
• Granted Patent: US 8,930,753 B2
• Time in Patent Office: Days
• 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:

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

comparing the processor hashes for the processor state data; and

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

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, further comprising 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.

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

7. The method of claim 5, wherein re-synchronizing comprises sending processor state data from a first majority computing module to a minority computing module.

8. The method of claim 7, wherein re-synchronizing further comprises

comparing the state data of a second majority computing module with the state data from the first majority computing module or the minority computing module after sending the processor state data from the first majority computing module to the minority computing module, and

flagging an error based on the comparison of the state data.

9. The method of claim 6, 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.

10. 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.

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

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

13. The method of claim 12, 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

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

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

16. The method of claim 1, further comprising:

identifying a computing module that has become unresponsive; and

resetting the unresponsive computing module;

18. 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. A fault tolerant computing apparatus, comprising:

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

a hashing module configured to generate hash values of the processor state data; and

a fault tolerant checking unit configured to receive the plurality of hash values and determine if each computing module is synchronized with the other computing modules.

19. The fault tolerant computing apparatus of claim 17, 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.

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

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

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

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

24. The fault tolerant computing apparatus of claim 23, 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.

25. The fault tolerant computing apparatus of claim 17, 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.

26. The fault tolerant computing apparatus of claim 17, further comprising a re-synchronization module configured to send processor state data or memory state data from a first majority computing module to a minority computing module when hash values from the majority computing module and minority computing module do not match.

27. The fault tolerant computing apparatus of claim 26, wherein the re-synchronization module is further configured to

compare the state data of a second majority computing module with the state data of the first majority computing module or the minority computing module after sending the processor state data from the first majority computing module to the minority computing module, and

flag an error based on the comparison of the state data.

28. The fault tolerant computing apparatus of claim 17, wherein the fault tolerant checking unit is further configured to

identify a computing module that has become unresponsive, and

reset the unresponsive computing module;

29. A fault tolerant computing apparatus, comprising:

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

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

means for comparing the plurality of hash values; and

means for determining if the processor within each computing module is synchronized with the processors of the other computing modules.

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

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

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

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

hashing processor state data for each of a plurality of computing modules;

comparing the processor hashes for the processor state data; and

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

34. The computer readable storage medium of claim 33, 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.