ON ONE METHOD FOR ORGANIZING THE OPERATION OF A SOFTWARE SYSTEM

Yu. N. Efimov, Yu. G. Yurenkov

(Presented by the scientific seminar of the UVL TPI)

Programs that organize the solution of problems on an electronic digital computer are usually designed on the assumption that the algorithm for solving the problem is represented in the form of a linear sequence of programs. In solving many problems (planning, control, etc.), it is more convenient to represent the system of programs in the form of a graph of nonlinear structure. This article considers one of the possible ways of constructing a program that organizes the operation of systems of programs of the above type.

We shall assume that the set of programs for a problem is a directed graph without cycles (a program graph), where each vertex of the graph is a program graph or a separate program, and the direction of an arc of the graph indicates the precedence of the operation of the vertices; if a vertex is a program graph (subgraph), then in turn its vertices are subgraphs or separate programs. Hence one may introduce the following hierarchy among the set of program and numerical arrays of the aggregate of problems solved on an electronic digital computer: arrays common to all problems are arrays of rank 0; arrays common to one problem are arrays of rank 1; arrays common to a part of the problems implemented by a subgraph (a vertex of the general program graph) are arrays of rank 2, etc.

Before beginning its operation, each problem must pass to the program organizing the computation (the dispatcher program) the complete set of data on its program and numerical arrays (the information array of the problem) and the assignment for the operation of the system of programs of the problem. The assignment must list the output vertices of the program graph of the problem that must be executed.

Let us introduce notation for the objects considered in the article and symbols for the relations between them:

\(k\) — rank number \((0 \leq k \leq q)\);

\(m_k\) — number of a program graph \((1 \leq m_k \leq n_k)\);

\(l\) — number of a numerical array \((1 \leq l \leq p)\),

where \(p\) is the limiting value of the number of a numerical array,

\(q\) is the limiting value of the rank number,

\(n_k\) is the limiting value of the number of a program of a graph of rank \(k\). The symbols of relations between objects are established as follows: for objects \(A\) and \(B\),

“\(A(B)\)” means that \(B \in A\);

“\(A, B\)” means that \(A\) and \(B\) are objects of the same rank;

“\(A:B\)” means that an arc of the graph is directed from vertex \(A\) to vertex \(B\).

Thus, the notation “$A(B:C,D,E:C)$” means that from vertex $B$ of graph $A$ there emanate two arcs directed to vertices $C$ and $D$, and from vertex $E$ of the same graph there emanates an arc directed to vertex $C$. Below, the upper index “$A^{(j)}$” means that, among all objects of type $A$, one with number $j$ has been selected.

With these notations, any program and numerical array is uniquely determined by specifying the sequence

\[ m_0\bigl(m_1(m_2(\ldots(m_q(l))\ldots))\bigr). \tag{1} \]

If $l=0$, then (1) is the identifier of a program; if $l\ne 0$, then (1) is the identifier of a numerical array needed for the operation of the program $m_0(m_1(\ldots(m_q)\ldots))$. If all $m_k$ in (1), beginning with some $k>0$, are equal to 0, then for $l\ne 0$ (1) specifies a numerical array common to a subgraph of rank $(k-1)$.

The information array of a task consists of two parts: the program graph and the list of numerical arrays of the task. The program graph can be defined as the union of the identifiers of all programs of the task, with an indication of their connections. Similarly, the list of numerical arrays is the union of the identifiers of all numerical arrays of the given graph.

With the adopted notation, a subgraph of rank $k$ can be written in the form of the following sequence of symbols:

\[ m^{(i)}_k\bigl(m^{(j_1)}_{k+1}:m^{(j_2)}_{k+1},\,m^{(j_3)}_{k+1},\ldots,\,m^{(j)}_{k\ldots}\bigr). \tag{2} \]

The program graph of a task is specified by the collection of expressions (2) with the total number of terms

\[ n = n_1 + n_2 + \cdots + n_{q-1}. \tag{3} \]

The list of numerical arrays needed for the operation of the subgraph $m^{(i)}_k$, with an indication of their applicability at the vertices of the subgraph, can be written in the form

\[ m^{(i)}_k(l_1,l_2,\ldots,l_{i_1}),\; m^{(f_1)}_{k+1}(l_1,\ldots l_1),\ldots) \tag{4} \]

The list of numerical arrays of the entire task is completely specified by the collection of expressions (4) with the total number of terms (3).

