COVERING CIRCUITS OF COMPUTING DEVICES WITH BLOCKS FROM A UNIFIED SET

V. K. Pogrebnoy

(Presented at the scientific and technical seminar of the Scientific Research Institute of Electronic Computing Machines at TPI)

One of the most important problems arising in the design and practical use of a unified set of blocks (USB) is the problem of optimally covering circuits with the given blocks [1].

The essence of the covering problem is as follows. There is information on the number of standard structures (SS) of each type in the circuit under consideration, and information on the blocks of the set, in which all SS are contained in various combinations. From the set it is necessary to select such blocks, and in such quantities, that the aggregate of their SS, by type and number, would constitute the set of SS contained in the circuit. At the same time, maximum use of the SS of the blocks must be achieved, which is equivalent to attaining the minimum total number of blocks used.

This optimality criterion can be refined if one takes into account the circumstance that the blocks of the set differ in the number of elements contained in them. In the process of covering, a situation may arise in which the choice of one block or another is not determined uniquely. In this case, preference should be given to the block with the smaller number of elements. Taking the above into account, the optimality criterion for the solution of the covering problem consists in achieving the maximum use of elements in the blocks. However, if one takes into account that the blocks of the set differ only insignificantly in the number of elements contained in them, then this refinement of the criterion leads to only an insignificant optimization of the solution. Moreover, as will be shown below, the use of the criterion of the minimum total number of blocks simplifies the solution of the problem.

Let us represent the information on the SS contained in the blocks of the set in the form of a matrix \(A=\lVert a_{ij}\rVert\) of size \(W \times H\), where \(W\) is the number of types of SS contained in the USB, and \(H\) is the number of blocks in the set. The matrix element \(a_{ij}\) characterizes the number of SS of the \(i\)-th type in the \(j\)-th block.

Let us assign to the matrix \(A\) a column vector \(B=\{b_1,\ b_2,\ldots,b_W\}\), whose components \(b_i\) characterize the number of SS of the \(i\)-th type in the circuit under consideration.

Let us define the variable \(x_j\) as the number of blocks of the \(j\)-th type required to cover the circuit under consideration.

Following the criterion of the minimum total number of blocks used, the problem of optimally covering a circuit consists in minimizing the linear form

\[ P:\qquad \sum_{j=1}^{H} x_j = Z, \tag{1} \]

under the conditions

\[ \sum_{j=1}^{n} a_{ij}x_{ji}\geq b_j,\quad i=1,2,\ldots,H, \tag{2} \]

\[ x_j\geq 0,\quad j=1,2,\ldots,H, \tag{3} \]

\[ x_j \text{ is an integer for all } j. \tag{4} \]

The integrality condition follows from the real possibility of using a block as an indivisible structural unit, regardless of whether all the TC’s constituting the block are used or only a part of them.

Let us consider in more detail the process of forming the constraints (2). As a rule, a circuit does not contain all types of TC’s. Therefore, from the matrix \(A\) one may exclude the rows corresponding to the zero components of the vector \(B\). The zero columns that arise in this process are also excluded from the matrix.

The matrix thus reduced is analyzed for the possibility that some blocks (columns) are absorbed by others.

Introduce the following notation:

\(W^*\) — the set of types of TC’s contained in the circuit under consideration;

\(A_j\) — the set of types of TC’s contained in the \(j\)-th block;

\(A_j^*=\{i\mid i\in W^*\cap A_j\}\) — the set of types of TC’s of the \(j\)-th block corresponding to the nonzero components of the vector \(B\).

With the adopted notation, formulate the condition for absorption of the \(p\)-th block by the \(j\)-th.

If among the blocks corresponding to the columns of the reduced matrix there are two blocks with sets of TC’s \(A_j^*\) and \(A_p^*\) such that the conditions

\[ A_p^*\in A_j^*, \tag{5} \]

