Cycle segmented prefix circuits

• US 6,609,189 B1
• Filed: 03/12/1999
• Issued: 08/19/2003
• Est. Priority Date: 03/12/1998
• Status: Expired due to Fees

• Current Assignee: Yale University
• Original Assignee: Yale University
• Inventors: Kuszmaul, Bradley C., Henry-Kuszmaul, Dana Sue
• Primary Examiner(s): Pan, Daniel H.
• Application Number:
  US09/267,827
• Time in Patent Office: 1,621 Days
• Field of Search: 712/1, 712/2, 712/3, 712/7, 712/8, 712/9, 712/16, 712/23, 712/221, 712/12, 702/300, 702/201, 702/10, 702/36, 702/23, 702/19, 702/18, 702/17, 702/25, 702/27, 702/26, 702/38, 702/212, 702/129, 702/29, 702/35, 702/34, 708/682, 708/505, 708/506, 708/421, 708/503, 708/517, 708/504, 708/521, 708/632, 708/534, 341/67, 341/76, 341/93, 375/359, 710/12, 710/21, 710/33, 710/38, 710/51, 710/72, 710/111, 710/130, 710/243, 710/125, 710/126
• US Class Current: 712/23
• CPC Class Codes: G06F 2207/5063 2-input gates, i.e. only using 2-input logical gates, e.g. binary carry look-ahead, e.g. Kogge-Stone or Ladner-Fischer adder
• CPC Class Codes: G06F 7/506 with simultaneous carry generation for, or propagation over, two or more stages
• CPC Class Codes: G06F 9/3802 Instruction prefetching
• CPC Class Codes: G06F 9/3836 Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution
• CPC Class Codes: G06F 9/3838 Dependency mechanisms, e.g. register scoreboarding
• CPC Class Codes: G06F 9/384 Register renaming
• CPC Class Codes: G06F 9/3844 using dynamic branch prediction, e.g. using branch history tables
• CPC Class Codes: G06F 9/3854 Instruction completion, e.g. retiring, committing or graduating
• CPC Class Codes: G06F 9/3856 Reordering of instructions, e.g. using queues or age tags
• CPC Class Codes: G06F 9/3858 Result writeback, i.e. updating the architectural state or memory
• CPC Class Codes: G06F 9/3867 using instruction pipelines
• CPC Class Codes: G06F 9/3869 Implementation aspects, e.g. pipeline latches; pipeline synchronisation and clocking
• CPC Class Codes: G06F 9/3885 using a plurality of independent parallel functional units

Abstract

The poor scalability of existing superscalar processors has been of great concern to the computer engineering community. In particular, the critical-path delays of many components in existing implementations grow quadratically with the issue width and the window size. This patent presents a novel way to reimplement these components and reduce their critical-path delay growth. It then describes an entire processor microarchitecture, called the Ultrascalar processor, that has better critical-path delay growth than existing superscalars. Most of our scalable designs are based on a single circuit, a cyclic segmented parallel prefix (cspp). We observe that processor components typically operate on a wrap-around sequence of instructions, computing some associative property of that sequence. For example, to assign an ALU to the oldest requesting instruction, each instruction in the instruction sequence must be told whether any preceding instructions are requesting an ALU. Similarly, to read an argument register, an instruction must somehow communicate with the most recent preceding instruction that wrote that register. A cspp circuit can implement such functions by computing for each instruction within a wrap-around instruction sequence the accumulative result of applying some associative operator to all the preceding instructions. A cspp circuit has a critical path gate delay logarithmic in the length of the instruction sequence. Depending on its associative operation and its layout, a cspp circuit can have a critical path wire delay sublinear in the length of the instruction sequence.

Claims

1. A circuit comprising:

a plurality of multiple input multiplexers and multiple input function generators connected in series,

each multiplexer having one input that is an identity function and an output that is selected by a segment bit, and

each function generator having one input that is output of the preceding multiplexer and an output that is an input to the next multiplexer, and

the output of the last function generator is connected as an input to the first multiplexer.

2. A circuit comprising:

a plurality of modules connected in a tree structure, each module comprising;

at least first and second function generators, first and second multiplexers and an OR gate,

a first input and a first output connecting the module to an output and an input, respectively, of a module closer to the root of the tree structure,

a second input and a second output connecting the module to an output and an input, respectively, of a module farther from the root of the tree structure and a third input and a third output connecting the module to an output and an input, respectively, of another module farther from the root of the tree structure,

a fourth and a fifth input providing segment bits to the module from modules farther from the root and a fourth output providing a segment bit to a module closer to the root,

said first and second inputs of each module being connected as inputs to the first function generator of that module and said second and third inputs being connected as inputs to the second function generator of that module,

the first multiplexer having a first input that is an output of the first function generator and a second input that is the second input to that module and the second multiplexer having a first input that is an output of the second function generator and a second input that is the third input to that module, the first and second multiplexers having outputs that are selected by segment bits on the fourth and fifth inputs, the first output of each module being derived from the second multiplexer and one of the second and third outputs being derived from the first multiplexer, and

the OR gate generating a logical OR of the fourth and fifth inputs and providing it to the fourth output, and

the first output of at least one module closest to the root of the tree structure being connected to the first input of a module closest to the root of the tree structure.

3. A prefix computation circuit comprising:

a plurality of input terminals to receive input data,

a circuit configuration to perform prefix computation based on said input data, and

a plurality of output terminals to provide output data based on said prefix computation,

wherein the prefix computation is cyclic and segmented.

4. The circuit of claim 3 wherein the prefix computation is performed serially.

