Precise-Restartable Parallel Execution of Programs

A method of executing a program of computational operations;

• the method comprising the steps of:
• (a) determining a total order of the computational operations so that execution of the computational operations in the total order would produce a same result as execution of all of the computational operations on a single processor
• (b) executing different computational operations in parallel on different processors while delaying commitment of that execution to conform with the total order;
• and
• (c) in the event of an interrupt of a given computational operation at a given processor:
• (i) recording an architectural state for that given processor;
• (ii) committing execution of computational operations on other processors earlier than the given computational operation according to the total order and squashing execution of computational operations on other processors subsequent to the given computational operation according to the total order;
• (iii) handling the interrupt;
• and
• (iv) restarting execution of the program using the committed state of the other processors according to step (c) (ii) and the architectural state for the given processor

A multiprocessor computer system for executing a computer program, the multiprocessor computer system executing program steps fixed in non-transient medium to:

• (a) distribute portions of the computer program among multiple processors of the multiprocessor computer system for parallel execution;
• (b) define a total order of the portions that preserves correct resolution of data dependencies among the portions consistent with execution of the computer program on a single processor;
• (c) upon receipt of an interrupt during execution of a given instruction of a portion on one of the processors, capture an architectural state of the multiprocessor computer system that reflects completion of all instructions of the portions preceding the interrupted instruction in the total order and none of the instructions in the portions succeeding the interrupted instruction in the total order;
• (d) handle the interrupt;
• and
• (e) upon completion of the interrupt, restore the captured architectural state and continue execution of the computer program.

A multiprocessor computer system for executing a computer program composed of multiple computational operations, the multiprocessor computer system executing program steps fixed in non-transient medium to:

• (a) determine a total order of the computational operations that ensure a same result as execution of the all of computational operations on a single processor
• (b) execute different computational operations in parallel on different processors while delaying commitment of that execution to conform with the total order;
• and
• (c) in the event of an interrupt at a given processor executing a given computational operation:
• (i) record an architectural state for that given processor;
• (ii) commit execution of computational operations on other processors earlier than the given computational operation according to the total order and squash execution of computational operations on other processors subsequent to the given computational operation according to the total order;
• (iv) handle the interrupt;
• and
• (v) restart execution of the program using the committed state of the other processors according to step (c) (ii) and the recorded architectural state for the given processor.

A method for processing a computer program in a multiprocessor computer system comprising the steps of:

• (a) dividing the computer program into portions having instructions at least one of which may generate an interrupt and distributing the portions among multiple processors of the multiprocessor computer system for parallel execution;
• (b) defining a data flow order of the portions that preserves correct resolution of data dependencies among the portions consistent with execution of the computer program on a single processor;
• (c) in the event of a fault in execution of a portion on a given processor, determining dependent portions having data dependencies on the given portion;
• and
• (e) restarting that given portion and the dependent portions while allowing continued execution of other portions.

A multiprocessor computer system for executing a computer program composed of multiple computational operations, the multiprocessor computer system executing program steps fixed in non-transient medium to:

• (a) divide a computer program into portions having instructions at least one of which may generate an interrupt and distributing the portions among multiple processors of the multiprocessor computer system for parallel execution;
• (b) define a data flow order of the portions that preserves correct resolution of data dependencies among the portions consistent with execution of the computer program on a single processor;
• (c) in the event of a fault in execution of a portion on a given processor, determine dependent portions having data dependencies on the given portion;
• and
• (e) restart that given portion and the dependent portions while allowing continued execution of other portions.