Experimental Study of Algorithms for Minimization of Binary Decision Diagrams Using Algebraic Representations of Cofactors

Abstract

Binary decision diagram (BDD) is used for technology-independent optimization, performed as the first stage in the synthesis of logic circuits in the design of application-specific integrated circuits (ASICs). BDD is an acyclic graph defining a Boolean function or a system of Boolean functions. Each vertex of this graph is associated with the complete or reduced Shannon expansion formula. Binary decision diagrams with mutually inverse subfunctions (cofactors) are considered. We have developed algorithms for finding algebraic representations of cofactors of the same BDD level in the form of a disjunction or conjunction of other inverse or non-inverse cofactors of the same BDD level. The algorithms allow reducing the number of literals by replacing the Shannon expansion formulas of a system of Boolean functions. It is proposed to use the developed algorithms for an additional logic optimization of the constructed BDD representations of systems of Boolean functions. The experimental results of application of the corresponding programs in synthesizing the logic circuits in the design library of custom VLSI CMOS circuits are presented.

1. INTRODUCTION

Automation of logic design of functional units of combination logic entering the custom digital VLSIs (very large-scale integrated circuits) still is a topical scientific problem, because the dimensions of the solved problems increase, there appear more rigorous requirements to the energy consumption of logic circuits, and the libraries of logic elements change. Logic design of combination circuits in design libraries of custom VLSIs is traditionally divided into two stages: logic optimization and technological mapping, at which the optimized logic functional descriptions of the designed logic circuits are covered by functional descriptions of logic elements. Logic optimization, often called technology-independent optimization, usually does not involve the used basis (library) of logic elements, but tends to decrease the number of literals and the number of two-operand operations of disjunction and conjunction in the minimized algebraic representations of systems of completely specified Boolean functions. In the design practice it was noticed long ago [1, p. 44] that a reduction in the number of literals and logic operations in functional descriptions positively impacts the reduction in the number of elements of the technological library (basis of synthesis) in the circuit, that is, positively impacts the reduction in the total number of transistors entering all elements of the circuit. Decreasing the number of transistors allows lowering the energy consumption of circuits.

Today, logic minimization is made by means of the methods of optimization of multilevel Boolean functions on the basis of Shannon expansion; graphical forms of such representations, frequently used as data structures, are called binary decision diagrams [2–7]. In work [8] we proposed a method for additional minimization of BDD representations of systems of Boolean functions based on search of disjunctive, conjunctive, and modular expansions of subfunctions entering the optimized BDD representations. The method allows replacing the formulas of Shannon expansion by two-operand formulas of disjunction g₃ = g₁ $\vee$ g₂, conjunction g₃ = g₁ & g₂, or modular formulas of type g₃ = g₁ $\oplus$ g₂ (where g₁, g₂, and g₃ are cofactors of the same BDDI level). Such replacement reduces the number of literals and logic operations in the resulting logic formulas, which are used to perform technological mapping, that is, the final stage of circuit synthesis. In the current work the method from [8] is elaborated to algorithms and programs whose efficiency is studied on flows of examples entering the well-known example library used to check and compare the programs of logic optimization and synthesis of logic circuits. For the expansions of cofactors we use only disjunctive and conjunctive expansions, and the cofactors in such expansions may be in both inverse and non-inverse form.

2. BINARY DECISION DIAGRAMS AND ALGEBRAIC EXPANSIONS OF COFACTORS

The Shannon expansion of a completely specified Boolean function f = f(x), x = (x₁, x₂, …, x_n), in variable x_i is the representation

$$\begin{gathered} f = f({\mathbf{x}}) = {{{\bar {x}}}_{i}}f({{x}_{1}},...,{{x}_{{i - 1}}},0,{{x}_{{i + 1}}},...,{{x}_{n}}) \\ \vee \,{{x}_{i}}f({{x}_{1}},...,{{x}_{{i - 1}}},1,{{x}_{{i + 1}}},...,{{x}_{n}}). \\ \end{gathered} $$

(1)

The functions f₀ = f(x₁, …, x_{i – 1}, 0, x_{i + 1}, …, x_n) and f₁ = f(x₁, …, x_{i – 1}, 1, x_{i + 1}, …, x_n) in the right-hand side of Eq. (1) are referred to as cofactors of expansion in variable x_i. They are obtained from the function f by substitution of the constants 0 and 1, respectively, instead of the variable x_i. Each of the cofactors f₀ and f₁ can be expanded in one variable from the set {x₁, …, x_{i – 1}, x_{i + 1}, …, x_n}. The process of expansion of cofactors terminates either when all n variables are used for expansion or when all cofactors degenerate to constants 0, 1. At each step of expansion we perform comparison by equality of the obtained cofactors.

Let f(x) be an ordered system of completely specified component Boolean functions f_i(x), i = 1, …, m, (the vector Boolean function f = (f₁, …, f_m)): f(x) = (f₁(x), …, f_m(x)), x = (x₁, x₂, …, x_n). Under the BDD representation of a vector Boolean function f(x) we understand the oriented acyclic graph prescribing sequential Shannon expansions of all component functions f_i(x), i = 1, …m, in all its variables x₁, …, x_n for the same given order (permutation) of variables in which we perform expansions. The BDDs considered in this paper correspond to shared reduced ordered BDDs (ROBDDs) [5, p. 18]. In joint ROBDDs the functional vertices of BDDs correspond to the cofactors common to the functions of the system; here, the functional vertices are just implied (identified with vertices-variables). Description of OBDDs (ordered BDDs) is given in [2, p. 90; 5, p. 16], whereas description of ROBDDs is given in [3, p. 243]. Below, BDDs will be understood as joint ROBDDs for the systems of functions (vector functions).

