Oracle has developed new implementations for integer division and floating-point division and square root. Our task was to verify the correctness of the new designs by formally proving equivalence between the RTL for these designs and their specifications in the SPARC ISA and in the IEEE 754 Standard on floating-point arithmetic. Performing such verifications involved many steps, which we describe in this paper. The contributions of this paper are two-fold. First, this paper describes Oracle's methodology for abstracting from low-level Verilog to a high-level algorithm using the latest open-source tools. Second, this paper describes the use of interval arithmetic in the error analysis of each algorithm. Our verification efforts proved that the designs had no errors, resulted in various improvements, and reduced the lookup tables by approximately 50% (division) and 75% (square root).

This paper presents a derivation of four radix-2 division algorithms by digit recurrence. Each division algorithm selects a quotient digit from the over-redundant digit set {-2, -1, 0, 1, 2}, and the selection of each quotient digit depends only on the two most-significant digits of the partial remainder in a redundant representation. Two algorithms use a two's complement representation for the partial remainder and carry-save additions, and the other two algorithms use a binary signed-digit representation for the partial remainder and carry-free additions. Three algorithms are novel. The fourth algorithm has been presented before. Results from the synthesized netlists show that two of our fastest algorithms achieve an improvement of 10 percent in latency per iteration over a standard radix-2 SRT algorithm at the cost of 36 percent more power and 50 percent more area.

One of the potential advantages of asynchronous circuits is that they can be optimized for average-case performance rather than worst-case performance. The performance analysis of asynchronous circuits, however, is more challenging than that of synchronous circuits because of the absence of a clock. We discuss some performance measures of special asynchronous networks, viz., response-time properties of asynchronous pipelines with various handshake communications. The response times of a pipeline are the delays between requests and succeeding acknowledgments for the first cell. We derive simple formulas for the bound on worst-case response time and average-case response time of such pipelines using a variable-delay model, where delays may vary between a lower and upper bound. The properties are independent of any particular implementation of the cells of the pipeline. The formulas give insight into the role of each parameter and allow a quick back-of-the-envelope prediction of the performance of an asynchronous pipeline.

Various applications have demonstrated that asynchronous circuits have great potential for energy-efficient and high-performance design. One of the primitives used in asynchronous control circuits is the C-element. Analytical delay and energy models are presented and applied to the most popular complementary metal-oxide-semiconductor (CMOS) implementations of the C-element. Optimization of these implementations are discussed. The implementations are also compared using simulations. The simulation results are in good agreement with the analytical predictions.

The C-element is one of the most frequently used primitives in asynchronous control circuits. This paper introduces various single-rail and double-rail implementations of the C-element, explains ways to optimize their performance and compares them with respect to energy and speed in a micropipeline control circuit environment. The issue of divergence of the complementary outputs in the double-rail implementations is also discussed.

One of the most frequently used primitives in asynchronous control circuits is the C-element. The three most popular CMOS implementations of the C-element are compared with respect to energy-efficiency, delay, and area, with an emphasis on energy. The three implementations have been introduced by Sutherland, Martin, and Van Berkel. We show that in a typical environment, Van Berkel's implementation is superior to the other implementations with respect to energy consumption and area, for the same delay.

In classical switching theory, asynchronous sequential circuits are operated in the fundamental mode. In this mode, a circuit is started in a stable state, and then the inputs are changed to cause a transition to another stable state. The inputs are not allowed to change again until the entire circuit has stabilized. In contrast to this, delay-insensitive circuits-the correctness of which is insensitive to delays in their components and wires-use the input-output mode. In this case, it is assumed that inputs may change again, in response to an output change, even before the entire circuit has stabilized. It is shown that such commonly used behaviors as those of the set-reset latch and Muller's C-ELEMENT do not have delay-insensitive realizations, if gates are used as the basic components. It is proved that no nontrivial sequential behavior with one binary input possesses a delay-insensitive realization using gates only. The proof makes use of the equivalence between ternary simulation and the general-multiple-winner model of circuit behavior.>