Method and system executing user programs on non-deterministic processors

• US 20050223274A1
• Filed: 01/25/2005
• Published: 10/06/2005
• Est. Priority Date: 03/30/2004
• Status: Active Grant

• Current Assignee: Valtrus Innovations Limited (f/k/a Dolya Holdco 9 Limited) (Key Patent Innovations Limited)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Garcia, David J., Bruckert, William F., Jardine, Robert L., Klecka, James S., Smullen, James R., Mehra, Pankaj, Bernick, David L.
• Granted Patent: US 7,426,656 B2
• Time in Patent Office: Days
• US Class Current: 714/11
• CPC Class Codes: G06F 11/1482 by means of middleware or OS functionality
• CPC Class Codes: G06F 11/1645 and the comparison itself uses redundant hardware
• CPC Class Codes: G06F 11/1683 at instruction level
• CPC Class Codes: G06F 11/1691 using a quantum
• CPC Class Codes: G06F 9/3851 from multiple instruction streams, e.g. multistreaming
• CPC Class Codes: G06F 9/3861 Recovery, e.g. branch miss-prediction, exception handling error detection or correction G06F11/00

Abstract

A method and system of loosely lock-stepped non-deterministic processors. Some exemplary embodiments may be a processor-based method comprising executing fault tolerant copies of a user program, one copy of the user program executed in a first processor performing non-deterministic execution, and a duplicate copy of the user program executing in a second processor performing non-deterministic execution, with the executing in the first processor and second processor not in cycle-by-cycle lock-stepped.

Claims

1. A method comprising:

executing fault tolerant copies of a user program, one copy of the user program executed in a first processor performing non-deterministic execution, and a duplicate copy of the user program executing in a second processor performing non-deterministic execution;

wherein the executing in the first processor and second processor is not in cycle-by-cycle lock-step.

2. The method as defined in claim 1 further comprising:

executing the user program in the first processor being part of a first computer system;

executing the duplicate copy of the user program in a second processor being part of a second computer system.

3. The method as defined in claim 1 further comprising exchanging information about the state of the respective user programs using a logic system coupling the first and second computer systems.

4. The method as defined in claim 1 further comprising consolidating input/output (I/O) requests generated by software into single I/O requests presented to an I/O device.

5. The method as defined in claim 4 further comprising providing I/O responses to each of the processors.

6. The method as defined in claim 1 further comprising replicating externally initiated requests directed to the user programs.

7. The method as defined in, claim 6 further comprising consolidating responses from each of the processors triggered by the request.

8. The method as defined in claim 1 further comprising executing a duplicate copy of the user program in a third processor performing non-deterministic execution, and wherein the executing in the first, second and third processors is not in cycle-by-cycle lock-step.

9. The method as defined in claim 1 wherein the non-determinism comprises at least one selected from the group:

timing non-determinism;

non-architecturally visible non-determinism;

or non-determinism related to error handling in data access.

10. A system comprising:

a first processor;

a second processor coupled to the first processor;

wherein the processors execute fault tolerant copies of a user program, the first processor executing the user program, and the second processor executing a duplicate copy of the user program;

wherein the execution of the user programs in the first and second processors are not in strict lock-step, and wherein the first and second processors execute their respective user programs non-deterministically.

11. The system as defined in claim 10 further comprising a third processor coupled to the first and second processors that executes a duplicate copy of the user program, and wherein the third processor is not in strict lock-step with the first and second processor, and wherein the third processor executes its respective user program non-deterministically.

12. The system as defined in claim 10 further comprising:

a first computer system comprising the first processor;

a second computer system comprising the second processor; and

a voter logic system coupling the first and second computer systems;

wherein the voter logic receives, from the processors, duplicate read requests directed to an input/output (I/O) device, consolidates the requests into a single request, and forwards the single request to the I/O device.

13. The system as defined in claim 10 further comprising:

a first computer system comprising the first processor;

a second computer system comprising the second processor; and

a voter logic system coupling the first and second computer systems;

wherein the voter logic receives, from an external device, requests directed to the software executing on each processor, duplicates the requests, and forwards the requests one each to each processor.

14. The system as defined in claim 13 further comprising wherein the voter logic receives, from the processors, duplicate responses to the requests from the external device, consolidates the responses into a single response, and forwards the single response to the external device.

15. The system as defined in claim 10 further comprising:

a first computer system comprising the first processor;

a second computer system comprising the second processor; and

a voter logic system coupling the first and second computer systems;

wherein the voter logic receives duplicate write requests directed to an input/output (I/O) device, consolidates the requests into a single request, and forwards the single request to the I/O device.

16. The system as defined in claim 10 further comprising:

a synchronization logic coupling the first and second processors, the synchronization logic comprising a register set; and

wherein the first and second processor exchange data regarding interrupts using the register set.

17. The system as defined in claim 16 wherein the first and second processors exchange data by writing data to the register set, and wherein the first and second processors retrieve data from the register set with a waited read.

18. The system as defined in claim 16 wherein the first and second processors exchange data by writing data to the register set, and wherein the synchronization logic writes at least a part of the data in the register set to a memory of each processor.

19. The system as defined in claim 10 wherein the non-deterministic execution of the user program comprises at least one selected from the group:

timing non-determinism;

non-architecturally visible non-determinism;

or non-determinism related to error handling in data access.

20. The system as defined in claim 10 wherein both the first and second processors execute their respective user programs using out of order processing.

21. A system comprising:

a first processor that executes programs utilizing branch prediction speculation;

a second processor coupled to the first processor, the second processor executes programs using branch prediction speculation;

wherein the processors execute fault tolerant copies of a user program, the first processor executing the user program, and the second processor executing a duplicate copy of the user program;

wherein the execution of the user programs in the first and second processors are at least partially lock-stepped without relying on counting retired instructions to control synchronism as between the first and second processors.

22. The system as defined in claim 21 wherein both the first and second processors execute their respective user programs using out of order processing.

23. The system as defined in claim 21 further comprising a third processor coupled to the first and second processors that executes a duplicate copy of the user program utilizing branch prediction speculation, and wherein the third processor is not in cycle-by-cycle lock-step with the first and second processor.

24. The system as defined in claim 23 wherein the third processor executes its application program using out of order processing.

25. A system comprising:

a first means for processing that executes a user program;

a second means for processing coupled to the first means for processing, the second means for processing executes a duplicate copy of the user program;

wherein the execution of the user programs in the first and second means for processing is for fault tolerance, and is at least partially lock-stepped without fully synchronized clocking signals applied to each means for processing and without relying on counting retired instructions to control synchronism as between the first and second means for processing.

26. The system as defined in claim 25 further comprising a third means for processing coupled to the first and second means for processing that executes a duplicate copy of the user program, and wherein the third means for processing is at least partially lock-stepped with the first and second means for processing.

27. The system as defined in claim 25 further comprising a means for comparing input/output (I/O) requests coupling the first and second means for processing.

28. The system as defined in claim 25 further comprising:

a means for assisting in synchronization of the first and second processors coupling the first and second means for processing; and

wherein the first and second means for processing exchange data regarding interrupts using the means for assisting.