PROCEEDINGS
OF THE TOMSK ORDER OF THE OCTOBER REVOLUTION AND ORDER OF THE
RED BANNER OF LABOR POLYTECHNIC
INSTITUTE named after S. M. KIROV

Vol. 269 1976

ORGANIZATION OF INFORMATION ARRAYS IN ACS

V. Z. YAMPOLSKY, I. L. CHUDINOV

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

Any control process may be characterized as a system of purposeful actions, the principal components of which are the planning of certain operations and control over their execution. Both the planning of operations and control over them are usually accompanied by the collection, transmission, accumulation, and processing of arrays of information. The more complex the control system, the stronger the informational links among its elements, and the greater the volume of information that must be processed in order to make a decision.

It is known that the use of electronic computers makes it possible to store large arrays of information in compact form and to process them at high speed. However, an irrational organization of the process of collecting, storing, and processing information may nullify the capabilities of a computer. Of particularly great importance is the optimal organization of information arrays in an automated control system (ACS). For most ACS tasks, logical processing of information arrays is characteristic; it reduces to selecting the necessary data from an array, performing the simplest operations on them, recording the resulting information in new arrays, and outputting information from the computer.

The restructuring of arrays or, as it is usually called, the processing of arrays, has a large and often predominant influence on the expenditure of machine time and, consequently, on the cost of ACS operation.

Academician V. M. Glushkov [1] defined the information system as the core of an automated control system and formulated the principal system-engineering task of ACS design as the task of optimally forming information arrays, rationally processing them, and using them comprehensively. The effectiveness of information organization is largely determined by the choice of such a structure for an information array as permits information to be stored in the machine memory in such a form that these data occupy a minimum of space in the storage device and at the same time can be processed in the least possible time. These two contradictory conditions force one to find a compromise solution in the choice of an information-retrieval language. In [2] a comparative analysis is given of types of information-retrieval languages using such qualitative characteristics as semantic power, ambiguity, compactness, and cost. However, the absence of a quantitative basis for the analysis does not permit the imple—

make it possible to make a strictly justified choice of the structure of a specific information array.

Another important problem in the organization of information in an ACS is the problem of data distribution (formation of arrays). In order to economize on computer memory, it is advantageous to have a single information array for the system, and to form arrays for specific tasks by program means. On the other hand, the presence of many arrays describing individual objects from different aspects leads to a reduction in the time required for searching and processing the arrays. Moreover, the time of search and processing, as well as the reliability of the technical equipment of storage devices, may require the duplication of certain information arrays to the detriment of economy in computer memory and the time for introducing changes into such arrays. Consequently, the problem of forming arrays is an optimization one, and in the terms of mathematical programming it can be posed in accordance with the following objective function: to minimize the total processing time of arrays subject to constraints on the parameters of the computer’s storage devices (capacity, reliability, speed, cost, etc.) and of the arrays (capacity, frequency of access, sorting time, etc.).

Among the works devoted to this problem, one should note [1, 3, 4, 5]. In [1] a methodology is given for determining the necessary number of duplicates. The time of waiting for the result when an array is accessed, and the cost of executing the access, are adopted as evaluation criteria. Functional dependences are derived for the values of the indicated criteria on the number of duplicates of arrays and their ordering; from these dependences the values of the optimal number of duplicates \(n_c\) and \(n_T\) are determined, where \(n_c\) determines the minimum value of operating cost, and \(n_T\) the minimum waiting time for the result. The most expedient number of duplicates \(n_0\) is chosen from the condition \(n_c < n_0 < n_T\). Evidently, this method can be improved if both local criteria—operating cost and waiting time for the result—are in one way or another reduced to some generalized criterion. An attempt to resolve the contradiction between the prevailing extreme points of view:

a) a single array for all tasks,

and

b) individual arrays for each task, is given in [3, 4]. It is proposed to achieve this by combining some arrays that have common attributes into one array, on the condition that the time for processing the combined array is less than the total processing time of its component arrays over the entire complex of tasks. It should be noted that if the number of arrays having common attributes is large, and the common attributes among different combinations of arrays differ in composition, then determining the optimal variant for combining arrays will require the use of combinatorial methods, for example, the branch-and-bound method.

Another direction in the development of methods for forming information arrays is the approach proposed in [5]. Here the problem is considered of forming a primary set of information arrays \(G_{\mathrm{pr}}\), which makes it possible to obtain the secondary set of \(G\)-type arrays required for solving tasks in minimum time; moreover, the primary set is held in memory with a sequential sampling scheme, and the capacity of this memory is limited in the sense that the secondary set does not fit in memory. The solution of the problem is reduced to the problem of “coloring the vertices of a graph.”

The question of forming information arrays for an automated control system was touched on above. But the performance of the computer of an ACS depends to a significant degree on the placement of information arrays in the system memory. The set of information carriers included among the technical means of an ACS usually contains various types of storage devices (SDs) with different speed, capacity, reliability, cost, etc. In turn, information arrays also have different characteristics: frequency of use, size, type of ordering, relation to tasks, etc.; moreover, some of these can be calculated only with the aid of probabilities (for example, the probability of access).

