System and method for speculative execution in a geometry accelerator

• US 5,883,641 A
• Filed: 04/29/1997
• Issued: 03/16/1999
• Est. Priority Date: 04/29/1997
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Krech, Alan S. Jr., Strunk, Glenn W
• Primary Examiner(s): Tung, Kee M.
• Application Number:
  US08/837,875
• Time in Patent Office: 686 Days
• Field of Search: 345/424-427, 345/433, 345/434, 345/441, 345/501-503, 345/514, 345/522, 345/523, 345/505, 345/506, 395/701, 395/704
• US Class Current: 345/505
• CPC Class Codes: G06F 9/3842 Speculative instruction execution
• CPC Class Codes: G06F 9/3861 Recovery, e.g. branch miss-prediction, exception handling error detection or correction G06F11/00
• CPC Class Codes: G06T 15/005 General purpose rendering architectures

Abstract

A system and method for performing speculative execution of state machine operation in a graphics accelerator. In accordance with one aspect of the invention, the method includes the step of executing steps in a first state machine that is operating on a graphic primitive. As is known, a graphic primitive is defined by a plurality of vertices. In accordance with the invention, the preferred embodiment receives the coordinate parameters for the second to last primitive vertex. Then it evaluates one or more conditions that indicate whether steps in a second state machine need to be executed, based upon parameters of primitive vertices already received. It then branches to and begins executing steps in another state machine, based upon the tentative conditions, and continuing execution of the steps in the transformation state machine in parallel with the continued execution of the steps in the another state machine. After a predetermined number of states, the method reevaluates the one or more conditions, at which time the value of the one or more conditions is no longer tentative, but determinative of the next state information. Then, the method invokes a reset condition, aborts execution of the steps in the another state machine, and returns execution to a predetermined step in the first state machine, if the one or more conditions of the evaluating and reevaluating steps are inconsistent. If, however, the one or more conditions of the evaluating and reevaluating steps are equal or consistent, the method terminates the execution of the first state machine and continues executing the steps in the another state machine.

Claims

1. A method for performing speculative execution of state machine operation in a graphics accelerator, comprising the steps of:

(a) executing steps in a graphic primitive transformation state machine;

(b) receiving second to last primitive vertex parameters into the transformation state machine;

(c) evaluating branch codes that indicate whether steps in a clipping state machine need to be executed, based upon the primitive vertex parameters already received;

(d) branching and beginning execution of steps in another state machine, based upon tentative values of the branch codes, and continuing execution of the steps in the transformation state machine in parallel with the execution of the steps in the another state machine;

(e) reevaluating the branch codes after a predetermined number of states, at which time the value of the branch codes is no longer tentative, but determinative of the next state information;

(f) invoking a reset condition, aborting execution of the steps in the another state machine, and returning execution to a predetermined step in the transformation state machine, if the branch codes of the evaluating and reevaluating steps are inconsistent; and

(g) terminating the execution of the transformation state machine and continuing the execution of the steps in the another state machine, if the branch codes of the evaluating and reevaluating steps are consistent.

2. The method as defined in claim 1, wherein the branching step (d), further includes the step of protecting state information needed for downstream execution.

3. The method as defined in claim 2, wherein the terminating step (g) further includes the step of releasing the protection of the state information needed for downstream execution.

4. The method as defined in claim 1, wherein the another state machine is a clipping state machine.

5. The method as defined in claim 1, wherein the another state machine is a plane equation state machine.

6. The method as defined in claim 1, wherein the another state machine is a shading state machine.

7. The method as defined in claim 1, wherein the step of invoking a reset condition includes asserting a power-up reset signal for read only memory (ROM) containing state machine execution code.

8. The method as defined in claim 1, wherein the branch codes include vertex coordinate information.

9. A method for performing speculative execution of state machine operation in a graphics accelerator, comprising the steps of:

(a) executing steps in a first state machine operating on a graphic primitive;

(b) receiving second to last primitive vertex parameters;

(c) evaluating one or more tentative conditions that indicate whether steps in a second state machine need to be executed, based upon the primitive vertex parameters already received;

(d) branching and beginning execution of steps in another state machine, based upon the tentative conditions, and continuing execution of the steps in the transformation state machine in parallel with the continued execution of the steps in the another state machine;

(e) reevaluating the one or more tentative conditions after a predetermined number of states, at which time the value of the one or more tentative conditions is no longer tentative, but determinative of the next state information;

(f) invoking a reset condition, aborting execution of the steps in the another state machine, and returning execution to a predetermined step in the first state machine, if the one or more conditions of the evaluating and reevaluating steps are inconsistent; and

