Using Bisection

To use bisection, the following is required:

• A user-specified pair of upper and lower boundary input variable values. For a solution to be found, one of these values must result in an output variable result
|goal value| and the other in a result < |goal value|

• Specified goal value
• Error tolerance value. The bisection process stops when the difference between successive test values <= error tolerance. If the other criteria are met, see below.
• Related variables. Variables must be related by a monotonic transfer function, where a steadily progressing time (increase or decrease) results in a single occurrence of the "goal" value at the "target" input variable value

The error tolerance is included in a relation used as a process-termination criterion.

Bisection Example for Three Iterations shows an example of the binary search process used by the bisection algorithm. This example is of the "pass/fail" type, and is appropriate for a setup-time analysis that tests for the presence of an output transition as shown in Determining Setup Time with Bisection Violation Analysis. Here, a long setup time TS (= T2 - T1 ) results in a VOUT transition (a "pass"), and a too-short setup time (where the latch has not stabilized the input data before the clock transition) results in a "fail." A "pass" time value, for example, might be defined as any setup time TS that produces a VOUT output "minimum high" logic output level of 2.7 V - the "goal" value . The "target" value is that setup time that just produces the V OUT value of 2.7 V. Since finding the exact value is impractical, if not impossible, an error tolerance is specified to give a solution arbitrarily close to the target value. The bisection algorithm performs tests for each of the specified boundary values to determine the direction in which to pursue the target value after the first bisection. In this example, the upper boundary value is a "pass" value, and the lower boundary value is a "fail" value.

To start the binary search, a lower boundary and upper boundary are specified. The program tests the point midway between the lower and upper boundaries (see Bisection Example for Three Iterations).

If the initial value passes the test, the target value must be less than the tested value (in this case), so the bisection algorithm moves the upper search limit to the value it just tested. If the test fails, the target value must greater than the tested value, so the bisection algorithm moves the lower limit to the value it just tested.

Then the algorithm tests a value midway between the new limits. The search continues in this manner, moving one limit or the other to the last midpoint, and testing the value midway between the new limits. The process stops when the difference between the latest test values is less than or equal to the user-specified error tolerance (normalized by multiplying by the initial boundary range).

Examining the Command Syntax

.MODEL <OptModelName> OPT METHOD=BISECTION ...

or

.MODEL <OptModelName> OPT METHOD=PASSFAIL ...

OptModel- The model to be used. Refer to Statistical Analysis and Optimization for Name information on specification of optimization models in Star-Hspice.

METHOD Keyword to indicate which optimization method to use. For bisection, the method may be one of the following:

BISECTION

When the difference between the two latest test input values is within the error tolerance and the latest measured value exceeds the goal, bisection has succeeded, and stops. The process reports the optimized parameter that corresponded to the test value that satisfies this error tolerance, and this goal (passes).

PASSFAIL

When the difference between the two latest test input values is within the error tolerance and one of the values >= goal (passes) and the other fails, bisection has succeeded and stops. The process reports the value the input parameter value associated with the "pass" measurement.

OPT Keyword to indicate optimization is to be performed

The parameters are passed in a normal optimization specification:

.PARAM <ParamName>=<OptParFun> (<Initial>, <Lower>, <Upper>)

In the BISECTION method, the measure results for <Lower> and <Upper> limits of <ParamName> must be on opposite sides of the GOAL value in the .MEASURE statement. For the PASSFAIL method, the measure must pass for one limit and fail for the other limit. The process ignores the value of the <Initial> field.

The error tolerance is a parameter in the model being optimized.

Note that the bisectional search is applied to only one parameter.

When the OPTLST option is set (.OPTION OPTLST=1), the process prints the following information for the BISECTION method:

bisec-opt iter = <num_iterations> xlo = <low_val> xhi = <high_val>

x = <result_low_val> xnew = <result_high_val>

err = <error_tolerance>

where x is the old parameter value and xnew is the new parameter value.

When .OPTION OPTLST=1, the process prints the following information for the PASSFAIL method:

bisec-opt iter = <num_iterations> xlo = <low_val> xhi = <high_val>

x = <result_low_val> xnew = <result_high_val>

measfail = 1

(measfail = 0 for a test failure for the x value).

Example: transient analysis .TRAN statement:

.TRAN <TranStep> <TranTime> SWEEP OPTIMIZE=<OptParFun>

+ RESULTS=<MeasureNames> MODEL=<OptModelName>

Example: transient .MEASURE statement:

.MEASURE TRAN <MeasureName> <MeasureClause> GOAL=<GoalValue>