Area-driven Boolean bi-decomposition by function approximation

Bi-decomposition [10, 24, 30, 37, 46] is a well-known form of decomposition, where a Boolean function \(f\) is rewritten as \(f = g \ {\texttt {op}}\ h\) and op is a two-input binary operator. When the operator is conjunction, bi-decomposition can be seen as a special case of Boolean division with an exact quotient [45]: \(f = g \cdot h\), where \(f, g, h\) are respectively the dividend, divisor and quotient functions. Bi-decomposition may be applied with different objectives: A common objective is size optimization (e.g., measured by literals) as in Reference [6] or delay optimization as in Reference [10] (either independent from technology measured by depth of Boolean networks, or timing optimization after technology mapping). When targeting size optimization, we can view bi-decomposition as a way to explore the implementations of a given logic expression by introducing one more level in the circuit and so exploring a larger solution space. For example, the logic expression \(x_1 x_2 x_4 + x_2 x_3 x_4\) of the form AND-OR with two products and six literals can be bi-decomposed as \(x_2 x_4 . (x_1 + x_3)\) of the form AND-OR-AND with four literals. In general, by bi-decomposition a \(k\)-level form can be rewritten as a \((k+1)\)-level form with a potentially smaller size due to more opportunities of factorization and restructuring.

The challenge for bi-decomposition as for Boolean division is as follows: Given \(f\), how to find a good divisor \(g\) and then how to determine the quotient \(h\), where \(f \subseteq g\) and \(f \subseteq h\) are necessary conditions on \(g\) and \(h\). A common technique to find divisors has been to search kernels as factors restricting the operation to algebraic division. Moreover, for bi-decomposition the problem has one more degree of freedom, since the goal is to rewrite a given Boolean function \(f\) as \(f = g \ {\texttt {op}}\ h\), where op is a two-input binary operator, of which there are 10 non-trivial ones. So, different choices of op yield different versions of the problem.

If algebraic techniques work fine in many applications, then Boolean techniques promise to search a larger solution space with a higher computational price. When op is conjunction (conjunctive bi-decomposition), it was suggested in Reference [10] to choose as divisors over-approximations \(g\) of \(f\), and to derive the associated conjuncts \(h\) by Boolean minimization using the don’t care set (dc-set) derived from the divisors \(g\). Therefore, one could obtain a sequence of decompositions \(f = g_i \cdot h_i, i = 0, \dots , n\), by pairs of divisors and quotients, in which the logic is distributed bouncing between \(g_i\) and \(h_i\), from \(g_0 = f, h_0 = 1\) to \(g_n = 1, h_n = f\), choosing the best tradeoff according to some objective function.

As a follow-up to the previous hint, we cast the problem of bi-decomposition \(f = g \ {\texttt {op}}\ h\), as selecting the divisor \(g\) by an approximation of \(f\), where the binary operation op used in the decomposition determines whether to use over-approximations or under-approximations of \(f\) as divisors \(g\). More precisely, according to the specific op, \(g\) must be an approximation for \(f\) or for its complement \(\overline{f}\), introducing only one type of errors: either 0 to 1 complementations of the output bits, or 1 to 0 complementations. The only exception are the bi-decompositions based on the XOR operation, where both types of errors can be introduced. Finding good divisors \(g\) from the approximations of \(f\) is not all, the next challenge is to compute the quotient: Given a function \(f\), an operator op and a divisor \(g\) as an approximation of \(f\), characterize the complete flexibility of the quotient function \(h\). In Reference [6], we expressed the full quotient by an incompletely specified function \(h\) with the smallest on-set and the largest dc-set such that \(f = g \ {\texttt {op}}\ h\).

The idea to compute the full quotient is that, according to the operation used in the bi-decomposition of \(f\), the on-set or the off-set of \(g\) become the dc-set for the function \(h\), together with the dc-set of \(f\), defining the full flexibility to obtain a more compact representation of \(f\), since the larger is the on (or off)-set of \(g\), the higher is the flexibility in the implementation of \(h\). In other words, \(h\) corrects the errors introduced by the approximation \(g\), so that \(g \ {\texttt {op}}\ h\) is an exact alternative representation of \(f\). The methodology of deriving divisors as over- or under-approximations of \(f\) and then computing the full quotient can serve the purpose either to explore different exact bi-decompositions of \(f\) for a given type of logic expressions like AND-OR or XOR-AND-OR forms (to find the best one, e.g., in terms of size, say, literals), or to explore different approximate bi-decompositions of \(f\), to be implemented approximately within a tolerable error rate.

