STRUCTURAL ANALYSIS OF FUNCTIONAL DIAGRAMS OF COMPUTING DEVICES

V. K. POGREBNOI

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

The study of the problem of unification in the design of computing devices reveals a diversity of possible approaches to solving this problem. This diversity, on the one hand, is generated by the presence of a large number of conditions, each of which individually, or in combination with others in a specific situation, acquires primary importance and thereby determines the approach to solving the problem. On the other hand, the absence of a unified methodology and of any mathematical theory for solving this problem gives rise, under specific conditions, to a diversity of possible methods and algorithms for solving unification problems.

In this connection it is necessary to note that, at the present time, any successful or less successful practical attempts to solve specific unification problems are relevant, since, along with rationalizing the design process and directly improving the characteristics of computing devices, these attempts make it possible to accumulate the material necessary for developing a methodology and a mathematical theory for solving unification problems.

At the same time, despite the existence of such diversity in the approaches and methods for solving unification problems, already at the present stage of research paths are emerging toward the development of more universal, unified approaches and methods. Thus, following the principle already outlined in the course of research—solving unification problems by designing a unified set of blocks [1, 2, 3]—it is possible, independently of the physical nature of the systems being designed and of the hierarchy level at which the unification problem is being solved, to use one and the same scheme for solving the problem. Among the main stages of such a scheme the following may be distinguished:

— construction of graphs of interconnections of the objects of systems of the corresponding hierarchy level;

— structural analysis of the resulting graphs with the aim of determining frequently repeated (typical) subgraphs (typical structures);

— formation, from the typical structures obtained, of unified blocks;

— development of methods for implementing systems with blocks of the unified set with minimal redundancy.

The construction of graphs of interconnections of the objects of systems often does not present fundamental difficulties. However, both the construction and

the method of representing the given graph in a computer has a substantial effect on the specificity and efficiency of the structural-analysis algorithm. As an example of the construction of a graph and of a method for representing it in a computer for the lowest level of the hierarchy of a computing device (the level of logical elements) implemented on micro-modules, one may consider the method proposed in [2]. Here, too, the basic requirements on the method of describing functional diagrams of computing devices at this level of the hierarchy are identified and discussed. The indicated requirements are of a sufficiently general nature and are therefore acceptable under any concrete conditions. However, the methods of description that satisfy these requirements may differ substantially in each particular case.

Structural analysis of the graph obtained, with the aim of identifying repeated subgraphs (typical structures), leads to the need to solve a number of complex problems, for example the problem of graph identification. It should be noted that the results of investigations carried out on solving the problem of identical occurrence of typical structures in diagrams of computing devices make it possible to conclude that the available algorithms [1, 2] can be effectively used to solve this problem as applied to typical structures containing up to 10 elements. Moreover, the emerging ways of improving these algorithms make it possible to hope for a successful solution of the problem for typical structures containing up to 20 elements. The possibility of identifying typical structures of this size by means of the indicated algorithms will make it possible to use them effectively in solving many practical problems, for example in determining a rational nomenclature of large integrated circuits and their applications.

Fig. 1.

In the present work, problems of structural analysis of functional diagrams of computing devices are considered under conditions where some a priori specified list of typical structures (TS) is absent. Let us note that if some set of TS is specified, then they can be identified in diagrams by the algorithm set forth in [2]. The use of the results of identifying such TS will be discussed below. Here we only note that, in the process of identification, the frequencies of use of the given TS are determined, while the functional diagram undergoes no changes; that is, the second variant of the identification algorithm [2] is used.

The representation of the functional diagram in a computer is carried out in accordance with the methodology set forth in [2]. For convenience of use in the subsequent algorithms of structural analysis, the list of connections of the graph of the diagram \(G=(P,U)\) is converted programmatically into a list of vertices \(p_i\), with indication of the direct \(F_{p_i}\) and inverse \(F_{p_i}^{-1}\) mappings, the values of the out-degrees \(\alpha_i\) and in-degrees \(\beta_i\), and the corresponding values of the code numbers [2]. An example of a list of vertices with indication of the data enumerated above, for the graph shown in Fig. 1, is presented in Table 1.

For each \(i\)-th vertex, the table indicates the power \(m_i\), which characterizes the number of structural units, or their parts, implementing the given vertex. In the case where the vertices \(p\) identify elements of integrated circuits [2], the power \(m_i\) characterizes the part of the module of the corresponding integrated circuit.

Table 1

If the vertices \(p_i\) are identified with certain structures (nodes of computing devices), then the power of such vertices shows the number of modules required to implement the corresponding structures.