The BDD representation corresponds to the formulas of Shannon expansion, and each functional vertex of BDD [6, p. 18] corresponds to its own formula in which both cofactors take part in non-inverse form. Using the BDD representation, we can find specification of each of the component functions f_i(x) in form of two orthogonalized disjunctive normal forms (DNFs): one of such DNFs prescribes the region $M_{{{{f}_{i}}}}^{1}$ of unit values of the function f_i(x), whereas the other DNF prescribes the region $M_{{{{f}_{i}}}}^{0}$ of zero values. Similarly, we can find the representations in form of DNF for each of the cofactors. These transitions are thoroughly described in [6, p. 37]. Figure 1a shows a BDD which corresponds to the following coupled equations of Shannon expansions:

$$\begin{gathered} {{f}_{1}} = {{{\bar {x}}}_{3}}{{g}_{1}} \vee {{x}_{3}}{{x}_{1}};\quad {{f}_{2}} = {{{\bar {x}}}_{3}}{{g}_{2}} \vee {{x}_{3}}{{g}_{4}}; \\ {{f}_{3}} = {{{\bar {x}}}_{3}}{{g}_{5}} \vee {{x}_{3}}{{g}_{3}}; \\ \end{gathered} $$

$$\begin{gathered} {{f}_{4}} = {{{\bar {x}}}_{3}} \vee {{x}_{3}}{{g}_{6}};\quad {{g}_{1}} = {{{\bar {x}}}_{1}}{{s}_{1}} \vee {{x}_{1}}{{s}_{2}}; \\ {{g}_{2}} = {{{\bar {x}}}_{1}}{{s}_{1}};\quad {{g}_{3}} = {{x}_{1}}{{s}_{2}};\quad {{g}_{4}} = {{{\bar {x}}}_{1}}{{s}_{2}}; \\ \end{gathered} $$

$${{g}_{5}} = {{x}_{1}}{{s}_{1}};\quad {{g}_{6}} = {{\bar {x}}_{1}}{{s}_{2}} \vee {{x}_{1}}{{s}_{1}};\quad {{s}_{1}} = {{x}_{2}};\quad {{s}_{2}} = {{\bar {x}}_{2}}.$$

Fig. 1.

(a) BDD with labeled cofactors and (b) BDD in traditional image.

The cofactors g₁, …, g₆ are determined at the second BDD level and depend on two variables x₁, x₂; the cofactors at the first level depend on the variable x₂: s₁ = x₂, s₂ = ${{\bar {x}}_{2}}$ (see Fig. 1a). At the bottom BDD level there always are constants 0, 1 that can be doubled for simplifying the depiction of the BDD graph in the figure. Figure 1b shows the graph of the same BDD in the notation accepted in the foreign literature: dashed curves in Fig. 1 correspond to labels 0, whereas solid ones correspond to labels 1.

Using the BDD graph, we can easily find the cofactors appearing at the same BDD level, and from the prescription of cofactor (or the function of the original system) in form of DNF we can proceed to its prescription in the form of completed DNF (PDNF) or truth table. We consider the cofactors g₁, g₂, g₃, g₄, g₅, g₆ of the second BDD level (Fig. 1a), eliminate the intermediate variables, and obtain the completed DNFs:

$$\begin{gathered} {{g}_{1}} = {{{\bar {x}}}_{1}}{{s}_{1}} \vee {{x}_{1}}{{s}_{2}} = {{{\bar {x}}}_{1}}{{x}_{2}} \vee {{x}_{1}}{{{\bar {x}}}_{2}}; \\ {{g}_{2}} = {{{\bar {x}}}_{1}}{{s}_{1}} = {{{\bar {x}}}_{1}}{{x}_{2}};\quad {{g}_{3}} = {{x}_{1}}{{s}_{2}} = {{x}_{1}}{{{\bar {x}}}_{2}}; \\ \end{gathered} $$

$$\begin{gathered} {{g}_{4}} = {{{\bar {x}}}_{1}}{{s}_{2}} = {{{\bar {x}}}_{1}}{{{\bar {x}}}_{2}};\quad {{g}_{5}} = {{x}_{1}}{{s}_{1}} = {{x}_{1}}{{x}_{2}}; \\ {{g}_{6}} = {{{\bar {x}}}_{1}}{{s}_{2}} \vee {{x}_{1}}{{s}_{1}} = {{{\bar {x}}}_{1}}{{{\bar {x}}}_{2}} \vee {{x}_{1}}{{x}_{2}}. \\ \end{gathered} $$

We prescribe the CDNF of cofactors and their inversions by the truth table (Table 1).

Table 1. Cofactors of second BDD level (Fig. 1)

Using the truth tables, we can easily check the representations of cofactors of the same BDD level in form of algebraic expansions: disjunctive,

$${{g}_{p}} = {{g}_{i}} \vee {{g}_{j}},$$

(2)

or conjunctive,

$${{g}_{r}} = {{g}_{i}}\& {{g}_{j}}$$

(3)

expansion. We can also use inversions ${{\bar {g}}_{i}}$, ${{\bar {g}}_{j}}$ of cofactors g_i, g_j in expansions of form (2), (3). For the cofactors that have four literals in their notation (these are the cofactors g₁, g₆), we write the equations of their algebraic expansions via other cofactors:

