FORMATION OF STABLE COMBINATIONS OF SETS OF MODULES OF SCHEMATIC DIAGRAMS OF COMPUTING DEVICES

E. F. Zhigalova

(Presented by the scientific-technical seminar of the Department of ACS
and the Control Laboratory)

The need for structural analysis of schematic diagrams of computing devices may arise in solving many practical problems, including the grouping of modules into blocks, when the minimum number of block types is chosen as the criterion. The purpose of such analysis is to establish the structural composition of the schematic diagram, i.e., what types of stable combinations it contains and in what ratio. Here, by a stable combination we shall mean a structure consisting of “\(n\)” functionally interconnected modules and recurring in the diagram of a device or a set of devices no fewer than a certain number of times, which we shall subsequently denote by “\(\beta^*\).”

Under conditions of a rapidly changing design base and an increasing level of integration of elements, the “images” of stable combinations are not constant. Thus, at an integration level equal to \(3 \div 4\), the constructive implementations of elementary logical functions (ELF)—“AND,” “OR,” “NOT,” etc.—could be accepted as stable combinations. At an integration level greater than 10, each ELF is implemented by a single module or a part of it, while various sets of modules implement more complex logical functions, whose form changes and becomes more complicated as the integration level increases. This leads to the fact that the existing list of stable combinations must be partially or completely changed when transitioning to a new design base of elements in accordance with the results of structural analysis of diagrams. The difficulty of carrying out structural analysis under these conditions lies in the absence of information about structures—their topology, size, and type. In connection with this, the development of a methodology for structural analysis when structures are not specified a priori is of theoretical interest and has important practical significance. This paper considers a methodology of structural analysis in the case when information about typical structures is completely absent.

Structural analysis of diagrams with structures not specified a priori provides for the solution of a number of problems, such as:

— decomposition of the schematic diagram of a computing device;
— formation of a list of stable combinations (typical structures).

The result of solving the problem of decomposing a diagram is a finite set of structures \(S = \{r_1, r_2, \ldots, r_n\}\), in which a family of its subsets \(S_j,\ j = \overline{1,m}\), is distinguished, possessing the property that any element of the set \(S\) belongs to at least one of the distinguished subsets. The physical interpretation of this is as follows: the set of struc-

…structures \(S\) corresponds to the set of subgraphs obtained by decomposing the graph that interprets the basic circuit diagram of a certain computing device. This set of subgraphs is divided into identical groups forming a family of subsets \(S_j\). To the family \(S_j\) there is assigned a vector \(\vec B=\{b_1, b_2,\ldots,b_n\}\), whose elements show how many elements of the set \(S\) belong to each of the subsets of the family \(S_j\). In other words, the elements of this vector indicate the number of structures of the \(j\)-th type. The given set \(S\) is characterized by the fact that it contains intersecting groups of structures, representing in a certain sense a “conglomerate.” This follows from the decomposition algorithm itself, which makes it possible to obtain all possible structures within a specified range of their cardinalities. The problem of forming typical structures consists in selecting, from the given set \(S\), those subsets of the family \(S_j\) that correspond to the largest value of the elements of the vector \(\vec B\); more precisely, the set of typical structures must include only those subsets for which the condition \(b_j \ge \beta^*\) is satisfied (the quantity \(\beta^*\) was defined above). The fact that the structures of the set \(S\) intersect with one another leads to the fact that the subsets of the family \(S_j\) also intersect with one another.

If the selection of typical structures from the family \(S_j\) is carried out by directly comparing the elements of the vector \(\vec B\) with the quantity \(\beta^*\), then the resulting set will have considerable redundancy. This follows from the fact that the set of typical structures is intended to be used for implementing the circuits being analyzed and circuits of the same class as them, while the basic requirement for implementation is the requirement that the structures be nonintersecting, i.e., each element of the circuit may be placed in only one typical node.

Thus, the solution of the problem of forming typical structures must satisfy the following basic requirements:

1) only nonintersecting subsets may enter into the solution;
2) the repetition frequency of the subsets included in the solution must be no less than the specified value of the quantity \(\beta^*\).