Targeting the first objective of exact bi-decompositions of \(f\), in Reference [6] we studied the bi-decomposition of EXOR-AND-OR forms with op = AND or \(\not\Rightarrow\); here, instead, we report on the bi-decomposition of AND-OR (Sum-of-Products (SOP)) forms with op = AND.

In Section 2, we introduce some basic notation, and in Section 3 we state and prove in detail all the results on the full quotient flexibility for all 10 non-trivial two-input Boolean operators (divided in three classes: AND-like, OR-like, XOR-like). Sections 4 and 5 discuss subtle points of approximations for bi-decomposed forms and their application to SOP synthesis. Experiments for SOP synthesis are discussed in 6. Section 7 summarizes conclusions and future work.

This article is an extended version of a previous conference paper [6]. The novelties are as follows: Section 2 on previous work is mostly new; Section 3 on the full quotient for all 10 binary operators has been extended adding the complete proofs omitted in Reference [6] for lack of space; Sections 4 and 5 are completely new, and the same as Section 6 reporting the implementation of SOP bi-decomposition with op = AND. Section 7 concludes with the summary of where we stand and the expected future work.

Let \(f : \lbrace 0,1\rbrace ^n \rightarrow \lbrace 0,1,-\rbrace\) be the function that must be synthesized. Let \(g\) be a (completely specified) approximation of \(f\) or of its complement \(\overline{f}\). Note that we define the complement of \(f\) as the function \(\overline{f}\) such that

Given \(f\) and \(g\), and a two-input Boolean operator op, we want to compute an incompletely specified Boolean function \(h\) such that \(f\) can be represented in bi-decomposed form as \(f = g \ {\texttt {op}}\ h\).

In our analysis, we only consider the 10 (of 16) binary operations depending on both input variables, described in Table 1. Thus, we will not consider the two constant operations, as well as the four degenerate operations depending on only one input.

Applying the De Morgan’s laws as shown in the table, we can note how the 10 operations can be naturally divided into three sets as follows:

We now describe how to approximate \(f\) with \(g\), and how to derive the quotient function \(h\) for each set of operations.

In the following exposition, we use \(f^{{\it \,on}}, g^{{\it \,on}}\), and \(h^{{\it \,on}}\) to denote the on-sets of the three functions \(f\), \(g\), and \(h\), \(f^{{\it \,off}}\), \(g^{{\it \,off}}\), and \(h^{{\it \,off}}\) to denote their off-sets, and \(f^{{\it \,dc}}\) and \(h^{{\it \,dc}}\) to denote the dc-sets of the incompletely specified functions \(f\) and \(h\) (observe that \(g\) is completely specified).

In this section we discuss several interesting aspects of approximation and bi-decomposed forms.

First, we notice that we cannot simply exploit \(1 \rightarrow 0\) approximation to mimic exactly the minimization based on \(0 \rightarrow 1\) approximation, and vice-versa, even if we use the negation of the considered Boolean function. We explain this point through a simple example. Consider, for instance, the Boolean function \(f\) depicted in Figure 7(a). The minimal SOP \(0 \rightarrow 1\) approximated form is shown in Figure 7(c), with an error in the point 0101 and the corresponding algebraic SOP form: \(x_2 x_4\). If we negate \(f\), then we obtain the function \(\overline{f}\) depicted in Figure 7(b). If we minimize \(\overline{f}\) using a \(1 \rightarrow 0\) approximation, then we obtain the solution depicted in Figure 7(d), with an error in the point 1001 and algebraic SOP form: \(\overline{x}_1 \overline{x}_3\). We can notice that the two solutions do not correspond. This means that we cannot exploit a \(1 \rightarrow 0\) approximation on \(\overline{f}\) to mimic exactly a minimization based on \(0 \rightarrow 1\) approximation. This example shows that even if we could easily get \(\overline{f}\), in some way, one kind of approximation cannot be implemented with the other one. Of course, we could consider a different approximation (for example the one given by Figure 7(d)), and then complement the given solution. This is possible only in the cases when the computation of the complemented function \(\overline{f}\) is easy. Moreover, the resulting solution for \(f\) is given by the negation of the final approximated circuits (of \(\overline{f}\)), resulting in an additional level of logic. For this reason, in this article we always distinguish cases where \(0 \rightarrow 1\) approximation or \(1 \rightarrow 0\) approximation is required.

