Patent ID: 12204902

DETAILED DESCRIPTION

The following description is made for illustrating the general principles of the invention and is not meant to limit the inventive concepts claimed herein. In the following detailed description, numerous details are set forth in order to provide an understanding of the computer system, computer architectural structure, processor, processor architectural structure, processor execution pipelines, functional units, register files, and their method of operation, however, it will be understood by those skilled in the art that different and numerous embodiments of the computer system, computer architectural structure, processor, processor architectural structure, processor execution pipelines, functional units, and their method of operation may be practiced without those specific details, and the claims and invention should not be limited to the system, assemblies, subassemblies, architecture, embodiments, functional units, features, circuitry, processes, methods, aspects, and/or details specifically described and shown herein. Further, particular features described herein can be used in combination with other described features in each of the various possible combinations and permutations.

Unless otherwise specifically defined herein, all terms are to be given their broadest possible interpretation including meanings implied from the specification as well as meanings understood by those skilled in the art and/or as defined in dictionaries, treatises, etc. It must also be noted that, as used in the specification and the appended claims, the singular forms “a,” “an” and “the” include plural referents unless otherwise specified, and that the terms “comprises” and/or “comprising” specify the presence of stated features, integers, steps, operations, elements, and/or components, but do not preclude the presence or addition of one or more features, integers, steps, operations, elements, components, and/or groups thereof.

The following discussion omits or only briefly describes conventional features of information processing systems, including microprocessors, processors, processor architecture, processor execution pipelines, processor functional units, and register files which are apparent to those skilled in the art. It is assumed that those skilled in the art are familiar with the general architecture of processors, and, in particular, with processors having execution pipelines where each execution pipeline has one or more functional units including one or more execution units.

FIG.1illustrates an example computing and/or data processing system100in which aspects of the present disclosure may be practiced. It is to be understood that the computer and/or data processing system100depicted is only one example of a suitable processing system and is not intended to suggest any limitation as to the scope of use or functionality of embodiments of the present invention. For example, the system shown may be operational with numerous other special-purpose computing system environments or configurations. Examples of well-known computing systems, environments, and/or configurations that may be suitable for use with the system shown inFIG.1may include, but are not limited to, server computer systems, mainframe computers, distributed cloud computer systems, personal computer (PC) systems, PC networks, thin clients, thick clients, minicomputer systems, handheld or laptop devices, multiprocessor systems, microprocessor-based systems, smart phone, set top boxes, and programmable consumer electronics, that include any of the above systems or devices, and the like.

In some embodiments, the computer system100may be described in the general context of computer system executable instructions, embodied as program modules stored in memory112, being executed by the computer system. Generally, program modules may include routines, programs, objects, components, logic, data structures, and so on that perform particular tasks and/or implement particular input data and/or data types in accordance with the present invention.

The components of the computer system100may include, but are not limited to, one or more processors or processing units110, a memory112, and a bus115that operably couples various system components, including memory112to processor110. In some embodiments, the processor110, which is also referred to as a central processing unit (CPU) or microprocessor, may execute one or more programs or modules108that are loaded from memory112, where the program module(s) embody software (program instructions) that cause the processor to perform one or more operations. In some embodiments, module108may be programmed into the integrated circuits of the processor110, loaded from memory112, storage device114, network118and/or combinations thereof.

The processor (or CPU)110can include various functional units, registers, buffers, execution units, caches, memories, and other units formed by integrated circuitry, and may operate according to reduced instruction set computing (“RISC”) techniques. The processor110processes data according to processor cycles, synchronized, in some aspects, to an internal clock (not shown). Bus115may represent one or more of any of several types of bus structures, including a memory bus or memory controller, a peripheral bus, an accelerated graphics port, and a processor or local bus using any of a variety of bus architectures. By way of example, and not limitation, such architectures include Industry Standard Architecture (ISA) bus, Micro Channel Architecture (MCA) bus, Enhanced ISA (EISA) bus, Video Electronics Standards Association (VESA) local bus, and Peripheral Component Interconnects (PCI) bus. The computer system may include a variety of computer system readable media, including non-transitory readable media. Such media may be any available media that is accessible by the computer system, and it may include both volatile and non-volatile media, removable and non-removable media.

Memory112(sometimes referred to as system memory) can include computer readable media in the form of volatile memory, such as random-access memory (RAM), cache memory and/or other forms. Computer system may further include other removable/non-removable, volatile/non-volatile computer system storage media. By way of example only, storage system114can be provided for reading from and writing to a non-removable, non-volatile magnetic media (e.g., a “hard drive”). Although not shown, a magnetic disk drive for reading from and writing to a removable, non-volatile magnetic disk (e.g., a “floppy disk”), and an optical disk drive for reading from or writing to a removable, non-volatile optical disk such as a CD-ROM, DVD-ROM or other optical media can be provided. In such instances, each can be connected to bus115by one or more data media interfaces.

The computer system may also communicate with one or more external devices102such as a keyboard, track ball, mouse, microphone, speaker, a pointing device, a display104, etc.; one or more devices that enable a user to interact with the computer system; and/or any devices (e.g., network card, modem, etc.) that enable the computer system to communicate with one or more other computing devices. Such communication can occur via Input/Output (I/O) interfaces106. Communications adapter116interconnects bus115with an outside network118enabling the data processing system100to communicate with other such systems. Additionally, an operating system such as, for example, AIX (“AIX” is a trademark of the IBM Corporation) is used to coordinate the functions of the various components shown inFIG.1.

The computer system100can communicate with one or more networks118such as a local area network (LAN), a general wide area network (WAN), and/or a public network (e.g., the Internet) via network adapter116. As depicted, network adapter118communicates with the other components of computer system via bus115. It should be understood that although not shown, other hardware and/or software components could be used in conjunction with the computer system. Examples include, but are not limited to: microcode, device drivers, redundant processing units, external disk-drive arrays, RAID systems, tape drives, and data archival storage systems, etc.

FIG.2depicts a simplified block diagram of a processor110according to an embodiment. The processor110includes memory202, instruction cache204, instruction fetch unit206, decode unit210, dispatch unit220, an execution slice225that includes LSU processing pipeline230and VSU processing pipeline260, and destination resource290. The processor110may be included within a computer system or otherwise distributed within a computer system, e.g., computer system100. Instructions and data can be stored in memory202, and the instruction cache204may access instructions in memory202and store the instructions to be fetched. The memory202may include any type of volatile or nonvolatile memory. The memory202and instruction cache204can include multiple cache levels.