Above, a task specification was defined as an enumeration of some number of output vertices of the program graph of the task, i.e., the specification is a list of identifiers of the system’s output programs. This list is more conveniently represented in a form analogous to (4),

\[ m_1\bigl(m^{(i_1)}_2(m^{(j_1)}_3(m^{(\ldots)}_4,\ldots),\,m^{(j_2)}_3(\ldots),\ldots),\ldots\bigr). \tag{5} \]

The purpose of the dispatcher program is as follows: after receiving a work assignment from the task, to determine, from the program graph, the sequence of programs necessary for carrying out the task, and to execute them.

A dispatcher program of this type has been developed for the “Ural-14D” digital computer as the control program of the automated production planning and control system “ASUP-Tomsk.” “ASUP-Tomsk” is used for planning and controlling the production of several enterprises. The set of programs of “ASUP-Tomsk” is a fairly complex system, which is most conveniently represented by a nonlinear graph. This system of programs is used for various purposes of planning and control; moreover, in each particular case not all programs included in the system are needed for the work. The dispatcher program is designed for a number of array ranks $k=3$. In application to the “ASUP-Tomsk” program system, the concepts introduced above of a program graph and a subgraph mean the following: the program graph of a task is the entire system of programs for the complete computation of the tasks being solv-

… “ASUP-Tomsk” systems for a single enterprise; a subgraph is a part of the system that solves a particular problem within the framework of the entire system.

The dispatcher program is intended for the sequential execution of enterprise tasks in planning and production management. Since the operating scheme of the dispatcher program is analogous to other programs of the same type, only a general description of the dispatcher program is given below, indicating the features that distinguish it from analogous programs. The dispatcher program sequentially executes enterprise tasks; moreover, to speed up operation the program provides for 5 parallel streams of computation: solving problems, input of information from punched cards, input of information from punched tape, printing of information on an alphanumeric printing device (ATsPU), and output of information to punched tape.

Program and numerical arrays, both initial and those formed in the course of computation, are stored in a magnetic-tape storage unit (NML) and are called into core memory (NF) only for processing. Data on their location in the NML (NML address) are stored in the control array of the dispatcher program. This array consists of subarrays corresponding to the ranks of the system arrays. The first subarray stores the NML addresses of arrays of rank 1 and of subarrays of the control array with data on arrays of rank 2, etc. The NML addresses in a subarray of the control array are arranged in increasing order of the numbers of the corresponding arrays. The NML address in the control array occupies 48 binary digits and contains the NML block number, the NML mechanism number, the NML zone number, and the number of zones occupied by the given array. The relative addresses in a subarray of the control array are determined by the following formula:

\[ A_0(m)=AH+2m, \tag{6} \]

where \(m\) is the array number,
\(A_0(m)\) is the relative address of the NML address from the beginning of the subarray,
\(AH\) is the relative address of the beginning of the data on arrays of type \(m\).

Information is input into the electronic digital computer at the instruction of the operator, given from the console. The initial arrays input into the electronic digital computer are, as they are entered, copied to the NML, and the data from them are entered into the control array. From these data the NML addresses of arrays formed in the process of solution (NML allocation) are determined. Arrays called from the electronic digital computer are formed by the system programs and written to the NML, after which the program gives an instruction to the dispatcher program to output them to print or to punched tape, while it itself continues operation. Allocation of core memory is carried out as follows: a part of the NF of a definite length (constant for all programs) is assigned to the program, and the programmer, when preparing the program, distributes this part of the NF at his own discretion; before the program begins operation the list of NF arrays is transmitted to the dispatcher program, which, according to the list of program arrays, forms the table of arrays of the electronic digital computer. Moreover, during operation the program may redistribute its part of the NF, of which it informs the dispatcher program, which in turn makes changes in the array table.

The dispatcher program begins operation with the initial input of information. After the information array of the task and the assignment have been entered into the electronic digital computer, the sequence of rank-2 subgraphs corresponding to the assignment is determined from the program graph of the problem (rank 1), and a cycle is constructed over the number of these subgraphs. Within this cycle, for each subgraph, a linear sequence of programs (rank 3) corresponding to the assignment is determined, and these programs are executed for each-

of each subgraph. During the computation, the dispatcher program checks for the presence of the arrays required for the work. If the arrays are absent, the dispatcher program gives the operator a list of the missing arrays and proceeds to a subgraph independent of the one being executed, or to another task. After completing the cycle over the number of subgraphs, the dispatcher program switches to another task.

One year of experience operating the described dispatcher program for the Ural-14D electronic digital computer has shown its fairly high efficiency.