US 6,079,006 AGrant

Stride-Based Data Address Prediction Structure

Issue Date:2000-06-20

•18 Claims

•42 Drawing Sheets

Abstract

A data prediction structure is provided for a superscalar microprocessor. The data prediction structure stores base addresses and stride values in a prediction array. The base address and the stride value from a location within the data prediction structure indexed by an instruction address are added to form a data prediction address which is then used to fetch data bytes into a reservation station storing an associated instruction. If the data associated with an operand address calculated by an associated functional unit resides in the reservation station, the clock cycles used to perform the load operation have occurred before the instruction reached the reservation station. Additionally, the base address is updated to the address generated by executing an instruction each time the instruction is executed, and the stride value is updated when the data prediction address is found to be incorrect.

Metadata

Assignee

Advanced Micro Devices, Inc.

Inventor

James K. Pickett

Application Information

Application Number:US 0521833

Filing Date:1998-03-31

Priority Date:1995-08-31

Art Unit:273

Classifications

IPC:

G06F 938G06F 932G06F 9355

Field of Search:

711712365213;1;3;221218;215;238;16;237;233;23949

Patent Drawings (42 sheets)

Description

BACKGROUND OF THE INVENTION

1. Field of the Invention

This invention relates to the field of superscalar microprocessors and, more particularly, to data prediction mechanisms in superscalar microprocessors.

2. Description of the Relevant Art

Superscalar microprocessors achieve high performance by simultaneously executing multiple instructions in a clock cycle and by specifying the shortest possible clock cycle consistent with the design. As used herein, the term "clock cycle" refers to an interval of time during which the pipeline stages of a microprocessor perform their intended functions. For example, superscalar microprocessors are typically configured with instruction processing pipelines which process instructions. The processing of instructions includes the actions of fetching, dispatching, decoding, executing, and writing back results. Each action may be implemented in one or more pipeline stages, and an instruction flows through each of the pipeline stages where an action or portion of an action is performed. At the end of a clock cycle, the instruction and the values resulting from performing the action of the current pipeline stage are moved to the next pipeline stage. When an instruction reaches the end of an instruction processing pipeline, it is processed and the results of executing the instruction have been recorded.

Since superscalar microprocessors execute multiple instructions per clock cycle and the clock cycle is short, a high bandwidth memory system is required to provide instructions and data to the superscalar microprocessor (i.e. a memory system that can provide a large number of bytes in a short period of time). Without a high bandwidth memory system, the microprocessor would spend a large number of clock cycles waiting for instructions or data to be provided, then would execute the received instructions and/or instructions dependent upon the received data in a relatively small number of clock cycles. Overall performance would be degraded by the large number of idle clock cycles. Superscalar microprocessors are, however, ordinarily configured into computer systems with a relatively large main memory composed of dynamic random access memory (DRAM) cells. DRAM cells are characterized by access times which are significantly longer than the clock cycle of modern superscalar microprocessors. Also, DRAM cells typically provide a relatively narrow output bus to convey the stored bytes to the superscalar microprocessor. Therefore, DRAM cells provide a memory system that provides a relatively small number of bytes in a relatively long period of time, and do not form a high bandwidth memory system.

Because superscalar microprocessors are typically not configured into a computer system with a memory system having sufficient bandwidth to continuously provide instructions and data, superscalar microprocessors are often configured with caches. Caches include multiple blocks of storage locations configured on the same silicon substrate as the microprocessor or coupled nearby. The blocks of storage locations are used to hold previously fetched instruction or data bytes. The bytes can be transferred from the cache to the destination (a register or an instruction processing pipeline) quickly; commonly one or two clock cycles are required as opposed to a large number of clock cycles to transfer bytes from a DRAM main memory.

Unfortunately, the latency of one or two clock cycles within a data cache is becoming a performance problem for superscalar microprocessors as they attempt to execute more instructions per clock cycle. The problem is of particular importance to superscalar microprocessors configured to execute instructions from a complex instruction set architecture such as the x86 architecture. As will be appreciated by one skilled in the art, x86 instructions allow for one of their "operands" (the values that the instruction operates on) to be stored in a memory location. Instructions which have an operand stored in memory are said to have an implicit (memory read) operation and an explicit operation which is defined by the particular instruction being executed (i.e. an add instruction has an explicit operation of addition). Such an instruction therefore requires an implicit address calculation for the memory read to retrieve the operand, the implicit memory read, and the execution of the explicit operation of the instruction (for example, an addition). Typical superscalar microprocessors have required that these operations be performed by the execute stage of the instruction processing pipeline. The execute stage of the instruction processing pipeline is therefore occupied for several clock cycles when executing such an instruction. For example, a superscalar microprocessor might require one clock cycle for the address calculation, one to two clock cycles for the data cache access, and one clock cycle for the execution of the explicit operation of the instruction. Conversely, instructions with operands stored in registers configured within the microprocessor retrieve the operands before they enter the execute stage of the instruction processing pipeline, since no address calculation is needed to locate the operands. Instructions with operands stored in registers would therefore only require the one clock cycle for execution of the explicit operation. A structure allowing the retrieval of memory operands for instructions before they enter the execute stage is therefore desired.

SUMMARY OF THE INVENTION

The problems outlined above are in large part solved by a data prediction structure for a superscalar microprocessor in accordance with the present invention. The data prediction structure stores base addresses and stride values in a prediction array. A particular base address and associated stride value are added to form a data prediction address. The data prediction address is then used to fetch data bytes which are conveyed to the reservation stations of the superscalar microprocessor. If the data associated with an operand address calculated by a functional unit resides in the reservation station, the data is used as the operand. Advantageously, the clock cycles used to perform the load operation occur before the instruction reaches the reservation station. The instruction occupies the reservation station for fewer clock cycles than would be necessary utilizing the conventional method of executing these instructions. The clock cycles that are saved may be profitably used to store other instructions.

Additionally, the base address is updated to the address generated by a functional unit each time an associated instruction is executed, and the stride value is updated when the data prediction address is found to be incorrect. In this way, the data prediction address is in many cases more accurate then a static data prediction address that changes only when it is found to be incorrect. Advantageously, the implicit load may be performed more often prior to the instruction reaching the reservation station. Furthermore, if several correct predictions are made in consecutive executions of an associated instruction, the prediction must be incorrect in several consecutive executions before the stride is changed (according to one embodiment of the present invention). Advantageously, a single execution of another instruction whose instruction address indexes the same storage location as the correct prediction information does not destroy the prediction information.

Broadly speaking, the present invention contemplates a method for predicting a data address which will be referenced by a plurality of instructions when said plurality of instructions are fetched, comprising several steps. A data prediction address is generated from a base address and a stride value during a clock cycle in which a data prediction counter indicates that the base address and the stride value are valid. Data associated with the data prediction is fetched from a data cache. Then, the data is stored within a plurality of reservation stations.

The present invention further contemplates a data address prediction structure comprising an array, an adder circuit, and a reservation station. The array includes a plurality of storage locations for storing a plurality of base addresses and a plurality of stride values. A particular storage location is selected by an instruction address which identifies an instruction. The instruction generates one of the plurality of base addresses. The adder circuit is coupled to the array for adding a base address and a stride value conveyed from the array to produce a data prediction address. The reservation station stores the instruction and data associated with the data prediction address.

BRIEF DESCRIPTION OF THE DRAWINGS

Other objects and advantages of the invention will become apparent upon reading the following detailed description and upon reference to the accompanying drawings in which:

FIG. 1 is a block diagram of a superscalar microprocessor.

FIG. 2 is a diagram depicting a branch prediction unit, a load/store unit, and a data cache of the superscalar microprocessor of FIG. 1, along with several elements of one embodiment of the present invention.

FIG. 3A is a diagram of the branch prediction unit shown in FIG. 2 depicting several elements of one embodiment of the present invention.

FIG. 3B is a diagram of a reservation station of the superscalar microprocessor shown in FIG. 1 showing several elements of one embodiment of the present invention.

FIG. 4 is a diagram of the information stored in a storage location of a branch prediction array in accordance with the present invention.

FIG. 5 is a block diagram of a superscalar microprocessor.

FIG. 6 is a block diagram of a pipeline for calculating addresses within processor 500.

FIG. 7 shows a programmer's view of the x86 register file.

FIG. 8 is a timing diagram which shows fetching, scanning, aligning, decoding, and muxing of instructions in microprocessor 500.

FIG. 9 is a block diagram which illustrates a portion of an exemplary embodiment of processor 500.

FIG. 10 is a block diagram of a portion of the instruction cache shown in FIG. 5.

FIG. 11 is a block diagram illustrating routing of instructions starting at various byte positions to various decode units.

FIG. 12 is a block diagram of an exemplary layout for the ICTAGV.

FIG. 13 is a block diagram of one embodiment of ICNXTBLK.

FIG. 14 is a block diagram of a global branch predictor.

FIG. 15 illustrates processor 500 pipeline execution cycles with a branch misprediction detected.

FIG. 16 is a block diagram of an exemplary layout for ICNXTBLK.

FIG. 17 is a timing diagram illustrating branch misprediction.

FIG. 18 is a block diagram of a return stack.

FIG. 19 is a block diagram of a predecode unit.

FIG. 20 is a timing diagram illustrating fetching, scanning, and aligning of instructions in processor 500.

FIG. 21 is a block diagram illustrating alignment, early decode, and decode blocks.

FIG. 22 is a block diagram illustrating exemplary hardware for early decoding of prefixes and opcodes.

FIG. 23 is a block diagram of logic for forming OPBYTE signals.

FIG. 24 is a block diagram illustrating MROM register decoding.

FIG. 25 is a block diagram illustrating multiplexing of 2-dispatch position instructions.

FIG. 26 shows an embodiment of the ICCNTL state machine.

FIG. 27 is a block diagram illustrating an exemplary layout of ICACHE arrays.

