DESIGN OF DIGITAL COMPUTING DEVICES USING A NON-STANDARD SET OF BLOCKS

E. F. ZHIGALOVA, T. G. MAKSIMENKO

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

At present, when solving the problem of arranging the structural elements (modules) of a computing device into blocks, the method of “cutting” a circuit into blocks according to the criterion of the maximum number of intra-block connections has become most widespread. The set of modules included in one block will hereafter be called structures, and the set of blocks obtained in this way a non-standard set (NSS). It is obvious that the modules of structures are functionally interconnected, but in the general case structures may consist of unconnected substructures. Cutting into blocks according to the named criterion has the positive aspect that the resulting blocks have a sufficiently high filling coefficient \(K_z\).

\[ K_z = \frac{n}{N}, \tag{1} \]

where

\[ \begin{aligned} N &\text{ is the maximum possible number of modules in a block,}\\ n &\text{ is the actual number of modules in a block.} \end{aligned} \]

At the same time, this method has a drawback, namely that the topology of the structures is not taken into account at all, and each circuit is represented by its own set of structures. As a result of such an approach, the device being designed becomes, in a certain sense, “unique.” If, moreover, one takes into account the fact that repeated production of computing-device units costs several times less than the manufacture of a new unit, then the desire will be understandable, if not all, then at least part of the blocks from the set obtained from previous cuts, to use in the design of new devices.

Statistical analysis of the schematic diagrams of computing devices shows that devices of one and the same class contain identical structures, which is a good prerequisite for the possibility of using structures from an NSS in newly designed devices.

Common sense suggests that the probability of using an entire block structure is less than the probability of using a part of it. Let us call the block utilization coefficient the quantity \(K_i\), equal to

\[ K_i = \frac{m}{n}, \tag{2} \]

\(n\)—defined above.

The use of blocks with a low coefficient \(K_{\mathrm{и}}\) leads to an increase in the number of blocks in the structure, which may substantially reduce the economic effect of using the given set of blocks, and may also lead to an unjustified increase in the dimensions of the device. Figure 1 shows the dependence of the number of blocks \(P\) in a device on the value of the coefficient \(K_{\mathrm{и}}\). The steepness of this characteristic is different for different classes of computing devices; therefore, the lower rational bound of the coefficient \(K_{\mathrm{и}}^*\) must be determined in each particular case. Thus, the applicability of nonstandard blocks lies in the range \(K_{\mathrm{и}}^* \leq K_{\mathrm{и}} \leq 1\).

Fig. 1

For the further exposition of this question we shall use the apparatus of graph theory, which makes it possible to interpret the principal circuit of a computing device, as well as the structures of blocks, as directed graphs. In terms of this theory, the conditions that each substructure used must satisfy are written as:

\[ K_{\mathrm{и}}^* \leq K_{\mathrm{и}} \leq 1, \tag{1} \]

\[ \forall u \in U \exists x_i,\; y_j \in X \{P(x_i,\; u,\; y_j)\}, \tag{2} \]

\[ \forall L'_i \in L \exists x_i,\; x_j \in X' [I_{\vee}^{-1}(x_i,u)\; \&\; \neg I^{+}(x_i,u) \wedge I^{+}(x_j,v)\; \&\; \exists I_{\vee}^{-1}(x_j,v)] , \tag{3} \]