Another aspect, worth to be highlighted, of the proposed technique is the number of don’t cares that are generated to enhance the exact minimization (i.e., \(h^{dc}\)). This is the key idea of the proposed method. In fact, the higher is the number of don’t cares, the higher is the flexibility of the synthesis. For this reason, we notice that this method is not very effective for the operator XOR and XNOR. In fact, in Table 2 we can observe that the don’t care set of \(h\) (i.e., the column labeled with \(h^{dc}\)) in all the cases, but XOR and XNOR, contains the union of the don’t care set \(f^{dc}\) of the given function \(f\), and of the on or off set of the approximation function \(g\).

The proposed bi-decomposition method is very general and can be applied to any approximation technique. As a case study in this article, we consider the standard synthesis of Boolean functions in two-level Sum of Products or SOP forms, to derive bi-decompositions \(f = g \ {\texttt {op}}\ h\), where both the approximation \(g\) and the quotient function \(h\) are represented in SOP forms.

In the previous section, we observed that bi-decomposition with operations based on the binary AND and OR operators generate more don’t cares than bi-decompositions based on EXOR, and therefore might provide more interesting results.

In the literature, we found many techniques for over-approximation, i.e., for a \(0 \rightarrow 1\) approximation, which can be used for the AND-based bi-decomposition, while we did not find general heuristics for \(1 \rightarrow 0\) approximation, required to implement the bi-decomposition based on the OR function. As pointed out in Reference [39], a possible reason might be that, in the context of approximate SOP synthesis, approximate functions obtained by complementing a minterm in the off-set (i.e., by a \(0 \rightarrow 1\) complement) usually contain the smallest number of literals. Indeed, with one \(1 \rightarrow 0\) complement, we can remove at most one product in the original SOP cover. Instead, a \(0 \rightarrow 1\) complement can expand many products in the original cover, and in turn, expanded products may entirely cover other products that become redundant and hence can be removed from the SOP cover for the approximate function. For these reasons, we have chosen to implement a \(0 \rightarrow 1\) approximation heuristic inspired by References [5, 39] to derive and experimentally validate the bi-decomposition \(f = g \cdot h\) based on the AND operation.

The heuristic proposed in Reference [39] identifies minterms that can be complemented to maximally reduce the number of literals in the final SOP form, for a given error rate threshold \(r\), defined as the percentage of input vectors on which the output computed by the circuit can be different from the exact one. In particular, for an error rate \(r\) and a target function \(f\) depending on \(n\) binary variables, let \(M_t = 2^n \times r/100\) denote the number of minterms on which the output computed by the circuit can be different, on at least one bit, from the exact one. The heuristic exploits a so-called Assisting Expansion procedure, consisting in the removal of a single literal from a prime implicant in an initial SOP representation \(S\) of the target function \(f\), and optimizes the resulting representation by use of redundancy removal techniques and heuristic minimizers. If the expansion due to the literal removal implies the complement of a number of minterms greater than the chosen error threshold \(M_t\), then the expansion is discarded; otherwise, the generated product is subjected to further evaluation and eventually added to the new approximated SOP form. Note that since this heuristic involves only the removal of literals from the implicants, the only modified minterms are part of the off-set \(f^{{\it \,off}}\) of the function, so that the heuristic produces a \(0 \rightarrow 1\) approximation of \(f\).

We have implemented the Assisting Expansion heuristic of Reference [39] in the following way: Let \(S\) be an initial SOP representation of a function \(f\), and let \(P\) be the set of all products in \(S\).

This procedure is repeated for all products in \(P\). Once all products have been expanded in all possible directions, we must select the subset \(I\) of expanded products that maximizes the overall gain within the minterm threshold \(M_t\). This final step consists basically in solving an instance of the well known Knapsack problem [20], which is an NP-hard problem. For this reason, we perform the step heuristically, by means of a greedy selection of the expanded products, as done for three-level forms in Reference [5]. More precisely, all products are extracted from the priority queue and then selected until the number of 0 to 1 complements introduced in the approximate version of \(f\) reaches the threshold \(M_t\). Whenever an expanded product \(p_i^{\,j}\) has been selected and inserted in \(I\), all other expansions of \(p_i\), i.e., all \(p_i^k\) with \(k \ne j\), are discarded from the priority queue. The reason is that the choice of another expansion \(p_i^k\) of the same product \(p_i\) is never convenient as it introduces one more product in the final algebraic form.

Once the set \(I\) has been determined, it is possible to proceed with the construction of the final SOP representation in the following way:

Observe that the SOP \(S^{\prime }\) satisfies the following property.

