PROCEEDINGS
OF THE TOMSK POLYTECHNIC INSTITUTE
NAMED AFTER S. M. KIROV, HOLDER OF THE ORDER OF THE OCTOBER REVOLUTION
AND THE ORDER OF THE RED BANNER OF LABOR

Vol. 290
1974

FORMATION OF BLOCKS OF A UNIFIED SET

V. K. POGREBNOI

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

The initial data for solving the problem of forming a unified set of blocks (USB) is the matrix \(A=\|a_{su}\|\, S \times W\) of the frequencies of use of typical structures (TS) in the circuits of computing devices. Here \(S\) is the number of circuits being analyzed, and \(W\) is the number of types of TS adopted for use in the blocks of the set [6]. Given such a matrix, abstracting from the physical nature of the systems under study and of the TS obtained, one can formulate the problem of unifying system blocks as the problem of forming a collection of blocks of minimum nomenclature satisfying certain conditions, which makes it possible to cover the elements of the matrix \(A\) with an admissible quality in accordance with some criterion.

In works [1, 2, 3] this problem is considered under conditions in which there is a large sample of circuits being analyzed and specified block parameters. In this case, the algorithms were based on analysis of the matrix \(A\) in order to construct a generalized matrix \(Z\) of compatibility of pairs of typical structures. The set of blocks was formed according to the matrix \(Z\). After determining the optimal size of the set of blocks, a USB not exceeding the given size was formed. In general, such an approach made it possible, for a particular system, to reduce the nomenclature of blocks by half. The algorithm for forming the USB and a preliminary series of sets according to the matrix \(Z\) is characterized primarily by the fact that, under given restrictions on the size of the set, the algorithm successively forms the most preferable blocks in the sense of the estimates determined by the elements of the matrix \(Z\). That is, the set consists of blocks having the highest estimates. Such a collection of blocks of the set, rigidly limited in nomenclature, turns out to be poorly tied to the specific features of the matrix \(A\), since the process of forming the blocks after construction of the matrix \(Z\) is carried out independently of the matrix \(A\). In this connection it seems expedient to solve the given problem by forming a set of blocks substantially exceeding the dimensions of the USB and selecting from among them an optimal collection of blocks on the basis of covering the sample of circuits according to a certain criterion. This work investigates such an approach and attempts to solve the problem under consideration in an optimization formulation. It is also characteristic that the approach considered is oriented toward a small sample of circuits, including the presence of only one circuit. We note that the method in the above-mentioned works was considered for large

sample sizes and was tested for a matrix \(A\) of size \(60 \times 75\). The formation of a UBD for a matrix of such size in an optimization formulation does not at present seem possible. However, it should be noted that for a large number of real systems the size of matrix \(A\) is considerably smaller. In this connection, in order to obtain a higher-quality solution of the problems and to form a UBD for such systems, there arises a need to develop a method oriented toward small samples of devices.

It should also be noted that the available algorithms [1, 2, 3] form a UBD under given restrictions on the parameters of the blocks. At the same time, the joint study of questions of unification and the determination of rational block parameters, despite the additional difficulties that arise in this connection, deserves close attention, since it makes it possible to substantially improve the quality of the solution of the unification problem under consideration and to justify the adopted block parameters. The approach considered below contains preliminary studies of this question.

Formalization of the Evaluation of Block Quality

The formation of the set of blocks from which the UBD blocks must subsequently be selected is carried out by enumerating possible combinations of standard structures of matrix \(A\). Each combination satisfying certain conditions represents a block variant. To select such variants into the set being formed, it is necessary to introduce an evaluation of their quality. One of the principal factors determining the quality of a block is the frequency with which the block under consideration can be used in implementing the sampling circuits. The frequency of use is determined with allowance for the presence, in some blocks, of redundancy, which lowers the evaluation of the block quality. The higher the value of the redundancy, the lower the evaluation of the corresponding block should be. Moreover, if the redundancy exceeds some prescribed value, then such a block cannot be included at all in the set being formed.