where \(L = (x, u, p)\) is the graph of the block structure;
\(L'\) is a part of the graph \(L\), or the graph of a substructure of the block.

Conditions (2) and (3), respectively, mean that the substructure used, together with its vertices, must also contain the arcs incident to them; the substructure must contain vertices corresponding to the input and output contacts of the connector. It is advisable to solve this problem in two stages. At the first, preparatory stage, substructures satisfying conditions (2), (3), and (1) are formed a priori. At the second stage, the problem of covering the circuit of the computing device by the obtained set of structures (substructures) is solved.

Algorithm for Partitioning Block Structures into Substructures

Partitioning into substructures may be carried out by successively eliminating elements from the structure, with simultaneous checking for satisfaction of conditions (2) and (3). The number of operations is substantially reduced if the structure represented by a directed graph is partitioned into subsets of finite sequences of elements \(x_0,\; x_1,\; x_2,\; \ldots,\; x_{k-1},\; x_k\), for which the proposition

\[ P(x_0,u,x_1)\; P(x_1,u_2,x_2)\; \ldots\; P(x_{k-1},u_k,x_k) \]

is true, where \(x_0\) and \(x_k\) are vertices corresponding to the input and output contacts of the block connector. Then the problem of partitioning into substructures reduces to finding all paths in the graph with fixed beginning and end. Since we are interested not in all paths in general, but only in those beginning and ending at vertices corresponding to the connector contacts and going in the direction of ori-

…of the graph, this makes it possible to simplify the algorithm presented in [1] as follows. The “improved” adjacency matrix \(R_u\) is constructed on the basis of the adjacency matrix \(R\) of the given graph \(L=(x,u,p)\) with Boolean variables and the incidence matrix \(H\) of the same graph over the free semiring \(K\) with the imposed defining relations:

\[ \xi\theta \ne \theta\xi;\quad \eta\xi=0;\quad \xi\theta=\xi\tau=1. \]

Multiplying the resulting matrix \(R_u\) by itself \(l\) times, where \(l_{\max}\) is equal to the diameter of the graph, we obtain all routes of length \(l\). Here it is also possible to reduce the number of operations if the rows corresponding to vertices \(x_i \in x_1\) for which \(l_x^{-1} \ne \varnothing\) is true are regarded as zero; in other words, these are vertices not corresponding to the input contacts of the connector. We shall illustrate the partitioning process by the example of a graph containing no cycles, shown in Fig. 2, a.

The “improved” adjacency matrix \(R_u\) of the given graph has the form:

\[ R_u= \begin{array}{c} \\[-1.2em] \begin{array}{cccccccc} 1&2&3&4&5&6&7&8 \end{array}\\ \left\| \begin{array}{cccccccc} 0&u_1&0&0&0&0&0&0\\ 0&0&u_2&0&u_5&0&0&0\\ 0&0&0&u_3&0&0&0&0\\ 0&0&0&0&0&u_4&0&0\\ 0&0&0&u_6&0&0&0&u_8\\ 0&0&0&0&0&0&0&0\\ 0&0&u_7&0&0&0&0&0\\ 0&0&0&0&0&0&0&0 \end{array} \right\| \begin{array}{c} 1\\2\\3\\4\\5\\6\\7\\8 \end{array} \end{array} \]

Let the vertices \([x_1,x_7]\) correspond to the input contacts of the block connector, and the vertices \([x_6,x_8]\) to the output contacts. Then, in accordance with the foregoing, we write the matrix \(R_u^*\):

\[ R_u^*= \begin{array}{c} \begin{array}{cccccccc} 1&2&3&4&5&6&7&8 \end{array}\\ \left\| \begin{array}{cccccccc} 0&u_1&0&0&0&0&0&0\\ 0&0&u_7&0&0&0&0&0 \end{array} \right\| \begin{array}{c} 1\\7 \end{array} \end{array} \]

As a result of multiplying the matrix \(R_u^*\) by \(R_u\), we obtain the matrix \(R_{u1}^*\). The matrix \(R_{u2}^*=R_{u1}^*\times R_u\), and so on. \(R_{ul}^*=R_{u,l-1}^*\times R_u\). The multiplication process ends when the matrix \(R_{ul}^*\) becomes zero. Thus, in the present example we have

\[ R_{u2}^*= \begin{array}{c} \begin{array}{cccccccc} 1&2&3&4&5&6&7&8 \end{array}\\ \left\| \begin{array}{cccccccc} 0&0&0&u_1u_2&u_1u_5&u_1u_3&0&0\quad 0&u_1u_5u_8\\ & & &+u_1u_5u_6&u_7u_3&u_4& &\\ 0&0&0&0&0&0&0&0 \end{array} \right\| \begin{array}{c} 1\\7 \end{array} \end{array}, \]

\[ R_{u3}^*= \begin{array}{c} \begin{array}{cccccccc} 1&2&3&4&5&6&7&8 \end{array}\\ \left\| \begin{array}{cccccccc} 0&0&0&0&0&u_1u_2u_3&u_1u_5u_6&u_4&0&0\\ & & & & &+u_1u_5u_6u_4& & &\\ 0&0&0&0&0&0&0&0 \end{array} \right\| \begin{array}{c} 1\\7 \end{array}. \end{array} \]

Fig. 2

It is obvious that the matrix \(R_{u}^{*}\) will be zero. The presence of terms in the elements of the matrix \(R_{ul}^{*}\) indicates the presence of parallel paths. Thus, we have obtained the following paths, beginning and ending, respectively, at the vertices:

\[ 1\ u_1\quad 2\ u_2\quad 3\ u_3\quad 4\ u_4\quad 6, \tag{1} \]

\[ 1\ u_1\quad 2\ u_5\quad 5\ u_8\quad 8, \tag{2} \]

\[ 1\ u_1\quad 2\ u_5\quad 5\ u_9\quad 4\ u_4\quad 6, \tag{3} \]

\[ 7\ u_7\quad 3\ u_3\quad 4\ u_4\quad 6. \tag{4} \]

It is easy to verify that these paths satisfy conditions (2) and (3). Analysis of the paths obtained shows that paths (1) and (3) begin and end at the same vertices \([x_1, x_7]\). This means that they cannot be used each separately and are component parts of one “complex” path passing through the vertices \([1, 2, 3, 5, 4]\). It follows that the substructures corresponding to paths beginning and ending at the same vertices must be combined into one. In accordance with this, the structure represented by the given graph is divided into three substructures that include the following elements:

\[ 1,\ 2,\ 3,\ 4,\ 5,\ 6,\qquad (1) \]

\[ 1,\ 2,\ 5,\ 8,\qquad (2) \]

\[ 7,\ 3,\ 4,\ 6.\qquad (3) \]

In practice it is known that the circuit of a computing device, represented in a real basis, contains “specific” connections that link certain sets of elements into an indivisible group. Examples of such connections may be modules that implement at the input the conjunction of input signals. It is obvious that through the vertex of the graph corresponding to such a module there will pass as many paths as the number of variables it combines. However, the substructures corresponding to these paths cannot operate autonomously, since this would lead to a substantial change in the algorithm of operation of the device. It may be stated at once that in some cases, in order to expand the functional capabilities of modules, structures may also be divided by inputs, provided that the electrical connection diagram is not disturbed. Thus, the RTM of the IC elements of the 155 series permits up to two inputs not to be used, leaving them free. In this case an element of type LB 551 can perform the function of elements LB 553 and LB 554, and an element LB 554 can perform the function of element LB 553. Therefore, when partitioning, it is sufficient to recode the module types. In the remaining cases, in order to divide structures, certain changes must be introduced into the partitioning algorithm itself. Thus, after fixing the vertices corresponding to modules that are carriers of specific connections, one should carry out the partitioning in accordance with the algorithm described. Then one should “glue” the paths containing the fixed vertices. Having considered the algorithm for partitioning structures whose graphs do not contain cycles, we turn to consideration of the more complex case in which the graph contains cycles. As an example, let us take the graph shown in Fig. 2, b.

Let the vertices \([x_1, x_7]\) correspond to the input contacts of the unit connector, and the vertex \([x_5]\) to the output contact. The vertices \([x_2, x_5, x_4, x_6]\) enter into the cycle \(Q\). In accordance with the algorithm described, let us partition the given—

… graph into paths, setting equal to zero those terms of the elements of the matrix \(R_{ui}^{*}\) in which some factor occurs more than once, thereby excluding repeated traversal along one and the same path. Then we obtain the following paths beginning at the vertices \([x_1, x_7]\):

\[ 1\ u_1\ 2\ u_3\ 3\ u_4\ 4\ u_5\ 5, \tag{1} \]

\[ 1\ u_1\ 2\ u_3\ 3\ u_4\ 4\ u_5\ 6\ u_2\ 2, \tag{2} \]

\[ 7\ u_7\ 6\ u_2\ 2\ u_3\ 3\ u_4\ 4\ u_5\ 6, \tag{3} \]

\[ 7\ u_7\ 6\ u_2\ 2\ u_3\ 3\ u_4\ 4\ u_6\ 6, \tag{4} \]

where paths (2) and (4) do not satisfy condition (3), and paths (1) and (3) do not satisfy condition (2). The obtained set of paths will satisfy conditions (2) and (3) if each path is supplemented, respectively, by the arcs \((u_6,u_2)\), \((u_5)\), \((u_6)\), \((u_5)\), as a result of which we obtain that paths (1) and (2), (3) and (4) coincide pairwise, i.e., the given graph is decomposed into only two paths satisfying conditions (2), (3):

\[ \begin{cases} 1\ u_1\ 2\ u_3\ 3\ u_4\ 4\ u_5\ 5\ u_6\ 6,\\ 7\ u_7\ 6\ u_2\ 2\ u_3\ 3\ u_4\ 4\ u_6\ 6\ u_5\ 5, \end{cases} \tag{1a, 2a} \]

each of which includes the cycle \(Q\). It follows from this that if a path passes along arcs belonging to a cycle, then this path must also include the cycle itself. The following method can be proposed for decomposing structures whose graphs contain cycles.

Fig. 3.

First determine the subset of vertices and arcs belonging to the cycle \(Q\), and then “contract” the cycle \(Q\), identifying all its vertices in the process. As a result, the graph containing the cycle \(Q\) is transformed into a graph without a cycle. We illustrate this procedure using the example of the graph shown in Fig. 3, a, where the vertices \([x_3,x_4,x_5,x_6]\) and the arcs \([u_3,u_4,u_5,u_6]\) constitute the cycle \(Q\). In Fig. 3, b, the same graph is shown after contraction of the cycle. In accordance with the algorithm, the graph shown in Fig. 3, b, is decomposed into the paths:

\[ \begin{cases} 2\ u_2\ 3'\ u_7\ 7,\\ 1\ u_1\ 3'\ u_7\ 7, \end{cases} \tag{1, 2} \]

satisfying conditions (2), (3). Now it is sufficient to append the cycle \(Q\) itself to each path in place of the vertex \(3'\); then paths (1) and (2) will have the form:

\[ \begin{cases} 2\ u_2\ (3\ u_3\ 5\ u_4\ 6\ u_5\ 4\ u_6\ 3)\ u_7\ 7, \tag{1}\\ 1\ u_1\ (3\ u_3\ 5\ u_4\ 6\ u_5\ 4\ u_6\ 3)\ u_7\ 7. \tag{2} \end{cases} \]

Thus, the tasks of partitioning into substructures are divided into the following main stages:

1) identification of contours in the graph;
2) partitioning into elementary routes;
3) construction of substructures satisfying conditions (2) and (3).