An effective organization of information placement must ensure a minimum of time spent working with external storage devices and a minimum cost of operating all storage devices of the system, taking into account the characteristics of the information arrays and information carriers. Thus, in [6] the time of access to information arrays during operation of a program complex over a fixed time interval is minimized, where access time is a function of the speed of storage devices and the frequency of use of the arrays. The problem is reduced to the successive solution of one-dimensional “knapsack problems” (separately for each SD). A graphical method is presented for obtaining an approximate solution of the problem, in which first the storage device with higher speed is filled with arrays having a higher probability (frequency) of access and a smaller size. Let us note that, when minimizing the access time to arrays, it is also useful to take into account the time required to process arrays, which depends on the type of SD, and the constraint on the required time for obtaining results for the entire complex of tasks. In addition, it is desirable to solve the problem for all SDs in the complex.

No less important from the standpoint of the efficiency of the computing process is the problem of optimal placement of information arrays within memory of a single type: distribution of arrays among SDs of one type [7, 8] and placement of arrays on an individual carrier [9–15]. In the published works, as a rule, the problem consists in finding such an order for placing arrays on magnetic tape that the mathematical expectation of the time of access to an arbitrary array is minimal, under various operating modes of the reading device. The following modes are considered: with preliminary return of the tape to the initial state (most often the center of the tape) [10, 12, 15], without return to the initial state [9, 13], and a mixed mode. In [11] questions are considered concerning the construction of a criterion that determines the expediency of using one mode or another. It should be noted that most algorithms give an approximate solution. The basic idea of these algorithms consists in ordering the arrays by the probability of access to the arrays \((P_i)\), or by the ratio of the access probability to the length of the array \((P_i/L_i)\), where \(i\) is the current index of the array. The general obstacle that must be overcome here is the catastrophic growth in the number of variants as the number of arrays increases. It appears fruitful to use, for these purposes, algorithms based on the ideas of the “branch and bound” method.

The works cited above considered problems of placing information arrays with known access probabilities. An analogous problem arises if the order of access to the arrays is known, but accesses to the same arrays are made repeatedly.

Thus, the organization of information arrays entails determining the content of the information, distributing data among arrays, choosing the structure of the arrays, and placing the arrays in the machine’s memory. The choice of a solution for each of these issues is influenced by many interrelated factors: the physical characteristics of storage devices, the characteristics of the arrays, the logic by which the arrays are used, the reliability of the system, etc. It should be noted that at the stage of developing a new system it is not always possible to have all the necessary data for most of the characteristics. All this compels one to seek new approaches and improve existing ones for solving problems of organizing arrays of information in an automated control system.

REFERENCES

1. V. M. Glushkov, V. P. Gladun, L. S. Lozinskii, S. B. Pogrebinskii. Processing Information Arrays in Automated Control Systems, Kiev, “Naukova Dumka,” 1970.

2. Ch. Meadow. Analysis of Information-Retrieval Systems. Moscow, “Mir,” 1970.

3. L. S. Lozinskii. On the question of forming information arrays in an automated control system. “Kibernetika,” Kiev, 1970, No. 6.

4. L. S. Lozinskii. Formation of information arrays. In: “1st Scientific and Technical Conference of the Special Design Bureau for Mathematical Machines and Systems.” Kiev, 1970.

5. V. B. Sokolov. Some methods for reducing the time required to solve problems in an automated control system. “All-Union Conference on Problems of Control. Moscow, 1971.” Abstracts of reports, part I. “Nauka,” 1971.

6. V. A. Niesov. Optimal distribution of machine memory of various performance levels. In: “Mathematical Support and Effective Organization of the Computing Process.” Computing Center of the Academy of Sciences of the Ukrainian SSR, issue 2, 1968.

7. V. N. Burkov, V. B. Sokolov. Optimal placement of information arrays in memory on magnetic tapes for the case of bidirectional search. “Avtomatika i Telemekhanika,” Moscow, 1969, No. 4.

8. B. B. Timofeev, V. A. Litvinov. On the question of organizing the placement of information in memory on magnetic tapes. “Kibernetika,” Kiev, 1969, No. 4.

9. V. A. Niesov. Problems of rational arrangement of information arrays on magnetic tape. “Kibernetika,” 1968, No. 4.

10. V. A. Litvinov. An algorithm for optimizing the placement of information arrays on magnetic tape. “Kibernetika,” Kiev, 1970, No. 4.

11. V. A. Litvinov. On the choice of search modes for information arrays on magnetic tape. “Kibernetika,” Kiev, 1970, No. 5.

12. V. A. Litvinov. On one mode of searching for information on magnetic tape. In: “Technical Means of Data-Processing Systems,” issue 3. Computing Center of the Academy of Sciences of the Ukrainian SSR, Kiev, 1969.

13. V. A. Litvinov, Yu. S. Filimonov. Some questions of the optimal placement of information on magnetic tapes. In: “Technical Means of Data-Processing Systems,” Computing Center of the Academy of Sciences of the Ukrainian SSR, Kiev, 1967.

14. V. N. Burkov, M. I. Rubinshtein, V. B. Sokolov. Some problems of optimal placement of information in large-capacity memory. “Avtomatika i Telemekhanika,” Moscow, 1969, No. 9.

15. S. S. Veniaminov, G. A. Sokolov. Optimal placement of information on magnetic tape with preliminary positioning of the tape. “Kibernetika,” Kiev, 1971, No. 1.