Systems and methods for handling instructions of in-order and out-of-order execution queues
View Patent ↗Processing systems and methods are disclosed that can include an instruction unit which provides instructions for execution by the processor; a decode/issue unit which decodes instructions received from the instruction unit and issues the instructions; and a plurality of execution queues coupled to the decode/issue unit, wherein each issued instruction from the decode/issue unit can be stored into an entry of at least one queue of the plurality of execution queues. The plurality of queues can comprise an independent execution queue, a dependent execution queue, and a plurality of execution units coupled to receive instructions for execution from the plurality of execution queues. The plurality of execution units can comprise a first execution unit, coupled to receive instructions from the dependent execution queue and the independent execution queue which have been selected for execution. When a multi-cycle instruction at a bottom entry of the dependent execution queue is selected for execution, it may not be removed from the dependent execution queue until a result is received from the first execution unit. When a multi-cycle instruction at a bottom entry of the independent execution queue is selected for execution, it can be removed from the independent execution queue without waiting to receive a result from the first execution unit.
1. A processor, comprising:
an instruction unit which provides instructions for execution by the processor;
a decode/issue unit which decodes instructions received from the instruction unit and issues the instructions; and
a plurality of execution queues coupled to the decode/issue unit, wherein each issued instruction from the decode/issue unit is stored into an entry of at least one queue of the plurality of execution queues, wherein the plurality of queues comprises:
an independent execution queue; and
a dependent execution queue; and
a plurality of execution units coupled to receive instructions for execution from the plurality of execution queues, wherein the plurality of execution units comprises:
a first execution unit, coupled to receive instructions from the dependent execution queue and the independent execution queue which have been selected for execution;
wherein:
when a multi-cycle instruction at a bottom entry of the dependent execution queue is selected for execution, it is not removed from the dependent execution queue until a result is received from the first execution unit, and
when a multi-cycle instruction at a bottom entry of the independent execution queue is selected for execution, it is removed from the independent execution queue without waiting to receive a result from the first execution unit
wherein the decode/issue unit is configured to, in response to receiving a multi-cycle pipelined instruction, decode the multi-cycle pipelined instruction and determine whether an operand of the multi-cycle pipelined instruction includes a dependency on any instruction in the plurality of execution queues, wherein:
when the decode/issue unit determines that an operand of the multi-cycle pipelined instruction does not include a dependency on an instruction in the dependent execution queue, the multi-cycle pipelined instruction is stored in a first entry of the dependent execution queue and selectively stored in a first entry of the independent execution queue.
2. The processor of claim 1 , wherein the decode/issue unit is configured to, in response to receiving a multi-cycle pipelined instruction, decode the multi-cycle pipelined instruction and determine whether an operand of the multi-cycle pipelined instruction includes a dependency on any instruction in the plurality of execution queues, wherein:
when the decode/issue unit determines that an operand of the multi-cycle pipelined instruction includes a dependency on an instruction in the dependent execution queue, the multi-cycle pipelined instruction is stored in a first entry of the dependent execution queue.
3. The processor of claim 1 , wherein the multi-cycle pipelined instruction is further characterized as a complex integer instruction and the first execution unit is further characterized as a complex integer instruction unit.
4. The processor of claim 1 , wherein when the decode/issue unit determines that the dependent execution queue is empty, the multi-cycle pipelined instruction is not stored in the first entry of the independent execution queue.
5. The processor of claim 1 , wherein when the decode/issue unit determines that an operand of the multi-cycle pipelined instruction does not include a dependency on an instruction in the dependent execution queue and the dependent execution queue is not empty, the multi-cycle pipelined instruction is stored in the first entry of the independent execution queue.
6. The processor of claim 5 , wherein when the multi-cycle pipelined instruction is stored in the independent execution queue, a result pending indicator for the multi-cycle pipelined instruction in the first entry is asserted to indicate that it is waiting for result data from the first execution unit for the multi-cycle pipelined instruction provided to the first execution unit from the independent execution queue.
7. The processor of claim 1 , wherein when a multi-cycle instruction at the bottom entry of the dependent execution queue is selected for execution by the first execution unit, a corresponding result pending bit for the multi-cycle instruction at the bottom entry of the dependent execution queue is asserted to indicate that it is waiting for result data from the first execution unit.
8. The processor of claim 1 , wherein when a single-cycle instruction at a bottom entry of the dependent execution queue is selected for execution, it is immediately removed from the dependent execution queue upon selection for execution.
9. In a processor having a decode/issue unit, an independent execution queue and a dependent execution queue, and an execution unit coupled to receive instructions from each of the independent and dependent execution queues, a method comprising:
receiving a first multi-cycle pipelined instruction;
decoding the first multi-cycle pipelined instruction by the decode/issue unit to determine operands of the first multi-cycle pipelined instruction;
determining whether an operand of the first multi-cycle pipelined instruction includes a dependency on any instruction stored in the dependent execution queue;
when an operand of the first multi-cycle pipelined instruction includes a dependency on any instruction stored in the dependent execution queue, storing the first multi-cycle pipelined instruction in a first entry of the dependent execution queue; and
when an operand of the first multi-cycle pipelined instruction does not include a dependency on any instruction stored in the dependent execution queue, the method comprises:
selectively storing the first multi-cycle pipelined instruction in a first entry of the independent execution queue based on whether or not the dependent execution queue is empty; and
storing the first multi-cycle pipelined instruction in a first entry of the dependent execution queue.
10. The method of claim 9 , wherein the step of selectively storing the first multi-cycle pipelined instruction in a first entry of the independent execution queue comprises:
storing the first multi-cycle pipelined instruction in the first entry of the independent execution queue when the dependent execution queue is not empty; and
not storing the first multi-cycle pipelined instruction in the first entry of the independent execution queue when the dependent execution queue is empty.
11. The method of claim 10 , wherein when the first multi-cycle pipelined instruction is stored in the first entry of the independent execution queue, the method further comprises:
setting a result pending indicator for the first multi-cycle pipelined instruction in the first entry of the dependent execution queue to indicate that it is waiting for result data from the execution unit for the first multi-cycle pipelined instruction provided to the execution unit from the independent execution queue.
12. The method of claim 9 , further comprising:
when a multi-cycle instruction reaches a bottom entry of the dependent execution queue and is selected for execution, not removing the multi-cycle instruction from the dependent execution queue until a result is received from the execution unit; and
when a multi-cycle instruction reaches a bottom entry of the independent execution queue and is selected for execution, removing the multi-cycle instruction from the independent execution queue without waiting to receive a result from the execution unit.
13. The method of claim 9 , wherein the processor has a load/store execution queue, and a load/store execution unit, the method further comprising:
determining that an operand of the first multi-cycle pipelined instruction includes a dependency on a load instruction in a first entry of the load/store execution queue;
setting a synchronization indicator corresponding to the first multi-cycle pipelined instruction in a second entry of the load/store execution queue which is immediately adjacent the first entry of the load/store execution queue to indicate that the first multi-cycle pipelined instruction is stored in the dependent or independent execution queue and to indicate a location of the stored first multi-cycle pipelined instruction.
14. The method of claim 13 , further comprising:
setting a synchronization pending indicator for the first multi-cycle pipelined instruction in the first entry of the independent execution queue to indicate that the first multi-cycle pipelined instruction has a corresponding synchronization indicator stored in another execution queue.
15. The method of claim 14 , further comprising:
after the load instruction reaches a bottom entry of the load/store execution queue and is selected for execution, removing the load instruction from the load/store execution queue when a result is received for the load instruction, wherein, after the load instruction is removed from the load/store execution queue, the synchronization indicator for the first multi-cycle pipelined instruction reaches the bottom entry of the load/store execution queue; and
when the synchronization indicator for the first multi-cycle pipelined instruction is at the bottom entry of the load/store execution queue, providing a synchronization clear indicator to clear the synchronization pending indicator in the first entry of the independent execution queue to indicate that the first multi-cycle pipelined instruction is ready for selection for execution.
16. The method of claim 15 , further comprising:
after providing the synchronization clear indicator, removing the synchronization indicator from the bottom entry of the load/store execution queue.
17. In a processor having a decode/issue unit, an independent execution queue and a dependent execution queue, and an execution unit coupled to receive multi-cycle pipelined instructions from each of the independent and dependent execution queues, a method comprising:
receiving a first multi-cycle pipelined instruction;
decoding the first multi-cycle pipelined instruction by the decode/issue unit to determine operands of the first multi-cycle pipelined instruction;
determining whether an operand of the first multi-cycle pipelined instruction includes a dependency on any instruction stored in the dependent execution queue;
when an operand of the first multi-cycle pipelined instruction does not include a dependency on any instruction stored in the dependent execution queue, determining whether the dependent execution queue is empty, and when the dependent execution queue is empty, storing the first multi-cycle pipelined instruction in a first entry of the dependent execution queue, and when the dependent execution queue is not empty, storing the first multi-cycle pipelined instruction in a first entry of the dependent execution queue and in a first entry of the independent execution queue, and setting a result pending indicator for the first multi-cycle pipelined instruction in the first entry of the dependent execution queue to indicate that it is waiting for result data; and
when an operand of the first multi-cycle pipelined instruction includes a dependency on any instruction stored in the dependent execution queue, storing the first multi-cycle pipelined instruction in a first entry of the dependent execution queue.
18. The method of claim 17 , further comprising:
when a multi-cycle instruction reaches a bottom entry of the dependent execution queue and is selected for execution, not removing the multi-cycle instruction from the dependent execution queue until a result is received from the execution unit; and
when a multi-cycle instruction reaches a bottom entry of the independent execution queue and is selected for execution, removing the multi-cycle instruction from the independent execution queue without waiting to receive a result from the execution unit.
19. The method of claim 17 , wherein the processor has a load/store execution queue, and a load/store execution unit, the method further comprising:
determining that an operand of the first multi-cycle pipelined instruction includes a dependency on a load instruction in a first entry of the load/store execution queue;
setting a synchronization indicator corresponding to the first multi-cycle pipelined instruction in a second entry of the load/store execution queue which is immediately adjacent the first entry of the load/store execution queue to indicate that the first multi-cycle pipelined instruction is stored in the dependent or independent execution queue and to indicate a location of the stored first multi-cycle pipelined instruction.