In [4] an algorithm is described for identifying contours in a directed graph. To implement this algorithm on an M 220 class computer, the initial information is represented in the form of a list of functional connections between the elements in a block. This initial information is then represented programmatically by a two-dimensional array \(A[1:N, 1:4]\) of the form \(A(M_i\ \psi_{\mu ij}\ M_j)\), where

\(M_i, M_j\) are the numbers of informationally connected elements,
\(\mu_{ij}\) is the connection function,
\(\Psi\) is a fictitious column for marking contacts,
\(N\) is the number of rows in the array.

Fig. 4

As a result of partitioning the structures of blocks, we obtain some set of routes with fixed beginnings and ends. In this case, depending on the topology of the graph, this set may consist either of nonintersecting subsets or of intersecting ones. We shall call intersecting those subsets of routes that include at least one common arc or vertex. In Fig. 4, \(a, b\), graphs of different topology are shown. In accordance with the given partitioning algorithm, we obtain that the graph (4, \(a\)) is divided into the routes: I — \((1\ u_1\ 3\ u_2\ 4\ u_4\ 8)\); II — \((1\ u_1\ 3\ u_2\ 4\ u_3\ 7)\); III — \((2\ u_5\ 5\ u_6\ 4\ u_4\ 8)\); IV — \((2\ u_5\ 5\ u_6\ 4\ u_3\ 7)\), where the vertices \([x_1, x_2]\) correspond to input contacts, and the vertices \([x_7, x_8]\) to the output. All routes of the graph (4, \(a\)) pass through the vertex \(x_4\), i.e., all routes intersect. The graph shown in Fig. 4, \(b\), is divided into the routes: I — \((1\ u_1\ 6\ u_2\ 7\ u_8\ 4\ u_9\ 5)\); II — \((1\ u_1\ 6\ u_9\ 8\ u_4\ 9)\), III — \((2\ u_6\ 3\ u_7\ 4\ u_9\ 5)\), IV — \((10,\ u_4\ 8\ u_5\ 9)\). Here routes III and IV do not contain a single common vertex and are nonintersecting. Let us consider one method for checking route intersections, easily implemented on a computer. If the entire set of obtained routes is divided into such subsets of routes that begin (end) at some one vertex, then the following becomes obvious. If the graph \(L=(x,u,p)\) is par—