In this section we report the experimental results conducted to evaluate the bi-decomposition by the approximation strategy discussed in the previous sections. We consider completely specified and incompletely specified benchmarks in PLA form (from the Espresso and LGSynth’89 benchmark suite [47]), and we study the performance of the proposed approach by comparing the size (in terms of number of literals) of the SOP form of a given benchmark \(f\) vs. the size of the AND-based bi-decomposition form \(f = g \cdot h\), where \(g\) and \(h\) are represented as SOPs. The choice of limiting the analysis to the AND-based bi-decomposition is due to the following facts:

To derive the over-approximation \(g\), we have implemented the heuristic described in Section 5 in C, using the CUDD library to represent and manipulate Boolean functions with BDDs, e.g., to compute unions and intersections between \(f\) and \(g\) to define the quotient \(h\). Sum of product forms have been minimized using the standard SOP minimizer Espresso [27]. The experiments have been run on a Linux Intel Core i5-8250U CPU with 8 GB of RAM.

Finally, the choice of benchmarks for our experiments is due to the fact that we consider SOP expressions to optimize with tools such as Espresso, which require inputs represented in PLA form. The benchmarks available in other standard sets (such as EPFL benchmark suite [41, 42]) are, unfortunately, not given in PLA form. We further discuss this point in the concluding section.

In the experiments, the bi-decomposition of \(f\) is described in Algorithm 1, and consists of the following steps:

Table 3 reports the results of the experiments on multi-output benchmarks (we report only a significant subset of the benchmarks as representative indicators of our experiments). We consider different error rates for the construction of \(g\), ranging from 1% to 20%. The first two columns report the name of the benchmarks, the number of their inputs and outputs, and the number of literals in their initial SOP representation (minimized heuristically by Espresso). The remaining groups of two columns show the overall number of literals in the bi-decomposed forms \(g \cdot h\) obtained for each benchmark \(f\), for seven different error rates allowed in the approximation \(g\), together with the percentage gain in the number of literals. Whenever the bi-decomposition method produces forms with a higher number of literals, the benchmark is left unchanged (i.e., we set \(g=f\), and \(h=1\)), and the gain is set to 0. The last three rows of the table report the average gain for the whole set of benchmarks, and the average gain computed only on the subset of benchmarks that benefit from the bi-decomposition, i.e., which present a strictly positive gain. For each benchmark, in Table 3, we underline in bold the error rate that exhibits better results.

The average results show how the bi-decomposed forms provide gains of about 5–7% in the number of literals, if we consider the whole set of benchmarks. However, considering only benchmarks that benefit from the bi-decomposition approach, which are about 75% of the total, we can observe how the average gain increases up to 15.36%. In both cases, the gains initially grow as the error rate \(r\) increases, and then stabilize when \(r\) exceeds \(5\%\). A possible explanation for this trend could be that, when the error rate \(r\) increases, we obtain a more compact representation for the approximation \(g\), but the flexibility in the implementation of the quotient function \(h\) decreases, so that the size of \(h\) increases. Therefore, these two trends offset each other and the gains stabilize.

Regarding the overall CPU time required for the synthesis of bi-decomposed forms, which includes the computation of both the approximation function \(g\) and the quotient function \(h\), we have noticed from our experiments that the running times do not exhibit significant variations as the error rate changes. The average CPU time is quite short, about 0.18–0.20 s, for all the different values of the error rate \(r\) chosen for the construction of \(g\), with variances ranging from 0.8 to 1.14 s, and maximum values of about 10 seconds for benchmarks with a high number of inputs and outputs.

Table 4 shows the average results obtained studying each benchmark’s output independently of the others, as if it were a single-output function. We notice how in this case the gain is higher for low error rates \(r = 1\)–\(2\%\), and then it decreases, and stabilizes at the value of about 5%. On the contrary, if we consider only the outputs presenting a positive gain, the average gain increases with the error rate, and becomes maximum for \(r = 20\%\), reaching the value of 17.17%.

Figure 8 shows how the gain varies as the error rate increases for both sets of experiments, on multi-output and single output functions. The plot on the left reports the average gains relative to the entire set of benchmarks, while the plot on the right considers only the average gains computed on the subset of benchmarks that benefit from the bi-decomposition. Observe that when the outputs of the benchmarks are studied independently, we get slightly higher gains, if we consider only outputs with positive gain. On the contrary, the average gains computed on all benchmarks are generally higher for multi-output bi-decompositions.