The choice of a criterion for solving this problem is determined by its specificity. Thus, if the maximum of the total number of repetition frequencies of each type of structure is adopted as the criterion, this may lead to structures of small cardinality entering into the solution. Such an approach to solving the problem would significantly worsen the results of the analysis. In this sense, the most rational criterion is one that takes into account the repetition frequency and the cardinality of structures of each type. By introducing weighting coefficients in accordance with the method described in [3], one can, in each particular case, vary these parameters, which makes the given formulation of the problem more flexible. Thus, the structure of each type will be characterized by a certain generalized parameter \(k_{ij}\).

Let us state the problem formally. We shall denote the structures of the set \(S\) by \(i\) \((i=1,2,\ldots,n)\), and the subsets of the family \(S_j^*\) by \(j\) \((j=1,2,\ldots,m)\).

Introduce Boolean variables \(x_{ij}\) having the following meaning:

\[ x_{ij}= \begin{cases} 1, & \text{if the } i\text{-th structure of the } j\text{-th subset}^{1)}\\ & \text{has entered into the solution,}\\ 0, & \text{otherwise.} \end{cases} \]

and the matrices: the intersection matrix \(\|b_{ik}\|\) and the matrix \(\|l_{ij}\|\), where \(b_{ik}=1\) if the \(i\)-th structure contains the \(k\)-th circuit element, and \(0\) otherwise; \(l_{ij}=1\) if the \(i\)-th structure belongs to the \(j\)-th subset, and \(0\) otherwise. On the basis of the matrices \(\|l_{ij}\|\) and \(\|b_{ik}\|\) we obtain the coefficient \(a_{ijk}\), for which we have

\[ a_{ijk}= \begin{cases} 1, & \text{if the } k\text{-th element enters the } i\text{-th substructure}\\ & \text{of the } j\text{-th subset},\\ 0, & \text{otherwise.} \end{cases} \]

In the notation adopted, the problem of forming stable combinations consists in maximizing the linear form

\[ L(x_{ij})=\sum_i^n \sum_j^m \kappa_{ij} x_{ij} => \max \tag{1} \]

under the conditions:

\[ \begin{cases} \displaystyle \sum_i^n \sum_j^m a_{ijk}x_{ij}\leq 1,\quad k=\overline{1,l},\\[1.2em] \displaystyle \sum_i^n x_{ij}\geq \beta^*,\quad j=\overline{1,m}, \end{cases} \tag{2} \]

\[ \tag{3} \]

where

\[ x_{ij}=0;\ 1,\qquad a_{ijk}=0;\ 1, \]

\[ \kappa_{ij}=\gamma_1 b_{ij}+\gamma_2\delta_{ij},\quad \gamma_1 \text{ and } \gamma_2 \text{ are weight coefficients }(\gamma_1+\gamma_2=1); \]

\[ \delta_{ij} \text{ is the cardinality of the } i\text{-th structure of the } j\text{-th type,} \]

\[ b_{ij} \text{ is the number of structures of the } j\text{-th type.} \]

Conditions (2) and (3), respectively, mean that the structures included in the solution do not intersect and that the number of structures of the \(j\)-th type must be no less than the specified value \(\beta^*\).

Problem (1–3) can be reduced to a weighted covering problem in the following way.

On the basis of the matrices \(\|b_{ik}\|\) and \(\|l_{ij}\|\) we construct the matrix \(\|r_{jk}\|\), where \(r_{jk}=1\) if the \(j\)-th subset includes the \(k\)-th circuit element, and \(0\) otherwise. We add to the matrix \(\|r_{jk}\|\) the \((k+1)\)-st column, whose elements are the corresponding values of the vector \(B\). We also extend the matrix \(\|b_{ik}\|\) by adding the \((k+1)\)-st column, whose elements are the numbers of the subsets of the family \(S_j\) corresponding to each structure. On the basis of the extended matrices \(\|r_{jk}\|^*\) and \(\|b_{ik}\|^*\) we construct the subset-intersection matrix \(\|\sigma_{jp}\|_{m\times m}\), where \(\sigma_{jp}\) is equal to the number of intersections of the corresponding subsets. The matrix \(\|\sigma_{jp}\|\) is symmetric. The number of columns and rows of this matrix is equal to the number of subsets of the family \(S_j\).