$$\begin{gathered} {{g}_{1}} = {{{\bar {g}}}_{4}}\& {{{\bar {g}}}_{5}};\quad {{g}_{1}} = {{g}_{2}} \vee {{g}_{3}}; \\ {{g}_{6}} = {{{\bar {g}}}_{2}}\& {{{\bar {g}}}_{3}};\quad {{g}_{6}} = {{g}_{4}} \vee {{g}_{5}} \\ \end{gathered} $$

and represented the obtained equations in form of orgraph (Fig. 2).

Fig. 2.

Prescription of equations in form of orgraph.

We can easily see (Fig. 3) that the cofactors g₁ = ${{\bar {x}}_{1}}{{s}_{1}} \vee {{x}_{1}}{{s}_{2}}$ and g₆ = ${{\bar {x}}_{1}}{{s}_{2}} \vee {{x}_{1}}{{s}_{1}}$ can be expressed by the formulas of algebraic expansions through two cofactors g₂, g₃: g₁ = g₂ $\vee$ g₃; g₆ = ${{\bar {g}}_{2}}\& {{\bar {g}}_{3}}$. Replacement of the formulas g₁ = ${{\bar {x}}_{1}}{{s}_{1}} \vee {{x}_{1}}{{s}_{2}}$, g₆ = ${{\bar {x}}_{1}}{{s}_{2}} \vee {{x}_{1}}{{s}_{1}}$ by simpler ones allows reducing the number of literals and logic operations in the functional description of BDD (Fig. 1a).

Fig. 3.

Reduced acyclic orgraph.

Note that the cofactors g₁ and g₆ are mutually inverse; therefore, below, as original formulas, we use the formulas of Shannon expansions corresponding to BDDIs. Binary decision diagram with inverse cofactors (BDDI) is below understood as oriented acyclic graph prescribing sequential Shannon expansions of a Boolean function f(x₁, …, x_n) in all its variables x₁, …, x_n for a given order (permutation) of variables by which we perform expansions, under the condition of finding the pairs of mutually inverse cofactors [9]. The BDDI graphs contain four types of vertices: root vertices corresponding to the functions; functional vertices corresponding to the pairs of expanded mutually inverse cofactors (one of the elements of the pair can be absent if there is no such cofactor among the cofactors at the given BDDI level); vertices-variables; and leaf vertices corresponding to constants 0, 1. A functional vertex of BDDI (Table 2) implements one cofactor s_i or two cofactors: s_i and its inversion ${{\bar {s}}_{i}}$. The formula s_i = $\bar {x}\alpha \, \vee \,x\beta$ in the right column in Table 2 is formula (1) of Shannon expansion of the cofactor s_i in the variable x: α = f₀, β = f₁.

Table 2. Correspondence of graphic BDDI elements and logic formulas

Note that in the BDD the functional vertex implements a single cofactor; mutually inverse cofactors are represented by a pair of vertices. The BDDIs correspond to joint ROBDDs in which the pair of mutually inverse vertices-cofactors is given by a single functional vertex. In the equations of Shannon expansions corresponding to BDDIs, the cofactors may be either with the inverse sign or in the

In what follows, we propose the algorithms of finding the maximal sets of algebraic expansions of form (2), (3) of the cofactors appearing at the same BDDI level. The main issue is as follows: at prescription of the algebraic equations in form of orgraph there may arise cycles, which is unacceptable in circuit implementation of the combination logic. In the considered simple example of orgraph (Fig. 2) illustrating prescription of equations, there are no cycles. Transition to the resulting acyclic orgraph (Fig. 3), in which each cofactor is represented by a single algebraic expansion, is a complex combinatorial problem for graphs containing hundreds and thousands of vertices and in which there may be a vast number of cycles that must be eliminated. Preliminary determining the pairs of mutually inverse cofactors (using BDDIs instead of BDDs) reduces the combinatorial exhaustive search in finding the variants of algebraic expansions of cofactors; we will explain it further.

3. ALGORITHM 1 FOR FINDING ALGEBRAIC EXPANSIONS OF COFACTORS IN BDDI

Initial data for the proposed algorithm 1 for finding algebraic representations of cofactors are the BDDI graph, representing an original vector completely specified Boolean function, and logic equations (the formulas of Shannon expansion), corresponding to the functional vertices of the BDDI and prescribing the multilevel description of the component functions. These equations can be easily written using a BDDI graph.

The proposed algorithm includes the stages executed for the cofactors of each BDDI level, except for the root, leaf, and first one. At the first BDDI levels, there are the cofactors obtained as a result of expansion in the last variable in a given permutation of variables in which we perform the Shannon expansion. The cofactors of the first BDDI level depend on one variable; the cofactors of the second level depend on at most two variables; etc. In our algorithm, the BDDI levels are considered from top to bottom, that is, from the cofactors obtained at expansion in the first variable to the cofactors of the second BDD level. The algorithm is focused on replacing the largest number of formulas of Shannon expansion by the formulas of either disjunction or conjunction, which allows reducing the total number of literals in the multilevel prescription of a system of Boolean functions. For the considered BDDI level we solve the problem of determining the largest number of cofactors that are representable in form of disjunction or conjunction of other cofactors of the given level (earlier, such representations were called algebraic expansions).

Stage 1. Divide the set of equations into the BDDI levels.

Stage 2. For each BDDI level (except for the root, leaf, and first one), find the maximal set of implementable equations (implementable cofactors).

Execution of stage 2 reduces to the execution of the following steps.

Step 2.1. Eliminate the intermediate variables and construct the truth table of cofactors of the given (considered) BDDI level.

Step 2.2. Add the inversions of cofactors to the truth table.