FIG. 28 is a block diagram of an exemplary ICDECODE layout.

FIG. 29 is a block diagram of exemplary reservation station logic.

FIG. 30 is a timing diagram for one embodiment of the reservation stations.

FIG. 31 is a block diagram of one embodiment of a functional unit.

FIG. 32 is a more detailed block diagram of one embodiment of a functional unit.

FIG. 33 is a block diagram of an exemplary reorder buffer.

FIG. 34 is a block diagram of an exemplary layout for a reorder buffer.

FIG. 35 is a block diagram illustrating dependency checking in one embodiment of a reorder buffer.

FIG. 36 is a block diagram of another exemplary layout for the reorder buffer.

FIG. 37 is a timing diagram for an exemplary register file.

FIG. 38 is a block diagram of one embodiment of a register file.

FIG. 39 is a block diagram of one embodiment of a load/store unit.

FIG. 40 is a block diagram illustrating an exemplary common load/store buffer.

FIG. 41 illustrates an exemplary load/store buffer entry.

FIG. 42 is a timing diagram illustrating update of the common load/store buffer.

FIG. 43 is an exemplary timing diagram for aligned load/store data cache accesses.

FIG. 44 is an exemplary timing diagram for dependency checking in the load/store unit.

FIG. 45 is a block diagram illustrating dependency checking according to one embodiment of the load/store unit.

FIG. 46 is a block diagram illustrating segment calculations according to one embodiment of the load/store unit.

FIG. 47 is a timing diagram illustrating limit/protection checks according to one embodiment of the load/store unit.

FIG. 48 is a block diagram of one embodiment of a special register block.

FIG. 49 is a block diagram of one embodiment of protection checking hardware.

FIG. 50 is a block diagram illustrating an exemplary load/store unit partitioning.

FIG. 51 is a block diagram illustrating a layout of the exemplary load/store unit with respect to other units.

FIG. 52 is a block diagram of one embodiment of the data cache.

FIG. 53 is a block diagram of one embodiment of a tag array entry.

FIG. 54 is a block diagram of one embodiment of a way prediction entry.

FIG. 55 is a timing diagram for dcache load accesses according to one embodiment of the data cache.

FIG. 56 is a block diagram showing exemplary hardware for performing aligned loads.

FIG. 57 is a timing diagram for dcache store accesses according to one embodiment of the data cache.

FIG. 58 is a timing diagram for unaligned load accesses according to one embodiment of the data cache.

FIG. 59 is a second timing diagram for unaligned load accesses according to one embodiment of the data cache.

FIG. 60 is a third timing diagram for unaligned load accesses according to one embodiment of the data cache.

FIG. 61 is a fourth timing diagram for unaligned load accesses according to one embodiment of the data cache.

FIG. 62 is a timing diagram for unaligned store accesses according to one embodiment of the data cache.

FIG. 63 is a second timing diagram for unaligned store accesses according to one embodiment of the data cache.

FIG. 64 is a third timing diagram for unaligned store accesses according to one embodiment of the data cache.

FIG. 65 is a timing diagram for processing a load miss according to one embodiment of the data cache.

FIG. 66 is a timing diagram for data cache reloads according to one embodiment of the data cache.

FIG. 67 is a block diagram of one embodiment of a computer system including the microprocessor shown in FIG. 1.

While the invention is susceptible to various modifications and alternative forms, specific embodiments thereof are shown by way of example in the drawings and will herein be described in detail. It should be understood, however, that the drawings and detailed description thereto are not intended to limit the invention to the particular form disclosed, but on the contrary, the intention is to cover all modifications, equivalents and alternatives falling within the spirit and scope of the present invention as defined by the appended claims.

DETAILED DESCRIPTION OF THE INVENTION

Turning now to FIG. 1, a block diagram of a superscalar microprocessor 200 including reservation stations 210 and a branch prediction unit 220 in accordance with the present invention is shown. As illustrated in the embodiment of FIG. 1, superscalar microprocessor 200 includes a prefetch/predecode unit 202 and a branch prediction unit 220 coupled to an instruction cache 204. Instruction alignment unit 206 is coupled between instruction cache 204 and a plurality of decode units 208A-208F (referred to collectively as decode units 208). Each decode unit 208A-208F is coupled to respective reservation station units 210A-210F (referred to collectively as reservation stations 210), and each reservation station 210A-210F is coupled to a respective functional unit 212A-212F (referred to collectively as functional units 212). Decode units 208, reservation stations 210, and functional units 212 are further coupled to a reorder buffer 216, a register file 218 and a load/store unit 222. A data cache 224 is finally shown coupled to load/store unit 222, and an MROM unit 209 is shown coupled to instruction alignment unit 206.

Generally speaking, instruction cache 204 is a high speed cache memory provided to temporarily store instructions prior to their dispatch to decode units 208. In one embodiment, instruction cache 204 is configured to cache up to 32 kilobytes of instruction code organized in lines of 16 bytes each (where each byte consists of 8 bits). During operation, instruction code is provided to instruction cache 204 by prefetching code from a main memory (not shown) through prefetch/predecode unit 202. It is noted that instruction cache 204 could be implemented in a set-associative, a fully-associative, or a direct-mapped configuration.

Prefetch/predecode unit 202 is provided to prefetch instruction code from the main memory for storage within instruction cache 204. In one embodiment, prefetch/predecode unit 202 is configured to burst 64-bit wide code from the main memory into instruction cache 204. It is understood that a variety of specific code prefetching techniques and algorithms may be employed by prefetch/predecode unit 202.

As prefetch/predecode unit 202 fetches instructions from the main memory, it generates three predecode bits associated with each byte of instruction code: a start bit, an end bit, and a "functional" bit. The predecode bits form tags indicative of the boundaries of each instruction. The predecode tags may also convey additional information such as whether a given instruction can be decoded directly by decode units 208 or whether the instruction must be executed by invoking a microcode procedure controlled by MROM unit 209, as will be described in greater detail below.

Table 1 indicates one encoding of the predecode tags. As indicated within the table, if a given byte is the first byte of an instruction, the start bit for that byte is set. If the byte is the last byte of an instruction, the end bit for that byte is set. If a particular instruction cannot be directly decoded by the decode units 208, the functional bit associated with the first byte of the instruction is set. On the other hand, if the instruction can be directly decoded by the decode units 208, the functional bit associated with the first byte of the instruction is cleared. The functional bit for the second byte of a particular instruction is cleared if the opcode is the first byte, and is set if the opcode is the second byte. It is noted that in situations where the opcode is the second byte, the first byte is a prefix byte. The functional bit values for instruction byte numbers 3-8 indicate whether the byte is a MODRM or an SIB byte, or whether the byte contains displacement or immediate data.

As stated previously, in one embodiment certain instructions within the x86 instruction set may be directly decoded by decode units 208. These instructions are referred to as "fast path" instructions. The remaining instructions of the x86 instruction set are referred to as "MROM instructions". MROM instructions are executed by invoking MROM unit 209. More specifically, when an MROM instruction is encountered, MROM unit 209 parses and serializes the instruction into a subset of defined fast path instructions to effectuate a desired operation. A listing of exemplary x86 instructions categorized as fast path instructions as well as a description of the manner of handling both fast path and MROM instructions will be provided further below.

Instruction alignment unit 206 is provided to channel variable byte length instructions from instruction cache 204 to fixed issue positions formed by decode units 208A-208F. Instruction alignment unit 206 independently and in parallel selects instructions from three groups of instruction bytes provided by instruction cache 204 and arranges these bytes into three groups of preliminary issue positions. Each group of issue positions is associated with one of the three groups of instruction bytes. The preliminary issue positions are then merged together to form the final issue positions, each of which is coupled to one of decode units 208.

Before proceeding with a detailed description of the data address prediction structure embodied in reservation stations 210 and branch prediction unit 220, general aspects regarding other subsystems employed within the exemplary superscalar microprocessor 200 of FIG. 1 will be described. For the embodiment of FIG. 1, each of the decode units 208 includes decoding circuitry for decoding the predetermined fast path instructions referred to above. In addition, each decode unit 208A-208F routes displacement and immediate data to a corresponding reservation station unit 210A-210F. Output signals from the decode units 208 include bit-encoded execution instructions for the functional units 212 as well as operand address information, immediate data and/or displacement data.

The superscalar microprocessor of FIG. 1 supports out of order execution, and thus employs reorder buffer 216 to keep track of the original program sequence for register read and write operations, to implement register renaming, to allow for speculative instruction execution and branch misprediction recovery, and to facilitate precise exceptions. As will be appreciated by those of skill in the art, a temporary storage location within reorder buffer 216 is reserved upon decode of an instruction that involves the update of a register to thereby store speculative register states. Reorder buffer 216 may be implemented in a first-in-first-out configuration wherein speculative results move to the "bottom" of the buffer as they are validated and written to the register file, thus making room for new entries at the "top" of the buffer. Other specific configurations of reorder buffer 216 are also possible, as will be described further below. If a branch prediction is incorrect, the results of speculatively-executed instructions along the mispredicted path can be invalidated in the buffer before they are written to register file 218.

The bit-encoded execution instructions and immediate data provided at the outputs of decode units 208A-208F are routed directly to respective reservation station units 210A-210F. In one embodiment, each reservation station unit 210A-210F is capable of holding instruction information (i.e., bit encoded execution bits as well as operand values, operand tags and/or immediate data) for up to three pending instructions awaiting issue to the corresponding functional unit. It is noted that for the embodiment of FIG. 1, each decode unit 208A-208F is associated with a dedicated reservation station unit 210A-210F, and that each reservation station unit 210A-210F is similarly associated with a dedicated functional unit 212A-212F. Accordingly, six dedicated "issue positions" are formed by decode units 208, reservation station units 210 and functional units 212. Instructions aligned and dispatched to issue position 0 through decode unit 208A are passed to reservation station unit 210A and subsequently to functional unit 212A for execution. Similarly, instructions aligned and dispatched to decode unit 208B are passed to reservation station unit 210B and into functional unit 212B, and so on.