The choice of the permissible value of redundancy is made on the basis of an analysis of the specific conditions of the problem under consideration. Such conditions, in particular, may include the degree of deterioration of the technical and economic indicators of the devices being designed that is introduced by block redundancy; the complication of solving the block-selection problems when the number of formed block variants is increased; and others.

We shall characterize the redundancy of a block by the value of the redundancy coefficient \(K_{\mathrm{u}}\). The coefficient \(K_{\mathrm{u}}\) is defined as the ratio of the total capacity of the unused elements of the block to the capacity of the entire block. The value of the coefficient \(K_{\mathrm{u}}\) that determines the permissible redundancy will be denoted by \(K_0\). To take into account the decrease in block quality determined by the frequency of its use, we introduce a penalty function for the presence of redundancy \(\beta(K_{\mathrm{u}})\). The function \(\beta(K_{\mathrm{u}})\) is defined on the interval \(0 \le K_{\mathrm{u}} < K_0\) as follows:

\[ \beta(K_{\mathrm{u}})=\left(1-\frac{K_{\mathrm{u}}}{K_0}\right). \tag{1} \]

On the interval \(K_0 \le K_{\mathrm{u}} \le 1\), the function \(\beta(K_{\mathrm{u}})=0\), since this interval corresponds to values of redundancy exceeding the permissible value; that is, such block variants must not be used.

Under the assumption of linearity of the value of the deterioration of block quality with an increase in its redundancy, the penalty function \(\beta(K_{\mathrm{и}})\) will also be linear. In this case, for zero redundancy the value of the penalty function is taken to be equal to 1. This maximum value of the penalty function \(\beta(K_{\mathrm{и}})=1\) was chosen on the basis of the condition that the frequency of use of a block with redundancy \(K_{\mathrm{и}}=0\) is introduced into the evaluation of the block without change. The function \(\beta(K_{\mathrm{и}})\), taking into account what was said above, is shown in Fig. 1.

Fig. 1.

For the case when \(K_0 > K_{\mathrm{и}} > 0\), the frequency of use of blocks with the corresponding value of \(K_{\mathrm{и}}\), reduced depending on the value of the penalty function \(\beta(K_{\mathrm{и}})\), is introduced into the evaluation of block quality. The reduced value of the frequency of use \(P_{K_{\mathrm{и}}}\) in this case is determined by the expression

\[ P_{K_{\mathrm{и}}}=S_{K_{\mathrm{и}}}\left(1-\frac{K_{\mathrm{и}}}{K_0}\right), \tag{2} \]

where \(S_{K_{\mathrm{и}}}\) is the number of blocks used in the realization of all analyzed circuits with redundancy \(K_{\mathrm{и}}\). The estimated frequency of use, taking into account all values of \(K_{\mathrm{и}}\) encountered for the \(j\)-th block in the realization of circuits, is determined by the expression

\[ P_j=\sum_{K_{\mathrm{и}}\in K_j} S_{K_{\mathrm{и}}}\left(1-\frac{K_{\mathrm{и}}}{K_0}\right), \quad 0 \leq K_{\mathrm{и}} \leq K_0, \tag{3} \]

where \(K_j\) is the set of values of \(K_{\mathrm{и}}\) for the \(j\)-th block.

The evaluation of a block obtained from expression (3) determines the quality of the block in absolute value, irrespective of the size of the block and the frequencies of use of structures in the circuits on the basis of which the analyzed version of the block was constructed. The size of the block can be taken into account when solving the subsequent problem of selecting the optimal aggregate of blocks. As for the frequency of use of structures in circuits, here it is necessary to conduct a careful study of the influence of this factor on the formation of the set of blocks.

With reference to the problem of forming a set of blocks, an evaluation of block quality is necessary first of all in order to answer the question of whether the given block must be included in the set being formed. If this question is resolved by introducing some limiting value of the estimate, for example \(P_0\), then the possibility of including a block will be determined largely by the frequency of use of the structures constituting the given block. Under these conditions, structures with a low frequency of use may turn out not to be included in any block of the set. The number of such structures will depend on the value of \(P_0\). The number of blocks included in the set will also depend on the value of \(P_0\), since inclusion of a block is carried out when the condition

\[ P_j \geq P_0, \tag{4} \]

is satisfied.

