Method of Executing Coded Instructions in a Multiprocessor Having Shared Execution Resources Including Active, Nap, and Sleep States in Accordance With Cache Miss Latency

1. Field of the Invention

The present invention relates in general to microprocessors and, more particularly, to a system, method, and processor architecture for dynamically reconfiguring a processor between uniprocessor and selected multiprocessor configurations.

2. Relevant Background

Early computer processors (also called microprocessors) included a central processing unit or instruction execution unit that executed only one instruction at a time. As used herein the term processor includes complete instruction set computers (CISC), educed instruction set computers (RISC) and hybrids. The processor executes programs having instructions stored in main memory by fetching their instruction, decoding them, and executing them one after the other. In response to the need for improved performance several techniques have been used to extend the capabilities of these early processors including pipelining, superpipelining, superscaling, speculative instruction execution, and out-of-order instruction execution.

Pipelined architectures break the execution of instructions into a number of stages where each stage corresponds to one step in the execution of the instruction. Pipelined designs increase the rate at which instructions can be executed by allowing a new instruction to begin execution before a previous instruction is finished executing. Pipelined architectures have been extended to "superpipelined" or "extended pipeline" architectures where each execution pipeline is broken down into even smaller stages (i.e., microinstruction granularity is increased). Superpipelining increases the number of instructions that can be executed in the pipeline at any given time.

"Superscalar" processors generally refer to a class of microprocessor architectures that include multiple pipelines that process instructions in parallel. Superscalar processors typically execute more than one instruction per clock cycle, on average. Superscalar processors allow parallel instruction execution in two or more instruction execution pipelines. The number of instructions that may be processed is increased due to parallel execution. Each of the execution pipelines may have differing number of stages. Some of the pipelines may be optimized for specialized functions such as integer operations or floating point operations, and in some cases execution pipelines are optimized for processing graphic, multimedia, or complex math instructions.

The goal of superscalar and superpipeline processors, is to execute multiple instructions per cycle (IPC). Instruction-level parallelism (ILP) available in programs written to operate on the processor can be exploited to realize this goal. However, many programs are not coded in a manner that can take full advantage of deep, wide instruction execution pipelines in modern processors. Many factors such as low cache hit percentage, instruction interdependency, frequent access to slow peripherals, and the like cause the resources of a superscalar processor to be used inefficiently.

Superscalar architectures require that instructions be dispatched for execution at a sufficient rate. Conditional branching instructions create a problem for instruction fetching because the instruction fetch unit (IFU) cannot know with certainty which instructions to fetch until the conditional branch instruction is resolved. Also, when a branch is detected, the target address of the instructions following the branch must be predicted to supply those instructions for execution.

Recent processor architectures use a branch prediction unit to predict the outcome of branch instructions allowing the fetch unit to fetch subsequent instructions according to the predicted outcome. These instructions are "speculatively executed" to allow the processor to make forward progress during the time the branch instruction is resolved.

Another solution to increased processing power is provided by multiprocessing. Multiprocessing is a hardware and operating system feature that allows multiple processors to work together to share workload within a computing system. In a shared memory multiprocessing system, all processors have access to the same physical memory. One limitation of multiprocessing is that programs that have not been optimized to run as multiple process may not realize significant performance gain from multiple processors. However, improved performance is achieved where the operating system is able to run multiple programs concurrently, each running on a separate processor.

Multithreaded software is a recent development that allows applications to be split into multiple independent threads such that each thread can be assigned to a separate processor and executed independently parallel as if it were a separate program. The results of these separate threads are reassembled to produce a final result. By implementing each thread on a separate processor, multiple tasks are handled in a fast, efficient manner. The use of multiple processors allows various tasks or functions to be handled by other than a single CPU so that the computer power of the overall system is enhanced. However, because conventional multiprocessors are implemented using a plurality of discrete integrated circuits, communication between the devices limits system clock frequency and the ability to share resources amongst the plurality of processors. As a result, conventional multiprocessor architectures result in duplication of resources which increases cost and complexity.

Given the wide variety and mix of software used on general purpose processors, it often occurs that some programs run most efficiently on superscalar, superpipeline uniprocessors while other programs run most efficiently in a multiprocessor environment. Moreover, the more efficient architecture may change over time depending on the mix of programs running at any given time. Because the architecture was defined by the CPU manufacturer and system board producer, end users and programmers had little or no ability to configure the architecture to most efficiently use the hardware resources to accomplish a given set of tasks.

Briefly stated, the present invention involves a method of executing coded instructions in a dynamically configurable multiprocessor having shared execution resources including steps of placing a first processor in an active state upon booting of the multiprocessor. In response to a processor create command, a second processor is placed in an active state. When either the first or second processor encounter a cache miss that has to be serviced by off-chip cache the processor requiring service is placed in nap state in which instruction fetching for that processor is disabled. When either the first or second processor encounter a cache miss that has to be serviced by main memory, the processor requiring services I placed in a sleep state by flushing all instructions from the processor in the sleep state and disabling instruction fetching for the processor in the sleep state.