is broken down into intersecting paths beginning respectively at vertices \(x_i\) and \(x_j\), in which at least two paths \(\mu_i \subset T_i\) and \(\mu_j \subset T_j\) end at one and the same vertex \(x_k\), i.e., \(x_k \in \mu_i\) and \(x_k \in \mu\). For example, the graph shown in Fig. 4, a, contains two subsets \(T_1\), combining paths I and II, and \(T_2\), combining paths III and IV. Here we have that vertex \(x_7 \in T_1\) and \(x_7 \in T_2\), that is, the subsets \(T_1\) and \(T_2\) intersect. The graph shown in Fig. 4, b, contains the subset \(T_1\), combining paths I and II, and the subsets \(T_3\) and \(T_2\), consisting respectively of paths III and IV. Here the subsets \(T_2\) and \(T_3\) do not contain a single common vertex, that is, they are not intersecting. Information on intersections of paths will be used below in solving the problem of covering circuits by a nonstandard set of blocks, which will be considered later. The substructures obtained as a result of the partition are minimal substructures satisfying conditions (2) and (3), for which, in the general case, condition (1) on the left is not satisfied. To obtain substructures satisfying all three conditions, it is sufficient to combine the minimal substructures in such a way that the condition \(K_u^* \le K_{ui}\) is fulfilled.