It follows from condition (4) that, in order to reduce the number of blocks in the set, it is necessary to increase the value of \(P_0\). However, this will lead to an increase in the number of structures not included in blocks. Reduction

of the value \(P_0\) to such an extent that all structures are taken into account may lead to an excessive increase in the number of blocks in the set. Consequently, condition (4) is unsuitable for use in forming blocks. A condition is needed that would make it possible to estimate the possibility of including the formed block independently of the frequency of use of the corresponding structures.

In forming such a condition, we shall proceed from the fact that, for any considered aggregate of structures, an ideal variant of a block can be constructed. Then the estimate of the formed variant of the block is compared with the estimate of the ideal block, and a conclusion is drawn about the possibility of including the block in the set. As the estimate of the ideal block, we shall take the average capacity of the considered variant of the block, computed from the expression

\[ m_j^0= \frac{ \displaystyle \sum_{s=1}^{S}\sum_{\omega \in A_j} m_{\omega} a_{s\omega} }{ \displaystyle \sum_{K_i \in K_j} S_{K_i}\left(1-\frac{K_i}{K_0}\right) }, \tag{5} \]

where \(m_{\omega}\) is the capacity of a structure of the \(\omega\)-th type;
\(A_j\) is the set of types of structures constituting the \(j\)-th block.

The quantity \(m_j^0\) characterizes the capacity that the \(j\)-th block should have in order to cover the corresponding structures in all circuits at a frequency of use of the block equal to \(P_j\). The actual capacity of the \(j\)-th block, \(m_j\), is determined by the sum of the capacities of the structures included in it,

\[ m_j=\sum_{\omega \in A_j^0} m_{\omega}, \tag{6} \]

where \(A_j^0\) is the set of structures constituting the \(j\)-th block.

If the quantities \(m_j\) and \(m_j^0\) are compared, then it is obvious that, for any variants of blocks, the condition \(m_j \leq m_j^0\) will be satisfied. Let us denote the excess of \(m_j^0\) over \(m_j\) by \(\delta_j\):

\[ \delta_j = m_j^0 - m_j . \]

The quantity \(\delta_j\) characterizes the loss of capacity due to the presence of redundancy when using the \(j\)-th block. The greater the redundancy for the considered variant of the block, the greater the value of \(\delta_j\). Consequently, the quantity \(\delta_j\) can be used to characterize the quality of the selected types of structures and their quantitative ratio in the variant of the block being formed. In this case, the estimate \(\delta_j\) does not depend on the frequency of use of structures in circuits or on the frequency of use of the block \(P_j\). In order that the quantity \(\delta_j\) not depend on the capacity of the block, as an estimate we shall take the ratio \(\delta_j/m_j^0\). Then the question of the possibility of including the \(j\)-th block in the set being formed can be decided by checking the condition

\[ \frac{\delta_j}{m_j^0}\,100 \leq \delta^0, \tag{7} \]

where \(\delta^0\) is the admissible deviation of the capacity of the formed block from the average capacity of the ideal block, expressed as a percentage.

By means of the quantity \(\delta^0\), the number of block variants in the set being formed can be regulated. If, for the \(j\)-th block, condition (7) is satisfied, then this block is included in the set.

The estimate obtained above responds well to the redundancy of the block and, for the considered aggregate of structures, makes it possible to choose

the best variant of a block, irrespective of the frequency obtained for it in this case. The use of such an estimate reduces to a minimum the possible frequency with which structures of one type are included in UNB blocks, since blocks are formed in such a way as, insofar as possible, to cover with a single type of block the set of structures in the circuits composing the given block. In a number of cases this even leads to undesirable phenomena.

Thus, for example, structures with low and high frequencies of use in circuits have little chance of being combined in one block. To illustrate what has been said above, let us consider a circuit containing, in addition to others, two types of structures with frequencies \(a_{11}=2\), \(a_{12}=13\) and sizes 4 and 2, respectively. The best variant of a block in this case contains one structure of the 1st type and 6 structures of the 2nd. Such a variant may prove unacceptable because of restrictions on the permissible size. A block variant containing one structure each of the first and second types may prove necessary, but by condition (7) it cannot be included in the set. However, this and a number of other shortcomings can be eliminated by introducing the corresponding conditions and restrictions into the algorithm for forming the set of blocks.