We perform an element-by-element comparison of the entries of the matrix \(\|\sigma_{jp}\|\) with the values of the corresponding elements of the \((k+1)\)-st column of the matrix \(\|r_{jk}\|^*\), standing at the intersection with the \(j\)-th and \(p\)-th rows, for satisfaction of the relations:

\[ (b_j-\sigma_{jp})\geq \beta^*, \tag{4a} \]

\[ (b_p-\sigma_{jp})\geq \beta^*. \tag{4b} \]

If these relations are satisfied, then we extend the matrix \(\|\sigma_{jp}\|\) by adding the \((j+1)\)-st and \((p+1)\)-st rows and columns, and the matrix \(\|r_{jk}\|^*\), by adding the \((j+1)\)-st and \((p+1)\)-st rows\(^2\). The elements of the new columns and rows of the matrices \(\|\sigma_{jp}\|^*\) and \(\|r_{jk}\|^{**}\) are obtained as follows. In the matrix \(\|b_{ik}\|^*\) we find the rows whose elements standing at the intersection with the \((k+1)\)-st column are equal to the numbers of the \(j\)-th and \(p\)-th

\(^2\) In the case when one of relations 4a and 4b is satisfied, the matrices are extended by only one column and one row.

structures. Among them, intersecting rows are selected and added element by element. Then, by subtracting element by element the resulting row vectors respectively from the \(j\)-th and \(p\)-th rows of the matrix \(\|r_{jk}\|^{*}\), the elements of the \((j+1)\)-st and \((p+1)\)-st rows of the matrix \(\|r_{jk}\|^{**}\) are obtained. The elements located at the intersection of these rows and the \((k+1)\)-st column of the given matrix are respectively equal to the elements located at the intersection of the \(j\)-th and \(p\)-th rows and the \((k+1)\)-st column of the matrix \(\|r_{jk}\|^{*}\), reduced by the amount \(\delta_{jp}\).

The elements of the \((j+1)\)-st and \((p+1)\)-st columns of the matrix \(\|\delta_{jp}\|^{*}\) are obtained analogously to the elements of the matrix \(\|\delta_{jp}\|\). The exception consists of the elements located at the intersection of these columns and, respectively, the \(j\)-th and \(p\)-th rows. The value of these elements is chosen so that the relations

\[ \{b_j-\delta_j,\ j+1\}<\beta^{*}, \tag{5a} \]

\[ \{b_p-\delta_p,\ p+1\}<\beta^{*}. \tag{5b} \]

are satisfied.