\[ a_{ip}\leq a_{ij},\quad \text{for all } i\in W^*, \tag{6} \]

are satisfied, then, consequently, the \(j\)-th block absorbs the \(p\)-th. The absorbed \(p\)-th block is excluded from the reduced matrix.

Let us indicate a rule that makes it possible to accelerate the absorption process.

Introduce the function \(\delta_j=\delta(x_j)\), defined on the set of blocks \(x_j\). The value of the function at each \(j\in H\) is determined by the following formula:

\[ \delta_j= \frac{\displaystyle \sum_{i\in A_j^*} a_{ij}d_i} {\displaystyle \sum_{i\in A_j} a_{ij}d_i}, \tag{7} \]

where \(d_i\) is the number of logic elements in the \(i\)-th TC. The quantity \(\delta_j\) is bounded by the values \(0\leq\delta_j\leq 1\). For blocks with \(\delta_j=1\), it is true that \(A_j^*=A_j\). Obviously, blocks with \(\delta_j=1\) cannot be absorbed, since the UNB does not contain blocks with identical combinations of TC’s.

The rule for absorption of blocks in the reduced matrix is as follows. A block with the maximum value of \(\delta_j\) is selected, and then, successively, for all blocks with \(\delta_j<1\), conditions (5), (6) are checked. If these conditions are satisfied for some block, then that block (column) is excluded from the matrix.

Denote the dimension of the resulting matrix by \(m\times n\), and in what follows conduct the reasoning with respect to the problem of maximizing the linear form

\[ P_1:\qquad \sum_{j=1}^{n} x_j=Z, \tag{8} \]

under

\[ \sum_{j=1}^{n} a_{ij}x_j\leq b_i,\quad i=1,2,\ldots,m, \tag{9} \]

\[ x_j \geqslant 0,\quad j = 1, 2, \ldots, n, \tag{10} \]

\[ x_j \text{ is an integer for every } j, \tag{11} \]

\[ a_{ij} \geqslant 0. \tag{12} \]

Such a formulation of the problem is more convenient in the subsequent discussion and, at the same time, does not restrict the possibility of using the results obtained for problem \(P\).

It is known that solving linear-programming problems with the imposition of an integrality requirement is associated with considerable difficulties. Therefore, taking into account the specific features of the problem under consideration—namely, the form of the objective function (8) and the additional condition (12)—it seems expedient to construct a more efficient algorithm for its solution.

Suppose that we are given the linear-programming problem shown in Fig. 1.

Fig. 1.

Before us is a convex region satisfying the condition \(a_{ij} \geqslant 0\) of problem \(P_1\). The figure also shows the iso-objective lines. The optimal continuous solution of such a problem will be at point \((a)\). If the integrality condition is imposed, then the optimal solution will be at one of the points \(b\), \(c\), \(d\). Moreover, it is immaterial which of these points is taken as the solution, since at each of them the objective function assumes equal values.

Definition 1. The set of integer points of the feasible region \(R\) at which the function \(Z\) assumes identical values is called a level.

From Fig. 1 it is clear that all integer points of the region \(R\), with respect to the function \(Z\), are divided into levels. If the levels are numbered as shown in Fig. 1, then the value of the function \(Z\) coincides with the number of the level on one of whose points the given function is defined.

Definition 2. The maximal level \(h_{\max}\) of the region \(R\) is the level containing at least one integer point that satisfies the constraints of problem \(P_1\) and maximizes the function \(Z\).

Let us solve problem \(P_1\) without imposing the integrality condition, and let the optimal solution be \(X = \{x_1, x_2, \ldots, x_n\}\). Of particular interest is the neighborhood of this point, namely, the \(n\)-dimensional unit cube in which it is located. It is important to determine whether this cube contains an integer point belonging to the level \(h_{\max}\). We shall consider this question in the following sequence. First we shall define the unit \(n\)-dimensional cube that contains the continuous point. Then, in this cube, we shall find an integer point optimizing the function \(Z\).