(g) terminating the execution of the first state machine and continuing the execution of the steps in the another state machine, if the one or more conditions of the evaluating and reevaluating steps are consistent.

10. The method as defined in claim 9, wherein the one or more conditions include branch condition codes.

11. The method as defined in claim 10, wherein the branch condition codes include primitive vertex coordinate information.

12. The method as defined in claim 9, wherein the first state machine is a primitive transformation state machine.

13. The method as defined in claim 9, wherein the second state machine is a clipping state machine.

14. A system for improving execution in a graphics accelerator comprising having a plurality of state machines, the plurality of state machines having a shared data and control bus, the system comprising:

a controller for controlling the execution of the plurality of state machines, the controller particularly adapted to provide limited parallel execution of the plurality of state machines;

a read only memory (ROM) containing program code executed by the controller;

a code location including information relating to branching conditions;

a first state machine defined to execute a plurality of steps, and having a predetermined sequence ending state S1;

second and third state machines, defined by the controller to substantially execute after the execution of the first state machine, but the second and third state machines having one or more steps for execution in parallel with one or more steps of the first state machine;

evaluation means for evaluating the code location at a state S2 that occurs prior to the occurrence of state S1;

branching means responsive to the evaluation means for branching to the second state machine prior to the occurrence of state S1;

reevaluation means, operative upon or after the occurrence of state S1, for reevaluating the code location; and

terminating means responsive to the reevaluation means for terminating execution of the second state machine if the code location has changed since evaluation by the evaluation means, the terminating means further operative to return operation back to first state machine at a predetermined point of operation.

15. The system as defined in claim 14, further including a memory segment for storing data needed for the execution of the first state machine, after the execution of state S2.

16. The system as defined in claim 15, further including protection means for protecting the integrity of the data stored in the memory segment.

17. The system as defined in claim 16, further including means responsive to the termination means to deactivate the protection means, and relinquish the protection on the memory segment.

18. The system as defined in claim 14, wherein the ROM forms part of the controller.

19. The system as defined in claim 14, wherein the code location includes a condition code register.

20. The system as defined in claim 14, wherein the first state machine is a transform state machine.

21. The system as defined in claim 14, wherein the second state machine is a clipping state machine.

22. The system as defined in claim 14, wherein the third state machine is a plane equation state machine.

23. The system as defined in claim 14, wherein the termination means includes a power-up reset signal.

24. A computer readable storage medium containing program code for controlling the speculative execution of state machine operation in a graphics accelerator, comprising:

(a) a first code segment for executing steps in a first state machine operating on a graphic primitive;

(b) a second code segment for receiving the second to last primitive vertex parameters;

(c) a third code segment for evaluating one or more conditions that indicate whether steps in a second state machine need to be executed, based upon the primitive vertex parameters already received;

(d) a fourth code segment for branching and beginning execution of steps in another state machine, based upon the tentative conditions, and continuing execution of the steps in the transformation state machine in parallel with the continued execution of the steps in the another state machine;

(e) a fifth code segment for reevaluating the one or more conditions after a predetermined number of states, at which time the value of the one or more conditions is no longer tentative, but determinative of the next state information;

(f) a sixth code segment for invoking a reset condition, aborting execution of the steps in the another state machine, and returning execution to a predetermined step in the first state machine, if the one or more conditions of the evaluating and reevaluating steps are inconsistent; and

(g) a seventh code segment for terminating the execution of the first state machine and continuing the execution of the steps in the another state machine, if the one or more conditions of the evaluating and reevaluating steps are consistent.

25. A computer readable storage medium containing program code for controlling the execution of a graphics accelerator comprising having a plurality of state machines, the plurality of state machines having a shared data and control bus, the graphics accelerator comprising:

a controller for controlling the execution of the plurality of state machines, the controller particularly adapted to provide limited parallel execution of the plurality of state machines;

a read only memory (ROM) containing program code executed by the controller;

a code location including information relating to branching conditions;

a first state machine defined to execute a plurality of steps, and having a predetermined sequence ending state S1;

second and third state machines, defined by the controller to substantially execute after the execution of the first state machine, but the second and third state machines having one or more steps for execution in parallel with one or more steps of the first state machine;

evaluation means for evaluating the code location at a state S2 that occurs prior to the occurrence of state S1;

branching means responsive to the evaluation means for branching to the second state machine prior to the occurrence of state S1;

reevaluation means, operative upon or after the occurrence of state S1, for reevaluating the code location; and

terminating means responsive to the reevaluation means for terminating execution of the second state machine if the code location has changed since evaluation by the evaluation means, the terminating means further operative to return operation back to first state machine at a predetermined point of operation.