As a result of the procedure described, we obtain an extended family of subsets \(S'_j\), possessing the property that all its subsets have a repetition frequency not less than the value \(\beta^{*}\). Let us explain this by a concrete example.

In Fig. 1, where structures are conventionally denoted by circles, the set \(S(1, 2, 3,\ldots, 27)\), obtained by decomposing a certain circuit \(Q\), is shown. Table 1 gives the subsets of identical structures forming the family \(S_j\), and Fig. 2 illustrates this graphically. It should be noted that in this case it is immaterial in which particular elements the structures intersect; the fact of intersection itself is important. This makes it possible to reduce the number of columns of the matrices

Table 1

Fig. 1.

\(\|r_{jk}\|\) and \(\|b_{ik}\|\) by removing those circuit elements that belong to a single structure, and also because intersections of structures can be fixed by a single element. The intersection points may be numbered arbitrarily.

It is obvious that when several structures intersect, from which pairwise nonintersecting ones can be singled out, the points of their intersection with a third structure must be distinct. Thus, for Fig. 1 shown, the intersections of structures 1; 2; 10 can be fixed by one point, whereas the intersections of structures 1; 2; 3 must be fixed by two distinct points. In Fig. 3,a an extended matrix \(\|b_{ik}\|^{*}\) is given, whose row numbers correspond to the numbers of the structures of the given set—

of the family \(S\), and the column numbers to the numbers of intersection points. For this example we have: \(i=\overline{1,27}\); \(j=\overline{1,22}\). The elements of the 22nd column vector correspond to the numbers of the subsets of the family \(S'_j\) (in the present case, for clarity, the subset numbers have been replaced by letter designations). It was noted above that the elements of the matrix \(\lVert b_{ik}\rVert^{*}\) take the values 0 and 1. Zero elements correspond to empty cells of the matrix. Figure 3,b gives the matrix \(\lVert r_{ij}\rVert^{*}\). The row numbers of this matrix correspond to the numbers of the subsets of the family \(S_j\), and the columns correspond to the numbers of the intersection points of these subsets. The matrix \(\lVert r_{jk}\rVert^{*}\) can easily be obtained from the matrix \(\lVert b_{jk}\rVert^{*}\) by elementwise summation of rows with the same index².

Fig. 2

In this example \(j=\overline{1,6}\); \(k=\overline{1,22}\). The elements of the 22nd column vector indicate the number of structures of the corresponding type. Figure 4(a) gives the matrix of intersections of the subsets of the family \(S_j\)—\(\lVert \sigma_{jp}\rVert_{m\times m}\). The matrix \(\lVert \sigma_{jp}\rVert\) is square and symmetric. The number of rows and columns of this matrix is equal to the number of subsets of the family \(S_j\). In this example \(j=p=\overline{1,6}\). The elements of the matrix show the number of intersections of the corresponding subsets.

a)

\[ \lVert \sigma_{jp}\rVert = \]

b)

\[ \lVert \sigma_{jp}\rVert^{*} = \]

\[ \left\| B_{jk} \right\|^{*} = \]

(a)

Sparse matrix diagram with columns numbered \(1,2,\ldots,22\) and rows numbered \(1,2,\ldots,27\). The row labels on the right are:

\[ \begin{array}{c|c} 1 & a\\ 2 & g\\ 3 & b\\ 4 & c\\ 5 & a\\ 6 & d\\ 7 & f\\ 8 & b\\ 9 & a\\ 10 & b\\ 11 & a\\ 12 & d\\ 13 & f\\ 14 & b\\ 15 & a\\ 16 & f\\ 17 & a\\ 18 & c\\ 19 & \text{ }\\ 20 & c\\ 21 & d\\ 22 & c\\ 23 & b\\ 24 & c\\ 25 & a\\ 26 & g\\ 27 & g \end{array} \]

\[ \left\| z_{jk} \right\|^{*} = \]

(b)

Sparse matrix diagram with columns numbered \(1,2,\ldots,22\) and rows labeled

\[ a,\ b,\ c,\ d,\ f,\ g, \]

with the right-hand values respectively

\[ 6,\ 5,\ 5,\ 4,\ 3,\ 3. \]

Fig. 3

By pairwise checking of the fulfillment of relation (a, b) for all elements of the matrix \(\|\sigma_{jp}\|\), we determine the possibility of extending the family \(S_j\).

