Sun Microsystems, Inc.

Oracle International Corporation

Oracle America, Inc.

Josephus Ebergen

Ivan E Sutherland

Christopher Hans Olson

Robert J Drost

Jeffrey S Brooks

Paul N Loewenstein

Ali Vahidsafa

William Stuart Coates

Scott M Fairbanks

Hesam Fathi Moghadam

Danny Cohen

Sheueling Chang Shantz

Matthew Cohen

Navaneeth P Jamadagni

Damien Walker

Priyambada Mitra

Andrew Brock

Ishwardutt Parulkar

Ilyas Elkin

Ian W Jones

Mark R Greenstreet

David Lawrence Rager

Jon Lexau

Austin Lee

Jonathan K Gainsley

Austin A T Lee

Adam Megacz

Dmitry Nadezhin

Dmitry Nadehzin

A cache coherence system manages both internode and intranode cache coherence in a cluster of nodes. Each node in the cluster of nodes is either a collection of processors running an intranode coherence protocol between themselves, or a single processor. A node comprises a plurality of coherence ordering units (COUs) that are hardware circuits configured to manage intranode coherence of caches within the node and/or internode coherence with caches on other nodes in the cluster. Each node contains one or more directories which tracks the state of cache line entries managed by the particular node. Each node may also contain one or more scoreboards for managing the status of ongoing transactions. The internode cache coherence protocol implemented in the COUs may be used to detect and resolve communications errors, such as dropped message packets between nodes, late message delivery at a node, or node failure. Additionally, a transport layer manages communication between the nodes in the cluster, and can additionally be used to detect and resolve communications errors.

Fault-tolerant cache coherence over a lossy network

Control circuitry coupled to a multiply unit which includes a plurality of stage, each of which may be configured to perform a corresponding arithmetic function, may be configured to retrieve a given entry from a lookup table dependent upon a first portion of a binary representation of an input operand. An error value of an error function evaluated dependent upon a lookup value in a given entry of the plurality of entries is included in a predetermined error range. The control circuitry may be further configured to determine an initial approximation of a result of an iterative arithmetic operation using the first entry and initiate the iterative arithmetic operation using the initial approximation and the input operand.

Methods for constructing lookup tables for division and square-root implementations

Embodiments of a processor are disclosed for performing arithmetic operations on a machine independent number format. The processor may include a floating point unit, and a number unit. The number format may include a sign/exponent block, a length block, and multiple mantissa digits. The number unit may be configured to perform an operation on two operands by converting the digit format of each mantissa digit of each operand, to perform the operation using the converted mantissa digits, and then to convert each mantissa digit of the result of the operation back into the original digit format.

Floating point unit with support for variable length numbers

A multiplier unit may be configured to generate a final approximation of an iterative arithmetic operation performed on two operands. Circuitry coupled to the multiplier unit may perform a shift operation and a mask operation on the final approximation to generate shifted and un-shifted approximations, respectively. The circuitry may generate a first remainder using the un-shifted approximation and a sign value of a second remainder using the first remainder. Using the sign value of the second remainder, the circuitry may perform a rounding operation on the shifted approximation to generate a final answer.

Iterative division with reduced latency

The disclosed embodiments disclose techniques for performing quotient selection in an iterative carry-save division operation that divides a dividend, R, by a divisor, D, to produce an approximation of a quotient, Q=R/D. During a divide operation, a divider approximates Q by iteratively selecting an operation to perform for each iteration of the carry-save division operation and then performing the selected operation. The operation for each iteration is selected based on the current partial sum bits of a partial remainder in carry-save form (rs) and the current partial carry bits of a partial remainder in carry-save form (rc). More specifically, the operation is selected from a set of operations that includes: (1) a 2X* operation; (2) an S1 & 2X* operation; (3) an S2 & 2X* operation; (4) an A1 & 2X* operation; and (5) an A2 & 2X* operation.

Performing quotient selection for a carry-save division operation

The disclosed embodiments disclose techniques for using a split division circuit that includes a first divider that is optimized for a first range of divisor values and a second divider that is optimized for a second range of divisor values; the first range is distinct from the second range. During operation, the circuit receives a divisor for the division operation. The circuit: determines whether the divisor is in the first range or the second range to determine whether the first divider or the second divider should perform the division operation; performs the division operation in the selected host divider; and then outputs the result that was generated by the selected host divider.

Performing a division operation using a split division circuit