Upon decode of a particular instruction, if a required operand is a register location, register address information is routed to reorder buffer 216 and register file 218 simultaneously. Those of skill in the art will appreciate that the x86 register file includes eight 32 bit real registers (i.e., typically referred to as EAX, EBX, ECX, EDX, EBP, ESI, EDI and ESP). Reorder buffer 216 contains temporary storage locations for results which change the contents of these registers to thereby allow out of order execution. A temporary storage location of reorder buffer 216 is reserved for each instruction which, upon decode, is determined to modify the contents of one of the real registers. Therefore, at various points during execution of a particular program, reorder buffer 216 may have one or more locations which contain the speculatively executed contents of a given register. If following decode of a given instruction it is determined that reorder buffer 216 has a previous location or locations assigned to a register used as an operand in the given instruction, the reorder buffer 216 forwards to the corresponding reservation station either: 1) the value in the most recently assigned location, or 2) a tag for the most recently assigned location if the value has not yet been produced by the functional unit that will eventually execute the previous instruction. If the reorder buffer has a location reserved for a given register, the operand value (or tag) is provided from reorder buffer 216 rather than from register file 218. If there is no location reserved for a required register in reorder buffer 216, the value is taken directly from register file 218. If the operand corresponds to a memory location, the operand value is provided to the reservation station unit through load/store unit 222.

Details regarding suitable reorder buffer implementations may be found within the publication "Superscalar Microprocessor Design" by Mike Johnson, Prentice-Hall, Englewood Cliffs, N.J., 1991, and within the co-pending, commonly assigned patent application entitled "High Performance Superscalar Microprocessor", Ser. No. 08/146,382, filed Oct. 29, 1993 by Witt, et al., now abandoned. These documents are incorporated herein by reference in their entirety.

Reservation station units 210A-210F are provided to temporarily store instruction information to be speculatively executed by the corresponding functional units 212A-212F. As stated previously, each reservation station unit 210A-210F may store instruction information for up to three pending instructions. Each of the six reservation stations 210A-210F contain locations to store bit-encoded execution instructions to be speculatively executed by the corresponding functional unit and the values of operands. If a particular operand is not available, a tag for that operand is provided from reorder buffer 216 and is stored within the corresponding reservation station until the result has been generated (i.e., by completion of the execution of a previous instruction). It is noted that when an instruction is executed by one of the functional units 212A-212F, the result of that instruction is passed directly to any reservation station units 210A-210F that are waiting for that result at the same time the result is passed to update reorder buffer 216 (this technique is commonly referred to as "result forwarding"). Instructions are issued to functional units for execution after the values of any required operand(s) are made available. That is, if an operand associated with a pending instruction within one of the reservation station units 210A-210F has been tagged with a location of a previous result value within reorder buffer 216 which corresponds to an instruction which modifies the required operand, the instruction is not issued to the corresponding functional unit 212 until the operand result for the previous instruction has been obtained. Accordingly, the order in which instructions are executed may not be the same as the order of the original program instruction sequence. Reorder buffer 216 ensures that data coherency is maintained in situations where read-after-write dependencies occur. Reservation stations 210 additionally store information related to the data prediction structure disclosed herein, as will be described below.

In one embodiment, each of the functional units 212 is configured to perform integer arithmetic operations of addition and subtraction, as well as shifts, rotates, logical operations, and branch operations. It is noted that a floating point unit (not shown) may also be employed to accommodate floating point operations.

Each of the functional units 212 also provides information regarding the execution of conditional branch instructions to the branch prediction unit 220. If a branch prediction was incorrect, branch prediction unit 220 flushes instructions subsequent to the mispredicted branch that have entered the instruction processing pipeline, and causes prefetch/predecode unit 202 to fetch the required instructions from instruction cache 204 or main memory. It is noted that in such situations, results of instructions in the original program sequence which occur after the mispredicted branch instruction are discarded, including those which were speculatively executed and temporarily stored in load/store unit 222 and reorder buffer 216. Exemplary configurations of suitable branch prediction mechanisms are well known.

Results produced by functional units 212 are sent to the reorder buffer 216 if a register value is being updated, and to the load/store unit 222 if the contents of a memory location is changed. If the result is to be stored in a register, the reorder buffer 216 stores the result in the location reserved for the value of the register when the instruction was decoded. As stated previously, results are also broadcast to reservation station units 210A-210F where pending instructions may be waiting for the results of previous instruction executions to obtain the required operand values.

Generally speaking, load/store unit 222 provides an interface between functional units 212A-212F and data cache 224. In one embodiment, load/store unit 222 is configured with a load/store buffer with eight storage locations for data and address information for pending loads or stores. Decode units 208 arbitrate for access to the load/store unit 222. When the buffer is full, a decode unit must wait until the load/store unit 222 has room for the pending load or store request information. The load/store unit 222 also performs dependency checking for load instructions against pending store instructions to ensure that data coherency is maintained.

Data cache 224 is a high speed cache memory provided to temporarily store data being transferred between load/store unit 222 and the main memory subsystem. In one embodiment, data cache 224 has a capacity of storing up to eight kilobytes of data. It is understood that data cache 224 may be implemented in a variety of specific memory configurations, including a set associative configuration.

Turning now to FIG. 2, several elements of one embodiment of a data address prediction structure are shown. Branch prediction unit 220 is included, along with load/store unit 222 and data cache 224. Branch prediction unit 220 is connected to a data prediction bus 253 which is coupled to an arbitration multiplexor 254. Also coupled to arbitration multiplexor 254 is a second request bus 255 and an arbitration select line 256. In this embodiment, signals on both second request bus 255 and arbitration select line 256 originate in load/store unit 222. The output bus of arbitration multiplexor 254 is coupled to an input port of data cache 224. A first request bus 257 is coupled between load/store unit 222 and an input port of data cache 224. Data cache 224 is configured with two output ports which are coupled to a first reply bus 258 and a second reply bus 259. Both first reply bus 258 and second reply bus 259 are coupled to load/store unit 222, and second reply bus 259 is coupled to reservation stations 210 (shown in FIG. 1).

Generally speaking, branch prediction unit 220 produces a data prediction address on data prediction bus 253 during a clock cycle. The data prediction address is a prediction of the data addresses that are used by instructions being fetched during the clock cycle, and is generated from a stored set of addresses and associated stride values as will be detailed below.

During clock cycles in which the data prediction address is selected by arbitration multiplexor 254, the data prediction address accesses data cache 224. The data bytes associated with the data prediction address are transferred on second reply bus 259 to reservation stations 210 if the data prediction address is a hit in data cache 224. Reservation stations 210 store the data bytes along with the data prediction address and the associated instructions provided by decode units 208. Reservation stations 210, in a later clock cycle, direct the corresponding functional units 212 to generate a linear address if one or more of the associated instructions have an implicit memory read operation. If the linear address matches the data prediction address, then the data stored in the respective reservation station 210 is used as the operand for the instruction. Load/store unit 222 is informed by the corresponding reservation station 210A-210F that the associated implicit memory read operation need not be performed. Load/store unit 222 thereby discards the implicit memory read operation transferred by decode units 208 when the associated instruction was decoded. Therefore, the implicit memory read associated with an instruction may be performed before the instruction enters a functional unit 212. The latency of data cache 224 is endured prior to the instruction reaching the reservation station. Performance may be advantageously increased by allowing subsequent instructions to more quickly enter reservation stations 210 during clock cycles in which the associated instruction would have occupied reservation stations 210 due to the latency of data cache 224.

In another embodiment, load/store unit 222 stores data associated with data prediction addresses. When a functional unit 212 computes a linear address and it matches data stored by load/store unit 222, then load/store unit 222 conveys the stored data to the respective reservation station 210 without accessing data cache 224. Advantageously, data is provided for a load memory access without enduring the latency associated with data cache 224.

When a data prediction address misprediction is detected (as described below with respect to FIGS. 3A and 3B), the instruction address associated with the data prediction address and the correct data prediction address are conveyed to branch prediction unit 220. Branch prediction unit 220 stores the correct prediction address for use in a subsequent prediction.

The data prediction address is conveyed on data prediction bus 253 to arbitration multiplexor 254, which arbitrates between the data prediction address and a second request from load/store unit 222. The term arbitration, as used herein, means the selection of one request over another according to an arbitration scheme. In one embodiment, the arbitration scheme is a priority scheme in which a load/store request conveyed on second request bus 255 is a higher priority that the data prediction address request. Therefore, the arbitration select signal conveyed on arbitration select line 256 is an indication that a load/store request is being conveyed on second request bus 255. If a valid load/store request is being made during a clock cycle, arbitration multiplexor 254 selects the load/store request to be conveyed to data cache 224. If no valid load/store request is being made during a clock cycle, arbitration multiplexor 254 selects the data prediction address to be conveyed to data cache 224.

In one embodiment, load/store unit 222 is configured to make up to two requests to data cache 224 during a clock cycle. During clock cycles in which load/store unit 222 is making one request, first request bus 257 is used to allow the data prediction address the maximum opportunity to access data cache 224. If a data prediction address request is valid during a clock cycle in which load/store unit 222 is making no requests or one request to data cache 224, then the data prediction address request will be given access to data cache 224. Load/store unit 222 receives the data bytes associated with requests on first request bus 257 and second request bus 255 on first reply bus 258 and second reply bus 259, respectively. It is noted that other embodiments of load/store unit 222 may have different numbers of request buses for data cache 224.