Algorithm for Forming the Set of Block Variants

The basic restrictions that must be taken into account when forming block variants are restrictions on the size of a block and on the number of external inputs and outputs. It was noted earlier that in this work the problem of designing a UNB is considered under conditions in which the size of the block is not specified. This means that only the possible range of variation of block sizes is specified. In the general case there may be several such ranges; therefore the algorithm for forming blocks must provide for the possibility of forming only those blocks which, in terms of size, fit into one of the specified ranges.

Thus, there is a sequence \(m_1^1—m_2^1,\ m_1^2—m_2^2,\ldots,\ m_1^k—m_2^k,\ldots,\ m_1^D—m_2^D\) of size ranges. Each formed block variant must satisfy the condition for one of the ranges of the set \(D\), for example the \(k\)-th,

\[ m_j^k \leq m_j \leq m_2^k . \tag{8} \]

In addition, to each \(k\)-th range of sizes there may in the general case correspond some permissible number of inputs and outputs, \(f_\beta^k\) and \(f_\alpha^k\), respectively. Then, in addition to condition (8), for the \(j\)-th block variant corresponding to the \(k\)-th size range, the condition

\[ f_{\beta j} \leq f_\beta^k,\quad f_{\alpha j} \leq f_\alpha^k, \tag{9} \]

must be satisfied, where \(f_{\beta j}, f_{\alpha j}\) are, respectively, the number of inputs and outputs in the \(j\)-th block variant under consideration.

In each specific case, depending on technological conditions and on the formulation of the problem, the number of ranges and the various quantities \(f_\beta\) and \(f_\alpha\) may vary. In particular, there may be only one range of size variation and, correspondingly, one value of the quantities \(f_\beta\) and \(f_\alpha\), or several size ranges and a constant value of the number of inputs and outputs.

The formation of the set of block variants is carried out by enumerating all possible combinations of combining typical structures

into blocks and selecting among them combinations satisfying constraints (8), (9) and the quality condition (7). The process of forming possible combinations of two and three structures for the case in which there are 4 types of structures is represented by the graph in Fig. 2.

Fig. 2.

The set of vertices of any branch of the tree beginning at the zero vertex corresponds to a possible variant of a block containing structures with the numbers of the corresponding vertices of the branch. The graph in Fig. 2 contains 30 possible variants of blocks, each of which consists of either 2 or 3 structures. In the general case, when there are \(W\) types of structures, the number of possible variants of blocks with the number of structures varying in the interval from \(\nu_{\min}\) to \(\nu_{\max}\) can be determined from the expression

\[ \sum_{\nu=\nu_{\min}}^{\nu_{\max}} C_{W+\nu-1}^{\nu}, \tag{10} \]

where \(C_{W+\nu-1}^{\nu}\) is the number of combinations of \(W+\nu-1\) taken \(\nu\) at a time. Thus, for the conditions of the example considered above (\(W=4,\ \nu_{\min}=2,\ \nu_{\max}=3\)), the total number of possible variants, calculated by formula (10), is

\[ C_{4+2-1}^{2}+C_{4+3-1}^{3}=10+20=30. \]

For \(W=10,\ \nu_{\min}=2,\ \nu_{\max}=5\), the number of possible variants is already 2992. It is obvious that for real problems, in which, as a rule, there are 20–30 types of structures, the formation of all possible variants of blocks and the evaluation of their quality will require considerable expenditures of machine time. Therefore the algorithm for forming the set of variants of blocks provides for a number of measures to reduce the number of variants being enumerated. In the course of forming a variant it may turn out that its capacity is equal to or exceeds the capacity \(m_i^D\). In this case there is no point in increasing such a variant by attaching other structures. Continuing the increase of variants is likewise pointless if the maximum permissible number of inputs and outputs is exceeded for them.

A substantial reduction of enumeration is also achieved by discarding low-quality variants. The possibility of excluding poor variants from consideration can be explained as follows. Suppose that some \(j\)-th variant of a block contains a set of structures \(A_j^0\) and does not satisfy the quality condition (7). The question is whether the corresponding vertex can be excluded from the tree of variants and thereby all possible variants constructed through this ...

