Cycle segmented prefix circuits

[0002] This application claims the benefit of Provisional Application Serial No. 60/077,669, filed Mar. 12, 1998, and Provisional Application Serial No. 60/108,318, filed Nov. 13, 1998, both of which are incorporated herein by reference in their entireties.

[0003] This invention draws from two different areas: parallel-prefix circuits and superscalar-processor circuits. Parallel-prefix circuits have, in the past, been most often used for parallel computation in machine such as the Connection Machine CM-5 supercomputer. (See, for example, [25, 18, 16, 7, 2].) Throughout this patent, numbers enclosed in square brackets refer to the references cited in Section 4.4 below, each of which is incorporated by reference herein.

[0004] Superscalar processor circuits are used to implement processors that exploit instruction-level parallelism (ILP) using out-of order execution. Instruction-level parallelism is the parallelism that can be found in a serial instruction stream because certain of the serial chain of operations are actually independent. One strategy to exploit ILP is to execute the instructions in a different order from that specified by the original serial execution, hence “Out-of-order execution”. A mechanism for out-of-order execution was first described in [44].

[0005] The rest of this section first describes parallel-prefix circuits and then describes today's superscalar-processor circuits.

[0006] Notation

[0007] We use the following notation:

[0008] O: The “big-Oh” notation is used to indicate how fast a function grows, ignoring constant factors. Intuitively, we write “g(x) is O(f(x))” if g(x) grows no faster than f(x), for large x ignoring a constant multiplicative factor.

[0009] Ω: The “big-Omega” notation is used similarly. Intuitively, we write “g(x) is Ω(f(x))” if g(x) grows no slower than f(x), for large x ignoring a constant multiplicative factor.

[0010] Θ: The “big-Theta” notation is the intersection of big-Oh and big-Omega. g(x) is Θ(f(x)) exactly when g(x) is O(f(x)) and g(x) is Ω(f(x)). Intuitively, this means that g(x) grows at the same speed as f(x) for large x ignoring a constant multiplicative factor. See [5] for a complete and exact treatment of the O, Ω, and Θ notation.

[0011] lg I is the logarithm, base 2, of I.

[0012] log I is the logarithm of I in the natural base e.

[0013] Thus, lg I=log₂I. Note that choice of the base of a logarithm makes only a difference of a constant factor. E.g., lg I≈0.693 log I, which means that lg I is Θ(log I) and log I is Θ(lg I). In this document we generally use the log base two and we use binary trees. There may be engineering reasons to use a trees of higher degree because the base of the log changes which gives a constant-fold change in the performance. Our designs work for any base and any degree of the tree, including trees of mixed degree.

[0014] Ceiling: We write ┌x┐ (pronounced “the ceiling of x”) to be the smallest integer greater than or equal to x.

[0015] append lists: If a and b are two lists, then {a,b} is the concatenation of the two lists.

[0016] The set of integers x such that a≦x≦b is denoted by [a . . . , b].

[0017] Base numerals: When we write 0010₂the string “0010” should be interpreted as a base two number. Thus 1010₂=12₈=10₁₀=10.

[0018] 1.1 Parallel Prefix

[0019] This section contains a tutorial on parallel-prefix circuits. First we define the prefix problem, then show how to implement it to run fast. Parallel-prefix circuit design is a technique that can often convert linear-time circuits into logarithmic-time circuits. (See, for example, [5] for a discussion of log-depth parallel-prefix circuits. Segmented parallel prefix circuits are the subject of an exercise of [5], and were implemented in the CM-5 supercomputer [25, 18, 16, 7].)

[0020] The prefix problem is as follows. One is given an associative operator {circle around (×)} with an identity value, I. Given some inputs x₀, x₁, . . . , x_n−1we need to compute y₀, y₁, . . . , y_nas: y_i=x₀{circle around (×)} x₁{circle around (×)} . . . {circle around (×)}x_i−1, where y₀is defined to be the identity value for the {circle around (×)}. (For example, if {circle around (×)} is addition (and the identity for addition is 0), then y_i=Σ_j=0ⁱ⁻¹x_j.)