Step 2.3. Find all variants of algebraic representations of non-inverse cofactors in form of two-operand disjunctions or conjunctions of other cofactors (or their inversions) of the considered BDDI level. As a result, a single cofactor, we call it representable, can be represented by different equations.

Step 2.4. Find the set of implementable cofactors.

From the set of representable cofactors we separate the subset of implementable cofactors with maximum cardinality; for this purpose, from the set of equations of the algebraic representation of one cofactor we choose one equation or choose no equation. This choice is determined by solution to problem 1 that is formulated in terms of the graph theory.

Stage 3. Correct the original multilevel BDDI representation of the system of Boolean functions.

The original set of formulas of Shannon expansions varies: the formulas of Shannon expansion of the implementable cofactors are replaced by the given disjunction or conjunction formulas.

Let us estimate the number of searched-through variants at step 2.3. Suppose that k is the number of non-inverse cofactors g₁, …, g_k. Then we need to consider 12 × $C_{k}^{3}$ ($C_{k}^{3}$ is the number of combinations of k cofactors by triples, k $\geqslant$ 3) variants of testing the disjunctive expansions: the number of all distinct unordered triples of cofactors g_p, g_i, and g_j is $C_{k}^{3}$, and for each triple {g_p, g_i, g_j} we need to test 12 disjunctive expansions,

$$\begin{gathered} {{g}_{p}} = {{{\bar {g}}}_{i}} \vee {{g}_{j}};\quad {{g}_{p}} = {{g}_{i}} \vee {{{\bar {g}}}_{j}}; \\ {{g}_{p}} = {{{\bar {g}}}_{i}} \vee {{{\bar {g}}}_{j}};\quad {{g}_{p}} = {{g}_{i}} \vee {{g}_{j}}; \\ \end{gathered} $$

$$\begin{gathered} {{g}_{i}} = {{{\bar {g}}}_{p}} \vee {{g}_{j}};\quad {{g}_{i}} = {{g}_{p}} \vee {{{\bar {g}}}_{j}}; \\ {{g}_{i}} = {{{\bar {g}}}_{p}} \vee {{{\bar {g}}}_{j}};\quad {{g}_{i}} = {{g}_{p}} \vee {{g}_{j}}; \\ \end{gathered} $$

$$\begin{gathered} {{g}_{j}} = {{{\bar {g}}}_{i}} \vee {{g}_{p}};\quad {{g}_{j}} = {{g}_{i}} \vee {{{\bar {g}}}_{p}}; \\ {{g}_{j}} = {{{\bar {g}}}_{i}} \vee {{{\bar {g}}}_{p}};\quad {{g}_{j}} = {{g}_{i}} \vee {{g}_{p}}. \\ \end{gathered} $$

Similarly, for each of $C_{k}^{3}$ triples of cofactors we need to search through 12 variants for constructing the conjunctive expansions.

Now, we can easily explain that using the BDDI instead of BDD reduces the combinatorial exhaustive search of variants in determining the formulas of disjunctive and conjunctive expansions. For instance, if it is not preliminary established that cofactors g_p and g_s are mutually inverse, then, in finding the expansions and determining the formula g_p = g_i $\vee$ g_j, for the inversion ${{\bar {g}}_{p}}$ = g_s we always can find the dual formula g_s = ${{\bar {g}}_{i}}\& {{\bar {g}}_{j}}$. Thus, for each formula of the algebraic expansion of the non-inverse cofactor, we will find the dual formula for the inverse cofactor and the search through the triples of cofactors appears to be more labor-intensive.

4. DETERMINATION OF THE SET OF IMPLEMENTABLE COFACTORS

Let us construct an orgraph G specifying the formulas of algebraic representations of cofactors (we call them logic equations or simply equations). The vertices of the orgraph G correspond to the cofactors in the direct form that are mentioned in equations. Let us denote this set of cofactors by K_Y and the set of cofactors for which we have not constructed the equations by K_Z. The edges (oriented edges) corresponding to the operands of algebraically represented cofactor (result of logic operation) are labeled by the same number, the number of equation. Each equation is given by a subgraph with three vertices and two labeled edges: the vertex corresponding to a representable cofactor has two input edges (with one and the same label, number of equation). The edges arising from the vertex of a representable cofactor (Fig. 3) can correspond to the direct form of cofactor (filled circle) or to the inverse form of cofactor (unfilled circle).

Let us introduce the notion of cluster (subset of the vertices of the graph G): the cluster includes the vertices corresponding to the equations with the same cofactor in the left-hand side. A cluster is labeled by the name of the same cofactors.

Using the orgraph G, we can reduce the problem of determining the set of implementable cofactors to the following problem.

Problem 1. In the orgraph G we need to leave just a single vertex in each cluster (condition А) and remove such subset of pairs of equally labeled edges from the graph G that the orgraph G becomes acyclic (condition B) and contains the largest number of nonisolated vertices with just a pair of incoming equally labeled edges (condition С).

The meaning of leaving a single vertex in the cluster (condition А) is clear: it suffices to represent the cofactor by a single equation in the circuit implementation. We demonstrate the requirement of the absence of cycles (condition В) on example of two equations g₆ = g₁ $\vee$ g₄ and g₁ = g₆ & g₇ from the below considered example. These equations create a cycle in the orgraph G, that is, the following logic contradiction in the requirement of algebraic (and circuit) representation of cofactors. To express g₆ as a conjunction g₆ = g₁ $\vee$ g₄, we need a circuit implementing the cofactor g₁. However, in order to obtain g₁ in form of g₁ = g₆ & g₇, we need a circuit implementing g₆. Condition С requires that the largest possible number of cofactors are represented in form of conjunction or disjunction.