InFIG.2, a simplified example of instruction fetch unit206, decode unit210, dispatch unit220, and execution slice225are depicted. In various embodiments, the processor110may include multiple processing execution slices225, e.g., four execution slices225. In an embodiment, each execution slice225includes processing pipeline0(230) and processing pipeline1(260). In an aspect, processing pipeline0(230) includes issue unit0(235), execution unit0(240), and physical register file0(250). Execution unit240in an embodiment includes one or more execution units245, for example, a load-store unit, a vector-scalar unit, store/simple/branch (SX) unit, etc. Processing pipeline0(230) may also include other features, such as error checking and handling logic, one or more parallel paths through processing pipeline0(230), and other features now or hereafter known in the art. In an aspect, processing pipeline1(255) includes issue unit1(270), execution unit1(275), and physical register file1(285). Execution unit275in an embodiment includes one or more execution units280, for example, a vector-scalar unit, a Fixed point (FX) unit, an Arithmetic Logic Unit (ALU), etc. Processing pipeline1260may also include other features, such as error checking and handling logic, one or more parallel paths through processing pipeline1(260), and other features now or hereafter known in the art. Processor pipeline225also has a logical register mapper255which maps logical (architectural) register file entries to physical register file entries in register files250,285. That is, in the example embodiment ofFIG.2, processing pipeline0(230) and processing pipeline1(260) share logical register mapper255. Not shown inFIG.2is a history buffer (HD), e.g., a save-restore buffer (SRB), to hold instructions and metadata on instructions evicted from the logical register mapper255.

In the processor110ofFIG.2, the instruction fetch unit206fetches instructions from the instruction cache204according to an instruction address, for further processing by the decode unit210. The decode unit210decodes instructions and passes the decoded instructions, portions of instructions, or other decoded data to the dispatch unit220. The decode unit210may also detect branch instructions. More specifically as an overview, in the example ofFIG.2, the decode unit210will transmit the decoded instruction to the dispatch unit220which will dispatch the decoded instruction to either Issue Unit0(235) or Issue unit1(270). The respective issue units235,270analyze the instructions or other data and transmits the decoded instructions, portions of instructions, or other data to execution units240,275in the respective pipelines230,255based on the analysis. The respective physical register file250,285holds data for the respective execution units240,275. Physical register files250,285can be separate register files where data in one register file can be used by either execution unit240,275, and in an embodiment register files250,285can be a single register file. While a forward path through the processor110is depicted inFIG.2, other feedback and signaling paths may be included between elements of the processor110.

Processor110also includes result/write back logic290to write the results of executed instructions, e.g., results from processing pipeline230and processing pipeline260, to a destination resource. The destination resource may be any type of resource, including registers, cache memory, other memory, I/O circuitry to communicate with other devices, other processing circuits, or any other type of destination for executed instructions or data. Register files250,285have read ports for reading data residing in entries in the register files250,285, and write ports to write data to entries in the register files250,285. In an embodiment, the results are written back to certain blocks, e.g., STF blocks, of entries in the register files250,285. The processor110may include other circuits, functional units, and components.

Instructions may be processed in the processor110ofFIG.2in a sequence of logical, pipelined stages. However, it should be understood that the functions of these stages and functional units may be merged together so that this particular division of stages should not be taken as a limitation, unless such a limitation is clearly indicated in the claims herein. Indeed, some of the stages or functional units are indicated as a single logic/functional unit inFIG.2for the sake of simplicity of understanding, and further detail as relevant will be provided below.

FIG.3illustrates a block diagram of a portion of a processor110, and in this example a multi-slice processor110in accordance with an embodiment of the disclosure. It may be noted thatFIG.3only shows portions of the multi-slice processor110in diagrammatic fashion for purpose of discussion. It will be appreciated that the multi-slice processor may have other configurations. As shown inFIG.3, the multi-slice processor110includes two processing slices-Slice0(slice S0or225A) and Slice1(slice S1or225B). The processor110also includes Memory202, Instruction Cache204, Instruction Fetch Unit206, Decode Unit210. Each of the slices S0and S1includes an Instruction Dispatch Unit (220A and220B); a Logical Register Mapper (265A and265B); a History Buffer (HB) (366A and366B); a first processing pipeline (230A and230B); and a second processing pipeline (260A and260B). The two processing slices225A and225B share an Instruction Completion Table (ICT) (222).

Each first processing pipeline (230A and230B) includes a first Issue Unit (ISQ) (235A and235B), and first Execution Units (240A and240B), where each execution unit240A,240B in the respective first processing pipeline230A,230B can include multiple execution units, including a SX/Agen execution unit (245A and245B) as shown in the example ofFIG.3. First processing pipeline230A,230B can include other execution units, such as, for example, a load store unit (LSU), a floating-point execution unit (FPU), a fixed point execution unit (FXU), etc. Each second processing pipeline (260A and260B) can include a second Issue Unit (ISQ) (270A and270B) and Execution Units (275A and275B), where each execution unit275A,275B in the respective second processing pipeline260A,260B can include multiple execution units, including a FX/ALU execution unit (280A and280B) as shown in the example ofFIG.3. Second processing pipeline260A,260B) can include other execution units, such as, for example, vector scalar units (VSUs), floating point execution units (FPU), etc.

A physical Register File (RF)250A can be used by both first processing pipeline230A and second processing pipeline260A in SuperSlice225A, while a physical Register File250B can be used by both first processing pipeline230B and second processing pipeline260B in SuperSlice225B. While processor110inFIG.3shows a single register file250A,250B shared between the first and second processing pipelines230,260, it can be appreciated that one or more register files250can be used in the first and second processing pipelines and across execution slices225A and225B. The Execution Units240A,240B,275A,275B can include one or more queues to hold instructions for execution by the Execution Units. It can be appreciated that the physical register files250A,250B contain a plurality of entries, and the physical register files250A,250B can be subdivided into blocks of entries, where in an aspect each block of entries receives (contains one or more write ports to receive) data from a specific execution unit, more specifically a specific execution unit such as for example SX/AGen245, FX/ALU280.