The disclosed embodiments facilitate converting binary values into the BCC format. One technique facilitates the direct conversion of binary numbers into BCC. A second variation first converts a binary number into an intermediate BCD value, and then converts that BCD value into a BCC value. Look-ahead comparators can further improve conversion performance by decreasing the latency of the conversion operation. By speeding up the conversion of binary values to decimal-format values, the disclosed techniques facilitate leveraging dedicated binary-format hardware for decimal-format operations, and thus improve the performance of decimal-format operations.

Converting binary values into binary-coded-centimal values

One embodiment of the present invention provides a system that regulates communications between a plurality of transmitters and a receiver. The system comprises a plurality of cells, wherein each cell controls communications from a transmitter in the plurality of transmitters to the receiver. A single token flows through a ring which passes through the plurality of cells, wherein the presence of the token within a cell indicates that the corresponding transmitter may communicate with the receiver.

Method and apparatus for regulating communications between multiple transmitters and receivers

The disclosed embodiments provide a first-in, first-out (FIFO) circuit that operates asynchronously. The FIFO circuit includes a data path that contains data latches sequentially connected through data-wire segments. The FIFO circuit also includes a control circuit that generates control signals for the data latches so that the data path behaves like a FIFO. The control circuit includes control components sequentially connected to each other through control-wire segments and repeaters located within the control-wire segments. The control components are configured to asynchronously generate the control signals for the data latches, and the repeaters are configured to repeat asynchronous signals communicated between the asynchronous control components.

Asynchronous FIFO circuit for long-distance on-chip communication

The disclosed embodiments relate to an asynchronous down counter, which can be loaded with any value N and then decrement exactly N times. The counter comprises an array of cells, wherein each cell is configured to hold a digit in a redundant base-k representation of a number contained in the array of cells. Each cell further comprises a finite state machine that defines state transitions between states, where these states are held on wires and state transitions are synchronized between neighboring cells. Each cell is further configured to asynchronously borrow, if possible, from a more significant adjacent cell to increase a value of a digit in the cell. This asynchronous borrowing improves performance by ensuring that a decrement operation, which decrements a digit in a least significant cell in the array, will borrow from an adjacent more significant cell, without having to wait for the completion of a rippling sequence of borrows from more significant cells.

Asynchronous loadable down counter

A method and apparatus for test of asynchronous pipelines. An asynchronous data pipeline includes first and second pluralities of pipeline stages in an alternating sequence. Each of the pipeline stages includes a control circuit, a latch circuit configured to latch data responsive to an indication from the control circuit, and a combinational logic circuit coupled to receive data from an output of the latch circuit. Each of the latch circuits is scannable. The latch circuits of the first and second pluralities of pipeline stages form a data scan chain configured to load test data into the combinational logic circuits during testing of the data pipeline. The data pipeline further includes a control scan chain configured to load control data for operating the control circuits during testing of the data pipeline. Testing of the data pipeline can include independent testing of the control portion or the data portion.

Method and apparatus for test of asynchronous pipelines

One embodiment of the present invention provides a system that performs a carry-save division operation that divides a numerator, N, by a denominator, D, to produce an approximation of the quotient, Q=N/D. The system approximates Q by iteratively selecting an operation to perform based on higher order bits of a remainder, r, and then performing the operation, wherein the operation can include, subtracting D from r and adding a coefficient c to a quotient calculated thus far q, or adding D to r and subtracting c from q. These subtraction and addition operations maintain r and q in carry-save form, which eliminates the need for carry propagation and thereby speeds up the division operation. Furthermore, the selection logic is simpler than previous SRT division implementations, which provides another important speed up.

Method and apparatus for performing a carry-save division operation

One embodiment of the present invention provides a system for high-throughput asynchronous communication that includes a sender and a receiver. A sender's first-in, first-out (FIFO) buffer is coupled to an input of the sender, a receiver's FIFO buffer is coupled to an input of the receiver, a forward communication channel is coupled between the sender and the receiver's FIFO buffer, and a reverse communication channel is coupled between the receiver and the sender's FIFO buffer. The forward communication channel, the receiver's FIFO buffer, the reverse communication channel, and the sender's FIFO buffer operate collectively as a network FIFO between the sender and the receiver. The network FIFO is configured to ensure that asynchronous communication between the sender and the receiver takes place reliably and without unnecessary waiting by the sender or the receiver.

Growing community of inventors

San Francisco, CA, United States of America

Josephus Ebergen