vertex. It is obvious that among the discarded variants there may be some that satisfy the necessary conditions and must be included in the set being formed. Let us consider one such variant with the set of structures \(A_k^0\). In this case \(A_j^0 \subset A_k^0\), since the variant \(A_k^0\) is constructed on the basis of the variant \(A_j^0\). An improvement in the quality of the variant \(A_j^0\) after adding to it the set of structures \(A_k^0 \setminus A_j^0\) can occur only if the combination of the structures of the set \(A_k^0 \setminus A_j^0\) and one or several structures of the set \(A_j^0\) proves to be extremely favorable and gives a good quality estimate. Thus, the combination of structures \(A_k^0 \setminus A_j^0 \cup \overline{A}_j^0\), where \(\overline{A}_j^0 \subset A_j^0\), as an independent variant has a good estimate—so good that, when it is expanded even by unfavorable structures \(A_j^0 \setminus \overline{A}_j^0\), it satisfies the quality condition.

Here it is important to note that, when using a block with the set of structures \(A_k^0\), the principal redundancy will be provided by the structures \(A_j^0 \setminus \overline{A}_j^0\). For such a block, the set of structures \(A_j^0 \setminus \overline{A}_j^0\) is superfluous. At the same time, the variant with the set of structures \(A_k^0 \setminus A_j^0 \cup \overline{A}_j^0\) will be formed independently of the variant \(A_j^0\), and the structures \(A_j^0 \setminus \overline{A}_j^0\) must and can be combined into a variant with more favorable structures. Similar reasoning can be extended to all variants constructed on the basis of expansion of the variant \(A_j^0\). Consequently, one may conclude that it is legitimate to exclude from consideration all variants constructed on the basis of expanding a variant with inadmissibly low quality.

The possibilities listed above for reducing the number of variants to be enumerated make it possible to construct an efficient algorithm for forming rational variants of blocks. The algorithm is constructed in such a way that the next variant is formed on the basis of an analysis of the set of structures of the preceding variant; that is, in order to form variants of the \(\nu\)-th level there is no need to remember all variants of the \(\nu - 1\)-st level. If the next obtained variant is to be excluded from consideration according to the considerations indicated above, then an attempt is made to form a rational variant by replacing the last structure of the obtained variant by the next one. If it turns out that all structures have been enumerated, then the last two structures are excluded and the process of expanding the remaining set continues. For example, if for the graph shown in Fig. 2 the variant \(\{1, 2, 2\}\) is to be excluded, then the variant \(\{1, 2, 3\}\) is considered next.

If the variant \(\{1, 2, 4\}\) is to be excluded (there is nothing by which to replace the last structure), then the last two structures \(\{2, 4\}\) are excluded, and the variant \(\{1, 3\}\) is considered next. In the case where the variant \(\{1, 2, 3\}\) satisfies all necessary conditions, that is, is included in the set being formed, the variant \(\{1, 2, 2, 2\}\) is considered next. The enumeration process ends if it is not possible to expand a variant containing only structures with the last number. For the example considered, this number is 4.

To increase the number of variants in the set being formed, for variants excluded by the quality condition, the algorithm may provide for an additional check of the condition

\[ \frac{\delta_j}{m_j^0}\,100 \leq \hat{\delta}_0,\quad \text{where } \hat{\delta}_0 > \delta_0 . \tag{11} \]

The quantity \(\overline{\delta}_0\) is introduced in order to exclude only those variants that have a significant deviation of the quality estimate from the admissible value. This makes it possible, on the whole, to expand the possibilities of choice in subse...

of the blocks of the unified set without increasing the value of the admissible estimate $\delta_0$.

The following may be distinguished as the main steps of the algorithm:

1. Formation of the next variant of a block.

2. Verification of condition (9). If condition (9) is satisfied, control is transferred to 3. If condition (9) is not satisfied, the variant is excluded from consideration and control is transferred to 5.