The main point characterizing the proposed method of structural analysis and determining the paths of its implementation consists in the fact that the analysis is carried out by forming the set of all possible structures with a limited range of powers and by choosing among them the optimal aggregate according to a specified criterion. Such an approach can be characterized as an exact solution method, since, by enumerating the set of formed structures in accordance with their accepted evaluation, the method makes it possible to obtain the best solution, that is, to carry out the structural analysis in the highest-quality manner. At the same time, the exact method can be used only for the analysis of small circuits. Therefore, such an approach is mainly of methodological and theoretical interest.

In analyzing real circuits of computing devices, especially at the element level, it proves possible to use only approximate methods. In obtaining an approximate or rational solution in the given case—as, indeed, in solving other problems—two approaches are possible. The first consists in studying the problem under consideration in an optimization formulation and obtaining an approximate solution. The second approach consists in developing a certain heuristic algorithm that makes it possible to obtain a rational solution. The method considered below makes it possible to obtain an approximate solution through an optimization formulation. In this case the following principal stages of solving the problem of structural analysis are distinguished:

— formalization of the evaluation of the quality of a structure;

— formation of a set of structures of a specified range of powers;

— computation of the quality estimate of the structures formed;

— selection of the optimal aggregate of typical structures.

Formalization of the Evaluation of the Quality of a Structure

Before proceeding to the direct study of the factors affecting the evaluation of structures, let us carry out a qualitative analysis of the influence

results of structural analysis on the result of solving the entire problem, which consists in achieving the maximum possible level of unification. There is no doubt that reducing the nomenclature of TS used for designing UNB helps reduce its size. At the same time, the desire to cover a large part of the elements of diagrams with typical structures of a minimum nomenclature is equivalent to increasing the frequencies of use of the corresponding TS.

Thus, the frequencies of use of TS in the diagrams being analyzed largely determine the quality of the solution to the unification problem. At the same time, the frequency of use of TS depends on their capacity. It is clear that the less capacious the TS selected are, the higher their frequency will be. Designing UNB on the basis of more capacious structures has a positive effect on a number of important characteristics, such as the ratio of the number of terminals and modules of a block, the coefficient of utilization of blocks, and a number of others. Therefore it is important that the TS be sufficiently capacious.

Analyzing what has been said above, one can distinguish two main factors for assessing the quality of structures—capacity and frequency of use. The definition of the capacity of a structure was given above. We shall denote the capacity of the \(i\)-th TS by \(M_i\). The quantity \(M_i\) is readily determined as the sum of the capacities \(m_j\) of the elements \(p_j\) belonging to the set \(A_i\) of elements of the \(i\)-th TS:

\[ M_i = \sum_{p_j \in A_i} m_j . \tag{1} \]

The concept of frequency of use, as applied to assessing the quality of structures, requires clarification. The point is that the frequency of use obtained as a result of structural analysis depends on other structures. The frequency with which a TS occurs in diagrams, calculated independently of other TS, will be called repeatability. The repeatability \(g_i\) of the \(i\)-th structure characterizes the maximum possible frequency of use of a structure of the \(i\)-th type. Note that from the value of the quantity \(g_i\) one cannot judge the value of the frequency of use that will be obtained after analysis. It may turn out that a structure with a high value of \(g_i\) receives a low or zero value of frequency of use. This only means that the elements constituting structures of the \(i\)-th type have entered into other structures. Repeatability thus characterizes the potential possibility of a structure having the corresponding value of frequency of use.

The general assessment of a structure of the \(i\)-th type can be obtained as a weighted sum of the normalized values of the capacity \(m_i'\) and repeatability \(g_i'\):

\[ C_i = \beta_m m_i' + \beta_g g_i', \quad \beta_m + \beta_g = 1, \tag{2} \]

where \(C_i\) is the assessment of the structure of the \(i\)-th type;