The Instruction Fetch Unit206fetches instructions to be executed by the processor110. Instructions that are fetched by the Instruction Fetch Unit206are sent to the Decode Unit210where the instructions are decoded by instruction type. The Decode Unit210transmits the decoded instructions to respective Instruction Dispatch Unit220A,220B. The Instruction Dispatch Units220A,220B dispatch instructions to first respective Issue Unit235or second respective Issue Unit270depending upon the type of instruction and which execution units240or275should process that particular instruction. The Instruction Dispatch Units220A,220B dispatch the instructions to the respective first Issue Unit235or second Issue Unit270typically in program order. In one or more embodiments, each instruction dispatched to the first Issue Unit235or second Issue Unit270is stamped with an identifier, e.g., identification tag (iTag), to identify the instruction. The instructions can be stamped with other information and metadata. The instructions (iTags) typically are allocated (assigned) and stamped in ascending program order on a per thread basis.

The respective first Issue Unit235or second Issue Unit270will issue instructions to the respective execution units240or execution units275based upon the instruction type. For example, multi-cycle arithmetic instructions, matrix-multiply accumulator (MMA) instructions are typically handled by the second processing pipeline260(for example by FX/ALU execution unit285), while store instructions, load instructions, branch and store instructions are typically handled in the first processing pipeline230(for example in the SX/Agen unit245). The first and second Issue Units235,270typically hold an instruction until data associated with the instruction has been retrieved and ready for use. In certain aspects, the respective first Issue unit235and second Issue Unit270holds a set of instructions while the physical register file250accumulates data for the instruction inputs. A register file may be used for staging data between memory and other functional (execution) units in the processor. There may be numerous register files and types. When all source data accumulates for the instruction, the data in one or more embodiments is passed on to one or more execution units240,275designated for execution of the instruction. A physical register (or main register) file250may serve to store data to be used in an operation specified in an instruction dispatched to Execution Units240,275, and the result of the operation performed by the Execution Units240,275(e.g., SX/Agens245and FX/ALUs280) may be written to the designated target register entry in the physical register file250. Each of the execution units, can make result data available on the write back buses for writing to a register file (STF) entry.

Logical register mapper265contains metadata (e.g., iTag, STFtag, etc.) which provides a mapping between entries in the logical register (e.g., GPR1) and entries in physical (main) register file250(e.g., physical register array entry). The STFtag is the pointer that correlates a logical register entry (LREG) to an entry in the physical register file250. For example, when an instruction wants to read a logical register, e.g., GPR1, the logical register mapper265tells respective issue unit235,270, which tells respective execution unit240,275, e.g., SX/Agen245and FX/ALU280where in the physical register file250it can find the data, e.g., the physical register array entry. The respective Execution Unit240,275, e.g., SX/Agen245or FX/ALU280, executes instructions out-of-order and when the respective Execution Unit240,275finishes an instruction, the respective Execution Unit240,275will send the finished instruction, e.g., iTag, to the ICT222. The ICT222contains a queue of the instructions dispatched by the Dispatch Unit220and tracks the progress of the instructions as they are processed.

When a mispredicted branch instruction or other exception is detected, instructions and data subsequent to the mispredicted branch or exception are discarded, e.g., flushed from the various units of processor110. A history buffer (HB)366, e.g., Save & Restore Buffer (SRB)366, contains both speculative and architected register states and backs up the logical register mapper255when a new instruction is dispatched. In this regard, the history buffer (HB)366stores information from the logical register mapper265when a new instruction evicts data from the logical register mapper265in case the new instruction is flushed and the old data needs to be recovered. The history buffer (HB)366keeps the stored information until the new instruction completes. History buffer (HB)266interfaces with the logical register mapper265in order to restore the contents of logical register mapper265from the history buffer (HB)266back to the logical register mapper265, updating the pointers in the logical register mapper265so instructions know where to obtain the correct data, e.g., the processor is returned to the state that existed before the interruptible instruction, e.g., the before branch instruction was mispredicted.

CPU110having multiple processing slices may be capable of executing multiple instructions simultaneously, for example, one instruction in each processing slice simultaneously in one processing cycle. Such a CPU having multiple processing slices may be referred to as a multi-slice processor or a parallel-slice processor. Simultaneous processing in multiple execution slices may considerably increase processing speed of the multi-slice processor. In single-thread (ST) mode a single thread is processed, and in SMT mode, two threads (SMT2) or four threads (SMT4) are simultaneously processed.

FIG.4illustrates a more detailed view of Dispatch Unit220, register (rename) file250and Mapper265according to one or more embodiments of the disclosure. In one or more embodiments of the processor110, the register file250as illustrated inFIG.4contains a plurality of entries452, and the register file250is sub-divided into two or more blocks455or banks455, each block/bank455containing a plurality of the register file entries452. Physical (rename) register file250also contains a plurality of write ports454and a plurality of read ports456. Register file250further includes a valid (V) register bit field453that is used to indicate whether a register file entry454is available for use. The register file250provides information to Mapper265identifying the register file entries452that are available to receive data (e.g., ready to be used). Mapper265in the example ofFIG.4includes a plurality of mapper entries466and maintains, for each register block455, an available pool (AP)467of rename register entries452that are ready (available) to be allocated. The Mapper265in an embodiment sends to the Dispatch Unit220information indicating each register block465that has register entries452that can be allocated (e.g., are ready for use). The Dispatch Unit220maintains a counter (C)425for each register block455that tracks the number of register file entries452that are available to be allocated. When the Dispatch Unit220sends an instruction to the Mapper265(and Issue Unit235) that uses a register block455, the Dispatch Unit220decrements the counter (C)425for that respective register block455, and when a register entry452is retired by the Mapper265(e.g., after a completion or flush), the Mapper265increments the counter (C)425of that respective register block455.

Each execution unit245,280in one or more embodiments are assigned a block455of register file entries452to which the respective execution unit245,280can write data. Additionally, or alternatively, certain instructions can only be processed in certain execution units in either first processing slice230or second processing slice260. In one or more embodiments, the architectural registers (the logical registers (LREGs)) can in circumstances be assigned so results are written back to the physical (rename) register file entries452in an uneven manner such that some blocks455in register file250become full or nearly full, while other blocks455are underutilized. In circumstances where blocks455of register file entries452are full or nearly full, the processor can stall dispatching instructions to the processing pipelines. To alleviate this potential bottleneck where one or more blocks455of register file entries452are nearly full, while one or more other blocks455of register file entries452are underutilized, a mechanism is provided to dynamically steer results of instructions (e.g., the write of execution unit results) to less full register blocks455to reduce the imbalance of register file entries452in various blocks455of the register file250.