A processor in accordance with the present invention includes a processor creation unit responsive to a processor create command to output signals indicating a current processor configuration and plurality of virtual or logical processors each virtual processor having a first set of execution resources that are uniquely identified with the virtual processor and a second set of execution resources that are shared amongst the plurality of virtual processors. A plurality of state machines responsive to the processor creation unit are provided, each corresponding to a selected one of the plurality of virtual processors. The state machines maintain processor status information representative of whether the processor is available to receive and execute instructions. The processor further includes status logic analyzing expected latency of instructions on each processor and updating the state machine corresponding to any processor having an instruction with an expected latency greater than a preselected threshold.

The foregoing and other features, utilities and advantages of the invention will be apparent from the following more particular description of a preferred embodiment of the invention as illustrated in the accompanying drawings.

FIG. 1 shows in block diagram form a computer system incorporating an apparatus and system in accordance with the present invention;

FIG. 2 shows a processor in block diagram form incorporating the apparatus and method in accordance with the present invention;

FIG. 3 illustrates a processor create unit in accordance with the present invention;

FIG. 4 shows a portion of the processor create unit of FIG. 3 in greater detail;

FIG. 5 shows an instruction fetch unit in accordance with the present invention in block diagram form;

FIG. 6 illustrates an example format for a branch repair table used in the fetch unit of FIG. 3;

FIG. 7 illustrates an example instruction bundle in accordance with an embodiment of the present invention;

FIG. 8 shows in block diagram form an instruction scheduling unit shown in FIG. 2;

FIG. 9 shows an exemplary entry in an instruction scheduling window in accordance with the present invention;

FIG. 10 shows an exemplary instruction wait buffer used in conjunction with the instruction scheduling window shown in FIG. 9; and

FIG. 11 shows in block diagram form instruction execution units in accordance with an embodiment of the present invention.

FIG. 12 shows in block diagram form a data cache (D$), data cache tag (D$TAG), and data cache translation lookaside buffer (D$TLB) connected to an L2 cache (L2$).

The present invention recognizes the wide variation in software (i.e., computer instruction code) that must be accommodated by a general purpose processor. Some code is most efficiently executed on a single high-speed processor with multiple deep pipelines. However, some applications cannot take advantage of these processor architectures.

Also, older software that was written before superscalar processors were common may not be optimized to take advantage of the benefits of multiple pipeline execution. Further, many applications now use multithreading software techniques that are best implemented on a multiprocessor platform rather than a single processor platform. The method, processor, and computer system in accordance with the present invention allows the processor hardware to be dynamically configured to meet the needs of a particular software application.

In such a dynamically configurable multiprocessor, however, many execution resources may be shared among the multiple virtual or logical processors on a single integrated circuit chip. Fairness issues may arise between the processes if, for example, one process misses in the cache more frequently than the others. In this case, the process that misses in the cache occupies space in the shared resources without doing any useful work while the cache miss is serviced by higher cache levels or main memory. The present invention recognizes this fairness issue with a solution for allocating resources fairly amongst the active processes.

Computer systems and processor architectures can be represented as a collection of interacting functional units as shown in FIG. 1 and FIG. 2. These functional units, discussed in greater detail below, perform the functions of storing instruction code, fetching instructions and data from memory, preprocessing fetched instructions, scheduling instructions to be executed, executing the instructions, managing memory transactions, and interfacing with external circuitry and devices.

The present invention is described in terms of apparatus and methods particularly useful in a superpipelined and superscalar processor 102 shown in block diagram form in FIG. 1 and FIG. 2. The particular examples represent implementations useful in high clock frequency operation and processors that issue and executing multiple instructions per cycle (IPC). However, it is expressly understood that the inventive features of the present invention may be usefully embodied in a number of alternative processor architectures that will benefit from the performance features of the present invention. Accordingly, these alternative embodiments are equivalent to the particular embodiments shown and described herein.

FIG. 1 shows a typical general purpose computer system 100 incorporating a processor 102 in accordance with the present invention. Computer system 100 in accordance with the present invention comprises an address/data bus 101 for communicating information, processor 102 coupled with bus 101 through input/output (I/O) device 103 for processing data and executing instructions, and memory system 104 coupled with bus 101 for storing information and instructions for processor 102. Memory system 104 comprises, for example, cache memory 105 and main memory 107. Cache memory 105 includes one or more levels of cache memory. In a typical embodiment, processor 102, I/O device 103, and some or all of cache memory 105 may be integrated in a single integrated circuit, although the specific components and integration density are a matter of design choice selected to meet the needs of a particular application.

