Queues for inter-pipeline data hazard avoidance

Patent metadata

Field	Value
Publication number	US-11698790-B2
Application number	US-202117523633-A
Country	US
Kind code	B2
Filing date	Nov 10, 2021
Priority date	Jun 16, 2017
Publication date	Jul 11, 2023
Grant date	Jul 11, 2023

Abstract

Methods and parallel processing units for avoiding inter-pipeline data hazards identified at compile time. For each identified inter-pipeline data hazard the primary instruction and secondary instruction(s) thereof are identified as such and are linked by a counter which is used to track that inter-pipeline data hazard. When a primary instruction is output by the instruction decoder for execution the value of the counter associated therewith is adjusted to indicate that there is hazard related to the primary instruction, and when primary instruction has been resolved by one of multiple parallel processing pipelines the value of the counter associated therewith is adjusted to indicate that the hazard related to the primary instruction has been resolved. When a secondary instruction is output by the decoder for execution, the secondary instruction is stalled in a queue associated with the appropriate instruction pipeline if at least one counter associated with the primary instructions from which it depends indicates that there is a hazard related to the primary instruction.

First claim

What is claimed is:

1. A queue for use in a parallel processing unit wherein each instruction is related to a task of a plurality of tasks and data hazards are tracked using a plurality of counters, the queue comprising:
a first-in-first-out queue configured to receive instructions output by an instruction decoder of the parallel processing unit to be executed by an instruction pipeline of the parallel processing unit, store the instructions in the order in which they were received, and output the received instructions in a same order;
a hazard instruction queue configured to store hazard instructions in the order they are received until all hazards associated with a hazard instruction have been resolved;
hazard detection logic configured to determine whether an instruction output from the first-in-first-out queue is a hazard instruction by:
determining whether there is at least one instruction in the hazard instruction queue that is related to a same task as the instruction;
in response to determining that there is at least one instruction in the hazard instruction queue that is related to the same task as the instruction, storing the instruction in the hazard instruction queue;
if the instruction is a secondary instruction that is dependent on one or more primary instructions, determining whether a counter associated with at least one of the one or more primary instructions from which the secondary instruction depends indicates that a hazard related to the corresponding primary instruction has not been resolved;
in response to determining that a counter associated with at least one primary instruction from which the secondary instruction depends indicates that the hazard related to the corresponding primary instruction has not been resolved, storing the instruction in the hazard instruction queue;
otherwise output the instruction; and

a multiplexor configured to select one of an instruction output by the hazard instruction queue and an instruction output by the hazard detection logic to forward to the instruction pipeline for execution.

2. The queue of claim 1 , wherein the multiplexor is configured to:
if only one of the hazard detection logic and the hazard instruction queue output an instruction in a same clock cycle, forward the output instruction to the instruction pipeline for execution; and
if both the hazard detection logic and the hazard instruction queue output an instruction in the same clock cycle, forward the instruction output by the hazard instruction queue to the instruction pipeline for execution.

3. The queue of claim 1 , further comprising an information queue configured to store information, for each hazard instruction in the hazard instruction queue, indicating the hazards associated with that hazard instruction.

4. The queue of claim 3 , wherein the information queue is configured to store, for each hazard instruction in the hazard instruction queue, information indicating whether the hazard related to each primary instruction from which the hazard instruction depends has been resolved and/or information indicating whether the hazard instruction is waiting for another instruction in the hazard instruction queue and if so, which one.

5. The queue of claim 3 , wherein the information queue is configured to store, for each hazard instruction in the hazard instruction queue, a flag indicating whether that hazard instruction is waiting for a hazard related to a primary instruction from which the hazard instruction depends and/or a flag indicating whether the hazard instruction is waiting for another instruction in the hazard instruction queue to be forwarded to the instruction pipeline for execution.

6. The queue of claim 3 , wherein the hazard instruction queue is configured to, when the information in the information queue indicates that all hazards for a hazard instruction have been resolved, forward the hazard instruction to the multiplexor.

7. The queue of claim 1 , further comprising active logic configured to: receive an instruction output by the multiplexor, determine from active information whether the instruction is to be forwarded to the instruction pipeline for execution, and if the active information indicates that the instruction is not to be forwarded to the instruction pipeline for execution, discard the instruction.

8. The queue of claim 7 , wherein execution of an instruction causes multiple instances of the instruction to be executed, the multiple instances being grouped into a plurality of groups, and the active logic is configured to:
determine from the active information whether at least one of the plurality of groups is active for the instruction;
in response to determining that at least one group is active for the instruction, forward the instruction to the instruction pipeline for execution; and
in response to determining that there is not at least one group that is active for the instruction, discard the instruction.

9. The queue of claim 8 , wherein the active logic is configured to, if the instruction is a primary instruction and the active information indicates that at least one group is active for the instruction but not all of the groups are active for the instruction, cause the counter associated with the primary instruction to be updated to indicate that the hazard associated with the primary instruction has been partially resolved.

10. The queue of claim 7 , wherein the active logic is configured to, if a discarded instruction is a primary instruction, cause the counter associated with the primary instruction to be adjusted to indicate that the hazard associated with the primary instruction has been resolved.

11. The queue of claim 1 , wherein each instruction comprises a primary instruction field and a secondary instruction field, the primary instruction field configured to indicate whether the instruction is a primary instruction and to identify the counter associated with that primary instruction, and the secondary instruction field configured to indicate whether the instruction is a secondary instruction and the counter associated with each primary instruction from which the secondary instruction is dependent.

12. The queue of claim 11 , wherein the primary instruction field is configured to hold a number and when the number is a predetermined value it indicates that the instruction is not a primary instruction and when the number is not the predetermined value it indicates that the instruction is a primary instruction and the number represents a number of the counter associated with the primary instruction.

13. The queue of claim 11 , wherein the secondary instruction field is configured to hold a bit mask wherein each bit of the bit mask corresponds to a counter of the plurality of counters and when a bit of the mask is set it indicates that the instruction is a secondary instruction that is dependent on the primary instruction associated with the corresponding counter.

14. The queue of claim 11 , wherein the received instructions have been generated by a compiler configured to identify data hazards within a set of related instructions, allocate a counter to each identified data hazard, and generate computer executable instructions that include primary and secondary instruction fields that are configured based on the identifications and counter allocations.

15. The queue of claim 1 , wherein the parallel processing unit comprises one wait counter corresponding to each counter that is used to keep track of a number of secondary instructions waiting on the results of the corresponding primary instruction, and wherein the queue is configured to, in response to

Assignees

• Imagination Tech Ltd

Inventors

• Iuliano Luca
• Nield Simon
• Foo Yoong-Chert
• Mower Ollie

Classifications

• G06F9/3889

  controlled by multiple instructions, e.g. MIMD, decoupled access or execute · CPC title

• G06F9/3867

  using instruction pipelines · CPC title

• G06F9/3016

  Decoding the operand specifier, e.g. specifier format · CPC title

• G06F9/3838

  Dependency mechanisms, e.g. register scoreboarding · CPC title

• G06F9/3861 Primary

  Recovery, e.g. branch miss-prediction, exception handling (error detection or correction G06F11/00) · CPC title