3. Calculation of the estimate and verification of condition (7). If the condition is satisfied, the variant is included in the set being formed and control is transferred to 5. If the condition is not satisfied, then to 4.

4. Verification of condition (11). If the condition is satisfied, the variant is included in the set and control is transferred to 5. If the condition is not satisfied, the variant is excluded and 5 is carried out.

5. Verification of whether all variants have been enumerated. If all have, then 6 is carried out; if not all variants have been enumerated, control is transferred to 1.

6. Printing of the necessary data. End of the algorithm. In addition to the combination of structures constituting a block variant, the block power, its repeatability, and the value of the estimate are output for printing. This completes the formation of the set of rational variants of blocks, from among which the blocks of the unified set are selected.

Selection of the Minimum Nomenclature of Blocks for a Given Redundancy

The problem of selecting the minimum nomenclature of blocks for a given redundancy is the final one in the sequence of problems considered above that are associated with the design of a UNS. The presence of this problem makes the design method considered in the present work differ in many respects from that proposed in works [1, 2, 3]. The quality of the UNS will be determined to a considerable degree by how successfully this problem is solved.

It was noted earlier that in the indicated works the UNS was designed under conditions in which there existed a considerably large sample of circuits, and it was oriented toward use not only in the implementation of the analyzed sample, but also in the implementation of circuits of a similar class. On the contrary, a UNS obtained on the basis of a small sample (including for a single circuit) cannot and should not be oriented toward effective use in the development of subsequent circuits. Of course, a UNS obtained in this way may also be successfully applied in subsequent circuits, but it does not seem possible to control this possibility when designing a UNS on the basis of a sample, for example, of two circuits. This makes it possible to draw the conclusion that, in solving the problem under consideration, it is expedient to take careful account of the specificity of the concrete data on the frequencies of use of TS in circuits. This circumstance considerably narrows the applicability of the blocks obtained for other circuits, but at the same time makes it possible to achieve a higher-quality solution.

It follows from what has been said that the choice of the optimal set of blocks from the formed set must be made from the condition of achieving their best use in the implementation of the circuits being analyzed. Consequently, the problem of selecting the blocks of the optimal set (the blocks of the UNS) must be considered jointly with the analysis of the quality of their use for implementing circuits. It is clear that the UNS obtained in this way will be the best (in accordance with the established criterion) for the circuits of the sample, since it takes into account all

quantitative ratios of the frequencies of use of typical structures in circuits (without any averaging of them).

Let us consider the most essential requirements that the selected set of blocks must satisfy. First of all, this is the requirement of a minimum nomenclature of blocks. The second requirement is the minimum total redundancy that the blocks of the selected set provide when implementing circuits. It is obvious that the requirements of minimum nomenclature and minimum redundancy are contradictory, since reducing the number of types of blocks leads to an increase in redundancy.

The nature of the relationship between the magnitudes of the nomenclature and redundancy under the corresponding formation conditions was established in [3]. This dependence was exponential in character. In the works cited, on the basis of the obtained dependence and using economic indicators, the optimal value of the nomenclature and the redundancy obtained thereby were found. In the present work it is proposed to consider the problem of selecting the optimal set of blocks as a problem of minimizing the nomenclature of blocks for a given redundancy. Such a formulation has a number of practical advantages.

It is possible to trace the dependence between nomenclature and redundancy when there is a large sample of blocks under conditions in which redundancy is a constraint and the nomenclature is minimized. In a number of cases, the technical indicators of the devices being designed are decisive and are practically established independently of economic considerations. For example, the redundancy indicator often cannot exceed some admissible value.

The selected set of blocks must cover all typical circuit structures in the sample. This third requirement may also be considered less rigidly. For example, one may be limited to the requirement of maximum coverage of structures, sacrificing some of them in order to satisfy other requirements more fully.

It should also be noted that the blocks of the selected set should, as far as possible, be more powerful. In a number of cases this requirement may also be disregarded, since the ranges of possible values of block power were taken into account when forming the set of blocks, and no preference is given to larger blocks. The requirements listed above may, in each particular case, be refined depending on the specific conditions of the unification problem being solved.