In an embodiment a mechanism is used to detect that an imbalance in register block455usage is occurring based upon the number of entries452available within a particular register block455dropping below a threshold level, and then attempts to rectify the imbalance by steering more of the unrestricted operations to the blocks455that have more available entries452. In an approach, the instructions that can be executed by one or more processing pipelines and/or in one or more execution units can be steered (e.g., assigned and routed) to the processing pipeline and/or execution units that write results to the block455of the register file250that has greater availability of register entries452. In an aspect, Mapper265can send register block utilization rates to Dispatch Unit220. Logic in Dispatch Unit220can review/examine the fullness or utilization status of each register file block455and then steer (e.g., assign and/or route) more instructions to register blocks455that have more unused (empty) entries452.

In another embodiment, routing logic in Dispatch Unit220checks only that there are at least some entries (STF tags)452available in at least some of the blocks455in the register file250, and checks that other resource requirements are met, and makes the initial assignment decision without regard to balancing the register blocks455. After the assignment decision has been made, the specific register entry452assignment is adjusted to not overrun register blocks455that are already full. That is, while register block455assignments in the register file250are usually made in parallel with the routing decision, in an embodiment, a fast adjustment is made one or more cycles after the initial assignment and/or routing decision to minimize unnecessary stalling due to the initial chosen register blocks455being nearly full. This mechanism of making an adjustment later can be beneficial in a highly pipelined processor where usage cannot be communicated immediately everywhere. By making adjustments later in the processing pipeline after the initial assignment decision in the Dispatch Unit, register entries452that were used when making an assignment and/or routing decision can be released (no longer used) by the adjustment stage, and instructions then can be reassigned and routed to register entries452in register blocks455that were recently released.

FIG.5illustrates an example processing of instructions in cycles in a pipeline (e.g., pipeline225A) in processor110according to one or more embodiments of the disclosure. Instructions are decoded in decode unit210and are directed to one of multiple processing pipelines and to one of the execution units in the processing pipeline for execution in the processor. In many processors, a number of instructions can be executed by one or more execution units. For example, simple arithmetic operations, or other trivial instructions can be executed by more than one execution unit. To reduce latency, in situations where register blocks455to which instruction results are to be written are full or nearly full, a processor can direct instructions to one of the one or more pipelines, and to one of the one or more execution units in the processor pipeline that write back the results to a register block455of the register file that has greater capacity than other register blocks455, and/or to avoid a register block455that is full or nearly full, in order to avoid and/or prevent the processor from stalling, and accordingly to improve processor latency.

