Report.dvi

We describe two extensions of CLP( ), motivated by an application to model- based diagnosis of active analog lters. The rst extension addresses the problem of rounding errors in CLP( ). We represent eals with oating-point intervals which are computed by outward rounding. The second extension increases the expressive- ness of linear CLP( ). Constants in linear expressions can now be intervals, which enables reasoning with imprecise model parameters (tolerances). Bounds ( ) for individual variables are computed by the linear optimization via modi ed Simplex. Both extensions are implemented in a CLP shell | an adaptation of SIC- Stus Prolog, which allows for easy and fast developments and modi cations of CLP 1 IntroductionThe motivation for this work was the idea to use CLP( ) for the simulation and diagnosis of analog circuits. First experiments Mozetic et al., 1991] showed that CLP( ) has some advantages over classical simulation tools (like SPICE or Micro-CAP) since the same model can be used for both, simulation and diagnosis. CLP( ) can locate potential soft faults, i.e., parameter values (resistors, capacitors) deviating from nominal values. Recently Novak et al., 1993] this was combined with the design-for-test (DFT) methodology Soma, 1990] in order to be able to distinguish between previously indistinguishable faults. The idea of the DFT methodology is to introduce MOS switches into a circuit in order to increase its Experiments with the simulation and diagnosis of analog circuits very soon revealed the oating-point problems of CLP( ). A potential solution of using CLP( ) instead of CLP( ) is not practical. In our particular experiments CLP( ) turned out to be 100 times slower then CLP( ) and needed considerably more space. What we tried next, and what we describe in this paper, is to extend CLP( ) by real intervals.
Real intervals were already incorporated in CLP languages, e.g., in BNR Prolog Older and Vellino, 1990, Older and Vellino, 1992] and in ICLP( ) Lee and van Emden, 1992]. The main motivation there is the control of rounding errors, and the ability to resolve nonlinear constraints. The mechanism for doing this is a new type of variables called an interval. A variable is initialized to an interval which subsequently narrows as more constraints on the variable are imposed. The constraint satisfaction mechanism for narrowing is based on local constraint propagation. It is non-symbolic and resembles a classical iterative numerical approximation technique.
In contrast, existing CLP( ) Ja ar and Michaylov, 1987] implementations are limited to systems of linear (in)equations and use symbolic (in)equation solving techniques. Here, variables which gure in inequalities can be interpreted as intervals. Their bounds (sup and inf) are not explicit, but can be computed by the Simplex optimization.
We introduce an extension to CLP( ) where generalized constants can be used. A generalized constant is an ordered pair of oating-point numbers, de ning the lower and upper bound of an interval which contains the original constant. These intervals are not narrowed during the computation | their ranges, however, have an e ect on the variables.
Originally ground variables might become just constrained (bound between sup and inf), and originally constrained variables might get looser bounds. The motivation for having The representation of eals by oating-point intervals in order to cure the rounding problems. These generalized constants cannot be speci ed by the user | they are introduced by the low level numerical evaluator as a result of outward rounding.
The increased expressive power of linear CLP( ) by retaining the advantages of symbolic techniques. In this case, the generalized constants are introduced by the user in order to model parameter tolerances.
2 Outward roundingThe CLP shell Holzbaur, 1992] we are using for our experiments is an extension of SICStus Prolog Carlsson and Widen, 1991]. Various CLP instances themselves are implemented in Prolog and coded in a rather modular fashion. This coding discipline, together with the relative ease of applying partial evaluation to declarative programs, makes it possible to replace the numeric evaluator which works at the bottom of every CLP( tion. In fact, our CLP( ) and CLP( ) implementations share 99% of the code. The only di erence besides some special case analyses that stem from the nite precision of oating- point numbers, is the numeric evaluator which computes with oating-point numbers in the case of CLP( ), and with normalized rational numbers in the case of CLP( ).
We implemented an outward rounding evaluator which returns a pair of oating-point numbers for each arithmetic expression involving (simple of generalized) constants. The pair encloses the actual results of the computation as tight as possible within the space of (hardware) representable oating-point numbers.
Although this evaluator is speci ed as a Prolog predicate, there is no call overhead during the execution of the resulting system, because we unfold references to the evaluator predicate. This is such a simple instance of partial evaluation, that we have no need for the power of a general partial evaluator. This leads us to unfolding e ciency | which is no issue after all because this process only takes place once when the CLP system is 3 Generalized constantsReplacing scalars, i.e., constants and coe cients in linear equations, by pairs of constants denoting lower and upper bound, allows one to model additional properties of parameters such as tolerances. This can be modelled directly in CLP( ). Take, for example, the Assume that and are generalized constants with given bounds: Each factor with a generalized coe cient can be replaced by a fresh variable and two A generalized coe cient requires a case analysis (2 or 3). This can be executed directly by CLP( ) (through backtracking), but the complexity is of course exponential in the number We propose a two pass solution. In the rst pass, mean values of generalized constants are taken, yielding ground or (in general) constrained solutions for the variables: In the second pass, these mean solutions are used to resolve the cases (2 or 3), and looser bounds on the original variables are computed. This two-pass technique is e ectively realized by the freeze mechanism Carlsson and Widen, 1991], by delaying (2, 3) on X1 until it is su ciently constrained. The technique is sound but incomplete. In general, a solution to the system of linear equations with generalized constants yields a set of bounds (interpreted as intervals) for each variable. The proposed technique nds just one interval, expanded around the ground solution, computed in the rst pass from the mean values.
The question arises: \Why shouldn't one use the low level outward rounding evaluator to deal with all generalized constants (needed internallyand introduced by the user) ?" The evaluator works under the assumption that terms submitted for evaluation are independent, even when several represent the same constant. This is the well know `variable (constant) identity' problem. As a consequence, the tightness of the computed bounds is suboptimal.
Therefore, to make these identities explicit, fresh variables with associated inequalities are 4 An exampleWe illustrate various interval handling techniques by a simple example of two resistors in a series (Figure 1). Both resistors and given voltages have tolerances. The goal is to compute the voltage and current ranges at the node between the resistors.
Figure 1: Two resistors with tolerances in a series.
The following CLP( ) program speci es the circuit: of generalized constants, and is bound between lower and upper bounds of generalized constants. The following code speci es the assignment of a generalized constant to a variable, and the multiplication of a generalized constant by a variable: The multiplicationof a generalized constant to a variable is delayed until is ground. This reduces backtracking, but misses some solutions. The correct (but less e cient) de nition of the bounds predicate should test the sign of instead of .
The rst query illustrates how the outward rounding is used to compute the mean solution, i.e., and are computed from the mean values of generalized constants. Instead of a single oating-point number, the result is a pair of oating-point numbers which I = 0.00083333333333333328, 0.0008333333333333335], V = 11.249999999999999, 11.250000000000002] The same mechanism applied to the actual generalized constants (instead of their mean values) yields a naive block, i.e., an interval in two dimensions. However, due to the `con- stant identity' problem the block contains a considerable number of impossible solutions I = ( 11,14] { 8,12])/( 1000,2000] + 1000,2000]), I = {0.00050000000000000001, 0.0030000000000000001], V = 4.9999999999999992, 15.000000000000002] Figure 2: Interval ranges for the two resistors example.
If we consider the generalized constants then the actual solution polyhedron is deter- mined by a set of inequalities. Through backtracking, CLP( ) returns two solutions, It is convenient to represent the polyhedron by the smallest block which contains it. In CLP( ) this can be done by computing inf and sup of each variable involved: The proposed two pass technique (with mean values and freeze) computes in the rst pass the mean solutions, and in the second pass the block around the mean solution (Fig- 0, in the missed block) is not computed, since there 5 DiscussionFrom the CLP( ) solver's point of view the proposed technique amounts to an additional workload because of the two inequalities added for each constant or coe cient being gen- eralized. While we are pleased with the additional modelling power of our system, we are not satis ed with the overall performance. Our current explanation is the following.
We decide the satis ability of systems of inequalities by an incremental version of the Simplex Dantzig, 1963] algorithm. The current version does not take advantage of special properties of the submitted inequalities.
One such property is the dimension (= number of variables) of the inequalities. There are variants of the Simplex algorithm which perform the costly basis transformations only for equations in more than one variable, i.e., simple upper and lower bounds on variables are treated specially (bounded variable linear programs Murty, 1976]). Note that this restriction on the syntactical form of inequalities is local in the sense that it does not restrict the number of variables in the other inequalities of a system. This is in contrast to the global restrictions imposed by TVPI algorithms Cohen and Megiddo, 1991].
Special treatment of inequalities of low dimension also facilitates the detection of re- dundant inequalities. For simple bounds this is an evaluable test, for inequalities in more dimensions one can (sometimes)detect syntactic redundancy by sorting Lassez et al., 1989] or hashing Pugh, 1991]. In general, however, one has to run linear optimization programs Therefore we plan to incorporate specializations for inequalities of low dimension into the decision algorithm for inequalities.
AcknowledgementsThe authors acknowledge the support of the Austrian "Fonds zur Forderung der wis- senschaftlichen Forschung" under grant P9426-PHY. Austrian Research Institute for Arti- cial Intelligence is supported by the Austrian Federal Ministry of Science and Research.
Carlsson and Widen, 1991] Carlsson, M., Widen, J. SICStus Prolog user's manual.
Swedish Institute of Computer Science, Kista, Sweden, 1991.
Cohen and Megiddo, 1991] Cohen, E., Megiddo, N. Improved algorithms for linear in- equalities with two variables per inequality. IBM Research Report, RJ 8187 (75146), Dantzig, 1963] Dantzig, G.B. Linear Programming and Extensions. Princeton University Holzbaur, 1992] Holzbaur, C. DMCAI CLP reference manual. Report TR-92-24, Austrian Research Institute for Arti cial Intelligence, Vienna, Austria, 1992.
Ja ar and Michaylov, 1987] Ja ar, J., Michaylov, S. Methodology and implementation of a CLP system. Proc. 4th Intl. Conf. on Logic Programming, pp. 196-218, Melbourne, Lassez et al., 1989] Lassez, J.L., Huynh, T., McAloon, K. Simpli cation and elimination of redundant linear arithmetic constraints. Proc. North American Conf. on Logic Pro- gramming 1989, pp. 35-51, Cleveland, MIT Press, 1989.
Lee and van Emden, 1992] Lee, J.H.M, van Emden, M.H. Adapting CLP( ) to oating- point arithmetic. Proc. Intl. Conf. on Fifth Generation Computer Systems, pp. 996- Mozetic et al., 1991] Mozetic, I., Holzbaur, C., Novak, F., Santo-Zarnik, M. Model-based analogue circuit diagnosis with CLP( ). Proc. 4th Intl. GI Congress, pp. 343-353, Murty, 1976] Murty, K.G. Linear and Combinatorial Programming. Wiley, New York, Novak et al., 1993] Novak, F., Mozetic, I., Santo-Zarnik, M., Biasizzio, A. Enhancing design-for-test for active analog lters by using CLP( ). Analog Integrated Circuits and Signal Processing, to appear, 1993.
Older and Vellino, 1990] Older, W., Vellino, A. Extending Prolog with constraint arith- meticon real intervals. Proc. Canadian Conf. on Electrical and Computer Engineering, Older and Vellino, 1992] Older, W., Vellino, A. Constraint arithmetic on real intervals.
In Constraint Logic Programming: Selected Research (F. Benhamou, A. Colmerauer, Pugh, 1991] Pugh, W. The Omega test: a fast and practical integer programming algo- rithm for dependence analysis. Proc. of Supercomputing, 1991.
Soma, 1990] Soma, M. A design-for-test methodology for active analog lters. Proc. IEEE Intl. Test Conf. 1990, pp. 183-192, Washington D.C., IEEE, 1990.

Source: http://ponta.ijs.si/mozetic/papers/oefai-tr-93-19.pdf