Translation of a Functional Diagram into a Real Design Basis
Abstract Generated abstract
The paper examines computer aided translation of a functional diagram of a computing device into a concrete structural implementation, with attention to covering by structural elements, timing coordination, and load matching. It formulates load matching as an optimization problem on a directed graph representation of the logical circuit, minimizing a linear power consumption criterion under integer load capacity constraints for structural element groups. The proposed procedure uses vertexwise descent for acyclic graphs, dynamic programming for the integer allocation subproblem, and an iterative breaking and closing method for circuits containing loops. The resulting load matching algorithm, including cycle detection and element matching, is reported as implemented on the MIR-1 computer.
Full Text
Translation of a Functional Diagram into a Real Structural Basis
E. F. Zhigalova
(Presented by the scientific and technical seminar of the Department of Automated Control Systems and the Control Laboratory)
The current rates of development of microelectronics and the improvement of the technology of its production largely determine the rates of design of computing devices. An effective means of achieving high quality and substantially reducing design time is the use of computers. Over the last decade in the USSR, many theoretical and practical works have appeared devoted to the design of computing devices with the use of computers. At the same time, the greatest practical results have been obtained in the design of the logical and technical stages. Along with this, positive results have been obtained in the complete automation of design. Here one may refer to the work of the Institute of Cybernetics of the Academy of Sciences of the Ukrainian SSR, as well as of the IBM firm in the USA. One of the advantages of complete design automation is the continuity of design, which helps reduce the time required for preparing the initial information and for its input into and output from the computer. From this point of view, and also taking into account the practical results obtained in the automation of the logical and technical stages of design, the problem of translating a functional diagram into a real structural basis with the use of a computer is of interest; in it one may distinguish a number of questions, including:
a) covering the functional diagram with structural elements;
b) coordination of the elements of the schematic diagram in time;
c) coordination of the elements of the schematic diagram with respect to load.
The translation of a functional diagram into a real structural basis is also of practical interest in the sense that changing the structural basis of the elements does not necessarily entail a change in the functioning algorithm of a given computing device. This makes it possible to implement the designed functional diagram in several structural variants.
For an unambiguous understanding of the subsequent exposition, we shall use the basic definitions given in [2]. Depending on the adopted structural basis of elements, the following cases of implementation of a functional diagram are possible:
1) each logical element can be implemented by one structural unit;
Fig. 1
2) the realization of certain functional nodes by a single structural unit (such as a trigger) is possible;
3) each logic element can be realized by a functionally connected group of structural elements.
In accordance with this, the covering of a functional diagram by modules of the adopted structural basis is reduced to assigning to each logic element or functional node a certain number of corresponding structural units, with subsequent recording of their functional connections; from the theoretical point of view this presents no particular difficulty and is easily implemented on a computer.
The method of realizing the functional diagram, as well as the physical nature of the structural elements, may introduce certain discrepancies in the operating times of individual nodes and elements of the corresponding schematic diagram. For proper operation of the device, it is necessary to construct a real timing diagram that takes these features into account. On the basis of the real timing diagram, delays in the information chains are equalized. To check the correctness of signal propagation through the device, the method of test analysis described by E. I. Gurvich and T. P. Kulikovskaya [2] may be used.
The logic elements of the functional diagram have no limitation on load capacity; therefore, when passing to a real structural basis, mismatches of elements with respect to load are possible, i.e., some structural elements may prove to be overloaded. As a rule, series of structural elements contain elements of several groups differing from one another in load capacity. The table gives the load-capacity table for the various groups of elements of a certain series of structural elements, where \(A, B, \ldots, F\) are groups of elements, and \(a_{11}; a_{12}; a_{21}; a_{mn}\) are the limiting load capacities of one element of groups \(A, B, \ldots, F\).
Let us consider the problem of matching the elements of a schematic diagram by load for a series of structural elements containing two load groups. We shall adopt the following initial assumptions:
- The functional diagram is represented by a Berge graph, whose vertices correspond to logic elements and nodes, and whose arcs correspond to the functional connections between them.
-
The load capacity of the structural elements, as well as the load itself, is expressed in numbers of elements.
-
To each logic element of the functional diagram there is assigned a corresponding structural element (or group of elements) that realizes the given logical operator.
-
The given structural series contains elements of two groups, \(A\) and \(B\). The elements of group \(B\) are more powerful than the elements of group \(A\). Then the following relations hold:
\[
a_{11} > a_{12}.
\]
\[
a_{21} > a_{22}.
\tag{1}
\]
Table
| Type of loaded element | \(A\) | \(A \cup B \cup \cdots \cup F\) | \(B\) | \(\cdots\) | \(F\) |
|---|---|---|---|---|---|
| \(A\) | \(a_{11}\) | \(a_{11}+a_{12}+\cdots+a_{1n}\) | \(a_{12}\) | \(\cdots\) | \(a_{1n}\) |
| \(B\) | \(a_{21}\) | \(a_{21}+a_{22}+\cdots+a_{2n}\) | \(a_{22}\) | \(\cdots\) | \(a_{2n}\) |
| \(\cdots\) | \(\cdots\) | \(\cdots\) | \(\cdots\) | \(\cdots\) | \(\cdots\) |
| \(F\) | \(a_{m1}\) | \(a_{m1}+a_{m2}+\cdots+a_{mn}\) | \(a_{m2}\) | \(\cdots\) | \(a_{mn}\) |
From the relations given it is evident that the number of structural elements in the device depends on the choice of the group of elements when covering the functional diagram, since, depending on the number of elements and also on their group in the load, the loaded logic element or node can be realized by corresponding elements belonging to one group or to two groups. The matching algorithm is based on the simple relation
\[ k \cdot x_i^{A,B} \geq p_j, \tag{2} \]
where
\[ x_i^{A,B} \]
is the number of elements of some group in the \(y_i\)-th vertex;
\(k\) is the corresponding load coefficient;
\(p_j\) is the load, or consumed power, in the \(y_j\)-th vertex, where
\[ y_j \in \Gamma y_i. \]
We shall call optimal such a solution in which, at each vertex, the elements of one group or another, on the one hand, balance the corresponding load, i.e., relation (2) is satisfied, and, on the other hand, themselves represent the minimum load; in other words, they require less power.
Let us consider a certain function of consumed power \(\varphi(x_A; x_B)\), defined on the set of all vertices of the graph \(G=(y,\vec u)\). It is obvious that
\[ \varphi(x_A, x_B)=\sum_{i=1}^{N}\left(\gamma_A \cdot x_i^A+\gamma_B \cdot x_i^B\right), \tag{3} \]
where
\[ i=\overline{1,N} \]
is the set of all vertices,
\(\gamma_A; \gamma_B\) are coefficients of consumed power.
Then the problem of load matching is the problem of minimizing the linear function \(\varphi(x_A, x_B)\) subject to condition (2).
The objective function that minimizes the value of the power consumed by the structural elements is a sufficiently reasonable optimality criterion, one that to a considerable degree determines the number of elements in the real circuit. Let us consider the process of computing this problem. Since the consumed power is determined by the number and group of load elements, relation (2) can be written in the form
\[ k_j x_i^{A,B} \geqslant \sum_{y_j \in \Gamma y_i} \left(x_j^A + x_j^B\right), \tag{4} \]
where \(x_j^A, x_j^B\) are the numbers of elements of groups \(A\) and \(B\) in the load.
Relation (2) shows that the number of elements at the \(y_i\)-th vertex is determined by the magnitude of the consumed power at the vertices \(y_j \in \Gamma y_i\), or by the number of elements of the corresponding group, and is completely independent of the decision made at the vertex \(y_k \in \Gamma^{-1} y_i\). This makes it possible to make the decision at each vertex separately. Then the process of solving the problem will be as follows. Having specified the load or consumed power at vertices \(\{y_i\} \in Y_N\) such that \(\Gamma Y_N = \varnothing\), we obtain that relation (4) for the vertices \(Y_{N-1} \in \Gamma^{-1}Y_N\) on the right will have a fully definite numerical value. Solving equations (3) and (4) jointly, we obtain a solution at the vertices \(Y_{N-1}\), which determines the load at the vertices \(Y_{N-2} \in \Gamma Y_{N-1}\) or \(Y_{N-2} \in \Gamma^2 Y_N\). These arguments may also be continued for the vertices \(Y_0 \in \Gamma^{-n}Y_N\). In other words, the decision-making process at each vertex of the graph \(G=(Y,\vec U)\) is a sequential descent along a tree whose orientation is opposite to the orientation of the given graph. In Fig. 2 the graph \(G=(Y,\vec U)\) is shown, and the descent tree is indicated by a dashed line.
Fig. 2
Load-Matching Algorithm
The left-hand side of relation (4) contains the load-capacity coefficient \(k\), whose value depends both on the group of load elements and on the group of loaded elements (Table 1). Let us represent the variable \(x_i^{A,B}\) as the sum of variables \(Z_1^{A,B}\) and \(Z_2^{A,B}\), which compensate, respectively, the power consumed by elements of groups \(A\) and \(B\) in the load. Then relation (4) for the energy balance at the vertex \(y_i=\Gamma^{-1}y_j\) can be represented in the form of the system of relations \((4^*)\):
\[ \left\{ \begin{aligned} a_{11} Z_1^A + a_{21} Z_1^B &\geqslant x_j^A,\\ a_{12} Z_2^A + a_{22} Z_2^B &\geqslant x_j^B, \end{aligned} \right. \tag{4*} \]
where
\[ Z_1^A+Z_2^A+Z_1^B+Z_2^B=x_i^{A,B}. \]
Thus, we have an allocation problem with two types of resources. Determining the optimal policy for multidimensional allocation processes is a rather complicated problem. Therefore, using the specifics of the present problem, we shall reduce it to a problem with one type of resources. Let us write the energy-balance equation for one element of groups \(A\) and \(B\) in accordance with the relation (1) given above:
\[ \begin{cases} a_{11}P_A=a_{12}P_B,\\ a_{21}P_A=a_{22}P_B, \end{cases} \tag{5} \tag{6} \]
where \(P_A\) is the power consumed by one element of group \(A\),
\(P_B\) is the power consumed by one element of group \(B\).
Multiplying both sides of equation (5) by the quantity \(\dfrac{1}{a_{12}P_A}\), and equation (6) by
\[ \frac{1}{a_{22}P_A}, \]
we obtain the relations:
\[ \begin{cases} \dfrac{a_{11}}{a_{12}}=\dfrac{P_B}{P_A},\\[6pt] \dfrac{a_{21}}{a_{22}}=\dfrac{P_B}{P_A}, \end{cases} \tag{7} \tag{8} \]
whence it follows that
\[ \frac{P_B}{P_A}=\frac{a_{11}}{a_{12}}=\frac{a_{21}}{a_{22}}=j,\quad \text{i.e.} \]
\[ P_B=jP_A. \tag{9} \]
Since power here is measured in conventional units, i.e., in numbers of elements, let us rewrite relation (7) in the corresponding notation:
\[ x_B=jx_A. \tag{10} \]
Relation (8) makes it possible to express the consumed power of each element of group \(B\) in the load through the consumed power of one element of group \(A\). Now the given problem can be written as: minimize the linear form
\[ \varphi(x_i^A,x_i^B)=x_i^A+jx_i^B \tag{11} \]
under the condition
\[ \begin{cases} a_{11}x_i^A+a_{21}x_i^B\geq P_j,\\ x_i^{A,B}=0,1,2,\ldots \end{cases} \tag{12} \]
If condition (12) were reduced simply to the constraint \(x_i^{A,B}\geq 0\), the problem would be quite simple, and its solution could be determined as follows. Consider the ratios \(\dfrac{P_j}{a_{11}}\) and \(\dfrac{P_i}{a_{21}}\), and let \(b\) be the index for which this ratio assumes the minimum value. Then we shall select only elements of type \(b\); in this case we obtain the consumed power of the elements
\[ \varphi_b=\frac{P_j}{a_b}\cdot\gamma_b. \]
It is obvious that this solution will not always satisfy condition (12). Rounding the solution of the problem to the nearest integer may lead to a solution far from optimal. Consider a problem that includes two groups of elements:
\[ \begin{gathered} P_j=18 \quad \text{— load}\\ a_1=4 \quad \gamma_1=1\\ a_2=5 \quad \gamma_2=1.25. \end{gathered} \]
If it were not for the integrality condition, then to compensate this power we would choose \(18:5=3.6\) elements with consumed power \(18:5\cdot 1.25=4.5\). In order for condition (12) to be satisfied, one may round \(3.6\) down to 3 and take 1 element of the first group to compensate the excess power. This solution gives a consumed power of \(4.75\). However, the true optimum is easily determined by simple enumeration; it is equal to \(4.5\) and is attained by choosing two elements of the first group and two elements of the second group. To solve this problem one may use an algorithm based on the idea of dynamic programming.
Let us write the recurrence relation for computing the function \(f_N(P_j)=\min L_N(x)\) at each vertex of the graph:
\[ f_N(P_j)=\min_{\{x_N\}}\{x_N\gamma_N+f_{N-1}(P_j-x_N\cdot a_N)\}, \tag{13} \]
where \(x_N\) takes the values \(0,1,2,\ldots,\left[\dfrac{P}{a_N}\right]\).
The computational procedure proposed by R. Bellman [3], which gives an optimal integer solution, can also be applied to the computation of formula (13).
In considering the problem of matching the elements of the functional diagram by load, we proceeded from a number of assumptions, including the assumption that the logical circuit contains no loops. Let us make the opposite assumption: the logical circuit contains loops, and let us examine how this problem will now be solved. A logical circuit may contain simple loops, i.e., each arc belonging to a loop belongs to only one loop, as well as complex ones, i.e., in a loop it is possible to distinguish at least one arc belonging to two loops. First let us consider the first, simpler case. Figure 2,a shows part of the graph of a logical circuit containing a loop \(Q\). It should be stated at once that the algorithm for detecting cycles will not be considered here. Let the vertices \(A,B,C\) belong to the loop \(Q\). Write the balance equation for these vertices:
\[ \left\{ \begin{aligned} a_{11}x_C^A+a_{21}x_C^B &\geq P_i^*+(x_A^1+\gamma x_A^B)\\ a_{11}x_B^A+a_{21}x_B^B &\geq P_k^*+(x_C^1+\gamma x_C^B)\\ a_{11}x_A^A+a_{21}x_A^B &\geq P_l^*+(x_B^1+\gamma x_B^B), \end{aligned} \right. \tag{14} \]
where \(P_i^*, P_k^*, P_l^*\) are the reduced loads of the vertices \(A,B,C\) at the vertices \(y_i\in \Gamma y_C\), \(y_k\in \Gamma y_B\), \(y_l\in \Gamma y_A\), under the condition \(y_i\notin Q\), \(y_k\in Q\), \(y_l\in Q\). The decision-making process in the loop \(Q\) cannot be represented by a descent tree, which follows from relation (), valid for any vertex \(y_i\in Q\): \(\Gamma^n y_i=y_i\) (), where \(n\) is the order of the mapping, equal to the length of the loop.
The solution in the circuit can be found iteratively. Let us “break” the circuit \(Q\) at any point (it is more expedient to do this at the point where the vertex \(y_q \in Q\) has only a mapping into the set \(\{y\} \subset Q\)) and seek the solution at the vertices of the circuit without taking this connection into account. After the solution has been found, we “close” the point of the break and check whether the balance equation is satisfied at the vertex \(y_q\). If so, the solution is complete; if not, an additional load equal to the number of elements in the vertex \(y_j = \Gamma y_q\), obtained as a result of the first iteration, is added to the vertex \(y_q\), and the next iteration is carried out. Obviously, this process is convergent, and the solution will be found in a finite number of steps. To accelerate the convergence of this process, one may, already at the first iteration, add to the vertex \(y_q\) a load of one element of the group of minimum power, which does not contradict common sense, since this is the minimum of the possible loads.
In the case where the logical network contains not a simple circuit, as shown in Fig. 2, b, one should first exclude the arc belonging to both circuits. After this it is again necessary to check whether the remaining arcs form a circuit. If so, one should exclude one more arc from the circuit. Then the first iteration for determining the solution is carried out analogously to the way this was done in the case of a simple circuit, with a subsequent check of the energy-balance condition when the circuit is closed.
Thus, the algorithm for matching the elements of the schematic diagram by load includes: a) an algorithm for finding circuits in a graph; b) an algorithm for matching elements by load. The load-matching algorithm was implemented on the “MIR-1” computer.
REFERENCES
-
A. A. Zykov. Theory of Finite Graphs. Novosibirsk, “Nauka,” 1969.
-
Application of Computers to the Design of Digital Devices. Collection of articles edited by M. Matyukhin, “Sovetskoe radio,” 1968.
-
R. Bellman, S. Dreyfus. Applied Problems of Dynamic Programming. “Nauka,” 1965.
-
Ya. I. Fet. Some algorithms for designing digital computers. Computing Systems, Issue 18, Novosibirsk, 1965.