In one or more embodiments, as shown inFIG.5, the Instruction Dispatch Unit (IDU)220receives decoded instructions from the Instruction Decode Unit210. At pre-dispatch stage0(524) the decision where to assign and/or route instructions is made. That is, the decision is made at per-dispatch0(524) as to which processing pipe and/or Issue Unit235(e.g., Issue Queue (ISQ)536) should receive the instruction for processing. The decision as to which processing pipe and/or Issue Unit235(e.g., Issue Queue (ISQ536) to issue the instructions can be based upon many factors, including the type of instruction, the execution units in various pipelines, and which queues, which register banks or blocks455of the register file250, and other resources, have available space. Next, at pre-dispatch stage1(526) the decision is made as to which register bank or block455of the register file250will receive the results after the instruction is executed in an execution unit240. That is, at the pre-dispatch stage1(526) the decision is made as to which register bank or block455to write the result of the executed instruction. The destination register bank or block455to write the result will be communicated to the Issue Queue236and Mapper265. In an embodiment, the Pre-Dispatch0(524) and Pre-Dispatch1(526) stages occur in the Instruction Dispatch Unit220. Most dispatch decisions typically are made in Pre-Dispatch0(524) and pre-Dispatch1(526) stages.

Next during the Map stage555, the specific register entry452in the register block455to receive the result of the instruction is allocated (e.g., selected) by the Mapper265. That is, the instruction's destination register entry452(the address of the rename register) is allocated by the Mapper265at Map stage555. The address is allocated at Map stage555as the address of the selected register entry452is written into the issue queue as the instruction's result destination in the next stage. It is noted that any following instructions that source that destination register entry452will also receive that address from the Mapper265. The instruction is dispatched to the Issue Unit235and during the next stage (referred to as the ISR stage) written into the Issue Queue (ISQ)536in the Issue Unit235. The instruction might reside in the Issue Queue536for a while. When data and resources (e.g., register file resources) are available (which can take more than one cycle), then the instruction is issued to the Execution Unit240. The instruction can issue from the Issue Queue536to the Execution Unit240out of order with respect to the program.

The instruction is issued from the Issue Queue536to the Execution Unit240when the source registers are available (the source register entry452contains the required data), and the Execution Unit240is available, among other considerations. The Execution Unit240executes the instruction and returns (e.g., writes) the result to the identified destination (rename) register entry452. Since in embodiments, a certain bank455of the register file250can be written to only by a particular execution unit (e.g., not all execution units can write to all banks455of the register file250), if the register file entry452identified in the certain block455of register file250as the destination for the result of the execution unit is unavailable, the processor might stall as it waits for that entry452in the register block455to become available. Disclosed are embodiments to detect that an imbalance in register file block usage is occurring and steering (e.g., assigning and/or routing) one or more operations, e.g., unrestricted operations, to register file blocks455that have available register entries452, to avoid the processor from stalling because of unavailable destination resources (e.g., an unavailable register file entry452).

FIG.6is an exemplary overview flowchart in accordance with an embodiment illustrating and describing a method600of routing instructions in a processor. While the method600is described for the sake of convenience and not with an intent of limiting the disclosure as comprising a series and/or a number of steps, it is to be understood that the process600does not need to be performed as a series of steps and/or the steps do not need to be performed in the order shown and described with respect toFIG.6, but the process600may be integrated and/or one or more steps may be performed together, simultaneously, or the steps may be performed in the order disclosed or in an alternate order.

The method600inFIG.6relates to routing instructions in a processor preferably with multiple execution pipelines and/or execution units. At605, one or more instructions are received by the instruction dispatch unit for processing. It can be appreciated that the instructions can be received as a group of instructions or as one instruction at a time, but in an example embodiment up to eight instructions are received at a time as a group by the instruction dispatch unit220. The one or more instructions received by the dispatch unit is referred to as the first decode group of instruction. At610it is determined whether the one or more instructions can be routed without exceeding any resource. For example, issue queues and register banks can be checked to determine whether any resource will be exceeded. If at610processor pipeline resources will not be exceeded (610: Yes), then at615the instruction types are equally distributed among the issue units (e.g., Issue Queues536).

For example, at615when the instructions can be routed without exceeding resources the routing logic can attempt to balance different instruction classes among the issue queues so that the issue queues remain approximately equally utilized. Some instruction types have longer latency than others, for example floating point instructions have a relatively long latency, so in an embodiment routing logic attempts to spread floating point instructions equally among the one or more issue queues. Similarly loads and stores are ideally equally spread among the one or more issue queues. At615dispatch routing logic assigns the one or more instructions, in the example embodiment the eight instructions, from the decode unit210to the issue queues (e.g., Issue Queues536). In an embodiment, the dispatch decision as to what issue queue to assign and route the instruction is made at the pre-dispatch stage0(524). According to an approach, the routing decision does not take into account rebalancing the (rename) register banks, and only checks that a (rename) register bank will be available (e.g., register bank will not be overrun). That is, in an approach, at this stage of processing the instruction(s) (e.g., at pre-dispatch0(524) stage), routing logic in the dispatch unit at pre-dispatch stage0(524) makes its decision as to the issue queue (ISQ) to assign the instruction without regard to balancing the rename register banks. In an embodiment, the decision and/or selection of the rename block455is made at pre-dispatch1(526) stage, and the actual register (rename) address (e.g., register entry452) in the register (rename) block455is assigned/selected during the Map cycle555(by Mapper265).

If at610it is determined that the instructions cannot be routed without exceeding the resources (610: No), then the process600continues to620where in an embodiment the one or more instruction(s) are held, and in an approach, the resources are checked again. The process600after620continues to625where an attempt is made to route one instruction looking at the resources at for example the issue queues (e.g., Issue Queues536) and destination register blocks455. If the instruction can be processed, e.g., there are available resources, the instruction is processed and routed. Process600continues after625to630where it is determined whether all the one or more instructions, e.g., all eight of the instructions, in the first decode group of instruction are routed. If at630it is determined that all the one or more instructions, e.g., all eight of the instructions, in the decode group have not been routed (630: No) then process600goes back to620where the resources are checked again, and to625where an attempt is made to route one of the one or more instructions remaining in the first decode group by looking at the resources of the processor including the issues queues and destination register blocks, e.g., the availability of an issue queue and a destination register block for processing the instruction. If resources are available to process another instruction in the first decode group, that instruction is processed, and this process of going back to620and625to process the one or more instructions from the first decode group is continued until at630it is determined that all the instructions in the first decode group have been routed (630: Yes), and then the process600goes back to605where one or more instructions (e.g., a second decode group of instructions) are received by the dispatch unit220from the decode unit210and the routing process600starts again at610.

FIG.7is an exemplary overview flowchart in accordance with an embodiment illustrating and describing a method700of assigning and/or routing instructions to various functional units and/or destination register file blocks in a processor, and, in an embodiment, re-assigning instructions to be processed in a manner where the results are written to a different destination (rename) register block to potentially improve processor latency. While the method700is described for the sake of convenience and not with an intent of limiting the disclosure as comprising a series and/or a number of steps, it is to be understood that the process700does not need to be performed as a series of steps and/or the steps do not need to be performed in the order shown and described with respect toFIG.7, but the process700may be integrated and/or one or more steps may be performed together, simultaneously, or the steps may be performed in the order disclosed or in an alternate order.

In process700, during processing of an instruction, for example at the dispatch unit, a register block usage count and/or rate is determined at705for one or more register blocks, and in an approach for each of the register blocks. For example, in an embodiment the register block usage count and/or rate is determined for one or more (e.g., selected) register blocks455(e.g., for a register block455associated with and/or assigned to an instruction) and/or each register block455in the register file250. That is, in705the number of entries in a particular register bank, and in an embodiment the number of entries in each register bank, that are available for use or that are being used is determined and/or calculated.

The register block usage count and/or rate can be determined in one or more manners. In an approach the number of register entries452in each register block455in the register file250that are valid and being used are counted from for example, the valid field453in the register file250, and that information (number of register files452per register block455being used) can be used to calculate a usage count and/or rate for a particular register block and/or for each register block in the register file. In an approach, that information (e.g., the number of register entries in a register block and/or the register entry count in each register bank) is sent to the dispatch unit220, directly or indirectly, and stored in counter425in the Dispatch Unit220. In one or more approaches, the Mapper265can maintain for each register block455an available pool (AP)467of register entries452that are ready to allocate and the number or count of register entries452(and in an aspect the identity of the register entries452) available for allocation by the Mapper265(or vice versa the number of register files425per register block455being used) per register block455is sent to the Dispatch Unit220, and the number of register entries452in each register bank455that can be allocated (or vice versa the number of entries452in each register block455that are being used) can be stored in the counter425in the Dispatch Unit220. The Mapper265can receive information from the register file250on the register file entries452that are in usage (or vice versa the register file entries452that are not in use and can be allocated) from the register file250. In other approaches, the Dispatch Unit220can have one or more bank counters425that maintains a running count of the number of register file entries452in each register block455that are available for use by decrementing the count in respective counter425when Dispatch Unit220sends an instruction associated with and/or assigned to a register block455to the Mapper265and/or the Issue Queue536, and increment the count in the respective counter425when the Mapper265retires an instruction. Other means of determining the register block usage count/rate (or available count/rate) are contemplated.

At710it is determined whether a specific (e.g., assigned) register block, or one or more register blocks, including for example each register bank, is being overutilized. In one or more embodiments, the register block usage count and/or rate is used to determine whether a particular register bank is being overutilized. In an embodiment, it is determined at710whether a register block associated with an instruction is overutilized. In an aspect, at710the utilization rate or an availability rate of a register block is determined, where a utilization rate in an aspect provides information on how many register entries in a register block are being used and an availability rate is related to utilization or usage rate as it provides information on how many register files in a register block are available for use (e.g., not being used). The usage rate and availability rate measure how full a register bank is and can be used to determine whether a register bank is being overutilized. In a further embodiment, at710the utilization or availability rate is determined for each of the register blocks455in a register file250. In an embodiment, at710it is determined whether the register block455to be assigned to, or that was initially assigned to, an instruction is overutilized.

Determining whether a register block455is overutilized at710can be accomplished in a number of manners or ways. In an approach, the register block usage (utilization) count/rate can be compared to a threshold. In an alternative approach the register block availability rate, which is also a measure of the register block usage rate, can be compared to a threshold. In one or more embodiments, determining whether a register block is overutilized includes comparing the count of used (or available) register entries in a register block (the usage rate of the register blocks) in the register file to the threshold. The threshold can be fixed, predetermined, predefined, preset, adjustable, and/or programmable and will depend upon the design characteristics desired of the processor. For example, in a scenario where the usage rate of a register block455is 80% indicating that 80% (eight out of ten) of the register entries452in a register bank455are being used, and the threshold for determining overutilization of the destination register bank455is set at 75%, the register bank associated with the instruction is overutilized as its utilization rate is over the threshold. It can be appreciated by a person of skill in the art that availability counts/rates could be used instead of usage (utilization) counts/rates, as well as determining underutilization of register blocks instead of overutilization of register blocks, and that different threshold values would be selected depending upon the criteria and parameters used to determine register bank usage/availability. Accordingly, in the example above, the availability rate of the register block455is 20% as2out of ten register file entries in the register block are available for use, and the threshold for determining underutilization is 25%, and since the availability of 20% is less than 25% and not greater than 25%, the register block is not underutilized.

If at710a register block is not being overutilized, e.g., is being underutilized (710: No), then the process700continues to715where the register block associated with (e.g., initially assigned) the instruction is retained. For example, if the register block has been assigned to an instruction, and that register block is being underutilized or at least not over utilized (710: No), then the process continues to715where those assignments and/or routing decisions are not disturbed and the process retains the register bank assignment for that instruction. In another example, where an instruction through routing logic, in for example the dispatch unit, desires to select and/or assign a particular destination register block for the result of the instruction to be written, for example because the processor desires to use a preferred execution unit to process the instruction which writes its result to a particular register block, and the processor determines that the particular register block to be associated with and assigned to that instruction is underutilized, or at least not overutilized (710: No), then the preferred assignment of a destination register block for that instruction can be retained.

If the register block associated with an instruction is overutilized (710: Yes), then the process700continues to720where the register bank assignment logic reassigns the destination assignment to a register block that is not overutilized and/or at least less utilized than the register block associated with the instruction. That is, in an embodiment at710where an instruction is initially associated with and/or assigned to a destination register block that is overutilized (710: Yes), then the processor, Dispatch Unit, and/or system at720attempts to reassign the register bank of the instruction destination so that it writes its result to a different destination register block, for example a register block that is underutilized and/or at least less utilized than the associated register block. For example, if an instruction associated with a register block has a register block usage rate more than the threshold indicating overutilization of the register block (710: Yes), than at720the assignment and routing of the instruction can be changed so the result is written to a different destination register block. In other words, the register block assignment for that instruction is changed. It can be appreciated that the register block assignment in one or more embodiments will be unable to be changed for example in those situations where the instruction is restricted to writing to a particular register block, for example, where the instruction is restricted to a specific execution unit that only writes to a specific register block.

It can be appreciated that the adjustment of the destination register blocks to which the results of an instruction are written can be implemented in various embodiments. For example,FIG.8is an exemplary overview flowchart in accordance with an embodiment illustrating and describing a method800of assigning the register block destination of an instruction in a processor, and, in an embodiment, reassigning (rename) register blocks to instructions to be processed in a manner where the results are written to a different destination (rename) register block to potentially improve processor latency. While the method800is described for the sake of convenience and not with an intent of limiting the disclosure as comprising a series and/or a number of steps, it is to be understood that the process800does not need to be performed as a series of steps and/or the steps do not need to be performed in the order shown and described with respect toFIG.8, but the process800may be integrated and/or one or more steps may be performed together, simultaneously, or the steps may be performed in the order disclosed or in an alternate order.

At805the register block availability count and/or rate for each register block in the register file is determined, and at810it is determined and/or calculated whether the register entries available in each register block are under a threshold. For each register block where the available number of register entries are not below (e.g., are equal to or above) the threshold (810: No), indicating, for example, that the destination register block is not over-utilized, then the process continues to815where the destination register block assignment is retained and/or permitted. In other words, instructions that are assigned during normal dispatch logic to a preferred destination register block, that preferred destination register block assignment is permitted, used, and/or retained. For each destination register block where the available number of register entries are below the threshold (810: Yes), indicating, for example, that the destination register block is being over-utilized, then the process continues to820where the register block assignment is steered away from the register block that is under the threshold. In other words, instructions that can be assigned to one or more destination register block(s), are assigned to the destination register blocks that are not under the threshold and destination register blocks under the threshold are avoided.

In an example embodiment, in the pre-dispatch stage0(524) when the issue unit235(and Issue Queue (ISQ)536) is being selected and/or assigned, the availability of the destination register block as determined in process800can be used in selecting and assigning the Issue Unit235and/or Issue Queue (ISQ)536. For example, dispatch logic can have a preferred ISQ and execution unit to execute an instruction, which will write the results to a preferred destination register block, and if the number of available register entries in the preferred destination register block is under the threshold, then the instruction can be assigned and routed to an issue unit (e.g., an Issue Queue) that feeds (e.g., writes to) a different destination register block (other than the preferred destination register block), and if the number of available entries in the register block is over the threshold, then the instruction can be assigned and routed to the issue unit (e.g., an Issue Queue) that feeds (e.g., writes to) the selected and/or preferred destination register block. Alternatively, during the pre-dispatch stage0(524) the fullness of the destination register blocks are not taken into consideration when making the ISQ assignment decision, and during pre-dispatch stage1(526) when the destination register bank is being selected and/or assigned, the availability of a destination register block as determined in process800can be used in selecting and/or assigning the destination register bank for that instruction. In other words, if the number of available register entries in a preferred destination register block is over (e.g., not under) the threshold, then the preferred destination register block can be selected and assigned as the destination register block and the instruction results will be routed to that preferred destination register block, and if the number of register entries available in the preferred destination register block is under the threshold, then the destination register block for the instruction will be steered away from that preferred destination register block which is over the threshold (e.g., assigned and routed to a different destination register block). That is, in an embodiment, the destination register block fullness is not taken into consideration when selecting the Issue Unit and/or Issue Queue (ISQ) during pre-dispatch stage0, but the fullness of the destination register block is taken into consideration during pre-dispatch stage1to balance the rename register blocks afterward.

FIG.9is an exemplary overview flowchart in accordance with another embodiment illustrating and describing a method900of assigning (and/or reassigning) destination (rename) register blocks to instructions in a processor, and, in an embodiment, reassigning the destination (rename) register block to the instruction to be processed in a manner where the results are written to a different destination (rename) register block to potentially improve processor latency. While the method900is described for the sake of convenience and not with an intent of limiting the disclosure as comprising a series and/or a number of steps, it is to be understood that the process900does not need to be performed as a series of steps and/or the steps do not need to be performed in the order shown and described with respect toFIG.9, but the process900may be integrated and/or one or more steps may be performed together, simultaneously, or the steps may be performed in the order disclosed or in an alternate order.

In process900, the register block associated and initially assigned to an instruction is checked later in the routing decision process, and if a register bank is going to be overrun (e.g., is overutilized), then register blocks will be swapped. In one or more embodiments, the register block assignments are left intact or can be swapped according to a table of assignments. At905in process900, the register block usage count is determined. The register block usage count can be determined in a number of different ways, including, but not limited to, the several embodiments discussed in connection with705in process700, and/or the embodiments discussed in connection with805in process800.

At910it is determined whether the destination register block associated with an instruction is over utilized. That is, in an embodiment the instruction has already been associated with (e.g., assigned to) a destination register block through normal processing, and at910it is determined whether the destination register block initially associated with and/or assigned to the instruction is overutilized. Determining whether a destination register block associated with and/or assigned to an instruction is over utilized can be determined and/or calculated in a number of different ways, including the embodiments discussed in connection with710in process700, and/or the embodiments discussed in connection with810in process800. As other examples, over-utilization can be defined according to whether the number of available or used entries in a register block is over or under a threshold. In other embodiments, over-utilization can be determined by determining whether there is any room (any available entry) in a destination (rename) register block. In other words, in an example, a destination (rename) register block is determined to be over-utilized if there are not any available entries in the destination (rename) register block, and more specifically is determined to be over-utilized only if there is not one available entry in the destination (rename) register block.

One of skill in the art can appreciate that the number of register entries available for use or that are being used in a register block can both be used to measure the utilization or “fullness” of a register block. In the present disclosure various counters and means to determine the usage or availability of a register block have been disclosed, from which the utilization of the register block can be calculated as the number of entries in a register block is generally known or determinable. The information on the count of the register entries per register block is maintained in one or more embodiments in count pool425in the Dispatch Unit220. In process900, the calculation of the utilization count and/or rate of the register blocks can be performed in the dispatch stage of processing the instruction, and in an embodiment is preferably calculated/determined at the pre-dispatch (cycle) stage0(524).

If at910it is determined that the destination register block associated with (e.g., initial assigned to) the instruction is overutilized (910: Yes), then at915the destination register block assignments are changed, and in an embodiment are swapped according to a table. For example, each instruction type can be correlated to particular destination register block as per a default (preferred) table of assignments, and each instruction type can also be correlated to a different particular destination register block as per a swapped table of assignments. For example, a swappable load instruction can be assigned to block0in default table I and can be assigned to block2in swap table II. It will be appreciated that not all instruction types may be capable of being swapped to a different register block so such an instruction type will be assigned to the same register block in both tables. In the process900, if a destination register block assigned to an instruction is overutilized (910: Yes), then at915the destination register block to which the instruction is assigned is swapped according to the instruction type as provided by swap table II. After915, the process continues to925where the instructions are sent to the Mapper and Issue Unit (e.g., Issue Queue) with the register block assignment as per swap table II. The swapping and/or reassignment of the destination register block preferably takes place at the pre-dispatch stage1(526).

If at910it is determined that the register block associated with (e.g., initial assigned to) the instruction is not overutilized (910: No), then at920the register block assignments remain (e.g., the default/preferred register block assignment table I is used) and the process continues to925where the instructions are sent to the Mapper/Issue Unit with the register block assignment as per default table I.

In an embodiment, once you start swapping which destination register block (which write port for the register file to use) to use for an instruction type (e.g., a load instruction), it is preferred to swap all the destination register blocks to use for that instruction type. Changing and/or swapping the register blocks can potentially avoid writeback collisions. In an approach, once the utilization rate drops below the threshold, destination register block assignments for all the instructions in the dispatch group are swapped until the utilization rate climbs above the threshold. In a preferred embodiment, this threshold check is made every cycle, so all instructions dispatched together in the same cycle will initially either be all swapped or all not swapped.

While the illustrative embodiments described above are preferably implemented in hardware, such as in units and circuitry of a processor, various aspects of the illustrative embodiments may be implemented in software as well. For example, it will be understood that each block of the flowchart illustrated inFIGS.6-9, and combinations of blocks in the flowchart illustration, can be implemented by computer program instructions. These computer program instructions may be provided to a processor or other programmable data processing apparatus to produce a machine, such that the instructions that execute on the processor or other programmable data processing apparatus create means for implementing the functions specified in the flowchart block or blocks. These computer program instructions may also be stored in a computer-readable memory or storage medium that can direct a processor or other programmable data processing apparatus to function in a particular manner, such that the instructions stored in the computer-readable memory or storage medium produce an article of manufacture including instruction means which implement the functions specified in the flowchart block or blocks.

Accordingly, blocks of the flowchart illustrations inFIGS.6-9support combinations of means for performing the specified functions, combinations of steps for performing the specified functions and program instruction means for performing the specified functions. It will also be understood that each block of the flowchart illustration, and combinations of blocks in the flowchart illustrations, can be implemented by special purpose hardware-based computer systems that perform the specified functions or steps, or by combinations of special purpose hardware and computer instructions.

The present invention may be a system, a method, and/or a computer program product at any possible technical detail level of integration. The computer program product may include a computer readable storage medium (or media) having computer readable program instructions thereon for causing a processor to carry out aspects of the present invention.

The computer readable storage medium can be a tangible device that can retain and store instructions for use by an instruction execution device. The computer readable storage medium may be, for example, but is not limited to, an electronic storage device, a magnetic storage device, an optical storage device, an electromagnetic storage device, a semiconductor storage device, or any suitable combination of the foregoing. A non-exhaustive list of more specific examples of the computer readable storage medium includes the following: a portable computer diskette, a hard disk, a random access memory (RAM), a read-only memory (ROM), an erasable programmable read-only memory (EPROM or Flash memory), a static random access memory (SRAM), a portable compact disc read-only memory (CD-ROM), a digital versatile disk (DVD), a memory stick, a floppy disk, a mechanically encoded device such as punch-cards or raised structures in a groove having instructions recorded thereon, and any suitable combination of the foregoing. A computer readable storage medium, as used herein, is not to be construed as being transitory signals per se, such as radio waves or other freely propagating electromagnetic waves, electromagnetic waves propagating through a waveguide or other transmission media (e.g., light pulses passing through a fiber-optic cable), or electrical signals transmitted through a wire.

Computer readable program instructions described herein can be downloaded to respective computing/processing devices from a computer readable storage medium or to an external computer or external storage device via a network, for example, the Internet, a local area network, a wide area network and/or a wireless network. The network may comprise copper transmission cables, optical transmission fibers, wireless transmission, routers, firewalls, switches, gateway computers and/or edge servers. A network adapter card or network interface in each computing/processing device receives computer readable program instructions from the network and forwards the computer readable program instructions for storage in a computer readable storage medium within the respective computing/processing device.

Computer readable program instructions for carrying out operations of the present invention may be assembler instructions, instruction-set-architecture (ISA) instructions, machine instructions, machine dependent instructions, microcode, firmware instructions, state-setting data, configuration data for integrated circuitry, or either source code or object code written in any combination of one or more programming languages, including an object oriented programming language such as Smalltalk, C++, or the like, and procedural programming languages, such as the “C” programming language or similar programming languages. The computer readable program instructions may execute entirely on the user's computer, partly on the user's computer, as a stand-alone software package, partly on the user's computer and partly on a remote computer or entirely on the remote computer or server. In the latter scenario, the remote computer may be connected to the user's computer through any type of network, including a local area network (LAN) or a wide area network (WAN), or the connection may be made to an external computer (for example, through the Internet using an Internet Service Provider). In some embodiments, electronic circuitry including, for example, programmable logic circuitry, field-programmable gate arrays (FPGA), or programmable logic arrays (PLA) may execute the computer readable program instructions by utilizing state information of the computer readable program instructions to personalize the electronic circuitry, in order to perform aspects of the present invention.

Aspects of the present invention are described herein with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems), and computer program products according to embodiments of the invention. It will be understood that each block of the flowchart illustrations and/or block diagrams, and combinations of blocks in the flowchart illustrations and/or block diagrams, can be implemented by computer readable program instructions.

