Resource locking for load store scheduling in a VLIW processor

• US 10,346,165 B2
• Filed: 10/31/2014
• Issued: 07/09/2019
• Est. Priority Date: 04/25/2014
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Inventors: Kurd, Tariq
• Primary Examiner(s): Petranek, Jacob
• Application Number:
  US14/530,117
• Publication Number:
  US 20150309793A1
• Time in Patent Office: 1,712 Days
• CPC Class Codes: G06F 9/30145 Instruction analysis, e.g. decoding, instruction word fields
• CPC Class Codes: G06F 9/30181 Instruction operation extension or modification
• CPC Class Codes: G06F 9/3834 Maintaining memory consistency
• CPC Class Codes: G06F 9/3836 Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution

Abstract

A load/store unit including a memory queue configured to store a plurality of memory instructions and state information indicating whether each memory instruction of the plurality of memory instructions can be performed independently, with, separately, or after older pending instructions; and a state-selection circuit configured to set a state information of each memory instruction of the plurality of memory instructions in view of an older pending instruction in the memory queue.

Claims

1. A method, comprising:

receiving, by a load/store queue, a memory instruction requiring a first memory resource;

comparing, by a state-selection circuit, the memory instruction against an older memory instruction of a plurality of pending memory instructions stored in the load/store queue, and requiring a second memory resource;

setting a state information for the memory instruction that includes information regarding respective states of the plurality of pending memory instructions when the memory instruction is moved from a first portion of a load/store unit to a second portion of the load/store unit; and

setting a status, by the state-selection circuit, to indicate whether (i) the memory instruction can be performed independent of the older memory instruction;

(ii) the memory instruction can be performed if the older memory instruction cannot be performed;

(iii) the memory instruction can be performed concurrently with the older memory instruction;

or (iv) the memory instruction must be performed, if at all, after the older memory instruction is performed,

wherein the memory instruction is evaluated against other pending memory instructions in the load/store queue within a single processor clock cycle.

2. The method of claim 1, wherein the memory instruction and the older memory instruction are concurrently pending in the load/store queue.

3. The method of claim 1, wherein the memory instruction or the older memory instruction comprise load instructions or store instructions.

4. The method of claim 1, wherein the setting the status comprises setting the status when the memory instruction is received by the load/store queue in the second portion of the load/store unit.

5. The method of claim 1, wherein the memory instruction and the older memory instruction can be performed independently when the first memory resource and the second memory resource correspond to different memory banks.

6. The method of claim 1, wherein the memory instruction can be performed when the older memory instruction is not performed and the first and second memory resources specify a same memory bank, but different indices.

7. The method of claim 1, wherein the memory instruction can be performed when the older memory instruction is performed, the memory instruction and the older memory instruction include a same type of memory instruction, and the first and second memory resources correspond to a same memory bank and a same index.

8. The method of claim 1, wherein the memory instruction can be performed when the older memory instruction is not performed, the memory instruction and the older memory instruction include different types of memory operations, the first and second memory resources correspond to a same memory bank and a same index, and the first and second memory resources do not correspond to same memory bytes.

9. The method of claim 1, wherein the memory instruction can only be performed after the older memory instruction is performed when the memory instruction and the older memory instruction include different types of memory operations, the first and second memory resources correspond to a same memory bank and a same index, and the first and second memory resources correspond to at least one common memory byte.

10. An apparatus, comprising:

a memory queue configured to store a plurality of memory instructions and state information indicating whether each memory instruction of the plurality of memory instructions can be performed independently, with, separately, or after older pending memory instructions of the plurality of memory instructions; and

a state-selection circuit configured to set a respective state information for each memory instruction of the plurality of memory instructions in view of respective older pending memory instructions in the memory queue when each memory instruction is moved from a first portion of a load/store unit to a second portion of the load/store unit, wherein the respective state information includes information regarding respective states of older pending memory instructions, and

wherein a memory instruction of the plurality of memory instructions is evaluated against other older pending memory instructions of the plurality of memory instructions in the memory queue within a single processor clock cycle.

11. The apparatus of claim 10, wherein the plurality of memory instructions comprise load or store instructions.

12. The apparatus of claim 10, wherein the state-selection circuit generates the state information of the memory instruction in the single processor clock cycle.

13. The apparatus of claim 10, wherein the state-selection circuit is further configured to generate the state information when a new memory instruction is put into the memory queue in the second portion of the load/store unit.