Let the solution of problem \(P_1\) be the point \(X=\{x_1,x_2,\ldots,x_n\}\), in which at least one variable is fractional. Suppose that such a variable is \(x_{j_k}=x_{j_k}^{\circ}+\rho_{j_k}\), \(0<\rho_{j_k}<1\), where \(x_{j_k}^{\circ}\) is the integer part of the value of the variable \(x_{j_k}\) at the point \(X\).

We shall show that the point \(X^\circ=\{x_1^\circ,x_2^\circ,\ldots,x_n^\circ\}\) also lies in the region \(R\). Suppose that the point \(X^\circ\) lies outside the region \(R\). In this case at least one of the constraints (9) is violated. Let this constraint be the \(i\)-th one. Then

\[ \sum_{\substack{j=1\\ j\notin N}}^{n} a_{ij}x_j^\circ+a_{ij_k}x_{j_k}^\circ>b_i,\qquad N=\{1,2,\ldots,n\}, \]

moreover, we have

\[ \sum_{j=1}^{n} a_{ij}x_j\leq b_i, \]

whence it follows that

\[ \sum_{\substack{j=1\\ j\notin N}}^{n} a_{ij}x_j^\circ+a_{ij_k}x_{j_k}^\circ> \sum_{j=1}^{n} a_{ij}x_j . \]

Separating in the right-hand side of the obtained inequality the \(j_k\)-th component \(a_{ij_k}x_{j_k}\), we then have

\[ \sum_{\substack{j=1\\ j\notin N}}^{n} a_{ij}x_j^\circ+a_{ij_k}x_{j_k}^\circ> \sum_{\substack{j=1\\ j\notin N}}^{n} a_{ij}x_j+a_{ij_k}x_{j_k}. \]

The left-hand components of both sides of the inequality are equal to one another, since only the variable \(x_{j_k}\) was changed. Hence it follows that

\[ a_{ij_k}x_{j_k}^\circ>a_{ij_k}x_{j_k}, \]

substituting into the left-hand side \(x_{j_k}^\circ=x_{j_k}-\rho_{j_k}\), we obtain \(a_{ij_k}(x_{j_k}-\rho_{j_k})>a_{ij_k}x_{j_k}\), or \(\rho_{j_k}<0\), and this contradicts the fact that \(\rho_{j_k}>0\). Thus it has been proved that the point \(X^\circ\) lies in the region \(R\).

Let the point \(X=\{x_1^\circ+\delta_1,x_2^\circ+\delta_2,\ldots,x_n^\circ+\delta_n\}\) be an optimal solution of problem \(P_1\) without imposing the integrality requirement. Here \(0\leq\delta_j<1\). Then, in accordance with the proof given above, the point \(X^\circ=\{x_1^\circ,x_2^\circ,\ldots,x_j^\circ,\ldots,x_n^\circ\}\) is integral and lies in the region \(R\). Move the origin of coordinates to this point and introduce constraints of the form \(x_j\leq 1\), \(j=1,2,\ldots,n\). We have the problem of maximizing the linear form

\[ P_2:\qquad \sum_{j=1}^{n} x_j=Z, \tag{13} \]

subject to