Turning now to FIG. 3A, an embodiment of branch prediction unit 220 is shown. The data prediction information is stored within a prediction array 270. In this embodiment, prediction array 270 is a linear array of storage locations. The current fetch address (conveyed from instruction cache 204) is used to index into prediction array 270 and select a storage location. Stored within the selected storage location is a base address, a stride value, and a data prediction counter. The base address is a data address generated by an instruction, wherein the address indicative of the memory location storing the instruction indexes to the selected storage location. The stride value is the difference between two addresses generated by the instruction on two consecutive executions of the instruction. The stride value is a signed value allowing both positive and negative strides to be stored. The data prediction counter is configured to indicate the validity of the base address and the stride value. Furthermore, the data prediction counter may store values indicating that a number of previous data prediction addresses were correct predictions. A comparable number of consecutive mispredictions must then be detected before the stride value is changed. Generally speaking, the data prediction counter value may be incremented and decremented but does not decrement below zero nor increment above the largest value that may be represented by the data prediction counter. Instead, if the data prediction counter contains zero and is decremented, it remains zero. If the data prediction counter contains the largest value that it may represent and is incremented, it remains at the largest value that it may represent. The data prediction counter is therefore a saturating counter.

An adder circuit 271 is coupled to the output port of prediction array 270. Adder circuit 271 is configured to add the stride value stored within the selected storage location to the base address stored within the selected storage location, creating a data prediction address. The data prediction address is conveyed on data prediction bus 253, along with the associated data prediction counter value. In one embodiment, if the stride value is invalid (as indicated by the data prediction counter value), then the base address is added to zero.

In one embodiment, branch prediction unit 220 receives four sets of inputs from reservation stations 210. First, branch prediction unit 220 receives a plurality of linear address buses 261 which convey the actual data addresses (referred to below as linear addresses) generated by functional units 212 as well as a valid indicator for each address indicating the validity of the address. If a reservation station 210A-210F detects a mispredicted data prediction address, the associated one of linear address buses 261 will convey the corrected addresses (as will be explained below with respect to FIG. 3B). Each reservation station 210A-210F also provides one of a plurality of mispredicted lines 273 indicating whether or not the linear address conveyed on the associated one of linear address buses 261 matches the data prediction address provided with the associated instruction. Additionally, branch prediction unit 220 receives a plurality of instruction address buses 274 from reservation stations 210 conveying instruction addresses associated with the linear addresses received on linear address buses 261. The instruction address is used to index into prediction array 270 in order to store the updated base address, stride value, and data prediction counter value. Finally, prediction address buses 276 are received by branch prediction unit 220. Prediction address buses 276 convey the data prediction address received by each reservation station 210A-210F along with the associated data prediction counter value. Linear address buses 261, mispredicted lines 273, instruction address buses 274 and prediction address buses 276 are received by a prediction validation and correction block 275 within branch prediction unit 220.

If one of mispredicted lines 273 signals an incorrect data address prediction and the corresponding address valid indicator from the associated one of linear address buses 261 indicates the linear address is valid, then a data address misprediction has occurred. Prediction validation and correction block 275 causes the corresponding linear address to be stored as the base address in prediction array 270 in the storage location indexed by the corresponding instruction address. The associated data prediction counter value is decremented for this case and stored as the data prediction counter in the indexed storage location. In this manner, a data prediction address is corrected if predicted incorrectly. Additionally, a base address is created if a valid base address was not previously stored in prediction array 270 as indicated by the associated data prediction counter. A particular one of mispredicted lines 273 indicates a misprediction if the data prediction address associated with the instruction currently being validated is invalid. Therefore, the address provided on the associated one of linear address buses 261 is stored as the base address.

If a particular one of mispredicted lines 273 signals a correct prediction and the corresponding address valid indicator conveyed on the corresponding one of linear address buses 261 is indicative of a valid linear address, then the data prediction address is correctly predicted. Prediction validation and correction block 275 causes the corresponding linear address to be stored as the base address within prediction array 270 in the storage location indexed by the corresponding branch instruction address. The corresponding data prediction counter value is incremented and stored as the data prediction counter in the indexed storage location.

If the address valid indicator of a particular one of linear address buses 261 is not indicative of a valid linear address, then no prediction validation information is conveyed with respect to the instructions stored by the corresponding reservation station.

In either the misprediction case or correct prediction case detailed above, another check is performed. If the current data prediction counter value (i.e. prior to incrementing or decrementing) indicates that the stride value is invalid but the base address is valid, a new stride value is calculated by prediction validation and correction block 275. The new stride value is the difference between the prediction value conveyed on the associated one of prediction address buses 276 and the linear address conveyed on the associated one of linear address buses 261. The new stride value is stored as the stride value in the indexed storage location within prediction array 270. If the stride value is invalid (as indicated by the data prediction counter) then the data prediction counter is incremented regardless of the misprediction/prediction status of the current data address prediction.

For mispredicted lines and address valid indicators in a given clock cycle, reservation station 210A's outputs are given highest priority, then reservation station 210B's outputs, etc. In other words, if reservation station 210A is conveying prediction validation information during a clock cycle (as indicated by the associated address valid indicator), then reservation station 210A's information is processed by prediction validation and correction block 275. If reservation station 210A is not conveying prediction validation information during a clock cycle and reservation station 210B is conveying prediction validation information, then reservation station 210B's information is processed, etc. Prediction validation and correction block 275 is coupled to a dedicated write port into prediction array 270 to perform its updates, in one embodiment.

Because the prediction is formed by adding a formerly generated data address and a stride value generated from the difference between two consecutive generations of the data address, the prediction address advantageously predicts the next address correctly for at least two types of data access patterns. First, if an instruction accesses the same address each time it executes, then the stride value will be zero and the data prediction address associated with that instruction will be the same each time the instruction executes. Therefore, the current data prediction structure will correctly predict static data addresses. Additionally, instructions which access a regular pattern of data addresses such that the data address accessed on consecutive executions of the instruction differ by a fixed amount may receive correct address predictions from the present data prediction structure. Static data prediction structures (which store the previously generated data address without a stride value) do not predict these types of instruction sequences correctly. Therefore, the present prediction structure may correctly predict a larger percentage of data addresses than static data prediction structures.

Turning now to FIG. 3B, an embodiment of reservation station 210A is depicted. One storage entry is shown in FIG. 3B, but reservation station 210A is configured with several storage entries for storing decoded instructions and related data. Other storage entries within reservation station 210A are configured similar to the storage entry shown. Additionally, reservation stations 210B-210F are configured similar to reservation station 210A. The logic circuits shown in FIG. 3B are exemplary circuits for implementing the data prediction structure. Other circuits (not shown) select instructions for execution by functional units 212.

The reservation station storage entry shown in FIG. 3B includes storage for the decoded instruction and related information. A decoded instruction register 300 stores a decoded instruction conveyed from decode unit 208A on an input instruction bus 303. The input operands are stored in a pair of registers: AOP register 301 and BOP register 302. AOP register 301 and BOP register 302 receive their respective values either from a pair of data forwarding buses 304 and 305 from functional units 212 through operand steering logic (not shown), or from a predicted data register 306. The selection of data to store within AOP register 301 and BOP register 302 is performed by multiplexors 307 and 308, respectively, under the control of a reservation station control unit 309. AOP register 301 and BOP register 302 are each configured with a valid bit indicative of whether or not a value has been provided for the corresponding operand. When both operands are valid, the explicit operation of the associated instruction may be executed by functional unit 212A.

Predicted data register 306 is coupled to second reply bus 259. During a clock cycle in which a decoded instruction is first stored into decoded instruction register 300, data from second reply bus 259 is stored into predicted data register 306, along with an indication of whether or not the address associated with the data is the data prediction address and whether or not the address was a hit in data cache 224. During this clock cycle, the address used to fetch the instruction from instruction cache 204 is stored into instruction address register 310. Additionally, the associated data prediction address and data prediction counter value generated by branch prediction unit 220 are stored into a predicted address register 311. Predicted address register 311 is configured with a validation done bit (represented in FIG. 3B by the D field of predicted address register 311). The validation done bit is used to ensure that a particular predicted address is validated only once by reservation station 210A and conveyed to branch prediction unit 220. The validation done bit is initially cleared by reservation station control unit 309 and subsequently set as described below. Finally, the storage entry includes a linear address register 312 for storing a linear address generated for the decoded instruction by functional unit 212A. Additionally, a valid bit is stored in linear address register 312 to indicate the validity of the linear address.

Reservation station control unit 309 is configured to control the storing of data into the various registers within each reservation station storage location. A decoded instruction is conveyed to the storage location and stored in decoded instruction register 300. During the same clock cycle, predicted data register 306 receives data from data cache 224 and instruction address register 310 and predicted address register 311 receive values routed through decode unit 208A from branch prediction unit 220. Additionally, AOP register 301 and BOP register 302 may receive operand values from data forwarding buses 304 and 305. The decoded instruction occupies the storage entry within reservation station 210A until the explicit operation of the instruction is executed by functional unit 212A.

If the decoded instruction utilizes an implicit memory read operation to retrieve one of its operands, reservation station control unit 309 causes functional unit 212A to generate a linear address for the implicit memory read from the appropriate address values (not shown). The linear address is conveyed to load/store unit 222 for use in performing the implicit memory read if the data prediction address is incorrect, and is additionally stored into linear address register 312. Reservation station control unit 309 causes the valid bit in linear address register 312 to be set. During a subsequent clock cycle, a comparator circuit 313 compares the generated linear address to the data prediction address stored in predicted address register 311. Comparator circuit 313 is configured to indicate a mismatch if the data prediction counter value stored in predicted address register 311 indicates that the data prediction address is invalid (i.e. the associated storage location within prediction array 270 is not currently storing a valid base address).