Analyzing the list of requirements given above, which the selected set of blocks must satisfy, we come to the conclusion that a mathematical programming model must be adopted as the basis for constructing a model for solving this problem. This conclusion is dictated above all by the need to solve the problem of implementing circuits by means of the blocks of the formed set. As applied to a single circuit, a similar problem is considered in [4], with optimization according to the criterion of minimum redundancy. In the present case, the formulation of the problem must take into account a larger number of requirements, which leads to a considerable complication of the problem.

Among the listed requirements, from the point of view of formalization, the greatest difficulty is presented by minimization of the nomenclature of blocks. The requirements of covering all circuit structures at a given value of admissible redundancy are taken into account by constraints.

Let us associate with each $j$-th type of block of the formed set a variable $x_{sj}$, $j = 1, 2, \ldots, n$; $s = 1, 2, \ldots, S$, which determines the number of blocks of the $j$-th type used in covering

types of structures of the \(s\)-th circuit. Then the requirement of covering all structures of circuits, in formalized form, can be written as follows:

\[ \sum_{j=1}^{n} a_{\omega j} x_j^s \geq b_\omega^s,\quad \omega = 1, 2, \ldots, W;\quad s = 1, 2, \ldots, S, \tag{12} \]

where \(a_{\omega j}\) is the number of structures of the \(\omega\)-th type contained in the \(j\)-th block;
\(b_\omega^s\) is the number of structures of the \(\omega\)-th type contained in the \(s\)-th circuit;
\(W\) is the number of types of standard structures obtained in the structural analysis of circuits.

The total redundancy provided by the set of blocks required to cover all structures of the circuits is conveniently expressed through the total redundant capacity. The total capacity of the blocks used in covering the circuits is determined by the expression

\[ \sum_{s=1}^{S} \sum_{j=1}^{n} m_j x_j^s, \tag{13} \]

where \(m_j\) is the capacity of the block of the \(j\)-th type.

The total capacity of the structures of the circuits can be calculated from the expression

\[ \sum_{s=1}^{S} \sum_{\omega=1}^{W} m_\omega b_\omega^s = P, \tag{14} \]

where \(m_\omega\) is the capacity of the structure of the \(\omega\)-th type.

The total redundant capacity obtained when covering the circuits is determined as the difference between the total capacity of the blocks and the total capacity of the circuit structures \(P\):

\[ \sum_{s=1}^{S} \sum_{j=1}^{n} m_j x_j^s - P. \tag{15} \]

The value of the redundant capacity calculated by expression (15) depends on the quality of the selection of the required set of blocks for covering the circuits and on the total capacity \(P\). The quality of the coverage, irrespective of the capacity \(P\), can be determined from the expression

\[ \frac{1}{P} \sum_{s=1}^{S} \sum_{j=1}^{n} m_j x_j^s - 1. \tag{16} \]

Then the constraint on the admissible redundancy in covering the circuits is written in the form

\[ \frac{1}{P} \sum_{s=1}^{S} \sum_{j=1}^{n} m_j x_j^s - 1 \leq P_{\mathrm{n}}, \tag{17} \]

where \(P_{\mathrm{n}}\) is the coefficient of admissible redundancy, characterizing the excess of the total capacity of the blocks selected for covering all structures of the circuits over the total capacity of the circuit structures. The value of the coefficient \(P_{\mathrm{n}}\) is established depending on specific conditions and, as a rule, varies in the interval \(0 \leq P_{\mathrm{n}} \leq 0.2\).

In forming the objective function it is necessary to take into account two factors—the minimization of the nomenclature of the selected set of blocks and preference for more powerful blocks. A reduction in the nomenclature of blocks

is attained when choosing such a set of blocks for which the number of cases in which the condition

\[ \sum_{s=1}^{S} x_j^s > 0,\quad j=1,2,\ldots,n \tag{18} \]

is satisfied is minimal.

Introduce the variable \(\sigma_j\), which takes the value 1 when condition (18) is fulfilled and 0 otherwise. Then the objective function, taking into account the two factors indicated above, can be written as follows:

\[ \min L=\beta_{\sigma}\sum_{j=1}^{n}\sigma_j+\beta_m m^*\sum_{j=1}^{n}\frac{1}{m_j}\cdot\sigma_j,\quad \beta_{\sigma}+\beta_m=1, \tag{19} \]