Summarizing the above, we list the main tasks of the preparatory stage:

1. Identification of cycles in the graph.
2. Partitioning graphs into paths satisfying conditions (2) and (3).
3. Formation of nonintersecting subsets of paths.
4. Formation of substructures satisfying conditions (1), (2), (3).

The algorithm for partitioning blocks into substructures is implemented in the ALPHA language. The main task of the second stage consists in implementing, in the best possible way, the circuits of computing devices by the obtained set of structures. Let us consider the methodology for solving this problem.

Covering Circuits of Computing Devices by a Nonstandard Set of Blocks (NSB)

Before giving a formal description of the statement of this covering problem, let us consider some of its physical features and formulate the basic requirements for the covering. When covering circuits by a specified set of nonstandard blocks, in every structure accepted for implementation all modules must be used, as well as the functional connections between them; in other words, the utilization coefficient \(K_u\) of each structure must be equal to one. This requirement follows from the very method of forming structures described above. It is also obvious that each element of the circuit must be assigned to only one particular structure. In practice, when covering a circuit by a set of structures, some elements, as well as sets of elements, may be assigned to several structures.

Fig. 5

This is a consequence of the fact that, on the one hand, in a real circuit some sets of elements whose topologies of functional connections are identical to certain structures from the given set intersect, as is shown in Fig. 5, where \(P\) is the circuit of a computing...

…of the device; \(A\) and \(B\) are regions corresponding to certain sets of functionally related elements belonging to the circuit \(P_i\); the point \(a\) represents an element that simultaneously belongs to both sets. On the other hand, the circuit may contain sets of elements whose interpreting graph is identical to the graph obtained by identifying isomorphic parts of two, three, etc., graphs interpreting structures from the given set, as shown in Fig. 6. Figures 6, \(a\) and 6, \(b\) show graphs

Fig. 6

of two structures I and II containing isomorphic parts, indicated by dashed lines, while Fig. 6, \(c\) presents a part of the graph interpreting the schematic diagram, where the subgraphs isomorphic to graphs I (Fig. 6, \(a\)) and II (Fig. 6, \(b\)) are indicated by dashed lines. It is obvious that the given circuit cannot be implemented by both structures in such a way that the requirements formulated above are not violated. Hence it follows that only one structure from the given set, the one that best implements the circuit, may be accepted for implementation. Extending the conclusion made to the set of structures from a nonstandard set of blocks, we arrive at the fact that the problem of covering a schematic diagram by a given set of structures is a combinatorial one, consisting in the optimal selection of a set of structures.