Comparator circuit 313 conveys its output signal indicative of a match or mismatch between the data prediction address and the linear address to a multiplexor 314. Additionally, the value stored in instruction address register 310 is conveyed to a multiplexor 315; the value stored in predicted address register 311 is conveyed to a multiplexor 316; and the value stored in linear address register 312 is conveyed to a multiplexor 317. Multiplexors 314, 315, 316, and 317 are controlled by reservation station control unit 309 and receive similar values from other reservation station storage entries (not shown). During a clock cycle in which the valid bit within linear address register 312 is set and the validation done bit within predicted address register 311 is clear, reservation station control unit 309 selects the values stored in the associated storage entry through multiplexors 314, 315, 316, and 317 and sets the validation done bit in predicted address register 311. Multiplexor 314 is configured to convey a value on mispredicted line 273A, which is one of the plurality of mispredicted lines 273 shown in FIG. 3B. Similarly, multiplexor 315 is configured to convey a value on instruction address bus 274A, which is one of the plurality of instruction address buses 274 shown in FIG. 3B. Multiplexor 316 is configured to convey the value stored in predicted address register 311 on prediction address bus 276A, which is one of plurality of prediction address buses 276. Finally, multiplexor 317 is configured to convey the value stored in linear address register 312 (including the valid bit, which forms the address valid indicator described above) on linear address bus 261A, which is one of plurality of linear address buses 261. In this manner, the values used by prediction validation and correction block 275 of branch prediction unit 220 (shown in FIG. 3A) receive the appropriate values to validate and correct the data address prediction generated for the instruction stored in decoded instruction register 300.

During the clock cycle that the values associated with the instruction in decoded instruction register 300 are conveyed to branch prediction unit 220, reservation station control unit 309 sets the validation done bit in predicted address register 311. Since the validation done bit must be clear for validation values to be conveyed by the reservation station storage entry, the validation in branch prediction unit 220 is performed once for a particular instruction. If the linear address and data prediction address are found to match and the data stored in predicted data register 306 is associated with the data prediction address, reservation station control unit 309 causes the data stored in predicted data register 306 to be stored into either AOP register 301 or BOP register 302. AOP register 301 or BOP register 302 are chosen according to which operand is intended to receive the result of the implicit memory read operation. If the linear address and data prediction address do not match, the implicit memory read operation is performed by load/store unit 222 in a subsequent clock cycle. If the predicted data is transferred to AOP register 301 or BOP register 302, then reservation station control unit 309 conveys an indication to load/store unit 222 that the associated implicit memory read operation need not be performed. Load/store unit 222 thereby discards the implicit memory read operation (as noted above).

If none of the reservation station storage entries within reservation station 210A are in condition to convey prediction validation information during a clock cycle, reservation station control unit 309 causes the address valid indicator on linear address bus 261A to convey an invalid address indication. Therefore, branch prediction unit 220 will ignore the values conveyed on linear address bus 261A, prediction address bus 276A, instruction address bus 274A, and mispredicted line 273A during this clock cycle. Reservation stations 210B-210F thereby may update data prediction values during this clock cycle.

Turning now to FIG. 4, a diagram of the fields within a storage location 400 of prediction array 270 is shown. A field of information stored in storage location 400 of prediction array 270 is the base address field 401. The base address is stored in this field. In one embodiment, base address field 401 is 32 bits wide. Associated with the base address is a stride value stored in stride value field 402. In one embodiment stride value field 401 is 10 bits wide. The base address and stride value are added to form the data prediction address.

Finally, data prediction counter field 403 is included in storage location 400. The data prediction counter is stored in this field. In one embodiment, the data prediction counter is two bits. A binary value of 00 for the data prediction counter indicates that neither the base address field 401 nor the stride value field 402 contain valid values. A binary value of 01 indicates that base address field 401 is valid but stride value field 402 does not contain a valid value. The base address field is added to zero for this encoding, and the stride value is updated when the linear address is generated by one of decode units 208. A binary value of 10 or 11 indicates that both base address field 401 and stride value field 402 are valid. Having two values with the same indication allows for a stride value to be maintained until two consecutive mispredictions are detected for basic blocks which index storage location 400. In this way, prediction accuracy is maintained for the case where a basic block is intermittently executed between multiple executions of a second basic block and the two basic blocks index the same storage location 400. Other embodiments may implement more or less bits for the data prediction counter value.

In another embodiment of the data address prediction structure, data prediction address bus 253 is connected to an additional read port on data cache 224. In this embodiment, arbitration multiplexor 254 may be eliminated. It is noted that, although the preceding discussion described an embodiment of the data prediction structure within a processor implementing the x86 architecture, any microprocessor architecture could benefit from the data prediction structure.

Turning next to FIGS. 5-66, details regarding various aspects of another embodiment of a superscalar microprocessor are next considered. FIG. 5 is a block diagram of a processor 500 including an instruction cache 502 coupled to a prefetch/predecode unit 504, to a branch prediction unit 506, and to an instruction alignment unit 508. A set 510 of decode units is further coupled to instruction alignment unit 508, and a set 512 of reservation station/functional units is coupled to a load/store unit 514 and to a reorder buffer 516. A register file unit 518 is finally shown coupled to reorder buffer 516, and a data cache 522 is shown coupled to load/store unit 514.

Processor 500 limits the addressing mechanism used in the x86 to achieve both regular simple form of addressing as well as high clock frequency execution. It also targets 32-bit O/S and applications. Specifically, 32-bit flat addressing is employed where all the segment registers are mapped to all 4 GB of physical memory. the starting address being 0000-0000 hex and their limit address being FFFF hex. The setting of this condition will be detected within processor 500 as one of the conditions to allow the collection of accelerated data paths and instructions to be enabled. The absence of this condition of 32-bit flat addressing will cause a serialization condition on instruction issue and a trapping to MROM space.

Another method to ensure that a relatively high clock frequency may be accommodated is to limit the number of memory address calculation schemes to those that are simple to decode and can be decoded within a few bytes. We are also interested in supporting addressing that fits into our other goals, i.e., regular instruction decoding.

As a result, the x86 instruction types that are supported for load/store operations are:

The block diagram of FIG. 6 shows the pipeline for calculating addressing within processor 500. It is noted that base +8/32 bit displacement takes 1 cycle, where using an index register takes 1 more cycle of delay in calculating the address. More complicated addressing than these requires invoking an MROM routine to execute.

An exemplary listing of the instruction sub-set supported by processor 500 as fast path instructions is provided below. All other x86 instructions will be executed as micro-ROM sequences of fast path instructions or extensions to fast path instructions.

The standard x86 instruction set is very limited in the number of registers it provides. Most RISC processors have 32 or greater general purpose registers, and many important variables can be held during and across procedures or processes during normal execution of routines. Because there are so few registers in the x86 architecture and most are not general purpose, a large percentage of operations are moves to and from memory. RISC architectures also incorporate 3 operand addressing to prevent moves from occurring of register values that are desired to be saved instead of overwritten.

The x86 instruction set uses a set of registers that can trace its history back to the 8080. Consequently there are few registers, many side effects, and sub-registers within registers. This is because when moving to 16-bit, or 32-bit operands, mode bits were added and the lengths of the registers were extended instead of expanding the size of the register file. Modem compiler technology can make use of large register sets and have a much smaller percentage of loads and stores. The effect of these same compilers is to have a much larger percentage of loads and stores when compiling to the x86. The actual x86 registers are often relegated to temporary registers for a few clock cycles while the real operation destinations are in memory.

FIG. 7 shows a programmer's view of the x86 register file. One notes from this organization that there are only 8 registers and few are general purpose. The first four registers, EAX, EDX, ECX, and EBX, have operand sizes of 8, 16, or 32-bits depending on the mode of the processor or instruction. The final 4 registers were added with the 8086 and extended with the 386. Because there are so few real registers, they tend to act as holding positions for the passing of variables to and from memory.

The important thing to note is that when executing x86 instructions, one must be able to efficiently handle 8, 16, and 32-bit operands. If one is trying to execute multiple x86 instructions in parallel, it is not enough to simply multi-port the register file. This is because there are too few registers and all important program variables must be held in memory on the stack or in a fixed location.

RISC designs employ regular instruction decoding along natural boundaries to achieve very high clock frequencies and also with a small number of pipeline stages even for very wide issue processors. This is possible because finding a large number of instructions and their opcodes is relatively straightforward, since they are always at fixed boundaries.

As stated previously, this is much more difficult in an x86 processor where there are variable byte instruction formats, as well as prefix bytes and SIB bytes that can effect the length and addressing/data types of the original opcode.

Processor 500 employs hardware to detect and send simple instructions to fixed issue positions, where the range of bytes that a particular issue position can use is limited. This may be compensated for by adding many issue positions that each instruction cache line can assume in parallel.

Once the instructions are aligned to a particular issue position, the net amount of hardware required to decode common instructions is not significantly greater than that of a RISC processor, allowing equivalent clock frequencies to be achieved. Processor 500 achieves high frequency, wide issue, and limited pipeline depth by limiting the instructions executed at high frequency to a sub-set of the x86 instructions under the conditions of 32-bit flat addressing.

The results of executing instructions are returned to the corresponding entry in the reorder buffer. If a store, the store is held in speculative state in front of the data cache in a store buffer, from which point it can be speculatively forwarded from. The reorder buffer then can either cancel this store or allow it to writeback to the data cache when the line is retired.

The following set of instructions probably comprise 90% of the dynamically executed code for 32-bit applications:

8/32-bit operations

move reg/reg reg/mem

arithmetic operations reg/mem reg/reg logical operations reg/reg reg/mem push

logical operations reg/reg reg/mem

push

pop

call/return

load effective address

jump cc

jump unconditional

16-bit operations

prefix/move reg/reg

prefix/move reg/mem

prefix/arithmetic operations reg/reg, reg/mem

prefix/logical operations reg/reg reg/mem

prefix/push

prefix/pop

When executing 32-bit code under flat addressing, these instructions almost always fall within 1-8 bytes in length, which is in the same rough range of the aligned, accelerated fast path instructions.

Accelerated instructions are defined as fast-path instructions between 1 and 8 bytes in length. It noted that it is possible that the start/end positions predecoded reflect multiple x86 instructions, for instance 2 or 3 pushes that are predecoded in a row may be treated as one accelerated instruction that consumes 3 bytes.