After solving problem 1, we divide the set K_Y of vertices of the orgraph G into three mutually nonintersecting subsets. The vertices with no incoming edges, but with an emerging edge correspond to the unimplementable cofactors. The vertices with one pair of incoming edges (with the same label) correspond to the implementable cofactors. The vertices appeared to be isolated, for instance, at removing the edges to satisfy condition B, will not participate in the equations are included in the set K_Z of also unimplementable cofactors. An implementable cofactor will be written as an equation to the resulting multilevel representation of the system of Boolean functions.

Algorithm for Solving Problem 1

Stage А1. Selection of one equation in each cluster.

Step А1.1. Arrange the clusters in ascending (nondescending) order by the number of vertices in them and consider the clusters in this order.

Step А1.2. Leave just a single vertex in each cluster.

Put the current set T of vertices empty: T = $\varnothing$. Each remaining vertex g_r in the cluster that have the incoming equally labeled edges incident to the vertices g_i and g_j fulfills the set T by the elements g_i, g_j, and g_r.

To choose the vertex left in the first cluster, we use heuristic 1.

Heuristic 1. Each vertex g_r of the cluster with incoming edges from the vertices g_i and g_j is evaluated by the total number ${{W}_{{{{q}_{r}}}}}$ of edges arising from the vertices g_i and g_j. In the cluster we leave the vertex g_s corresponding to the maximal number ${{W}_{{{{q}_{r}}}}}$.

The vertices that have not remained in the cluster are removed from the graph together with the edges incoming in them. We introduce three vertices into the set T: the vertex g_s and the two vertices incident to the edges incoming to the vertex g_s.

For the following clusters at consideration we use heuristic 2.

Heuristic 2. In a cluster we leave the vertex that has two incoming edges from the vertices of the set T; if there are no such vertices, then we leave the vertex that has one incoming edge from the vertices of the set T. If there are no such vertices for which heuristic 2 is fulfilled, then we use heuristic 1 to leave a vertex in a cluster. The vertices not remaining in the cluster are removed from the graph together with the edges incoming to them.

Step А1.2 and stage А1 are accomplished when a single vertex remains in each cluster.

Stage А2. Reduce the orgraph G to acyclic graph.

We iteratively execute steps А2.1–А2.3 until the orgraph becomes acyclic.

Step А2.1. Test the orgraph at consideration for the absence of cycles.

At this step we perform construction of the set of simple cycles of the graph. For this purpose, we execute exhaustive search over all the vertices of the graph. For the next chosen vertex we carry out depth-first search to construct all possible paths in the graph starting from this vertex. Such procedure is a modification of the software implementation [10] in the C# language of the well-known Johnson algorithm [11].

If cycles are revealed as a result of testing, then we execute step А2.2. If the orgraph has no cycles, then we proceed to step А2.4.

Step А2.2. Find the equation removed from the graph, that is, the pair of edges with the same labels corresponding to the equation and incoming to the same vertex of the graph.

Each pair of edges with the same label (number of equation) p is evaluated by the number C_p of cycles that can be broken when this pair of edges is removed from the graph.

Step А2.3. Remove the pair of edges (equation) with label p that corresponds to the maximal value of C_p. Proceed to step А2.1.

Step А2.4. End.

5. EXAMPLE OF EXECUTION OF ALGORITHM 1

Let us illustrate the proposed algorithm 1 on example of the BDDI depicted in Fig. 4. We consider the third BDDI level whose cofactors depend on the variables x₃, x₄, and x₅.

Fig. 4.

BDDI graph.

Stage 1. Partition the set of equations into the BDDI levels.

The equation for each of the BDDI levels are given in Table 3.

Table 3. Equations for BDDI (Fig. 4)

Stage 2. Find the set of implementable cofactors.

Steps 2.1–2.3. Using program [12] of elimination of intermediate variables, construct the truth table of the cofactors of the third BDDI level and find the inversions of the cofactors (Table 4). After that, perform the complete combinatorial exhaustive search over the variants of determining the disjunctive and conjunctive expansions of non-inverse cofactors from Table 4. Write the obtained algebraic formulas in Table 5.

Table 4. Cofactors and their inversions of third BDDI level (Fig. 4)

Table 5. Equations of algebraic expansions of cofactors of third BDDI level

Step 2.4.

Stage А1 of solving problem 1. Choose equations in clusters (cluster reduction).

Step А1.1. The order of cluster consideration follows increasing (nondecreasing) cluster weights: 〈g₆, g₂, g₄, g₁, g₅, g₇, g₃〉.

Step А1.2.

1. Consider the cluster g₆; leave the equation g₆ = g₁ $\vee$ g₄; the set T = {g₁, g₄, g₆}.

2. Consider the cluster g₂; leave the equation g₂ = ${{\bar {g}}_{4}}$ & ${{\bar {g}}_{8}}$; implement heuristic 1; the set T is fulfilled by the vertices from the preserved equation: T = {g₁, g₂, g₄, g₆, g₈}.

3. Consider the cluster g₄; the maximum weight ${{W}_{{{{q}_{4}}}}}$ = 18 is for the vertex g₄ for the equation g₄ = g₆ & ${{\bar {g}}_{1}}$; keep the equation g₄ = g₆ & ${{\bar {g}}_{1}}$; implement heuristic 1; the set T = {g₁, g₂, g₄, g₆, g₈} is left unchanged.

Similarly, we preserve the equations in the other clusters g₁, g₅, g₇, and g₃. The result of execution of stage А1 is the orgraph (Fig. 5) and the corresponding equations (Table 6).

