Equivalence checking by an outsider is unsolvable even for combinational circuits and even in “a practical sense”

Here, I discuss some results on equivalence checking (EC) of circuits with a common specification. These results provide a strong evidence that external EC is unsolvable even for combinational circuits and even in “a practical sense”. I call EC external if it is performed by an outsider i.e. if no information is provided about the circuits N and N* to be checked for equivalence other than circuit description.  From a practical point of view, this  means that

·         Efficient external EC of N and N* is possible only if

·         these circuits are narrow, i.e. have small width and so have compact BDDs, 

·         or "almost identical" e.g. they have a lot of functionally equivalent internal points.

·         On the contrary, internal EC i.e. EC where some extra information is provided about the relation between N and N* can be efficient even if external EC is not.

·         A logic synthesis tool should preserve some constraints  (like toggle equivalence, see below) guaranteeing that EC can be done efficiently.  Similarly, a compiler parses a string of symbols based on a grammar , which, in a sense, is a bunch of constraints, rather than tries to understand this string according to some ever-growing set of  heuristics.

Below, I describe some results on EC and  explain my point of view in the Q&A session. Some questions are "real" and were asked explicitly or implicitly by reviewers and some I made up myself. (This is work in progress. I am going to add new questions and answers in the future .)

Brief introduction into EC of circuits with a common specification

The formulation of the EC problem can be found in [1]. Here, I discuss the "simplest version" of EC, namely the EC of combinational circuits.

Here is the main idea. Let N and N* be two single-output combinational circuits to be checked for equivalence. Let N and N* be partitioned into subcircuits N1,..., Nk and N*1,...,N*k respectively so that

 

A partition of N into subcircuits Ni is called a specification of N (denoted as Spec(N)). Circuits N and N* are said to have a common specification if subcircuits Ni and N*i, i=1,..,k satisfy the two conditions above.

Let circuits M and M* have identical sets of input variables. M and M* are said to be toggle equivalent if M(y) ≠ M(y') M*(y) ≠ M*(y'). That is for each pair of input assignments y and y' for which M toggles (i.e. produces different output assignments), M* toggles too and vice versa. (More about toggle equivalence can be found, for example, in [2]) Toggle equivalence of M and M* means that there is a one-to-one mapping between their output assignments. In other words, M and M* can be viewed as two different implementations of the same multi-valued function. Circuits N and N* with a common specification can be viewed as two different implementations of the same network of muti-valued gates (pair of subcircuits Ni and N*i being two different implementations of i-th multi-valued gate). Originally, we considered this (hypothetical) network of multi-valued gates as a common specification of N and N*. However, it is more convenient to view a partition of N (or N*) into subcircuits Ni (respectively N*i) as its specification.

Importantly, circuits N and N* with a common specification can be efficiently checked for equivalence if specifications of N and N* are known. The corresponding EC procedure can be found, for example, in [2]). (We will refer to this procedure as EC_TE where EC stands for Equivalence Checking and TE stands for Toggle Equivalence). The EC_TE procedure is linear in the number of subcircuits in Spec(N) and Spec(N*) and exponential in the granularity of Spec(N) and Spec(N*) (where the granularity of, say, Spec(N) is the size of its largest subcircuit Ni.) This means that if we consider a class of equivalence checking problems where granularities of Spec(N) and Spec(N*) are bounded by a constant, this class can be solved in linear time.

Along with paper [7], we call EC external if no extra information about circuits N and N* to be checked for equivalence is given. Otherwise, EC is called internal . So the EC_TE procedure is internal because Spec(N) and Spec(N*) provide extra knowledge about N and N*. This knowlege is exactly what makes EC_TE efficient. However, if specifications of N and N* are not known, then efficient EC of N and N* (if they are "wide" [3]) is most likely infeasible. (In other words, external EC of circuits with a common specification most likely cannot be done efficiently.) Our reasoning is as follows. If N and N* are "wide", one can not check their equivalence by building ,say, BDDs [4]. The only way to do the job efficiently is to relate intermediate points of N and N*. However, finding toggle equivalent subcircuits Ni and N*i efficiently, is very unlikely due to the huge number of subcircuits one has to enumerate. (If the granularity of Spec(N) and Spec(N*) is 100, then, roughly speaking, one has to enumerate |N|100 × |N*|100 pairs of subcircuits.)

Q&A