5. The circuit of claim 3 wherein the prefix computation is performed in parallel.

6. The circuit of claim 3 wherein there are N input terminals.

7. A prefix computation circuit comprising:

a plurality of N input terminals to receive input data,

a circuit configuration to perform prefix computation based on said input data, and

a plurality of output terminals to provide output data based on said prefix computation,

wherein the prefix computation is cyclic and segmented, and

wherein the longest path through the circuit configuration is O (log N) circuit elements.

8. A prefix computation circuit comprising:

a plurality of input terminals to receive input data,

a circuit configuration to perform prefix computation based on said input data, and

a plurality of output terminals to provide output data based on said prefix computation,

wherein the prefix computation is cyclic and segmented, and

wherein the circuit configuration computes a cyclic segmented prefix using a plurality of modules in which at least one module is connected to each of a plurality of other modules via a child connection comprising an output connected to an input of a child module, a first input connected to a first output of the same child module, and a second input connected to a second output of the same child module, and the child connections are ordered so that each child connection has a predecessor child connection whereby if the second input from a child connection'"'"'s predecessor is true, then the output of the child connection is an identity value, and if the second input from a child connection'"'"'s predecessor is false, then the output of the child connection is the same value as a combination, by an associative function, of the first input of the predecessor child connection and the output of the predecessor child connection.

9. A circuit comprising:

a plurality of child modules and

at least one cyclic prefix module, having a plurality of child connections, each child connection comprising;

an output connected to an input of a child module,

a first input connected to a first output of the same child module, and

a second input connected to a second output of the same child module, the child connections being ordered so that each child connection has a predecessor child connection;

the cyclic prefix module further comprising a circuit which computes a cyclic segmented prefix, whereby if the second input from a child connection'"'"'s predecessor is true, then the output of the child connection is an identity value, and if the second input from a child connection'"'"'s predecessor is false, then the output of the child connection is the same value as a combination, by an associative function, of the first input of the predecessor child connection and the output of the predecessor child connection.

10. A circuit, as claimed in claim 9, in which there are N child modules and the cyclic prefix module comprises a circuit in which the longest path through the circuit is O(log N) circuit elements.

11. A circuit, as claimed in claim 9, wherein each child module comprises an input which encodes an input value, a first output which encodes an output value and a second output which encodes a boolean value.

12. A circuit, as claimed in claim 9, wherein each of the child connections is identified by a different number from 1 to N, and for each leaf connection numbered I, if I is less than N the child connection is called the predecessor of child connection number I+1, and if I equals N the child connection is called the predecessor of child connection number 1.

13. A circuit as claimed in claim 9, in which one of the at least one cyclic prefix modules has a root connection, the root connection comprising an output, and an input, the root output of the module connected to the root input of the module, whereby the module performs a segmented parallel prefix computation, in which if the second input of child connection N is true, then the root output is the identity value, and if the second input of child connection N is false, then the root output is the same value as a combination, by the associative function, of the first input of child connection N with the first input of child connection 1, and the output of child connection 1 is the same value as the root input, and for each child connection other than child connection 1, if the second input from the child connection'"'"'s predecessor is true, then the output of the child connection is the identity value, and if the second input from the child connection'"'"'s predecessor is false, then the output of the child connection is the same value as a combination, by the associative function, of the output of the child connection'"'"'s predecessor and the input of the child connection'"'"'s predecessor.

14. A circuit, as claimed in claim 13, organized as a tree-structured circuit in which the longest path through the circuit is O(log N) circuit elements.

15. A circuit comprising:

a plurality of leaf modules, each leaf module comprising;

an input which encodes an input value,

a first output which encodes an output value, and

a second output which encodes a boolean value;

a cyclic prefix module, having a plurality of leaf connections, each leaf connection comprising;

an output connected to the input of a leaf module,

a first input connected to the first output of the same leaf module, and

a second input connected to the second output of the same leaf module, there being a total of N leaf connections,

each leaf connection being identified by a different number from 1 to N and for each leaf connection numbered I, if I is less than N the leaf connection being called the predecessor of leaf connection number I+1, and if I equals N the leaf connection being called the predecessor of leaf connection number 1;

the cyclic prefix module further comprising a circuit which computes a cyclic segmented prefix, whereby if the second input from a leaf connection'"'"'s predecessor is true, then the output of the leaf connection is an identity value, and if the second input from a leaf connection'"'"'s predecessor is false, then the output of the leaf connection is the same value as a combination, by an associative function, of the first input of the leaf connection'"'"'s predecessor and the output of the leaf connection'"'"'s predecessor.

16. A circuit, as claimed in claim 15, organized as a tree-structured circuit in which the longest path through the circuit is O(log N) circuit elements.

17. A circuit as claimed in claim 15, in which one of the cyclic prefix modules has a root connection, the root connection comprising an output and an input, the root output of the module connected to the root input of the module, whereby the module performs a segmented parallel prefix computation, in which if the second input of child connection N is true, then the root output is the identity value, and if the second input of child connection N is false, then the root output is the same value as a combination, by the associative function, of the first input of child connection N with the first input of child connection 1, and the output of child connection 1 is the same value as the root input, and for each child connection other than child connection 1, if the second input from the child connection'"'"'s predecessor is true, then the output of the child connection is the identity value, and if the second input from the child connection'"'"'s predecessor is false, then the output of the child connection is the same value as a combination, by the associative function, of the output of the child connection'"'"'s predecessor and the input of the child connection'"'"'s predecessor.

18. A circuit, as claimed in claim 17, organized as a tree-structured circuit in which the longest path through the circuit is O(log N) circuit elements.