Fig. 5.

Orgraph G after cluster elimination.

Table 6. Equations implemented in graph G after reducing the cofactors

Stage А2 of solving problem 1. Reduce the orgraph G to an acyclic graph.

As an original, we consider the orgraph (Fig. 5).

Iteration 1 (there will be iterations 2 and 3 below).

At step А2.1 we find all simple cycles: {g₁, g₆, g₁}, {g₁, g₄, g₁}, {g₁, g₄, g₆, g₁}, {g₁, g₆, g₄, g₁}, and {g₄, g₆, g₄}.

At step А2.2, for each of the equations (pairs of identically labeled edges) 1, 20, 26 we count the number of broken cycles if we can remove this pair of edges from the graph. It is easy to see that removal of each of the pairs of edges lead to breakage of four contours.

At step А2.3 we choose the pair of edges with label 1 (Fig. 6) that are removed from the graph.

Fig. 6.

Step 1 of converting a graph to acyclic one (dashed edges corresponding to equation 1 are removed).

Iteration 2. At step А2.1 we find one simple cycle {g₄, g₆, g₄} that forms two edges with labels 20, 26.

At step А2.2 we find out that removal of any of the pairs of edges with labels 20, 26 breaks the only simple cycle {g₄, g₆, g₄}.

At step А2.3 we remove the pair of edges with label 20 and obtain the graph (Fig. 7).

Fig. 7.

Resulting acyclic orgraph prescribing the implementable cofactors.

Iteration 3 is not executed until the end, because at step А2.1 we find out that the graph (Fig. 7) is acyclic.

The result of execution of stage А2 is the equations for the found implementable cofactors (Table 7). In Fig. 8 we show the logic circuit corresponding to the found set of implementable cofactors; it has no feedback, because it corresponds to the oriented acyclic graph.

Table 7. Equations corresponding to the implementable cofactors

Fig. 8.

Logic circuit corresponding to resulting acyclic orgraph.

Stage 3. Correct the original multilevel BDDI representation of Boolean function.

At Stage 3 of algorithm 1, in the functional description (Table 3) the equations of Shannon expansion for the cofactors g₂, g₃, g₅, g₆, and g₇ are replaced by the formulas of algebraic expansions from Table 7, and we obtain the functional description

$$\begin{gathered} {{f}_{1}} = {{{\bar {x}}}_{1}}{{h}_{1}} \vee {{x}_{1}}{{h}_{2}};\quad {{f}_{2}} = {{{\bar {x}}}_{1}}{{h}_{2}} \vee {{x}_{1}}{{h}_{3}};\quad {{f}_{3}} = {{{\bar {x}}}_{1}}{{h}_{4}} \vee {{x}_{1}}{{h}_{5}}; \\ {{f}_{4}} = {{{\bar {x}}}_{1}}{{h}_{4}} \vee {{x}_{1}}{{h}_{6}};\quad {{f}_{5}} = {{{\bar {x}}}_{1}}{{h}_{6}} \vee {{x}_{1}}{{h}_{7}}; \\ {{h}_{1}} = {{{\bar {x}}}_{2}}{{{\bar {g}}}_{1}} \vee {{x}_{2}}{{{\bar {g}}}_{3}};\quad {{h}_{2}} = {{{\bar {x}}}_{2}}{{g}_{2}} \vee {{x}_{2}}{{{\bar {g}}}_{8}}; \\ \end{gathered} $$

$$\begin{gathered} {{h}_{3}} = {{{\bar {x}}}_{2}}{{{\bar {g}}}_{5}} \vee {{x}_{2}}{{g}_{6}};\quad {{h}_{4}} = {{{\bar {x}}}_{2}}{{g}_{6}} \vee {{x}_{2}}{{{\bar {g}}}_{7}}; \\ {{h}_{5}} = {{{\bar {x}}}_{2}}{{g}_{6}} \vee {{x}_{2}}{{g}_{{10}}};\quad {{h}_{6}} = {{{\bar {x}}}_{2}}{{g}_{4}} \vee {{x}_{2}}{{g}_{9}}; \\ {{h}_{7}} = {{{\bar {x}}}_{2}}{{g}_{8}} \vee {{x}_{2}}{{g}_{{10}}};\quad {{g}_{1}} = {{{\bar {x}}}_{4}}{{s}_{2}} \vee {{x}_{4}}{{s}_{3}}; \\ {{g}_{2}} = {{{\bar {g}}}_{4}}\& {{{\bar {g}}}_{8}};\quad {{g}_{3}} = {{g}_{7}}\& {{{\bar {g}}}_{6}};\quad {{g}_{4}} = {{{\bar {x}}}_{4}}{{x}_{5}} \vee {{x}_{4}}{{s}_{2}}; \\ \end{gathered} $$

(4)

$$\begin{gathered} {{g}_{5}} = {{g}_{{10}}}\& {{{\bar {g}}}_{4}};\quad {{g}_{6}} = {{g}_{1}} \vee {{g}_{4}};\quad {{g}_{7}} = {{g}_{2}} \vee {{g}_{5}}; \\ {{g}_{8}} = {{{\bar {x}}}_{4}}{{s}_{3}} \vee {{x}_{4}}{{{\bar {s}}}_{1}};\quad {{g}_{9}} = {{{\bar {x}}}_{4}}{{s}_{2}} \vee {{x}_{4}}{{{\bar {x}}}_{5}}; \\ {{g}_{{10}}} = {{{\bar {x}}}_{4}}{{x}_{3}} \vee {{x}_{4}}{{x}_{5}};\quad {{s}_{1}} = {{x}_{5}}{{{\bar {x}}}_{3}}; \\ {{s}_{2}} = {{{\bar {x}}}_{5}}{{{\bar {x}}}_{3}};\quad {{s}_{3}} = {{x}_{5}}{{x}_{3}}. \\ \end{gathered} $$