Let us consider a formal statement of this covering problem. Suppose there is a finite graph \(L=(x,u,p)\) belonging to the class of Berge graphs, and some finite family of graphs \(S_j=(y,v)\). It is also known that \(x \gg y_j,\; j=1,2,\ldots,N\). It is required to find such a covering of the graph \(L\), i.e., a set of subsets \(S_j\) isomorphic to the corresponding subgraphs of the graph \(L\), under which any vertex \(x_i \in X\) may belong to only one of the subsets \(S_j\), and this set must also be such that it includes as many vertices of the graph \(L\) as possible. Introduce the intersection matrix \(\|a_{ij}\|\), in whose columns are placed the vertices of the graph \(L\), and in whose rows are the numbers of the graphs from \(S_j\), where \(a_{ij}=1\) if the \(i\)-th vertex belongs to the \(j\)-th subset. Then this covering problem, in terms of discrete programming, is a weighted covering problem maximizing the linear form:

\[ z(x)=\sum_{j=1}^{m} b_j x_j \tag{1} \]

under the conditions

\[ \sum_{j=1}^{m} a_{ij}x_j \leqslant 1,\quad i=\overline{1,n}, \tag{2} \]

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

where

\[ b_j \text{ is the cardinality of the } j\text{-th structure,} \]

\[ a_{ij} = \begin{cases} 1, & \text{if the } i\text{-th vertex is assigned to the } j\text{-th subset,}\\ 0, & \text{otherwise.} \end{cases} \]

The specific nature of this problem is such that only those vertices whose topology of functional connections is identical to the graph of the \(j\)-th subset may be assigned to the \(j\)-th subset. Obviously, more than one such collection may be assigned to some \(j\)-th subset; among them there may be collections that intersect with collections of elements assigned to other subsets of the family \(S_j\), as well as nonintersecting ones. In this connection, the intersection matrix \(\lVert a_{ij} \rVert\) must be such that in each row the sum of the values \(a_{ij}\) is equal to the cardinality of the corresponding \(j\)-th subset, and at the same time \(a_{ij}=1\) at the vertices belonging to one collection. The constraint matrix \(\lVert a_{ij} \rVert\) can be obtained in the following way. On the basis of a structural analysis of the circuit, consisting in the fact that an independent covering of the circuit by each structure from the family \(S_j\) is performed with the covered elements recorded, a matrix \(\lVert r_{ij} \rVert\) is constructed, whose columns correspond to the numbers of the circuit elements, and whose rows correspond to the numbers of the structures \(S_j\), where

\[ r_{ij} = \begin{cases} 1, & \text{if the } i\text{-th vertex was covered by the } j\text{-th structure;}\\ 0, & \text{otherwise.} \end{cases} \]

The sum of the elements of the \(i\)-th row can be calculated from the expression:
\[ \sum_j x_{ij} b_j, \]
where \(b_j\) is the cardinality of the \(j\)-th structure, and \(x_{ij}\) is the number of \(i\)-th collections of circuit elements covered by the \(j\)-th structure. Moreover, after covering the circuit by the \(j\)-th structure, the former is restored completely. The structural-analysis algorithm was developed in [3].

The obtained matrix \(\lVert r_{ij} \rVert\) can easily be transformed into the matrix \(\lVert a_{ij} \rVert\) by splitting each row into a number of rows equal to the number of collections covered by the corresponding \(j\)-th structure. In doing so, the following two conditions must be satisfied:

1. Each newly obtained row must contain only one collection \(x_{ij}\). 2. The element-by-element sum of these rows must be equal to the original row. The dimensionality of the matrix \(\lVert a_{ij} \rVert\) can be reduced by deleting zero columns. Using the results of [5], this problem can be solved by slightly modifying the simplex method.

REFERENCES

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

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

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, 1970.

4. L. Ya. Leifman, L. G. Petrova. Some algorithms for the analysis of directed graphs. In: Computing Systems. Siberian Branch, USSR Academy of Sciences, issue 11, 1964.

5. V. A. Trubin. On solving the choice problem. In: Mathematical Methods in Economics, issue 3, Kiev, 1968.