These computer readable program instructions may be provided to a processor of a general purpose computer, special purpose computer, or other programmable data processing apparatus to produce a machine, such that the instructions, which execute via the processor of the computer or other programmable data processing apparatus, create means for implementing the functions/acts specified in the flowchart and/or block diagram block or blocks. These computer readable program instructions may also be stored in a computer readable storage medium that can direct a computer, a programmable data processing apparatus, and/or other devices to function in a particular manner, such that the computer readable storage medium having instructions stored therein comprises an article of manufacture including instructions which implement aspects of the function/act specified in the flowchart and/or block diagram block or blocks.

The computer readable program instructions may also be loaded onto a computer, other programmable data processing apparatus, or other device to cause a series of operational steps to be performed on the computer, other programmable apparatus or other device to produce a computer implemented process, such that the instructions which execute on the computer, other programmable apparatus, or other device implement the functions/acts specified in the flowchart and/or block diagram block or blocks.

The flowchart and block diagrams in the Figures illustrate the architecture, functionality, and operation of possible implementations of systems, methods, and computer program products according to various embodiments of the present invention. In this regard, each block in the flowchart or block diagrams may represent a module, segment, or portion of instructions, which comprises one or more executable instructions for implementing the specified logical function(s). In some alternative implementations, the functions noted in the blocks may occur out of the order noted in the Figures. For example, two blocks shown in succession may, in fact, be executed substantially concurrently, or the blocks may sometimes be executed in the reverse order, depending upon the functionality involved. It will also be noted that each block of the block diagrams and/or flowchart illustration, and combinations of blocks in the block diagrams and/or flowchart illustration, can be implemented by special purpose hardware-based systems that perform the specified functions or acts or carry out combinations of special purpose hardware and computer instructions.