After formulas replacement it turns out that the equations

$${{s}_{0}} = {{\bar {x}}_{5}}{{x}_{3}};\quad {{s}_{4}} = {{\bar {x}}_{5}}{{\bar {x}}_{3}} \vee {{x}_{5}}{{x}_{3}}$$

are unused (redundant) and absent in the set of coupled formulas (4). As a result of applying the proposed method of logic optimization, in the functional BDDI description the number of literals reduces and we have obtained the results of logic synthesis best in terms of area (Table 8). Information about the used library of logic elements will be given below in description of the computational experiment.

Table 8. Results of logic synthesis

6. ALGORITHMS 2–4 FOR FINDING ALGEBRAIC EXPANSIONS OF COFACTORS IN BDDI

To describe the differences of algorithms 2–4 from the described algorithm 1, we note that in algorithm 1 all cofactors are represented as algebraic expansions, that is, the cofactors with two, three, or four literals in their notation.

We call the formulas of Shannon expansion including just two literals short and the formulas consisting of three or four literals long. The equations of type (2), (3) that replace the formulas of Shannon expansion are referred to as the substituted equations, or substitutions.

Algorithm 2 differs from algorithm 1 in that, at stage 3 of the correction of the original multilevel BDDI representation, the original short equations are not replaced by the found disjunctive or conjunctive expansions.

Algorithm 3 differs from algorithm 1 in that the algebraic disjunctive and conjunctive expansions are sought only for the cofactors represented only by long equations, whereas for the sought expansions we use the cofactors represented in the original notation by both long and short equations.

Algorithm 4 differs from algorithm 3 by an auxiliary step: if in the found resulting formulas of algebraic expansions

$${{g}_{p}} = {{\bar {g}}_{i}} \vee {{\bar {g}}_{j}};\quad {{g}_{r}} = {{\bar {g}}_{i}}\& {{\bar {g}}_{j}};$$

we use the two inverse cofactors, then, by the axioms of Boolean algebra (de Morgan formulas), we write equivalent substitutions in the solution, that is, we write the formulas

$${{g}_{p}} = \neg ({{g}_{i}}\& {{g}_{j}});\quad {{g}_{r}} = \neg ({{g}_{i}} \vee {{g}_{j}}),$$

containing a single inversion operator.

7. PROGRAM IMPLEMENTATION

The software implementation of the above presented algorithms was carried out in the C++ language within the cross-platform Qt environment [13]; here, we intensely applied the previously developed libraries for operations with Boolean objects [14] and for processing the descriptions written in the SF language [15, p. 51]. For purposes of practical use, the general organization of the program is performed according to the rules for developing the design procedures in the FLC-2 system [16].

The program is parametrically adjustable. Its parameters are as follows:

-i <src> is the path to the original file of circuit description represented in form of BDD file, the system of logic equations written in the SF language.

-o <tar> is the path to the resulting file optimized by the number of literals.

-r <config> is the path to the configuration file, the file of INI format of the Windows system containing the sections with the collection of key parameters establishing the modes of program operation:

[BDD_OPT]

. . .

inversion=2

donothandleshort=2

. . .

[DATA]

RPT_Name=e:/FLC2/workDir/protokol.txt

Here, the parameter inversion can take on the values from the set {0,1,2}: 0 means that we do not use the inverse functions for selection of optimizing substitutions; 1 is the equivalent use of both direct and inverse functions; 2 stands for that, in addition to use of inverse functions, we transit to the inverse representation for substitutions:

$${{g}_{p}} = {{\bar {g}}_{i}} \vee {{\bar {g}}_{j}}; \to {{g}_{p}} = \neg ({{g}_{i}}\& {{g}_{j}});$$

$${{g}_{r}} = {{\bar {g}}_{i}} \vee {{\bar {g}}_{j}}; \to {{g}_{r}} = \neg ({{g}_{i}}\& {{g}_{j}}).$$

The parameter donothandleshort adjusts the rules of consideration of the equation from the aspect of searching the substitution of cofactors and can also take on the values from the set {0, 1, 2}: 0 means that all equations of the considered system will undergo testing on replacement, 1 stands for dropout the possible substitutions capable of reducing the number of literals in the equation, which will be performed at the stage of generation of the resulting file; 2 is for dropout at the stage of searching the substitutions.

The parameter RPT_Name from the DATA section determines the path to the file of session protocol containing information about errors in the accepted initial data.

The considered program has several limitations. The fixed ones among them are the following: the number n of arguments of the implemented system of Boolean functions n $\leqslant$ 27; the number of possible representations of an individual cofactor (no more than 96 variants); and the number of edges of the graph G (no more than 30 000). However, achieving these values was not observed in practice because of the required amount of performed calculations. We had the cases of normal operation of the program for dimensions of the adjacency list of graph description of more than 15 000 elements (edges of the graph) and approximately 90 steps of execution of the algorithm for transforming the orgraph to the acyclic form.

8. COMPUTATIONAL EXPERIMENT

We conducted the experiment on testing the efficiency of the programs implementing the proposed algorithms 1–4 for reduction in the area and increase in the performance of the combination logic units implemented as part of custom digital VLSIs (ASIC).