When a cache line is fetched from the instruction cache, it moves into an instruction alignment unit which looks for start bytes within narrow ranges. The instruction alignment unit uses the positions of the start bytes of the instructions to dispatch the instructions to four issue positions. Instructions are dispatched such that each issue position accepts the first valid start byte within its range along with subsequent bytes.

A multiplexer in each decoder looks for the end byte associated with each start byte, where an end byte can be no more than seven bytes away from a start byte. The mechanism to scan for a constant value in an instruction over four bytes in length may be given an extra pipeline stage due to the amount of time potentially required.

Note that instructions included in the subset of accelerated instructions, and which are over four bytes in length, always have a constant as the last 1/2/4 bytes. This constant is usually not needed until the instruction is issued to a functional unit, and therefore the determination of the constant value can be delayed in the pipeline. The exception is an instruction requiring an eight-bit displacement for an address calculation. The eight-bit displacement for stack-relative operations is always the third byte after the start byte, so this field will always be located within the same decoder as the rest of the instruction.

It is possible that a given cache line can have more instructions to issue than can be accommodated by the four entry positions contained in each line of the four issue reorder buffer. If this occurs, the four issue reorder buffer allocates a second line in the buffer as the remaining instructions are dispatched. Typically, in 32-bit application and O/S code, the average instruction length is about three bytes. The opcode is almost always the first two bytes, with the third byte being a sib byte specifying a memory address (if included), and the fourth byte being a 16-bit data prefix.

The assumption in the processor 500 alignment hardware is that if the average instruction length is three, then four dedicated issue positions and decoders assigned limited byte ranges should accommodate most instructions found within 16-byte instruction cache lines. If very dense decoding occurs (i.e., lots of one and two byte instructions), several lines are allocated in the four issue reorder buffer for the results of instructions contained in a few lines of the instruction cache. The fact that these more compact instructions are still issued in parallel and at a high clock frequency more than compensates for having some decoder positions potentially idle.

Overview of the Processor 500 Instruction Cache (Icache)

This section describes the instruction cache organization, fetching mechanism, and pre-decode information. The Processor 500 instruction cache has basic features including the ICSTORE, ICTAGV, ICNXTBLK, ICCNTL, ICALIGN, ICFPC, and ICPRED. Highlights are: the pre-decode bits per byte of instructions are 3 bits, the branch prediction increases to 2 targets, 2 different types of branch prediction techniques (bimodal and global) are implemented, the X86 instructions align to 4 fixed length RISC-type instructions, and the pre-decode logic eliminates many serializtion conditions. Processor 500 executes the X86 instructions directly with a few instructions requiring two Rops, the BYTEQ is configured for fast scanning of instructions, and instructions are aligned to 4 decode units. The pre-decode data is separate in a block called ICPDAT, instead of inside the ICSTORE. The pre-fetch buffers are added to the ICSTORE to write instructions directly into the array, and the prefixes are not modified. All branches are detected during pre-decoding. Unconditional branches are taken during pre-decoding and aligning of instructions to the decode units. A return stack is implemented for CALL/RETURN instructions. Way prediction is implemented to read the current block and fetch the next block because the tag comparison and branch prediction do not resolve until the second cycle. The scanning for 4 instructions is done from ICPDAT before selected by tag comparison. Since the pre-decode data does not include the information for the 2-Rop instructions, the instructions must be partially decoded for the 2-rop during prioritizing and aligning of instructions to decode units. The early decoding includes decoding for unconditional branches, operand addresses, flags, displacement and immediate fields of the instruction. The CMASTER takes care of the replacement algorithm for the Icache and sends the way associative along with the data to the pre-fetch buffer. This section includes signal lists, timings and implementation issues for the Icache and all sub-blocks.

The Icache size is 32K bytes with 8-way set associative. The Icache is linearly addressed. The number of pipeline stages is 9. Icache will have more than one clock cycle to read and align the instructions to the decode units. The row decoding of index address is calculated in first half of ICLK, the data, tag, pre-decode, and predicting information are read in by the end of ICLK. In the next cycle, the data are selected by the TAGHITs and latched. The pre-decode data are scanned to generate the controls to the multiplexers for aligning and sending the instructions to the decode units and MROM units. A part of the scanning logic is done in parallel with the tag comparison. The scanning and alignment of instructions takes two clock cycles. The decode units can start decoding in the second half of the third clock. The Icache includes a way-prediction which can be done in a single clock using the ICNXTBLK target. The branch prediction includes bimodal and global branch prediction which takes two clock cycles. The timing from fetching, scanning, aligning, decoding, and muxing of instructions to decode units are shown in FIG. 8.

Throughout this documentation, a discussion of the layout organization is included in each section. The array is organized into many sets, and each set has its own decoder. The decoder is in the center of the set.

Signal List

SRBB(31:0)--I/O from SRB indicates the special register address for the array or data transferring to/from the SRB.

SRB.sub.-- VAL--Input from SRB indicates a special register instruction is on the SRBB.

ICTAR.sub.-- VAL--Output to SRB indicates completion of the special register instruction, for read the data is on the SRBB.

IRESET--Global signal used to reset ICACHE block. Clears all state machines to Idle/Reset.

IDECJAMIC--Global signal from FIROB. Used to indicate that an interrupt or trap is being taken. Effect on Icache is to clear all pre-fetch or access in progress, and set all state machines to Idle/Reset.

EXCEPTION--Global input from FIROB indicates that an interrupt or trap is being taken including re-synchronization. Effect on Idecode and FUs is to clear all instructions in progress.

REQTRAP--Global input from FIROB, one cycle after EXCEPTION, indicates that the trap is initiated with new entry point or new PC is driven.

INVBHREG--Input from FIROB to invalidate the branch holding register. The branch mis-prediction is speculative, an early branch can be mis-predicted at a later time. CS32X16--Input from LSSEC indicates operand and address size from the D bit of the segment descriptor of the code segment register. If set, 32-bit, if clear, 16-bit.

SUPERV--Input from LSSEC indicates the supervisor mode or user mode of the current accessed instruction.

TR12DIC--Input from SRB indicates that all un-cached instructions must be fetched from the external memory.

SRBINVILV--Input from SRB to invalidate the Icache by clear all valid bits.

INSTRDY--Input from BIU to indicates the valid external fetched instruction is on the INSB(63:0) bus.

INSTFLT--Input from BIU to indicates the valid but faulted external fetched instruction is on the INSB(63:0) bus.

INSB(63:0)--Input from external buses for fetched instruction to the Icache.

L2.sub.-- IC.sub.-- ALIAS--Input from CMASTER indicates the instruction is in the Icache with different mapping. The CMASTER provides the way associative and new supervisor bit. The LV will be set in this case.

PFREPLCOL(2:0)--Input from CMASTER indicates the way associative for writing of the ICTAGV.

UPDFPC--Input from FIROB indicate that a new Fetch PC has been detected. This signal accompanies the FPC for the Icache to begin access the cache arrays.

FPC(31:0)--Input from FIROB as the new PC for branch correction path.

BPC(11:0)--Input from FIROB indicates the PC index and byte-pointer of the branch instruction which has been mis-predicted for updating the ICNXTBLK. This index must be compared to the array index for exact recovery of the global shift register.

BRNMISP--Input from the Branch execution of the FU indicates a branch mis-prediction. The Icache changes its state machine to access a new PC and clears all pending instructions.

BRNTAKEN--Input from FIROB indicate the status of the mis-prediction. This signal must be gated with UPDFPC.

BRNTAG(3:0)--Input from FIROB indicates the instruction byte for updating the branch prediction in the ICNXTBLK.

FPCTYP--Input for FIROB indicates the type of address that is being passed to the Icache.

HLDISP(1:0)--Output to Idecode indicates all instructions of the first (bit 0) and/or the second (bit 1) 8-byte of the current line has been dispatched to decode units.

REFRESH2--Input from Idecode indicates current line of instructions will be refreshed and not accept new instructions from Icache.

MROMEND--Input from MENG indicates completion of the MROM.

D0USEFL(4:0)

D0WRFL(4:0)--Output to FIROB indicates the type of flag uses/writes for this instruction of decode unit 0:

xx1 CF-carry flag,

x1x OF-overflow flag,

1xx SF-sign, ZF-zero, PF-parity, and AF-auxiliary carry

D1USEFL(4:0)

D1WRFL(4:0)--Output to FIROB indicates the type of flag uses/writes for this instruction of decode unit 1.

D2USEFL(4:0)

D2WRFL(4:0)--Output to FIROB indicates the type of flag uses/writes for this instruction of decode unit 2.

D3USEFL(4:0)

D3WRFL(4:0)--Output to FIROB indicates the type of flag uses/writes for this instruction of decode unit 3.

RD0PTR1(5:0)--Indicates the register address for operand 1 of decode unit 0. The MROM is responsible to send bit 5:3 for the MROM register.

RD1PTR1(5:0)--Indicates the register address for operand 1 of decode unit 1. The MROM is responsible to send bit 5:3 for the MROM register.

RD2PTR1(5:0)--Indicates the register address for operand 1 of decode unit 2. The MROM is responsible to send bit 5:3 for the MROM register.

RD3PTR1(5:0)--Indicates the register address for operand 1 of decode unit 3. The MROM is responsible to send bit 5:3 for the MROM register.

RD0PTR2(5:0)--Indicates register address for operand 2 of decode unit 0. The MROM is responsible to send bit 5:3 for the MROM register.

RD1PTR2(5:0)--Indicates register address for operand 2 of decode unit 1. The MROM is responsible to send bit 5:3 for the MROM register.

RD2PTR2(5:0)--Indicates register address for operand 2 of decode unit 2. The MROM is responsible to send bit 5:3 for the MROM register.

