Understanding the Bisection Methodology

Bisection is a method of optimization that employs a binary search method to find the value of an input variable (target value) associated with a "goal" value of an output variable. The input and output variables may be of various types - for example, voltage, current, delay time or gain- related by some transfer function. In general, use a binary search to locate the output variable goal value within a search range of the input variable by iteratively halving that range to converge rapidly on the target value. At each iteration the "measured value" of the output variable is compared with the goal value. Bisection is employed in both the "pass/fail" method and the "bisection" method (see Using Bisection). The process is largely the same for either case.

The Star-Hspice bisection procedure involves two steps when solving the timing violation problem. First, the procedure detects whether the output transition occurred. Second, the procedure automatically varies the input parameter (T 1 in Determining Setup Time with Bisection Violation Analysis) to find the value for which the transition barely occurs. The Star-Hspice measurement and optimization features handle these two steps.

Measurement

Use the Star-Hspice MAX measurement function to detect success or failure of an output transition. In the case of a low-to-high output transition, a MAX measurement produces zero on failure, or approximately the supply voltage Vdd on success. This measurement, using a goal of Vdd minus a suitable small value to ensure a solution, is sufficient to drive the optimization.

Optimization

The bisection method is straightforward, given a single measurement with a goal and known upper and lower boundary values for the input parameter. The characterization engineer should be able to specify acceptable upper and lower boundary values.