General purpose dichotomic search method is often requested by designers when they want to find a specific element (voltage, current, parameter value ...) in an already sorted set. For example, a typical problem that makes extensive use of this kind of algorithm is the computation of setup and hold time for cell characterization. This problem was already discussed in two articles [1] and [2] and a solution was proposed with the use of the SmartSpice Script Language and .MODIF statement.

Continuing on the same kind of example, this article describes a new approach now available in Smartspice which offers significant improvement in terms of speed. The syntax used in the input deck is very close to the one of the optimizer. Therefore the complexity of the parser was absolutely not increased. Of course the powerful .MEASURE statement is also used in conjunction for the definition of the criterions that will lead the dichotomic search.

Example of Dichotomic Search for Latch Setup Time Computation

As already defined in [1], the setup time of a latch is the minimum time, prior to the clock edge, that the input must remain stable to ensure reliable device operation.

If we know the exact time of the clock edge, it is possible to find the setup time by varying the input edge time in a user defined interval. This interval has to be chosen properly : that means that with its minimum value the latch must operate properly (PASS), with its maximum value the latch can?t behave properly (FAIL).

To determine whether the test Fails or Passes, one or several .MEASURE statements have to be specified by the user.

Knowing the interval and the .MEASURE criterion the dichotomic search can begin. The initial guess for the parameter is either given by the user or calculated as MIN + (MAX - MIN)/2. This is the starting point for the dichotomic algorithm. Depending on the result of the first test, PASS or FAIL, then a new interval is calculated with the initial guess becoming the MIN or MAX respectively. Then the second guess is again MIN + (MAX - MIN)/2 and so on... Thus at each step the time interval is divided by 2.

The last parameter that the user needs to specify is the accuracy requested for the result. The algorithm will stop when the interval becomes smaller than the accuracy :

(MAX ? MIN)/2^n < ACCURACY

In the example below the behavior of the latch is approximated with an A-device. The output V(latch) is equivalent to V(inp) if the parameter is > 100e-12. This value of 100p is the solution the method should find with the required accuracy :

**** DICHOTOMIC ALGORITHM EXAMPLE *** .PARAM delaytime = 1e-12 .PARAM otherparam = 1 Vin inp 0 PWL 0 5 delaytime 5 ?delaytime + 4e-12? 0 Rin inp 0 10K A1 latch 0 V = if delaytime > 100e-12 then V(inp) else 0 R1 latch 0 10K .TRAN 20e-12 3e-8 .MEASURE TRAN result CROSS v(latch) VAL=3 .MODIF + OPTIMIZE + delaytime = OPT ( 0 5000p 150p ) + otherparam = OPT ( 1 2 1.5 ) $ parameter not used -> Warning generated + TARGETS result = 2 + OPTIONS passfail = -1e-12 .END

All the important parameters are specified in the .MODIF statement with a syntax close to the optimizer one. The difference comes from the OPTIONS parameter : "PASSFAIL". If this option is not specified the normal optimizer is called, if it is specified, the new dichotomic search algorithm is called.

PARAMETERS:

In this example two parameters are specified : DELAYTIME and OTHERPARAM, but only the first one, DELAYTIME, will be used. The two parameters will be parsed without any problem, but at the run time, a warning is generated explaining that only one parameter is used in this method.

The specification of delaytime requires two or three parameters :

either Opt ( MIN MAX INIT ) like in this example
or Opt ( MIN MAX ) and then INIT is then calculated as MIN + ( MAX ? MIN )/2

TARGETS:

Parameters specified as targets must be the result of an existing .MEASURE statement. If, after a simulation, the measurement can?t be done, an error message appears and the test is considered FAILED. If the measurement can be achieved, whatever the value found, the test is considered PASSED.

The option "OFF" on the .MEASURE line is not supported with this algorithm. (Option "PROFF" is still available on the modif line and has the same effect). A non zero value has to be specified for the targets ( here RESULT = 2 ). This value is absolutely never used, but this is kept unchanged to avoid complicating the parser and to give flexibility for future improvements.

Several targets can be specified, and the test will be considered FAILED if all the targets fail, and will be considered PASSED if at least one target passes.

OPTIONS:

As mentioned above the only important option is PASSFAIL which makes the difference between traditional optimizer and new dichotomic search method. But, very important is the absolute value of this option ( in this case 1e-12 ), which represent the accuracy requested for the final result.

The sign of the PASSFAIL parameter is also very important, it makes the difference between two opposite situations PASS-FAIL or FAIL-PASS. The sign needs to be chosen like the following:

-1- PASSFAIL > 0 means : for parameter = MIN -> test PASS and for parameter = MAX -> test FAIL

-2- PASSFAIL < 0 means : for parameter = MIN -> test FAIL and for parameter = MAX -> test PASS

End of Search

The binary search process stops when the search interval becomes smaller than the accuracy, then the final value is displayed.

Figure 1 shows the 6 first steps of the search. The final value is surrounded step by step more and more accurately.

If, during the process, the tests FAILED ( or PASSED ) at every steps, then a particular warning is generated to inform the user. In fact a situation like that occurs if the sign of the PASSFAIL options is not properly chosen, if the searched value is outside the MIN and MAX boundaries or if there is a problem with the .MEASURE statement. Nevertheless, if the value searched is very close to the MIN or MAX of the interval, the final value may also be correct. Anyway, even in this case, in addition to the warning, the final result is displayed.

Figure 1. Six first steps of the dichotomic search

Conclusion

This article has explained the use of the new SmartSpice dichotomic algorithm through one typical example of latch characterization.

In addition to speed improvement, it is important to mention that all traditional .MODIF general options ( prtbl, proff ... ) are available with the method. All the flexibility of the .MODIF statement is retained. For example, it is still possible to define multiple sets of parameter variations.

The example of Latch Setup time is representative of the use of this feature but of course this new method is general purpose and can be used for many other applications.

References

[1] "Cell Characterization using the .MODIF Statement in 
SmartSpice", Simulation Standard, Vol. 9, No. 7, pp 12-13, January 1998. 

[2] "Advanced Cell Characterization using SmartSpice Scripting Features", Simulation 
Standard, Vol.9, No. 4, pp 6-7, April 1998.