User I/O devices 106 are coupled to bus 101 and are operative to communicate information in appropriately structured form to and from the other parts of computer 100. User I/O devices may include a keyboard, mouse, card reader, magnetic or paper tape, magnetic disk, optical disk, or other available input devices, include another computer. Mass storage device 117 is coupled to bus 101 and is implemented using one or more magnetic hard disks, magnetic tapes, CDROMs, large banks of random access memory, or the like. A wide variety of random access and read only memory technologies are available and are equivalent for purposes of the present invention. Mass storage 117 may include computer programs and data stored therein. Some or all of mass storage 117 may be configured to be incorporated as a part of memory system 104.

In a typical computer system 100, processor 102, I/O device 103, memory system 104, and mass storage device 117, are coupled to bus 101 formed on a printed circuit board and integrated into a single housing as suggested by the dashed-line box 108. However, the particular components chosen to be integrated into a single housing is based upon market and design choices. Accordingly, it is expressly understood that fewer or more devices may be incorporated within the housing suggested by dashed line 108.

Display device 109 is used to display messages, data, a graphical or command line user interface, or other communications with the user. Display device 109 may be implemented, for example, by a cathode ray tube (CRT) monitor, liquid crystal display (LCD) or any available equivalent.

FIG. 2 illustrates principle components of processor 102 in greater detail in block diagram form. It is contemplated that processor 102 may be implemented with more or fewer functional units and still benefit from the apparatus and methods of the present invention unless expressly specified herein. Also, functional units are identified using a precise nomenclature for ease of description and understanding, but other nomenclature often is often used by various manufacturers to identify equivalent functional units.

Unlike conventional multiprocessor architectures, the present invention may be, and desirably is, implemented as a single circuit on a single integrated circuit chip. In this manner, the individual processors are not only closely coupled, but are in essence merged such that they can share resources efficiently amongst the processors. This resources sharing simplifies many of the communication overhead problems inherent in other multiprocessor designs. For example, memory, including all levels of the cache subsystem, are easily shared among the processor and so cache coherency is not an issue. Although the resources are shared, the multiprocessor configuration in accordance with the present invention achieves the same advantages as conventional multiprocessing architectures by enabling independent threads and processes to execute independently and in parallel.

In accordance with the present invention, processor create unit 200 is coupled to receive a processor create instruction from either the computer operating system, a running application, or through a hardware control line (not shown). In a specific example, the processor create instruction is added to the SPARC V9 instruction architecture as a privileged command that can be issued only by the operating system. The processor create instruction instructs processor 102 to reconfigure as either a uniprocessor or as one of an available number of multiprocessor configurations by specifying a number of virtual processors. In a specific example, one virtual processor is created for each thread or process in the instruction code. In this manner, when it is determined by the operating system, application, or otherwise that the current instruction code can be executed more efficiently in a multiprocessor of n-processors, the processor create instruction is used to instantiate n virtual processors to execute the code. The configuration may change dynamically in response to new applications starting or a running application spawning a new thread.

The term "virtual processors" is used herein to describe the functional operation of the dynamically configurable processor and method in accordance with the present invention. Each virtual processor is a logical processor as opposed to a physically implemented processor. As described in greater detail below, each virtual processor requires a set of execution resources that are unique to that processor. These unique resources are enabled in response to the processor create command to activate a virtual processor. Also, each virtual processor requires access to a set of shared execution resources. These shared resources are enabled independently of the processor create command. In accordance with the present invention, when a virtual processor is activated, the processor behaves as if it is the selected uniprocessor or multiprocessor, however, no physical reconfiguration, rewiring, or the like is required.

Referring to FIG. 3 and FIG. 4, processor creation unit 200 may be implemented as a plurality of state machines 301. In the example of FIG. 3, one state machine 301 is provided for each virtual processor. Any number of state machines 301, hence any number of virtual processors, may be included in processor 102. One of the state machines 301 is designated as a primary unit that is analogous to a boot processor in a conventional multiprocessor design. The primary state machine 301 will become active automatically when processor 102 is activated, while the other state machines 301 wait to respond to the processor create command to become activated.

At a minimum, each state machine comprises a "dead" or inactive state and a "live" or active state. The transition between dead and active states is controlled by the processor create command. Optionally, a processor destroy command can also be provided to move a state machine 301 from an active state to a dead state. Desirably, each state machine 301 includes a "nap" state that can be reached from the active state, and a "sleep" state that can be reached from the nap state. The active state can be reached from the dead, nap, or sleep states as shown in FIG. 4.

In a particular implementation, a virtual processor in the active state is assigned exclusive control over some of the shared resources in the functional units of processor 102. When one of the virtual processors experiences a delay in executing instructions, that delay preferably does not affect the other virtual processors. For example, when one virtual processor experiences an on-chip cache miss, it will require tens of clock cycles to obtain the required data from the off-chip cache. When an off-chip cache miss occurs and data must be retrieved from main memory, or mass storage, hundreds of clock cycles may occur before that process can make forward progress.

