Mechanism for completing atomic instructions in a microprocessor

Method and apparatus for completing atomic instructions in a microprocessor may be provided by identifying from a program-ordered Instruction Completion Table (ICT) a last entry in a completion window of instructions for completion in a current clock cycle of a processor; in response to determining that the last entry includes an atomic instruction that straddles the completion window: excluding the last entry from completion during the current clock cycle; completing instructions in the completion window for the current clock cycle; and shifting the completion window to include the last entry and a next entry adjacent to the last entry in the ICT in a next clock cycle.

BACKGROUND

The disclosure relates to processors, and more specifically, to improvements in the functionality thereof in the handling of atomic instructions. Atomic instructions are instructions that a processor handles as an indivisible unit to be completed at the same time. Some atomic instructions may include several sub-instructions that the processor is directed to complete as one atomic instruction.

SUMMARY

According to one embodiment of the present invention, a method for completing atomic instructions is provided, the method comprising: identifying from a program-ordered Instruction Completion Table (ICT) a last entry in a completion window of instructions for completion in a current clock cycle of a processor; in response to determining that the last entry includes an atomic instruction that straddles the completion window: excluding the last entry from completion during the current clock cycle; completing instructions in the completion window for the current clock cycle; and shifting the completion window to include the last entry and a next entry adjacent to the last entry in the ICT in a next clock cycle.

According to another embodiment of the present invention, a system for completing atomic instruction is provided, the system comprising: system, comprising: a computational unit; an Instruction Completion Table (ICT), including a plurality of entries, each entry of the plurality of entries including at least two instructions for processing by the computational unit, wherein the entries are organized in a program order in the ICT; a controller, in communication with the computational unit and the ICT, configured to: identify a last entry in a completion window of the ICT for a current clock cycle; in response to determining that the last entry includes an atomic instruction that straddles the completion window: prevent the computational unit from completing instructions included in the last entry during the current clock cycle; allow the computational unit to complete instructions included in other entries in the completion window during the current clock cycle; and shift the completion window to include the last entry and a next entry adjacent to the last entry in the ICT in a next clock cycle.

According to another embodiment of the present invention, a computer-readable storage medium having computer-readable program code embodied therewith for completing atomic instruction is provided, the computer program product comprising: a computer-readable storage medium having computer-readable program code embodied therewith, the computer-readable program code executable by one or more computer processors to: identify from a program-ordered Instruction Completion Table (ICT) a last entry in a completion window of instructions for completion in a current clock cycle of a processor, wherein each entry in the ICT is associated with more than one instruction; in response to determining that the last entry includes an atomic instruction that straddles the completion window: excluding the last entry from completion during the current clock cycle; completing instructions in the completion window for the current clock cycle; and shifting the completion window to include the last entry and a next entry adjacent to the last entry in the ICT in a next clock cycle.

DETAILED DESCRIPTION

Modern processors may complete multiple instructions per clock cycle. These processors may issue and finish instructions out of order relative to the order specified in a program using those instructions (a program order), and may have many instructions in-process at any given time. To ensure that the instructions complete in program order, despite being handled in a potentially different order by the processor, the instructions are tracked in an Instruction Completion Table (ICT). The Instruction Completion Table (ICT) for a processor may include references for several instructions in the program order for those instructions, and the statuses of those instructions. In some embodiments, a tail pointer is maintained to point to the oldest not finished instruction in the ICT so that the processor may complete all instructions stored in the ICT before (relative to the program order) the pointed-to instruction.

When using a tail pointer that points to the oldest non-finished instruction to complete all instructions earlier in the ICT, the operation of the processor may be disrupted when the instruction pointed to is part of an atomic instruction. Atomic instructions include several sub-instructions, each of which occupies an individual position in the ICT, but that the processor is to complete during the same clock cycle as the other sub-instructions that make up the atomic instruction. If one sub-instruction is noted by the tail pointer to be the non-finished instruction, but an earlier sub-instructions is noted as finished, the processor may attempt to complete the earlier sub-instruction at a different time than the later sub-instruction; violating the atomic nature of the set of sub-instructions.

