INCREASING THE EFFICIENCY OF MODELING CENTERS V. V. Ivanov, V. S. Mikhalevich, and I. V. Sergienko
UDC 517.598
In this article we present an unformalized description of a modeling center (MC), introduce a dynamic model which can be used to discuss the main mathematical formulations of MC tasks and the questions of increasing MC efficiency, present some qualitative results relating to improved functional efficiency of MC software, hardware, and orgware, and discuss some issues of managing the development of these factors. I. DESCRIPTION AND EXAMPLES OF MC A modeling center is a large specialized unit which generally constitutes part of the computing center (CC) in an organization or actually encompasses the entire CC. Therefore, functional description of a MC is entirely analogous to the description of a computational process in a CC. The MC input is a stream of problems P w h i c h a r e p r o c e s s e d i n t o a s t r e a m o f solution results R by MC software S, hardware H, and orgware O. The main functional feature of a MC is that the results R often include new elements of S, H, and O, so that the MC can evolve and improve itself. Thus, while solving some problem for one of the "customers," the MC usually develops improved algorithms and programs and possibly program packages (PP) which (~ogether with the solution results) a r e d e l i v e r e d to the customer and at the same time copied and retained by the MC as new elements of S. The need to order and organize the operation of a large number of programs inevitably leads to the development of the system component of S. In the same way, original specimens of cybernetic technology developed for the first time at the MC are not only delivered to the "customer," but also retained by the MC as new hardware components in H. A large MC also has facilities for computer-aided development of progressively better cybernetic machines and devices, which are incorporated as new components of H. Similarly, the results of automatic teaching systems for programmers, other specialists on the MC staff constitute new elements of O.
technicians, and
Thus, a MC is an evolving system which partially processes the incoming resources into useful products for the "customer" and partially utilizes them for its further evolution and improvement. Therefore the description of MC should naturally consist of at least two essentially different (in functional terms) subsystems: subsystem A of MC improvement, which also improves itself and thus acts as a source for the evolution of the MC as a whole; subsystem B in charge of producing MC "output." In each of the subsystems, a functional unit is one standard (average) position. In reality, there are special positions for the production of the elements of S, H, and O. The notion of position in a MC is not specifically related with time and place in space, but rather with a specific MC function that the position performs (compare [I]). In many cases, a position localized in time and in space by virtue of its association with a particular professional at a first glance has no relation whatsoever to the particular MC. However, if the individual spends a large part of his working time solving MC problems, then it is this part which should naturally be identified with the corresponding part of the position in the MC. Summing these parts over the entire host enterprise with which the MC is affiliated (and possibly over several enterprises), we may obtain a fairly large number of MC positions. One standard (average) position comprises the collection of jobs and functions [2] that one professional of average qualifications (with average pay) is capable of completing in one working day. The process of software development and operation in a MC focusing on a certain subject area can be divided into the following stages: Translated from Kibernetika, No. 5, pp. 22-32, September-October, submitted May 16, 1982.
556
0011-4235/82/1805-0556507.50
1982.
Original article
9 1983 Plenum Publishing Corporation
I) system analysis of the subject area; 2) construction or updating of models for subject area problems; 3) modeling,
or project development;
4) analysis and processing of the results; 5) optimization of model parameters. Note that in the process of modeling we repeatedly pass from one stage to another, cyclically repeating some specific subsequences. The realization of these stages in specific MC projects involves diverse and multifaceted issues. In particular, when investigating the synthesis and use of mathematical models borrowed from the area of operations research or computer-aided design, it is advisable to represent the corresponding components of S in PP form. The development of modern PP for the solution of optimization problems has suggested a new trend, whereby the elements of S are created so as to solve whole classes of problems, and not just individual problems. It is noteworthy that such PP also include formalization of subject area problems and development of combination computing schemes sequentially using several optimization algorithms. For example, the package DISO [3] developed at the Computing Center of the Academy of Sciences of the USSR and the package VEKTOR-2 [4] developed at the Institute of Cybernetics, Academy of Sciences of the Ukrainian SSR allow a wide scope for updating of the mathematical models of problems from appropriate classes, fixing the current state of the computational process in order to analyze the results and make on-the-spot decisions. There are also options for revising the mathematical models of problems and the solution algorithms. On-line intervention into the computational process requires development and implementation of a sufficiently powerful interactive mode, which constitutes a significant feature of these PP. The package DISO is designed to solve a number of classes of optimization problems with continuous variables. It includes a wide range of optimization algorithms, varying in their efficiency and complexity, which solve problems of the following classes: -- unconstrained minimization; - -
nonlinear programming;
-- optimal control. The package VEKTOR-2 is designed to solve combinatorial optimization problems, a large proportion of which focus on optimal design of digital hardware, so that the package can be directly used to develop new elements for H. The service utilities of the package are capable of analyzing the solution results and correcting the software if necessary. In this way the package gradually improves its structure and organization. The package DISPRO [5], also developed at the Institute of Cybernetics, Academy of Sciences of the Ukrainian SSR, includes a wide selection of algorithms for the solution of general and special integer programming problems. The program and language facilities of the package make it possible to update the numerical parameters of the mathematical models, to refine the variable parameters of the optimization algorithms, and also to create and modify sets of data used in the solution of large-dimensionality problems. Activity modeling problems associated with optimization of transportation networks may be solved with the PTP package [6]. It is intended to solve transportation problems, and the corresponding mathematical models and solution methods may be applied to practical problems of freight shipments and plant location, production synchronization, inventory management, etc. The system TsENTRAS [7] is designed for integral solution of problems of organization and scheduling of the computational process in a computing center with a multiprogramming computer. In addition to solving problems of optimal organization of the computational process on the multiprogramming computer, the system also stores and classifies information about the various stages of the computational process, derives performance measures for the multiprogramming computer and for the computing center as a whole, and also solves a number of other problems. Problems in certain subject areas often may be modeled by a MC in the form of specialized program complexes combining two software systems, one acting as a modeling system proper and the other as a system that processes snd analyzes the modeling results. 557
This is actually the approach adopted in 1973 at tlie institute of Cybernetkcs to develop the SLENG-USOD software modeling complex [8] intended for modeling systems with discrete events, statistical processing, and analysis of the modeling resu]Ls. This complex was created by combining two autonomously developed software systems using different source languages: the SLENG system for discrete process modeling [9] and the system USOD [I0]. The complex is intended for processing and analysis of diverse data by methods of probability theory and statistics. To this end, the system SLENG was incorporated in the system USOD as one of the users, and an additional mode was introduced in SLENG -- the cooperative mode; the module for automatic generation of alternatives, the memory management mechanism, and the initiation facility in the system USOD were all updated. The cooperative mode in USOD is implemented by a specialized subsystem which in the event of cooperation with a generated data processing program connects an unconditional transfer operator, which ensures feedback to the calling program. The system for the processing of nuclear experimental data [11] developed at the United Institute of Nuclear Studies under the direction ofN. N. Govorun consists of three components. The first component, operating on-line, receives information from the measuring device, checks it, compresses the data and writes them on magnetic tapes. The second group of programs takes care of the final processing of the experimental data. The specific functions of these programs include checking the correct operation of the measuring device during the experiment, filtering of events, and reconstitution of the spatial map of the events. This group also includes programs for identification and statistical processing of the data. The third group includes parameter generating programs for the measuring device and the modeling programs. A special multilevel software-hardware system BARS []2] was developed for on-line acquisition, transmission, checking, and editing of messages about high-speed technical and production processes. Because of its high efficiency and realiability, the system is currently used in different areas. A computer-aided system ISSLEDOVATEL' [13] is being developed at the Institute of C y b e r netics, Academy of Sciences of the Ukrainian SSR and at the Institute's independent design office of the International Mathematical Union. Its objective is to investigate the operation of program packages and computer-aided data processing systems, by collecting and processing statistical information about various operating aspects of a PP. It includes criteria and algorithms for assessing the performance of the available PP and DPS and is capable of generating recommendations concerning possible improvement of their efficiency. This system also may be used to investigate the performance of separate computer modules and computing system components. It has been implemented on the ES computer and is currently in the stage of acceptance tests. 2. DYNAMIC MC MODELS The known results of the t h e o r y of p o s i t i o n modeling [1, ] 4 - ] 8 ] can be a p p l i e d to d e v e l o p the following generalized mathematical model of a Me: t
m (t) ----- ~ a ('~, t) y ('0 m ('0 d%
adt; c (t) =
i p ('~' t) [1 -- y ('~)1 m ('0 d'~, a~(t)
t
p (t) =
t
v
m
+
ado
[1--V a~(t)
(I)
a~(t)
[ (t) = m (t) k,~ (t) + k~ (t) c (t), G~ (t) = ,i" y(T)m(~)d~, adto)
a~(t )
G2 (t) = i [ 1 - - y ('0] m ('0 dT, 0 ~ y (~) ~ 1, a~(to)
a;(t),
a;(t)>/O,
a~(t),
a~(t)~t,
t ~ t o.
Here m(t) is the rate of creation of new positions in the MC at time t; y(T)m(~) is the fraction of m(T) functioning in subsystem A (the MC improvement subsystem); ~(T, t) is the performance measure of a position in A: this is the number of new positions created in unit time
558
at the moment t per one position in A at the moment T; at(t) is the time limit for liquidating obsolete positions inA; c(t) is the rate of creation of new generalized product by theMC, delivered to outside"customers"; [l--y(~)]m(T) is the fraction ofm(r) functioning i n s u b s y s t e m B (theMC output subsystem); B(T, t) is the performance measure of a p o s i t i o n i n B : the number of units of generalized product created in unit time at the moment t per one position in B at the moment ~; ~2(t) is the time limit for liquidating obsolete positions in B; P(t) is the total number of active positions in the MC at time t; f(t) is the consumption of the external resource at the moment t, received by the MC from the outside; km(t), kc(t) are the costs (in units of f) per one unit of m(t), c(t), respectively; al(to), a2(to) are time moments such that all positions created in A and B, respectively, prior to these moments are obsolete for all t to; G1(t), G2(t) are the obsolescence factors of A and B, respectively, at time t, and G(t) = G1(t) + G2(t) is the total number of obsolete positions in the MC; to is the initial moment of MC modeling; in the time interval [min(a1(to), a2(to)), to] all the model functions are assumed given [~l(to), ~2(to) are also given]. Thus, (I) is a system of nonlinear integrofunctional equalities and inequalities of given MC characteristics with known history.
in terms
If ~, @, y, P, f are given, the system of the first four (nonlinear) equations in (I) c a n b e solved under very broad assumptions to find the unknowns m, c, al, a2. If a I = ~2, the first three equations suffice. Frequently, al, a2 can be found from the historical values of GI, G2 and y, m. Then m is found from the first equation in (1), which is treated as a linear Volterra equation, and c is obtained by substituting the results in the second equation. The allocation y is naturally obtained by solving various optimization problems. Examples of two basic optimization problems are given in [I]. The first corresponds to maximizing the output of useful generalized product in a given period [to, T]:
I i (y) ----
i
r (t) dt ------
to
#[i
~ ('~, t) [ 1 - - y ( ~ )
to
m ('0 d'~
a t)
]
dt = m a x Y
(2)
subject to all the relationships of model (I) (e, B, P, f are given), and the second corresponds to minimizing labor cost in the period [to, T]:
I,@) = ~ P(t)at=_. to
[1--y(~)]m(~d~
y(~)m(~)d~ -1to L a,(r
dt = r a i n
(3)
a2(t)
for given ~, S, c, f. The first problem was investigated in detail in [14, 16] (the case al = a2 = a). It was shown that for sufficiently small T -- to, max Il is attained for the smallest possible y, and for sufficiently large T -- to it is attained for essentially larger y at the beginning of the given period and for the smallest possible y at the end of the period. Moreover, it was shown that the asymptotically highest rate of growth c(t) for t § ~ is attained for y(t) § I (but not too fast). The meaning of these results becomes clear if we note that the decisive factor is the rapid growth of m(T), so that in the expression [I -y(T)]m(~) the increase of m(~) more than offsets the decrease of [I -- y(T)]. Some results of computer calculations of the boundary between "small" and "large" T -- to are given in [14]. In application to MC, assuming the fraction of positions in subsystem A to be proportional to the fraction of machine time used for "internal" MC development, we find that for a sufficiently large period [to, T] a maximal number of "outside" problems can be solved only if the machine time allotted to the solution of "internal" problems is increased substantially. We should stress that the model (1) leads not only to definite qualitative conclusions, but also yields corresponding quantitative results. Let us now consider
in more detsil multiproduct MC models.
Let
~ = ~;m~,m~: m3", m (t) = ml (t) + m 2 (t)+ m3 (t),
(4)
where m I is the rate of creation of new positions in subsystem I of the MC, whose external p r o d u c t s a r e position elements in the form of software; m2, m 3 are analogous rates for the production in subsystems 2 and 3 of hardware and orgware, respectively. Then (I) is replaced w~th
559
3
t
i ~ % ('~, t) w,.~ (~)~,~ (r d~:,
m~ (0 =: ~
.1'=1 aQ,(t'r 3
c, (t) = ~
~' [hJ ('~, t) z~j ('~) mj (-c) a-~,
1=1 bH(t) 3
r )
(y~j + z& = 1, i =1
I YU('0 % ('~)d~ + a zi.j ('0 mj (.c)a.~
P~ q)
i = ! l aii(t)
bii(t)
fj = ~im~ + k~ic~, 0 ~ ~tu, z~.~ 1, a u,b u < t ,
i,]=i',3,
t>~t o,
where ~ i j , a i j , Yijmj, Bij, b i j , z i j , mj, Pi, f i , kmi, kcs are analogous to a, a : , Ym, 13, a2, (1 - - y)m, P, f, km, kc, r e s p e c t i v e l y . In t h i s way, we can introduce more d e t a i l e d n-product models (with n > 6, see [15]), focusing on production "sectors" of different types of MC software, hardware, and orgware. If a random factor ~ is introduced in ~ij, Bij, we obtain corresponding stochastic models. Note that a different Indeed, let
interpretation of the parts of m gives a different type of models.
' ~ = ('m:, 'm2; 'm3), m (0 = 'm: + 'm2 + 'ms,
(4 ')
where 'm: is the rate of creation of new MC positions generating software elements; 'm2, 'm3 the corresponding rates for hardware and orgware, respectively. Then, instead of (5) we have "k
Z
t
$
I%(
'oZ
k = l 'a~k
,~ ~
0~< 'y~<~ 1,
k~-I "bik(l) 'k
t
'P,(t)=~{
5'
j~l
1=I
3
l
3
/
2 'yk'(T')'mj(':)+d'~+ S ~ [1-'y~('O'm'(~)d'c
k..~-I ,'aik(t) ]~I
'fi = k'mi'mi + kcici,
(5')
3
"bik(t) ]~1
i = I, 3, t >/ to, 'k is any integer,
'k ~> I; '~ik, 'Bik have the same
meaning as ~, B in the channels 3
3
Y, 'v~ (~)'m~ ('0 -- 'm~ (t), respectively.
We can rewrite
]~ [1-'wa ('~) ]'mA'O -- ~ (0
(5') in matrix-vector form as follows: t
'm (t) = ~'(t) =
~ ~ ('~, t)'~ ('0'~ (t) dr,
o ~< '~ ~< 1,
i '~ (-~,t) [1 -- 'v= (%'m- ('~) J-~, '=a, 'V
@(t)
(6) t_
560
t
Here, a single bar is used for vectors and a double bar for matrices; denotes a column matrix.
the asterisk
(*)
3. ON MC EFFICIENCY By Sec. 2, the main measures of MC efficiency are functions of the type ~ and B that characterize the productivity of positions in subsystems A and B, respectively. These functions usually increase in the variable T and decrease in the variable t. Therefore, the MC development efficiency measures are naturally provided by indexes of the form [17] ~h'~
=
"-OT- '
Nma
=
"
Ol
'
N1,~=-~,,~2,~=
Ot
"
(7)
The higher nl,~, ~z,B, the faster increases the productivity of new positions at the moment for fixed t; the lower ~2,a, ~2,B, the slower is the wear (decrease of productivity) at the moment t of the positions created at the moment ~. Let us consider three techniques for assessing the functions of the type e, B using as an example the functions ~, B of the model (I), since all the other functions can be similarly assessed. The first technique may be based on experimental determination of ~, B, proceding from their definition and using the recorded operating history of the MC to extrapolate the values of ~, B to some future period. To implement this technique, let us first consider the determination of ~, B in tabular form as ~ik = ~(ti, tk) and Bik = B(ti, tk) for discrete time moments ti, tk; I < i ~ k ~ N; ti ~ tk. First it is easier to elucidate the construction of ~ik. Let r i be the total number of positions in subsystem B at the moment t i and ~ik the number of positions (from ri) which in unit time, starting with the moment tk, generate Cik units of external generalized MC product. Then N
c~h
V
~ih=
%
(8)
Here ~ik is the sum of the results of the separate positions, which essentially increases the measurement accuracy when there a r e a l a r g e number of positions. In order to construct ~ik, we have to sharpen the notion of a new position in subsystem A. Recall that each position is characterized by a collection of functions and the corresponding resources (software, hardware, orgware). If any one of the functions and (or) resource components is changed (in practice quite substantially), the corresponding position will be regarded as new. An active position in A alters the position components in A and in B, thus resulting in new values of ~ and B. Note that hiring a new person or firing a veteran may lead, respectively, to renewal of all the existing positions and creation of one new position or to renewal of all the remaining positions; this is so because inclusion or exclusion of one person may affect the functioning of all the other persons in a team. Thus, let n i be the total number of positions in subsystem A at time ti and ~ik the n u m ber of positions (from n i) which create in unit time, starting with the moment tk, mik new positions. Then N
ml ~i~h
E
(9)
k=i
To assess ~, B as functions of ~, we can naturally apply various interpolation and approximation techniques for tabular functions. In this connection, note the new results of [19] connected with optimal-accuracy reconstruction of a class of tabular functions satisfying the Lipschitz condition and some other classes. The second technique may be based on the ordinary methods of model identification using the specific features of the models of type (I), (5), (6). We seek ~, B in the form ~~, O =
~
a, mI
( 1 O)
561
from the condition "
rt
(f~
I :.. ~ trh/* ~1'~/ are given systems of basis functions, mi(t) , yi(t) a r e g i v e n on t h e i n t e r v a l [ t oII, Clearly, problem (11) to] , ~i(t) i s g i v e n on t h e i n t e r v a l i;~0 - . t 0 .j ( a i.( t ) ~. t : .. ' t o r t .., z~,p ' ' , i = 1, R. reduces to solving a system of linear algebraic equations for {ak}. H o w e v e r , t h e r e a r e many essential difficulties associated with the choice of basis systems of functions and the sampling of mi, Yi, ~i. Often q%(z) is conveniently taken as a function of the form 6(v)(r -Xs), where ~ is the Dirac delta, and v is not greater than the number of derivatives that exist for Yimi .
To reduce the number of parameters n, we can apply a third technique based on nonlinear approximation of ~, ~ using their structure and their meaning. Thus, in some cases ~ is naturally sought in the form [16]
(% t) = ~o
m (~)
eC:_c:,
( 1 2)
y (u) m (u) du a(~
where only three parameters are to be found, a ~ cl, c2. Here a tional to the number of functioning positions i n s u b s y s t e m A, c l a due to the introduction o f new t e c h n o l o g i e s , c2 r e p r e s e n t s the previously created position components. More g e n e r a l s t r u c t u r e s system aggregation and disaggregation methods [17].
is taken inversely proporcharacterizes the growth of d e c r e a s e due t o t h e w e a r o f o f a, B c a n b e o b t a i n e d b y
Having determined the functions a , B, we c a n i n v e s t i g a t e Me e f f i c i e n c y . What a r e t h e main determining factors o f MC e f f i c i e n c y ? Glushkov [20] investigated the notions of effective computer speed and the cost of effective speed and in the process identified some of the determining factors. He showed, in particular, that the computer productivity is affected by input--output devices, the computer memory, the computer instruction set, computer checking and preventive facilities, etc. Following [20], we supplement ~, B by the prices of ~, B:
EA (t, ~) Pc, ('~, t) ---- c~ (-~, t) y ('~) m ('~j' ' P~ ('q t) =
(13)
g B (t, "~) "~t ~
where EA, EB are the costs at the moment t of creating and operating a position in A and B, created at the moment ~. The characteristics and models introduced above can be easily used to assess the main technicoeconomic indexes (TEI) of MC operation. Let us calculate, for example, the payback period of a newly created, an updated, or a reorganized MC. All the characteristics of the old MC will be subscripted I, and those of the new MC will be subscripted 2. For a newly created MC, all the economic indexes of the old MC (costs, revenues, etc.) are naturally set equal to zero. In application to the optimization problem I considered above, let I~,z and I~,2 be the attainable best (maximal) outputs of external MC product in the period T -- to. Denoting by Pc the unit price of this external product, we calculate the incremental income from operating the new MC compared with the old MC: AG~ =
The c o r r e s p o n d i n g
cost
AW,=
i[
increment
is
given
l~.~pc,2--1~.lPc.1.
(14)
by
I EA':(t'~)d~- i 'eA''(t'~)-t- i ' EB'z(t'~)d~--
J EB,~(t,~)dg] dt+hw,,
(15)
where 5wi is the incremental cost of solving optimization problems of type I on a computer. Hence the incremental profit is
562
7"
t
to a~,2(t)
+EB,~(~,~)]dzdt--
~,~p~,~
~[Ea,~(I,'O+Ea a (l,'O]d'~dl 9
(16)
t~ a~,l(l )
Therefore,
the
sought
paybaek
period
T~ -- t0
is
obtained
as
the
root
of
the
equation
A6~ ----AW~.
( 1 7)
Suppose that in application to optimization problem. .~ [ I / ( T - to)]I~,s~ and [ I / ( T - to)] I2,2" are the attainable best (minimal) values of the mean labor cost in period T - to and let pp be the money value of the (mean) output of one person in national accounts. Then the incremental income is given by
12a - - 1.9,2
( 18 )
PP'
hG==- T--t o
the incremental cost is obtained similarly, and the sought payback period T2 -- to is obtained as the root of the equation
AO~ -- AW~,
( 1 9)
where T i
t
t
/
zXW~= i'~ f [Ea,2(t,'O+eB,2(t,~)]d~-- ~" [EA,~(t,~)+Eaa@,~)ld~jdt+Aw~, ,o o;.#
(20)
4.,,'
Aw2 is the cost increment due to the solution of optimization problems of type 2 on a computer, a*(t) denote everywhere the values of a(t) corresponding to the best value I*. Note that Eq. (13) may be used to calculate the payback period of the cost of position improvement. Indeed, let ~i, Bz and ~2, B2 be the respective productivities of old and new positions. Then, by analogy with the preceding, we have
AOa = /l,2p=, 2 - - ll,lPml,
AG 4 = . I~,IT---- 12,~to PP'
(21)
and
' to t aa,2(t )
}
a3,1(t)
(22)
A~,, = ~"f'} I [P~#, + po,13duo ('0,,,,('0d,~io a4,2(t)
[' [p,~,m + pf,#,] I:~ - v,, ('0 m," ('0 d*/I dr, a471 (f)
whence the sought payback periods T3 and T4 (with respect to the first and the second functional, respectively) are obtained as the roots of the equations AG~ = AW,,,
AC~, = A'[17~.
(23)
The payback period thus essentially depends on the particular objective functional used. 4. INCREASING THE EFFICIENCY OF MC SOFTWARE, HARDWARE, AND 0RGWARE Let us first consider the general aspects of MC operating efficiency using the model (I), and then the efficiency of the main MC resources using the model (4)-(6). The output of the MC improvement subsystem A is directly linked with increasing the efficiency of positions in A and B, and it may therefore be identified (up to dimensions) with ~(:r, T) and F~(~, t). This means that for a two-product model ..u
!, ~
=
/e.-~y, ~§~, "r) -T- .,j~i~~, T~ ,
=
(?
-- I~c ('r) c) ~y (z) {'~) .
,
'
(24)
563
where ka, k[~ are coefficients numerically equal to i whose dimension is suci~ that the dimension of the products k~c~ and k6!~ is the same as the dimeasion of m. Given ::,:(', ~) sad :;(~, ~), the sought characteristics a('E, t) and !3(~E, t) can be expressed by
r (~, t) = cr (~:, ~) r (~, t), [~(,~, t) :: i5 f~, ~) s (~, O, where r(z, t), s(z, t)(r(~, T) = s(~, z) = I) characterize resources. The simplest natural model of wear is clearly r ('~, t) = e - c r ( t - ~ ) ,
where Cr, Ca are sought constants
Using (24)-(26), we rewrite model
the rate of wear of the position
s (% t) = e -c~(t-~) ,
to be determined
( 25)
(26)
experimentally.
(I) in the form t
=
i o~(~)(cz (~) + [3 (,)) e-O~-~)dz,
(t) + ~ (t) = y(t)
ado t
~ ~ (T) (~ (T) + ~ (,)) e-Cs"--*) ~ (T) dT,
c (t) =
a=(t) t
P (t) =
t
{ (c~ (~) + ~ (~)) d~ + at(t) f (t)
=
(27)
~" (~ (~) + i~ (~)) (1 -- V ('~)) d~, V (~) a~(Jl)
(~z (0 + 1~ (t)) ~,,, (t) + c (t) ko (t), v (t)
t > to.
Here, for the sake of simplicity, kaa(t, t) and kfiB(t , t) are denoted by ~(t) and B(t) and the equations are written in nondimensional form retaining the previous notation. Let f, c, km, kc, P, y, Cr, Cs be given and it is required to find a, B, al, a 2. We have four equations and four unknowns. In the general case, (27) is a highly complex nonlinear system of equations with a given history on [a(t0), to]. We will show how to solve this system in the simple case when f, c, kc, km, P, y are constants. Rewrite (27) in the form 1 =
Io:ec,~e-~/d*,
y
al t
~ ff (f --k,,,ckc) eCs~eCst (1 -- g) dT,
c=
k~P
t -- V. (t -- a~),
V (f -- ck~) = (t -- ad +
~+[~=
V
f'ck~
whence c ~ = ~ (t) - - ~z (ao d / ~ ' - t ~ a ; , g ~mC 9C s
f-- ck~ = ([~ (t) -- ~ (a2) e~(a'-~
1 --g g
0 = g(1 - - a I) + (1 - - g) (1 --a~), tem
and assuming
g
-
-
o~,
that on past history
cz (ao
=
s0
(aO ~ O,
ff (a.2) = ~o = const g= O,
f -- ck~ kr n
564
Y - - Cr,
cc f l ~ k , ) (1 -- e-*,( t-to) ~] ([ --ck~) (1 - - g) ~3o 'J '
Q~--t ~ CZ
1 - - g (a~ - - t) a~ - - t
=
(28)
Pk~ ck~) g '
Y
([ --
max (at (t), a~ (t)) ~ to, to ~ t ~ t~. From
(28)
increases
sume
it follows,
in particular,
that as y increases
from
f--cko
to
I
f_ck~
, B
from 0 to (f -- ckc)/k m -- c r.
If f, c, kc, km, B, y, Cr, Cs are given and ~, P, al, ~2 are the unknowns, that f, c, kc, kin, B, y are constants (~0 = ~, B0 = B) and easily find
k~
Y -- 13'
,(
t - - a 2 = -~--ln
t
--
at
in 1 -- yc* c--r-~'\-' ] ,
CCskm 13 ([ -- c k~) (1 -- y)
1
we again as-
(29)
)--r ' l--g
In
k~
From
(29)
it follows
1 --
~)
that P has a m i n i m u m
1-c--r . If b >/ 1, then P attains s
I -- 13 (f _
ck~) (I -- y)')
"
in y on the interval [[c~s l--b],j if b---- 13~--ck~)ccskm <
its m i n i m u m
for y = 0 (cr = 0).
This m i n i m u m is important for assessing the least number of positions in the MC required to perform the functions that ensure the desired value of c for given values of f, kc, km, B, cr, Cs 9 From
Suppose that al, a2, kin, Y, er, Cs, (27), we have for to ~< t ( tl
f, P are also given and we have
to find ~, B, c, k c.
max (at (t), a, (t)) ~-~to np~I to ~ t ~ tl, P' (t) = -- [So (ai) + 13o(ai)] a~ -- [s o (a,) + 13o(ai)] whence we easily find ~ + B (here the subscript the given history). Given ~ + B, we find
1 -- 9o (a~) a~ + [s (t) + 13 (t)] 1--~(t)
yo (a,)
( t -y- - ) - '
0 identifies
the known
function
values
from
gs (t) = ='s(t)(t)++13'(t)(t) fi + c~ + 0%(a0s[s~ (a0+~+(t)13~(ai)] e~#=,(Ot)a;(t), 13(t)= Is(t) +13(t)] --s(t). Substituting
all t h e s e
results
in the secono
k~ (t)
equation
= f (t)
y (t) c (t)
"
determined the solution on the interval [to, tl], we use the same method to find functions on the interval [tl, ti], max(at(t), ai(t)) ~< tl for tl ~< t ~< ti, etc.
We can similarly
construct
obtain
[s(t)+13(t)lk~(t)
c (t) Having sought
in (27), we find c(t) and finally
many o t h e r MC modeling
problems
the
based 9 on (27).
Let us analyze some of the major factors which determine the values of km(t) and kc(t). Recall that these are the unit costs of m(t) and c(t), respectively. From (13) we have
1 L~ (t) = y
9 \ v (t) m (t) +
B(t,t) I1 -- v (t)]m (t)]"
(3 0)
565
The smaller k m and kc, the higher is the eperating <~ff[ci{~cy of ti~(~ ~IC. the main !:~ct{~s that determine k m and k c are the following. 1.
The amount of unnecessary work done, including unnecessary duplication of necessary work. There are usually many objective and subjective reasons for unnecessary activities. Among the objective reasons we can apparently list the inevitable increase of "friction" among the professionals as their number in a given team increases. Among subjective reasons we should mention poorly organized planning, coordination, and control of activities.
2.
The attitude of the professionals to their responsibilities and ability to correctly manage their work and time. According to non-Soviet estimates, this factor may cause the costs to vary by as much as 40%.
3.
Timely introduction of the latest tools and facilities for performing various functions. Delay in the introduction of more productive facilities may cause the costs to vary by several orders of magnitude in certain time intervals.
4.
Cost and value of the facilities that increase the position operating efficiency.
5.
Consistency of the various activities with the individual qualifications of the personnel and with the available resources (both in quality and in quantity). These factors may also cause the costs to fluctuate by several orders of magnitude.
Let us consider the possibility of increasing the efficiency of software, hardware, and orgware resources using the model (4)-(6). Setting by analogy with (24)-(27)
y~JmJ~)
=
~J
aij (x, t) = ~ ~) e *#~-t), we obtain an indeterminate system for ~ij, Bij. bij(t) (see [ 1 ] ) .
(t) + ~j (t), ~ (% t) = ~ (~) e ~i(*•
(3 1
In (31) we set aij(t) = Bij(t), aij(t) =
In this case I
cqj (t) = [~j (t) ---- -~- Ylj (t) mj (t)
(32)
and (5) takes the form 3
2,,,
t
= Z
!
i=1
c )e
aij(t)
3
t
j=l
bl](t)
t
3
P~i (t) = ~ Iv. ('~) + z~j (~)l mj ('0 d~, Pj = ~ P . , a~j(t)
(33
i~l
3
X (Y:J + zi~) = 1,
fi ---- t~mim~ + l~eicl,
i=l
i,]
=
1,3, t > t o .
For known Pij, fixing Yij, zij or finding them from the solution of some optimization problem, we obtain a determinate system in (33) for mi and aij. Solving this system, we find the sought ci and fj. Then from (31), (32) we obtain aij and Bij. The system in (33) is a nonlinear Volterra system with history, and the main results obtained in [14-16] therefore can be extended to this case also. In the particular case when Yij, zij and the historical values of mj are independent of time, we easily find (for t E [to, tl]i
2tn, (t) =
566
yL
9~ i= i q
m 2 ( t o - - a,~ (t)) -{- rn ~. (T) d~ i, , I
lo
,
P i j (t) -~ (to - - a~j (t)) + J/i/-}- Zij mJ~
m~ ('~) d-co ., fo
(34)
Eliminating ~ij and differentiating the first equality in (34), we obtain a system of Ricatti equations for m i [21]. It is relevant to investigate this system as for general systems (33) and for (4)-(6). Let us consider some qualitative aspects of increasing the efficiency of various MC resources. The problem of increasing software efficiency can be stated as minimizing the execution time for a given class of problems under certain restrictions on solution accuracy, memory requirements, and other characteristics of the problems, the algorithms, and the computers (the available reserves and results in this formulation are given, e.g., in [22]). We will stress two trends in software optimization which are particularly relevant in the light of modern computer developments. The first trend attempts to reduce the execution time with the aid of parallel solution algorithms on multiprocessor computers. It is generally assumed that the parallelism is e f fective if the execution time on a q-processor machine is cut roughly by a factor of q. Numerous results relating to parallel algorithms are now available (see, e.g., [23]). Important new results were obtained with parallel versions of the sequential analysis of alternatives, with space-stretching generalized gradient descent algorithms [24], and also with numerical methods for the solution of various modeling problems for evolving systems representable by models of the form (I). The second trend attempts to minimize the execution time by manipulating the basic computer instruction set, as well as the algorithms. In a general theoretical framework, lower bounds over all algorithms and instruction sets for all the possible computer-solvable problems were derived in [25], where the corresponding optimal algorithms and instruction sets were also given. Some results with optimization of algorithms and basic instruction sets for a number of important classes Of problems in computational mathematics are given in [26]. Another promising trend is associated with the construction of efficient adaptive algorithms minimizing the execution time for each particular problem through adaptation to the specific input data. At this stage, however, the theory of adaptive algorithms is still in an embryonic stage. Glushkov's algebra of algorithms is of great importance for automatic adaptation of computer algorithms (see, e.g., [27]). The solution of many difficult classes of applied problems substantially benefits from efficient realization of the algorithm with the aid of software and hardware facilities embodied in various MC operating modes: interactive mode, program debugging on a computer, input data and program modification, output of results in prespecified form, accumulation of past experience, etc. An example of the modern level of realization of these and many other operating modes with the aid of application program packages is provided by [4]. Efficient organization of computations is considered in [22, 28]. The most significant feature of the modern level of development of computer technology is the high degree of integration and the low cost of the basic components. This leads to a proliferation of computers of various classes and uses, and also increases the amount of computational requirements. In practice, however, we often run into very difficult problems which cannot be solved unless the available computer resources are utilized in an optimal way. An example of a high-throughput computer of the future capable of solving difficult problems is provided by the macropipelined computing system [22, 29]. The macropipeline dynamically adjusts its structure depending on the particular class of problems being solved; it allows parallel processing of both linear and cyclic program sections and includes a communication network for parallel fast local swaps, a collection of fast problem-oriented processors, etc. The cost and the development time for all the jobs are an order of magnitude lower than in conventional systems, thanks to the extensive accumulated experience (in particular, various intelligent computers), parallel development of theory, hardware, and software (both system and problem-oriented), etc. The effectiveness of team work in computer science and applications is essentially dependent on advances in the field of operations research -- a theory of the scientific approach to decision analysis and decision making. Each step in human activity involves decision making. The fo]lowin g topics in optima] decision theory are particularly relevant [30]. ].
Development of efficient (in terms of total time requirements) numerical methods for the solution of optimization problems with many variables and with nonsmooth objective functions and constraints. 567
2.
Development of easily implementable solutio~ method~ f<>r discrete programming i)robiems with a large number of variables.
3.
Development of numerical methods of optimization unde~ incomplete and inaccurate initial data and under risk and uncertainty.
4.
Development of procedures for goal-directed
5.
Creation of interactive optimization systems.
simulation.
5. MANAGING MC DEVELOPMENT In the light of Glushkov's dynamic models of evolving systems and our discussion of MC tasks and structure, we can outline the following requirements for managing future MC growth. I.
Development of an inquiry procedure in order to elucidate the main functions of MC positions and to derive performance measures for these functions. Various functions should be traced all the way to the final results of MC operations, i.e., products of the type m(t) and c(t). Although the performance measures of separate activities along the entire chain should be averaged according to the model, the analysis of the individual activities will provide useful material for identifying bottlenecks that reduce overall system performance.
2.
Increasing the role of MC improvement subsystems, including subsystem improvement by focusing on the internal functions of the subsystems. We should stress again that successful development of a MC depends on improving those positions which improve the positions that perform the main external MC functions as viewed by the outside "customer."
3.
Ensuring timely updating of system software and hardware with the object of increasing system efficiency.
4.
Development and implementation of measures to reduce the cost of internal and external MC products.
5.
Further development of MC models on the basis of a new class of Glushkov's dynamic models, extending the theoretical research to computer program design and acceptance, with special focus on the solution of a number of optimization problems and MC development forecasting problems.
In conclusion note that one of the decisive factors for successful MC development is correct treatment of the human factor or orgware. This requires a careful plan for economic and social advancement of the entire team. LITERATURE CITED I. 2.
3.
4.
V . M . Glushkov, "On a class of dynamic macroeconomic models," Upr. Sist. Mash., No. 2, 3-6 (1977). V . E . Khmel'ko and V. I. Paniotto, "A social-information procedure for balanced improvement of job structure and labor force development of an industrial enterprise," Kiev (1981) (Manuscript filed with INION Akad. Nauk SSSR, 13.5.80.N1235). E . N . Veselov, Yu. G. Evtushenko, and V. P. Mazurik, "Conceptual possibilities of the interactive optimization system DISO," in: Problems of Computing Technology, collected papers [in Russian], Mezhdunar. Tsentr Nauchn. Tekh. Inf., Moscow (1981), pp. 110-122. L . F . Gulyanitskii, I. V. Sergienko, and A. N. Khodzinskii, "An interactive program package VEKTOR-2," Preprint Inst. Kibern. Akad. Nauk Ukr. SSR, No. 81-63 [in Russian], Kiev
(1981). 5.
V . S . Mikhalevich, I. V. Sergienko, T. T. Lebedeva, et al., "An application program package DISPRO for the solution of discrete programming problems," Kibernetika, No. 3, 117-
6.
V. S. Mikhalevich, A. A. Bakaev, Yu. M. Ermol'ev, et al., "A program package for the solution of transportation problems, Solvable problems, possibilities, and source language," Preprint Inst. Kibern. Akad. Nauk Ukr. SSR, No. 81-40 [in Russian], Kiev (1981). L . P . Bogdanene and I. V. Sergienko, "An automated multiprogramming data processing system," Upr. Sist. Mash., No. 5, 43-46 (1977). I . N . Parasyuk and M. A. Sakhnyuk, "The software complex SLENG-USOD," Upr. Sist. Mash., No. 3, 40-42 (1974).
137 (1981).
7. 8.
568
9. 10. 11.
12. 13. ]4. 15.
16. 17.
18.
19. 20. 21. 22.
23. 24. 25. 26.
27. 28. 29. 30.
V. M. Glushkov, L. A. Kalinichenko, and T. P. Mar'yanovich, SLENG -- A Programming System for Discrete System Modeling [in Russian], Inst. Kibern. Akad. Nauk Ukr. SSR, Kiev (1969). I. V. Sergienko, I. N. Parasyuk, and N. I. Tukalevskaya, Automated Data Processing Systems ]in Russian], Naukova Dumka, Kiev (1976). N. N. Govorun, I. M. Ivanchenko, and L. S. Nefed'eva, "Software for nuclear experimentation systems using real-time computers," in: ]st Soviet Symp. on Software for RealTime Computers [in Russian], Kiev (1972), pp. 74-78. V. M. Glushkov, A. A. Morozov, and V. I. Skurikhin, "The system BARS. Objectives, structure, Characteristics," Upr. Sist. Mash., No. 2, 3-7 (1979). I. V. Sergienko and V. V. Skopetskii, "Investigation of data processing systems and problems of increasing their efficiency," Kibernetika, No. 6, 41-46 (1977). V. M. Glushkov and V. V. Ivanov, "Modeling the optimization of job distribution between group A and B industries," Kibernetika, No. 6, 117-131 (1977). V. M. Glushkov, V. V. Ivanov, and V. M. Yanenko, "On a new class of dynamical models and its application in biology, I-3," Kibernetika, No. 4, 131-139 (1979); No. 4, 109117 (1980); No. 5, 113-127 (1981). V. M. Glushkov, V. V. Ivanov, and Yu. P. Yatsenko, "Analytical investigation of a class of dynamical models, I, 2," Kibernetika, No. 2, 1-12 (1980); No. 3, 114-119 (]982). V. M. Glushkov, V. S. Mikhalevich, V. V. Ivanov, and V. M. Yanenko, "Modeling the main mechanisms of system growth management," in: 2nd Soviet Conf. on Problems of System Growth Management (KURS-II), abstracts of papers [in Russian], Tallin, April 26-28, 1982 (1982), pp. 13-19. M. D. Babich, V. V. Ivanov, and I. V. Sergienko, "On some problems of developing special software for computing center networks," Preprint Inst. Kibern. Akad. Nauk Ukr. SSR, No. 80-54 [in Russian], Kiev (1980). Optimization of Computations, I-III [in Russian], RFAP, Kiev (1977). V. M. Glushkov, "Two universal criteria of computer efficiency," Dokl. Akad. Nauk Ukr. RSR, No. 4, 477-481 (1960). E. Kamke, A Handbook of Ordinary Differential Equations [Russian translation], Nauka, Moscow (1965). V. M. Glushkov, V. V. Ivanov, V. S. Mikhalevich, I. V. Sergienko, and A. A. Stognii, "Reserves of computation optimization," Preprint Inst. Kibern. Akad. Nauk Ukr. SSR, No. 77-76 [in Russian], Kiev (1977). D. H. Enslow (ed.), Multiprocessors and Parallel Processing, Wiley (1974). V. S. Mikhalevich, I. V. Sergienko, and N. Z. Shor, "Investigation of solution methods of optimization problems and their applications," Kibernetika, No. 4, 89-113 (1981). Yu. V. Golunkov, "Algorithmic completeness and complexity of microprograms," Kibernetika, No. 3, 1-15 (1977). V . V . Ivanov, Yu. L. Ivas'kiv, and V. S. Kharam, "Optimization of computations by combined software and hardware means," in: Optimization of Computations and Numerical Analysis [in Russian], Inst. Kibern. Akad. Nauk Ukr. SSR, Kiev (1980), pp. 3-10. V. M. Glushkov, G. E. Tseitlin, and E. L. Yushchenko, Algebras, Languages, Programming [in Russian], Naukova Dumka, Kiev (1978). A. F. Tutov, "An administrative distributed system of a multiuser computing center," Upr. Sist. Mash., No. 4, 45-47 (1978). V. M. Glushkov, Yu. V. Kapitonova, A. A. Letichevskii, and S. P. Gorlach, "Macropipelined computations of functions on data structures," Kibernetika, No. 4, ]3-21 (1981). V. S. Mikhalevich and Yu. M. Ermol'ev, "Some topics in operations research theory," Preprint Inst. Kibern. Akad. Nauk Ukr. SSR, No. 76-60 [in Russian], Kiev (1976).
569