RD3PTR2(5:0)--Indicates register address for operand 2 of decode unit 3. The MROM is responsible to send bit 5:3 for the MROM register.

IDxDAT(1:0)--Output to indicates the data size information. 01-byte, 10-half word, 11-word, 00-not used.

ICBTAG1(3:0)--Output to Idecode indicates the position of the first target branch instruction with respect to the global shift register in case of branch mis-prediction. The branch can be taken or non-taken, branch tag must be sent with all branch instruction.

ICBTAG2(3:0)--Output to Idecode indicates the position of the second target branch instruction with respect to the global shift register in case of branch mis-prediction. The branch can be taken or non-taken, branch tag must be sent with all branch instruction.

UNJMP(3:0)--Output indicates the unconditional branch instruction needs to calculate target address.

BRNTKN(3:0)--Output indicates which decode unit has a predicted taken branch. The operand steering uses this signal to latch and send BTADDR(31:0) to the functional unit.

BRNINST(3:0)--Output indicates which decode unit has a global branch prediction. The operand steering uses this signal to latch and send ICBTAG1(3:0) and ICBTAG2(3:0) to the functional units.

CALLDEC(3:0)--Output to FIROB indicates the CALL instruction is detected, the return stack should be updated with the PC address of instruction after CALL. The information is latched for mis-predicted CALL branch.

RETDEC(3:0)--Output to FIROB indicates a RETURN instruction is detected. The information is latched for mis-predicted RETURN branch.

ICPREF(9:0)--Output to Idecode and MROM indicates the encoded prefix byte. The two most significant bits are repeat prefixes for MROM.

IC2ROP0(3:0)--Output to decode unit 0 indicates 2-rop instruction. Bit 3 indicates the first rop or second rop of the 2-rop instruction, bit 2 indicates POP instruction, bit 1 indicates the MUL instruction, and bit 0 indicates the SIB-byte instruction.

NODEST(3:0)--Output to FIROB indicates no destination for the first rop of the SIB-byte instruction.

DEPTAG(3:1)--Output to FIROB indicates forced dependency tag on the first instruction; the second rop of the SIB-byte instruction.

REFRESH2--Input from Idecode indicates current line of instructions will be refreshed and not accept new instructions from Icache.

IB1(191:0)--Output indicates the combined instruction line for dispatching to decode units.

MROMEN--Input from MENG indicates the micro-instructions is sent to Idecode instead of the Icache.

M0USEFL(4:0)

M0WRFL(4:0)--Input from MENG indicates the type of flag used/written for this micro-instruction of decode unit 0:

xx1 CF-carry flag,

x1x OF-overflow flag,

1xx SF-sign, ZF-zero, PF-parity, and AF-auxiliary carry

M1USEFL(4:0)

M1WRFL(4:0)--Input from MENG indicates the type of flag used/written for this micro-instruction of decode unit 1.

M2USEFL(4:0)

M2WRFL(4:0)--Input from MENG indicates the type of flag used/written for this micro-instruction of decode unit 2.

M3USEFL(4:0)

M3WRFL(4:0)--Input from MENG indicates the type of flag used/written for this micro-instruction of decode unit 3.

MINS0(63:0)--Input from MENG indicates the displacement and immediate field of micro-instruction being sent to decode 0.

MINS1(63:0)--Input from MENG indicates the displacement and immediate field of micro-instruction being sent to decode 1.

MINS2(63:0)--Input from MENG indicates the displacement and immediate field of micro-instruction being sent to decode 2.

MINS3(63:0)--Input from MENG indicates the displacement and immediate field of micro-instruction being sent to decode 3.

MR0OPC(7:0)--Input from MENG to decode unit 0 indicates the opcode byte.

MR1OPC(7:0)--Input from MENG to decode unit 1 indicates the opcode byte.

MR2OPC(7:0)--Input from MENG to decode unit 2 indicates the opcode byte.

MR3OPC(7:0)--Input from MENG to decode unit 3 indicates the opcode byte.

MR0EOP(2:0)--Input from MENG to decode unit 0 indicates the extended opcode field.

MR1EOP(2:0)--Input from MENG to decode unit 1 indicates the extended opcode field.

MR2EOP(2:0)--Input from MENG to decode unit 2 indicates the extended opcode field.

MR3EOP(2:0)--Input from MENG to decode unit 3 indicates the extended opcode field.

MR0SS(1:0)--Input from MENG to decode unit 0 indicates the scale factor of the SIB byte.

MR1SS(1:0)--Input from MENG to decode unit 1 indicates the scale factor of the SIB byte.

MR2SS(1:0)--Input from MENG to decode unit 2 indicates the scale factor of the SIB byte.

MR3SS(1:0)--Input from MENG to decode unit 3 indicates the scale factor of the SIB byte.

ICMROM--Output to MENG indicates the current instruction is MROM. The MROM instruction may take two cycles to read the IB, ICEND, and ICFUNC.

ENDINST--Input from ICPRED indicates that pre-decoding is completed for the current instruction. The byte position of the branch instruction is from STARTPTR. The selected instruction from IB should be sent to decode unit 0.

ICVALI(3:0)--Output to Idecode indicates valid instructions. NOOP is generated for invalid instruction.

IC0OPC(7:0)--Output to decode unit 0 indicates the opcode byte.

IC1OPC(7:0)--Output to decode unit 1 indicates the opcode byte.

IC2OPC(7:0)--Output to decode unit 2 indicates the opcode byte.

IC3OPC(7:0)--Output to decode unit 3 indicates the opcode byte.

IC0EOP(2:0)--Output to decode unit 0 indicates the extended opcode field.

IC1EOP(2:0)--Output to decode unit 1 indicates the extended opcode field.

IC2EOP(2:0)--Output to decode unit 2 indicates the extended opcode field.

IC3EOP(2:0)--Output to decode unit 3 indicates the extended opcode field.

IC0SS(1:0)--Output to decode unit 0 indicates the scale factor of the SIB byte.

IC1SS(1:0)--Output to decode unit 1 indicates the scale factor of the SIB byte.

IC2SS(1:0)--Output to decode unit 2 indicates the scale factor of the SIB byte.

IC3SS(1:0)--Output to decode unit 3 indicates the scale factor of the SIB byte.

DISPTR0(6:0)--Output to decode unit 0 indicates the displacement pointer and size.

Bits 2:0 is the pointer to the 8-byte block, bit 6:5 is the size, and bit 4:3 indicates which 8-byte block. Bit 6:5=00 indicates no displacement.

DISPTR1(6:0)--Output to decode unit 1 indicates the displacement pointer and size.

Bits 2:0 is the pointer to the 8-byte block, bit 6:5 is the size, and bit 4:3 indicates which 8-byte block. Bit 6:5=00 indicates no displacement.

DISPTR2(6:0)--Output to decode unit 2 indicates the displacement pointer and size.

Bits 2:0 is the pointer to the 8-byte block, bit 6:5 is the size, and bit 4:3 indicates which 8-byte block. Bit 6:5=00 indicates no displacement.

DISPTR3(6:0)--Output to decode unit 3 indicates the displacement pointer and size.

Bits 2:0 is the pointer to the 8-byte block, bit 6:5 is the size, and bit 4:3 indicates which 8-byte block. Bit 6:5=00 indicates no displacement.

IMMPTR0(4:0)--Output to decode unit 0 indicates the displacement pointer and size.

Bits 2:0 is the pointer to the 8-byte block, and bit 4:3 indicates which 8-byte block.

Decoding of all opcodes is needed to detect immediate field.

IMMPTR1(4:0)--Output to decode unit 1 indicates the displacement pointer and size.

Bits 2:0 is the pointer to the 8-byte block, and bit 4:3 indicates which 8-byte block.

Decoding of all opcodes is needed to detect immediate field.

IMMPTR2(4:0)--Output to decode unit 2 indicates the displacement pointer and size.

Bits 2:0 is the pointer to the 8-byte block, and bit 4:3 indicates which 8-byte block.

Decoding of all opcodes is needed to detect immediate field.

IMMPTR3(4:0)--Output to decode unit 3 indicates the displacement pointer and size.

Bits 2:0 is the pointer to the 8-byte block, and bit 4:3 indicates which 8-byte block.

Decoding of all opcodes is needed to detect immediate field.

CONSTn(2:0)--Output to decode unit n indicates the constant for add/substract to ESP of the two-dispatch position instruction.

MROMEN--Input from MENG indicates the micro-instructions is sent to Idecode instead of the Icache.

IB2(191:0)--Output to decode units indicates the current line of instructions.

ICMROM--Output to MENG indicates the current instruction is MROM. The MROM instruction may take two cycles to read the IB, ICEND, and ICFUNC.

ICPC1TAR--Output to Idecode indicates is ICPC1 a branch target of a previous instruction which is a predicted taken branch instruction.

ICPC2TAR--Output to Idecode indicates is ICPC2 a branch target of a previous instruction which is a predicted taken branch instruction.

ICPC1(31:0)--Output to Idecode indicates the current line PC of the first instruction in the 4 issued instructions to pass along with the instruction to FIROB.

ICPC2(31:0)--Output to Idecode indicates the current line PC of a second instruction which cross the 16-byte boundary or branch target in the 4 issued instructions to pass along with the instruction to FIROB.

ICPOS0(4:0)--Output to decode unit 0 indicates the PC's byte position of the next instruction. Bit 4 indicates the next instruction is on the next line.

ICPOS1(4:0)--Output to decode unit 1 indicates the PC's byte position of the next instruction. Bit 4 indicates the next instruction is on the next line.

ICPOS2(4:0)--Output to decode unit 2 indicates the PC's byte position of the next instruction. Bit 4 indicates the next instruction is on the next line.

ICPOS3(4:0)--Output to decode unit 3 indicates the PC's byte position of the next instruction. Bit 4 indicates the next instruction is on the next line.

