Out-of-order processor that avoids deadlock in processing queues by designating a most favored instruction

• US 10,169,046 B2
• Filed: 08/31/2017
• Issued: 01/01/2019
• Est. Priority Date: 10/31/2016
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Boersma, Maarten J., Cordes, Robert A., Hrusecky, David A., Molnar, Jennifer L., Thompto, Brian W., Van Norstrand, Jr., Albert J., Ward, Kenneth L.
• Primary Examiner(s): Mehta, Jyoti
• Application Number:
  US15/693,387
• Publication Number:
  US 20180121205A1
• Time in Patent Office: 488 Days
• CPC Class Codes: G06F 11/30 Monitoring
• CPC Class Codes: G06F 11/302 where the computing system component is a software system
• CPC Class Codes: G06F 11/3404 for parallel or distributed programming
• CPC Class Codes: G06F 11/3466 Performance evaluation by tracing or monitoring
• CPC Class Codes: G06F 12/0875 with dedicated cache, e.g. instruction or stack
• CPC Class Codes: G06F 2201/81 Threshold
• CPC Class Codes: G06F 2201/865 Monitoring of software
• CPC Class Codes: G06F 2201/88 Monitoring involving counting
• CPC Class Codes: G06F 2212/452 Instruction code
• CPC Class Codes: G06F 9/30043 LOAD or STORE instructions; Clear instruction
• CPC Class Codes: G06F 9/3005 to perform operations for flow control
• CPC Class Codes: G06F 9/3009 Thread control instructions
• CPC Class Codes: G06F 9/30181 Instruction operation extension or modification
• CPC Class Codes: G06F 9/3802 Instruction prefetching
• 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
• CPC Class Codes: G06F 9/3856 Reordering of instructions, e.g. using queues or age tags
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/524 Deadlock detection or avoidance

Abstract

An instruction sequencing unit in an out-of-order (OOO) processor includes a Most Favored Instruction (MFI) mechanism that designates an instruction as an MFI. The processing queues in the processor identify when they contain the MFI, and assures processing the MFI. The MFI remains the MFI until it is completed or is flushed, and which time the MFI mechanism selects the next MFI.

Claims

1. A processor for executing software instructions, the processor comprising:

a plurality of processing queues that process the software instructions and provide out-of-order processing of the software instructions when specified conditions are satisfied;

an instruction sequencing unit circuit that determines a sequence of the software instructions executed by the processor, wherein the instruction sequencing unit circuit comprises a most favored instruction circuit that selects an instruction as the most favored instruction (MFI) and communicates the MFI to the plurality of processing queues; and

wherein at least one of the plurality of processing queues comprises a plurality of slots that receive any instruction that is not the most favored instruction when written to one of the plurality of slots, and a dedicated slot for processing the MFI, wherein the dedicated slot cannot process any instruction that is not the MFI.

2. The processor of claim 1 wherein the most favored instruction circuit selects a thread and selects an oldest instruction in the selected thread as the most favored instruction.

3. The processor of claim 1 wherein the most favored instruction circuit communicates the MFI to the plurality of processing queues via a flag transmitted on an Itag bus with an Itag for the MFI.

4. The processor of claim 1 wherein, when the MFI is in one of the plurality of processing queues, the one processing queue assures processing of the MFI.

5. The processor of claim 1 further comprising:

a deadlock counter that detects when the processor has executed a number of cycles that exceeds a predetermined threshold value without issuing an instruction, and in response, flushes at least one of the plurality of processing queues.

6. The processor of claim 1 wherein, when the MFI is completed or is flushed, the most favored instruction circuit selects a next instruction as the MFI.

7. A method for executing software instructions in a computer program by a processor, the method comprising the steps of:

providing in the processor a plurality of processing queues that process the software instructions and provide out-of-order processing of the software instructions when specified conditions are satisfied;

providing an instruction sequencing unit circuit that determines a sequence of the software instructions executed by the processor, wherein the instruction sequencing unit circuit selects an instruction as the most favored instruction (MFI) and communicates the MFI to the plurality of processing queues;

providing a plurality of slots in at least one of the plurality of processing queues, wherein the plurality of slots receive any instruction that is not the most favored instruction when written to one of the plurality of slots; and

providing a dedicated slot for processing the MFI in the at least one of the plurality of processing queues, wherein the dedicated slot cannot process any instruction that is not the MFI.

8. The method of claim 7 wherein the instruction sequencing unit circuit selecting an instruction as the most favored instruction comprises:

selecting a thread; and

selecting an oldest instruction in the selected thread as the most favored instruction.

9. The method of claim 7 further comprising:

communicating the MFI to the plurality of processing queues via a flag transmitted on an Itag bus with an Itag for the MFI.

10. The method of claim 7 further comprising:

when the MFI is in one of the plurality of processing queues, the one processing queue assures processing of the MFI.

11. The method of claim 7 further comprising:

detecting when the processor has executed a number of cycles that exceeds a predetermined threshold value without issuing an instruction; and

in response, flushing at least one of the plurality of processing queues.

12. The method of claim 7 further comprising:

when the MFI is completed or is flushed, selecting a next instruction as the MFI.