To improve the functionality of computing devices using instruction sets with atomic instructions, a sliding completion window is used in association with the finished status and atomic status information in a Ready to Complete (RTC) vector associated with an ICT. The atomic status information indicates whether the instruction(s) at a given table entry correspond(s) to an atomic begin or an atomic end. The atomic begin corresponds to the first sub-instruction of a given atomic instruction in the program order and the atomic end corresponds to the last sub-instruction of the given atomic instruction in the program order. The position of the tail pointer may be adjusted according to not only the status of the individual instruction (finished/non-finished), but also according to the atomic identifier for that instruction so that the tail pointer is moved depending on the completion status and atomic nature of the instruction.

As used herein, numbers in bases other than base ten are identified with a subscript identifying the base that should be used to interpret the number. For example, the number 11 will be understood to be a base ten representation of eleven, while 112will be understood to be a base two representation of three, while 1116will be understood to be a base sixteen (hexadecimal) representation of seventeen. Examples given in the present disclosure that refer to an index or a position of a given value in an array or matrix shall begin at 1 (rather than 0), and the teachings provided by the present disclosure may be applied in embodiments using different indexing and/or ordering schemes than used in the examples.

With reference now toFIG. 1, a microprocessor unit100is illustrated, as may be part of a computing device. An instruction completion table (ICT)110is organized as a circular list with each entry in the ICT110tracking a one or more instructions for the microprocessor unit100to track whether those instructions are ready for completion. Once an entry is completed, the instructions in that entry may be flushed so that the ICT100may reuse those entries for later instructions. The ICT110orders how the instructions are assigned to the entries in program order, although the individual instructions may be handled in any order. The program order specifies that an instruction held in an earlier entry is to be completed before an instruction held in a later entry for the orderly use of a program using the microprocessor unit100to perform calculations and hardware commands on behalf of that program.

A Ready to Complete (RTC) vector120is associated with the ICT110such that each entry in the RTC vector120is associated with the statuses of the entries in the ICT110. The RTC vector120provides a controller130in communication with the ICT110and computational unites140in the microprocessor unit110with knowledge of the instructions stored in the ICT110without needing to query the ICT110directly.

The instructions in the ICT110are processed by the computational units140, and may read or write from various memory150in the microprocessor unit100or external to the microprocessor unit100, including registers, storage devices, sensors, and other external devices. Once the computational units140have finished a given instruction, the controller130may update the ICT110and/or the RTC vector120to reflect that the given entry has instructions that are finished and ready for completion. The controller130may then signal the computational units140to complete the instructions in the associated entries when the order and status of the entries in the ICT110allows for completion in program order.

FIG. 2A, illustrates an example of a Ready to Complete (RTC) vector120associated with an Instruction Completion Table (ICT)110. The RTC vector120includes a completion status bit210for each entry in the ICT110, which may be set to 02or 12to indicate whether the associated instruction in the ICT110is not-ready for completion or finished (i.e., ready for completion) respectively. Additionally, one or more atomic status bits220in the RTC vector120may be associated with each entry in the ICT110to identify when the given entry includes the start or the end of an atomic instruction. For example, a first atomic status bit220amay indicate that the associated entry includes the beginning of an atomic instruction when set to 12, and a second atomic status bit220bmay indicate that the associated entry includes the end of an atomic instruction when set to 12. In another example, a single atomic status bit220may be used to track whether the associated entry includes an atomic begin instruction.

For clarity in the figures, the status bits (completion status bits210and atomic status bits220) for some of the entries are omitted from illustrated views, but each entry in the RTC vector120is associated with status bits that track the finished/non-finished status and atomic nature of the associated instructions. For purposes of the examples given herein, unless indicated otherwise, the completion status bits210for the non-illustrated entries may be assumed to be set to 12(indicating that the associated instructions are ready for completion) and the atomic status bits220for the non-illustrated may be assumed to be set to 02(indicating that the associated instructions are non-atomic).

In embodiments that include multiple instructions per entry in the ICT110, the completion status bit210for a given entry is set to 02or 12when all instructions in that entry are finished, but the atomic status bit(s)220is set to 02or 12based on at least one instruction in that entry having a particular atomic status (atomic begin or atomic end). For example, when using a first atomic status bit220ato indicate the presence of an atomic begin, and a second atomic status bit220bto indicate the presence of an atomic end, the atomic status bits220may indicate: 002when neither instruction is part of an atomic instruction; 012when at least one instruction is an atomic start; 102when at least one instruction is an atomic end; and 112when one instruction is an atomic start and one instruction is an atomic end. As will be appreciated, an atomic status of 112may indicate that a complete atomic instruction (i.e., the start through the end instructions) is included in one entry, or may indicate that two atomic instructions neighbor each other in the ICT110(e.g., the end of a first atomic instruction and the start of a second atomic instruction are included in one entry). The controller130may therefore evaluate the atomic status bits220to determine whether to examine neighboring entries before determining whether to allow completion of a given entry.

