New Builtin Dichotomic Search Algorithm in Smartspice
Introduction
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 :
In the example below the behavior of the latch is approximated with an Adevice. The output V(latch) is equivalent to V(inp) if the parameter is > 100e12. This value of 100p is the solution the method should find with the required accuracy :

**** DICHOTOMIC ALGORITHM EXAMPLE ***
.PARAM delaytime = 1e12
.PARAM otherparam = 1
Vin inp 0 PWL 0 5 delaytime 5 ?delaytime + 4e12? 0
Rin inp 0 10K
A1 latch 0 V = if delaytime > 100e12 then V(inp) else 0
R1 latch 0 10K
.TRAN 20e12 3e8
.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 = 1e12
.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 1e12 ), 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 PASSFAIL or FAILPASS. 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 1213, January 1998.
[2] "Advanced Cell Characterization using SmartSpice Scripting Features", Simulation
Standard, Vol.9, No. 4, pp 67, April 1998.