Multi-threaded pipeline with context issue rules

• US 20040034759A1
• Filed: 10/17/2002
• Published: 02/19/2004
• Est. Priority Date: 08/16/2002
• Status: Abandoned Application

• Current Assignee: Lexra Inc.
• Original Assignee: Lexra Inc.
• Inventors: Katzman, Solomon J., Cotsford, Michael A., Gelinas, Robert G., Snyder, Todd H., Hays, W. Patrick
• Application Number:
  US10/274,427
• Publication Number:
  US 20040034759A1
• Time in Patent Office: Days
• US Class Current: 712/1
• CPC Class Codes: G06F 9/3826 Bypassing or forwarding of data results, e.g. locally between pipeline stages or within a pipeline stage
• CPC Class Codes: G06F 9/3828 with global bypass, e.g. between pipelines, between clusters
• CPC Class Codes: G06F 9/3836 Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution
• CPC Class Codes: G06F 9/3851 from multiple instruction streams, e.g. multistreaming

Abstract

An apparatus and method for increasing throughput in a processor having a multi-threaded pipeline is provided. Throughput is increased by dynamically allocating hardware contexts to pipeline flows according to context issue rules. The context issue rules eliminate some hardware bypass paths allowing for a shorter clock period and minimize pipeline stalls. One context issue rule eliminates the need for an E-E bypass path by ensuring that no context is allowed to issue in two adjacent pipeline flows. Another context issue rule eliminates the need for an M-E bypass path by ensuring that data retrieved from memory in a pipeline flow for a context is available prior to a successive pipeline flow for the same context entering the execution stage. A beat issue rule looks for reduced utilization of the pipeline when no active context can issue an instruction due to the context issue rules. By application of the context issue rules, a multi-threaded pipeline can be kept filled and operating at 100% efficiency with as little as two concurrent contexts issuing in alternating cycles.

Claims

1. A method for increasing processor throughput, the processor having a multi-threaded pipeline comprising the steps of:

concurrently processing a plurality of contexts; and

dynamically assigning the plurality of contexts to pipeline flows according to a context issue rule.

2. The method of claim 1 wherein the number of contexts is at least two.

3. The method of claim 2 wherein the number of contexts is 4.

4. The method of claim 1 wherein the context issue rule prevents a context which issues in a pipeline flow from issuing in a successive pipeline flow.

5. The method of claim 4 wherein the context issue rule prevents a context which issues in pipeline Flow N from issuing in pipeline Flow N+1.

6. The method of claim 5 wherein a result of an execution stage in the pipeline flow for the context is available at least one cycle before a successive pipeline flow for the context enters the execution stage.

7. The method of claim 1 where the context issue rule prevents a context which issues in pipeline Flow N from issuing in pipeline Flow N+P, where P depends upon a configuration of stages of the pipeline.

8. The method of claim 7 where P is dependent on a number of stages between at least two predetermined pipeline stages.

9. The method of claim 8 wherein the predetermined stages are an execution stage and a memory stage.

10. The method of claim 9 wherein P=2 plus the number of stages between the execution stage and a memory stage.

11. The method of claim 7 wherein P=3.

12. The method of claim 6 wherein data retrieved from a memory stage in a pipeline flow for the context is available prior to a successive pipeline flow for the context entering an execution stage.

13. The method of claim 1 wherein a result of a branch instruction is available for a successive instruction in a same context to select a next address without prediction.

14. The method of claim 13 wherein the result is available after a delay slot instruction.

15. The method of claim 1 wherein a jump destination resulting from a data dependent jump instruction is available for a successive instruction in the same context.

16. The method of claim 15 where the jump destination is available after a delay slot instruction.

17. The method of claim 1 wherein the multi-threaded pipeline is filled by two contexts issuing in alternate cycles.

18. The method of claim 1 wherein upon determining no context issued in pipeline Flows N+1 and N+3, and determining that a different context issued in pipeline Flow N+2, the context which issued in pipeline Flow N is prevented from issuing in pipeline Flow N+4.

19. The method of claim 1 wherein pipeline stalls due to delayed results are less frequent.

20. A processor comprising:

a multi-threaded pipeline which concurrently processes a plurality of contexts; and

a scheduler which dynamically assigns the plurality of contexts to pipeline Flows according to a context issue rule.

21. The processor of claim 20 wherein the number of contexts is at least two.

22. The processor of claim 21 wherein the number of contexts is 4.

23. The processor of claim 20 wherein the context issue rule prevents a context which issues in a pipeline Flow from issuing in a successive pipeline Flow.

24. The processor of claim 23 wherein the context issue rule prevents a context which issues in pipeline Flow N from issuing in pipeline Flow N+1.

25. The processor of claim 24 wherein a result of an execution stage in a pipeline Flow for a context is available at least one cycle before a successive pipeline Flow for the context enters the execution stage.

26. The processor of claim 20 where the context issue rule prevents a context which issues in pipeline Flow N from issuing in pipeline Flow N+P, where P depends upon a configuration of stages of the pipeline.

27. The processor of claim 26 where P is dependent on a number of stages between at least two predetermined pipeline stages.

28. The processor of claim 27 wherein the predetermined stages are an execution stage and a memory stage.

29. The processor of claim 28 wherein P=2 plus the number of stages between the execution stage and a memory stage.

30. The processor of claim 26 wherein P=3.

31. The processor of claim 27 wherein data retrieved from a memory stage in a pipeline Flow for the context is available prior to a successive pipeline Flow for the context entering an execution stage.

32. The processor of claim 20 wherein a result of a branch instruction is available for a successive instruction in a same context to select a next address without prediction.

33. The processor of claim 32 wherein the result is available after a delay slot instruction.

34. The processor of claim 20 wherein a jump destination resulting from a data dependent jump instruction is available for a successive instruction in the same context.

35. The processor of claim 34 wherein the jump destination is available after a delay slot instruction.

36. The processor of claim 20 wherein the multi-threaded pipeline is filled by two contexts issuing in alternate cycles.

37. The processor of claim 20 wherein upon determining no context issued in pipeline Flows N+1 and N+3, and a different context issued in pipeline Flow N+2, the context which issued in pipeline Flow N is prevented from issuing in pipeline Flow N+4.

38. The processor of claim 20 wherein pipeline stalls due to delayed results are less frequent.