The nap and sleep states in state machines 301 are provided to account for these delays. When a virtual processor encounters an on-chip cache miss it is placed in a nap state. The nap state disables instruction fetching only for the virtual processor in the nap state. Instruction fetching continues for the remaining virtual processors. In the nap state, instruction scheduling and execution remain enabled (described in greater detail hereinbelow). Hence, in the nap state a virtual processor is allowed to continue possession of execution resources that it has already occupied, but is not allowed to take possession of any more resources so that other virtual processors may use these resources.

When a napping virtual processor encounters a cache miss that must be satisfied by main memory, or mass storage, the virtual processor enters the sleep state. In the sleep state, all instructions belonging to the sleeping virtual processor are flushed from ISU 206. Hence, not only is the sleeping processor prevented from taking additional resources, but it is also forced to release resources previously occupied so that other virtual processors may continue execution unimpaired. The sleep state prevents instructions from the sleeping virtual processor from clogging up ISU 206 and thereby interfering with execution of instructions from other virtual processors.

Instruction fetch unit (IFU) 202 (shown in greater detail in FIG. 5) comprises instruction fetch mechanisms and includes, among other things, an instruction cache I$ for storing instructions, branch prediction logic 501, and address logic for addressing selected instructions in instruction cache I$. The instruction cache I$ is a portion of the level one (L1) cache with another portion (D$, not shown) of the L1 cache dedicated to data storage in a Harvard architecture cache. Other cache organizations are known, including unified cache structures, and may be equivalently substituted and such substitutions will result in predictable performance impact.

IFU 202 fetches one or more instructions each clock cycle by appropriately addressing the instruction cache I$ via MUX 503 and MUX 305 under control of branch logic 501 as shown in FIG. 5. In the absence of a conditional branch instruction, IFU 202 addresses the instruction cache sequentially. Fetched instructions are passed to IRU 204 shown in FIG. 2. Any fetch bundle may include multiple control-flow (i.e., conditional or unconditional branch) instructions. Hence, IFU 202 desirably bases the next fetch address decision upon the simultaneously predicted outcomes of multiple branch instructions.

The branch prediction logic 501 (shown in FIG. 5) handles branch instructions, including unconditional branches. An outcome for each branch instruction is predicted using any of a variety of available branch prediction algorithms and mechanisms. In the example of FIG. 5, an exclusive-OR operation is performed on the current address and a value from a selected branch history register (BHR) to generate an index to the branch history table (BHT) 519. To implement a multiprocessor in accordance with the present invention, each virtual processor has a unique BHR. For a four processor implementation shown in FIG. 5, four BHR inputs labeled BHR.sub.-- 0, BHR.sub.-- 1, BHR.sub.-- 2, and BHR.sub.-- 3 are provided.

Each active BHR comprises information about the outcomes of a preselected number of most-recently executed condition and unconditional branch instructions for a particular active virtual processor. For virtual processors in the dead state, the BHR value is a don't care. An outcome can be represented in binary as taken or not taken. In a specific example, each active BHR comprises a seventeen-bit value representing the outcomes of seventeen most-recently executed branch instructions.

Processor create unit 200 selects one active BHR using multiplexor 517. Only one BHR is selected at a time, and processor create unit 200 serves to select the BHR in a round-robin fashion each clock cycle from the virtual processors that are in an active state. Hence, if only one processor is active, only BHR.sub.-- 0 will be selected. Each BHR comprises the outcomes (i.e., taken or not taken) for a number of most-recently executed conditional and unconditional branch instructions occurring on a processor-by-processor basis. In a specific example, each BHR comprises a 17-bit value. When a conditional branch instruction is predicted, the predicted outcome is used to speculatively update the appropriate BHR so that the outcome will be a part of the information used by the next BHT access for that virtual processor. When a branch is mispredicted, however, the appropriate BHR must be repaired by transferring the BHR VALUE from BRT 515, along actual outcome of the mispredicted branch are loaded into the BHR corresponding to the virtual processor on which the branch instruction occurred.

Next fetch address table (NFAT) 513 determines the next fetch address based upon the current fetch address received from the output of MUX 503. For example, NFAT 513 may comprise 2048 entries, each of which comprises two multi-bit values corresponding to a predicted next fetch address for instructions in two halves of the current fetch bundle. Two bits of the multi-bit values comprise set prediction for the next fetch, while the remaining bits are used to index the instruction cache I$ and provide a cache line offset in a specific implementation.

A branch repair table (BRT) 515 comprises entries or slots for a number of unresolved branch instructions. BRT 515 determines when a branch is mispredicted based upon input from IEU 208, for example. BRT 515, operating through branch logic 501, redirects IFU 202 down the correct branch path. Each entry in BRT 515 comprises multiple fields as detailed in FIG. 6. Branch taken fields (i.e., BT ADDRESS.sub.-- 1 through BT ADDRESS.sub.-- N) store an address (i.e., program counter value) for the first fetch bundle in the branch instructions predicted path. Branch not taken fields (i.e., BNT ADDRESS.sub.-- 1 through BNT ADDRESS.sub.-- N) store an address for the first fetch bundle in a path not taken by the branch instruction. A branch history table (BHT) index (BHT INDEX.sub.-- 1-BHT INDEX.sub.-- N) points to a location in the branch history table that was used to predict the branch instruction. The BHR VALUE and BHT VALUE fields store the value of the BHR and BHT, respectively, at the time a branch instruction was predicted.