14. The apparatus of claim 10, wherein the state-selection circuit is further configured to set an instruction-pair state information to indicate the plurality of memory instructions are independent if they do not correspond to same memory banks.

15. The apparatus of claim 10, wherein the state-selection circuit is further configured to set an instruction-pair state information to indicate that either instruction can be performed but not both if they correspond to a same memory bank with different indices.

16. The apparatus of claim 10, wherein the state-selection circuit is further configured to set an instruction-pair state information to indicate that a younger memory instruction can be performed with the older memory instruction if they correspond to a same memory bank and a same index and are a same type of instruction.

17. The apparatus of claim 10, wherein the state-selection circuit is further configured to set an instruction-pair state information to indicate that either memory instruction can be performed but not both concurrently if they correspond to a same memory bank and a same index, they are different operations, and they do not correspond to a common memory byte.

18. The apparatus of claim 10, wherein the state-selection circuit is further configured to set an instruction-pair state information to indicate that a younger instruction must be performed after the older instruction if they correspond to a same memory bank and a same index, they are different operations, and they correspond to a common memory byte.

19. A method, comprising:

identifying, by a state-update circuit, a first instruction that is an oldest non-evaluated pending memory instruction of a plurality of pending memory instructions;

determining, by the state-update circuit, whether the first instruction is currently eligible to be issued;

modifying, by the state-update circuit, a respective state for each remaining non-evaluated instruction of the plurality of pending memory instructions whose state indicated that they could be issued when the non-evaluated instruction is moved from a first portion of a load/store unit to a second portion of the load/store unit and when the first instruction issued to indicate that the plurality of pending memory instructions are independent if the determination is affirmative, wherein the respective state information includes information regarding respective states of respective older pending memory instructions; and

marking, by a load/store unit control logic circuit, the first instruction as eligible to be performed if the determination is affirmative,

wherein the first instruction is evaluated against the plurality of pending memory instructions within a single processor clock cycle.

20. The method of claim 19, further comprising:

modifying, by the state-update circuit, a state for each remaining non-evaluated instruction whose state indicated that it could be performed when the first instruction was not performed to indicate that the plurality of pending memory instructions are independent if the determination is affirmative.

21. The method of claim 19, further comprising selecting instructions to be performed from the plurality of pending memory instructions marked as eligible to be performed.

22. The method of claim 21, further comprising performing the selected instructions.

23. The method of claim 22, further comprising reverting the state for the pending instructions.

24. The method of claim 20, further comprising reverting the state for the pending instructions.

25. The method of claim 19, wherein the determining comprises determining that the oldest non-evaluated pending instruction does not conflict with any older pending memory instruction.

26. The method of claim 22, wherein the selecting is based on the instructions marked eligible to be performed.

27. The method of claim 22, wherein the state associated with selected instructions is cleared.

28. An apparatus, comprising:

a memory queue configured to store a plurality of memory instructions and state information indicating whether each memory instruction of the plurality of memory instructions is to issue independently, with, separately, or after older pending memory instructions of the plurality of memory instructions and if it is eligible to be performed; and

a state-update circuit configured to update a state information for a first memory instruction of the plurality of memory instructions, when the first memory instruction is moved from a first portion of a load/store unit to a second portion of the load/store unit, indicating the relation between the first memory instruction and an older pending memory instruction of the plurality of memory instructions based on if the older pending memory instruction is eligible to be performed, wherein the state information includes information regarding respective states of every older pending memory instruction, and

wherein the first memory instruction is evaluated against the older pending memory instructions in the memory queue within a single processor clock cycle.

29. The apparatus of claim 28, wherein the plurality of memory instructions comprises load instructions or store instructions.

30. The apparatus of claim 28, wherein the state-update circuit updates the state of the memory instruction in the single memory queue clock cycle.

31. The apparatus of claim 28, wherein the state-update circuit is further configured to determine if the first memory instruction is eligible to be performed.

32. The apparatus of claim 31, wherein the state-update circuit is further configured to determine if the first memory instruction is eligible to be performed by determining if it is independent of all older pending memory instructions.

33. The apparatus of claim 28, wherein the state-update circuit is further configured to select a memory instruction to perform from the plurality of memory instructions marked eligible to be performed.

34. The apparatus of claim 33, wherein the state-update circuit is further configured to revert the state of the pending memory instructions once the selected memory instruction issues.

35. The apparatus of claim 33, wherein the state-update circuit is further configured to clear all states associated with the selected instruction.