Q. How do your results relate to state-of-the-art EC?
A. In a sense, EC of circuits N and N* with a common specification (and EC in general) can be viewed as a "decryption process". Here N is the original "message" and an optimized circuit N* is an "encrypted message" and EC of N and N* is a process of recovering N* from N. The common specification of N and N* is a "key". If this key is known, the decryption process is easy, otherwise it is hard. The current design flow is similar to behavior of a person who throws away his door key every time he leaves the house. There are basically two strategies to get back in. First strategy, is to kick the door in (if it is not strong enough). This is exactly what is done in BDD based verification. Building BDDs of circuits N and N* means destroying their original structure. This can be done efficiently only for "fragile" (i.e. narrow) circuits. If N and N* are wide, then some method of using their is structural similarity is employed (like finding functionally equivalent internal points). In terms of our analogy, this approach is very similar to picking the door lock. For simple locks it is possible. However, our theory implies that these locks can be made arbitrarily complex (by increasing the granularity of the common specification of N and N*). Importantly, increasing the granularity of common specification means making logic synthesis more powerful. In other words, EC of wide circuits (without any knowledge of their common specification) is possible only for very "weak" logic synthesis procedures.

Q. Are these results of any practical importance? Current logic synthesis algorithms do not produce circuits with a common specification
A. The main point is that the complexity of EC and power of logic synthesis are tightly related. The more perturbed an initial circuit N is by logic synthesis, the harder it is to prove the equivalence of N and the optimized circuit N* without any additional information.  

In [2], we sketch a powerful logic synthesis procedure enabled by EC_TE. Given a circuit N and its partition into subcircuits N1,...,Nk (i.e. its specification),this procedure builds an optimized circuit N* with the same specification as N. We will refer to this procedure as LS_TE (here LS stands for Logic Synthesis and TE for Toggle Equivalence). LS_TE builds circuit N* by replacing subcircuits Ni of Spec(N) with toggle equivalent counterparts N*i in topological order. Importantly, LS_TE has the same complexity as EC_TE that is it is linear in the number of subcircuits Ni and exponential in the granularities of Spec(N) and Spec(N*). So if the granularity of Spec(N) is bounded by a constant (this essentially means that granularity of Spec(N*) is also bounded by a constant), then LS_TE is linear in circuit size and so it is scalable. On the other hand, LS_TE enjoys great flexibility because the number of subcircuits toggle equivalent to Ni is astronomical even if the number of outputs inNi is small. (Let a subcircuit Ni has k outputs. Then the number of, say, k output Boolean functions toggle equivalent to the function implemented by Ni is, roughly speaking, 2k!. For k=5 this number is equal to 2.6 × 1035. In [5], we describe a procedure that, given a subcircuit Ni builds an optimized toggle equivalent subcircuit N*i. This procedure, makes LS_TE "a reality".

In [6], we show that LS_TE can be viewed as a way to address the local minima entrapment problem. The depth of the minimum that can be (potentially) escaped depends on the granularity of Spec(N). The larger this granularity is, the deeper local minimum can be escaped.

Q. How does the claim that EC is "unsolvable" is different from a well-known fact that EC is coNP-complete and so, most probably, it can not be solved efficiently in the general case?
A. The fact that a particular class of EC problems is hard to solve may mean two things. First, circuits N and N* of this class are very different from each other and so there is no short proof (in a particular proof system) that they are functionally equivalent. In this case, EC is "naturally" hard. Second, circuits N and N* of this class are actually "similar" and so there are short EC proofs. However these proofs can not be efficiently found without some extra information. In this case, EC of N and N* is "unnaturally" hard. Our results introduce a class of EC problems (namely EC of circuits with a common specification) that are most likely "unnaturally" hard. Another way to look at these two kinds of complexity is as follows. The first type of complexity concerns non-deterministic algorithms. That is EC is hard even if one has an oracle suggesting the best decisions. The second type of complexity concerns deterministic algorithms. In this case EC is easy with an oracle (i.e. for a non-deterministic algorithm) but becomes hard if one may not use an oracle (i.e. for a deterministic algorithm).

Note that the very existence of these two types of complexity is still an open question. If NP=coNP, the first type of complexity does not exist for EC problems. (In this case, there should exist a powerful enough proof system in which all EC problems have short proofs.) However, the second kind of complexity still remains even if NP=coNP (because short proofs may be exponentially hard to find) and "disappears" only if P = NP (in which case not only all EC problems should have short proofs, but there should exist an efficient algorithm for finding such proofs).

References

  1. Wikipedia. Article on equivalence checking.
  2. E.Goldberg. On Equivalence Checking and Logic Synthesis of Circuits with a Common Specification. GLSVLSI-2005.
  3. C.L.Berman. Circuit width, register allocation, and ordered binary decision diagrams. IEEE Trans. on CAD. Vol 10:8, 1991, pp.1059-1066.
  4. R.Braynt. Graph-Based Algorithms for Boolean Function Manipulation. IEEE Transactions on Computers. Vol. C-35, No. 8, August, 1986, pp. 677-691.
  5. E.Goldberg,K.Gulati,S.Khatri. Toggle Equivalence Preserving (TEP) logic synthesis , DSD-2007,Lubeck, Germany
  6. E.Goldberg. Escaping Local Minima in Logic Synthesis, IWLS-2007,San Diego 2007.
  7. E.Goldberg,K.Gulati. On Complexity of External and Internal Equivalence Checking. DSD-2007,Lubeck, Germany