The branch history table (BHT) 519 comprises a plurality of two-bit values. More than two-bit values may be used, but acceptable results are achieved with two bits. BHT 519 is indexed by computing an exclusive-or of the selected BHR value with the current fetch address taken from the output of MUX 503. In a specific example, the 17 least significant bits of the current address are used in the XOR computation (excluding the two most-least significant bits which are always 0's in a byte addressed processor with 32-bit instructions) to match the 17 bit values in each BHR. The XOR computation generates a 17-bit index that selects one entry in BHT. The 17 bit index enables selection from up to 2.sup.17 or 128K locations in BHT 519. One BHT 519 may be shared among any number of virtual processors.

Once a branch is resolved, the address of the path this branch actually follows is communicated from IEU 208 and compared against the predicted path address store in the BT ADDRESS fields. If these two addresses differ, those instructions down the mispredicted path are flushed from the processor and IFU 202 redirects instruction fetch down the correct path identified in the BNT ADDRESS field using the BRT input to MUX 505. Once a branch is resolved, the BHT value is updated using the BHT index and BHT value stored in BRT 515. In the example of FIG. 5, each entry in BHT 519 is a two-bit saturating counter. When a predicted branch is resolved taken, the entry used to predict this outcome is incremented. When a predicted branch is resolved not taken, the entry in BHT 519 is decremented. Other branch prediction algorithms and techniques may be used in accordance with the present invention, so long as care is taken to duplicate resources on a processor-by-processor basis where those resources are used exclusively by a given processor.

Although the fields in BRT 515 may include a thread identifier field to indicate which virtual processor executed the branch instruction assigned to that slot, BRT 515 is shared among all of the virtual processors and requires little modification to support dynamically configurable uniprocessing and multiprocessing in accordance with the present invention.

Another resource in IFU 202 that must be duplicated for each virtual processor is the return address stack (RAS) labeled RAS.sub.-- 0 through RAS.sub.-- 3 in FIG. 5. Each RAS comprises a last in, first out (LIFO) stack in a particular example that stores the return addresses of a number of most-recently executed branch and link instructions. These instructions imply a subsequent RETURN instruction that will redirect processing back to a point just after the fetch address when the branch or link instruction occurred. When an instruction implying a subsequent RETURN (e.g., a CALL or JMPL instruction in the SPARC V9 architecture) is executed, the current program counter is pushed onto a selected one of RAS.sub.-- 0 through RAS.sub.-- 3. The RAS must be maintained on a processor-by-processor (i.e., thread-by-thread) basis to ensure return to the proper location.

When a subsequent RETURN instruction is executed, the program counter value on top of the RAS is popped and selected by appropriately controlling multiplexor 505 in FIG. 5. This causes IFU 202 to begin fetching at the RAS-specified address. The RETURN instruction is allocated an entry in BRT 515 and the fall-through address is stored in the BNT ADDRESS field for that entry. If this RETURN instruction is mispredicted, it is extremely unlikely that the fall-through path is the path the RETURN should follow and IFU 202 must be redirected via an address computed by IEU 208 and applied to the IEU input to multiplexor 505.

IFU 202 includes instruction marker circuitry 507 for analyzing the fetched instructions to determine selected information about the instructions. Marker unit 507 is also coupled to processor create unit 200. This selected information, including the thread identification (i.e., the virtual processor identification) generated by processor create unit 200, is referred to herein as "instruction metadata". In accordance with the present invention, each fetch bundle is tagged with a thread identification for use by downstream functional units. Other metadata comprises information about, for example, instruction complexity and downstream resources that are required to execute the instruction. The term "execution resources" refers to architectural register space, rename register space, table space, decoding stage resources, and the like that must be committed within processor 102 to execute the instruction. The metadata can be generated by processor create unit 200 or dedicated combinatorial logic that outputs the metadata in response to the instruction op-code input. Alternatively, a look-up table or content addressable memory can be used to obtain the metadata. In a typical application, the instruction metadata will comprise two to eight bits of information that is associated with each instruction.

In many applications it is desirable to fetch multiple instructions at one time. For example, four, eight, or more instructions may be fetched simultaneously in a bundle. In accordance with the present invention, each instruction bundle includes the instruction metadata (e.g., THREAD ID) as shown in instruction bundle 700 shown in FIG. 7. I0-I7 represent conventional instruction fields that comprise, for example, an op-code, one or more operand or source register specifiers (typically denoted rs1, rs2, rs3, etc.) and a destination register specifier (typically denoted rd) and/or condition code specifiers. Other information, including instruction metadata, may be included in each I0-I7 field. As shown in FIG. 7, the instruction metadata for an entire bundle 700 may be grouped in a single field labeled THREAD ID in FIG. 7. Alternatively, the instruction metadata may be distributed throughout the I0-I7 instruction fields.

Although IFU 208 supporting dynamically configurable multiprocessing in accordance with the present invention has been described in terms of a specific processor capable of implementing one, two, three, or four virtual processors in a single processor unit, it should be appreciated that n-way multithreading can be achieved by modifying IFU 208 to fetch instructions from n different streams or threads on a round-robin or thread-by-thread basis each cycle. Because each fetch bundle includes instructions from only one thread, the modifications required to support dynamically configurable multithreading can be implemented with modest increase in hardware size and complexity. Essentially, any state information that needs to be tracked on a per-processor or per-thread basis must be duplicated. Other resources and information can be shared amongst the virtual processors. The BHR tracks branch outcomes within a single thread of execution so there should be one copy of the BHR for each thread. Similarly, the RAS tracks return addresses for a single thread of execution and so there should be one copy of the RAS for each thread.

The remaining functional units shown in FIG. 2 are referred to herein as "downstream" functional units although instructions and data flow bidirectionally between the remaining functional units. As described in greater detail below, some or all of the downstream functional units have resources that may be effectively shared among multiprocessors in accordance with the present invention. A significant advantage in accordance with the present invention is that the downstream functional units do not require complete duplication to enable multiprocessor functionality. Another advantage is that several functional units include resources that can be dynamically shared thereby enabling "on-the-fly" reconfiguration from a uniprocessor mode to any of a number of multiprocessor modes.

IRU 204, comprises one or more pipeline stages that include instruction renaming and dependency checking mechanisms. A feature of the present invention is that inter-bundle dependency checking is relaxed because bundles from different threads are inherently independent. IRU 204 implements necessary logic for handling rename registers in a register window-type architecture such as the SPARC-V9 instruction architecture. A dependency checking mechanism, called an inverse map table (IMT) or dependency checking table (DCT) in a specific example, is used to analyze the instructions to determine if the operands (identified by the instructions' register specifiers) cannot be determined until another live instruction has completed. A particular embodiment of an IMT is described in greater detail in U.S. patent application Ser. No. 08/882,173 titled "A STRUCTION AND MECHANISM FOR ENFORCING TRUE DEPENDENCIES IN AN OUT OF ORDER MACHINE" by Ramesh Panwar and Dani Y. Dakhil filed concurrently herewith, is operative to map register specifiers in the instructions to physical register locations and to perform register renaming to prevent dependencies. IRU 204 outputs renamed instructions to instruction scheduling unit (ISU) 206.

Each entry compares the source fields (rs1 and rs2) of all eight incoming instructions against the destination register field for that entry. If there is a match, the entry broadcasts its own address on to the corresponding bus through a simple encoder. This broadcast address is referred to as a producer ID (PID) and is used by the instruction scheduling window (ISW) within instruction scheduling unit 206 to determine the ready status of waiting instructions. A match also takes place between the CC fields of the eight incoming instructions and the CC field of the entry.

When a branch instruction is resolved and its predicted direction turns out to be wrong, the prefetched instructions following it (within the same thread or virtual processor) must be flushed from the ISW. Fetching into the window must resume at the position following the mispredicted branch, as described hereinbefore with respect to IFU 202. However, instructions being flushed may have been taken over as being youngest producers of certain registers in the machine. There are two ways to handle this situation. One, resume fetching into the window but prevent scheduling of the new instructions until all of the previous instructions have retired from the window. Alternatively, rewind the youngest-producer information within the dependency checking table so the older instructions are reactivated as appropriate.

Each entry in the ISW is tagged with a two-bit thread ID to identify the thread to which the instruction belongs. On a flush, the ISW entries belonging to only the thread that suffered the branch mispredict are eliminated while the entries corresponding to the other threads stay resident. Hence, the flush information that is broadcast by IEU 208 has to contain the thread identifier of the mispredicted branch.

IRU 204 further comprises a window repair table (WRT) operative to store status information about register window instructions used to restore the state of register windows after a branch misprediction. The WRT includes thirty-two entries or slots, each entry comprising one or more fields of information in a particular example. The number of entries in the WRT may be more or less depending on the needs of a particular application. The WRT can be shared amongst the multiprocessors in accordance with the present invention and does not require modification. The WRT would not be necessary in a processor that does not use register widows.

ISU 206 (shown in greater detail in FIG. 8) is operative to schedule and dispatch instructions as soon as their dependencies have been satisfied into an appropriate execution unit (e.g., integer execution unit (IEU) 208, or floating point and graphics unit (FGU) 210). ISU 206 also maintains trap status of live instructions. ISU 206 may perform other functions such as maintaining the correct architectural state of processor 102, including state maintenance when out-of-order instruction processing is used. ISU 206 may include mechanisms to redirect execution appropriately when traps or interrupts occur and to ensure efficient execution of multiple threads where multiple threaded operation is used. Multiple thread operation means that processor 102 is running multiple substantially independent processes simultaneously. Multiple thread operation is consistent with but not required by the present invention.

In accordance with an embodiment of the present invention, state machines 301 are implemented in ISU 206 by maintaining virtual processor status information in ISU 206. Although other functional units use the thread ID to implement multiprocessors in accordance with the present invention, ISU 206 uses the virtual processor status information to implement the active, nap, and sleep states described hereinbefore. Hence, to ease circuit complexity and improve operation speed, it is advantageous to implement state machines 301 in ISU 206.

ISU 206 also operates to retire executed instructions when completed by IEU 208 and FGU 210. ISU assigns each live instruction a position or slot in an instruction retirement window (IRW) shown in FIG. 8. In a specific embodiment, the IRW includes one slot for every live instruction. ISU 206 directs the appropriate updates to architectural register files and condition code registers upon complete execution of an instruction. ISU 206 is responsive to exception conditions and discards or flushes operations being performed on instructions subsequent to an instruction generating an exception. ISU 206 quickly removes instructions from a mispredicted branch and instructs IFU 202 to fetch from the correct branch. An instruction is retired when it has finished execution and all instructions from which it depends have completed. Upon retirement the instruction's result is written into the appropriate register file and is no longer deemed a "live instruction".

In operation, ISU 206 receives renamed instructions from IRU 204 and registers them for execution by assigning each instruction a position or slot in an instruction scheduling window (ISW). In a specific embodiment, the ISW includes one slot 900 (shown in FIG. 9) for every live instruction. Each entry 900 in the ISW is associated with an entry 1000 in an instruction wait buffer (IWB) shown in FIG. 10 by an IWB POINTER. In accordance with the present invention, each entry 900 includes a THREAD ID field holding the thread identification. Dependency information about the instruction is encoded in the PID fields of ISW entry 900. Metadata such as an instruction identification, ready status, and latency information, for example, are stored in a METADATA field of each entry 900. Status information, included virtual processor status, is stored in the STATUS field ISW entry 900. In a particular example, each STATUS field includes three bits to indicate status (e.g., active, dead, nap, sleep) for each instruction. State machines 301 are implemented by control logic that updates these status bits.

One or more instruction picker devices such as 802a and 802b in FIG. 8 pick instructions from the ISW that are ready for execution by generating appropriate signals on word lines 806 to the instruction wait buffer (IWB) so that the instruction will be read out or issued to execution units such as IEU 208 and FGU 210 in FIG. 2. Pickers 802a and 802b desirably base the decision of which instructions to pick upon the instruction's relative age as well (e.g., how long the instruction has been in ISU 206).

The instruction is issued to IEU 208 or FGU 210 together with the thread identification and instruction identification so that IEU 208 or FGU 210 can respond back with the trap and completion status on an instruction-by-instruction basis. When the trap and completion status of an instruction arrives from IEU 208 or FGU 210, they are written into an instruction retirement window (IRW) shown in FIG. 2. Retirement logic examines contiguous entries in the IRW and retires them in order to ensure proper architectural state update.

In addition to retirement, one or more instructions can be removed from the execution pipelines by pipeline flushes in response to branch mispredictions, traps, and the like. In the case of a pipeline flush, the resources committed to the flushed instructions are released as in the case of retirement, but any speculative results or state changes caused by the flushed instructions are not committed to architectural registers. In accordance with the present invention, a pipeline flush affects only instructions in a single thread or virtual processor, leaving other active virtual processors unaffected.

IEU 208 includes one or more pipelines, each pipeline comprising one or more stages that implement integer instructions such as integer arithmetic units 1106 in FIG. 11. The integer arithmetic units 1106 are shared amongst the virtual processors in accordance with the present invention. IEU 208 also includes an integer result buffer (IRB) 1108 that is shared amongst the virtual processors for holding the results and state of speculatively executed integer instructions. IRB 1108 comprises a hardware-defined number of registers that represent another type of execution resource. In a specific example IRB 1108 comprises one register slot for each live instruction.

IEU 208 functions to perform final decoding of integer instructions before they are executed on the execution units and to determine operand bypassing amongst instructions in an out-of-order processor. IEU 208 executes all integer instructions including determining correct virtual addresses for load/store instructions. IEU 208 also maintains correct architectural register state for a plurality of architectural integer registers in processor 102. IEU 208 preferably includes mechanisms to access single and/or double precision architectural registers 1101. In accordance with the present invention, a copy of the integer architectural register files is provided for each virtual processor as shown in FIG. 11. Similarly, a copy of the condition code architectural register files 1103 is provided for each virtual processor. Speculative results and condition codes in shared integer result buffer 1108 are transferred upon retirement to appropriate architectural files 1101 and 1103 under control of retire logic 804. Because the architectural register files 1101 and 1103 may be much smaller than integer result buffer 1108, duplication of the architectural files on a processor-by-processor basis has limited impact on the overall size and complexity of the dynamically reconfigurable multiprocessor in accordance with the present invention.

FGU 210, includes one or more pipelines, each comprising one or more stages that implement floating point instructions such as floating point arithmetic units 1107 in FIG. 11. FGU 210 also includes a floating point results buffer (FRB) 1109 for holding the results and state of speculatively executed floating point and graphic instructions. The FRB 1109 comprises a hardware-defined number of registers that represent another type of execution resource. In the specific example FRB 1109 comprises one register slot for each live instruction. FGU 210 functions to perform final decoding of floating point instructions before they are executed on the execution units and to determine operand bypassing amongst instructions in an out-of-order processor.

In a specific example, FGU 210 includes one or more pipelines (not shown) dedicated to implement special purpose multimedia and graphic instructions that are extensions to standard architectural instructions for a processor. FGU 210 may be equivalently substituted with a floating point unit (FPU) in designs in which special purpose graphic and multimedia instructions are not used. FGU 210 preferably includes mechanisms to access single and/or double precision architectural registers 1102 and condition code registers 1104. Speculative results and condition codes in shared floating point result buffer 1109 are transferred upon retirement to appropriate architectural files 1102 and 1104 under control of retire logic 804. Each processor is provided with a unique set of architectural registers 1102 and 1104 to provide processor independence.

Optionally, FGU 210 may include a graphics mapping table (GMT) comprising a fixed number of resources primarily or exclusively used for graphics operations. The GMT resources are typically used only for graphics instructions and so will not be committed for each live instruction. In accordance with the present invention, the instruction metadata includes information about whether the fetched instruction requires GMT-type resources. The GMT resources may be shared amongst the virtual processors in accordance with the present invention.

A data cache memory unit (DCU) 212, including cache memory 105 shown in FIG. 1, functions to cache memory reads from off-chip memory through external interface unit (EIU) 214 shown in FIG. 2. Optionally, DCU 212 also caches memory write transactions. DCU 212 comprises one or more hierarchical levels of cache memory and the associated logic to control the cache memory. One or more of the cache levels within DCU 212 may be read only memory to eliminate the logic associated with cache writes.

In a specific implementation, DCU 212 comprises separate Instruction and Data caches in the L1 cache, a unified level 2 cache (L2$) that is desirably formed on-chip, and an external level 3 cache (L3$). Details on the size, organization and operational policy are discussed herein to ease description, but it is expressly understood that a wide variety of cache and memory architectures can cooperate with and benefit from the apparatus and methods in accordance with the present invention.

Each cache level has an inherently higher latency (i.e., time to return data). Latency is typically measured from the launch of the virtual address of a memory operation instruction. The first level caches (I$ and D$) have the lowest latency in the range of a few clock cycles. L2 cache is next with a latency of two to ten times that of the L1 cache. In the specific example L3 cache is an off-chip cache resulting in approximate latency of twenty-five to fifty clock cycles. In many designs, L2 cache is off-chip and so latency estimates would be adjusted accordingly. Latency to main memory is approximately 100 clock cycles although this number can vary dramatically if some of main memory is serviced by swap files in mass storage 107 (shown in FIG. 1). For purposes of understanding the present invention, it is important only to know that each subsequent cache level results in increasing latency.

Each cache level includes some device to detect whether the data requested by a program or by a lower level of cache exists in the cache level. When data exists in the cache a "hit" is generated and the data is returned to service the memory operation instruction. When data does not exist in the cache, a "miss" is generated and the data must be fetched from a higher cache level or main memory. In accordance with the present invention, DCU 212 is coupled to update state machines 301 such that a cache miss in the on-chip cache(s) results in a transition from an active state to a nap state. The nap state prohibits instructions from being fetched for the napping processor. Further, a cache miss that must be serviced from main memory (including service from mass storage), places the processor generating the cache request into the sleep state. The sleep state results in termination of instruction fetching and instruction execution. Instruction execution is halted by, for example, flushing all instructions tagged with the thread id corresponding to the sleeping process from instruction scheduling unit 206. By removing these instruction, pickers 802a and 802b can move forward to pick instructions from active processes.

It is contemplated that other instructions in addition to memory operations may result in latencies that can be handled by the state machine process in accordance with the present invention. For example, CISC machines may include instructions specifically adapted to access external peripherals, network resources, or the like. These instructions may also suffer from long expected latency and so are desirably placed in a nap or sleep state to avoid clogging shared resources in a dynamically configurable multiprocessor in accordance with the present invention.

While the invention has been particularly shown and described with reference to a preferred embodiment thereof, it will be understood by those skills in the art that various other changes in the form and details may be made without departing from the spirit and scope of the invention. The various embodiments have been described using hardware examples, but the present invention can be readily implemented in software. For example, it is contemplated that a programmable logic device, hardware emulator, software simulator, or the like of sufficient complexity could implement the present invention as a computer program product including a computer usable medium having computer readable code embodied therein for dynamically configuring emulated or simulated processor. Accordingly, these and other variations are equivalent to the specific implementations and embodiments described herein.