\(m_i'\) is the normalized value of the capacity of the structure of the \(i\)-th type;

\(g_i'\) is the normalized value of the repeatability of the structure of the \(i\)-th type;

\(\beta_m, \beta_g\) are the values of the weighting coefficients characterizing the degree of influence of capacity and repeatability, respectively, on the value of the assessment.

The values of the weighting coefficients may be determined in advance by an expert method and refined in the course of the experiment. The normalized values of capacity and repeatability \(m_i'\) and \(g_i'\) have mathematical expectation equal to zero and variance equal to unity.

The assessment \(C_i\) places the structures being compared under equal conditions. Indeed, if a structure has low capacity, then, as a rule, it will have sufficiently high repeatability, and vice versa. In the course of structural analysis, the introduced assessment makes it possible to weed out unpromis-

structures and not take them into account when solving the problem of selecting an optimal set of typical structures. The main drawback of this evaluation is that it can be computed only after the complete set of structures has been formed for all the circuits being analyzed. Thus, the possibility of screening out structures directly in the course of their formation is eliminated.

Processing the structures of the complete set will require a significant amount of computation. At the same time, it should be noted that the formation of an evaluation that would make it possible to screen out unpromising structures in the course of their formation is apparently associated with difficulties of a fundamental nature. Therefore, in what follows the main attention is devoted to questions of increasing the efficiency of algorithms for forming and evaluating structures, rather than to the search for more effective evaluations.

Formation of the Complete Set of Structures

The algorithm considered below makes it possible to form the complete set of structures in a prescribed range of levels (the number of elements constituting the structure). In doing so, the algorithm makes it possible to exclude duplicate structures during their formation, while storing in memory mainly only the original graph of the circuit. The algorithm is constructed in such a way that, for each vertex of the graph, it successively analyzes the region of the graph around that vertex. The analysis is carried out by propagating a “wave” around the vertex until structures with prescribed level boundaries are obtained.

The propagation of such a “wave” is carried out according to certain rules successively around each vertex of the graph. In what follows, this process will be identified with the construction of a tree of structures. The vertices of the tree of structures are the vertices of the graph being analyzed, and the links reflect the membership of the linked vertices in some structure.

Each branch of the tree with its beginning at the initial vertex corresponds to a certain structure. The total number of structures is determined by the number of vertices of the tree, excluding the initial one. The vertices of the tree and the corresponding structures can be distributed by levels. The belonging of a structure, for example, to the \(f\)-th level indicates the presence in the corresponding branch of the tree of \(f\) vertices.

To formalize the process of constructing the tree of structures, we introduce the concept of a chain of mappings. By a chain of mappings we shall mean such a tree in which, at each level, only one vertex has a nonempty mapping. A chain of mappings is the basic element of the algorithm for forming a set of structures, which consists in the successive construction of chains of mappings of the tree of structures. Let us consider in more detail the process of transition from one chain of mappings to another. In the chain of mappings, select the sequence of vertices that have nonempty mappings. In Fig. 2a the sequence of such vertices is marked by a bold line.

The set of vertices of the mappings \(F^f_{p_i}\), located to the left of the vertex \(p_i\) with a nonempty mapping and including this vertex, will be denoted by \(F^f_{p_i,p_j}{}^{-}\). The chain of such mappings is shown in Fig. 2b. By analogy, the vertices located to the right of vertices with nonempty mappings are denoted by \(F^f_{p_i,p_j}{}^{+}\). Sets of such vertices are shown in Fig. 2c. Here it should be noted that the sequence of vertices in the mappings of the original chain and of the newly formed mappings-

… in the names may be arbitrary. However, subsequently, when passing from one chain of mappings to another, this sequence must remain unchanged.

Fig. 2.

The formation of mappings is carried out on the basis of the graph of the circuit and the existing chain of mappings. When forming the mapping \(F_{p_e}^{f}\) at the \(f\)-th level for the vertex \(p_e\), two sets \(A^f\) and \(B^f\) are first formed:

\[ A^f=\{F_{p_e}^{-1}\cup F_{p_e}\cup F_{p_k,p_e^{+}}^{f-1}\}, \tag{3} \]

\[ B^f=\{F_{0,p_i^{-}}^{1}\cup F_{p_i,p_j^{-}}^{2}\cup \ldots \cup F_{p_k,p_e^{-}}^{f-1}\}. \tag{4} \]

The mapping \(F_{p_e}^{f}\) is determined on the basis of the sets \(A^f\) and \(B^f\).

\[ F_{p_e}^{f}=\{A^f/B^f\}. \tag{5} \]

The sequence of constructing mappings is organized in such a way that the chain of mappings traverses the tree of structures, moving from left to right. In this case the newly formed mapping is written in place of the mapping of the maximum level of the preceding chain of mappings. Thus, in the computer memory it is always sufficient to store one chain of mappings, and not the entire tree of structures. After constructing the next mapping of the \(f\)-th level, the structures corresponding to it are stored in the \(f\)-th array \(M_f\). The maximum level of structures that must be obtained in the course of the analysis must be specified before constructing the tree of structures, since the tree itself is not stored and, consequently, subsequent extension without reconstructing it becomes impossible. The structures are recorded in the corresponding arrays in the form of Table 1. The data required for this are taken from the description of the initial graph of the circuit being analyzed.

Calculation of the Quality Estimate of the Formed Structures

It was indicated above that the quality estimate of a structure is carried out according to two factors: the power of a structure of the \(i\)-th type \(m_i\) and the repeatability \(g_i\).

Given the values of the quantities $m_i$, $g_i$ for a structure of the $i$-th type, the estimate $C_i$ is determined from expression (2). As for determining the quantity $m_i$, no difficulties arise here. The quantity $m_i$ is computed from expression (1). Considerable difficulties are caused by determining the quantity $g_i$. For this purpose, the set of structures recorded in the arrays $M_f$ must be divided into groups of identical structures, and for each group the maximum number of nonintersecting structures must be determined. Thus, the problem of determining the quantity $g_i$ is divided into two parts: partitioning the structures into groups and determining a nonintersecting set of structures within each group.

The problem of partitioning structures into groups is considered within each array $M_f$ separately, since structures with different numbers of vertices (different levels of structures) cannot be identical. The number of structures even in a single array $M_f$ may be measured in several thousands; therefore, the algorithm for partitioning structures must be sufficiently efficient. Thus, if the number of structures in an array is $n = 1000$, then the maximum number of comparisons of structures for determining their identity will be $n(n - 1)/2$, or about 500000. However, this is true for the case when all structures are of different types. If, for example, a set of $n = 1000$ structures is divided into $m = 10$ equal groups, then the number of comparisons will be much smaller and will be $n(m + 1)/2 = 1000(10 + 1)/2 = 5500$.

To reduce the number of comparisons of structures and to increase the efficiency of the algorithm for partitioning structures into groups, it seems advisable to construct it according to the following scheme. Select one or several simple conditions that are necessary for the identity of structures, and divide the group of structures under study into subgroups according to these conditions. The identity of any pair of structures belonging to different subgroups is excluded by the failure of the conditions to coincide. Therefore, subsequent comparisons of structures and the identification of identical groups are performed within each subgroup, which makes it possible to substantially reduce the total number of comparisons.

The second important point characteristic of the problem under consideration is that, in this case, when comparing a pair of structures, there is no need to find a one-to-one correspondence between their vertices. It is sufficient only to ascertain whether these structures are identical or not. In this connection, the question of forming such a set of certain simple conditions whose fulfillment would be not only necessary but also sufficient for the identity of the structures being compared appears very important. Of course, the efficiency of the algorithm for establishing identity in this case depends on how much faster the verification of such conditions can be carried out in comparison with establishing a one-to-one correspondence of vertices.

When comparing two structures described by the graphs $G = (P, U)$ and $G' = (P', U')$, the following may be adopted as a necessary condition for identity: for each vertex $p_i \in P$ of the graph $G$ there exists a vertex $p_i' \in P'$ of the graph $G'$ such that $\alpha_i = \alpha_i'$, $\beta_i = \beta_i'$, the set of arc functions $\{\mu_{ij}\}$ of the corresponding mapping $F_{p_i}$ coincides with the set $\{\mu_{ij}'\}$ corresponding to the mapping $F_{p_i'}'$, and $\{\mu_{ij}\}^{-1}$ of the mapping $F_{p_i}^{-1}$ coincides with $\{\mu_{ij}'\}^{-1}$ of the mapping $F_{p_i'}^{'-1}$.

Verification of this condition is carried out using the vertex lists of the structures being compared, presented in the form of Table 1. The process of comparing structures consists in selecting the next vertex from the list of the graph $G$ and searching for a vertex in the graph $G'$ satisfying the indicated condition. The vertex thus found in the graph $G'$ is marked and in the fol-

at the next step, when checking the condition for the next vertex of the graph $G$, is not used. If, for some next vertex $p_i$ of the graph $G$, the condition formulated above is not satisfied, then the structures being compared are not identical. The structures for whose vertices the indicated condition is satisfied are entered into one subgroup. In this case, the vertices of the graphs $G'$ are rewritten in the order in which they were selected when checking the condition, in accordance with the order in which the vertices are recorded in the list of the graph $G$. Such a record subsequently makes it possible, when establishing the identity of graphs within a subgroup, to begin checking identity with one of the possible variants of the one-to-one correspondence of vertices.

As for the question of forming a set of conditions that are necessary and sufficient for establishing the identity of structures, this question requires a special investigation and is not considered in the present work.

The groups of structures formed according to the introduced necessary condition of identity are divided into subgroups of identical structures. The division process is carried out in each of the groups independently of the others and consists in a sequential check of pairs of structures for identity. Such a check is performed in accordance with the algorithm set forth in [2]. In the present case the algorithm works quite efficiently, since there is a high probability that the structures belonging to one subgroup are identical and, consequently, the number of backtracking steps will be small.

After this stage has been carried out for all arrays $M_f$, the structures of all levels will be divided into groups of identical structures. In each group it is necessary to find the maximum number of nonintersecting structures $g_i$, which characterizes the repeatability of the structures of the $i$-th group. Since this problem is considered below as applied to one group, the index $i$ is omitted in the subsequent exposition. The problem of determining a nonintersecting set of structures was considered in [2]. It was assumed there that the structures have different cardinalities. Therefore, in the optimization formulation the problem was reduced to a weighted covering problem. In the case under consideration, all structures belong to one level, that is, they have the same cardinality. This makes it possible to regard the problem of determining $\max g$ as the problem of finding the internal stability number of a graph. Indeed, construct a graph $G=(S,U)$ whose vertices $s_i$ are the structures, and whose edges $s_i - s_j$ indicate the presence of common elements in the $i$-th and $j$-th structures. In other words, on the set of structures of the group we construct an intersection graph. Determining the internal stability number for this graph corresponds to finding the maximum number of nonintersecting (nonadjacent) vertices.

Among the known algorithms for determining the internal stability number one may single out the Magu—Weisman algorithm [4]. What is essential for this algorithm is that it finds all maximal empty subgraphs. For a graph containing 200–300 vertices, the number of maximal empty subgraphs becomes enormously large, and the use of the algorithm leads to considerable difficulties. In the problem under consideration it is important to find the internal stability number itself, and not all maximal empty subgraphs. Here it is necessary to note that the number of groups of identical structures will be large, and the corresponding intersection graphs may contain several hundred vertices. Therefore, one cannot count on using even a relatively efficient algorithm for solving this problem. The only possible course under these conditions is the development

effective algorithm for the approximate solution of the problem of determining the number of internal stability.

Consider the intersection graph \(G = (S, U)\), constructed on the set of structures belonging to one group. If the graph is not connected, then each of its components is considered separately. The algorithm for the approximate computation of the number \(g\) is based on a preliminary ranking of the graph \(G\). The ranking may be started from any vertex. In Fig. 3, a graph \(G\) is shown in Fig. 3a, and the result of its ranking in Fig. 3b.

Fig. 3

The ranking process is carried out as follows. The initial vertex \(s_i\), from which the ranking begins, is assigned rank 1. The second rank consists of the set of vertices in the mapping \(F_{s_i}\). The third rank is formed from the set of vertices contained in the mappings of the vertices of the set \(F_{s_i}\) (the vertices of the second rank). In doing so, vertices that have already entered the set of vertices of the second rank are not included. In the ranked graph all connections of the original graph are preserved. After ranking, the set of vertices of each rank is analyzed in order to determine the maximum number of nonintersecting structures. If, for some \(t\)-th rank, the set of vertices is not connected (for example, for \(t = 4\), Fig. 3b), the maximum number of nonintersecting structures for such a rank, \(g_t\), is determined by the number of vertices contained in this set. Thus, for \(t = 4\), \(g_4 = 5\). In the case where the entire set of vertices (or some part of it) of some \(t\)-th rank is connected, the number \(g_t\) is sought in the same way as for the original graph; that is, ranking is carried out and the quantities \(g'_t\) are determined, from which the quantities \(g_t\) are determined. In determining the quantities \(g'_t\), a situation may also occur in which, at the corresponding ranks, the set of vertices is connected. In this case the quantities \(g''_t\) are determined, from which the quantities \(g'_t\) are determined. Thus, the ranking process in determining the quantity \(g\) is carried out until none of the sets of all ranks contains a connected collection of vertices.

After computing all the quantities \(g_t\), the sequence of numbers \(g_1, g_2, \ldots, g_t, \ldots, g_{u-1}, g_u\) is obtained, where \(u\) is the number of ranks on which

the graph is distributed during ranking. To compute the value \(g\), it is necessary to solve the problem of choosing such a set \(A\) of numbers \(g_t\) that would not be adjacent in the sequence \(t=1,2,\ldots,u\), and

\[ \sum_{t \in A} g_t \to \max . \]

An effective method for solving this problem is a scheme according to which a graph is constructed and a route of maximum length is determined. The construction of the graph of possible traversal routes of the sequence of numbers \(g_t\) is carried out according to a rule that follows from the specific conditions of the problem. The essence of this rule is that, if the traversal of ranks is organized with increasing numbers, then from each \(t\)-th rank it makes sense to move only to ranks numbered \(t+2\) or \(t+3\). Movement to rank \(t+4\) from the \(t\)-th rank is inadmissible, since in the rank numbered \(t+4\) there is the possibility of passing through rank \(t+2\), and the total number of values \(g_t\) increases by \(g_{t+2}\). The graph constructed with the above in mind for nine ranks (Fig. 3, б) is shown in Fig. 4.

Fig. 4

The construction of the graph and the determination of the maximum route are carried out simultaneously. Let us consider the process of constructing the graph and determining the maximum route using Fig. 4 as an example. The construction begins with ranks (vertices) 1 and 2. From vertex 1 one can move to vertices 3 or 4. Next to the vertex numbers in the figure, the sums of the corresponding values of the numbers \(g_t\) are indicated in parentheses. From vertex 2 one can move to vertices 4 and 5. Thus, vertex 4 can be reached through vertices 1 and 2. When moving through vertex 1, the sum of the numbers is \(g_1+g_4=1+5=6\); when moving through vertex 2, the sum of the numbers is \(g_2+g_4=3+5=8\). Therefore the routes beginning \(1—4\) need not be considered subsequently, and the number 8 is placed in parentheses at vertex 4. In the course of construction it may turn out that different routes lead to vertices with the same number. For example, the routes \(1—3—5\) and \(2—5\). In this case, the values in parentheses at these vertices are compared, and routes through the vertex with the smaller value in parentheses are excluded from consideration. If the values in parentheses turn out to be equal, then any one of the set of routes passing through these vertices is excluded.

The route ending at the vertex with the maximum value in parentheses is the solution of the problem. The value in parentheses corresponds to the desired value \(g\).

A ranked graph that has no connections between vertices (let us call it a through graph) possesses a useful property. Regardless of the vertex from which the ranking is begun, the graph obtained is a through graph. In this case, for each graph obtained in this way,

of a through graph the value \(g\), found by the algorithm given above, remains constant.

In the general case, for a non-through ranked graph, when determining the number \(g_t\) on a set of connected vertices, it may be not immaterial which particular vertices are included in the set corresponding to the number \(g_t\). Thus, for example, for the example shown in Fig. 5, the number \(g_2 = 2\) is determined by one of the sets of vertices \((2,4)\), \((2,5)\), \((3,5)\); the number \(g_4 = 2\) by the sets \((9,11)\) or \((10,11)\). However, if in determining \(g_2\) the set \((2,4)\) or \((2,5)\) is chosen, and in determining \(g_4\) the set \((10,11)\) is chosen, then vertex 6 can additionally be included, which will allow the value \(g\), computed by the above algorithm, to be increased by one.

Fig. 5

Taking these points into account leads to a substantial complication of the algorithm given above. The complication occurs through an increase in the number of variants of the vertex sets corresponding to the numbers \(g_t\) and, consequently, an increase in the number of vertices in the graph that is constructed in determining the maximal path. If this additional possibility of increasing the number \(g_t\) is not used, then, independently of this, after determining the value \(g\), a check is made of the sets of ranks that were not included in the solution, for the possibility of including them in the solution.

After determining the values \(g\) for all groups of identical structures, the values of \(g\) and \(m\) are normalized so that these values have mathematical expectation equal to zero and variance equal to one. The estimate of each structure is determined by expression (2). Let us note that all structures of one group have identical estimates, since the cardinality of these structures and the value of the repetition frequency \(g\) are the same for them. The values of the weight coefficients are selected with regard to the specific conditions and also on the basis of an analysis of experimental results.

The estimate thus obtained for a concrete typical structure depends on the quantitative ratio of the repetition frequencies of the types of structures in the functional diagram being analyzed. When analyzing some set of functional diagrams, in estimating a structure it is necessary to take into account the repetition frequencies of structures of the given type in other diagrams. Indeed, structures of some \(i\)-th type occur, for example, in each of five analyzed diagrams twice. Thus, the total frequency is equal to ten. A structure of another \(j\)-th type occurs in all in only one diagram five times. It is clear that the structure of the \(i\)-th type, when each diagram is analyzed, will have a rather low estimate and may turn out to be excluded from further consideration, whereas the structure of the \(j\)-th type may have an estimate sufficient for it not to be excluded. Obviously, such a decision is incorrect, since it is more advantageous to leave the structure of the \(i\)-th type. In this connection, when determining the estimate of a structure it is necessary to take into account its repeatability in all the diagrams being analyzed.

Denote by $g_{ih}$, $h = 1, 2, \ldots, H$ the recurrence of structures of the $i$-th type in the $h$-th circuit. Then the total recurrence of structures of the $i$-th type, $g_i$, which is used in expression (2), is determined as follows:

\[ g_i = \sum_{h=1}^{H} g_{ih}. \tag{6} \]

After the estimates $C_i$ have been determined for all groups, the obtained results are analyzed and a decision is made to exclude from further consideration groups with low estimates $C_i$. An important point here is the establishment of the minimum admissible estimate; denote it by $C_0$. Groups of structures for which the condition

\[ C_i \geqslant C_0, \tag{7} \]

is not satisfied are excluded from further consideration. The value $C_0$ is selected depending on the specific conditions: the number of types of groups, the possibility of subsequent processing of the remaining set of groups, the number of vertices of the initial graphs thereby excluded, and a number of other conditions.

Selection of an Optimal Set of Structures

After the above stages of structural analysis have been carried out, there are $n$ groups of structures of the $j$-th type. Each group is characterized by an estimate $C_j$, the total number of structures $n_j$, and the number of nonintersecting structures $g_j$. The total number of structures of the $j$-th group belonging to the $h$-th circuit, $n_{jh}$, and the set of nonintersecting structures $g_{jh}$ are known. It is necessary, from the entire set of structures, to choose such a set which, without intersecting, would cover the elements of all the circuits being analyzed and at the same time would have a minimal number of types of structures. The subsequent success in solving the entire unification problem depends to a large extent on the quality of the solution of this problem.

A characteristic feature of the problem under consideration is that it must be solved jointly for all circuits. Indeed, if the problem is solved separately for each circuit, then the sets of structures obtained in this way may not coincide in type, which leads to an increase in the total number of types of structures. When solving the coverage problem simultaneously for all circuits, it is possible to take into account the frequency of use of structures of one type in all circuits. It was already noted earlier that, when choosing the nomenclature of structures, it is important that they be as large as possible, that is, the power of the structures must be taken into account. Thus, the solution of the problem of selecting a set of structures must satisfy two basic requirements—the structures must be sufficiently powerful and have a high frequency of use. Let us consider one of the possible formulations of the solution of this problem.

Introduce the variable $x_{jk}^{h}$,

\[ x_{jk}^{h} = \begin{cases} 1, & \text{if the } k\text{-th structure in the } j\text{-th group, belonging to the } h\text{-th circuit,}\\ & \text{is included in the solution; } j = 1, 2, \ldots, n;\ k = 1, 2, \ldots, n_j;\ h = 1, 2, \ldots, H;\\ 0, & \text{otherwise.} \end{cases} \]

Then the frequency of use of structures of the $j$-th type is determined as the sum of the values $x_{jk}^{h}$, $k = 1, 2, \ldots, n_j$. The objective function, taking into account the requirements indicated above, can be written as follows:

\[ \sum_{j=1}^{n} m_j^{2} \left( \sum_{k=1}^{n_j} x_{jk}^{h} \right)^{2} = Z \;(\max), \tag{8} \]

where \(m_j\) is the cardinality of structures of the \(j\)-th type. The quantity \(m_j\) in the objective function (8) is squared in order to give preference to more powerful structures. The quantity

\[ m_j^2 \sum_{k=1}^{n_j} x_{jk}^h \]

is essentially a coefficient of the variables in the objective function, since it characterizes the frequency of use of structures of the \(j\)-th type and their cardinality. This coefficient characterizes the participation of structures of the \(j\)-th group in covering the circuit; therefore, the sum of the variables over the \(j\)-th group in expression (8) is squared. The constraints for this problem are formed from the condition that none of the elements of the circuits being analyzed may simultaneously be contained in two or more structures included in the solution. This condition may be written in the form

\[ \sum_{j=1}^{n} \sum_{k=1}^{n_j} a_{lhjk} x_{jk}^h \leqslant 1;\quad h = 1,\,2,\,\ldots,\,H;\quad l_h = 1,\,2,\,\ldots,\,S_h, \tag{9} \]

where \(S_h\) is the number of elements contained in the \(h\)-th circuit;

\[ a_{lhjk} = \begin{cases} 1, & \text{if the } k\text{-th structure of the } j\text{-th group contains the } l\text{-th element}\\ & \text{of the } h\text{-th circuit,}\\ 0, & \text{otherwise.} \end{cases} \]

Problem (8), (9) belongs to the class of covering problems with a nonlinear objective function. Modern mathematical programming theory does not have sufficiently effective methods for solving such problems. Moreover, the dimension of the problem under consideration may reach several thousands, and the number of constraints, determined by the total number of elements in all the circuits being analyzed, may also exceed one thousand.

Proceeding from this, it appears expedient to analyze more thoroughly the groups of identical structures and to select from them those most promising from the point of view of their use in covering circuits. In this case, the selection of promising groups means the selection of a nomenclature of typical structures. Therefore, under such an approach, this stage is one of the most responsible in structural analysis.

An important advantage of the proposed approach is that the problem of selecting groups can be considered independently for each circuit. This proves possible if the given problem is considered as the problem of covering the elements of circuits by groups of structures according to the criterion of the maximum of their total estimates.

Introduce the variable \(x_j\), which is equal to 1 if the \(j\)-th group of structures is included in the solution, and 0 otherwise. Then the problem of selecting a rational set of groups for the \(h\)-th circuit will consist in maximizing the function

\[ \max L = \sum_{j=1}^{n} C_j x_j, \tag{10} \]

subject to

\[ \sum_{j=1}^{n} a_{lj} x_j \leqslant 1,\quad l = 1,\,2,\,\ldots,\,S, \tag{11} \]

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

where

\[ a_{ij} = \begin{cases} 1, & \text{if the } j\text{-th group of structures contains the } i\text{-th element of the diagram,}\\ 0, & \text{otherwise,} \end{cases} \]

\(C_j\) is the estimate of the structures of the \(j\)-th group.

It was noted above that the problem of selecting structures is solved independently for each diagram. Therefore, in (11) the values \(a_{ij}\) are formed on the basis of the structures of the \(j\)-th group belonging to the diagram under consideration. In doing so, only those structures that entered into the nonintersecting set when determining repeatability are taken into account. The remaining structures cannot be used, since in solving problem (10)—(12), together with the other structures, they will be used to cover the elements of the diagram, and subsequently will be excluded when selecting a nonintersecting set of structures.

Constraint (11) excludes the possibility of intersection between two groups even in one of the elements of the diagram and is therefore too rigid. This may lead to a situation in which, for example, some two groups having the highest estimates \(C_j\), because of an intersection in an insignificant number of elements, cannot be included in the solution. Therefore, instead of problem (10)—(12), the problem of minimizing the function is considered

\[ \min L = \sum_{j=1}^{n} \frac{1}{C_j} x_j, \tag{13} \]

under the conditions

\[ \sum_{j=1}^{n} a_{ij} x_j \ge 1, \tag{14} \]

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

When this problem is solved, some set of structures may intersect. Therefore, the solution of the problem must be corrected by selecting nonintersecting structures covering the maximum number of elements of the diagram. As a result of such correction, some of the elements of the diagram may turn out not to be covered by structures. If this circumstance is undesirable or inadmissible, then the solution of problem (13)—(15) can be improved by solving another covering problem, in which all the structures of the selected groups are used. In this case preference should be given to larger structures. The repeatability factor in this case plays no role, since the nomenclature of structures has already been determined. In this problem the variable \(x_j\) takes the value 1 if the \(j\)-th structure is included in the solution, and 0 otherwise. The problem consists in minimizing the function

\[ \min L = \sum_{j=1}^{n} \frac{1}{m_j} x_j, \tag{16} \]

\[ \sum_{j=1}^{n} a_{ij} x_j \ge 1,\quad i = 1, 2, \ldots, S, \tag{17} \]

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

where \(m_j\) is the cardinality of the \(j\)-th structure;

\(n\) is the total number of structures formed for the diagram under consideration;

\(S\) is the total number of elements of the diagram;

\[ a_{ij} = \begin{cases} 1, & \text{if the } i\text{-th element is contained in the } j\text{-th structure,}\\ 0 & \text{otherwise.} \end{cases} \]

If there is no need to give preference to the capacity of structures, the objective function (16) can be replaced by the simpler function

\[ \min L = \sum_{j=1}^{n} x_j . \tag{19} \]

Problem (19), (17), (18) can be solved by finding a minimal covering. In this case it may turn out that some groups of structures will not be included in the solution. If this is repeated for all the circuits being analyzed, then such a group is automatically excluded from the previously selected nomenclature. Possible intersections of structures can be eliminated by duplicating the elements of the intersection in the circuit. This completes the structural analysis of circuits. The set of structures obtained in covering the circuits is distributed among equivalence groups. The results of the analysis can be represented in the form of a matrix \(A=\|a_{s\omega}\|\), \(s=1,2,\ldots,S\), \(\omega=1,2,\ldots,W\). The matrix element \(a_{s\omega}\) characterizes the number of structures of the \(\omega\)-th kind used in the \(s\)-th circuit.

As is clear from the preceding exposition, structural analysis is associated with solving a large number of large-scale optimization problems and a number of combinatorial problems that are also of large scale. Considering the proposed methodology for carrying out structural analysis as a whole, one may conclude that the work has attempted to solve problems of structural analysis by means of rigorous methods. At the same time, considerable attention was paid to the feasibility of the formulated optimization statements. Complex problems, as a rule, were decomposed into simpler ones or, where possible, reduced to such problems for which acceptable solution methods exist or are proposed.

REFERENCES

1. V. K. Pogrebnoi, V. Z. Yampol’skii. 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 integral microelectronics. Research report. Tomsk, TPI, 1971.

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

4. A. A. Zykov. Theory of Finite Graphs. Novosibirsk, “Nauka,” 1969.