[0021] Sometimes one wants special initial and final values. One can formulate the prefix problem as having an initial value z that is passed to the circuit. In this case we have y_i=z{circle around (×)}x₀{circle around (×)}x₁. . . {circle around (×)}x_i−1. This can be viewed as the earlier case simply by renumbering the subscripts so that we have $x_i^{\prime }=\{\begin{array}{cc}z& \mathrm{if}i=0,\mathrm{and}\\ x_{i-1}& \mathrm{otherwise}.\end{array}$

[0022] and then performing a parallel prefix on the x′ values. Similarly, one would like to get a final output value w from the circuit which is defined to be w=z{circle around (×)}x₀{circle around (×)}x₁. . . {circle around (×)}x_n.

[0023] Again, this can be implemented by the earlier case by manipulating subscripts. We simply extend the subscript range to n+1 and compute w as y_n+1.

[0024] The natural and easy thing to do is to compute the y_i's serially. First one computes each y_i−1and uses that to compute y_ias $y_i=\{\begin{array}{cc}\mathrm{the}\mathrm{identity}\mathrm{value}& \mathrm{if}i=0,\mathrm{and}\\ y_{i-1}\otimes x_{i-1}& \mathrm{otherwise}.\end{array}$

[0025] FIG. 1 shows a circuit 10 that computes the prefix operation in linear time. Circuit 10 comprises a plurality of function generators 15, each having two inputs and one output. Each output is connected as one of the inputs to the next function generator and the other input is an x value. It is easy to see that prefix can be computed in time linear in n. It is surprising to many people that the prefix problem can be solved in time logarithmic in n by using a circuit structure known as parallel prefix. The next three sections review the parallel prefix circuit.

[0026] 1.1.1 Log-Time Parallel Prefix

[0027] Before reviewing the construction of parallel-prefix circuits in general, we present an example. FIG. 2 shows a parallel-prefix circuit 20 that takes eight inputs, x₀, x₁, . . . , x₇, and computes their prefix sums $y_i=\sum _{j=0}^{i-1}{x}_j.$

[0028] Circuit 20 comprises fourteen two-input adders 25 connected in a tree-like structure by signal wires 27 as shown. The inputs x_iare provided at the bottom of the circuit, and the outputs y_icome out the bottom, with output y_icoming out just to the left of where input x_igoes in. The identity (zero) goes in at the top and the sum of all the values (y₈) comes out at the top. The critical-path length of this circuit is logarithmic in the number of inputs. This circuit can be laid out in VLSI using an H-tree layout [23] with a resulting area of about A=O(n²b²) where b is the number of bits in the result y_n. The resulting wire delay is about O({square root over (A)}). We can further optimize the parallel-prefix sum circuit of FIG. 2. If we use a redundant representation (such as the carry-save adder as used in Wallace-tree multipliers), with a single final sum at the end, we can perform the entire parallel-prefix sum in only O(log n) gate delays as opposed to O(log²n). Furthermore, often the width of the data values is smaller at the inputs than at the outputs (for example, when the inputs x, to a sum are only one bit each, but the output is log n bits, a case which will come up later in this patent), then we can carefully size the ALUs so that they take just the right number of bits as inputs and produce the right number of bits as outputs, which will save area and power. One important special case is when the x_i's are one-bit each. The problem of summing one-bit inputs is often referred to as the enumeration problem.

[0029] In general, a parallel prefix circuit comprises a tree as shown in FIG. 3. The tree 30 comprises a plurality of treefix modules 35 at its vertices connected by signal wires 37 as shown. The x_ivalues are input at the leaves of the tree (at the bottom of the figure). The results y_iare also output at the leaves, adjacent to the corresponding x_i's. The identity value I is input at the root of the tree (at the top of the figure) and the result y₈of combining all the y_ivalues is output at the root of the tree. The signal wires may be several bits wide in order to encode the necessary information. The values along each signal wire have been labeled. We use the notation P_ijto indicate that a particular wire carries the value x_i{circle around (×)}x_i+1{circle around (×)} . . . {circle around (×)}x_j. Thus $p_{i,j}=\underset{k=i}{\overset{j}{\otimes }}{x}_k¨$

[0030] (If j<i then p_ijis the identity value.) The circuit computes y_j=p_0j−1for 0≦j≦7. (See [5] for a discussion of how to adapt the circuit of FIG. 3 to compute the special cases of w and z mentioned above.)

[0031] A treefix module 35 of FIG. 3 is shown in more detail in FIG. 4. Each treefix module has two function generators 42, 43, three inputs 44, 45, 46, and three outputs, 47, 48, 49 arranged in pairs of an input and an output. One pair connects to the circuit above, one to the lower-left and one to the lower-right. There are some integers j, k, and m, with j<k<m, such that the data coming from above will be P_0j−1, the data coming from the lower-left will be p_j,k−1and the data coming from the lower-right will be P_k,m−1. The treefix module then produces p_j,m−1which is output to above, p_0j−1which is output to lower-left and p_0,k−1which is output to lower-right. The reader can check that these are in fact the values carried on the wires of FIG. 3. The circuit to compute these values is very easy to design since

[0032] p_j,m−1=p_j,k−1{circle around (×)}p_k,m−1,

[0033] p_0,j−1=p_0,j−1,

[0034] and

[0035] p_0,k−1=p_0,j−1{circle around (×)}p_j,k−1,

[0036] Although the tree in FIG. 3 has a branching factor of two (that is, it is a binary tree), all the parallel-prefix circuits described in this patent can be implemented with an arbitrary branching factor. The choice of an appropriate branching factor depends on the parameters of a particular technology. For illustration, we will show all our circuits with a branching factor of two.

[0037] 1.1.2 Segmented Parallel Prefix

[0038] A segmented parallel-prefix circuit is also known. The segmented-prefix circuit is similar to the prefix circuit. A segmented-prefix operation comprises a collection of separate prefix operations over adjacent non-overlapping segments of the input x₀, x₁, . . . , x_n−1. The way this works is that in addition to providing inputs x_pto the prefix circuit we provide additional 1-bit inputs s_icalled the segment bits. The segment bits indicate where a new segment is about to begin. The output is $y_i=\underset{j=k_i}{\overset{i-1}{\otimes }}{x}_i,$

[0039] where k_i=max{0, max{k<i:s_k=1}}.

[0040] Thus if we have $\begin{array}{cccccccccccc}x& =& <x_0,& x_1,& x_2,& x_3,& x_4,& x_5,& x_6,& x_7,& x_8,& x_9>\\ & =& <1,& 2,& 3,& 4,& 5,& 6,& 7,& 8,& 9,& 10,>\\ s& =& <s_0,& s_1,& s_2,& s_3,& s_4,& s_5,& s_6,& s_7,& s_8,& s_9>\\ & =& <0,& 0,& 1,& 0,& 0,& 0,& 1,& 0,& 1,& 0,>\\ \mathrm{then}& & & & & & & & & & & \\ k& =& <k_{0,}& k_1,& k_2,& k_3,& k_{4,}& k_5,& k_6,& k_7,& k_8,& k_9>\\ & =& <0,& 0,& 0,& 2,& 2,& 2,& 2,& 6,& 6,& 8,>\\ \mathrm{and}& & & & & & & & & & & \\ y& =& <y_0,& y_1,& y_2,& y_3,& y_4,& y_5,& y_6,& y_7,& y_8,& y_9>\\ & =& <0,& 1,& 1+2,& 3,& 3+4,& 3+4+5,& 3+4+5+6,& 7,& 7+8,& 9,>\\ & =& <0,& 1,& 3,& 3,& 7,& 12,& 18,& 7,& 15,& 9,>\end{array}$

[0041] A linear-time segmented parallel-prefix circuit 50 is shown in FIG. 5. Circuit 50, comprises a plurality of two-input function generators 55. One input to each function generator is the output of a two-input multiplexer (MUX) 58, which output is selected by a segment bit. One input to each MUX is the identity function. The other input is the output of the preceding function generator. The other input to each function generator is an x value. This is similar to the circuit of FIG. 1 except that MUXes have been added to handle the segment bits.

[0042] The segmented parallel-prefix tree circuit has the same structure as the ordinary parallel-prefix tree, except that we modify the treefix module to compute an additional segmentation signal s_j,k−1, which is passed up the tree. The value s_j,k−1indicates if any of the segments bits are equal to one. FIG. 6 shows a segmented parallel-prefix circuit 60 with eight leaf nodes (n=8). The circuit comprises a plurality of treefix modules 65 at the vertices connected by signal wires 67 as shown. The tree uses the slightly modified treefix module 65 shown in FIG. 7. Circuit 65 comprises two function generators 72, 73, two multiplexers 75, 76 and an OR gate 78. The circuit also comprises two inputs, 81, 82 and one output 83 for the segment bits and the same three inputs 84, 85, 86 and the three outputs 87, 88, 89 as in the treefix module of FIG. 4. An OR-gate 78 computes the segmentation signal that will be passed up. Multiplexer (MUX) 75 operates so that no value will be added from above to the value from the left subtree if there is a segment bit in the left subtree. MUX 76 operates so that no value will be added from the left subtree if there is a segment bit in the right subtree.

[0043] A segmented parallel-prefix circuit can be viewed as a prefix computation on values which are pairs: <P,S> where P is the value being operated on by the original operator, and S is a segmentation bit. We have the following operator: $⟨P_i,S_i⟩\otimes \mathrm{seg}⟨P_r,S_r⟩=\{\begin{array}{cc}⟨P_r,1⟩& \mathrm{if}{S}_r=1,\\ ⟨P_i\otimes P_r,S_i⟩& \mathrm{otherwise}.\end{array}$

[0044] We can show that this operator is associative. To do this we show that

[0045] (<P_a,S_a>{circle around (×)}<P_b,S_b>){circle around (×)}<P_c,S_c>=<P_a,S_a>{circle around (×)}(<P_b,S_b>{circle around (×)}<P_c,S_c>).

[0046] Proof: If S_c=1 then $\begin{array}{c}\left(⟨P_a,S_a⟩\otimes ⟨P_b,S_b⟩\right)\otimes ⟨P_c,S_c⟩=\left(⟨P_a,S_a⟩\otimes ⟨P_b,S_b⟩\right)\otimes ⟨P_c,1⟩\\ =⟨P_c,1⟩\\ =⟨P_c,S_c⟩\end{array}$ $\mathrm{and}$ $\begin{array}{c}\left(⟨P_a,S_a⟩\otimes ⟨P_b,S_b⟩\otimes ⟨P_c,S_c⟩\right)=⟨P_a,S_a⟩\otimes \left(⟨P_b,S_b⟩\otimes ⟨P_c,1⟩\right)\\ =⟨P_a,S_a⟩\otimes ⟨P_c,1⟩\\ =⟨P_c,1⟩\\ =⟨P_c,S_c⟩\end{array}$ $\mathrm{Otherwise}$ $\begin{array}{c}\left(⟨P_a,S_a⟩\otimes ⟨P_b,S_b⟩\right)\otimes ⟨P_c,S_c⟩=\left(⟨P_a,S_a⟩\otimes ⟨P_b,S_b⟩\right)\otimes ⟨P_c,0⟩\\ =\left(⟨P_a,S_a⟩\otimes ⟨P_b,S_b⟩\right)\end{array}$ $\mathrm{and}$ $\begin{array}{c}\left(⟨P_a,S_a⟩\otimes ⟨P_b,S_b⟩\otimes ⟨P_c,S_c⟩\right)=\left(⟨P_a,S_a⟩\otimes ⟨P_b,S_b⟩\right)\otimes ⟨P_c,1⟩\\ =\left(⟨P_a,S_a⟩\otimes ⟨P_b,P_b⟩\right)\\ =⟨P_c,1⟩\\ =⟨P_c,S_c⟩\end{array}$

[0047] Thus, a segmented parallel-prefix is associative, and our tree switch circuit can be viewed as an ordinary parallel-prefix circuit with a certain associative operator. (See [5, Exercise 30-1].)

[0048] 1.1.3 Variations on Prefix Circuits

[0049] Often, the prefix is modified slightly from the formulae given above. For example, an inclusive prefix has $y_i=\underset{k=0}{\overset{i}{\otimes }}{x}_k$

[0050] instead of $y_i=\underset{k=0}{\overset{i-1}{\otimes }}{x}_k.$

[0051] An inclusive segmented prefix has $y_i=\underset{j=k_i+1}{\overset{i}{\otimes }}{x}_i,$

[0052] instead of $y_i=\underset{j=k_i}{\overset{i=1}{\otimes }}{x}_i.$

[0053] Sometimes it is useful to have a backwards prefix operation. An exclusive backwards prefix operation is $y_i=\underset{k=i+1}{\overset{N-1}{\otimes }}{x}_k.$

[0054] Similarly, an inclusive version can be made with and without segmentation.

[0055] When implementing these circuits, one must be careful to get the “fencepost” conditions right. That is, the lower and upper bounds to the summation index must be thought through carefully to avoid designed-in errors in the circuits.

[0056] Note: Sometimes prefix circuits are called “scan chains” (See, e.g., [9,27].)

[0057] 1.2 Superscalar Processors

[0058] The second background area for this invention is superscalar processors. FIGS. 8-10 show a six-stage pipeline processor 100 illustrative of how today's superscalar processors are organized. The stages, are Fetch, Rename, Analyze, Schedule, Execute, and Broadcast. An example set of three instructions is shown as they propagate through each of the stages.

[0059] The Fetch stage comprises an arithmetic logic unit (ALU) 105, a program counter 110, a multiplexer 115, and a pipeline register 120. Program counter 110 keeps track of the next instruction to be executed. The program counter's value is used as a memory address to fetch several words from an instruction cache (“I-cache” (not shown).) In this example, four instructions are fetched from the I-cache. The new program counter is computed by adding a value to the old program count. The value added depends on prediction logic (labeled “PREDICT”.) If the prediction logic predicts that there are no taken branches in the next four instructions, then the new program count is the old program count plus 4. If the prediction logic predicts that one of the instructions is a taken branch, then the predictor selects the branching instruction, and the “offset” field of the instruction is added to the old program count to get the new program count. The logic for handling absolute branches and mispredictions is not shown here. The four instructions are latched in pipeline register 120 between the Fetch and Rename stages.

[0060] The Rename stage comprises renaming logic 125 including a renaming table 130 and a pipeline register 135. The rename stage takes instructions and rewrites them to make it easier to execute them in parallel. In the example shown the instructions are

[0061] 0: R0:=R1+R2

[0062] 1: R3:=R0/R1

[0063] 2: R0:=R1/R5

[0064] Note that Instruction 2 is logically independent of Instruction 1, and they may run in parallel. Instruction 2 writes to Register R0, however, and if that write happens before Instruction 1 reads from Register R0, then the wrong value will be used by Instruction 1. This problem is referred to as a “write-after-read” hazard. To allow parallel execution of Instructions 1 and 2 without suffering from the write-after-read hazard, the renaming stage rewrites the instruction to use a different set of registers, called tags. The program is transformed into

[0065] 0: T42:=T35+T40

[0066] 1: T43:=T42/T35

[0067] 2: T44:=T35/T41

[0068] In this case we assumed that the most recent writer of Register R1 had been renamed to write to Tag T35, the most recent R2 to T40, and the most recent R5 to T41. Three new tags are allocated: T42, T43, and T44, and the registers are renamed appropriately. To facilitate this renaming a Renaming Table is used to provice a mapping from register names to tag names.

[0069] FIG. 11 shows the contents of the renaming table before and after renaming each of the three instructions mentioned above. Note that the table renames all the registers, not just the ones mentioned earlier. Thus, initially R0 is renamed to T30, and then after renaming Instruction 0, R0 is renamed to T42, and then after renaming Instruction 2, R0 is renamed to T44. Register R3 was initially renamed to T25 and was renamed to T43 after Instruction 1. The renaming for R2 was not affected by these three instructions, since none of the instructions mentioned R2 as a destination register.

[0070] The circuit for identifying free tags is not shown in FIG. 11. Such a circuit would, in this case, identify up to four unused tags. In our example we assume that the four unused tags are T42 through T45. Some systems allocate and deallocate the tags so that contiguous tags are always allocated, whereas some systems can allocate an arbitrary set of four tags.

[0071] The exact implementation of the Rename stage varies from processor to processor. Although we have shown the Rename stage renaming registers to successive tags (T42, T43, and T44), in general, there is no requirement that sequentially allocated tags have sequential numbers. Some superscalar processor implementations do have such a requirement. Others do not. Those that do not require circuitry to identify on every clock cycle up to four unused tags out of the list of unused tags. The renaming table also need not be directly addressed by the logical register number. The Digital Alpha 21264 compresses entries out of the renaming table when they are no longer needed. This means that the table requires an associative lookup, instead of a direct lookup [8].

[0072] After renaming, instructions are sent via pipeline register 135 to the Analyze Dependencies stage. This stage includes a reordering buffer 140 and a pipeline register 145. In this stage, instructions whose inputs are all available are identified as ready to run. Reordering buffer 140 keeps track of this dependency information. FIG. 9 illustrates some of the instructions stored in the reordering buffer but does not depict additional information that is ordinarily kept there. Instructions are stored in the reordering buffer in sequential order. The “Old” and “New” pointers point at the oldest and the newest instruction in the sequence, respectively. Buffer entries to the left of “Old” and to the right of “New” are not currently in use. A signal is produced for each instruction in the buffer indicating whether it is ready to run, and if so, what execution resource it needs. in FIG. 9 an arrow 143 from buffer 140 to register 145 identifies those instructions that are ready to run, and the absence of an arrow identifies those instructions not ready to run. On the arrow, the labels “Mem”, “Add”, or “Div” indicatie whether that instruction needs to access memory, an ALU capable of adding, or an ALU capable of dividing. In our example, the instruction at buffer entry 38 is ready to add, the one at entry 41 is ready to access memory, the one at entry 42 is ready to add, and the one at entry 44 is ready to divide. This information is stored in pipeline register 145 between the Analyze Dependencies stage and the Schedule stage.

[0073] The Schedule stage comprises a scheduler 150 and a pipeline register 155. This stage assigns specific execution resources to the collection of instructions that are ready to run. In our example, the instructions at entries 38, 41, and 44 are assigned to particular functional units, and the instruction at entry 42 is not scheduled. Scheduler 150 obtains the actual operands from reordering buffer 140, and feeds them via pipeline register 155 to the appropriate functional units in the Execute stage.

[0074] The Execute stage comprises an ALU 160 for adding, an ALU 165 for dividing, an interface to memory (168), and a pipeline register 170. This stage executes each of the instructions provided by scheduler 150 so as to actually perform the arithmetic or memory operation. When the result is computed, it notifies the Broadcast stage 175.

[0075] The Broadcast stage takes computed results from the Execute stage and broadcasts them back to the Analyze Dependencies stage in FIG. 9. All instructions in the reordering buffer associatively listen to the broadcast. As a result of the broadcast, more instructions may become ready to execute because their dependencies have been satisfied.

[0076] Different processors reuse entries in their reordering buffer differently. Those that assign tags serially can use each assigned tag as a direct address into the reordering buffer at which to store the renamed instruction. This is the case in FIG. 9. These processors including the Alpha 21264 write values to a canonical register file by compressing the entries in the reorder buffer so that the instruction in Buffer Entry 0 is always the oldest [8]. When scaled up, the circuitry used in the 21264 for compressing the window requires large area and has long critical-path lengths, however.

[0077] When the reorder buffer fills up, some processors exhibit performance anomalies. Some processors empty the reorder buffer, instead of wrapping around, and commit all results to the register file before they start back at the beginning. Some processors wrap around, but start scheduling newer instructions instead of older ones, which can hurt performance. (See [33] for an example of a circuit that works that way.)

[0078] In some processors there is an additional decode stage after the fetch stage, but before the rename stage. This stage may interpret a complex instruction stream, translating it to a simpler instruction stream. The Intel Pentium Pro does this.

[0079] In most processors there is bypass logic to allow data to move directly from the Broadcast stage to the Execute stage, bypassing the Analyze Dependencies stage and the Schedule stage. We do not show that bypass logic here, but that logic also has long critical-path lengths and large area in today's designs.

[0080] 1.2.1 Microprocessor Performance

[0081] The standard model for modeling the performance of a microprocessor [14] says that the time to run a program is T=N·CPI·τ where

[0082] N is the number of instructions needed to run the program,

[0083] CPI is the number of clock periods per instruction, and

[0084] τ is the length of a clock period in seconds, i.e. the cycle time.

[0085] The value of τ is determined by the critical-path length through any pipeline stage, that is the longest propagation delay through any circuit measured in seconds. Propagation delay consists of delays through both gates and wires, or alternately of delays through transistors driving RC networks. We are not changing N or directly changing CPI, but rather we aim to reduce the clock cycle by redesigning the processor to use circuits with reduced critical-path length.

[0086] One way to avoid slowing down the clock is by breaking down the processor into more pipeline stages. Increasing the number of pipeline stages offers diminishing returns, however, as pipeline registers begin to take up a greater fraction of every clock cycle and as more clock cycles are needed to resolve data and control hazards. In contrast, shortening the critical path delay of the slowest pipeline stage translates directly into improved program speed as the clock period decreases and the other two parameters remain unchanged.

[0087] The critical-path delays of many of today's processor circuits do not scale well. For example, Palacharla, Jouppi, and Smith [32J find that many of the circuits in today's superscalars have asymptotic complexity Ω(I²+W²), where I is the issue width (i.e., the maximum number of instructions that are fetched in parallel from the cache) and W is the window size (i.e., the maximum number of instructions within the processor core) of the processor. While delays appear to be practically linear for today's processors, optimized for I equal to four, and W in the range of 40 to 56, the quadratic terms appear to become important for slightly larger values of I and W. (Note that for today's processors with large W the window is typically broken in half with a pipeline delay being paid elsewhere. An HP processor sets W=56 [10]. The DEC 21264 sets W=40 [8]. Those systems employ two windows, each half size, to reduce the critical-path length of the circuits. Communicating between the two halves typically requires an extra clock cycle.) Some of today's circuits have critical-path length that grows at least as fast as Ω(I⁴) and have many components with area and power consumption that grows quadratically Θ(I²). (See [30,32,1].) Increasing issue widths and increasing window sizes are threatening to explode the cycle time of the processor.

[0088] We have found that a very useful improvement to the parallel prefix circuit can be made by allowing the prefix operation to “wrap around” from the end back to the beginning. This extension is called Cyclic Segmented Parallel Prefix (CSPP.)

[0089] Further, such CSPP circuits are useful to improve the performance of many of the circuits in a superscalar processor. In some situations, it is especially advantageous to use CSPP because it avoids performance penalties in certain situations, for example, when the window fills up or wraps around. This part of the invention also contains a number of other novel circuits that can improve the performance of superscalar processors but that are not prefix circuits.

[0090] Further, it is possible to completely reorganize the processor to take advantage of CSPP to do all the scheduling and data movement. We call the resulting processor an Ultrascalar processor.

[0091] The circuits used in our invention all grow much more slowly than those of the superscalar processor, with gate delays of O(log I+log W) and wire delays of O({square root over (I)}+{square root over (W)}) for memory bandwidth comparable to today's processors. The asymptotic advantage of the Ultrascalar over today's circuits translates to perhaps an order-of-magnitude or more advantage when W is on the order of several hundreds or thousands, a design point advocated by [35].

[0092] The Ultrascalar processor, our completely reorganized architecture, breaks the scalability barrier by completely restructuring the microarchitecture of the processor. The Ultascalar turns the processor's datapath into a logarithmic depth network that efficiently passes data from producer instructions to consumer instructions within the reordering window. The network eliminates the need for separate renaming logic, wake-up logic, bypass logic, and multi-ported register files.

[0093] These and other objects, features and advantages of our invention will be more readily apparent from the following Detailed Description of our invention in which

[0094] FIG. 1 is a schematic representation of a linear-time prefix circuit of the prior art.

[0095] FIG. 2 is a schematic representation of a parallel-prefix summation circuit of the prior art.

[0096] FIG. 3 is a schematic representation of a parallel-prefix circuit of the prior art.

[0097] FIG. 4 is a schematic representation of a treefix module of the prior art.

[0098] FIG. 5 is a schematic representation of a linear-time segmented prefix circuit of the prior art.

[0099] FIG. 6 is a schematic representation of a segmented parallel prefix circuit of the prior art.

[0100] FIG. 7 is a schematic representation of a segmented treefix module of the prior art.

[0101] FIGS. 8, 9 and 10 are a schematic representation of a superscalar parallel processor of the prior art.

[0102] FIG. 11 is a schematic representation of the buffer of FIG. 9.

[0103] FIG. 12 is a schematic representation of an illustrative embodiment of a linear-time cyclic segmented prefix circuit of the present invention.

[0104] FIG. 13 is a schematic representation of an illustrative embodiment of a cyclic segmented parallel prefix (CSPP) circuit of the present invention.

[0105] FIG. 14 is a schematic representation of an H-tree layout of the CSPP circuit of the present invention.

[0106] FIG. 15 is a schematic representation of a first embodiment of a treefix module for use in the invention.

[0107] FIG. 16 is a schematic representation of a second embodiment of a treefix module for use in the invention.

[0108] FIG. 17 is a schematic representation of a preferred embodiment of a CSPP circuit of the present invention.

[0109] FIG. 18 is a schematic representation of a third embodiment of a treefix module for use in the present invention.

[0110] FIG. 19 is a schematic representation of another embodiment of a CSPP circuit of the present invention.

[0111] FIG. 20 is a schematic representation of an instruction fetch unit.

[0112] FIG. 21 is a schematic representation of an instruction fetch unit using trace cache.

[0113] FIG. 22 is a schematic representation of an instruction fetch unit using a parallel prefix.

[0114] FIG. 23 is a schematic representation of an instruction fetch unit using a parallel prefix and a network.

[0115] FIG. 24 is a schematic representation of a pointer jumping trace cache.

[0116] FIG. 25 is a schematic representation of a finite state machine.

[0117] FIG. 26 is a schematic representation of computing the 9^thstate in parallel.

[0118] FIG. 27 is a schematic representation of the composition operator.

[0119] FIG. 28 is a schematic representation of an implementation of the composition operator.

[0120] FIG. 29 is a schematic representation of partial renaming in hardware.

[0121] FIG. 30 is a schematic representation of rename logic (part 1).

[0122] FIG. 31 is a schematic representation of rename logic (part 2).

[0123] FIG. 32 is a schematic representation of quickly find the index of the first “1” bit.

[0124] FIG. 33 is a schematic representation of wake-up logic.

[0125] FIG. 34 is a schematic representation of a scalable memory system.

[0126] FIG. 35 is a schematic representation of a circuit for computing when all previous stores are completed.

[0127] FIG. 36 is a schematic representation of a datapath for memory renaming.

[0128] FIG. 37 is a schematic representation of an example of invalidating redundant entries.

[0129] FIG. 38 is a schematic representation of a circuit that invalidates redundant entries.

[0130] FIG. 39 is a schematic representation of a circuit for scheduling several kinds of resources.

[0131] FIG. 40 is a schematic representation of the data movement network.

[0132] FIG. 41 is a schematic representation of moving data.

[0133] FIG. 42 is a schematic representation of a linear-time ring datapath.

[0134] FIG. 43 is a schematic representation of how instructions specify a wiring.

[0135] FIG. 44 is a schematic representation of an overview of a linear-time datapath.

[0136] FIG. 45 is a schematic representation of an execution station for the linear-time datapath.

[0137] FIG. 46 is a schematic representation of a switching graph.

[0138] FIG. 47 is a schematic representation of a log-depth cyclic datapath.

[0139] FIG. 48 is a schematic representation of a log-depth cyclic datapath.

[0140] FIG. 49 is a schematic representation of one slice of the logarithmic-depth network.

[0141] FIG. 50 is a schematic representation of the circuitry inside each switch slice.

[0142] FIG. 51 is a schematic representation of the flip-flop-free datapath converted to an acyclic tree.

[0143] FIG. 52 is a schematic representation of the execution station for an acyclic tree datapath.

[0144] FIG. 53 is a schematic representation of the cyclic execution station.

[0145] FIG. 54 is a schematic representation of the commitment unit.

[0146] FIG. 55 is a schematic representation of the overall layout of the ultrascalar.

[0147] FIG. 56 is a schematic representation of a VLSI layout.

[0148] FIG. 57 is a schematic representation of the optimized datapath.

[0149] FIG. 58 is a schematic representation of circuitry that computes the types of values propagating up the tree.

[0150] FIG. 59 is a schematic representation of one switch of FIG. 58.

[0151] FIG. 60 is a schematic representation of the circuitry that updates the committed register file.

[0152] FIG. 61 is a schematic representation of one module of FIG. 60.

[0153] FIG. 62 is a schematic representation of the circuitry that propagates register bindings up.

[0154] FIG. 63 is a schematic representation of one module of FIG. 62.

[0155] FIG. 64 is a schematic representation of the circuitry that propagates register bindings.

[0156] FIG. 65 is a schematic representation of one module of FIG. 64.

[0157] 4.1 Cyclic Segmented Parallel Prefix

[0158] We can define a cyclic segmented prefix circuit by using modulo arithmetic for the indices of x and s. We let $y_i=\underset{j=k_i}{\overset{i-1}{\otimes }}{x}_{\left(j\mathrm{mod}n\right)},$

[0159] where

[0160] k_i=max{k any integer: k<i and s_{(k mod n)}=1}, and

[0161] i mod n=min{m≧0: (i−m) is a multiple of n.} This allows the values to “wrap around.” Thus −4 mod 10=6. Note that k_imay be negative.

[0162] Returning to our previous example, if the input to a cyclic parallel prefix is $\begin{array}{ccccccccccc}x& =⟨x_0,& x_1,& x_2,& x_3,& x_4,& x_5,& x_6,& x_7,& x_8,& x_9⟩\\ & =⟨1,& 2,& 3,& 4,& 5,& 6,& 7,& 8,& 9,& 10,⟩\\ s& =⟨s_0,& s_1,& s_2,& s_3,& s_4,& s_5,& s_6,& s_7,& s_8,& s_9⟩\\ & =⟨0,& 0,& 1,& 0,& 0,& 0,& 1,& 0,& 1,& 0,⟩\end{array}$ $\mathrm{then}$ $\begin{array}{ccccccccccc}k& =⟨k_0,& k_1,& k_2,& k_3,& k_4,& k_5,& k_6,& k_7,& k_8,& k_9⟩\\ & =⟨-2,& -2,& -2,& 2,& 2,& 2,& 2,& 6,& 6,& 8,⟩\end{array}$ $\mathrm{and}$ $\begin{array}{ccccccccccc}y& =⟨y_0,& y_1,& y_2,& y_3,& y_4,& y_5,& y_6,& y_7,& y_8,& y_9⟩\\ & =⟨9+10,& 9+10+1,& 9+10+1+2,& 3,& 3+4,& 3+4+5,& 3+4+5+6,& 7,& 7+8,& 9,⟩\\ & =⟨19,& 20,& 22,& 3,& 7,& 12,& 18,& 7,& 15,& 9,⟩\end{array}$

[0163] A linear-time cyclic segmented prefix circuit 200 is shown in FIG. 12. Circuit 200 comprises a plurality of two-input function generators 205. One input to each function generator is the output of a two-input multiplexer 210, which output is selected by a segment bit. One input to each multiplexer is the identity function. The other input is the output of the preceding function generator. The other input to each function generator is an value. Circuit 200 is similar to the linear-time prefix circuit 50 of FIG. 5 except that circuit 200 is wrapped around to be a ring.

[0164] A cyclic segmented parallel-prefix circuit can be implemented by starting with a segmented parallel prefix tree, and modifying it as follows: connect the output at the root of the tree to the input at the root, discarding the segment bit. FIG. 13 shows a cyclic segmented parallel prefix circuit (CSPP) 220 comprising a plurality of treefix modules 225 connected as shown. The individual treefix modules 225 are the same as treefix modules 65 of the segmented acyclic circuit shown in FIGS. 6 and 7. Note that the tree produces some value even if none of the segment bits are equal to one (there is no cycle in the combinational logic), but the value produced is not the indicated by the formula above.

[0165] FIG. 14 shows a CSPP circuit 230 laid out in an H-tree layout. The subtree that is drawn on the left in FIG. 13 is at the top of FIG. 14 and the subtree on the right is at the bottom of FIG. 14. FIG. 14 comprises six treefix modules 235, each including two function generator 240 and two multiplexers 245. The leaf modules also include an OR gate 250. The root node of the tree has been optimized to take advantage of the fact that at least one of the segment bits must be set to one.

[0166] 4.1.1 Variations of CSPP

[0167] Just as ordinary prefix circuits can have inclusive and/or backwards prefix operations, so also inclusive and/or backwards prefix operations can be implemented with cyclic segmented parallel-prefix circuits.

[0168] It is clear that there are many alternatives for building prefix circuits. One can build a linear-time prefix chain, or one can build a separate tree to compute each output, possibly sharing some common subexpressions, or one can build a single bidirectional tree as described here. One can vary the degree of the tree, so that instead of each node having two children, each node could have three or more children. One could vary the timing methodology. For example, in a self-timed system data traveling along the tree links would carry its own clocking information. Or one could build a globally clocked system. Other timing schemes would work as well. One could vary the technology so that the circuits are implemented in CMOS or Bi-CMOS or other logic families, and the communications links could be implemented with traces on circuit boards, or twisted pair cables, or coaxial cables, or fiber optic cables, or other technologies. Standard circuit optimization techniques can be used to improve the speed of the circuit. For example, in some technologies, NAND gates are faster than any other gate. In such technologies, the circuits using AND and OR gates could be transformed into circuits using only NAND gates. Another example is shown in FIG. 14 which shows a CSPP circuit of the AND function. In that case, the MUX is simplified to an OR gate.

[0169] 4.1.2 Examples of CSPP

[0170] This section describes a number of CSPP circuits that we use in our designs. At block-level, all the CSPP circuits that we are about to describe are identical to each other. The different CSPP circuits only differ in their implementation of the treefix modules. In the following sections, we will specify different instances of these CSPP circuits by defining the circuit's inputs and wire widths.

[0171] The first example is the “oldest” CSPP circuit. The “oldest” CSPP circuit passes to each leaf node in the CSPP tree the input value of the oldest node in its segment. This circuit is useful for passing data between producer and consumer instructions, for example. The “oldest” CSPP circuit uses the operator a{circle around (×)}b=a. FIG. 15 illustrates the circuitry inside each treefix module for an “oldest” CSPP circuit 260. The circuitry comprises first and second multiplexers 270 and an OR gate 275. The inputs to the OR gate are the segment bits from the left and right subtrees. The output of the OR gate is a segment bit that is applied to the next treefix module in the tree. The segment bit from the right subtree also controls the upper multiplexer to determine whether signals from the left subtree or the right subtree are passed to the next module. The segment bit from the left subtree controls the lower multiplexer to detect whether signals from the left subtree or the next module are passed to the right subtree.

[0172] Another very useful type of a CSPP circuit is the conjunction CSPP circuit. The conjunction CSPP circuit tells each leaf node in the CSPP tree whether all preceding leaf nodes within its segment have met a certain condition. For example, a conjunction CSPP circuit can tell each instruction within an instruction window whether all preceding instructions have computed. The conjunction CSPP circuit uses the operator a{circle around (×)}b=ab. FIG. 16 shows the circuitry inside each treefix module for a conjunction CSPP circuit 280. Circuit 280 takes a k-bit input, and performs bitwise logical AND operations on those inputs. This can be viewed as performing k independent AND operations using a single, shared, segment bit. Circuit 280 comprises first and second AND gates 285, first and second multiplexers 290 and an OR gate 295. The inputs to OR gate 295 are the segment bits from the left and right subtrees. The output of the OR gate is a segment bit that is applied to the next treefix module in the tree. The segment bit from the right subtree also controls the upper multiplexer and the segment bit from the left subtree controls the lower multiplexer. Signals from the right subtree are one input to the upper multiplexer and the logical AND of the signals from the left and right subtrees is the other input. Signals from the left subtree are one input to the lower multiplexer and the logical AND of the signals from the next module and from the left subtree is the other input.

[0173] Of course, the circuitry within each treefix module can be optimized. For example, FIG. 17 shows an optimized, 8-leaf-node conjunction CSPP 300 with input and output width of 1 (k=1). Circuit 300 comprises six treefix modules 305 each including two-input AND gates 310. One of the two inputs to each AND gate is the output of an OR gate 315. The leaf modules also include an additional OR gate 320 which ORs together the segment bits from the left and right subtrees.

[0174] A disjunction CSPP circuit indicates whether any previous node within the segment has met a certain condition. This can be implemented by inverting the x_iinputs and the y_ioutputs for the conjunction CSPP circuit, or it can be implemented directly. FIG. 18 shows an unoptimized treefix module 330 for a disjunction CSPP circuit. Of course this module can also be optimized from $f\left(a,b,s\right)=\{\begin{array}{cc}a\bigvee b& \mathrm{if}\stackrel{\_}{s}\\ b& \mathrm{otherwise},\end{array}f\left(a,b,s\right)=b\bigvee \left(a\bigwedge \stackrel{\_}{s}\right).$

[0175] Module 330 comprises first and second OR gates 335, first and second multiplexers 340, and a third OR gate 345. The inputs to OR gate 345 are the segment bits from the left and right subtrees. The output of the OR gate is a segment bit that is applied to the next higher treefix module in the tree. The segment bit from the right subtree also controls the upper multiplexer 340 and the segment bit from the left subtree controls the lower multiplexer 340. Signals from the right subtree are one input to the upper multiplexer and the logical OR of the signals from the left and right subtrees is the other input. Signals from the left subtree are one input to the lower multiplexer and the logical OR of the signals from the next module and from the left subtree is the other input.

[0176] Another important type of a CSPP circuit is the summation CSPP circuit. The summation CSPP circuit tells each leaf node the sum of the preceding leaf nodes' inputs within its segment. A summation CSPP can be used, for example, to sum up the number of requests for a resource. A straightforward implementation of a summation CSPP uses a lookahead adder for each {circle around (×)} operator. A more efficient implementation can be achieved by using carry-save adders. FIG. 19 shows one possible implementation of a treefix module 360 for a summation CSPP circuit. Module 360 comprises first and second pairs of cascaded carry-save adders (CSA) 365, first and second pairs of multiplexers 370 and an OR gate 375. The inputs to OR gate 375 are the segment bits from the left and right subtrees. The output of the OR gate is a segment bit that is applied to the next treefix module in the tree. The segment bit from the right subtree also controls the upper pair of multiplexers and the segment bit from the lower subtree controls the lower pair of multiplexers. Signals from the right subtree are one input to the upper pair of multiplexers and the other input is the output of one of the cascaded pairs of CSA. Signals from the left subtree are one input to the lower pair of multiplexers and the other input is the output of the second pair of cascaded CSAs.

[0177] This CSPP circuit represents each sum by two partial sums that add up to the sum. Each pair of CSAs reduces four partial sums to two partial sums. Each CSA takes three n bit inputs and produces two n+1 bit outputs. As partial sums propagate up the tree, they increase in size by one bit at each treefix module. (In some situations, it is known that the output requires at most n bits to represent, in which case the high order bits can be removed from the circuit. An example of such a situation is adding together 32-bit numbers modulo 2³²to get a 32-bit sum for an address calculation.)

[0178] The advantage of using CSA circuitry is that the entire summation of n numbers to produce a k-bit result can be performed with critical-path delay Θ(log n+log k) instead of Θ(log n·log k) for adders using a nonredundant representation.

[0179] 4.2 Parallel Prefix in a Conventional Superscalar Processor

[0180] This section describes a number of novel circuits that can improve the performance of traditional superscalar processors. These novel circuits can plug into a traditional superscalar processor, replacing an existing component such as the scheduler. Most of the circuits are instances of CSPP circuits.

[0181] 4.2.1 Fetch Logic

[0182] CSPP can be used to speed up the fetch stage of a conventional superscalar processor. FIG. 20 shows a typical simple fetch stage of the prior art. A fetch unit 400 provides an address to a memory 405. The memory (typically an instruction cache) responds with four instructions, labeled “data from memory.” The fetch unit then takes those instructions and provides them to a decode stage (not shown). Meanwhile the fetch unit computes a new program count (PC) based on the branch prediction rules and stores it in a PC register 410. The fetch unit also receives information about how branches actually were taken, and uses that to adjust the program count. The contents of the PC register are then used by the fetch unit to fetch the next block from memory. The problem with this system is that only one taken branch can be handled per clock cycle. As soon as the processor takes a branch, the rest of the data from the cache line is no longer needed.

[0183] FIG. 21 shows a prior art instruction fetch unit using a trace cache 420. The unit further comprises a controller 425, a memory 430 and a register 435. In this system register 435 holds the program count (PC) and the branch history (BH). The PC and BH are provided to the trace cache 420, which then fetches eight successive instructions that were executed in the past. Those eight instructions do not necessarily have to have been contiguous in memory. They are simply eight successive instructions that were once executed before when the PC and BH matched the current state. Meanwhile, controller 425 watches how the branches actually are taken, and adjusts the PC and BH. If the controller determines that the trace cache does not have the right data for a particular combination of PC and BH, then the controller fetches four instructions at a time from memory 430 to refill the trace cache. Thus, the trace cache can handle multiple taken branches per clock cycle. However, this trace cache has the problem that only one block can be fetched from memory at a time, when the trace line is being constructed.

[0184] FIG. 22 shows an instruction fetch unit that can fetch more than one block at a time. In this model, the controller produces an initial PC. A parallel-prefix summation circuit 450 computes all the subsequent PC's, and fetches the instructions I₀through I₇from a multiported memory 455. A trace cache 460 keeps track of whether the instruction is a taken branch or not. If it is an untaken branch, the next instruction will be found at PC_i−1=PC_i+1. If the branch is taken, an offset o_iis predicted, and the next instruction will be found at PC_i+1=PC_i+o_i. If parallel-prefix summation circuit 450 is an unsegmented acyclic circuit, it is set up with $x_i=\{\begin{array}{cc}1& \mathrm{if}\mathrm{instruction}\mathrm{at}{\mathrm{PC}}_i\mathrm{is}\mathrm{predicted}\mathrm{not}\mathrm{taken},\\ o_i& \mathrm{otherwise}.\end{array}$

[0185] and y_i, is the predicted value of PC_i.

[0186] By adding segmentation in circuit 450, we can handle absolute unconditional branches. We use the following: $⟨x_i,s_i⟩=\{\begin{array}{cc}⟨1,0⟩& \mathrm{if}\mathrm{the}\mathrm{instruction}\mathrm{is}\mathrm{not}a\mathrm{branch},\\ ⟨N,0⟩& \mathrm{if}\mathrm{the}\mathrm{instruction}\mathrm{is}\mathrm{an}\mathrm{unconditional}\mathrm{branch}\mathrm{to}\mathrm{offset}N.\\ ⟨N,1⟩& \mathrm{if}\mathrm{the}\mathrm{instruction}\mathrm{is}\mathrm{an}\mathrm{unconditional}\mathrm{branch}\mathrm{to}\mathrm{location}N.\end{array}$

[0187] FIG. 23 shows an instruction fetch unit similar to the one in FIG. 22 except with a scalable memory system. Summation circuit 450 and cache 460 are the same as the corresponding elements in FIG. 22. In the circuit of FIG. 23 the memory addresses are provided to an interconnection network 470 which routes the requests to various memory modules 475, and the memory modules respond with data which is routed back to the various slots of the fetch units.

[0188] There is a remaining problem with the systems of FIGS. 22 and 23. That is that for trace lines of length k, with B bits of branch-prediction history the memory requirements can grow to be Θ(k2^B) in the worst case. This is because for each instruction, and each combination of branch-prediction history there may be a unique trace cache entry of k elements. Some recent research indicates that the problem is not bad enough to make the system infeasible, however [46, 38, 34 ], at least for small values of k and B. For larger values of k and B the problem may become worse.

[0189] Another issue with this is that we cannot generally compute the address of later instructions until we have fetched previous instructions, since we won't know ahead of time if the instruction is a branch, and we may not know the branch address until even later when the instruction has computed. For conditional branches, we may not know whether the branch is taken until the previous instructions have finished executing. Unless this problem is handled, the processor may serialize often.

[0190] Today's processors cope with this problem by using speculation. The idea is to guess whether a particular instruction will be a branch, and if it is, where it branches to. If the guess is wrong, then the work must be undone. If the guess is right, then by the time the guess is verified, the processor needs only to commit its changes, and it needs not recompute them.

[0191] A series of not-taken branches can thus be handled in parallel. For not-taken branches, the instructions are stored in sequential memory locations. The instructions can be fetched in a single block, and we use a parallel-prefix circuit to quickly communicate branch-taken information. We would like the circuit to handle correctly predicted taken branches with short circuit delay, however. To solve this we need accurate prediction, we need to communicate the predictions to various components of the processors, and we need a way to use the prediction information to allow us to compute the addresses of the several different non-contiguous parts of the program, in parallel, so that we can fetch them all at once.

[0192] The system of FIG. 24 solves this problem. One advantage of this system is the memory requirements grow to be only Θ((log k)2^B) a savings of (k/log k). As a matter of practice, it is likely that the savings will be even better than the k log k factor, because fewer branch-prediction bits will be needed to achieve the same success rate, reducing the 2^Bcomponent as well. FIG. 24 comprises a trace creator 500, lg k different stages 505 of memory, and a program count register 510. Since in our example k=8, there are three stages, labeled P1, P2, and P3. Each stage is a memory that takes a PC (and a branch-prediction history, which we don't show for simplicity.) Given an address x, we write P1[x] to indicate the value of P1 at index x. We write PC_ito mean the address of the ith instruction in the predicted dynamic instruction sequence after instruction PC. Thus, PC₀=PC, PC₁is the address of the first instruction after PC, and PC₄is the address of the fourth instruction after PC. Note that if the instruction at PC_iis not a branch, then PC_i+1=PC_i+1. If the instruction at PC_iis a branch, however, then PC_i+1may be quite different from PC_i. The memory is set up so that P1[x] contains the address of the instruction predicted to follow x, that is x₁; and P2[x] contains the predicted address of the 2nd instruction after x, that is x₂; and P[4] contains the address of the 4th instruction after x, that is x₄. Now to compute PC₇, we can simply read it out of the memory stages with a logarithmic number of lookups as PC₇=P1 [P2[P4[PC]]].

[0193] Generally to compute PC_i, we write i down as a sum of distinct powers of two: i=2^a+2^b+2^cand then read Pa[Pb[Pc[PC]]].

[0194] Note that there are many ways to achieve high bandwidth and minimize contention:

[0195] Use many banks of memory.

[0196] Use Ranade's algorithm on a butterfly switch with hashing of memory address [37].

[0197] Use the Ultracomputer fetching algorithm [11]. (There is no direct relationship between the Ultracomputer and the Ultrascalar processor.)

[0198] Build a sorting network which sorts the requests by their address. After the requests are sorted, duplicates can be identified. Only a single request to any given memory is actually sent to the memory. After the request has been filled, then use a segmented parallel prefix operation to distribute the data to the duplicate requesters (see [20,21].)

[0199] To fill in a trace cache there are many options:

[0200] Use static branch prediction (initialize the table once and then change it very seldom.)

[0201] When a trace is discovered to be wrong, repair only that trace. Other traces that are affected by the incorrectly predicted branches are not necessarily repaired. (For the system of FIG. 24, repairing one trace often causes other traces to be repaired as well, but we do not necessarily need to track down every incorrect trace entry.)

[0202] For each entry Pi[j] of the table of FIG. 24 one could maintain a list of the entries in level P(i−1) that refer to Pi[j]. When we change Pi[j] we then go and fix up the entries that refer to Pi[j] and then fix the entries that refer to those entries, and so forth. This fixing up can be done by a log-depth pointer jumping as well (see the next section on pointer jumping) with the advantage that only those entries that are changed need to be examined.

[0203] Perform the pointer-jumping algorithm described below.

[0204] Pointer Jumping for Log-Time Conditional Branches

[0205] This subsection explains how to handle correctly predicted taken and untaken branches in parallel. Here is a scheme to use pointer jumping to compute the addresses fast. We explain with an example. Suppose we have the following code

[0206] 0: a=1000

[0207] 1: c=d+e

[0208] 2: e=a+1

[0209] 3: f=a+2

[0210] 4: a=a−1

[0211] 5: c=c+f

[0212] 6: e=e+1

[0213] 7: if (a>0) goto 3;

[0214] We would like to be able to compute the branch prediction very fast for large issue width (let us use I=64 for example.) (One can make this work whether I is a power of two, or not. We chose a power of two for ease of explanation.) To do this we use a technique known as pointer jumping, which has been used in parallel computing [22]. We fill in a table, with one row for each instruction address and a number of columns equal to lg I. (Think of this table as being built into the instruction cache of the processor.) Let us refer to the jth column of the ith instruction entry as T_ij. We fill in one column at a time, from left to right. We initially fill in column 0 with the next instruction prediction using a standard branch-prediction strategy. (In our example, we will predict that every instruction i (i≠7) is followed by instruction i+1. For Instruction 7 let us assume that the branch prediction hardware predicts that the branch is taken to Instruction 3. Our assumption is reasonable since a is initially very large: Most state-of-the art compilers and profilers and branch predictors would be able to tell us that this particular branch is usually taken.) Thus on Step 0 we have $T=(\begin{array}{cc}\mathrm{Instruction}& C\mathrm{olumn}0\\ & \mathrm{Successor}\\ 0\text{:}& 1\\ 1\text{:}& 2\\ 2\text{:}& 3\\ 3\text{:}& 4\\ 4\text{:}& 5\\ 5\text{:}& 6\\ 6\text{:}& 7\\ 7\text{:}& 3\end{array})$

[0215] Now we iterate for lg I steps. On step k we fill in column k by letting T_i,k=T_{(Ti,k−1),k−1}.

[0216] Thus on Step 1 we have $T=(\begin{array}{ccc}\mathrm{Instruction}& \mathrm{Column}0& \mathrm{Column}1\\ & \mathrm{Successor}& 2\mathrm{nd}\mathrm{Successor}\\ 0\text{:}& 1& 2\\ 1\text{:}& 2& 3\\ 2\text{:}& 3& 4\\ 3\text{:}& 4& 5\\ 4\text{:}& 5& 6\\ 5\text{:}& 6& 7\\ 6\text{:}& 7& 3\\ 7\text{:}& 3& 4\end{array}).$

[0217] and on Step 2 we have $T=(\begin{array}{cccc}\mathrm{Instruction}& \mathrm{Col}.0& \mathrm{Col}.1& \mathrm{Col}.2\\ & \mathrm{Succ}.& 2\mathrm{nd}\mathrm{Succ}.& 4\mathrm{th}\mathrm{Succ}.\\ 0\text{:}& 1& 2& 4\\ 1\text{:}& 2& 3& 5\\ 2\text{:}& 3& 4& 6\\ 3\text{:}& 4& 5& 7\\ 4\text{:}& 5& 6& 3\\ 5\text{:}& 6& 7& 4\\ 6\text{:}& 7& 3& 5\\ 7\text{:}& 3& 4& 6\end{array}).$

[0218] and on Step 3 we have $T=(\begin{array}{ccccc}\mathrm{Instruction}& \mathrm{Col}.0& \mathrm{Col}.1& \mathrm{Col}.2& \mathrm{Col}.3\\ & \mathrm{Succ}.& 2\mathrm{nd}\mathrm{Succ}.& 4\mathrm{th}\mathrm{Succ}.& 8\mathrm{th}\mathrm{Succ}.\\ 0\text{:}& 1& 2& 4& 3\\ 1\text{:}& 2& 3& 5& 4\\ 2\text{:}& 3& 4& 6& 5\\ 3\text{:}& 4& 5& 7& 6\\ 4\text{:}& 5& 6& 3& 7\\ 5\text{:}& 6& 7& 4& 3\\ 6\text{:}& 7& 3& 5& 4\\ 7\text{:}& 3& 4& 6& 5\end{array}).$

[0219] and on Step 4 we have $T=(\begin{array}{cccccc}\mathrm{Instruction}& \mathrm{Col}.0& \mathrm{Col}.1& \mathrm{Col}.2& \mathrm{Col}.3& \mathrm{Col}.4\\ & \mathrm{Succ}.& 2\mathrm{nd}\mathrm{Succ}.& 4\mathrm{th}\mathrm{Succ}.& 8\mathrm{th}\mathrm{Succ}.& 16\mathrm{thSucc}.\\ 0\text{:}& 1& 2& 4& 3& 6\\ 1\text{:}& 2& 3& 5& 4& 7\\ 2\text{:}& 3& 4& 6& 5& 3\\ 3\text{:}& 4& 5& 7& 6& 4\\ 4\text{:}& 5& 6& 3& 7& 5\\ 5\text{:}& 6& 7& 4& 3& 6\\ 6\text{:}& 7& 3& 5& 4& 7\\ 7\text{:}& 3& 4& 6& 5& 3\end{array}).$

[0220] and after two more steps we have $T=(\begin{array}{cccccccc}\mathrm{Instruction}& \mathrm{Successor}& & & & & & \\ & 2^0& 2^1& 2^2& 2^3& 2^4& 2^5& 2^6\\ 0\text{:}& 1& 2& 4& 3& 6& 7& 4\\ 1\text{:}& 2& 3& 5& 4& 7& 3& 5\\ 2\text{:}& 3& 4& 6& 5& 3& 4& 6\\ 3\text{:}& 4& 5& 7& 6& 4& 5& 7\\ 4\text{:}& 5& 6& 3& 7& 5& 6& 3\\ 5\text{:}& 6& 7& 4& 3& 6& 7& 4\\ 6\text{:}& 7& 3& 5& 4& 7& 3& 5\\ 7\text{:}& 3& 4& 6& 5& 3& 4& 6\end{array}).$

[0221] It takes lg I steps to compute this table, since there are lg I columns in the table.

[0222] Given Table T, we can, in lg I steps, compute the kth successor to any instruction. Suppose we want to know the instruction that is predicted to run k=37 instructions after the first instruction. We first write k down as a sum of powers of two (i.e., write k in binary): 37=2⁵+2²+2⁰.

[0223] Now we take the exponents. 5,2,0 and use them as follows: We find $v=T_{T_{T_{0,5}\mathrm{.2}},0}.$

[0224] That is we first look up Instruction 0's column 5. We find T_0.5=7. Then we look up Instruction 7's column 2. (7 comes from T_0.5and 2 is one of the exponents.) We find T_7.2=6. Next we look up Instructions 6's column 0. We find T_6.0=7. Now we know that the 37th instruction after Instruction 0 will be Instruction 7 (if the branch prediction is correct.) We could have looked up the exponents in any order. For example, T_0.2=4, T_4.0=5, T_5.5=7, which gives us 7 again.

[0225] Computing the Branch Prediction

[0226] The above assumes that the processor has a branch prediction for each relevant situation. A typical branch predictor keeps some state bits, and appends them to the current program counter to look up, in a table, whether the instruction is a taken branch. (That is, for each instruction and for each combination of some state bits, there is a prediction for the next instruction.) Most of today's branch-prediction mechanisms run in time linear in the number of branches. This subsection shows how to compute the branch prediction values faster.

[0227] Another strategy is to propagate the table from one fetch destination to another through a parallel prefix tree. In the next section, we will show how to propagate such a table when used for memory renaming.

[0228] Another way to do this is shown by this example: In one branch predictor used in current processors, there are four bits, which indicate how each of the most recent four branches were resolved in the dynamic instruction sequence. Those four bits are used to index into a table to get the prediction for the next branch. The leftmost bit is shifted out, and the new branch result is shifted in on the right. A pointer-jumping calculation can be used in this case to compute what the branch prediction bits should look like after four branches are correctly predicted. Suppose we have the following 3-bit branch prediction table

[0229] If we started with branch history 1=001₂, then we predict that the next branch is not taken, so we then get that the next branch history will be 2=010₂(shifting the zero to the right and throwing away the leftmost bit.) The next prediction is taken, so we get 5=101₂. The next one is taken, so we get 3=011₂. Thus after four instructions a branch history of 001₂becomes 011₂. To compute this in log-time we first transform the table to a table with a row indicating the next state.

[0230] Now we apply the pointer jumping algorithm to compute what will be the 2nd state after each initial state, and then the 4th state after each initial state.

[0231] And we can read the state off in logarithmic time.

[0232] One of the issues for implementing this pointer-jumping algorithm is that sometimes several fetches are made from the same memory location. There are several approaches to implement those fetches efficiently.

[0233] Build a multiported memory system. This has the disadvantage of not being scalable, but it can work well for small numbers of concurrent reads.

[0234] Serialize the fetches, effectively ignoring the problem. It may be the case that the congestion happens infrequently enough that it is not a serious performance problem.

[0235] Use a combining network, such as the one described for the Ultracomputer [11] or Ranade's algorithm [37].

[0236] Use a sorting network, followed by a prefix network, followed by a conflict-free routing network as described above.

[0237] 4.2.2 Decode Logic

[0238] This section describes a novel circuit that can compute the next n states of a finite state machine with log n gate delay. The circuit is a prefix circuit and can be used, among other things, to decode instructions. This is useful for architectures where the instruction length is not known in advance. If you have an array of bytes that encodes a variable-length instruction stream, the problem is to identify those bytes that are the first byte of an instruction. (An example of such an instruction-set would be the Intel IA-32“x86” instruction set.)

[0239] If we want to decode in linear time, we can build a finite-state machine (FSM) that can determine the first byte of each instruction by considering the bytes one at a time. Microprocessors today use such a finite state machine. The finite state machine can find the beginnings of the instructions in time that is linear in the number of bytes being analyzed.

[0240] For example, suppose that the machine language for the processor looks like this: An instruction can be a basic instruction, which is two bytes long: The first byte of a basic instruction can be any number from 2 to 255. The second byte of a basic instruction can be any number. Or an instruction can have a prefix which is the number 1 followed by a basic instruction. Or an instruction can have a prefix which is the number 0 followed by an optional 1, followed by a basic instruction.

[0241] FIG. 25 shows a finite state machine for recognizing the beginnings of these instructions. Part (a) shows the state transition diagram, and Part (b) represents the same information as a state transition table. State zero (notated with a double circle) is the inital state, and indicates the beginning of an instruction.

[0242] Suppose we are given the following byte sequence to be interpreted as instructions: 0 1 3 0 1 3 0 1.

[0243] The beginnings of the instructions will turn out to be Byte numbers 0 (the first byte), 4, and 7.

[0244] The finite state machine would determine this in linear time by stepping through the bytes one at a time:

[0245] All the lines with 0 in the leftmost column are the beginnings of instructions. We can read, for example, that the next byte will not be the first byte of an instruction, because we will be in State 2.

[0246] The rest of this section describes how we can compute the leftmost column, and so determine the beginnings of all instructions, in logarithmic time using a parallel prefix circuit. We start by outlining how to compute the nth entry in the leftmost column. FIG. 26 illustrates. It shows how to compute the 9th entry and so determine whether the 9th byte will be a start byte. The top line of the figure is the input stream. Below each input byte is a Level 0 state vector. Below each pair of Level 0 state vectors is a Level 1 state vector. Below each pair of Level 1 state vectors is a Level 2 state vector. Below each pair of Level 2 state vectors is a Level 3 state vector. The Level 0 state vectors show the final state of the finite state-machine (FSM) for each possible initial state, given the particular input. The Level 1 state vectors show the final state of the FSM for each possible initial state given the pair of input bytes above it. (For example, the entry with a $\begin{array}{c}\mathrm{box}\end{array}$

[0247] around it shows the final state of the FSM if it started in State 3, and saw the bytes 0 and then 1. It would end up in State 2.) The Level 2 state vectors show the final state for each initial state, given the four bytes above. The Level 3 vector shows the final state of the machine, given any initial state, and the 8 bytes of input. We can read that if the machine started in State 0, it ends in State 2 (since 2 is the value of the first line in the Level 3 vector (which corresponds to an initial state of 0).) Thus, the next byte, the 9th byte, will not be a starting byte.

[0248] We can implement the algorithm of FIG. 26 using a simple (one-directional) parallel-prefix circuit. We number the states in the finite-state machine. The data being passed up the tree is a vector of state numbers. If there are n states in the finite-state machine, we use a vector of n integers (each integer is [lg n ] bits.) Given such a vector x, the ith element is written x_i. The idea is that vector x will tell us for each state where we will end up after parsing a particular sequence of bytes. A machine starting in State i will end up in State x_i. The identity vector is I_i=i. The identity vector is the vector for parsing no bytes. At the i-th leaf of the tree, we input the vector that tells us for each state where we will end up after parsing the i-th input. At each node of the tree, we compose the two incoming state vectors with this associative composition operator: (x{circumflex over (x)}y)_i=Y_x. That is, the ith entry in the composition is found by taking the ith entry of x and using that as an index into y. FIG. 27 gives an example of the inputs and the output to a node. FIG. 28 shows one possible implementation of the composition operator. At the root of the tree, an additional multiplexer computes z_swhere z is the output vector of the root node and s is the initial state of the FSM before the current sequence of instruction bytes. The resulting output, z_s, indicates whether the 9th byte is not or is a starting byte.

[0249] To design a circuit that computes the next k states of a finite state machine, given the next k instruction bytes, we simply turn the above one-directional tree into a two-directional parrallel-prefix tree. The inputs to the tree and the associative operator are the same as above. The prefix tree's i-th output vector, at the i-th leaf node, specifies for each initial state where we will end up after parsing the preceding (i−1) bytes.

[0250] For the problem of instruction decoding, we can design our decoder so that the initial state at the oldest byte is always the start state. So to determine whether the i-th byte is a start byte, one simply looks at the 0-th element of the prefix tree's i-th output vector.

[0251] In the more general case, we may wish to run a finite-state machine continuously, without resetting it to its starting state at the oldest unparsed byte. This can be useful for the general problem of finite-state interpretation at high-speed, and has many applications, including network protocols, parsing regular expressions, and program compilation. For this general problem, we want to compute for each byte what state the machine is in. To do this, we build a parallel prefix circuit. The operator is the composition operator shown in FIGS. 27 and 28. At each leaf of the parallel prefix tree, an additional multiplexer computes z_swhere z is the output vector of the parallel prefix circuit at that node and s is the initial state of the FSM at the oldest byte (i.e., before the current sequence of instruction bytes). The resulting output, z_s, at each leaf indicates the byte's state. Thus, we can keep on continually decoding a stream of instruction bytes (or any other FSM input) written into a wrap-around queue by using a cyclic, segmented parallel prefix circuit. The segment bit identifies the oldest byte in the sequence. The initial state of the oldest byte in the sequence, s, x{circumflex over (x)}y=x can be broadcast to all the leaves using an additional CSPP circuit with the operator. The oldest instruction supplies its initial state as data and sets its segment bit high.

[0252] 4.2.3 Rename Logic

[0253] This section describes a novel circuit that merges a wrap-around sequence of partial tables, tables that contain updates to a subset of the table's entries. The circuit can produce all intermediate tables that reflect earlier updates applied in serial order with gate delay logarithmic in the length of the sequence. The circuit can be used as a replacement for the renaming hardware in today's logic. The renaming hardware's job is take logical register names and change them to physical register names, or tags. The renaming hardware must support the following operations: (1) Find the current tag for a logical register, (2) change the current tag for a logical register, (3) checkpoint the current mapping from logical registers to tags, and (4) restore a mapping from a checkpoint. (The checkpoint and restore are only required for speculative execution, but speculative execution is generally viewed as being indispensable in a modern processor.) Furthermore, it must be possible to perform several of these operations in parallel. The results should be the same as if the operations were performed one after another, serially. In the prior art there are two ways to implement the renaming hardware: direct-addressing, and content-addressing.

[0254] Direct Addressing Approach

[0255] In direct addressing, there is a RAM table, called T, indexed by logical register number. For a typical RISC processor, the table has 32 entries, one for each register in the instruction-set architecture. Each entry contains a tag.

[0256] To find the tag currently associated with logical register R_i, one does a fetch from the RAM table, looking up j:=T [i] to get the tag.

[0257] To change the tag for a logical register, one writes the tag to T[i]:=j.

[0258] To checkpoint, one copies the entire table T to a “shadow table”.

[0259] To restore, one copies the shadow table back to T.

[0260] Note that the number of shadow tables, if small, may limit the amount of speculative execution that can be performed. If the number of shadow tables is large, on the other hand, then it will require much VLSI area to implement. In the prior art, to handle multiple find and change operations at the same time requires a memory with multiple ports. The memory of the prior art is slow if it has too many ports [32].

[0261] Content Addressing Approach

[0262] In content addressing, there is a table U with one entry for each tag. The jth entry contains the name of the logical register that uses that tag.

[0263] The find problem for logical register i is to find the youngest entry that names i. The entries may be sorted so that the oldest entries are first (e.g., [36]), in which case the last row that names i is the correct row. Or the entries may be kept unsorted, with an additional “age” associated with each row (e.g., [27].) To find the youngest entry that names the logical register i, the logical register number, i, is broadcast to all the table entries. Each table entry has an associated comparator that compares its entry to i. For the entries that match i, then a reduction operation is performed to determine which is the oldest entry. For either approach [36, 27], no circuit is shown for actually performing the reduction, and no suggestion is made that it could be done in faster than linear time. One reference [27] does show a circuit for finding the oldest row that satisfies a certain condition.

[0264] To change the tag for a logical register, one writes a new entry into the table.

[0265] To checkpoint a tag requires noting which entries are currently valid, and which are not. For the sorted system, one just remembers where the boundary is between the unwritten entries and the written entries. For the ageing system, one just remembers the current time.

[0266] To restore, one deletes the entries that were invalid at the time of the checkpoint. For the sorted system, one simply moves the boundary. For the ageing system, one marks as deleted any entry which has an age indicating that it was created after the time of the checkpoint.

[0267] The reuse of entries within the U table introduces additional complexity. For the sorted-by-age systems in the prior art, the system must eventually “retire” renaming entries, writing their register values to a canonical register file. Also, the system must stop processing instructions when it reaches the bottom of the renaming table, and then after retiring all instructions, it can start reusing the top again. Another approach is followed by [8], which keeps the table rows sorted (oldest at the top), but compacts the table entries upward when old entries are no longer needed. Many of the circuits described in [8] are slow as the issue width increases. For example, the compacting circuit must be capable of compacting up to n holes per clock cycle. The compacting circuit's delay is at least O(n).

[0268] In addition to those problems, the prior art also has the problem that a special circuit is required to perform dependency checks and renaming between the instructions that are being renamed in the same clock cycle. If two instructions are being renamed in the same clock cycle, then the second one will not see the the first one's entry in the renaming table. Special dependency checking hardware is used to resolve this situation. Such dependency checking hardware is quadratic-time in the prior art [32].

[0269] Our Approach

[0270] We show a different implementation of renaming logic. Our implementation uses “partial renaming maps”. A partial renaming map renames only some registers, not all of them. First we explain the concept using a mathematical notation, then we show circuitry to implement partial renaming maps. Here is the notation: Suppose that we have a sequence of instructions as follows:

[0271] Here we have shown the tag that each instruction's destination register is renamed to. (For example, Register 1 is renamed to Tag 42.) The effect of the entire sequence can be written as {1→44,3→43,4→45}.

[0272] Note that we did not include the effect of the first renaming because after renaming the sequence it is no longer important. We can compose two renamings as follows: Suppose we have the renaming from the first pair as {1→42,3→43}, and the renaming of the second pair as {1→44,4→45}.

[0273] The composed renaming is {1→42,3→43}⊙{1→44,4→45}={1→44,3→43,4→45}.

[0274] The rule for composing two renamings A⊙B=C is that renaming x→y is in C if x→y is in B or (x→y is in A and there is no renaming of x in B.)

[0275] FIG. 29 shows how to implement a partial renaming in hardware. For each partial renaming, one keeps a table T of renamings, with an additional bit vector V indicating which of the table entries are valid. The top of the figure shows the hardware representation of three renamings. Renaming A (left) is combined with Renaming B (center) to get Renaming C (right). Each renaming consists of a bit vector V indicating which entries are valid, and a table T of entries. We show only the valid entries in this example. At the bottom is shown the circuit which computes a row of C given a corresponding row of A and B. Note that the rows are independent. The circuit comprises on OR gate 550 and a multiplexer 555. The inputs to the OR gate are the values of V in a given row in A and B. The inputs to the multiplexer are the values of T in the same row in A and B. The value of V from Renaming B is used to select the output of the multiplexer.

[0276] Suppose we wish to rename a large number of instructions. We start with a complete renaming, A, that corresponds to the renaming state before renaming any instruction. (A complete renaming is a partial renaming in which all the V bits are 1.) We then create a partial renaming for each of the instructions (note that each instruction typically renames only one register.) Call those partial renamings B₀, . . . B_n−1. We then would like to compute the effect, for each instruction, of all previous renamings. That is, for instruction i we would like to compute C_i=A⊙B₀⊙B₁⊙. . . ⊙B_i−1.

[0277] We can do this in linear time simply by attaching N of the partial renaming circuits of FIG. 29.

[0278] FIG. 30 and FIG. 31 describe circuitry that implements our renaming approach in logarithmic gate delay as opposed to linear gate delay. Specifically, the figures show renaming logic that renames a sequence of four instructions and uses two logical registers. The sequence of instructions wraps around, with the oldest instruction identified by its signal Oldest being high. The circuitry comprises two components. FIG. 30 shows the circuitry that computes the tags for all four instructions' partial renaming tables. FIG. 31 shows the circuitry that computes the valid bits for all four instructions' partial renaming tables. Each figure shows two CSPP circuits 570 and 580, one for each of the two logical registers. For a machine with 32 registers, 32 CSPP circuits would be needed.

[0279] In addition to its Oldest bit, each instruction sends into the circuitry a tag, TagIn, and an array of valid bits, ValidIn_i, one for each logical register. If ValidIn_jis high, then the instruction has renamed register R_jto TagIn. The circuitry returns to each instruction an array of tags, TagOut_i, and an array of valid bits, ValidOut_i, one for each logical register. If ValidOut_jis high, then TagOut_icontains the tag to which logical register R_jis currently renamed. If ValidOut_jis low, then the preceding instructions in the sequence have not renamed register R_j.

[0280] The circuitry in both FIG. 30 and FIG. 31 include CSPP circuits. FIG. 30 uses one “oldest” CSPP circuit 570 for each logical register. The “oldest” CSPP circuit is described in FIG. 15 and FIG. 13. FIG. 31 uses one disjunction CSPP circuit 580 for each logical register. The disjunction CSPP circuit is described in FIG. 18 and FIG. 13. The circuitry in FIG. 30 and FIG. 31 can be easily extended to rename more instructions or to use more logical registers. For each new logical register, we add one more CSPP circuit to each figure. For each additional instruction, we add one more leaf node to every CSPP circuit in the two figures. The oldest instruction provides a complete renaming table, providing all ValidIns to be true and all TagIns to be the respective tags from the previous instruction execution.

[0281] The advantages of this circuitry are that it runs in logarithmic time, it requires no compacting, and it keeps instructions sorted in chronological order (which can help with certain other aspects of the circuit design.) Checkpointing and restoring are straightforward, and require no additional shadow storage. To restore renamings on a misprediction, we simply label the mispredicted branch instruction to be the newest, effectively moving the pointer to the newest instruction. Furthermore, because we designed this circuit as a cyclic circuit, when we get to the bottom of the renaming table, we can simply start using entries from the top of the table without interruption. Also no special additional dependency check needs to be done, since the correct renaming happens in a single clock cycle. Also, when an instruction commits, its result tag does not need to be written to a canonical renaming table, which saves additional complexity.

[0282] Reusing Tags

[0283] Here we describe several novel circuits that, given an array of bits, compute the binary (or unary) indexes of the first N entries in the array that are high. One of the applications of these circuits can be the reuse of tags in a superscalar processor.

[0284] On every clock cycle, a superscalar processor allocates a tag to the result register of every instruction entering the rename stage. Different superscalar implementations allocate tags differently. For example, some processors assign tags in a forward or wrap-around sequence. That is, the first instruction uses Tag 0, the next uses Tag 1, until all the tags are used up, by which time some of the early tags have retired, and we go back and start using Tags 0 and 1 again. Often, the tag number is the same as the number of the reservation station. The allocation of tags in such a system is the same as the allocation of reservation stations in the reordering buffer. The disadvantage of such a scheme is that the tags and the buffer entries are allocated together, and the tags cannot be reused without clearing out the buffer entries (e.g., by writing them to a canonical register file.) Such a write has typically been performed by a multiported register file which has poor scaling properties.

[0285] In other processors, tags are allocated out of a pool of tags. One advantage of this approach is that a separate logical register file may not be necessary. The problem for this system is to allocate tags quickly. On every clock cycle, the processor must identify I tags to reuse, where I is the number of instructions to be renamed per clock cycle. In this problem, there is a collection of tags that are free, and we need to find the names of several of those. Our input is a bit vector x indicating which tags are free. x_iis one if tag i is free, and zero if tag i is not free. The problem then is to determine the indexes of the first N bits that are one in a vector of bits. Finding the indices of the first N true bits has other applications, such as ALU scheduling, as we shall see below.

[0286] To find the first bit that is one, we ask “what is the maximum i such that x_i=1?” FIG. 32 shows how to compute that maximum i. The circuit is shown for a bit vector of length 16. The bit vector comes from the top, and out of the bottom comes a signal indicating that some bit is 1 (the “free exists?” signal) along with 4 bits indicating the number of the highest-numbered one. The 16 bits of the input bit vector are applied in pairs to eight two-input OR gates 600. The outputs of the eight OR gates 600 are applied in pairs to four two-input OR gates 605. In turn, the outputs of the OR gates 605 are applied in pairs to two two-input OR gates 610 and the outputs of OR gates 610 are applied to two-input OR gate 615. Every other bit of the input bit vector is also applied to a two-input multiplexer (MUX) 620. The outputs of MUXes 620 are applied in pairs to two input MUXes 625 and the output of MUXes 625 are applied to MUX 630. The output of every other OR gate 600 is also applied in pairs to two-input MUXes 635 and the output of MUXes 635 is applied to MUX 640. The outputs of every other OR gate 605 are also applied to two-input MUX 645. The MUXes are controlled by the output of various OR gates as shown in FIG. 37. In particular, the four MUXes 620 are controlled by the output of every other one of the eight OR gates 600. MUXes 625 and 635 are controlled by the output of every other one of the four OR gates 605. And MUXes 630, 640 and 645 are controlled by one of the two OR gates 610.

[0287] The underlying structure of this circuit will be apparent. At a first stage, each four bits of the input bit vector are processed by two OR gates 600, one OR gate 605 and a MUX 620 to produce a set of three outputs. In the next stage, each set of three outputs is processed by OR gate 610 and MUXes 625 and 635 with another set of three outputs to produce a set of four outputs. And in the final state, the two sets of four outputs are processed by OR gate 615 and MUXes 630, 640, 645 to produce the five outputs of the circuit.

[0288] To find the one bit of the 8-bit system requires building two circuits to find the bitnum of 4 bits. The two subcircuits are combined with some MUXes and an OR gate. If there is a bit in the left batch of 4, the MUXes select the low order bits of the bit number from the left side, otherwise the low order bits come from the right side. It will be clear to the reader how to extend this system to handle any number N of tags with gate-delays that are only O(log N).

[0289] Prior art for this problem includes [9] and [12]. Both perform an operation similar to the circuit of FIG. 32. In both of those circuits the output is encoded in unary, where in our circuit the result is output in binary. The circuits shown here are also faster and smaller.

[0290] Another variation works as follows: We use a parallel-prefix circuit with summation (e.g., see FIG. 2). The inputs provided are the free bit vector x indicating which tags are free (encoded as a one) and which are busy (encoded as a zero.) The outputs indicate for each bit, how many bits to the left of that bit are true. This number thus provides each bit with a unique nonnegative number in a contiguous range starting at zero. Let us call the output the enumeration index. Now each bit has an address, which is its index in the set of all bits, and an enumeration index which is the index in the set of all one bits. Each one-bit then sends its own address through a butterfly switch to the destination specified by the enumeration index. It is known that every such routing is conflict free in a butterfly switch [17]. Now destination zero has received the address of the first one bit, and destination one has received the address of the second one bit and so forth. An added innovation is to use a cyclic, segmented parallel-prefix circuit, with the segment bit indicating which bit is the oldest in a circular list. The result is that destination zero gets the address of the first free bit, in the cyclic ordering starting from the oldest, and destination one gets the next free bit, and so on.

[0291] Related prior art for the above circuit includes an enumeration algorithm that was described in a software context by Christman [4]. Our system is different from [4] in the following ways: (a) Our circuits are used in hardware in a microprocessor, whereas Christman's was used in software on a parallel computer. (b) We also have a cyclic version of the rendezvous.

[0292] Our enumeration algorithm is also superior to the ones of [12, 9] in that we can find an arbitrary number of first bits. [12] can only find the first 4 of 24 stations. [9] can only find the first one or two values. Also our system provides the results in binary or unary form (the address can be sent through the switch using binary or unary formatting), instead of only unary form. Also our system provides a cyclic allocator, whereas the systems in the prior art can only allocate from “left-to-right.” The prior art machines have either (a) compacted the instructions in the window (which can be expensive in VLSI area and critical-path delay) [8], or (b) effectively drained the instruction window when it fills up (which hurts performance), or (c) allocated the leftmost bit even when the oldest instruction is in the middle of the window (which, e.g. when used in a scheduler, can cause newer instructions to run before older ones, which delays retiring instructions, which can hurt performance.)

[0293] Instead of using a butterfly switch to route the free indices to their respective destinations, we can take advantage of a unary encoding. In this case, after computing the enumeration, each one bit performs a write of a one into a two dimensional array of bits. The row number is the address of the one-bit, the column number is the enumeration index of the bit. Note that no two one bits could try to write into the same row, so no routing circuit is needed. All that is required is an address decoder, one per row, to write a one to the appropriate bit in the row according to the enumeration index. At this point destination j reads column j and retrieves a unary representation of the name of the newly allocated tag. Sometimes this circuit is more efficient than the butterfly circuit mentioned above. For example, if destination j needs to control a MUX to read tag i, having i in unary form can be faster because the MUX selectors can be driven directly instead of having to decode i first.

[0294] 4.2.4 Register Dependence Analysis

[0295] This section describes a novel circuit that passes information about the validity of table entries through a wrap-around sequence of operations, where each operation can invalidate, validate, or leave unchanged each table entry. The circuit can be used to implement register dependence analysis, also known as wake-up logic.

[0296] Recall that in the dependence analysis stage, instructions reside in the reordering buffer. The role of the dependence analysis stage is to identify those instructions that are ready to run. An instruction is ready to run when all of its necessary register, memory, and control dependencies have resolved. (Not all instructions must wait for memory and control dependencies to resolve.) In this section, we describe logarithmic, delay circuits that identify instructions whose register dependencies have been met. In the following two sections, we describe circuits that identify instructions whose memory and control dependencies have been met.

[0297] The circuit that identifies when register dependencies have been met is the wake-up logic. The wake-up logic informs an instruction whenever one of its argument registers is computed. Typically the wake-up logic is implemented using associative memory. For every instruction in the reordering buffer, the wake-up logic compares the tags of its arguments against the tag of every broadcasted result. An instruction is awakened once all of its arguments have been broadcasted.

[0298] Our approach to implementing wake-up logic is based on prefix circuits and eliminates associative memory. The implementation is analogous to our implementation of renaming logic in Section 4.2.3. We use prefix circuits to compute information about each instruction's logical register file. Using prefix circuits, each instruction informs its successors which register it modifies and whether it has already computed the register's value. The prefix circuits in turn present each instruction with a bit vector indicating which of its incoming register values have already been computed. If the registers that an instruction uses (its “argument registers”) have been computed already, the instruction is awakened.

[0299] FIG. 33 describes the circuitry that implements our wake-up logic in logarithmic gate delay using parallel prefix circuits 660, 665. Specifically, the figure shows wake-up logic that operates on a four-instruction reordering buffer and uses a two-register logical register file (L=2). (We use a small register file for ease of explanation. It is clear how to make the register file larger.) The sequence of instructions in the reordering buffer wraps around, with the oldest instruction identified by its signal Oldest being high. In addition to its Oldest bit, each instruction sends into the circuitry an L-wide array of modified bits, Modified_i, and, in general, an L-wide array of valid bits, ValidIn_i. For each instruction, ${\mathrm{Modified}}_j=(\begin{array}{cc}1& \mathrm{if}\mathrm{the}\mathrm{instruction}\mathrm{modifies}\mathrm{register}{R}_j,\\ 0& \mathrm{otherwise}.\end{array}$ ${\mathrm{ValidIn}}_j=(\begin{array}{cc}1& \mathrm{if}\mathrm{the}\mathrm{instruction}\mathrm{modifies}\mathrm{register}{R}_j\\ & \mathrm{and}\mathrm{the}\mathrm{value}\mathrm{has}\mathrm{been}\mathrm{computed},\\ 0& \mathrm{if}\mathrm{the}\mathrm{instruction}\mathrm{modifies}\mathrm{register}{R}_j\\ & \mathrm{and}\mathrm{the}\mathrm{value}\mathrm{has}\mathrm{not}\mathrm{yet}\mathrm{been}\\ & \mathrm{computed},\\ \mathrm{don}\text{'}t\mathrm{care}& \mathrm{otherwise}.\end{array}$

[0300] Note that in FIG. 33 we assume that each instruction modifies at most one register R_jand so all the ValidIn signals for a given instruction, ValidIn_ithrough ValidIn_(L−1), can be set to ValidIn_j. The circuitry returns to each instruction an L-wide array of valid bits, ValidOut_i. If an instruction's ValidOut_iis high, then the instruction's register R_jhas been computed.

[0301] FIG. 33 uses one “oldest” CSPP circuit for each logical register. The “oldest” CSPP circuit is described in FIG. 15 and FIG. 13. The circuitry in FIG. 33 extends easily to wake up more instructions or to use more logical registers. For each new logical register, we add one more CSPP circuit. For each additional instruction, we add one more leaf node to every CSPP circuit. In mathematical notation, for each logical register R_j, we have a CSPP with

[0302] a{circle around (×)}b=a,

[0303] s_i=ModifiedOldest,

[0304] x_i=ValidIn,

[0305] ValidOut=y_i,

[0306] where i is the instruction number.

[0307] The circuitry we have described so far tells instructions when their arguments become available, but it does not tell them the argument values. There are a number of ways to pass argument values, once an instruction knows when its arguments become available. For instance, we can completely eliminate broadcasting by storing each result directly, according to its tag. In this implementation, computed results are stored directly. Consumer instructions are notified that the result has been computed via prefix circuits in FIG. 33. Once notified, consumer instructions read the result value directly, according to its tag. An alternate approach to passing argument values retains broadcasting. When an instruction is informed by a prefix circuit that its argument has just become available, it latches the broadcasted value. It there are multiple broadcast buses, the prefix circuits can compute which bus to latch from by passing bus identifiers in addition to valid bits along the prefix circuits in FIG. 33. Finally, a third approach passes argument values along the prefix circuits together with the valid bits. This is the approach taken in our Ultrascalar processor, described in Section 4.3.

[0308] 4.2.5 Memory Dependence Analysis

[0309] In order to exploit instruction level parallelism (ILP), the memory bandwidth must also scale. In particular, the processor must be able to issue more loads and stores per clock cycle (i.e. sustain a higher data bandwidth) and the fetch unit must supply more instructions along a correctly predicted program path per clock cycle (i.e. sustain a higher effective instruction bandwidth.)

[0310] To accommodate more loads and stores per clock cycle without scaling up the number of data cache read and write ports, we can resort to the well known mechanism of interleaving. FIG. 34 illustrates an interleaved data memory subsystem. The memory subsystem comprises an on-chip level-one cache 670 and an on-chip butterfly network 675 connecting the cache to the execution stations ES. Much like the main memory in traditional supercomputers [39], the cache is interleaved among a number of banks CB. In this example, the number of cache banks CB is the same as the number of execution stations ES. In particular, the system shown has 16 execution stations ES, 16 cache banks CB and a butterfly network of four tiers of eight two-input, two-output switches 677 connected as shown. The nth cache bank holds every nth cache line. (To illustrate, let us assume that the number of banks and execution stations is sixteen, that the cache is direct mapped with block size of one word and total size of 1 MB, and that the instruction set architecture uses 32-bit byte addresses. A memory access to address A will then be routed to bank A[5-2]. Bank A[5-2] will find entry A[19-6] and compare its tag against address bits A[31-20]. Should the comparison fail, the level-one cache will access off-chip memory.) The cache banks are connected to the execution stations via a butterfly network and to off-chip memory (not shown) directly. The butterfly network allows n load and store requests to proceed in parallel if they form a rotation or other conflict-free routing. For example, a vector fetch loop will run without any conflicts if the address increment equals the cache block size. But in general, multiple memory accesses may compete for the same bank, or they may suffer from contention in the butterfly, thus lowering the memory bandwidth. The same programming, compiler, and hardware techniques used to alleviate bank conflicts in an interleaved main memory will apply to an interleaved data cache. (For example, making array lengths be relatively prime to each other can reduce the conflicts to a banked memory system.)

[0311] Note that the circuitry of a scalable memory system can be used to fetch both instructions and data from memory to the processor.

[0312] Another promising approach to increasing data memory bandwidth is to duplicate the data cache. We could allocate a copy of the cache to different subtrees of the Ultrascalar datapath or, in the extreme, to every execution station. Duplicate caches must be kept coherent using, for example, a scalable SMP cache-coherence protocol.

[0313] Given that there are several ways to provide memory bandwidth, there is still the problem of coping with memory dependencies.

[0314] This section describes several novel circuits that enforce or eliminate memory dependencies in a wrap-around sequence of instructions. The simplest circuit detects when all preceding instructions in a wrap-around sequence of instructions have finished writing memory. An instruction in the sequence is free to read memory once all preceding instructions have finished writing memory. The more complex circuits pass memory addresses and values from producer to consumer instructions. They do so by propagating information about all preceding memory writes to every instruction. The circuits vary in complexity based on whether they append information about subsequent writes or sort the information by address, whether they compact the information, and whether they eliminate older writes to the same address from the information.

[0315] In addition to resolving register dependencies, memory instructions must also resolve their memory address dependencies before they access memory. For example, if there are several load instructions between two store instructions in the reordering buffer, then the loads can run in parallel. But the loads must often wait for at least some previous store operations to complete to get the right data. (Note that if we speculate on the data then the loads need not necessarily wait for the previous stores. Below, we discuss branch speculation, which has similar issues to data speculation.) We first present the design for a conservative strategy, which is to wait for all previous store instructions to complete, then we show how to relax this constraint to exploit more parallelism.

[0316] Conservative Approach

[0317] Our conservative approach requires only one cyclic, segmented conjunction prefix. FIG. 16 and FIG. 13 described a conjunction CSPP. The number of leaf nodes in the CSPP tree, n, is equal to the size of the reordering buffer. The CSPP's inputs are: $x_i=\{\begin{array}{cc}1& \mathrm{if}\mathrm{instruction}\mathrm{in}\mathrm{slot}i\mathrm{of}\mathrm{the}\mathrm{reordering}\mathrm{buffer}\mathrm{is}\mathrm{not}\\ & a\mathrm{store}\mathrm{or}\mathrm{if}\mathrm{it}\mathrm{is}a\mathrm{complete}\mathrm{store},\\ 0& \mathrm{otherwise}.\end{array}{s}_i=\{\begin{array}{cc}1& \mathrm{if}\mathrm{instruction}\mathrm{in}\mathrm{slot}i\mathrm{of}\mathrm{the}\mathrm{reordering}\mathrm{buffer}\mathrm{is}\mathrm{the}\\ & \mathrm{oldest},\\ 0& \mathrm{otherwise}.\end{array}$

[0318] The prefix circuit computes for each instruction whether all previous writes have completed.

[0319] Memory Renaming

[0320] Some of today's processors perform renaming on memory locations. This allows loads and stores to execute out-of-order and in parallel in the case where the memory addresses are known. In this situation, a read must wait until the memory addresses of all the previous writes are known and all writes to the same address have completed. (We have heard that the Pentium Pro memory subsystem uses memory renaming to allow out-of-order memory operations. In the Pentium Pro scheme, some small number of memory operations are queued on-processor. The off-chip memory operations are performed serially. The on-chip queue will allow reads to complete out-of-order, even if unrelated prior writes have not been committed to memory.)

[0321] Memory-renaming has three sources of delays: (1) The addresses of loads and stores are generally not known right away. (2) The data is often not ready. (3) The circuitry for moving data to a load from the correct previous store may introduce delays. This section shows how to keep the circuit delay down to logarithmic cost, and to minimize the impact of the other delays. The trick is to determine when there are dependencies between instructions as soon as possible after an address becomes known, and to pass the data between the instructions as soon as the data becomes available.

[0322] Our novel implementation of memory renaming passes a partial memory-renaming table along a prefix circuit called the memory renaming datapath. The approach is comparable to our partial register-renaming maps. Recall that, to rename registers, we passed information about the current renaming of every logical register through a prefix circuit. We do not pass information about every main memory location, but instead we pass information about only the memory locations written to by the instructions currently in the reordering buffer.

[0323] Consider a CSPP implementation of the memory renaming datapath for a reordering buffer using 32-bit addresses and data. Each instruction in the reordering buffer contributes one 66-bit memory-renaming entry. The memory-renaming entry specifies:

[0324] whether the instruction writes to memory, indicated by the V bit,

[0325] whether the data it writes, if any, has resolved, indicated by the DataV bit,

[0326] the memory address, and

[0327] the data to be written.

[0329] As memory renaming entries propagate through the memory-renaming datapath, an associative operator can simply append them: a{circle around (×)}b={a,b}. Thus, the CSPP's inputs are

[0330] x_i=memory renaming entry for the instruction in slot i of the reordering buffer $s_i=\{\begin{array}{cc}1& \mathrm{if}\mathrm{instruction}\mathrm{in}\mathrm{slot}i\mathrm{of}\mathrm{the}\mathrm{reordering}\mathrm{buffer}\mathrm{is}\mathrm{the}\mathrm{oldest},\\ 0& \mathrm{otherwise}.\end{array}$

[0331] An additional prefix circuit computes whether the addresses of all preceding memory writes have resolved. We can compute this information using one cyclic, segmented conjunction prefix. FIG. 16 and FIG. 13 described a parallel cyclic segmented conjunction prefix. The number of leaf nodes in the prefix tree is equal to the size of the reordering buffer. The prefix's inputs are: $x_i=\{\begin{array}{cc}1& \mathrm{if}\mathrm{instruction}\mathrm{in}\mathrm{slot}i\mathrm{of}\mathrm{the}\mathrm{reordering}\mathrm{buffer}\mathrm{does}\mathrm{not}\\ & \mathrm{write}\mathrm{memory}\mathrm{or}\mathrm{if}\mathrm{the}\mathrm{address}\mathrm{of}\mathrm{the}\mathrm{write}\mathrm{has}\mathrm{resolved},\\ 0& \mathrm{otherwise}.\end{array}{s}_i=\{\begin{array}{cc}1& \mathrm{if}\mathrm{instruction}\mathrm{in}\mathrm{slot}i\mathrm{of}\mathrm{the}\mathrm{reordering}\mathrm{buffer}\mathrm{is}\mathrm{the}\mathrm{oldest},\\ 0& \mathrm{otherwise}.\end{array}$

[0332] The prefix circuit computes for each instruction whether the addresses of all preceding memory writes have resolved.

[0333] The memory renaming datapath outputs to each instruction in the reordering buffer an array of n memory-renaming entries, where n is the size of the reordering buffer. The entries are sorted by age. If an instruction in the reordering buffer is executing a memory read and if the addresses of all preceding memory writes have resolved as indicated by the above conjunction CSPP, then the instruction can search the array for the most recent entry with the same address. If there is such an entry, then whenever the DataV bit of that entry goes high, the instruction can read the entry's data. If there is no such entry, then the instruction must read from the data cache. (While waiting for addresses to resolve, the instruction can always speculatively read from the memory renaming datapath or the cache.)

[0334] We can reduce the size of the datapath by sending the addresses of memory reading instructions up the tree and sending down the tree only the memory-renaming entries to be read, analogously to the optimized Ultrascalar datapath that will be described in Section 4.3.8.

[0335] To reduce the width of the memory-renaming datapath, we may also choose to pass information about a number of writes W that is less than the size of the reordering buffer. Since most instructions within the reordering buffer are unlikely to write to memory, a much narrower memory-renaming datapath should suffice in practice. If the number of memory writes within the reordering buffer exceeds W, however, memory instructions past the Wth write may have to wait. (A one-bit wide disjunction CSPP circuit can notify every instruction in the reordering buffer whether the memory-renaming datapath has overflowed.) Alternately, the instructions can speculate (value speculation or possibly doing the read from memory, and possibly use the scheme mentioned above with cache tagging). To limit the number of memory-renaming entries to W, we can simply stop doubling the size of the memory-renaming tables at level log W of the CSPP tree. (We could even reduce the size of the memory-renaming tables at lower levels of the tree, to further reduce the cost of the system. For example, we could set up the circuits so that at level i of the tree, there are ┌2^i/2┐ table entries, limiting the number of entries in the system to about {square root over (W)}.) The new associative operator a{circle around (×)}b returns the compacted and appended valid entries {a,b} by if the total number of valid entries in the two tables is less than W.

[0336] To try to keep the number of memory-renaming entries small, we can use an optimized associative operator that invalidates older writes to the same address and then compacts the table. FIG. 37 illustrates the behavior of this optimized operator. The inputs to the operator are two partial memory-renaming tables with four memory-renaming entries. Let's assume that W=4 and so the output is also a partial memory-renaming table with four memory-renaming entries.

[0337] Mathematically, a partial memory renaming table is a mapping f from memory addresses to values. Thus f(x)=y means that address x contains value y. (We need an extra NONE value in the range of f to indicate that f has “no value” for x.) The prefix operation that eliminates older writes to the same address, {circle around (×)}, is defined by $\left(f\otimes g\right)\left(x\right)=\{\begin{array}{cc}g\left(x\right)& \mathrm{if}g\left(x\right)\ne \mathrm{NONE},\mathrm{and}\\ f\left(x\right)& \mathrm{otherwise}.\end{array}$

[0338] If we have I instructions in the reordering buffer and it takes time τ_mfor the {circle around (×)} to run, then our CSPP circuit will have a critical path of length Θ(τ_mlog I). Note that τ_mdepends on W, the maximum size of the partial memory-renaming table.

[0339] To invalidate older writes to the same address, we must construct f {circle around (×)}g. One way to do this is to append f and g and then remove the entries from f that also appear in g. It is easy to design a circuit to perform the {circle around (×)} computation in time O(W). For example, a bus can be used. Each table entry, in sequence, broadcasts its memory address and sequence number, and any older sequence numbers with the same memory address delete themselves from the table. One can build a system which is faster, however.

[0340] A logarithmic depth implementation of f{circle around (×)}g compares each entry of g against each entry of f in parallel and then uses W W-to-1 or-trees to compute which entries of f should be invalidated. FIG. 38 shows how the third valid bit is computed when W=4. The inputs to the circuit are the addresses of the memory renaming entries in g on the left, the addresses of the memory renaming entries in f and the input valid bits of the memory renaming entries in f on the bottom. The shown output is the output valid bit of the third entry in f.

[0341] In general, to eliminate duplicates from a single sorted array, we can use an optimized version of the above circuit. We create a square grid of logic. Write the array entries along the bottom of the grid, and also write another copy of the array entries along the left edge of the grid. Broadcast the array along the rows of the grid, and also along the columns. Now at each grid point we have one combination of a row and a column. At the grid points above the diagonal, we check to see if the row and column entries match. If they do, the column entry should be invalidated.

[0342] Another improvement on the memory renaming datapath can merge sorted entries according to their addresses. The associative operator then replaces its append circuit with a merge circuit that merges two arrays of memory-renaming entries according to their addresses. Once the associative operator merges sorted arrays, it is easy to invalidate older writes to the same address. Each entry in the array independently reads its younger neighbor's address, and invalidates itself if its address matches that of its younger neighbor. It is also easy to compact a merged array. When merging entries, we simply sort using the inverted valid bit as the most-significant bit. Thus, invalid entries will appear at the end of the merged array.

[0343] Memory Data Speculation

[0344] Another approach is to use speculation on the memory reads: A read can assume that no uncommitted instruction actually writes to the same location, and go ahead and read. To make that work, one must go back and redo any reads that made this assumption incorrectly. To our knowledge, no processors perform read speculation, but ideas for read speculation appear in the literature (e.g., [40].)

[0345] One way to implement read speculation is to have the read operation put a note on the cache line indicating that if anyone writes to the cache line, then a particular reorder-buffer entry must be notified. If the entry sees that all previous instructions have committed, and it has not been notified, then it knows that the read got the right value, and it may commit, (and it must go and remove the note from the cache line.) If the execution station is notified that the value was changed, then the notification contains the proper data, and the execution station updates its output, and waits for the commit signal. (Also the execution station must continue to wait for notification that a serially previous memory operation has affected its result: For example if a previous store modifies the memory location read by the execution station, then the cache will notify the execution station. That is the reason that the cache must take note of all the readers of a particular location.) A similar idea is described for the Wisconsin Multiscalar architecture [40], to indicate which processor in a multiprocessor system has read or written a particular memory location.

[0346] To handle write-after-write conflicts we can play a similar trick. When an execution station writes to a cache-line, the cache line should be given a sequence number of the instruction that did the write. This sequence number contains enough information to determine which instruction is first (if there are N execution stations, then a sequence number in the range [0 . . . 2N−2] should suffice, since given two such sequence numbers we can determine whether they are closer by wrapping forward or closer by wrapping backwards, and thus determine their relative ordering.) The cache line must then keep a list of all the writes along with their sequence numbers and when writes commit they need to update the cache, and reads need to provide a sequence number so that the cache can provide the right value. Thus, a write with sequence number x affects all reads with sequence numbers in [(x+1) . . . (x+N−1)]. All reads with those sequence numbers must be given updated data.

[0347] Our scheme is divided up into cache lines to allow the system to be more scalable without costing more area. Thus our scheme is superior to a single queue as used, for example in the Pentium Pro.

[0348] 4.2.6 Control Dependence Analysis

[0349] This section describes a novel circuit that detects when all preceding elements of a wrap-around sequence have met a certain condition. In this case, the condition is that they have committed.

[0350] Superscalars are designed so that modifications to the logical register file can be quickly undone. Typically, memory writes cannot be undone and must instead wait until all previous instructions have committed (i.e., are not speculating on data or control flow) before writing memory.

[0351] We can compute whether all preceding instructions have committed using one cyclic, segmented conjunction prefix. FIG. 16 and FIG. 11 described a parallel cyclic segmented conjunction prefix. The number of leaf node in the prefix tree is equal to the size of the reordering buffer. The prefix's inputs are: $x_i=\{\begin{array}{cc}1& \mathrm{if}\mathrm{instruction}\mathrm{in}\mathrm{slot}i\mathrm{of}\mathrm{the}\mathrm{reordering}\mathrm{buffer}\mathrm{has}\mathrm{committed},\\ 0& \mathrm{otherwise}.\end{array}{s}_i=\{\begin{array}{cc}1& \mathrm{if}\mathrm{instruction}\mathrm{in}\mathrm{slot}i\mathrm{of}\mathrm{the}\mathrm{reordering}\mathrm{buffer}\mathrm{is}\mathrm{the}\mathrm{oldest},\\ 0& \mathrm{otherwise}.\end{array}$

[0352] The prefix circuit computes for each instruction whether all previous instructions have committed.

[0353] 4.2.7 Scheduling Instructions

[0354] This section describes a series of novel circuits that assign a set of resources to a set of the requesting elements from a wrap-around sequence of elements. Not all the elements in the sequence need be requesting and the number of requesting elements may exceed the number of available resources. Various criteria can be used to select which requesting elements receive the resources. For example, one of the circuits assigns the resources to the oldest requesting elements. A more elaborate circuit subdivides elements into several priority levels and assigns resources to higher priority level elements first and, within each level, to older elements first. Additional circuitry enables the assignment of only a subset of resources.

[0355] These circuits can be used to implement the scheduling stage of a superscalar processor which selects a set of ready instructions to run on functional units. The instructions are in reservation stations arrayed in the instruction window. Each reservation station contains information indicating whether its instruction is ready to run, and which functional unit is needed. The functional units include floating point adders, multipliers, integer units, and memory units. At the beginning of every clock cycle, some of the instructions in the reservation stations are ready to run. There may be more than one functional unit that can be used by any particular instruction. In many situations, certain of the instructions should be scheduled with higher priority than others. For example, it may be preferred to schedule the oldest instructions with higher priority, or it may be preferred to schedule instructions which resolve condition codes with higher priority. For memory operations it may be preferable to schedule nonspeculative loads rather than speculative loads.

[0356] We divide the functional units into classes. For our example, we let the adders be Class 0, the dividers be Class 1, and the memory units be Class 2. Let us assume there are three adders, two dividers, and one memory unit. The number of functional units in Class i is denoted by F_i. The functional units in Class i are numbered 0 to F_i−1 . All F_ifunctional units are available on every clock cycle.

[0357] After scheduling the instructions, the data must actually be moved to the appropriate functional units.

[0358] Scheduling The Instructions

[0359] FIG. 39 shows the logic that assigns functional units to ready instructions. This logic includes a schedule memory unit 700, a schedule divider 705 and a schedule adder 710. From the analyze dependencies stage come many “request” bits labeled Q_ij. Bit Q_ijis true if and only if ith instruction in the window is ready to run and it needs a functional unit from Class j. To avoid cluttering up the figure, the signals Q_ij, are collectively labeled Q_1*, and the signals Q_2j, are collectively labeled Q_2*, and the last window entry's request bits are labeled Q_(w−1)*. The logic produces signals G_ij(with a similar notation that G_i*, refers to all the request signals from Window i) which go back to the reordering buffer in the analysis stage. Signal G_ijmay require several bits to encode, since it must encode at least 1+F_i, different values (one for each functional unit of that class, and one value to indicate that no functional unit was assigned.) Hence G_ijmust be at least ┌lg(1+F_i)┐ bits wide. Several different encodings are possible. For concreteness, we will use the following encoding for G_ij $G_{i,j}=\{\begin{array}{cc}k& \mathrm{if}i\mathrm{the}\mathrm{instruction}\mathrm{in}\mathrm{the}\mathrm{window}\mathrm{is}\mathrm{assigned}\mathrm{to}\mathrm{function}\mathrm{unit}\mathrm{Number}k\mathrm{in}\mathrm{Class}j\\ F_i& \mathrm{if}i\mathrm{instruction}\mathrm{in}\mathrm{the}\mathrm{window}\mathrm{requested}a\mathrm{function}\mathrm{unit}\mathrm{and}\mathrm{the}\mathrm{request}\mathrm{was}\mathrm{denied},\\ \text{don't}\mathrm{care}& \mathrm{if}i\mathrm{the}\mathrm{instruction}\mathrm{in}\mathrm{the}\mathrm{window}\mathrm{did}\mathrm{not}\mathrm{request}a\mathrm{function}\mathrm{unit}.\end{array}$

[0360] In FIG. 39, schedule memory unit 700, schedule divider 705, and schedule adder 710 labeled “schedule, are the schedulers for each of our three example functional unit classes. Each of these is simply a CSPP summation circuit, summing 1-bit inputs Q_ij, followed by W comparators that compute min(y_j,F_i). Specifically, for Class i we have

[0361] s_i=the bit indicating that Window Entry j is oldest.

[0362] x_j=Q_ij

[0363] G_ij=min(y_j, F_i)

[0364] Thus if y_j<F_ithen G_ijindicates that Window Entry j receives functional unit Number y_jin Class j.

[0365] Note that there are some special cases that can be optimized to reduce the circuit complexity. Typically there are more window entries than functional units in a class. To compute ┌lgW┌ bits and then take the minimum of that number with F_imay, in some situations, be wasteful. Instead of doing that, a saturating adder can be used in the tally circuit so that the number of bits going up and down the tree never becomes larger than ┌lg(1+F_i)┐ bits in size.

[0366] An important special case is if F_i=1, (for example, we only have one memory unit in our example.) In this case an OR gate implements a saturating adder, and the circuit becomes the one shown in FIG. 18.

[0367] Moving The Data

[0368] To move the data to the functional units, several different strategies can be used, including, for example, a broadcast bus or a tree of busses, or a broadcast tree. For very large issue widths and very large numbers of functional units, it is important that the data movement mechanism scale well. (That is, large amounts of data need to move with low latency.) Here we show how to use a butterfly routing network to implement the data movement. This butterfly has enough bandwidth to move all the data in all cases without introducing contention at the internal switches, and it can move the data with only a logarithmic number of gate delays.

[0369] FIG. 40 shows a butterfly network implemented with switches 720 of degree two. (See, for example, [15, 20] for methods for routing in this kind of network.) This network can move data to the three functional units, illustratively adders from eight window locations 0-7. Switches 720 are connected in a butterfly network. The addresses are the G_ij, values provided by the scheduler CSPP circuits. The data are the two register values that the reorder buffer provides. Shown is a signal containing the address and a signal containing data from each of the 8 reorder buffer slots.

[0370] FIG. 41 shows an example of how this works. We have deleted a switch which was not needed since we had fewer destinations than sources. The thick line shows the path followed to get data from Sources 1, 2, and 7 to Destinations 0, 1, and 2 respectively. The path chosen is the one chosen by the algorithm of [15]. Specifically, to get from Source i to Destination j one computes the relative address XOR(i,j), which is the bitwise exclusive or of i and j. Then the message goes straight through switch k if bit k is false in the relative address. Thus to go from Source 1 to Destination 0, the relative address is 1 which is 001₂, in base 2. The message should go diagonally through the first switch and straight through the next two switches.

[0371] To go from Source 7 to Destination 2, the relative address is 101₂=XOR(111₂,010₂), so the message should go diagonally through the first and third switch, and straight through the second switch. Note that [15] uses a wormhole router, but other routing mechanisms can be used to establish the path through the circuit, since the circuit is all one VLSI chip.

[0372] Note that for the example we showed there is no conflict for the use of the wires. It turns out that for all the routing patterns produced by this scheduling circuit, there are no conflicts, and the messages can go through in one clock cycle. This is because our scheduler produces only routing patterns that are semi-contractions. A semi-contraction is a routing which has the property that the distance between the destinations of two messages is no greater than the distance between their initial locations. I.e., |i−j|≧|f(i)−f(j)|. In [17] a proof is given that semi-contractions can be routed on a butterfly with no conflicts.

[0373] Many of the other networks, such as fat trees, omega networks, complete networks, busses, or trees of busses can be used. Engineering considerations should include taking into account the exact size of the window, the number of functional units, and the number of function unit classes. For example, for a small system a bus may be the best solution, whereas for a large system, a butterfly of Radix 8 may be the best solution. For any particular problem size, determining the costs of the various options is straightforward, however. Also, several different VLSI layouts are possible, including the layout shown in FIG. 40 or an H-tree layout. See [20] for a complete discussion of networks for parallel computing.

[0374] Scheduling Certain Instructions with Higher Priority

[0375] Usually a scheduler that prefers older instructions rather than younger instructions is a good heuristic. Sometimes, certain younger instructions are preferred over older ones. For example, instructions that resolve conditional branches are good to execute. To schedule such instructions with higher priority we must first identify the instructions, and then schedule the identified instructions.

[0376] It is straightforward to use CSPP to identify an instruction that resolves a condition code for an unresolved branch. One performs a backwards CSPP with

[0377] {circle around (×)}=“and”,

[0378] s_i=true for unresolved branches, and

[0379] x_i=true for instructions that do not resolve conditions codes.

[0380] In this case y_isays that there are no instructions that resolve condition codes until the next unresolved branch. If an instruction resolves condition codes and y_iis true (i.e., y_i{overscore (x)}_i), then instruction i is identified as a higher-priority instruction.

[0381] Among the higher priority instructions, one can schedule the oldest one using a CSPP scheduler as described above. After scheduling the high priority instructions, one uses another CSPP circuit to schedule the low priority instructions. To account for the fact that some of the functional units were allocated to higher priority instructions, one simply adds the number of previously allocated functional units to the output of the tally circuit to compute the assignment of instructions to functional units in the ordinary-priority instructions. Note that the resulting routing of data may not be conflict-free through the butterfly, however. There are several ways to solve this problem. One way is to design a network that can handle the resulting routings. One such network consists of two butterflies, one for the higher priority instructions and one for the lower priority instructions. Another approach is to take advantage of the fact that once we have decided which instructions are to be allocated to a function unit, we do not really care which functional unit in the class is allocated to which instruction. One can take advantage of this leeway by running an additional parallel prefix operation: after identifying all the instructions that will be assigned a functional unit, one then tallies those instructions. An acyclic unsegmented parallel prefix will do the job in this case with

[0382] x_i=true if instruction i's first assignment was less than F_j, and

[0383] y_i=the actual functional unit to which instruction i is assigned.

[0384] Then one can route the allocated instructions to their functional units through a butterfly switch with no conflicts.

[0385] Scheduling a Subset of Functional Units

[0386] Note that so far we have assumed that all F_ifunctional units can be scheduled on every clock cycles. This is true of pipelined functional units such as a pipelined multiplier or 1-cycle functional units such as an integer adder. However, it is not true of multi-cycle functional units such as a divider. Consider the scenario where a processor has eight dividers that comprise Class 0. Dividers 3 and 7 are available to be scheduled. We wish to match dividers 3 and 7 with the two oldest requesting instructions, i and j. The two oldest requesting instructions received G_i,0=0 and G_j,0=1 respectively. To inform instructions i and j that they have been assigned dividers 3 and 7 respectively, we first use a summation parallel prefix to number available dividers: x_j=1 if divider is available, 0 otherwise. We then connect the scheduled instructions to available dividers using two back to back butterfly networks. The routing is collision free. Note that similar circuits were used for tag reuse and instruction scheduling.

[0387] 4.2.8 Broadcast Logic

[0388] The broadcast stage of a superscalar processor is responsible for forwarding values between producer and consumer instructions. The forwarding is typically accomplished by broadcasting every computed value to every instruction within the reordering buffer. When an instruction is informed by the wake-up logic that its argument has just become available along a given broadcast bus, it latches the broadcasted value along that bus. To scale this approach to large numbers of outstanding instructions, values should be fanned out along a fan-out tree instead of being broadcast along a single bus.

[0389] An alternate approach can eliminate broadcasting of values by storing each result directly in a file, according to its tag. In this implementation, computed results are stored directly. Consumer instructions are notified that the result has been computed via the processor's wake-up logic. Once notified, consumer instructions read the result value directly from the file, according to its tag.

[0390] We can draw on our implementation of the wake-up logic in Section 4.2.4 to further optimize the forwarding of values between producer and consumer instructions. This is because the prefix circuits in FIG. 33 can pass other useful information in addition to valid bits. Consider an implementation in which values are broadcasted. It there are multiple broadcast buses, the prefix circuits described in Section 4.2.4 can compute which bus to latch from by passing bus identifiers in addition to valid bits along the prefix circuits in FIG. 33. A completely different implementation arises when we pass logical register values in addition to valid bits along the prefix circuits in FIG. 33. This is the approach taken in our Ultrascalar processor. In this case, values are automatically forwarded from producer instructions to consumer instructions without the need to broadcast results or to store results in an intermediate file.

[0391] 4.2.9 Bypass Logic

[0392] To achieve good processor performance, it is critical to minimize the number of clock cycles between the time when an instruction's arguments become available and when that instruction begins executing. Superscalar processors can minimize this delay by broadcasting the tags of computed results a constant number of clock cycles before the results are actually computed. Since an instruction is awakened before its arguments are ready, it may be able to schedule itself and reach the beginning of the execute stage while its missing argument(s) are being computed. The instruction grabs its missing argument(s) along their bypass paths.

[0393] Note that our novel implementation of the wake-up logic described in Section 4.2.4 and illustrated in FIG. 33 allows instructions to be awakened a constant number of clock cycles, c, before their arguments are computed. To do that, each instruction in the reordering buffer simply sets its logical result register's Validln bit c clock cycles earlier: ${\mathrm{Modified}}_j=\{\begin{array}{cc}1& \mathrm{if}\mathrm{the}\mathrm{instruction}\mathrm{modifies}\mathrm{register}{R}_j,\\ 0& \mathrm{otherwise}.\end{array}{\mathrm{ValidIn}}_j=\{\begin{array}{cc}1& \mathrm{if}\mathrm{the}\mathrm{instruction}\mathrm{modifies}\mathrm{register}{R}_j\mathrm{and}\mathrm{the}\mathrm{value}\mathrm{has}\mathrm{been}\mathrm{computed}\\ & \mathrm{or}\mathrm{will}\mathrm{be}\mathrm{computed}\mathrm{within}c\mathrm{clock}\mathrm{cycles}\\ 0& \mathrm{if}\mathrm{the}\mathrm{instruction}\mathrm{modifies}\mathrm{register}{R}_j\mathrm{and}\mathrm{the}\mathrm{value}\mathrm{has}\\ & \mathrm{not}\mathrm{yet}\mathrm{been}\mathrm{computed}\\ \text{don't care}& \mathrm{otherwise}\end{array}$

[0394] Each instruction then knows that its logical input register R, will be computed c clock cycles after ValidOutj goes high. If bus identifiers are also being passed along the prefix circuits of FIG. 33, they too can be passed early allowing for a speedy setting of the bypass paths. If logical register values are being passed along the prefix circuits of FIG. 33, the computed value will arrive c clock cycles after its valid bit has been set high, allowing the consumer instruction time to schedule itself.

[0395] 4.2.10 Reusing the Reordering Buffer

[0396] As instructions compute and update state, the superscalar processor must remove them from the reordering buffer in order to make room for new instructions. Some superscalars store instructions in their reordering buffer in order with the oldest instruction in slot 0, second oldest in slot 1, and so on. These processors can use an and-tree circuit to compute when all instructions in the buffer have finished and then invalidate all buffer entries and begin refilling the buffer.

[0397] Some superscalars compact remaining unfinished instructions on every clock cycle and compute a pointer to the first free slot in the buffer. New instructions can be written into the buffer on every clock cycle starting at the first free slot.

[0398] The CSPP-based circuits that we have used to implement renaming logic, dependence analysis logic, scheduling logic, and broadcast logic, presume that instructions are stored in a wrap-around order, with the oldest instruction identified by its Oldest bit being set high. On every clock cycle, a buffer slot is free to be refilled when its instruction has finished and all older instructions have also finished. On every clock cycle, a buffer slot contains the oldest instruction if all the previous instructions have finished and its instruction has not finished. We can use another prefix circuit to compute these conditions on every clock cycle. The prefix circuit tells each buffer slot whether all the previous instructions have finished. The buffer slot can combine that information with information about its own instruction in order to determine its new status.

[0399] We can compute whether all preceding instructions have finished using one cyclic, segmented conjunction prefix. FIG. 16 and FIG. 13 described a parallel cyclic segmented conjunction prefix. The number of leaf nodes in the prefix tree is equal to the size of the reordering buffer. The prefix's inputs are: $x_i=\{\begin{array}{cc}1& \mathrm{if}\mathrm{instruction}\mathrm{in}\mathrm{slot}i\mathrm{of}\mathrm{the}\mathrm{reordering}\mathrm{buffer}\mathrm{does}\mathrm{not}\\ & \mathrm{write}\mathrm{memory}\mathrm{or}\mathrm{if}\mathrm{the}\mathrm{address}\mathrm{of}\mathrm{the}\mathrm{write}\mathrm{has}\mathrm{resolved},\\ 0& \mathrm{otherwise}.\end{array}{s}_i=\{\begin{array}{cc}1& \mathrm{if}\mathrm{instruction}\mathrm{in}\mathrm{slot}i\mathrm{of}\mathrm{the}\mathrm{reordering}\mathrm{buffer}\mathrm{is}\mathrm{the}\mathrm{oldest},\\ 0& \mathrm{otherwise}.\end{array}$

[0400] The prefix circuit computes for each instruction whether all previous instructions have finished.

[0401] 4.3 The Ultrascalar Processor

[0402] We have seen that today's superscalar processors rename registers, bypass registers, checkpoint state so that they can recover from speculative execution, check for dependencies, allocate execution units, and access multi-ported register files. The circuits employed today are complex and irregular, requiring much effort and ingenuity to implement well. Furthermore, the delays through many of the circuits grow quadratically with issue width (the maximum number of simultaneously fetched or issued instructions) and window size (the maximum number of instructions within the processor core), making future scaling of today's designs problematic [32, 8, 10]. With billion transistor chips on the horizon, this scalability barrier appears to be one of the most serious obstacles for high-performance uniprocessors in the next decade. (Texas Instruments announced recently a 0.07 micron process with plans to produce processor chips in volume production in 2001 [42].) Surprisingly, it is possible to extract the same instruction-level parallelism (ILP) with a regular circuit structure that has only logarithmic gate delay and linear wire delay (speed-of-light delay) or even sublinear wire delay, depending on how much memory bandwidth is required for the processor. This section describes a new processor microarchitecture, called the Ultrascalar processor, based on such a circuit structure.

[0403] The goal of this section is to illustrate that processors can scale well with issue width and window size. We have designed a new microarchitecture and laid out its datapath. We have analyzed the asymptotic growth and empirically computed its area and critical-path delays for different window sizes. We do not evaluate the benefits of larger issue widths and window sizes. Some work has been done showing the advantages of high-issue-width and high-window-size processors. Lam and Wilson suggest that ILP of ten to twenty is available with an infinite instruction window and good branch prediction [19]. Patel, Evers and Patt demonstrate significant parallelism for a 16-wide machine given a good trace cache [34]. Patt et al argue that a window size of 1000's is the best way to use large chips [35]. The amount of parallelism available in a thousand-wide instruction window with realistic branch prediction, for example, is not well understood however. We believe that in future applications there will be plenty of parallelism to keep a wide-issue processor busy.

[0404] The rest of this section is organized as follows. Section 4.3.1 shows a linear-time Ultrascalar processor core. Section 4.3.2 describes a more detailed performance analysis to show the benefits of our approach. Section 4.3.3 shows a log-time processor core. Section 4.3.4 shows ways to scale the memory subsystem. Section 4.3.5 describes speculation in the Ultrascalar. Section 4.3.6 shows the VLSI layout of the processor core, and analyzes the chip complexity using that layout. Section 4.3.7 shows the performance of our prototype processor core, and shows how to further improve the performance. Section 4.3.9 compares the Ultrascalar to some related work.

[0405] 4.3.1 A Linear-Time Datapath

[0406] This section describes the core of the Ultrascalar processor. The Ultrascalar processor core performs the same functions as a typical superscalar processor core. It renames registers, analyses register and memory data dependencies, executes instructions out of order, forwards results, efficiently reverts from mispredictions, and commits and retires instructions. The Ultrascalar processor core is much more regular and has lower asymptotic critical-path length than today's superscalars, however. In fact, all the scaling circuits within the processor core are instances of a single algorithm, parallel prefix, implemented in VLSI. Because of the core's simplicity, it is easily apparent how the number of gates within a critical path. grows with the issue width and window size.

[0407] The usual superscalar approach is to rename the registers mentioned in the instructions, and then build a sequential state machine that tries to schedule those instructions to execute in parallel. Our design is based on an alternative idea in which we assume that there are plenty of arithmetic logic units (ALUs) and our job is to wire them together to compute the right value. We start with the old register state and propagate the register state through a chain of switches and ALU's that produce new register values. Each instruction corresponds to a switch and an ALU. Each switch can locally set its switch settings based on its instruction's register fields.

[0408] An ALU is assumed to be cheap since to include one ALU for every instruction only costs linear area and costs no extra time. Since other parts of the chip have at least linear area the cost of ALU's will be acceptable for large I Also, it would be possible to share ALU's among different execution stations, using the same circuitry for sharing ALU's among buffer entries described in Section 4.2.7. In general, any circuit in Section 4.2 that operates on a sequence of instructions in the reordering buffer can also operate on a sequence of instructions in the Ultrascalar.

[0409] The core does not include the memory and branch prediction subsystems. Instead the core presents the same interface to the instruction fetch unit and the data cache as today's superscalar processor cores. Predicted instruction sequences enter the core, and data load and store requests are initiated by the core. We briefly discuss possible memory subsystems in Section 4.3.4, but the Ultrascalar core will benefit from the advances in effective instruction fetch rate and in data memory bandwidth that can be applied to traditional superscalar processors. In particular, since the Ultrascalar processor core performs the same functions as the core of today's superscalars, it achieves the same CPI, or more, performance as existing superscalars when attached to a traditional 4-instruction-wide fetch unit using traditional branch prediction techniques and a traditional cache organization. As effective fetch rates and data bandwidths increase, the Ultrascalar core can scale gracefully, raising the CPI without exploding the cycle time.

[0410] One way to think of the Ultrascalar processor is that it uses a circuit-switched network to compile at runtime the dataflow graph for a dynamic sequence of unrenamed instructions. The circuit switched network connects producer instructions with consumer instructions. The structure and the layout of this network are the key to the Ultrascalar's scalable performance.

[0411] Before we introduce the Ultrascalar, let us briefly consider a simpler datapath in which the network connecting producer instructions to consumer instructions consists of a simple ring. We will refer to this datapath as the linear-time datapath. FIG. 42 illustrates. The datapath is divided into four execution stations. Each execution station takes an entire copy of the registers and produces a new copy of the registers. The execution station includes, for each instruction, the instruction latch 730, its associated switching logic, and its ALU 735. The ring network routes the values of L logical registers through a pipelined series of execution stations. (The value of L is determined by the instruction set architecture. For example, for many RISC architectures L=32.) Each execution station holds and eventually executes one instruction from a dynamic sequence of instructions. Executing an instruction may take only one clock cycle (e.g., for integer addition) or many clock cycles (e.g., for division.) The number of execution stations corresponds to the number of outstanding instructions within the processor much like the instruction window (also known as the reordering buffer) in today's superscalars. As in today's superscalars, the fetch width is independent of the number of outstanding instructions. Newly fetched instructions simply refill execution stations in a wrap-around fashion, starting with the oldest instruction. In the figure, the oldest instruction in the current sequence resides in Execution Station 1, the youngest in Execution Station 0. Note that the pipeline registers of Execution Station 1 hold the committed state of the register file. Throughout the datapath, each register value has a ready bit. The ready bit is associated with the wires carrying the register value and indicates whether the value has already been computed. As instructions complete, they retire from the datapath and new instructions enter the datapath. Eventually, the output wires of Execution Station 0 hold the new state of the register file, with all of their ready bits set to high.

[0412] The execution station executes its instruction once its arguments are ready and outputs the result to the destination register's value bus. The execution station keeps the ready bit of the destination register low and raises it only after the result is ready. All other register values and their ready bits pass through the execution station unmodified. An execution station is committed when it has computed its values and its instruction definitely is to be run (e.g., no previous branch speculation can mispredict.)

[0413] Consider the performance of the linear-time datapath example in FIG. 42. The complete sequence of instructions currently in the datapath (with the corresponding execution station shown to the right) is:

[0414] Note that the first instruction in the sequence is not placed in the first execution station. Instead the first instruction is placed in any execution station and subsequent instructions wrap around. In our example, the first instruction is in the second execution station (Station 1), and the fourth instruction has wrapped around to Station 0. Suppose that division takes 24 clocks and addition takes one.

[0415] On Clock 0, we assume that all the registers become valid at Station 1. Station 1 begins executing.

[0416] On Clock 1, all the registers except for R₁become valid at Station 2. Station 2 waits for R₁.

[0417] On Clock 2, all the registers except for R₁and R₃become valid at Station 3. Station 3 executes and produces a new value of R₁.

[0418] On Clock 3, all the registers except for R₃become valid at Station 0. Station 0 executes and produces a new value of R₄.

[0419] On Clock 23, Station 1 finishes executing.

[0420] On Clock 24, Station 2 executes.

[0421] On Clock 26, all the registers become valid at Station 0.

[0422] Note that the instructions executed out of order. The last two instructions completed long before the first two. Moreover, the datapath automatically renamed registers. The last two instructions did not have to wait for the divide to complete and write R₁.

[0423] Our linear-time datapath bears similarities to the counterflow pipeline [41]. Like counterflow, the linear-time datapath automatically renames registers and forwards results. Counterflow provides a mechanism for deep pipelining, rather than large issue width, however. The counterflow pipeline is systolic, with instructions flowing though successive stages of the datapath. Since instructions serially enter the pipeline in the first pipeline stage, the CPI is limited by the rate at which instructions can enter the pipeline. It is not clear how counterflow could be modified to increase its issue width. In contrast, in our linear-time datapath, all execution stations can refill with new instructions simultaneously. Thus, whereas our linear datapath has no corresponding limit on CPI (and is limited by the clock period), the counterflow can push the clock period down but is limited to one CPI.

[0424] Another difference between our linear datapath and counterflow is that counterflow uses less area to route data. It only passes results and arguments down its pipeline, not the entire register file. In Section 4.3.7 we will discuss a similar modification to reduce the number of wires used in the Ultrascalar.

[0425] One weakness shared by counterflow as well as our linear-time datapath is the speed of routing. In a synchronous implementation our linear-time datapath, if a producer and a consumer of a register value are separated by n instructions in the dynamic instruction sequence, it takes n clocks to serially route the value through all it intermediate execution stations. For example, it took 3 clocks to route R₂from Station 1 to Station 0. (In a counterflow pipeline, it typically would take n/2 clocks to perform this operation.) This linear delay can be intolerably high compared to today's superscalars that forward values within one clock cycle.

[0426] 4.3.2 A More Detailed Performance Analysis

[0427] Here we introduce another variant on the Ultrascalar in order to make it easier to show some analytical results.

[0428] Another way to implement the linear-time Ultrascalar datapath is to bypass the register flipflops in most execution stations. A simple scheme is shown in FIG. 43. In this simple model, there are two registers, one holding the old register state and one holding the new register state. The instructions can be thought of as specifying how to wire together registers and arithmetic units. In this case, there are three instructions, which are supposed to execute leftmost first. The old register state is on the left, and the new register state is on the right.

[0429] FIG. 44 shows the same system as FIG. 43, but we have divided the system into execution stations.

[0430] FIG. 45 shows the the executions station for FIG. 44. The execution station takes as its input the instruction, stored in its original form (not renamed) in the instruction latch at the top of the circuit. It also takes the values of all L registers from its left. We will assume from now on that each register is 32 bits wide, although all of our ideas extend to arbitrary width. Attached to each register value is an additional ready bit that indicates whether the value is ready (i.e. holds the correct register state for that instruction). The execution station produces as outputs the L register values and their ready bits. When all the ready bits are high, the output values hold the state of the register file right after the instruction's execution.

[0431] This Ultrascalar is also a a linear-time system, but in this case the clock period must grow as the machine size grows, whereas in the version shown in FIG. 42 the clock period does not grow but the number of clock cycles grows. This is the tradeoff between the clock period and number of clock cycles familiar to digital designers. With this variant we can analyze everything in terms of clock period.

[0432] The clock period grows with gate delays. The gate delays come from two sources: There is the delay induced by the data dependencies in the program, and there is the delay induced, even in parallel programs, by the circuit switches. We will analyze these cases by studying an instruction sequence which has no dependencies between instructions, a sequence in which every instruction depends on the previous one, and a sequence which has an intermediate number of dependencies.

[0433] The first case is an instruction sequence in which there are no true data dependencies. Consider this sequence of I instructions (I=5 in this case):

[0434] R1=R2+R3;

[0435] R2=R3+R4;

[0436] R3=R4+R5;

[0437] R4=R5+R6;

[0438] R5=R6+R7;

[0439] All of those instructions could run in parallel. In one of today's superscalar processors, all the registers are renamed to remove the antidependency between each pair of instructions. (An antidependency is a situation where a later instruction writes to a register that an earlier instruction reads from. This would constrain the second instruction from finishing before the first one started. Tomasulo showed how to rename the registers to get rid of those antidependencies [44]. Our parallel-prefix technique also gets rid of antidepencies automatically, since effectively every register is renamed on every instruction.) In this case, the longest gate delay through the circuit is a path that goes through one L-to-1 MUX, and through an ALU, and through I 2-to-1 MUXes. This is because each 33-bit datapath must be switched through a 2-to-1 MUX in every execution station. Thus we have gate delay

[0440] τ=τ_{L-to-1 mux}+τ_ALU+I·τ_{2-to-1 mux}.

[0441] The next case is an instruction sequence in which every instruction depends on all of its predecessors. Consider this instruction sequence:

[0442] R2=R1+R1;

[0443] R2=R2*R1;

[0444] R2=R2+R1;

[0445] R2=R2*R1;

[0446] R2=R2+R1;

[0447] R2=R2*R1;

[0448] R2=R2+R1;

[0449] R2=R2*R1;

[0450] R2=R2+R1;

[0451] Each of those instructions depends on the previous instruction. Thus, the longest delay through the circuit is through I L-to-1 MUXes, I ALUs, and I 2-to-1 MUXes. We have

[0452] τ=I·(τ_{2-to-1 mux}+τ_{L-to-1 mux}+τ_ALU)

[0453] In this case we expect the delays of the L-to-one MUXes and the ALUs to dominate in comparison to the 2-to-1 MUX. (There are some mathematical transformations of the above instruction sequence to reduce the data dependency chain to logarithmic time as well. Such transformations could be implemented in hardware, but they are beyond the scope of this document. One such mechanism is described in [13].) Also, in this case, since the program has no parallelism, we would do just as well to use a 4-stage RISC pipeline of the sort found in late 1980's RISC processor.

[0454] Since our goal is to do well on programs that have parallelism, let us define the critical-path length, c, of an instruction sequence to be the maximum number of ALUs traversed through any path through the datapath, as set up by the switches for that instruction sequence. The critical-path length is a fundamental property of the instruction sequence and not an artifact of the details of the datapath.

[0455] Consider this instruction sequence which adds together the registers R₁through R₁₆, storing the result in R₁.

[0456] R1=R1+R2;

[0457] R3=R3+R4;

[0458] R5=R5+R6;

[0459] R7=R7+R8;

[0460] R9=R9+R10;

[0461] R11=R11+R12;

[0462] R13=R13+R14;

[0463] R15=R15+R16;

[0464] R1=R1+R3;

[0465] R5=R5+R7;

[0466] R9=R9+R11;

[0467] R13=R13+R15;

[0468] R1=R1+R5;

[0469] R9=R9+Ri3;

[0470] R1=R1+R9;

[0471] The switching graph for this sequence is shown in FIG. 46. Here there are 15 instructions, and the critical-path length is 4. If we do everything right, we should be able to exploit an average parallelism of 15/4=3.75 for this instruction sequence.