In Table 5, we report the average gains obtained choosing for each benchmark, or benchmark output, the most convenient bi-decomposed form, i.e., the form obtained using the error rate that provides the highest gain for that particular benchmark, including the trivial bi-decomposition where \(g = f\) and \(h = 1\). In the first row of the table we report the averages obtained over all benchmarks, considering multi-output functions as a whole; the averages in the second row are obtained considering each output function independently. The second column of the table reports the averages computed considering only bi-decompositions with a strictly positive gain. The fact that the left column (average) decreases from top to bottom, whereas the right column (average with positive gain) increases from top to bottom is likely due to the fact that for single output there are more benchmarks where the algorithm chooses the trivial decomposition (\(g = f, h = 1)\) with \(gain = 0\). These results suggest that the application of the algorithm using multiple error rates, is generally more convenient, as expected.

We finally run a last test, considering only multi-output bi-decomposition. The idea of this test is to choose for each output of a benchmark the bi-decomposed form with the smallest number of literals, independently of the error rate, and then to merge these forms back together to obtain a bi-decomposed multi-output representation for the whole benchmark, equivalent to the original one. A subset of results of this last experimental evaluation is reported in Table 6. The first two columns report the name of the benchmarks, the number of their inputs and outputs, and the number of literals in their initial SOP representation (computed heuristically). The remaining two columns show the overall number of literals in the final bi-decomposed forms \(f = g \cdot h\) obtained choosing the best bi-decomposed form for each benchmark output, together with the overall percentage gain in the number of literals. The last two rows report the average gain for the whole set of benchmarks, and the average gain computed only on the subset of benchmarks that benefit from the bi-decomposition. In this test, the average gain for all the 124 benchmarks studied is of about 27%; moreover, considering only the 99 benchmarks showing a positive gain, the average reduction in the number of literals increases to about 34%. Thus, the gain in size is quite interesting, also considering that the overall synthesis time is very short.

Last, the last two columns of Table 6 provide a comparison with the bi-decomposition approach discussed in References [2, 3], consisting of a new bounded-level form, called complemented circuits. A complemented circuit is a special type of decomposition aiming at representing a Boolean function \(f\) as \(\overline{f}_0 \ op \ f_1\), where \(op\) is a two input gate, and \(f_0\) and \(f_1\) are related to the off-set and on-set of \(f\). In particular, we consider the complemented circuits defined in terms of the AND gate, heuristically minimized using Boolean relations [1]. Even if in the original papers [2, 3] the cost of complemented circuits is measured in terms of the number of products, for the current comparison we refer to the number of literals, which we believe is a more accurate cost metric. Thus, we report the number of literals of the AND-based complemented circuits in the next-to-last column, and the percentage gain (or loss) in the number of literals provided by AND-based bi-decompositions compared to complemented circuits in the last column.

The results show that AND-based bi-decomposition forms are in general more compact than complemented circuits, with some exceptions (see, for example, \(dk17\) and \(tial\)). In summary, the average gain for all the benchmarks studied in this comparison is of about 14%; moreover, considering only the benchmarks showing a positive gain, the average reduction in the number of literals guaranteed by the new approach increases to 27%.

Eventually, we refer the reader to the conference version of this article [6] for the experimental evaluation of a similar approach in the framework of three-level EXOR-AND-OR forms (i.e., SPP expressions).

We presented an approach to the bi-decomposition of a function \(f = g \ {\texttt {op}}\ h\), where the divisor \(g\) is selected as an approximation of \(f\) (\(0 \rightarrow 1\) or \(1 \rightarrow 0\) or both, according to the type of \({\tt op}\)). Then, given a selection of the divisor \(g\), we provided the full flexibility of the quotient \(h\), for each operator.

Bi-decomposition can be applied to area-driven or delay-driven optimization flows. In the case of area, we can target exact or approximate optimizations. In Reference [6] we had reported an application of this approach to EXOR-AND-OR forms, for the two operators \({\tt op} =\) AND and \({\tt op} = \not\Rightarrow\). In this article we applied area-driven exact decomposition to SOP forms for the operator \({\tt op} =\) AND and \(0 \rightarrow 1\) approximation. The experiments show significant gains in literals.

Future work includes and is not limited to the following:

Finally, we note that in the literature on approximation it is common to find \(0 \rightarrow 1\) over-approximations, but not \(1 \rightarrow 0\) under-approximations, since under-approximations (\(1 \rightarrow 0\)) produce worse results than over-approximations (\(0 \rightarrow 1\)), see Reference [39]. However, in bi-decomposition it is possible to correct errors with the quotient \(h\), so that even if \(1 \rightarrow 0\) under-approximations may not be helpful for approximations, they can still be advantageous for exact or approximate bi-decompositions.