BTAG1N(3:0)--Output indicates the position of the first target branch instruction for a new line with respect to the global shift register in case of branch mis-prediction.

BTAG2N(3:0)--Output indicates the position of the second target branch instruction for a new line with respect to the global shift register in case of branch mis-prediction.

BTAKEN1(1:0)--Output to decode units and ICFPC indicates a predicted taken branch instruction from PTAKEN, BVAL1. Bit 0 is the last line and bit 1 is new line.

BTAKEN2(1:0)--Output to decode units and ICFPC indicates a predicted taken branch instruction from PTAKEN, BVAL2. Bit 0 is the last line and bit 1 is new line.

ICERROR--Output, indicates an exception has occurred on an instruction pre-fetched, the type of exception (TLB-miss, page-fault, illegal opcode, external bus error) will also be asserted.

INSPFET--Output to BIU and CMASTER requests instruction fetching from the previous incremented address, the pre-fetch buffer in the Icache has space for a new line from external memory.

ICAD(31:0)--Output to MMU indicates a new fetch PC request to external memory.

RETPRED--Output to Idecode indicates the current prediction of the return instruction of the fetched line. The return instruction must be detected in the current line of instruction or the Icache must be re-fetched from a new line.

IC.sub.-- EXT.sub.-- RD--Output to CMASTER indicates the next line of instruction should be fetched from external regardless of aliasing. This is for pre-fetching of instruction which crosses the line boundary.

MMUPFPGFLT--Input from MMU indicates page fault for the current instruction address.

TLB.sub.-- MISS.sub.-- PF--Input from MMU indicates TLB miss for the current instruction address.

PF.sub.-- IC.sub.-- XFER--Output to CMASTER indicates the address for the current line is written into the cache, the L2 should be updated with the physical address. This is when the

ICPDAT and the valid bit is written.

BIU.sub.-- NC--Input from BIU indicates the current line should not be cached.

LS2ICNOIC--Input from LSSEC indicates no caching, pre-fetch only.

LS.sub.-- CS.sub.-- WR--Input from LSSEC indicates the CS is being updated.

L2.sub.-- IC.sub.-- INV(1:0)--Input from CMASTER to invalidate up to 2 lines in the Icache.

PF.sub.-- IDX(6:0)--Input from CMASTER indicates the array index for invalidating up to 2 lines in the Icache or for aliasing.

PF.sub.-- SNP.sub.-- COL(2:0)--Input from CMASTER indicates the way associative for invalidating up to 2 lines in the Icache or aliasing. This signal may be redundant with

PFREPLCOL(2:0).

BIT20MASK--Input from CMASTER indicates masking of bit 20 for backward compatible with 8086. The line should not be cache if outside of the page.

BSTRUN--Input from TAP indicates to start the BIST.

BSTRD--Input from TAP indicates to read the array and compare to set the result.

BSTWR--Input from TAP indicates to write the array from input registers.

BSTRST--Input from TAP indicates to reset the counter.

BSTINCR--Input from TAP indicates to increment the counter.

BSTDIN--Input from TAP indicates the test pattern to the input registers. The input can be from the TDI pin or normal burn-in patterns.

FLUSHON--Input from TAP indicates flushing register mode, the result latch should use

BSTDIN instead of the compare input for flushing the result registers.

UPDOWN--Input from TAP indicates counting up or down.

BSTSHF1--Input from TAP indicates shifting of the master latch of registers.

BSTSHF2--Input from TAP indicates shifting of the slave latch of registers.

BSTFALSE--Input from TAP indicates to invert the test pattern.

PORTSEL--Input from TAP indicates to select the second dual port.

BSTIDOUT--Output to TAP indicates the result of the data chain from the ICSTORE and ICPDAT arrays.

BSTITOUT--Output to TAP indicates the result of the data chain from the ICNXTBLK and ICTAGV arrays.

BSTAMSB--Output to TAP indicates maximum count for dual port arrays.

MAXADDR--Output to TAP indicates maximum index counter.

ATPGIN(15:14)--Input from dedicated pins for ATPG.

ATPGOUT(15:14)--Output to dedicated pins for ATPG.

ICSTORE

Processor 500 executes fast X86 instructions directly, no ROPs are needed. The pre-decode bits with each byte of instruction are 3 bits; start bit, end bit, and functional bit. All the externally fetched instructions will be latched into the Icache. This should not be a problem since the Icache is idle and waits for external instructions. Only single byte prefix of 0.times.66 and 0.times.0F is allowed for Processor 500's fast path, multiple prefixes including 0.times.67 is allowed for multi-prefix, all other prefixes will take an extra cycle in decoding or go to MROM. With these simple prefixes, the instruction bytes need not be modified. The linear valid bit is used for the whole cache-line of instructions, 16-byte. The replacement procedure is done by the CMASTER. Along with each line of instruction, the CMASTER tells the Icache which way to put in the data and tag. The start and end bits are sufficient to validate the instruction. If branching to the middle of the line or instructions wrapping to the next line, the start and end bits must be detected for each instruction or else the instruction must be pre-decoded again. The possible cases are branching to the opcode and skipping the prefix (punning of instruction) and part of the wrapping instruction is replaced in the Icache. The instructions must first pass through the pre-fetch buffers before sending to the ICPRED. The ICPRED has only one input from the IB(127:0) for both the pre-fetched or cached instructions. The pre-decode information is written into the ICPDAT as the whole line is decoded. The output IB(127:0) is merged with the previous 8-byte to form a 24-byte line for the alignment unit to select and send to 4 decode units.

Since the instruction fetching from external memory will be written directly into the Icache, the pre-fetch buffer should be built into the ICSTORE; the input/output path of the array. In this way, the data will be written into the Icache regardless of the pre-decode information or the taken branch instruction and the instructions is available to the Icache as soon as they are valid on the bus. The number of pre-fetch buffers is two, and request will be made to BIU as soon as there is space in the pre-fetch buffer for another line of instructions. The pre-fetch buffer consists of a counter and a valid bit for instructions written into the cache and a valid bit for instructions sent to the decode unit. As long as the address pointer is still in the same block, the data will be written to the array. With the pre-fetch buffer in the Icache, a dedicated bus should be used to transfer instructions directly from the pads to the Icache; this is a step to keep Processor 500 from using dynamic pre-charged buses.

ICSTORE ORGANIZATION

The ICSTORE on Processor 500 does not store the pre-decode data, as shown in FIG. 9. The ICSTORE consists of 32K bytes of instructions organized as 8 sets of 128 rows by 256 columns. The array set in this documentation has its own decoder. The decoder is in the center of the set. Each of the sets consist of 2-byte of instructions. The 8-way associative muxing from the 8 TAG-HITs is performed before the data is routed to the ICALIGN block. With this arrangement, the input/output to each set is 16-bit buses. The muxing information relating to which byte is going to which decode unit should also be decoded; this topic will be discussed in detail below in the ICALIGN block section. For optimal performance the layout of the column should be 64 RAM cells, pre-charge, 64 RAM cells, write buffer and senamp. The row decoder should be in the middle of the array to drive 128 column each way. Basically, the pre-charge and the row decoder should be crossed in the middle of the array. The self-time column is used to generate internal clock for each set of the array. Pre-charge is gated by ICLK. The instruction is valid by the end of ICLK, the data muxes by the TAG-HIT should be gated by ICLK to be valid for the second ICLK. The two-entry pre-fetch buffers are implemented inside the array with data can be written from either entry. The output IB bus is taken from either the array or the pre-fetch buffer.

The BIST for the ICSTORE array uses 128 TAEC cells for reading and writing the arrays, as discussed further below.

Signal List

ISADD(11:2)--2--Input from ICFPC indicates the address of instruction to access the array. Bits 11:5 are for the row decoder, bits 4:2 are for column select. For normal operation, bits 11:4 is used to read/write 16-byte only. For special register operation, bits 11:2 is used to read/write 4-byte.

TAGHIT(7:0)--2--Input from ICTAGV indicates which set is selected to read instructions.

ICSRD--2--Input from ICCNTL to read instruction.

ICSWR--2--Input from ICCNTL to write instructions from pre-fetch buffers into the array. This signal is asserted at starting of the pre-fetch enable and de-asserted when a pre-fetch buffer entry is valid, the instruction is written into the array and the valid bit is reset.

GETNEWL--2--Input from ICPRED indicates that pre-decoding has reached the end of the line or encountered a taken branch instruction, a new line of instructions is needed in the next cycle. The ICSTORE should send a new line onto IB bus and write into the array.

SRSRD--2--Input from ICCNTL to read instruction from the array in the next cycle.

SRSWR--2--Input from ICCNTL to write instruction to the array in the next cycle.

ICSRBB(31:0)--14--I/O from SRB indicates the special register address for the array or data transferring to/from the SRB.

SETSEL(7:0)--14--Input from ICFPC indicates which set to read, no tag compare is needed.

TAGCHK--14--Input from ICCNTL to indicates the valid set is from TAGHIT or SETSEL.

PBENAB--14--Input from ICCNTL to enable the pre-fetch buffer to latch the

INSB(31:0) bus and write into the array.

INSTRDY--13--Input from BIU to indicates the valid external fetched instruction is on the INSB(63:0) bus.

INSTFLT--13--Input from BIU to indicates the valid but faulted external fetched instruction is on the INSB(63:0) bus.

INSB(63:0)--3--Input from external buses for fetched instruction to the Icache.

IB(127:0)--1--Output to ICALIGN after the set select to align instructions to decode units.

PBFLT--15--Output to ICCNTL indicates a valid faulted line of instruction from external fetch.

PBVAL--15--Output to ICCNTL indicates a valid line of instruction from external fetch.

PBEMPTY--15--Output to ICCNTL indicates the pre-fetch buffer is empty.

PBONE--15--Output to ICCNTL indicates the pre-fetch buffer has one available entry.

PBFULL--15--Output to ICCNTL indicates the pre-fetch buffer is full.