The example RTC vector120inFIG. 2Ais shown with thirty-two entries, corresponding to an ICT110with thirty-two entries, but an ICT110may have any number of entries in various embodiments, referred to herein as Z entries, each of which may track one or more instructions. In some embodiments, the computational units140may not be practically able to complete all Z entries in an associated ICT110in a single clock cycle; therefore the controller130may throttle the computational units140to complete a subset of the Z entries in a single clock cycle within a completion window230of Y entries. Furthermore, various word boundaries240of X entries in the ICT110may be set to ensure that the computational units140complete instructions up to a word boundary240in the ICT110by aligning the completion window230with the word boundaries240, so that the computational units140may start completing entries from one position, but will stop completing entries at a position that is an even multiple of X.

For example, with Z=32, Y=16, and X=8 as in the example RTC vector120inFIG. 2A, with a tail pointer initially set to position 1 in the RTC vector120, the computational units140may complete instructions in entries 1 through 16. The computational units140may complete these instructions in the present example because the completion window230of Y=16 allows for up to 16 entries to be completed in a single clock cycle, each of the entries 1-16 are noted as being finalized in associated completion status bits210, and position 16 falls at an even multiple of X.

In another example, with Z=32, Y=16, and X=8 as in the example RTC vector120inFIG. 2A, with a tail pointer initially set to position 6 in the RTC vector120, the computational units140may complete instructions in entries 6 through 16. The computational units140may complete these instructions in the present example because the completion window230of Y=16 allows for up to 16 entries to be completed in a single clock cycle, and position 16 falls at an even multiple of X, but position 22 (pointer+Y; 6+16=22) does not fall at an even multiple of X, and is outside of the completion window230.

FIG. 2Billustrates a second example RTC vector120, with an atomic instruction split between entries 16 and 17. In an example, with Z=32, Y=16, and X=8 with reference to the RTC vector120inFIG. 2B, with a tail pointer initially set to position 6 in the RTC vector120, the computational units140may initially attempt to complete instructions in entries 6 through 16. Because the entry in position 16 includes an atomic start instruction of an atomic instruction that completes with an atomic end instruction in position 17, the computational units140may not complete the instructions in entry 16 without completing the atomic end instruction in position 17; resulting in a deadlock or error if not resolved.

To resolve the potential deadlock/error outlined above, the controller130analyzes the completion status bits210and the atomic status bits220to determine which entries to complete, and slides the completion window230to include both of the atomic instructions for consideration for completion in a subsequent clock cycle. Because the completion window230is set larger than the word boundary240(i.e., Y>X), the computational units140may complete the finalized instructions up to the atomic instruction (i.e., from the pointer to position 15) in the initial completion window230, and the controller130shifts the completion window230to different word boundaries240to include both atomic instructions in a single completion window230for the subsequent clock cycle. For example, inFIG. 2B, the completion window230is originally set to coincide with positions 1 through 16, but is shifted to coincide with positions 8 through 24 for the next clock cycle so that the atomic instructions at positions 16 and 17 may be completed during the same clock cycle as one another. In the first clock cycle, the instructions in entries 6 through 15 are completed, and the second clock cycle, entries 16 up to 24 (or the next non-finished entry at a position between 16 and 24) are completed.

FIG. 3is a flowchart for an example method300for completing atomic instructions in a microprocessor. Method300begins with block310, where a controller130identifies a last entry in a completion window230for the current clock cycle. The completion window230may span from one word boundary240to another word boundary240, and is sized to be larger than a given word boundary240(i.e., Y>X).