\[ \sum_{j=1}^{n} a_{ij}x_j\leq b_i',\qquad i=1,2,\ldots,m, \tag{14} \]

\[ x_j=0,1,\qquad j=1,2,\ldots,n, \tag{15} \]

where

\[ b_i'=b_i-\sum_{j=1}^{n} a_{ij}x_j^\circ . \]

Assume that problem \(P_2\) has been solved by one of the known algorithms for solving programming problems with variables taking the values 0 or 1 [2]. The integer solution obtained in this way \(X^\circ=\{x_1^\circ,x_2^\circ,\ldots,x_n^\circ\}\) belongs

belongs to one of the levels of the region \(R\), for example, to \(h^\circ_{\max}\), and corresponds to the objective function \(Z^\circ\). It is necessary to determine whether the level \(h^\circ_{\max}\) is the maximal level of the region \(R\).

We shall investigate the region \(R\) for the presence of an integer solution \(X^*\) for which \(Z^* \geq Z^\circ\). Let us first note that if the condition \(Z_0 - Z^\circ < 1\) is satisfied, then the solution \(P_2\) is a solution of problem \(P_1\). Here \(Z^\circ\) corresponds to the solution of problem \(P_1\) without constraint (11). The validity of this assertion follows from the integrality of the coefficients in the variables of the function \(Z\).

Let us form constraints of the form

\[ x_j \leq x_j^\circ,\quad j = 1,\,2,\ldots,n. \]

We solve the linear programming problem \(P'\), obtained from \(P_1\) by replacing constraints (9) by (16).

Obviously, the optimal solution of problem \(P'\) is \(X^\circ=\{x_1^\circ, x_2^\circ,\ldots,x_n^\circ\}\), and therefore the region \(R'\), defined by constraints (16), can be excluded from consideration in the investigation of the region \(R\).

Replace constraints (16) of problem \(P'\) by constraints of the form

\[ x_j < x_j^\circ + 1,\quad j = 1,\,2,\ldots,n, \tag{17} \]

and obtain problem \(P''\) with the open region of feasible solutions \(R''\).

We shall show that the sets of feasible integer solutions of \(P'\) and \(P''\) coincide.

Every solution of problem \(P'\) is a feasible solution of problem \(P''\), since in problem \(P''\) the constraints are weaker than in \(P'\). Suppose that there exists a feasible integer solution of problem \(P''\) which is not a feasible solution of \(P'\). In this case, at least one of the constraints (16) of problem \(P'\) is violated. Suppose that the constraint corresponding to the variable \(x_{j_k}\) is violated. Then we have \(x_{j_k} > x_j^\circ\), whence

\[ T = x_{j_k} - x_j^\circ > 0. \]

\(x_j^\circ\) is an integer, and \(x_{j_k}\) is an integer by assumption; therefore \(T\) is an integer.

Moreover, \(x_{j_k} < x_j^\circ + 1\) holds; hence,

\[ T = x_{j_k} - x_j^\circ < 1, \]

but this contradicts the fact that \(T\) is an integer.

Thus it has been proved that the sets of feasible integer solutions of \(P'\) and \(P''\) coincide. It follows from this that the solution of problem \(P'\) is also an optimal solution for problem \(P''\); therefore, in the investigation of the region \(R\), the region \(R''\) may also be excluded from consideration.

We shall investigate the remaining part of the region \(R\). Form the constraint

\[ x_j \geq x_j^\circ + 1 \tag{18} \]

and add it to constraints (9) of problem \(P_1\). Having excluded from it the integrality condition, we obtain problem \(P_j\).

The value of the objective function \(Z_j\), obtained in solving problem \(P_j\), will be checked by the condition

\[ Z_j \leq Z^\circ + \varepsilon,\quad 0 < \varepsilon < 1. \tag{19} \]

Theorem 1. If condition (19) is satisfied for all \(j \in H\), then for problem \(P_1\) the value of the objective function \(Z^\circ\) is optimal.

Proof. First we shall show that, by solving problem \(P_j\) for all \(j=1,\,2,\ldots,n\), all solutions in the region \(R\), except \(R''\), are subjected to analysis.

Suppose that there is a solution \(X^*=\{x_1^*, x_2^*,\ldots,x_n^*\}\) which is not feasible for any of the problems \(P_j\) and \(P''\), and is feasible for problem \(P_1\).

Suppose the solution \(X^*\) is not feasible for \(P''\), i.e., at least one of constraints (17) is not satisfied; then

\[ x_j^* \geq x_j' + 1, \tag{20} \]

but this constraint is a closed boundary of the region \(R_j\) of problem \(P_j\). If, in addition, it also satisfies (9) of problem \(P_j\), then the solution \(X^*\) is a feasible solution of problem \(P_j\). However, this contradicts the initial assumption. It remains to accept that the solution \(X^*\) does not satisfy constraints (9) and, consequently, is not a feasible solution of \(P_1\). Thus it has been shown that, when solving the problems \(P_j,\ j=1,2,\ldots,n\), the entire region \(R\) is examined, except for \(R''\).

Let us solve one of the problems \(P_j\), for example \(P_{j_k}\), and let the solution of problem \(P_{j_k}\) be \(X^k=\{x_1^k,x_2^k,\ldots,x_n^k\}\). We represent the obtained value of the objective function \(Z_{j_k}\) as the sum

\[ Z_{j_k}=Z_{j_k}^{\circ}+\varepsilon,\quad 0\leq \varepsilon<1, \]

where \(Z_{j_k}^{\circ}\) is the integer part of \(Z_{j_k}\).

As was shown earlier, the maximum level containing an integer solution cannot exceed the integer part of the function \(Z_{j_k}\). Therefore one may assert that in the region \(R_{j_k}\) there is no integer solution \(X^k\) with corresponding value of the objective function \(\overline{Z}_{j_k}\) greater than \(Z_{j_k}^{\circ}\), i.e., \(\overline{Z}_{j_k}\leq Z_{j_k}^{\circ}\). Then it is also true that

\[ \overline{Z}_{j_k}\leq Z_{j_k}^{\circ}+\varepsilon . \tag{21} \]

Substituting (21) into (19), we have

\[ \overline{Z}_{j_k}\leq Z_{j_k}^{\circ}+\varepsilon \leq Z^{\circ}+\varepsilon, \]

whence

\[ \overline{Z}_{j_k}\leq Z^{\circ}, \]

i.e., the region \(R_{j_k}\) contains no integer solution for which the value of the objective function exceeds the previously attained \(Z^{\circ}\).

Extending these arguments to all \(R_j,\ j=1,2,\ldots,n\), we obtain that the value of the objective function \(Z^{\circ}\) is optimal for problem \(P_1\), as was required to prove.

Consider the case when condition (19) is violated, i.e., we have \(Z_j>Z^{\circ}+\varepsilon\). In this case it may turn out that \(\overline{Z}_j\geq Z^{\circ}\); consequently, the problem arises of determining \(\overline{Z}_j\) in the \(n\)-dimensional unit cube that contains the optimal solution of problem \(P_j\).

The neighborhood of this hypercube is analyzed in the same way as for the original hypercube. In doing so, regions that satisfied condition (19) in the original hypercube are not examined, nor are those for which the continuous solution lies in a unit hypercube examined earlier.

Thus, in the iterative process of analyzing the neighborhood of the original unit hypercube, we shall follow the following rule.

Suppose that, in the course of analyzing the regions \(R_f\), for some subset \(S\), condition (19) was not satisfied. Then, for each \(j\in S\), a hypercube is constructed that contains the continuous optimal solution of the problem, and for it problem \(P_2\) is formulated and solved. In doing so, a new set \(S_1\) is formed. This set does not include solutions leading to hypercubes already analyzed. At each subsequent step, condition (19) is checked with respect to the maximum level attained at the preceding step.

The process continues until, at some step, it turns out that \(S_j=\varnothing\). The integer solution corresponding to the maximum level,

is fixed and, in accordance with Theorem 1, is an optimal solution of problem \(P_1\).

The advantage of the proposed method is that the integer linear programming problem \(P_1\) is reduced to a linear programming problem and to an integer programming problem with zero variables.

References

1. Automation of certain stages in the design of computing devices. Research report. Tomsk, TPI, 1969.

2. A. A. Korbut, Yu. Yu. Finkelshtein. Discrete Programming. “Nauka,” Moscow, 1969.