where \(\beta_{\sigma}, \beta_m\) are weight coefficients that take into account, respectively, the degree of influence of the nomenclature factor and the capacity factor on the value of the objective function \(L\),

\(m_j\) is the capacity of blocks of the \(j\)-th type,

\(m^*\) is the average capacity of the blocks of the formed set, determined by the expression

\[ m^*=\frac{1}{n}\sum_{j=1}^{n}m_j. \tag{20} \]

The resulting problem of minimizing function (19) subject to constraints (12), (17) is a nonlinear and integer problem of large dimension. The integrality condition follows from the real possibility of using a block as an indivisible structural unit. At present there are no effective methods for solving such problems. Some simplification of this problem can be obtained by reducing it to a quadratic programming problem. It is obvious that, as the nomenclature decreases, the frequencies of use of blocks of one and the same type increase. Therefore, when solving the problem of covering circuits in order to reduce the nomenclature of blocks, it is necessary to encourage the \(j\)-th variant of the block depending on the value \(r_j\)

\[ r_j=\sum_{s=1}^{S}x_j^s. \tag{21} \]

As a measure of encouragement it is necessary to adopt some function \(f(r_j)\). Then the problem considered above can be formulated as follows. Maximize the function

\[ \sum_{j=1}^{n}m_j f(r_j)\sum_{s=1}^{S}x_j^s=L(\max), \tag{22} \]

subject to the conditions

\[ \sum_{j=1}^{n}a_{\omega j}x_j^s \geq b_{\omega}^{s},\quad \omega=1,2,\ldots,W;\quad s=1,2,\ldots,S, \tag{12′} \]

\[ \frac{1}{P}\sum_{s=1}^{S}\sum_{j=1}^{n}m_j x_j^s-1\leq P_{\mathrm{и}}, \tag{17′} \]

\[ x_j^s\geq 0,\quad j=1,2,\ldots,n;\quad s=1,2,\ldots,S, \tag{23} \]

\[ x_j^s\text{ are integers for all }j\text{ and }s. \tag{24} \]

If in (22) the function \(f(r_j)\) is linear, then we have a quadratic programming problem. As the linear function \(f(r_j)\), one may take, for example, a function of the following form:

\[ f(r_j)=\delta(r_j-1)=\delta\left(\sum_{s=1}^{S} x_j^s-1\right),\quad 0<\delta\leqslant 1, \tag{25} \]

where \(\delta\) is a coefficient establishing the measure of encouragement.

After substituting into (22) the function \(f(r_j)\) of the form (25), we obtain the quadratic form

\[ \max L=\sum_{j=1}^{n} m_j\delta\left(\sum_{s=1}^{S} x_j^s-1\right)\sum_{s=1}^{S} x_j^s . \tag{26} \]

The presence in the objective function (26) of the magnitude of the capacity of the \(j\)-th block, \(m_j\), makes it possible to choose more powerful blocks.

To solve the quadratic programming problem, known methods [5] may be used. Questions of the practical use of blocks of a unified set are set forth in [4], and obtaining solutions close to the optimum in these problems presents no fundamental difficulties.

REFERENCES

1. V. K. Pogrebnoi, V. Z. Yampolsky. Design of a unified set of blocks for a given class of functional circuits of computing devices. Izvestiya TPI, vol. 269, Tomsk, 1972.

2. Automation of the design of computing devices on elements of integrated microelectronics. Research report. Tomsk, TPI, 1971.

3. V. K. Pogrebnoi. Development and investigation of algorithms for automating the technical stage of designing computing devices. Dissertation for the degree of Candidate of Technical Sciences. Tomsk, TPI, 1970.

4. V. K. Pogrebnoi. Covering circuits of computing devices with blocks of a unified set. Izvestiya TPI, vol. 211, Tomsk, 1970.

5. J. Hadley. Nonlinear and Dynamic Programming. Moscow, “Mir,” 1967.

6. V. K. Pogrebnoi. Structural analysis of functional circuits of computing devices. (See the present collection, p. 21.).