Moreover, a system according to various embodiments may include a processor and logic integrated with and/or executable by the processor, the logic being configured to perform one or more of the process steps recited herein. By integrated with, what is meant is that the processor has logic embedded therewith as hardware logic, such as an application specific integrated circuit (ASIC), a field programmable gate array (FPGA), etc. By executable by the processor, what is meant is that the logic is hardware logic; software logic such as firmware, part of an operating system, part of an application program; etc., or some combination of hardware and software logic that is accessible by the processor and configured to cause the processor to perform some functionality upon execution by the processor. Software logic may be stored on local and/or remote memory of any memory type, as known in the art. Any processor known in the art may be used, such as a software processor module and/or a hardware processor such as an ASIC, a FPGA, a central processing unit (CPU), an integrated circuit (IC), a graphics processing unit (GPU), etc.

It will be clear that the various features of the foregoing systems and/or methodologies may be combined in any way, creating a plurality of combinations from the descriptions presented above.

It will be further appreciated that embodiments of the present invention may be provided in the form of a service deployed on behalf of a customer to offer service on demand.

The descriptions of the various embodiments of the present invention have been presented for purposes of illustration, but are not intended to be exhaustive or limited to the embodiments disclosed. Many modifications and variations will be apparent to those of ordinary skill in the art without departing from the scope and spirit of the described embodiments. The terminology used herein was chosen to best explain the principles of the embodiments, the practical application or technical improvement over technologies found in the marketplace, or to enable others of ordinary skill in the art to understand the embodiments disclosed herein.