\[ \sigma_{ab}: \begin{cases} (6-4)<3\\ (5-4)<3 \end{cases} \qquad \sigma_{bf}: \begin{cases} (5-2)=3\\ (3-2)<3 \end{cases} {}^{*}b' \]

\[ \sigma_{ac}: \begin{cases} (6-4)<3\\ (5-4)<3 \end{cases} \qquad \sigma_{cd}: \begin{cases} (5-2)=3\\ (4-2)<3 \end{cases} {}^{*}c' \]

\[ \sigma_{ag}: \begin{cases} (6-3)=3\\ (3-3)<3 \end{cases} \qquad \sigma_{cg}: \begin{cases} (5-1)>3\\ (3-1)<3 \end{cases} {}^{*}c'' \]

From the results of the check, we have that the family \(S_j\) can be extended by the subsets \(a''\), \(b'\), \(c'\), \(c''\). Below the extended family \(S'_j\) is presented. In Fig. 4, (b) the extended

Fig. 4

matrix \(\|\sigma_{jp}\|^{*}\) is presented. The frequencies of repetition of the subsets \(a''\), \(b'\), \(c'\), \(c''\) are respectively equal to 3, 3, 3, 4.

Further calculations show that the family \(S'_j\) can also be extended:

\[ \sigma_{ac'}: \begin{cases} (6-2)>3\\ (3-2)<3 \end{cases} {}^{*}a^{\mathrm{III}} \qquad \sigma_{ca^{\mathrm{II}}}: \begin{cases} (5-2)=3\\ (3-2)<3 \end{cases} {}^{*}c^{\mathrm{III}} \]

\[ \sigma_{ac^{\mathrm{II}}}: \begin{cases} (6-3)=3\\ (4-3)<3 \end{cases} {}^{*}a^{\mathrm{IV}} \qquad \sigma_{cb'}: \begin{cases} (5-2)=3\\ (3-2)<3 \end{cases} {}^{*}c^{\mathrm{IV}} \]

\[ \sigma_{ba^{\mathrm{II}}}: \begin{cases} (5-1)>3\\ (3-1)<3 \end{cases} {}^{*}b^{\mathrm{II}} \qquad \sigma_{ab'}: \begin{cases} (4-1)=3\\ (3-1)<3 \end{cases} {}^{*}d^{\mathrm{I}} \]

\[ \sigma_{bc^{\mathrm{II}}}: \begin{cases} (5-2)=3\\ (3-2)<3 \end{cases} {}^{*}b^{\mathrm{IV}} \qquad \sigma_{dc^{\mathrm{III}}}: \begin{cases} (4-1)=3\\ (4-1)=3 \end{cases} {}^{*}d^{\mathrm{II}} \quad {}^{*}c^{\mathrm{VI}} \]

Let us determine an upper bound for the expansion of the family \(S_j\). It is obvious that the maximum possible number of expansions is \(P = 2p\), where \(p\) depends on the number of intersections. For the given example \(P = 28\). In the case where all subsets intersect with one another,

\[ p = 2 \sum C_{n_t}^{2}, \]

where \(n_t\) is the number of intersecting subsets of the family \(S_j\).

Having obtained the expanded family of subsets, the problem of forming standard structures can be formulated as follows: it is required to select such a set of subsets of the family \(S_j\) that has the greatest total value of the quantities \(\kappa_j\) (\(\kappa_j\) is identical to \(\kappa_{ij}\)).

Introduce Boolean variables \(x_j\), \(j = 1, 2, \ldots, l\), where \(j\) is the number of the corresponding subset of the family \(S_j\).

\[ x_j = \begin{cases} 1, & \text{if the } j\text{-th subset is included in the solution,}\\ 0, & \text{otherwise.} \end{cases} \]

In the notation adopted, the problem of forming standard structures consists in maximizing the linear form

\[ L(x_j) = \sum_{j=1}^{l} \kappa_j x_j \to \max \]

under the conditions:

\[ \sum_{j=1}^{l} a_{ij} x_j \leq 1,\quad i = \overline{1, k}; \]

\[ x_j = 0;\ 1; \]

\[ a_{ij} = 0;\ 1. \]

Thus, the problem of forming standard structures has been reduced to a weighted covering problem, which can be solved by known methods, in particular by the method proposed in [2].

REFERENCES

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

2. V. A. Trubin. On a method for integer programming problems of a special type. Reports of the USSR Academy of Sciences, vol. 189, No. 5, 1969.

3. B. S. Matlis, V. Z. Yamol’skii. Application of the rank-correlation method for determining weight coefficients of indicators of the activity of a higher educational institution. In: Cybernetics and the Higher Educational Institution, issue 2, TPI, Tomsk, 1969.

1. In this work, the concept of a subset is adequate to the type of structures. ↩

2. The summation is performed according to the rules of Boolean algebra. ↩