The initial descriptions of the first collection of examples of combination logic were the DNF systems of Boolean functions written in the SF language [15, p. 53] borrowed from library [17] of circuit examples presented in the PLA format; here, the descriptions were converted from the PLA format to the SF format of the FLC-2 system of logic optimization [16].

The second collection of examples was the systems of Boolean functions prescribing the SF descriptions of truth tables of modular adders [18].

For each of examples of the systems of completely specified Boolean functions, we carried out BDDI minimization using the BDD_Builder program [9], also included in the FLC-2. The obtained circuit implementations were called reference for the experiment. The BDDI descriptions and the additionally minimized BDDI descriptions (additional optimization was carried out by means of programs implementing algorithms 1–4 of algebraic expansion of cofactors proposed in this work) were converted to VHDL descriptions and fed to the input of the LeonardoSpectrum synthesizer [19, p. 241]. For each of the examples, the logic circuit synthesis was conducted with the same options of synthesis control and for the same target synthesis library. The target library was the library of designing custom digital CMOS VLSIs; the content of the library is presented in [20].

The parameters of the systems of functions and BDDI descriptions for the first collection of examples are given in Table 9. We established that the GARY and IN0 examples prescribe the same system of functions in form of different DNF systems, that is, DNFs with different sets of elementary conjunctions. For the second collection of examples, the label of example Mod_i corresponds to the adder modulo i.

Table 9. Parameters of original systems of functions and BDDI

Below, in tables presenting the results of our experiments, we use the following denotations for the parameters of the systems of functions f(x) = (f₁(x), …, f_m(x)), x = (x₁, …, x_n): n is the number of variables x₁, …, x_n; m is the number of functions; k is the number of common elementary conjunctions entering the DNFs of all component functions f_j(x), j = 1, …, m.

The resulting logic circuits were evaluated by two parameters: S_ASIC is the total area of all elements of the logic circuit and τ is the circuit delay (in ns). The results of our experiment are listed in Tables 10–12. The best solutions (the circuits of smaller area or the circuits with shorter delay) are labeled by bold face, and asterisk is used to denote the solutions that improve the initial reference solutions, which, as we have already said, are the logic circuits constructed by the initial BDDIs. For each of algorithms 1–4, Table 11 presents the numbers of eliminated (redundant) equations after execution of the corresponding algorithm. The LeonardoSpectrum synthesizer outputs this information if at synthesis there are unused signals revealed in the functional descriptions by which we perform circuit synthesis. If, for any example for each of algorithms 1–4, the number of eliminated equations is zero, then information on such example is absent. For instance, we do not provide the information for the first example Add6 in Table 11, because there are no redundant equations for any of the algorithms.

Table 10. Results of experiment for the first collection of examples

Table 11. Results of experiment for the first collection of examples

Table 12. Results of experiment for the second collection of examples

Let us analyze the experimental results. The first collection of examples consisted of 59 functional descriptions of circuits. For 10 examples of low-dimensional circuits—the circuits CLPL, CO14, NEWAPLA2, NEWBYTE, NEWCOND , NEWTPLA1, NEWTPLA2, RYY6, SYM10, and Z9SYM—application of algorithms 1–4 did not vary the reference solution; therefore, the initial data and the results of computational experiment for these examples are not provided in Tables 9–11.

For the three examples B12, LOG8MOD, and MP2D, application of any of algorithms 1–4 for changing the functional reference BDDI descriptions led to an insignificant increase in the area of the corresponding logic circuit. This is related with the fact that the LeonardoSpectrum synthesizer has its own built-in tools of logic optimization and technological mapping. Technological mapping consists in covering the optimized logic equations by functional descriptions of logic elements entering the design library. Variation in the functional description led to other results of technological mapping. For 33 examples of circuits, application of the proposed algorithms allowed improving their area. Reduction in the area for high-dimensional circuits can be of practical significance: for the INTB circuit the area reduction is 13%, for the Tial circuit it is 18%. In general, algorithms 3 and 4 are more efficient compared to algorithms 1 and 2. Algorithm 4 allows improving the reference solutions (by area) for 27 circuits, and algorithm 3 allows increasing the performance for 18 circuits. Algorithms 3 and 4 can be recommended for practical use in the first wave. It is also not excluded that application of algorithms 1 and 2 can also improve the reference solution.

For the second collection of examples (modular adders), application of algorithms allowed reducing the areas for nine circuits and decreasing the delays for five circuits of 14 ones. The area of the Mod_61 circuit reduced by 28%, and the area of the Mod_37 circuit decreased by 23% (Table 12).

The program experiment also showed that, for reduction in the circuit area, always more efficient are disjunctive and conjunctive expansions of cofactors with the use of their inversions, compared to similar expansions without inversions of cofactors.

9. CONCLUSIONS

Our experiments [9] showed that determination of pairs of mutually inverse cofactors at BDDI optimization considerably improves the results of subsequent synthesis, compared to the BDD optimization executed without finding the inverse cofactors.

In the paper we described software-implemented algorithms of additional minimization of algebraic multilevel BDDI representations of systems of completely specified functions on the basis of disjunctive and conjunctive representations of subfunctions appearing at one BDDI level. Such additional logic optimization by the number of literals in the resulting logic equations prescribing the BDDIs leads to simpler functional descriptions by which logic circuit synthesis is carried out. Decrease in the circuit area, reduced to the decrease in the number of transistors in circuits, allows also reducing the energy consumption of circuits. However, reduction in the number of literals at algebraic expansions that allow frequently decreasing the area of circuits made of library CMOS elements can lead to both reduction and increase in the time delays of circuits.