At block320, the controller130determines whether the last entry in the completion window230includes an atomic start instruction. The controller130may query one or atomic status bits220in an RTC vector120to determine whether the corresponding entry in the ICT110includes a part of an atomic instruction. For example, a first atomic status bit220amay indicate that the entry includes an atomic start instruction and a second atomic status bit220bmay indicate that the entry includes an atomic end instruction. In another example, a single atomic status bit220may indicate whether the entry includes an atomic start instruction, and due to the ICT110maintaining the instructions in program order, the controller130may infer that the next entry includes the atomic end command. If the controller130determines that the entry does not include an atomic start instruction, method300proceeds to block330. If the controller130determines that the entry includes an atomic start instruction and the ICT110tracks multiple instructions per entry, method300proceeds to block350. In embodiments that track one instruction per entry in the ICT110, block350may be omitted from method300, and method300proceeds to block360if the controller130determines that the last entry includes an atomic start instruction.

At block330, controller130allows the computational units140to complete the instructions marked as finished in the ICT110in the current completion window230. In some embodiments, the controller130flushes the entries that have been completed and/or allows later received instructions from a program to overwrite the instructions marked as completed.

At block340, the microprocessor unit100advances to the next clock cycle. When all entries in the current completion window230are completed, the controller130shifts the completion window230such that the word boundary240where the current completion window230ends is the word boundary240where the next completion window230begins. For example, with a completion window230spanning position 1 to position 64 (i.e., Y=64), with word boundaries240set at positions of multiples of 32 (i.e., X=32), once entries in positions 1 through 64 have been completed, the completion window230shifts to span positions 65 to 128. Method300then returns to block310.

At block350, the controller130determines whether an atomic instruction for which the atomic start instruction (as a sub-instruction) is included in the last entry straddles the current completion window230. In embodiments that include multiple instructions in a single entry, the controller130determines whether the last entry includes the atomic start and the atomic end sub-instructions. For example, a second atomic status bit220bmay indicate that the last entry that includes the atomic start instruction (as determined per block320) may also include the atomic end instruction for the atomic instruction. If the controller130determines that the entry does not include an atomic end instruction, method300proceeds to block370. If the controller130determines that the entry includes an atomic end instruction, the controller130determines whether an entry in the ICT110that is adjacent to the last entry in the ICT110(which includes the atomic start) includes an atomic instruction to indicate whether the atomic start in the last entry straddles the current completion window230.

In some embodiments, the adjacent entry that is checked is the next entry in the ICT100(which is outside of the completion window230but adjacent to the last entry that was determined to include an atomic start). The next entry may be checked, via a second atomic status bit220b, to determine if an atomic end instruction is included in the next entry. In other embodiments, the adjacent entry that is checked is the prior entry in the ICT110(which is inside of the completion window230and adjacent to the last entry that was determined to include an atomic start). The prior entry may be checked, via a first atomic status bit220a, to infer whether an atomic start instruction is included in the next entry. If the prior entry includes an atomic start, the controller130may determine that the last entry includes an atomic end for the atomic start in the prior entry, and an atomic start that has an atomic end included in the next entry (outside of the current completion window230). If the controller130determines that the next entry includes an atomic end, indicating that an atomic start in the last entry straddles the current completion window230to end in the next entry, method300proceeds to block360. If the controller130determines that the next entry does not include an atomic end, indicating that the last entry in the completion window230includes both the atomic start and atomic end for a given atomic instruction, method300proceeds to block330.

At block360, the controller130allows the computational units140to complete the instructions marked as finished in the ICT110in the current completion window230during the current clock cycle except for those included in the last entry. For example, in a completion window230of 64 entries (i.e., Y=64) that spans positions 1 through 64, the computational units140may complete instructions in entries 1 through 63, but will not complete the instructions in entry 64 in the current clock cycle. The controller130may prevent the computational units140from completing the last entry by shifting a tail pointer from the last entry to the prior entry (or an even earlier entry without atomic instructions included therein) to signal the computational units140where to end instruction completion.

At block370, the microprocessor unit100advances to the next clock cycle. When all entries in the current completion window230are completed up to the last entry, the controller130may shift the completion window230such the next completion window230ends at the next word boundary240relative to the word boundary240where the current completion window230ends. For example, with a completion window230spanning position 1 to position 64 (i.e., Y=64), with word boundaries240set at positions of multiples of 32 (i.e., X=32), once entries in positions 1 through 63 have been completed, the controller130shifts the completion window230to span positions 33 to 96. In another example, with a completion window230spanning position 1 to position 64 (i.e., Y=64), with word boundaries240set at positions of multiples of 16 (i.e., X=16), once entries in positions 1 through 63 have been completed, the controller130shifts the completion window230to span positions 17 to 80. Method300then returns to block310.