THE UNIVERSITY OF MICHIGAN Technical Report 14 A SYSTEM FOR THE SOLUTION OF SIMPLE STOCHASTIC NETWORKS Keki B. Irani Victor L. Wallace CONCOMP: Research in Conversational Use of Computers F. H. Westervelt, Project Director ORA Project 07449 supported by: ADVANCED RESEARCH PROJECTS AGENCY DEPARTMENT OF DEFENSE WASHINGTON9 D. C. CONTRACT NO. DA-49-083 OSA- 3 050 ARPA ORDER NO. 716 administered through: OFFICE OF RESEARCH ADMINISTRATION ANN ARBOR September 1969

Abstract This report details the data and program structures for a conversational programming system which translates commands describing a Markovian queueing network into a matrix of transition intensities, and which provides equilibrium distributions and related solutions of the network according to requested specificationso iii

Table of Contents Page List of Figures vi List of Tables viii Preface ix 1. Introduction 1 2o The Basic Compilation and Calculation Philsophy 5 3. The Generation Process and Network Syntax 11 4. Primitive Elements and Their Meaning 29 5. The Compilation Process 43 6. The State and Transition-Matrix Structures 91 7' The Solution for Equilibrium Probabilities 107 8. Specification and Calculation of Results 113 9. Epilogue 125 References 131 Appendix A 133 V

List of Figures Page 2.1 Supervisor Flow Diagram 9 3. 1 A Diagram 14 3. 2 A Fragment of a Completed Network Structure 19 3o 3 Network Structure Diagram Notation 20 3. 4 Network Structure Fragment Showing Symbol Table and Unconnected Port Set R 24 4o 1 Fragment of Network Structure Showing Literal Type Definition 36 4o 2 Format of r-line of Element 38 4. 3 The Set Structure for n-Tuples 41 4. 4 The n-Tuple Set Head Word 41 5. 1 Illustrating the Compilation Procedure 45 5o 2 The Compiler Flow Diagram 46 5o 3 Flow Diagram for "Collect Associates" Routine 54 5, 4 Fragment of Working Structure upon Entry to "Collect Associates" Routine 55 5o 5 Status of Working Structure at 3 in Figure 5o 2 56 5. 6 Result of Collection Operation on Figure 5. 3 57 5. 7 Flow Diagram of Absorption of Connections 68 5o 8 Fragment of Working Network Structure at Beginning of Connection Absorption 70 5o 9 Fragment of Working Network Structure, Prepa- 71 tory to Generating Spontaneous Events vii

List of Figures (Continued) Page 5. 10 Prototype Flow Diagram for Spontaneous Event Routines 73 5.11 Fragment of Working Network Structure upon Exit from Spontaneous Event Routine 75 5. 12 Flow Diagram: Event Consolidation 78 5.13 Flow Diagram: Event Set Consolidation 79 5. 14 A Network Fragment Containing a Random Branch 81 5o 15 Communication Among States 83 5o 16 State Set Trimmer Flow Diagram 85 5o 17 "Test and Trim Events" Flow Diagram 86 5.18 A More Efficient "Test and Trim" Program 87 5. 19 Typical Result of Absorption of all Connections 88 6.1 Illustrating a Matrix Structure 96 6. 2 The Structure for the Matrix in Eqo (6. 9) 98 60 3 The State Area Structure (Fragment) 102 6. 4 Illustrating "Splitting" of bk for Constancy of g 103 6. 5 The Matrix-Event Generator 104 7. 1 Flow Diagram for State Probability Solver 112 A1 Free Block Formats 137 A2 Flow Chart for GET Function 138 A3 Flow Chart for FREE Subroutine 139 viii

List of Tables Page 3o 1 Connection Characteristics and Symbols for Standard Objects 15 3o 2 Generation Routines —Summary 22 3 3 Service Programs for Generation-Summary 26 4, 1 Summary of Basic Elements' State Sets and Events 35 4o 2 Type Structure Routines for Compiler 40 5o 1 Summary of Operation of Compiler and its Major Subprograms 48 5o 2 Summary-Associate Collection Routine 60 5. 3 Summary-Absorb Connection Routine 69 6 1 State Mapping and Matrix Construction Subprograms (of Compiler) 101 7o 1 Program for Solution of Equilibrium Probabilities 108 8o 1 Result Specifications 117 8. 2 Summary of Results Specification Commands 119 8o 3 Summary of Results Calculation Routines 120 9 1 Summary of Phases, Commands, and Areas Used 128 ix

Preface This report is in the form of a proposal heavily dosed with tutorial matter. It was originally written in the latter part of 1967, before work had begun on the program system now known as the Queue Analyzer System (QAS). A working version of QAS [9] was completed in early 1969, adhering in all major respects to the principles laid forth in this report, except that the solution technique of Sections 6 and 7 has not been used directly. While the system proposed here is described in terms of a specific hardware configuration, this work is not limited in use to any one such configuration. It should be noted that for a programming system to be truly efficient, it is always necessary to tailor its structures and formats in some way to the hardware used. This has been done here. However, the techniques and structures are readily adapted to other configurations. Because of the unique nature of the system, it is instructive to publish this report in essentially its original form, with only minor attempts to bring it to correspondence with the final system. Thus, it is more a treatment of programming philosophy, specialized theory, and technique, rather than a complete documentation of an existing program. Nevertheless, all essential information required to understand the operation of QAS is here contained, as well as some information pointing to future directions. xi

lo INTRODUCTION A graphical, problem-oriented system is being developed, by means of which solutions to simple stochastic networks can be obtained rapidly enough to facilitate conversational useo The problem descriptions will be constructed in network diagram form on a remote DEC 339 graphic console. Simultaneously, information concerning the construction will be sent via dataphone to a time-shared IBM 360/67, which will prepare the solutionso It is the purpose of this report to generally specify the central 360/67 programs and data structures which accomplish this latter feato These programs will be referred to here as the Queue Analyzer System (QAS)o The networks drawn will be restricted by the pictorial language syntax to systems which can be modeled by a continuous-time, finite Markov chain, and will be solved by numerical solution of the Kolmogorov equilibrium equations. The advantage, in terms of speed and precision, of this technique over simulation procedures is documented in [2]o Because the data required by the analysis program is in a very different form from that describing a network (which is in terms of blocks and connections), a translator from the latter to the former is requiredo This translator, called the network compiler, is the central, and most difficult, operation carried out by this system0 1

2 In addition, there are four other major operations which the system must perform. It must generate the network description, which is the input to the compiler, from information contained in commands supplied by the consoleo It must analyze the resulting structure for the equilibrium state probabilities. It must calculate from these probabilities the specific results requested by the console user. Finally, it must accept new definitions of symbols used in network generation, All of these operations are to be performed on the 360/67. The manipulation of pictures (network diagrams), the preparation and updating of display files, and the recognition of commands and interrupts from the user are all solely the responsibility of the SELMA system in the remote PDP9 which is part of the 339 console. The SELMA system [11] must also keep the QAS system informed, via the dataphone link, of any operations which concern it, and must issue commands to it to initiate major operationso The QAS system will carry out its processes under the control of the remote computer, treated as an input file (probably named *SOURCE* in MTS [4] terminology). It will send its responses to the remote computer as an output file (*SINK*)o To accomplish this, QAS will have its own version of the current "displayed network" stored in the central computer memory. In order to reduce some of the QAS system-programming problems to manageable proportions, certain limitations of capability

3 have been accepted. These limitations are chiefly ones which limit the meanings which can be assigned to network symbols, and the manner in which the symbols can be related. Our minimal objective in this system has been to provide a system which can at least treat networks consisting wholly of queues9 exponential servers, infinite sources, infinite sinks, random branches, merges, and priority branches. While many other symbols can also be treated in this system, we can by no means treat all meaningful symbols. Nevertheless, those which can be treated define a significant class of models having considerable variety and power,

2. THE BASIC COMPILATION AND CALCULATION PHILOSOPHY A continuous-time, finite Markov chain is a stochastic process Zt which takes on values in a finite set of points called states. If the set of states is mapped by a one-one function h onto a set of integers { 0 1,.... N } and if the equilibrium probability of the state mapped to the s integer k is represented by Tk' then the vector T =- <(O, *'' NT > of these probabilities is a solution of the equation 7xU = 0 (2.1) where U is a matrix of transition intensities descriptive of the Markov chain. An efficient procedure [1] for solving equation (2. 1) for large Ns has been in use for several years. and derives much of its efficiency from the form in which U is stored. An improved storage structure for this purpose called the matrix outline structure [3] has been devised. and proposed for this project. An adaptation of the earlier procedure to this new structure will be required, and will be called RQA-2. Its purpose is simply to calculate vT when U is given. In contradistinction to equation (2. 1). the description of the Markovian system provided by the console is in the form of a network. We may say. by way of definition, that a network N consists of a set of elements and a set - of connections, N = —~ <: 1,,:."_. ~> (2.2) 5

6 where the terms element and connection are yet to be defined but have the intuitive meaning implied by "blocks having a distinctive function" and "lines joining the blocks in particular ways." Our objective is the construction of the matrix outline structure for the matrix U from knowledge of the structure that describes the network N. It is this process which we term compilation of the network. It should be noted that the state of the Markov chain will be related to the joint conditions of all of the elements in the network, so that a part of the compilation will be to form the state mapping from a set of multi-dimensional state vectors to the set of consecutive integers {0 1, 2,. o. N }. It is only after this mapping is specified that the matrix U defines a Markov chain unambiguously. (The process of deriving a suitable mapping is not a trivial one, since the boundaries of the set of possible states will generally be irregular, and the mapping muist be one-one on consecutive integers if computer memory is to be used efficiently. ) The calculation process with which we are concerned involves eight distinct phases. (1) Generation of the Network (2) Compilation of the Network (3) Definition of New Elements (4) Calculation of Equilibrium Probabilities (5) Specification of Results

7 (6) Calculation of Results (7) Documentation (8) System Control and Supervision The user at the console creates a network through a long series of actions, such as creation of elements or connections, evaluating parameters, changing connections, etCo The sum total of all these commands defines the networko The SELMA system (or possibly a teletypewriter) conveys this list of commands to QAS, which must generate the appropriate descriptive structure, step by step. This process is the process of network generation (phase 1, above)o In definition of new elements, a series of commands is received which represents the meaning of a new symbol. This meaning must be assimilated during a definition phase (phase 3), and preserved in a form which can be used to identify future occurrences of the new symbol. Similarly, when de sired results are being specified (phase 5)9 the specifications are received as a stream of commands whose meaning must be collected in a specific form. This form is used by the calculator program (phase 6) to prepare a matrix which can produce the desired result when applied to the vector of equilibrium state probabilities. The documentation phase (phase 7) is one in which names are associated with structures to be saved, and structures in the system can be substituted by a named fileo

8 Each of the phases is a distinctly different operation, requiring its own set of programs and data structures. Each is likely to proceed for a significant interval of time, and to continue at the discretion of the SELMA-generated commands which are, in turn, responsive to the user's changes of pace or purpose. Any phase can be terminated before completion and resumed later. It is the purpose of the "System Control and Supervisor" programs (phase 8) to recognize changes of phase from the information received from SELMA, and make appropriate changes in the current files contained in (virtual) memory. (Since the entire system is large, and the user's sessions are likely to be long, it would be uneconomical to keep all files resident throughout the session.) The segmented nature of the 360/67 addressing scheme seems particularly well suited to this kind of overlaying of programs. In the succeeding sections of this report, the structures of the special files required will be described, along with the programs in the various phases which use them. In the remainder of this section, some further comments about the Supervisor and general file organization will be made. The Supervisor program is tentatively diagrammed in Figure 2o 1. The Supervisor will be assumed to reside in virtual memory throughout the session. One of its chief component parts is a program which regularly reads the commands and data arriving from SELMA. These are buffered (queued), and treated in the order in which they

9 ENTRY ) READ ALL AVAILABLE SCARDS RECORDS INTO COMMAND QUEUE! wAIT FOR QUEUE YES' NEXT INPUT < COMMAND > —->"< RETURN'".NO - gYNEXT Y -. E.ElU AN" END NO | r —" " ODISPATCHER1 * I, T - LOOK AT PHASE OF NEXT COMMAND I (P=PHASE) SAVE AREAS NOT I NEEDED. FETCH I AREAS NEEDED I I I "LINK" TO PHASE | I P PROGRAM 1_...."__ KA __A_ YES. COMMAND NO EMPTY. Figure 2. 1 Supervisor flow ctia-ra n.

10 arrived. Thus, QAS operates asynchronously with SELMA, lagging behind it more or less depending upon 360 scheduling, rate of SELMA command generation, and its own speed. For this reason, barring blunders of either system, care must be exercised that no command received from SELMA and queued by the Supervisor should be able to produce a "fatal" type error in QAS. QAS must not grind to a halt when SELMA commits a syntax error, for example, because by the time the error flag is conveyed to SELMA, SELMA may have gone far beyond the point of error and be unable to retrace. The result would be a dilemma resolvable only by starting again from a clean slate —an intolerable burden for the user. On the other hand, after certain commands SELMA might wait for an affirmative response before issuing more. One such case would be after the command for a network compilation. No other operations should proceed until it is known the network was compilable and did not require changes. The Supervisor has responsibility for a table of area names, and for calling the routines for each particular phase via a LINK-type call to MTS. Every area should have its own table of special pointers to items within itself, the structure of the table being known to every program which uses it. In that way, the Supervisor does not need to keep tables other than the area tables~

12 P. 4p..: J.}. (3.2) i 1 Pi1 j Ji Then the element e. can be algebraically described in the form e. = <..p.. P. >. for all i e I (3.3) 1 1 1 1 For certain useful elements. although not for the four basic primitives. the number of parameters and the number of ports in a particular element is a function of one or more of the parameters. Since tie nature of pi and Pi is consequently dependent upon the value of this parameter (or parameters), this parameter (or parameters) must be supplied before equation (3. 3) has meaning. Such parameter(s) will be called generation parameters because of their special role in the network generation phase. They will always be placed first in the parameter list. Quite similarly to elements. connections are defined by their type, their parameter values, and the ports they connect. Types of connections in our basic list are "simple, " "overflow branch" (sometimes called "priority branch"). "join, " and "random branch. " The remarks concerning parameter values of elements apply equally well to those of connections. The ports connected by connections are the ports of the elements, and each port may be involved in only one connection. Thus, if the connection set is represented by the inaexed set the a cock: Kt, (3.4) then a connection ck is represented as

13 Ck - rk Pk Pk > (3. 5) where rk and Pk are the type and the parameter list, respectively, and Pk is a subset of the ports of the elements Pk C. J Pi (3. 6) 1 e I Every port is in exactly one connection: Pk 6 kk2 E K (3.7) u P = i P. (3.8) ke K k i I (In other words {Pk: k e K} and P: i e I are each partitionings of the set of all ports.) The random branch is an example of a connection having a generation parameter. This parameter is the number of "branches" among which tasks can be switched. The number of ports connected by this connection is one more than the number of branches. as is the number of parameters. The elements and connections as described here collectively dascribe a network. However, it is not necessary that these elements correspond precisely with the symbols used at the console. This notation represents a language for describing networks wnich is distinct from that used by SFLMA. and it is the PDP-9's responsibility to translate between these languages when issuing generation commands to QAS. Nevertheless, if we associate particular graphs with each element

14 type in QAS. then a network N can be drawn like that in Figure 3. 1. r~~-r —mI l_^ ~ Figure 3. 1 A Diagram Such a diagram is useful in visualizing networks, and may be so used in this report. A summary of properties of the standard elements and connection types is given in Table 3.1, along with a set of graphics which may be used for them. 3.2 Syntax of Networks and Diagrams Fquations 2.1 and 3.1 tnrough 3. 8 define the syntax of a network as required by QAS. QAS must enforce rules upon the specification of networks to it which will guarantee that the network satisfies this form. In addition. SELMA may apply further rules for the form of its diagrams. These are primarily to protect the user from

15;^ X^2 *,-4"~0 Cu M + M Q - o C (-; E ) d d b. _ —. c 00 0ld a ro a)C 1..., ~ OO, " a.a0 Q a) 0 aU cy a 0 > CO 0 H S~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~,. I J v T ^"^ iz;~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~C' ( -X-~~~~~~~~

16 constructions which may be compilable, but not meaningful in semantic terms. The chief syntactic rule of QAS is that ports of elements may only be joined through connections. A second constraint is the one, mentioned in the description of connections, that requires ports to be associated with exactly one element and exactly one connection, A third constraint is that parameters of an object (element or connection) must be numerically valued (not variables) at the time of compilation, and generation parameters must be numerically valued at the time of the first mention of the object (io e., at the time of creation). Finally, elements and connections are restricted to instances of types whose meaning has been previously defined using the notation to be described in sections 4 and 5 of this reporto These restrictions merely reflect the requirements necessary to fit the data structures used by QAS. The first constraint, part of the second constraint (the requirement that exactly one element be associated with a port), and the last constraint will all be automatically enforced because, using the command set to be described, SELMA will be unable to violate them. However, it is possible to attempt multiple connections at a port, or to leave a port unconnected, or to supply the wrong number of generation parameters, or to fail to provide values for other parameters. Either SELMA will be expected to guarantee that the proper constraints are met, so that QAS may treat their violation as fatal, or QAS will be

17 empowered to test for them at the time their violation can cause difficulty, and demand immediate correction from SELMA. The latter course means that there must be a procedure for the QAS supervisor (the only program residing in memory at all times) to interrupt SELMA demanding a specific type of response without losing commands from the input stream. In any case, there must be provision in QAS to test these properties at appropriate times, and to return diagnostics. SELMA will require that ports be characterized as either input or output, and that each connection type may connect inputs and outputs only in certain ways. QAS does not have this requirement, and will not test for it. Indeed, it will not even know which ports are inputs and which are outputs. 3. 3 The Network Data Structure The mathematical notation used in equations 2. 2. 3.1. and 3. 2 in defining networks can also be regarded as a shorthand notation for a data structure. To illustrate, let = el e 2e,.... C =(C3....} el ='1P1. P1> e-n-pl. P3 e2 = <;2'P2' P3 > c3 = <'3.P3' P3

18 P1 <n P, ooo > P1 P2 < n, oo o > P2 P1 =P4 P5'~ o } P3 {=P59, } Figure 3 2 describes, schematically, a data structure for this network. The meaning of the various diagram symbols is called out in Figure 3, 3. We have represented sets by a one-word head of a ring, the ring linking its elements. The values of n-tuples have been represented by an nword contiguous block, while elements belonging to a predeterminable number of sets have been represented by a like number of contiguous, one-word ring elements followed contiguously by the value of the element. Because every set in this structure contains elements having identical form and because the programs operating on these structures will always know what kind of element is being operated upon, the use of contiguous blocks in this manner is feasible, and will result in an efficient and compact structureo If objects belonging to a variable number of sets were present, a form of association structure such as that used by Newman [5] could be easily incorporated using "nubs" and nested rings in addition to the above, So far, that has been unnecessary. Although the structure of the network is to be manipulated in the course of executing these programs, the sizes of contiguous blocks will not change during the executionO However, blocks will be created and

19.^ / jT4 \ V) r f )'f U an o Z ~~' Q; Q \ Wi I 0-. 0, 1'- <~* (^...1 iiibQ _ cC~~~~~~~h 0. C ^ ***~~~~~~~~~~

20 Ring Element (Defining Set) -IJ|J Ring Element (Definition) Value Dummy Value I J Pointer - Figure 3.3 Network structure diagram notation,

21 destroyed, and this structural technique depends heavily upon the availability of an efficient free-core manager. The manager proposed in a separate memo [6] (Appendix A) appears to satisfy the requirements. 3o 4 The "Generate" Program The generate phase program consists of a collection of routines corresponding to the generation-commands receivable from SELMA. Upon entry from the Supervisor, the generate program examines the command and issues a call to the appropriate generation routine. The network description is received by QAS in the form of a stream of these commands. The functions of the "generation routines" carrying out the commands are summarized in Table 3. 2. More generation routines may be added as use of this system becomes more sophisticatedo These routines operate entirely on an area called the network area of memory which contains the network structure, the type structure (to be described in section 4), and a symbol table, The symbol table provides the means for converting element names, connection names, and other names used by SELMA to corresponding addresses in the network area. The table grows as commands are received defining new objects. Objects also can be removed from the symbol table, The simplest form for it is obtained if SELMA assigns consecutive integers as names for objects, whereby the table consists solely

22 I0~ j &'@ X)O O i O C Or-. o ~ o a)f~~'~~ UI ( 0 o CD 0 0 d 0 X "0p I~!:: d ^^6 Dr C> < z O. > d O LS-s d2 > ^^. s C D r Y W X U U i;'C rwf^ ci ow^, Cdu PJ C' (Dk~ ~ ~~0 CO2 00 E ki 0rC o' a ~ c ~ *,S ~1 S ^2 a.2 ^2'o^ i ^ rt ^co ~a CP 0 CP ~'~'~ ~ C~ "~ ~',-Cr 0 i ~, Q' S 0 tOcQ ) _3 a a o> g a a Oi o. c- C'. " O ( O 5I~~~~~~~~~~~~~~ n u B BO C1 R 2 a.n E - o.,.,+ E a) >S 0S. S~ S S _ ~ Is 0 s, 0s P. r-j I 4-). i s b.Oh ii 4-L C; ) 3 —h F: k 56~~~~~~~~~~~~~~~~~~~~~~~~~~~e u r 4( 1 F~ %-L3 Opr-~~~~~~~~~~~ E4 E 1~~~~~~~~~-1

23 of a vector of pointers. The location of this vector within the network area should be permanent. The symbol table should also keep a pointer to the network block (N) as, say, its first symbol. Thus, the symbol table will keep the locations of all master objects as well as those which must be referred to by SELMA. This will permit master blocks to be moved at will for such things as documentation functions which use the network area, by merely changing a pointer in the network area's symbol table. To facilitate discovery of unconnected ports, which would prevent execution of a compile commando a special master object R is in the symbol table representing the set of unconnected ports. When elements are created, their ports are automatically joined to this set. "Connect" commands unjoin ports from this set, and join them to a newly created connection. The symbol table and unconnected port set block are illustrated in Figure 3. 4. The "create element" and'alter generation parameter" routines will be described in detail in section 4, which treats the information needed to define types. The other generation routines in Table 3. 2 should be self-explanatory. 3. 5 Service Programs Required Four sets of service programs will be needed by the generation routines. They should be FORTRAN-callable so that the generation subroutines can be written in FORTRAN. They will also be found

24 LLb aia ~~~~~~~~v \ J ~ c t ) 1 a::3 b.C - - 00 Q. Q. - c \ \ Y.,l..a.\'" (\ \ \Z \,~. /. \~~~~~~~~~~~~C \ / \~~~~~~Q x ^:Q Z C <U *** (D * cn_ __

25 useful to other phase programs, such as the compiler. Their functions and calls are summarized in Table 3. 3. The list of programs shown is probably not complete, and may be added to once programming is begun. In particular, the ring operators represent a subset of the commands used in Roberts' CORAL system [7], and some of the other CORAL commands may be also desirable.

26 () 4~" — 0 o 0 o o 0 o o C0 0 o oM I O D O U a)1, S 0 o 0o' O oO O oO o 0a O 0 O, z; 4 ZJ -Z z 4-. U ~ 0 * I 1 a * C), co 44 s) a-)0^ s I) V, 5 ~ O S 0 bf l A m k d -4-J +J 2 v u a) u.Sa) - ~0 0 0 0 0 10..," 0 -o cU C ~ ~ ) P1 EE k -c ~ U) a) -) Cg > 0 0 01 S-'- c;ctl CR a, to a 9 01C) Si k d C Q).,-, S ~) Co 0 0 o0 o o C 0 r?-, 0 > r 0'A rou 0 cj < D ^ (D^ FU CD 0 ( L no ooa CQ Cc at f ft c oI' 3 "Z ~co t ao0 1 t E: C 0 ~ ~r(~ d ~~~~ ~ ~ ~ ~l~ r SZ: (1)~~~~~~~:

27 I E I: a a O O O $ O,,' ~, O ~ O 1 4 o 0^E 3 a a b n >~ 4Ct 4- 0 a) u E cd M z Z S ct 5 aD a2:* a) a ~ > p I -e tl E k U S C O0 5 * e. _. a)2 0.g 0, ~rl g s.'2 s, ^ 1 s cl N: ) E.5 c D 2 oE 0 0 "0 a0 )' 0 9SSS S cr C H 0 0 0 0 CH 0 E (-4< O CH (D O0a ao o 0 0 0. -, -,..C^ 0 E=~~~.~ c^ 0t bD.c ^;|h ^ C^ ~2 M ^ (^ < M T~~b "d~ Q, c.

4o PRIMITIVE ELEMENTS AND THEIR MEANING The elements in the network structure have been described in terms of their types. Examples cited were the types "queue, " "server," "exit, " and "sourceo" Each of these are called primitive types because they cannot be described in terms of any other element typeso However, a description of their meaning must be given if the compiler is to have sufficient information on which to operate. In this section, a means for formal description of the meaning of a type will be given, and a data structure for conveying that meaning to the translator will be provided. 4. 1 The State Set Every element has a set of states associated with it. These states represent the various possible identifiable conditions which the element can assumeo In QAS, the state set of any element will be a finite set of non- negative integer n-tuples, where n is characteristic of the element. In the case of a queue whose "maximum. length" parameter is N, this set is the one-dimensional set of integers, {01, 1, 0 N}, representing "the number of waiting tasks." In the case of the server it is the onedimensional set of integers {0, 1, 2} representing the "idle, " "busy, " and "holding" conditions, respectively. Finally, in the case of both the exit and source it is the set {0}, a condition representing "readiness to receive (or send) a task " Although all four of the basic element types have one-dimensional state sets, higher dimensions are 29

30 possible for yet unnamed elements. The things which most characterize elements are the stimuli which can produce changes in state, and the responsive changes. These are characterized by the so-called events of the element-type. Some of the stimuli are self-generated, as, for example, the "service completions" of a server. Others are external stimuli, as the occurrence of "inputs of tasks" at a port of an element. The stimuli and responses of the former will be described by autoevents, while those of the latter will be described by exoevents. 4. 2 Autoevents By definition, an autoevent f of an element ei having a state set Si is a triple f - < bSggf > (4.1) where bf is a subset of Si gf is a constant n-tuple, such that for each x e bQ, x + gf is in S. Af is a positive real number f is an index in some index set L.. Here be is called the autocondition set of the event (l, and represents a set of states for which the event is possible; the constant it is called the rate of the event, and represents the probability intensity of its

31 occurrence; the constant n-tuple g, is called the increment of the event, and represents the change in state which results from the occurrence of the event. To illustrate, consider the "service completion" event a for a server having mean service rate (parameter) y. The event can occur only in the busy state, state 1, and when in that state it occurs with probability intensity y. The event causes a change from state 1 to the holding state, state 2, so that the change in state is unity. Thus, = < {1}, 1, y > (4. 2) It is possible for an element to have more than one autoevento Consequently, for every element there is a set of autoevents, called the autoevent set 14 =i'(4 3) i = { t e Li} (43) of the element ei where the index sets Li are disjoint over all i in I. Frequently, when the format of equation 4. 1 is insufficiently general to describe a particular stimulus and its response, the desired description can be obtained by splitting the description up into several autoevents. 4. 3 Exoevents By definition an exoevent m at a port p of an element e. having a state set Si is also a triple

32 m <= <bm' g' rT > (4.4) where: b is a subset of S. m 1 gm is a constant n-tuple such that for each x E bm, x + g is in S. m 1 Tm is a probability m is an index in some index set. Here bm is the endocondition set of the event, and represents a set of states for which the event is possible (e. g., if the port p is an input port, b is the set of states for which an input of a task can be accepted); the probability of the event wT is the probability, given that the stimum lus (eo go, an input of a task) has occurred and that the element is in a state of bm, that the change in state produced is equal to gm the increment of the event. An example of an exoevent is the "input of a task" event (call it 5 ) at the input port p of a queue whose maximum length is No An a2 input can be allowed only when the state is less than N, and it results, with certainty, in an increase of the state by unity. Thus C = <{0,1,.,N-1}, 1, 1 (4.5) for N 1. For every port p of an element ei, there is an exoevent set Z i(P),

33 representing all the possible responses to the external stimulus at the port po The function Z i will be called the exoevent function of the element e.o The exoevent set is a set of exoevents whose probabilities add up to zero or one for each state of the element. Let i(P) - m' m c Mi(), p Pi iI, (4 6) and (m < bm gm Tm >' (4. 7) m m m m where the b, gm Tm have the forms appropriate to exoevents of an element, and where the Mi(p) are disjoint for all p and i. Then Z - Oor (4 8) morn x ( b m for each x eS. where S. is the state set of the element. Those states for which this sum is zero are states for which the external stimulus cannot occur, such as, for example, the states where an input task cannot be accepted. 4o 4 Type Definition The meaning of the "type" r. of a particular element ei is consequently conveyed by the triple < Si, i>, so that we can write i < Si i Zi > (4 9) for all i E Io The above rules for determining the state set, autoevent set, and exoevent function have been applied for instances of each of

34 the four basic element-types, and these properties have been summarized in Table 4. 1. In each of the first two cases, the port p1 is the input port, and port P2 is the output port. It is interesting to note that the exit and source elements are identical in these terms. Consequently, they will both be treated as instances of a single elementtype, the source-exit. Other element-types are, of course, possible provided their stimuli and responses can be completely described by events of the form described. The information conveyed in Table 4. 1, and extensions of it if more element-types are defined, must be made available to the compiler. In particular, there must be a data structure which describes the type r. of an element ei in literal form, with all dependencies upon parameters evaluated and readily available. In addition, the compiler in the course of its work will be creating more elements which are not instances of these basic types but are equally described by triples < Si, S, Zi > > The structure for providing this information to the compiler is added, at the appropriate times, to the network structure by use of the r-line in the element blocks. This structure is illustrated schematically in Figure 4. 1 for an element e1 such that P I {fP1 P2} (4.10) 21 = t49 t21} (4.11) Zl(Pl) {C3' 4} (4 12) i; p, ) {5) (4. 13)

35 zz z z 0 0 0 0 A A VI I A oA 7-4-.1-1 — 0'-4r-t~ ~ ~ ~ ~ ~ ~ ~ ~~~~r. 66 a, 0- 0- 0. 0 4-J 0 L _ c 0 0 P^^W~~~~~~~~; caaa CO2 QC) Cl) cr 0 o o a)'-4 C.4 - -~" ~ ~ c,~ E Q, 3 Q> O~~Z4

36 it In Un It3 In 0. -4 rn ~.,4' OJ U) ) ~- m \-.\-^ ^:. ^y~~~~~~,)lrt \3 \l

37 The sets of states S19 b1, b2, o, b59 and the increments gl,.o., g5 are not shown; their form will be discussed in section 4. 6. The block L is referred to as a type block. It should be noted, however, that at the time the element block was created (during generation phase) the type line -r in the element block contained a name of the type, rather than a pointer to a structure like that shown in Figure 4o 1o It is not possible during element creation to form this type structure because the parameter values are not yet knowno (It should be noted in Table 4. 1 that variables N and yt were necessary to represent the state set and the eventso ) It is also not completely desirable to supply this structure immediately, even if it were possible, because it would considerably increase the amount of storage required during generationo This information is needed only during compilation, or if compilation has been partially performedo In any case, the;-l.ine in the element block has two possible meanings, and during compilation either meaning may appear in the lineo Since a pointer requires only 24 bits, and the name (a type number, actually) can be contained in an 8-bit byte or less, it is not difficult to distinguish between the two cases. By reserving the name "00" (hexadecimal) to literal valued types (i. e., those for which a structure is present), and using the format shown in Figure 4. 2 a simple routine can determine whether name or pointer is presento If the pointer to the type structure is present, we say the type is literal valuedo Otherwise,

38 the type is said to be named. NAME I POINTER 0 78 31 Figure 4. 2 Format of -r-line of element. 4. 5 Type Structure Generation When the compiler creates an element itself, it will always have a literal type. When the element is created by the "create element" routine during generation phase, it will have a named type. The conversion of the named type to a literal type will be carried out only when the type structure of the particular element is needed by the compiler. The compiler requests the literal type of an element through a routine called the type finder. The element is specified and if the element is already of literal type, the pointer to the type block is immediately returned. If the element has a named type, the finder calls a particular type-evaluation routine which creates the type structure, using the parameter values of the element. There is one type-evaluation routine for each type name. These routines are written wnenever a new type name is added to the repertoire of QAS. The operation of the type structure programs is summarized in

39 Table 40 2o These programs are used during compile phase, and require the presence of the working network structure onlyo 4o 6 Representation of Sets of States and Increments The set S for each element is a set of n-tuples. The autoconditionsets and endocondition-sets of the events of the element are subsets of this seto For reasons of efficiency in the operation of the compiler, it must be possible to rapidly form unions, intersections, and differences of these sets. For efficient use of storage, these sets cannot be represented by rings of members; their number is too great. For these reasons, a special data structure must be used for representing sets of n-tuples. The basic unit in this structure will be a structure representing rectangular sets of n-tuples, sets which are Cartesian products of sets of consecutive integerso Any state set, or subset, will be represented by a union of rectangular setso This structure is illustrated in Figure 4. 3. The basic line describing the set is a single word whose format is shown in Figure 4. 4. This word contains the dimension, n, of the ndtuples9 and is a ring heado The upper byte of the ring elements pointed to is zero, and, since sets of dimension zero are not permitted, the head is recognized by the non-zero value of this byteo The ring elements define rectangular blocks, with the ring itself representing the union of the rectangles representedo There are n+2 half-words in each rectrangle block (the first two being the ring element

40 tl,, S'-'. - 4 -.s l r- ^,^1 ^ r-^, C13 ^ rr —xl - l. 6 S, Q. CO a',2;~~~~~~~~~,1 0d ~^?^ } srr > aDJ w 0 CD,w c) C.) M SDg W 0 aC,) "8 c4 e, S }t~3 E g~~ ""_ r-4, CS 43 Cl a ) nd ^ g 8 3 s ^ s D 0F oL?; r Ci 0 a _ U a..4 ~ PLPJ'F -., C) t 3, d)i C)^ ~ ~ ~ L Il si3 )C * )^ (( C) HS C); C) b, ~ X==) ~ C) F-J

41 S N. C|| C|2 i C21 C22 0 uI l IM Cnl l C2 1 1 __ Figure 4. 3 The set structure for n-tuples. In, POINTER 0 78 31 Figure 4. 4 The n-tuple set head word.

42 word). Each half-word after the first word consists of two bytes, the first of which supplies the lower bound on the rectangle in one of the dimensions, and the second of which supplies the upper bound. Set operators for intersection, union, and difference can be readily designed for this structure. Increments (the g-lines in events) will be represented by the same type of head element as for sets, showing the dimension and a pointer. In this case, however, the pointer will be to a block of n bytes, each giving the increment in its corresponding dimension. All blocks in these two structures should be rounded to full words in their allocation. A set of operators for these two structures will be required for such things as intersection, union, sum, etc. One special operator, called back-projection, is needed by the compiler. It has two operands, a set and an "increment, a and forms the structure for a set whose members are the members of the set operand minus the value of the "increment" operand. This set will be represented by the symbol rl(S, g), where S and g are set and increment operands, respectively.

5. THE COMPILATION PROCESS The compiler is a program, called by a single command from SELMA, which transforms the network structure into a new structure suitable for numerical analysiso The new structure represents the matrix U of transition intensities (see eq. 2. 1) in a compact form, so that the iteration may proceed rapidly without extensive paging (which would cause response to the "solve" command to be uncomfortably slow)o The compiler operates destructively upon the network structure, so that a copy of the network structure must be saved prior to the compilationo This function, which calls upon the documentation phase programs, is carried out by the QAS supervisor when it detects a "compile phase" commando In order to distinguish between the network structure and the workspace of the compiler (which is identical to the network structure when compilation begins), we will refer to this workspace as the working network areao The compiler makes use of two areas, the working network area and the transition-table areao This latter area is the place where the new structure is placed after the compilation is finished. It is, obviously, one of the areas used by the analysis procedure during the analysis phaseo This area is required only at the last stage of compilation, and is created during the compile phaseo (If a translation table 43

44 area already exists at the time a compile command is given, its contents will be replaced by the new transition table. Hence, a documentation phase "save transition table area" command must be given by SELMA before the compile if the old information is to be saved ) The procedure for compiling the network involves a successive absorption of the connections. Each connection is considered in turn, and it and the elements it connects are replaced by a single equivalent element. This process continues until no connections remain. To illustrate, observe the network of Figure 5. la. The connections of this network will be absorbed in the (arbitrary) order shown by the encircled numbers. The compilation proceeds as schematically indicated in Figure 5. lb, c, d, e, finally resulting in a single element having no ports, which is equivalent to the original networko This procedure provides a systematic means for tracing the influence of each autoevent upon the entire network's behavior. The resulting element consists of a long list of autoevents describing the probability intensity of every change in state which is possible. The translation of this information into the form of the transition table is then a relatively simple operationo Figure 5.2 shows the flow diagram for the compiler. After it is invoked by a "compile" command, the compiler first determines that no ports remain in the network which are not connected to another port, by testing the ring whose head was labeled R in the symbol table of the (now) working network structureo If this test is successful, the

45 (a) - fb) ~ (c) rW) (d) (e) Figure 5. 1 Illustrating thre compilation procedure.

46 ENTRY EXAMINE FOR UNCONNECTED PORTS < EMPTY PICK A ce C 1 YES \ _ / CREATE MATRIX COLLECT ASSOCAND STATE MAPPING IATES OF c STRUCTURES 1 r....T CRETURN) (ABSORB c /TRIM STATE \ < SET OF NEW ELEMENT Figure 5. 2 The compiler flow diagram.

47 compiler proceeds through a loop, successively absorbing connections until none remaino The absorption of a connection has been divided into three distinct steps. In the first step, the elements joined by the connection to be absorbed (we will call these elements the associates of the connection) are collected into a single equivalent element having ports corresponding to each of those of the associates. This collected element then replaces the associates. In the second step the connection, which now joins only ports of a single element, is absorbed to create still another elemento This time the element is equivalent to the collected element with its connection, and the final replacement takes placeo (The two step operation eliminates the need to treat connections between ports of a single element differently from those between ports of different elementso ) In the third step, the state set is reduced to eliminate certain common types of transient stateso The operation of the compiler and its major subprograms is s ummarized in Table 5. 1. The remainder of this section will discuss the subprograms in more detail. The subprogram which creates the matrix and state mapping structures will be discussed in Chapter 60 50 1 Collection of Associates The operation called collection of the associates of a connection c has a simple algebraic interpretationo What it entails is the creation of a new element et whose port set is the union of the port sets of the

48 Cn cL o Ia ~.0 o 0 3 O *.. a) Q (D Zn ^ hf) Qz -4. —) ) U 5+ ) cPL Cd j QU O C 0 0 0 L) P, 0 o PiQ o o z C12 o "bl ^-. ~ uS a2 -0. gc w b'Db.;,I~~~~~~~~o z 4 (U o P |' "I $M4 CU |4 | X.0 7 -oPS4c U00=c d U a-) a 0 00 m ~ ~~~~~~~~ 4k o a,~~~~~~~~~~~~~'-Fo Ul P4 d Cd Ul m m m a) C?3 k E CR -bc~ 8) 4-J: 4z.-) CD0 S-~~~~~~~Pi U 0 0.S 0.7.-.7-4 - 4 —)' a) 0Q a, nl a)00 a) *i-L~ - a m G r h 0 d 0 o 0 a) ft o u^^ <;^ &-< a) b0 ~0 a) a).5 4 -,. O 0t: CbS 0 Qd ~O O, C~.- -Qc H

49 0 U U) {. r,O S..2 F d &s ^ ^ < o D CCO!)O, oo z Qa) a)O O Q) E Q) PC dd Q 0S C0 s *) z 0' C0 CO aQ, L^a) a) a) a) S S o b fl 8~ ~ ~ ~ ~ ~~~~~~~~b oRF M ^! ~-< SL(d PFe (J kS4

50 associates, whose state set is the Cartesian product of the state sets of the associates, and whose events are adjusted to correspond to the new state set. Let the set of elements to be "collected" be E*, where E*= {ei: i I*}, (5.1) and let the collected element (the result of this operation) be e* e* < r*,p*,P* > (5.2) where.* - <S*, *, Z* >, (5. 3) the parameter set p* is null, and the new port set of e* is p* = U p. (5. 4) i I* Let I* = {i1, i2,, in}, and select an arbitrary ordering < i19 i22. o o in > on the members of I*. The new state set can then be written S S. x S... xS., (5.5) 11 12 in, where the product A1 x A2 of two sets A1, A2 of n-tuples is defined as a set of n-tuples having a dimension which is the sum of the dimensions of A1 and A2, and for which the members of A1 x A2 consist of all concatenations of members of A1 with members of A2. For example,

51 f<1, 1>, <2, >} X {<3, 2>, <3, 3>} {= <1, 1, 3, 2>, <1, 1, 3, 3>, <2, 1, 39 2>, <29 19 39 3>} (5o 6) (Notice that this operator is not precisely the Cartesian product operator, for which the example would give the set f<<1, 1>, <3, 2>>, <<1 1 1>, <3, 3>>, <<2, 1> <3, 2>>, <<2, 1>, <3, 3>>}) The autoevent set E* is the union of autoevents of the elements, suitably modified to account for the changed state spaceO In particular, let ~ = <b& g, g l> be an autoevent of an element e. in E* (. eo f' L. a a i c IP)o Then ~ will be represented by the new autoevent *-= <b*, * gI1 >, 5 7 where b* G S x oo xS S. b1 X S X ~ ~. x S. (5o 8) &. a -1 a +1 n1 and g * <9 0 0 o 9 09 g,01, oo 0, O,> (5o 9) with g concatenated with zero-valued n-tuples in a position corresponding to S in S*. The set 2 is E -?i~oc T Li i( I*}. (5 L0) To simplify notation, eqo (5. 8) will be rewritten b* - S*x b (5 1l) a defining "<i. " as an operator meaning "restrict the projection of S* in the components corresponding to Si to the set b1" In a similar vein9 a

52 eqo 5. 9 will be rewritten gf* * S*i g, (5.12) a defining "0. "as an operator meaning " extend gf into the set S*, with a projection gf in the components corresponding to Si, and projection a zero in all other components. " For each port pj e Pi, i e I*, the exoevent function Z * is given, similarly by Z *(pj) - L m e Mi(Pj), i I*} (5. 13) where * m= <b*m,g* m7T > (5.14) m m mm b* = S*x. b (5.15) mn m g*m = S* igm (516) m 1 m and where M.(p.) is the index set, defined in section 4, 3, of the original elements. Each Z i*(Pj) is readily shown to be an exoevent set, satisfying the constraint on r m given in eq. 4. 8, provided only that Zi(pj) was. The collection routine, called by the compiler, makes the changes in the working network structure corresponding to the above equations. Its input is a pointer to a connection, and its output is a pointer to an element e* which is the "collection" of the connection's associates. The original elements (the associates) are destroyed.

53 This program, which is flow-charted in Figure 5. 3, has three main partSo The first finds the associates, removes them from the E ring, and joins them to a newly formed ring E*o The second forms the state set St of the collection E* using the natural order of the E-ring as the reverse order (right to left) of the products of the Si, i ~ IPo (The order is reversed for consistency with later operations, since the port set P* and event sets $* and Z* will be most easily formed by repeatedly joining successive components immediately behind the headO In the course of this activity the types will be evaluated by calls to the "type finder" ( cfo section 4. 5). The third part successively extends the event sets and then accumulates both the port sets and the evenrt sets of each element, destroying the elements as execution proceeds until E* is empty. Figure 5. 4 shows part of the structure upon entry to the colle.ec!oro The encircled symbol represents a "bkug" or pointer retained in the. oallector program. Figure 5. 5 shows that part of the structure after the first two parts have been executed and the program has progressed to the point marked 3 in the flow diagram (Figure 5, 3). Figure 5o 6 shows the same part of the structure upon return from the collector, The structure of the state sets has been omitted from the diagrams and will be treated separately later, in section 5o 6o The first two parts of this program need no further discuss.ion. Part three (poirnt 3 in Figure 5o 3) beginras by taking the first elemnent

54 ENTRY FIND ASSOCIATES \ LET E —E-E* / PART 1 E ^ YES EMPTY ERROR, NO EVALUATE TYPES FOR PART 2 ALL eEE* FORM S* PICK FIRST e'cE LET E*- E*- {e') LET S'-S* LET E —E U{e'} LETp* BE EMPTY EXTEND EVENTS | \_ _2 OF e, PART 3 YES TROY E* EMPTY DESTROY E MTNO /RETURN PICK FIRST ee E* | e EXTEND EVENTS OF e / _____ Y__ Figure 5.3 Flow diagram LET P' p-/P'UP for "called assoLET'-0'"U ciates" routine LET T'?-Z'UZ DESTROY e,T -1

55 & ~J) ~ ^,,.1, -. 0, 0 0 \^~~~~~~~~~~~~~~~~~c \ K)U' Q.;~~~~~~~~~~~~ i~ <M 0 CI,,' Vu T1\ ^C -^<u~~~~~~~~~~~~~~1, \ v^ i o \" iT / ^nn ms z~ LJU.?~a iTCo II* I bc 0 — 4 "^ \/ (') -/^ / \/ \ / _ ^^~~~~~/

5r ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~,,,..J..~._. mlii 0~ 1 1 NNN L,-,, J n 0. n ~ ~'.......{ 1) w~L L/I - _.. ~I \ I - (' 0.~~~~~~~~~~~~~~~~~~~~~~~~~~~Ur I~~~~~~~ OL Q: I F~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~C --- L. J il -4^ 7\.'aT i1Q LfU- ) /~y I K/ _ ^, b~~~~~~. a,_ —.

57 L_ 3 3~ ~ P PI P2 Px.Z(p1) b b* b* Figure 5. 6 R~esult of collection operation on figure 5. 3.

58 block of E* and letting it be the element block which will become the collected element e*. It is removed from E* and put back in E. The S* which was calculated in part two replaces the state set of this element. The parameter list of this element is replaced by an empty list (the type must henceforth be literal). From here on, following programming convention, this element will be referred to as e', until the end of the operation, when it becomes the e* of equation (5. 2). The ba and g of the exoevents and autoevents of e* are extended to the new state space, and replaced. That is, bf is replaced by S*x i bb and gg by S*O. g for each ~ e S* and each e Z*. This latter operation is done by a separate subroutine~ is done by a separate subroutine. At this point ("a" in Figure 5, 3) each remaining element in E* is taken, in turn, its events similarly extended to S*, and its ports and events added appropriately to the ports and events of e'. If P,, Z are the port set, autoevent set and exoevent function of the current element, then, since they are each represented by rings, they are added to PI, T, Z' by insertion P' <_ P' u P (5.18) 27 < = - u 2 (5. 19) Z' < — Z'U Z (5.20) where the arrow represents "replaced by" and the union symbol here means "insert the ring members of the second operand between the head and ring members of the first operand. " The head of the second

59 operand is destroyed in the operation, which was called "ring concatenation" in Table 3o 3. The major subprograms of the collect routine are summarized in Table 5. 2. 5o 2 The Meaning of Connections The exoevents at the ports of an element represent the conditions under which tasks can be removed from (or inserted into) the element via the port, and the consequence to the element's state of that removal (or insertion). The function of a connection is to indicate a relationship between the exoevents of a set of ports. It indicates the conditions under which a task is to be transferred between a pair of ports. For example, when a pair of ports is joined by a simple connection, a transfer of a task occurs immediately whenever the "output"v port has a task which can be removed and the "input" port simultaneously can accept a tasko The exoevents at the two ports are thought to "occur" spontaneously whenever these conditions are met. For each type of connection the rules determining the occurrence of the exoevents will differ, and the meaning of connections is conveyed by these rules. Since we will be operating only on collected elements, the only time we are concerned with the meaning of a connection will be when it is a connection between ports belonging to a single element. The definitions that follow will assume that condition~

60 r i2 pC I s~~~~~~:~a a) 4' a) 0CO a) 0a3 ~s ~l aas s ss3 as s $3. ~asa3 ~~~~~0 0~~~~~~~~~~~ ( a a) aa4 - " <U ~ ~ ~ m t+-(A',.,- * r-i~~~~~~~~fl l 0^ CD~ric~~~~~~~~~~~~~~~~ 0 ~ ~ ~ ~ ~ ~ ~ ~ c W u >u Oa4 Z O )Q* 0 ( 0 c, -r rd o~~~~~~~~~~~~C 4-j 0~~~~~~~~ Q) U1~~~~~U.SpZ~a) E ka4 0a) * a,)a 0cd a, a~"a, a)~ a)r ( ca f-i 0 0 0t-t 0 U a ~ ~ r ro~~~ cc:~c^sftS —~~~ S" 0 02 O2 4 limit~~~~~~r ri4 o~P U2 r/ UC 4PC1 P2a)5~ -c,,53 <U 03 *^ "S: > * ^' ro ~ C4^ ~ 5 1 ~~cJ2 C| 3 a)~~~~~~~~~~~~~~~~~~~~~t- Cd". a, a, -4, E4 eCt Mt r- Q a ~~~~d ~~~~~~~~~d E: -C3~~~~~~~~41 d- - Cd c ar ~ ~ bJ a)Es6 )U kOI F4 O cn ha o fl E c~~~4 Q. 4- 4-;t4 Q) d ~rl -r ~0 C) C, d > m l c5 0 i r Q^ ~~ 0 ~ ~^~~~~~~~~~~~~~a cu3 E *33 <U 0 ~ C Co C bI)~Q QO 0f S a %9 CO OC Q 0 > Fo ~~~~~~~~~( U1co 0 c Q) C4a) ( A > r o I~~~~~~~~~~~~~~~~~~~~~~- CO; ^"4 4- 0 as I s CJ 4 —( k c d o oc~ 4-j Q) k r-Iui 0~~~~~~~~5:r 61;~ -b, W V4 Ca Cd a C1 OO L k c u w co c ell P-4.~~~~~~~~~~~~~~- P i

61 CQ O CQ d zoo no ^*P4Cb 2 a) a)= a o *-4.0z X U F: 3, Q 8 a) - 9' *r3 00 0, S bfl CS CC O - - o o ~ i z o) ~: Pc Sq bt av a):) 0 Cl -4-a o a) l LO a)

62 The information describing the effect of such a connection upon its associated element will be described by a set of objects called spontaneous events. These events describe the conditions for, and immediate consequences of, transfer of tasks through the connection. These events can be thought to occur "spontaneously" whenever the state of the element becomes one of a set of forbidden states. For example, in the simple connection, a forbidden state would be one in which one port was "offering" a task and the other could "accept" one. The consequence would immediately be a further change in state. Let the spontaneous event set O of a connection ck joining ports k k of the element e. be 0 - {:h' h Hk}. (5.21) where h = < bh, gh' "h > (5.22) bh is a subset of Si gh is a constant n-tuple such that for each x e bh, x + gh is in S Th is a probability Hk is an index set. The set bh is the forbidden state set, gh is the increment of the event, and lh is the probability given that the state is in bh that it will jump by an amount gh. As for exoevent sets, the probabilities in a spontaneous event set must satisfy the restriction that, for each x c S.

63 f "h=- Oorl0. (5 23) ho xe bh The spontaneous events are formed from the information conveyed in the exoevent sets of the connected ports in a manner which is distinct to the "type" of the connectiono Let a connection ck be of simple typeo Let the ports joined by ck be Pk {p. I p. } and let those both be ports of the element ei, so that Pk C Pi~ Recall that the exoevent sets of p. and p. are given by Z1(P m e M )} (5.24) Zi(Pj ) - { m MP )} ( ) 1 I m "1 1 1 1mi < b 9 gml,,T > (5. 26) m m l < bm gm59 m >. (5. 27) 2n 2i m2 2' The spontaneous event set Ok for this simple connection is given by Ok -= {h~ h (g Mi(Pjl ) Mi(j )} (5. 28) 1 1 where mm0 ^<b n b, g g 9 r 71 >o (5o29) mlm2 m ml m 1 m2 m m This indicates that spontaneous events occur whenever the state is in both endocorndition sets, and that the increment is the sum of that due

64 to removing a task from one port and that due to inserting a task into the other port. The set of states for which no spontaneous event occurs is bk = S.- (b n b ). (5.30) m1 m2 m1 2 For convenience in the programming, we will find an augmented spontaneous event set 0k to be useful. It is defined, for the simple connection, as 6k=Ok u {<bk, 0, 1 >}, (50 31) where the additional event represents no change for states which are not forbidden. In this case, the probabilities add to 1 for every member of S.o It is readily shown that eq. 5. 23 is satisfied for the spontaneous event set,. The other connection types will be discussed below. In what follows the element whose ports are being connected will be called ei, and the exoevent set of any one of its ports p. will be assumed to be written ca Zi(Pj ) = {m:m e Mi(pj)} (5.32) with cm <b,gm,7T > (5 33) a a a a The probability summation property will hold for all spontaneous event sets definedo

65 Considering a connection ck of overflow type, let the output port joined by ck be p., the preferred input port be p., and the overflow k P 0 input be p., so that Pk {.. }.C_ P.i The spontaneous events consist of two classeso those which represent a preferred task flow, and those which represent an overflowo The first class occurs whenever the state is in both b and bm for each m and m in M( ) 0 1 1 and M(p. ) respectively, since that is the only condition where the preferred flow is possible. The second class occurs whenever the state is in both b and b but not in any of the b y mo P M(p ) (io eo preferred flow is not possible), for each m0 and m2 in M(pj ) and M(p )o - 0 1 Algebraically, k {0: h c M(pj ) M(pJ )} U { h M(p ) M(pj (5. 34) 0 (: <b n bm g + g I > (5 35) 0m m m 0 bm m0 mO mlm 0 m2 <b n b -( u b )' gm + gmh m 1rm > ~1 ~ ~ m (5.36) for m) e Mp. ), m2 Mp ), m M(p ). The no-event state set 0 1 h 2 is bk Si bh, (55. 37) hc H where H (M(p. ) X M(p. )) u (M(p. ) M(p. )), and the augmented 0 1 ~0 2 spontaneous event set Ok k u {< bk 0, 1 >}o (5. 38)

66 The merge type connection, joining an input port p0 of ei, a (preferred) output port pl, and (secondary) output port P2 (one must, in defining any merging-type elements resolve the competition among inputs, and that is done here on a purely priority basis) has precisely the same spontaneous events as the overflow-type element. Thus they are indistinguishable, and will henceforth be given the same type-name, the "overflow-merge " The random branch is defined, for the purposes of this report, as a branch for which flow can occur only if a task can be accepted at any connected input port of the element, and if a task is also available from the connected output port. Let the output port of the element be p0 and the input ports be P1,.,0 pn, where N is the number of branches in the connection. When this condition is met a task is transferred from po to one of the ports, pj say, with probability a, a=l, 2, o0 0 N where (N, 7,...,yN) is the parameter list of the connection. Algebraically, Ok = {Oh h e M(J)x. x M(jN) 1,..., N (5. 39) m =a < bM n..^ nbm, g + g,ITo...Nr y> (5.40) mc ~ gm m m' ~m m a O' 0 N 0 "N 0 a 0 N for all m e M(p. ), a=1,..,N. As usual aa bk S- U bh (5. 41) a ~nd~ ~h and

67 ok = ok u {< bk, 0 >}o (5.42) Provided that the property N - 1 i (5.43) a = holds, the probability summation property (eq. 5. 23) will also hold for Ok~ 5o 3 The Absorption of Connections The operation of connection absorption removes the ports connected from the associated element, prunes the exoevent sets at the removed ports from the exoevent function, forms the spontaneous event set, and then consolidates the autoevents, remaining exoevents, and spontaneous events, to produce a new element. The operation of this subroutine of the compiler is illustrated schematically in Figure 5. 7, and its major parts are summarized in Table 5. 3. The first operation in the program determines the element joined, and alters the structure in preparation for the formation of the spontaneous events. The ports joined by the connection are removed, and appropriate alteration of the exoevent function is carried out, with the exoevent sets of the removed ports shifted to the connection structure, This operation is clearly illustrated in Figures 5. 8 and 5. 9, which show fragments of the network structure before and after the first block of Figure 50 7 is executed. In the course of finding the element associated

68 ENTRY FIND ei MORE THAN Z;- i -Zi(Pk) ONE ELEMENT PiPi - Pk JOINED BY c, RR ETUF PkA'*- -i (P k) DESTROY ALL pEPk -:' Tk=?''SIMPLE" R RANDOM" "OVERFLOW' C REATE SPONT.\ CREATE SPONT. /CREATE SPONT. EVENTS EVENTS ) EVENTS (SIMPLE) (OVERFLOW (RANDOM) ONSOLIDATE EVENTS DESTROY, k Figure 5. 7 Flow diagram for absorption of connections.

69 bf a a Co ~ B ~ o, a a~~~O ~~cOD., a, 0 00"- J D ^^ ^ M 0 *-^^0 >ae)^O~3^S.. 0 u uX o a, 4 ~ P,?q z U O Q CQ P ~ c o S u e 2 0 42 a Bg a; a +-1-6 0 Xa 0 O bD O' O CO O ) 0 2 z I! up! I bX0 aSSSD S 0 &S^a ( a) ~~'~~4-4 ~ ~ ~ ~ ~ ~ ~ ~ ~ - CO ba 0 a (D, -0 COO, j?-C SU) o r i aa? 4 CQ e S - -- mO U)2 )' a) o a Co 0 *0.~.~r.... (D^a'^ a *^ 0 ^ *r sO ( (: 0 JPo o=xoa. (p 0 bn 0 0 0b ~QD a) 0a)aoa) 0 o Po4 CO) i)G 0]5 0 C7 ~~~S U^~~~~ ) VIaa S + ~a) + Sa)n —, -~ ~ Pa -0 U c ) CQ0a P0U2 U2a) a a) H o O4 M 0 cn > -A " I rr% ~ a~~ ab -ba acB -c E dU

70 -I — P ^-F 5. 83 _P1 P3 2 P23 --- f co7-n-c absrpto ^^~ — _-T VI g4 2 3 5, b4 2 b3 b 5 asI kL4 rp2 73 77(5 Figure 5. 8 Fragment of working network structure at beginning of connection absorption.

71 Q.- 0fl - \ II a,1~,,,?3. 44, \ f0 \ ^ ^, yv ^ / \ _~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

72 with the connection, this block will also discover if, by failure of the element collection program, the number of elements connected is not unity. This is a fatal error. At the conclusion of these operations, an appropriate Spontaneous Event Routine is called, depending on the connection typeo Since the spontaneous events will not be altered during the period of their existence, and since the operation of "getting" and "freeing" small blocks is relatively time-consuming, the Spontaneous Event Routines should create the entire O-structure so that it is physically contiguous. If this is done, only one fairly large block need be gotten from the free core manager, and it will be kept until the connection absorption is complete, at which time the entire structure can be destroyed by a single "free" command to the manager (see "Destroy Ok" in Figure 5. 7). The spontaneous event routine (a prototype of which is shown in Figure 5. 10) constructs a list structure which corresponds to the set described in the previous section in its requested core spaceo The events will be generated one by one and added to a ring, while the state set S. and no-event set bk will be pruned with the formation of each event. Thus, at the conclusion of the formation of the last spontaneous event, the state set has had all forbidden states removed from it, and the augmented spontaneous event set Ok has been formed. Whenever a forbidden state set bh is found to be empty, the corresponding spontaneous event 0h will be simply omitted. In this routine, also, the parameters

73 ENTRY COMPUTE AND GET REQUIREDOR RET TO',-ERROR RETURN) CORE BLOCK. CHECK PARAMETERS SET UP POINTERS FOR INDEXING THROUGH EXO- EVENTS. FORM bk4- Si GENERATE A bh EMPTY SPONT. EVENT 8h bk- bk b-b S-S- bh NO LAST.... DESTROY EXOEVENT SETS Figure 5.10 Prototype flow diagram for spontaneous event routines.

74 are checked, if this is a random branch, to see that the probabilities (ye in section 5, 2) sum to unity. The exoevent sets for the connected ports are being destroyed after the spontaneous events have been formed, and the structure finally appears as illustrated in Figure 5. 11o 5o 4 Consolidation of Events The operation of event consolidation replaces each event (either exoevent or autoevent) in the element ei associated with the connection by a new event, or events, which includes the effect of the spontaneous events. The action to be accounted for in this operation is that produced when an event of the element causes a spontaneous event to occur. Such is the case, for example, when a task completion in a server causes a transfer of the completed task through the connection joining its output port. The effect of the autoevent is to change the state. If the state is thereby changed to a forbidden state, the spontaneous event (task transfer) occurs, changing the state again. In this report, we assume that only one task may be required to pass through a connection upon occurrence of any event, so that the second state change cannot itself result in another spontaneous event at the same connection. A similar argument applies to exoevents, as, for example, the consequences of a task being entered into the input of a queue. This will result in an increase in state which may cause a transfer of a task through the connection joirning its output. That is, the state is changed

75 0 I; o,- 4 7-\ \ / \ \jr -o" o? ^~~~3 Q

76 to a forbidden state and a spontaneous event causes a still further change in state. The new event set is readily found from the old and the spontaneous events. Let Ok be the augmented spontaneous event set Ok = {h h e Hk}. (5. 44) h = <bh gh' h > (5. 45) and let i. be the auto-event set of the associated set e. = - {Y(t: e L} (5. 46) =:<b 5 g / > (5.47) Then the new auto-event set S i* of the associated element e. will be = *- {(. ^* Lix Hk} (5.48) These events are *h = < b n b n?g(bh) gf + gh' h (5 49) for all P c L. h E Hk, where, by definition r1g(b) represents the set found by subtracting the vector g from every member of the set b. The set bk n bh n 77g (bh) represents all non-forbidden states in bp which, upon occurrence of the event y, are carried into a (forbidden) state in bho It is these states only which are affected by the increment gh' Similarly let pj be any port in Pi, and the exo-event set zi(Pj) = {(m.i mj E MP)}, (5. 50)

77 m. < bm gm'n >M (5. 51) J J j J becomes Zi*(Pj) = { mj* Mi() X Hk} where m.h < b. n gm (bh) gm + gh, T > o (5. 52) m.h m< g bh m. h. h J J m. J (The probability property, eqo 4o 18, for exo-event sets is readily shown to be preserved. ) Many of the sets b n rg (bh) and bm n rg (bh) may be found to &// m]^m. be emptyo In such a case, the event conveys no useful information and may be omitted from the corresponding set of events. The program which will accomplish this transformation is the event consolidator, described by the flow diagram of Figure 5. 12o This program calls on the "event set consolidator'! which is described by the diagram of Figure 5o 13. The symbol D is used in this diagram to represent an arbitrary event set - {f: d e D} (5. 53) Od = {bd' gd'd } ~ (5. 54) This program proceeds around the D ring, inserting the new events behind it as it proceeds. Each time a 4d has been treated completely, it is destroyed and the program proceeds to the next'fd until it comes

78 ENTRY * CONSOLIDATE PICK FIRST Pi PEPi ERROR RETUR CONSOLIDATE SEE "EVENT SET CONSOLIDATOR" GET NEXT NO g LAST p OBTAI NED YES RETURN Figure 5. 12 Flow diagram: Event consolidator.

79 ( ENTRY - PICK FIRST Od E EMPTY RETURN PICK FIRST eh EMPTY <^ n (bh)'rd YES EMPT> NO PLACE h |l Ij AT RING HEAD NEXT NEXT FOUNDih eh EXHAUSTED DESTROY, TJd NEXT FOUND TEXT _d EXHAUSTED URETURN) Figure 5. 13 Flow diagram: Event set consolidator.

80 back to the head of the ring. If either set is empty, the result is an empty E*, 5. 5 Trimming of the State Set The consolidation procedure described above can, under certain circumstances, produce surprisingly large state sets, This will be particularly troublesome when a random branch was involved in the compilation at some stage. This is an manifestation of a general problem facing this translation which cannot be economically solved: the problem of transient states and reducible Markov chain models. The points in the rectangular "state set" SD of the (finite) Markov chain of the entire network fall basically into three categories 1) Forbidden states 2) Recurrent states 3) Transient states. The forbidden states are points of SR which result immediately in spontaneous events, which, in turn, take the process to a point which is not a forbidden state. The forbidden states are automatically pruned from the state set upon each consolidation, and hence are no problem. The present difficulty revolves around the presence of transient states in the model. Transient states are legitimate states of the Markov model. However, since they have an equilibrium probability of zero,

81 and since information bearing upon them ordinarily has no bearing on the calculation of equilibrium probabilities of other states, they are "excess baggage" and will waste valuable storage in the various data structures of QAS. The ideal procedure would be to identify all transient states of consolidated elements as they are created, and to remove them from the state set. Unfortunately, there appears to be no systematic procedure for identifying all of the transient states without performing a calculation very similar to evaluation of all equilibrium probabilities, which defeats our purpose. (We want the state set reduced before we calculate equilibrium probabilities. ) The example of the random branch is a good one. Let a diagram contain a fragment like that of Figure 5. 14. The states for which more PA (-................" -'....... _..... Figure 5. 14 A network fragment containing a random branch.

82 than one server is busy cannot be entered from any state for which less than two servers are busy, since the random branch is blocked when one server is busy, and no "tasks" will be transferred. However, if the system starts with more than one server busy it will, upon exit of tasks from service, enter states with less than two servers busy. Thus, there is a fairly large number of transient states (37 recurrent states, 120 transient states, 4 forbidden states). As more elements are consolidated with this fragment, the ratio of transient to recurrent states will remain much the same, at best decreasing to 2:1. The states of the example were easy to identify through physical insight, a weapon not available to the compiler. A general solution to the problem of eliminating a transient states is not available, A more specific "fix" must be one which is guaranteed valid for every network and every definable element and connectiono In other words, it should not unnecessarily restrict the already restricted class of models which can be treated by QASo Especially, it should not result in a restriction on inputs to the compiler which cannot be enforced syntactically before compilation is attemptedo Fortunately, there is a class of transient states which is relatively easily recognized and which includes those of the example. The recommended solution will eliminate this particular kind of transient state, and result in perfect pruning of states for the random branch. Figure 5. 15 illustrates various cases of communication among transient (shown by circles) and recurrent states (shown by x marks) for a total of three

83 states. (a) ox (e) (b) C i —x (f) o —.x x (c) o —x (g) x- -x (d) o-A-x x (h) x x x states can be found Since case (a) of Figure 5;5 is representative — n c a',,!g on. r. 1. sI-KWn F. ^..., -.:.....,^ -s';;.. 0'. ). The procedure recommended is that, subsequent to the absorption of each connection, the states which are not "target states" of any event be successively trimmed from the state set until no more such states can be found. Since case (a) of Figure 5. 15 is representative of what happens in the random branch example, the need for successive trimming should be clear. The target states of an event fd) (either auto- or exo-) are found by the expression q'(bd) using the "back projection" operator previously defined. using the "back projection" operator ~1 previously defined.

84 Figures 5. 16 and 5. 17 illustrate the programs required, and show how the removal of previously located transient states can be efficiently accomplished while new transient states are being sought. The set T1 represents a set of known transient states, while the set T2 is a set of states formed by starting with the state set and repeatedly deleting target state of events as they are sequenced through. Once T2 is found to be empty, we know that no further transient states will be found by this method. However, the sequence must be continued if T1 is not empty, so that all previously located transient states are removed from all events. Figure 5.17 is not particularly efficient as shown, since calculations of set-differences, and evaluations of r7 are performed even when some components (T1 or T2) are known to be empty. Suitable switch setting or branching can make this program highly efficient since the most probable situation is expected to be the case with T1 empty, and since T2 is expected to be frequently empty after only a few events are examined. Figure 5o 18 shows one possible configuration which will take advantage of such information, 5. 6 The Result of Collection, Absorption and Trimming After repeated collection of associates and absorption of connections, the working network structure will eventually lack remaining connectionso At that point, the network structure will ordinarily look like Figure 5. 19, with a single element having no ports or exoevents,

85 ENTRY JTTr-T2, T —- SJ- - T2 r' i T24 S- / TEST AND\ T1-.2,TRIM EVENTS)- -— ETUR OF i /T2I PICK FIRST Pi-= p Pi TEST AND\ I <TRIM EVENTS RETURN 1,._i _.. -T- RTU OFA Zi(P) L NEXT T2 = l _NO, *LAST ps T.r- c NO,< OBTAINED Y< ES RETURN Figure 5.16 State set trimmer flow diagram.

86 PICK FIRST c1dE" D E_'PTY bd* bd-T, T2 — T —.gd(bd) I: W NO I A<TI AI-ID T22, i SBOTH EMPTY —-- of. A L/SPECIAL RETURN,N0 k "T,,T2 =^ NEXT FOUND NEXr Pd ZD EXHAUSTED RETURN) Figure 5. 17 "Test and trim events" flow diagram.

87 ENTRY PICK FIRST i~d cE'3D ^YES EMPTY RETURN TNO EM PTY"' T 9'-T2-/ ge(bd)] 2 (2' —- N0'- 1sYES SPECIAL bd -bd-T T bd bd- T EMPTY RETURN; To 0 A NEXT I F NO FOUND NEXT YES T2 --- EMTY NEXT ^si"^ ^?^ FOUND Z EXHAUSTED NEXT RETURN T2-T2-rgd (bd) _- I EXHAUSTED (RETURN NEXT. FOUND/ r..~, Z EXHAUSTED RETURN Figure 5. 18 A more efficient "test and trim" program.

88 N I-Li /- 2 I-L _ / Fj I ~~b|, b3 Figure 5. 19 Typical result of absorption of all connections.

89 and a large set of autoevents. The information in this set of autoevents describes the information in the matrix of transition intensities for the retworkg which must be prepared next. It is, however, possible that the network will consist of more than one element, with all the elements isolated from one another. There can still be no ports, since there are no connections, and there were originally no unconnected ports. This multi-element condition is the result of the original network consisting of two or more isolated parts. This implies that the model described was, in fact, several models, each of which has been compiled here. At present, this situation can be treated as an error condition. Nevertheless, it offers interesting potentialities for more flexible use of the system, and future implementation should probably allow for it. In that case) procedures would be needed for identifying which isolated network was to be solved, and for what variables. For the time being, however, it is easier to give an error return if the result of absorbing all connections is a network with more than one element.

60 THE STATE AND TRANSITION-MATRIX STRUCTURES In the numerical calculation of equilibrium probabilities, it is necessary to repeatedly multiply the "matrix" of transition intensities by a probability "vectoro " The autoevent set resulting from the repeated absorption essentially describes the matrix of transition intensities, the set bk describes a set of columns of the matrix which contain the intensity " 9, while gk describes how far off-diagonal the intensity gk is in each of these columns —hence defining the row in which each can be fourndo The state set resulting from the repeated absorption describes the index set of the probability vectors. (To each state there must correspond a unique probability in the probability vector). Because of the multidimensional description of states, however, the structure that results from the repeated absorption is unsuited to rapid execution of the matrix-vector multiplicationo To use this structure in its original form one must either spread the probability vector over a prohibitively large area of memory so that a very simple formula can be used to find a probability when a state is given, or one must spend enormous amounts of time in the process of state mapping repeatedly upon each multiplication. The large number of dimensions involved makes it likely that a simple linear mapping of a large rectangular prism containing all the states may actually use hundreds or even thousands of times as many locations as there are states. Even 91

92 so, that mapping would have to be performed twice with each scalar multiplication in the matrix multiplication, and would be dominant in determining the time required for the operation. Any more efficient mapping would require much more time and be completely unreasonable, Such time demands would defeat the primary purpose of this project, which is to provide sufficiently rapid (and inexpensive) response to enable the user to experiment with models on the computer in a symbiotic manner, As a consequence, the only alternative is to prepare a new structure which is well suited to the matrix-vector multiplication-operation operation, and permits rapid execution with minimal storage requirements. The expense incurred is the addition of another stage of translation between the consolidated network structure and this new structure. This operation is a part of the compiler and was shown in the flow diagram in Figure 5. 2. The objective is to allow the matrix-vector multiplication to proceed with such computational efficiency that the time taken is only ten to twenty percent greater than that taken by the scalar multiplications and additions which are inherent in the matrix operation, This section will describe first the state mapping function and the structure which supports it. It will then describe the structure to be used to represent the matrix. Section 60 3 will finally describe the procedure used to create these structures,

93 60 1 The State Mapping Function To obtain an efficient use of memory for the probability vectors, the state set should be mapped onto a consecutive set of integers. This has the advantage of minimizing the number of pages to be used for the probability vectors, and hence decreasing the elapsed time (rather than cpu time) of solution under dynamic paging in the computero The state set has been represented as a union of rectangles (in n dimensions). Let the state set to be mapped be S, and let S S1L S u S u, SNs (6o1) where S is a rectangle, S {,^...: }Yv1 v0,v }oo <.~ ~.......v.. IVI, }\o (6o 2) n2 I Each v is an integer, corresponding to appropriate values in the ntuple structure and n is the dimension of the set, for v-1, 2.. o, NoS. The mapping will associate a unique integer with every state by providing a simple expansion of each rectangle. Let 6 be the car0 dinality of the union of the rectangles S1,..., S -. ~, 6 =,- # t S -, # (S.) (6. 3) and let 610: 0, (6.4)

94 Then 6 + 1 represents the state number corresponding to the lowest ~0 numbered state in S. The numbering of the remaining states within S is according to the usual rectangular mapping used in most programming systems. Let 6 be the product of cardinalities of the previous i-1 div. mentions of S, so that v 6 I= 1 (6. 5) 6 (i+1) = v(v - + 1), il, n. (6. 6) Then, accordingly, a vector x < xl 5,.. x > which is a state in S will be mapped to the integer x 6 o (x -v )6 + +.. +(x -v )6 (6.7) "0 11 1 ni n In this manner, each of the states in S has a distinct mapping x and the states in S map to a set of consecutive integers, {l1.., 0 6 N 0 Complete information required to use the state mapping, Eq. (6. 7), is given by the two-dimensional array < 6: I, v o,. N iN 0=l,, nA >. The state mapping structure produced by the compiler is simply a MAD (or FORTRAN)-type two-dimensional array of halfword integers, assuming (reasonably) that the number of states will always be less than 65, 536. Operators required to construct this structure include one (a "state structure generator" " which prepares the structure when the state set in n-tuple set form is given, and another (a "state mapper") which uses this matrix and the n-tuple form of S to obtain the mapped

95 value of a given state according to Eq. 6. 7. 6o 2 The Transition Matrix Description The matrix structure must describe the autoevents S in such a form that no state mapping need be performed during matrix-vector multiplication. It should permit rapid execution and efficient storage for the common forms encountered. The requirements seem to demand that the structure be in some type of outline form whereby events which occur for rectangular subsets of the state sets can be compactly represented and evaluated through direct indexing on the data of the structure. One such structure was proposed in [3] for a somewhat more general class of problems, and that reference gives scme useful ideas. A more specialized structure which appears to be more efficient will be incompletely presented hereo The structure is illustrated in Figure 60 1, A value-line (i or P, in the figure) indicates the value of a collection of identically valued matrix elements, A block-line (,09 g in the figure) indicates the first row index (03) of a subset (called a "block") of the collection of identical matrix elements, and a number (g) which, when added to a column index, gives a corresponding row index for each member of the block of matrix elements. The members of the block are identified by a series of indexing-lines (f, 6 in the figure), which indicate increments

96! 8 /9 8 Figure 6. 1 Illustrating a matrix structure. (5 ) to be applied to the column index to get another column index, and counts (j) of the number of times the increment is to be applied. Each line is a words the %O's 6's. and g's are halfwords, the j's are bytes, and the remaining bytes are coded with sufficient information o that line types can be recognized This structure. when the details are worked out, should be f2'~ Figucapable of describing any matrix at least as efficiently as by a listure. of triples (value, row index column index), and much more efficiently when element values are repeated diagonally in a regular pattern as will be the case for QAS transition intensity matrices using the abovedescribed state mapping procedure. Because tne information contained in the indexing-lines is exactly the information required for

97 quickly loading and testing "index-registers, " rapid execution of the matrix-vector multiplication should also be assured. To further illustrate. consider the matrix U: x I II I tI, 5 e X! \ I 1X i A X H. X,' I I. X' 1 I x I index is two less than its row Thus the g for this block is -2. The value repeats twit and that pair repeats four times with spacing of three. Two other blocks consisting of single elements ( e b-lines only) complete the treatment for there is a I! value repeats twie with unit spacingI and that pair repeats four times with spacing of three. Two other blocks consisting of single elements (i.e. b-lines only) complete the treatment for of For"A" there is a

98 VI b 4 -2 i - l2 I 4 3 b 3 -2 b 2 -I V X b I +5 i!31 i 2 6 * * Figure 6. 2 The structure for the matrix in eq. (6. 9). single block starting in the first row (01=l1 g=5, etc.). Multiplication of this matrix by a row vector proceeds by considering each block of the matrix structure in succession. The value /i is placed in a register and index registers are set up for nested loops, with depth of nesting equal to the number of i-lines in the block. The P0 gives the initial displacement of index of the appropriate element on the vector to be multiplied by /j, and g indicates the increment to be used to locate the index of the element of the result vector into which the product is to be accumulated. To be more concise. if y and x are vectors anci y xU, and if a vector y is initially zero, then y(03+ g + ii + i2 +...) will be

99 replaced by Y(O0Q+ g +il +i2+~~~ ) + M * X(0 +i +i 2+ ) repeatedly for each i1 06, 15, 26 o' 1; i2= 2' 26 2 ~ ~' 22; @ q; iqO, 6qo 26 6 o o q q; where q is the number of i-lines in the block. This replacement is repeated for each block of the matrix structureo The result is the vector y. By suitable use of registers, this operation should not require significantly more time for execution than is taken by the scalar multiplications and additions alone. 6. 3 Creation of Transition-Matrix and State Mapping Structures The proposed outline structure for matrix representation is well suited to the storage of transition intensity matrices because it is efficient for both isolated matrix elements and for nested, diagonally repetitive elements. These two cases occur with great frequency in transition intensity matrices of Markovian queueing networks, The final subprogram of the compiler has the task of providing the state mapping structure and the transition matrix structure, These are created in two separate areas: the state area, and the matrix areaO These areas are created by suitable calls to the QAS supervisor.

100 The state and matrix constructor (a subprogram of the compiler) contains two subprograms. The first creates the state area and its structures. The second converts an autoevent into a series of lines in the matrix structure. The state and matrix constructor calls the latter subprogram once for each autoevent in the network. The characteristics of these subprograms are summarized in Table 6. 1. The state area must contain three items: the state set (in its multidimensional form), the ring which identifies the state variables, and the state mapping structure. The first and third are required for the state mapper (which provides a mapped state when a vector is given), the second is required in the specification of results (cf,, section 7)o All three are required in the generation of the matrix structure and the compilation of the:results matrix. Figure 6. 3 illustrates a reasonable form for the structure in this area. The symbol table is used precisely as it was in the network and working network structures. The procedure for constructaing the state mapping structure should be clear from eqs. 6. 3 - 6 6 Two difficulties will be encountered in programming the matrixevent generatoro In converting an event tk = < bk9 gk9 k > (6. 9) to matrix form, we must note thato first, although a part of bk may be rectangular, it will map into a'bl1ock~' in general only if it is also a subset of the state rectangles; and, second, the 7'increment" g, will

101. I -. S.2 I 0E~ c ~0 ~'~ rC 0 0S o. — ~o 0~) z ~ z -> -, e3 0 ^ C30 05 S o~z zu, bfl bD - t!,,.. 0) - ci) "54 4^ ^.(n ci)a. r S 0 -0 d Cd -,,j C) 0. 0 3 0) y-d b4 z C) a) 0 dn 0 o u S'~:o HQ S ^ fi *"^ ^ Sico;q -4- 0 o2 0r/S~ 00r S) U a ^ a-? +- 9~ a>' a,' 0 Cl) 0 )4-j ^ j ~d o'3 0 -s HS''b Co M 0).^O 0) 4 4? - a-S 0,' "'' go ) 0 0 " i0 D0) E0 Q~ c/2 c, c2 bf >or 0 <u~x o r d 0, o. o,'3 o ~ E 6 ~ ~ h~~ a, c ~w~~ 8 ~ c,~,c Q i;c Sd~~'. ~,.. FoaF ~FaC 6FogS4a,~

102 ~~ z z z1 CC) w w Cf)~~3 o ii ---------- ~n 4jn iO/n ^ bfit,~~~~~~~~~~~~~~~~bl U) 1 Z U I ) / 4er V)cw mm:: g.n.O:^.^^

103 map into a constant only when it does not represent a crossing of a boundary between state rectangles. Thus, if the state set were of two dimensions and consisted of two rectangles S1 and S2, and bk were a rectangle contained in S1. bk may still need to be represented by more than a single "block" in the matrix, as illustrated in Figure 6. 4. Here the event is assumed to take each state in the direction of S2S S|/-/ S2 3 0. L.................. l k )o Figure 6. 4 Illustrating "splitting" of bk for constancy of g. All but the rightmost column would have a constant mapped increment gk. found by simply weighting the i-th component of gk by the respective 6 li. However, it can be readily shown that the mapped increment (gwk) would generally be different for each of the states in the rightmost column of b,. Some procedure like that diagrammed in Figure 6. 5 would have

104 ENTRY YES 0 INCORPORAEERROR b'-* bKn SV, bK —-bK- Sy, b" b'nTMg(S>-,) b'- b'- 7g(Svl ) YES NO /I NCORPORATE b" iNTO MATRIX; STRUCTURE FORE F.YES b = NO /INCORPORATE / S CROSSING STATES (b') INTO STRUCTURE FOR b? so NO ^\ BYES Figure 6. 5 Tlie matrix-event generator.

105 to be used to take account of these difficulties. Here, one first determines which of the S rectangles contains which portion of bko These are designated bv, and are removed from the bk. Then one determines which of the b' cross into a different state rectangle. These are designated b", and consist of a rectangle or set of rectangles readily mapped by a block or blocks. The remainder of the b' must be treated individually by a routine (labeled "incorporate S crossing o."). Experience with handworked examples suggests that the boundary crossing cases can fairly frequently be added to existing blocks, but in a nonpredictable way, and that this is sufficiently frequent to warrant considering a scan in the "incorporate S crossing.. o." routine which adds stray terms to existing blocks. However, the cost of such a scan and the typicalness of the handworked examples are still imponderables. In any event, the advantage of treating transitions within a state rectangle by blocks in the structure, rather than individually9 seems unquestionable. There should be a small number of state rectangles representing large numbers of states, giving major advantage to the technique. It should be declared also that since execution of the matrixvector multiplications will probably not use every indexing line as a register (hence fast) operation, and since order of indexing-lines within a block is irrelevant, the procedures should place the irndexing-line with highest repetitivity (3) first m every case, on the assumption that

106 only the first one will involve exclusively register-to-register indexing. The extension of this idea if more registers are available is obvious. Upon completion of the execution of the state and matrix constructor, the working network area contains no useful information, and will be cleared.

7, THE SOLUTION FOR EQUILIBRIUM PROBABILITIES Once the matrix structure has been formed, it can be used to calculate the equilibrium probability of each stateo A single command will initiate the process, which makes use of three areas the matrix area, a state probability area, and a working probability area. The latter two areas, which will contain vectors of state probabilities, are created upon entry to this process. The working probability area is temporary and will be destroyed upon completion of the process. The input of this program is the matrix, a specification of desired accuracy, and a specification of the maximum number of iterations to be allowed (which provides a limitation to the investment in a run, protecting the user from excessive expense for ill-conditioned problems). The output is the equilibrium state probability vector, which is left in the state probability area, and an error estimate, also placed in the state probability area. Table 7. 1 summarizes the characteristics of this program. The numerical technique to be followed is an iteration process of the form r n+l nA (7 1) where A is a stochastic matrix, and X is a state probability vector, When A is formed from a matrix of transition-intensities in a particular way, and when the initial iterate VO is suitably chosen, then the 107

108 0 F40 o Z ~, or4 a a 0 0 *_-4 6 3 O r3 ^ 0 _:S - V J X h3 U 3 ),ag <: M' o o0 PC0 *,-I o 0 e. a, o Fr 0 0-4 0 0 >0 3 0^ 4b-.p..

109 limit of this iteration is the equilibrium probability vector rr lim rn (7.2) n s A detailed treatment of the numerical technique is provided in [1], which describes the prototype program, RQA-1. The matrix stored in the matrix area is not precisely the matrix of transition intensities, since it does not include diagonal elements. Let d - <dl.. o, dN > be a column vector consisting of the diagS onal elements. Let Q be the matrix actually stored in the matrix area. Then the matrix U of transitional intensities is U Q Q-D (7 3) where d Q1 (7.4) and 1 is a column vector of appropriate dimension whose elements are all unitay Then, according to eqo (12) of [1], with a suitable change of notation, the stochastic matrix A is given by A A(Q + D) + I (7. 5) where 99 6 max d. (7. 6 i 1 Thus the iteration process is Tn+l = Tn(AQ) - S7 AD + Un (7o 7) n+1' - n n

110 This program follows the basic outline of the RQA-1 program, which we will assume is familiar to the reader. It differs, however, in several major ways. First, because the matrix stored describes Q rather than U, the iteration process is different. The values of A and d must be calculated, AQ is formed, the previous iterate n is copied from the probability area into the working probability area, and then 7 n(AQ) is accumulated onto the probability area, forming I n(AQ) + n. Finally, d is used to accumulate ST AD onto the same area, to complete eq. (7.7). Second, since the matrix Q is formed automatically, there is considerably less demand for testing and diagnostics, and the sizes of the arrays are known and do not need to be calculated. Third, there will be no repeated runs in any particular systematic form, so that the choice of how to form the initial iterate is narrowedo It. is also narrowed by the greater remoteness of the user, since he has no knowledge of the state space and is unlikely to want to provide his own initial iterate, Fourth, this program is designed as a subroutine, rather than as a main program, and the discipline subroutine (DISCPL in RQA-1) is no longer neededo Finally, output is the responsibility of another program, the result of this program being merely the probability vector.

Ill A flow diagram for this program is shown in Figure 7. 1, where the names of corresponding RQA-1 programs are inserted (in parentheses) where appropriate. A default is provided so that, if a matrix has not been prepared, the program supplies a trivial solution. This prevents system shutdown over such errors, with the error having a clear meaning to the user. It is expected that an interface program will be created which will allow a batch or teletype user to directly supply a list of autoevents and state rectangles, and a description of a results matrix (see section 8), and obtain a solution without involving the compiler and the network generation programs, (In this way we obtain a very powerful, primitive model solver which is akin to, but an improved version of, RQA=1 ) This interface program, which calls on several QAS subroutines including the "State Probability Solver, " will be called RQA-2.

112 ( ENTRY ) I N ITIALIZE PARAMETERS CREATE VECTOR AREAS /NORMALIZE MATRIX PRODUCE VOID ( Qo'aQ' 0 V VECTOR (STOCAL) / SET RETURN[ CONDITION SWITCH / ESTIMATE & \ RETURN / NORMALIZE \...... \INITIAL ITERATE/ \ (ESTIM) / " PERFORM' / ITERATION \ \Tr- TrQ-7rD+TT/ (ITER) WIZNEAK^ NO — ~ CONVERGENCE OR EXCESS ITERA- -"T~TIONP YES / STRONG\ CONVERGENCE, TEST / (CVGTST) / /ITEST^^ NO SAT ISFIED-N SYES ESTIMATE ERROFi (RETURN') Flow ai:agr art.. ~ori sat'e pr i:)'k;.:J.iity solver. Figt~rl r- 7. 1

8. SPECIFICATION AND CALCULATION OF RESULTS The results desired by the user of this system will not ordinarily be the state probabilities in their raw form. Rather, they will be various quantities which are readily computed from the state probabilities. For example, one may desire the probability distribution of the number of tasks in a particular queue; or the mean queue length; or the probability that a particular server is in use; or the mean rate of service completions in that server, or the rate of transfer of tasks through a particular port; or the probability that a task is blocked at that port. Each of these represents a weighted sum of state probabilities, or a set of weighted sums. In other words, there is a matrix F such that the result vector w (perhaps with dimension one) is w - ii. (8J 1) In addition, many other useful results, while not of this type, are readily found from results which are of this type. For example, the expected waiting time in a queue (which is the mean number of tasks in the queue, divided by the mean rate of task transfer into its input); or the mean time between service completions of a server (which is the reciprocal of the mean rate of service completions). Such results can be treated as functions of weighted sums W f(w) (8 2) which are describable by subroutines, 113

114 Furthermore, in any particular solution, the user may have several results which he would like to observe simultaneously, so that the vector w may consist of several results strung together, and the function f may be a set of functions on different parts of the vector. There are four separate operations which QAS must be prepared to carry out to produce output: (1) The specifications of results must be retained in a storage structure. (2) The matrix r must be prepared. (3) The vector w must be computed. (4) The result w must be transformed into the format required for SELMA. The commands associated with the first operation will be added to the generation phase commands, while the last three of these operations will together constitute a phase called the results -phaseo 8. 1 The Specification of Results The need for a separate structure which "remembers" the requested results stems primarily from the desirability of allowing SELMA users to specify results at any time during the development of the network model. Often he will want comparable results for several modifications of the network, and will want to change the network without charnging specifications. Often, too, he will want to make minor

115 alterations, as an afterthought, long after he has decided what results are to be observed. The specification can not be transformed to its final form (a matrix I ) until the network is complete and the state mapping structure determined. Thus, the results specifications must be saved, awaiting a command to prepare the matrix and to solve for the results at the appropriate time. The structure which accomplishes this should be available during the generation of the network, however, and consequently should be placed in the network area. During generation, changes in the network may invalidate existing result specifications, and procedures which are responsible should make adjustments. For example, a queue whose expected length has been specified as a result may subsequently be eliminated from the network. During the operation of the "destroy element" command in network generation phase, a test should be made to determine if a result specification is involved, and if so to eliminate the result specification at the same time. The reference of a specification to an element or a port is syntactically like a connection. in that a destruction of the object requires a choice of destroying the connection or refusing to destroy the object. Thus, one form which this structure can take is a ring structure form. adding new attributes to the element and/or port blocks and connecting them to appropriate "result blocks. " Since the number of results specifieci will generally be very small, most such attributes would

116 normally have their default (empty) values. A more efficient, but less uniform, structure would provide a simple table of result specifications which can be searched by generation routines anc rewritten in the (improbable) event that alterations are required. A minimum set of result specifications is tabulated in Table 8. 1. The purpose of each of these specifications should be self-evident, except for the sixth. By means of this latter specification. it is possible to establish the probability that an input port is in a blocking state, or that an output port has a blocked task. All of the specifications in the table represent weighted sums of state probabilities. Since commands altering the results specifications will be intermixed arbitrarily with generation commands, and their structures are in the same area. these commands are best treated as additional routines in the generation phase program. Table 8. 2 indicates a minimal set of results specification routines needed to carry out alterations of the results specifications. 8. 2 The Calculation of Results The calculation of results, which can result from a single QAS command issued after the compilation of a network. involves, as we've said, three operations: preparation of the matrix j computation of the vector w (cf., eq. 8. 1 ), and formatting for output to SELMA. In this section, we will assume that the last operation constitutes a

117 bn (D a ~ ~,., ~W +ez0~ )~>~,~ -4 0, - U 2 c|.a.,....,.4 } ~F= & 46 4) 0 0: -fl^ D0.' * 4- * 4F-'F. -,== C D ):R -4-a. 4,'-, - ~ a) "J' C, H; U) FS a ~ UO) a~ 44- 4;,< ~ s, bJ~,,c^::lS P- o 13 Q,~~'") 1 td'~a EH C ~ pb aa Q Q a) C) 0^~~~~~~~~~~a s C Ul 4J1 a T H e S S Sc g S^ S- c - C ) c C0 -, E D, ).,.^V ~,: d ~4 0 c c' HCD~~~~~~~~~~~~~~~C For~~~~~~~~~~~~~~~~~~~~~~~ -ed E E~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~,,,

118 simple supplying of the appropriate portions of the vector w with the copies of the results specifications so that the result can be identified by SELMA. Thus, we assume that SELMA takes responsibility for making necessary further transformations, either of the form of eqo (8. 2) or into graphical displayable form. (If this is not the case, and if QAS is to provide more general results than those which were described in Table 8. 2, or if QAS must prepare the output graphics, then further structures must be supplied to accept format specifications and function identifications in the results calculation phase. ) The commands for this phase are summarized in Table 8. 3. The only nontrivial operation in the figure is the preparation of the matrix K o For this purpose an area is created, called the results matrix area, where the structure describing will be kept. The matrix F should probably be represented in matrix outline form, with the modification that the increments g should be replaced simply by the row index of the result. This reflects the fact that repetitive element values in r will generally be along columns instead of diagonals. Naturally, the vector-matrix multiply operator will need to be different, reflecting this change. To illustrate how this process would proceed, consider a column of the matrix corresponing to the ma cosdig to e probability that a particular queue has length two. The elements of this column will consist of ones at

119.P cd -e, o6o u 0 0 r c1d Z Z 4 Z Z 0 *S 0 2 o ~a C )': 03 " 0 * -, ~ rJ "- O-4 CJ 0 S c O g.. aa o O.-U C:Q 2: 0 E — r,-q E-I, E ( -4-j -4-i 4- a ~4 0 0 a U *a) 2 0'-r- =. o Q Q) Q ad *) q * -C " a) a) a), a) a a a a) S a) F-< 0 20 c ) a D a) a Pc <^ ( o- < c+^ ( C

120 0 0 "z 0 0' 0 0 0 CQ bff~4l:: ~~o>~~~~~~~ C C,) n.J 4-4 0 I D' )"] co w 4l I - -d M F Q P) i. i' - a e E ~ a) | -( *P+ 1 U a ) z.~ 0 0 z Ez 0 ~ as s^| w

121 each row corresponding to a state for which the queue length is two. This set of row indices is the set found by restricting the state set to the value 2 in the appropriate dimension. An operator ("set restriction") for creating such a set of n-tuples already exists (see Table 4. 4), and is readily used. A set of iteration blocks for the matrix outline corresponding to this column can be generated from the set of n-tuples using programs developed for the transition matrix translationo The operation of preparing columns of the results-matrix are correspondingly simple for every specification-type in Table 8. 1 except type 5. For this type, the flow rate through a port is to be calculated. Equivalently, the probability intensity of occurrence of a particular spontaneous event must be shown for each state of the network. Since the autoevents which can cause the spontaneous event are not obvious, the desired probability intensities are not easily found, particularly from the information in the network structureo Nevertheless, the result specified in type 5 specification is valuable, and worthy of the difficulties. What is required is a form of partial compilation of the network, exploring only those connections whose spontaneous events can cause the spontaneous event under examination. By this procedure, each autoevent of the associates of the connection are examined to find the subset of their autocondition sets which are "taken into" the forbidden states of the connection by the autoevent.

122 The intensity (Mi) of this autoevent is added to the matrix outline for the state subset so found. The exoevents of the associates are similarly examined, and whenever a nonempty subset of the endocondition set at a port is found which is "taken into" the forbidden set by the exoevent, the connection at the offending port is absorbed. The new autoevents are then examined as before, and the process repeats until no more absorptions are necessary. This process will usually involve absorption of only one or two of the connections, and can make good use of existing compiler subprograms. All the intermediate results can be kept in the working network area as the compiler does. Alternatively, the network can be compiled with the connection in question being absorbed last. The desired information is readily found in the process of the final absorption, for which a special subroutine can be written that prepares the column of I instead of actually absorbing the connection. Of course, this method is expensive since it duplicates the process of compilation. The program which prepares the results matrix continues to addon columns to the - matrix, suitably identified with the specifications. until all specifications have been treated. Thus all results are computed simultaneously when the matrix is multiplied by the equilibrium probability vector. The computation of the matrix as an intermediate result, rather than computing the results directly, will facilitate future generalization

123 of QAS whereby parameter values will be permitted to be changed without necessitating recompilation of the transition-matrix or the resultsmatrix.

9. EPILOGUE It has been necessary to describe the system in considerable detail in order to work out the critical interrelationships between the major processes and data structures. In this concluding section, a series of observations will be made about some auxiliary matters which are not central to the main interrelationships, and hence do not need to be presented in such detail. These observations represent a summary of organization concepts, notions for useful generalization, and certain reservations about unresolved theoretical questions. 9. 1 Organization We have described a system for the solution of simple stochastic networks as an amorphous collection of well-defined routines which operate upon a collection of well defined data structures. The organization of this system is expected to be imposed by the calling system (in this case SELMA), and ultimately subject to the whim of a user. Such an organizational philosophy is a natural one for a programming system designed for conversational use, and imposes a minimum constraint upon the thought sequence of the user. To implement this organizational philosophy, each routine should be designed to function in any position in a command sequence without catastrophe. The consequence of the routine's operation should be the most logical and consistent one that could be expected. In some cases 125

126 that might have to be an, error diagnostic, and a default operation. In any case, the response must be consistent with previo7(us operattons. For examample, if a "ge neration comnmand&' (altering the network) is received after a'Vcompile& command, and then a "calculate-probabilities" command is received, the most logical response to the latter is to provide the probabilities for the altered network, rather than use the results of the'"compile' (a "transition matrix",o Thus, upon altering a network, the transitiot matrix from any previous "compile" should be destroyed, and the ^9calculate-probabilities^' should either give- an error indication (non-fatal) when no transition matrix is present, or it should automat'lc ally cal the "compile" program. (If, for some reason, the user desires that the tr.ansition matrix be saved before the network is altered, he should use a'"documentation." command ) SIm.ilar pcten+ial inco.nsister:.cles occur in the alteration of results speciff'catio'l^. _ t.he ca:lcullationr of resultts, and the.use of state mapping structure and state probabilitieso All of these confllicts can be resolved by.nr.s isting tha~t the information an all. areas be applicable, at all times, to the current network and results specEificatiJor:.. and automat.ca.lly cleariing such areas whenever an incons.stency arises, If this is done, no control over the order of commands will be required of SELMA by QASo (SELMA may, however, impose such control itselfo ) For convenience, the com mands, and their associated phases and

127 areas are listed in Table, 9. 1. In the column marked "areas cleared," areas in parentheses are those automatically cleared because of induced inconsistencyo 90 2 Documentation Documentation phase commands will provide the ability of a user to save any network structure, transition matrix-state mapping, results specification, or results as a named file, and to restore them to QAS for resumption of analysis. This documentation must be done in such a way that QAS can, at a later time, be restored to an operating condition with the saved network, Moreover, the file will have to contain sufficient information to restore the displays of SELMA, via dataphone, since the PDP-9 has no facility for long-term saving of display fileso 9o 3 Deferred Evaluation of Parameters One of the most crucial improvements which this system requires is a provision which permits compilation of networks and results specification with parameters in the elements9 parameter lists treated as variables, With such a provision, the operation of compilation will be expanded into three operations: compilation, evaluation, and calculationO The first operation compiles the network, preserving an arithmetic description of how each parameter-dependent constant can be found, The second operation uses the arithmetic descriptions to place the parameter

128 -., id1., Z.1 ~ 1 cr4-4I I,, k j;.,' %*' 1' I, i I. * [ T- -! |^ ei. x U I; r P'.< ri 9 ~,,; z.P, u! | En~~ *r9i 5, q ); e^ q i, _; _ -:, ILI <u 3 U i l Q i 1 U; G I 1 | I 0 IW J i CW N I | g i i: I W, - &,,II Sh_ }a 4 SS SI I... g;!!' I I i 0 o ki V Si "''^": f ^ ^'*'*>.''** *+^~:. ^' I a? ^ re u i' h;;' as' I * S~~~~~~~~~~~~~~~~~~-~c i- I l.^ll~ i n;.^ i? "ii: i | ~ l~~~~~g"! |~ id r-.-i l FI i: - ^ ~!1 0 i, Q, U P< *; 0 (^I;

129 dependent constants in the appropriate locations of the transition matrix structure. Then, when a user is exploring a single model with many values of the parameters, the compilation is performed only once and the evaluation (and calculations) are performed for each set of parameter values. With anticipated modes of use, based upon current usage of RQA-1 which has a similar feature, this will reduce the number of compilations required by an order of magnitude or more. Since compilation is an extensive operation, this is an important economic improvement, and will also provide a dramatic improvement of response time. Indications are that compile time will not be dramatically increased by implementing this capability, and that evaluation can take considerably less time than compilation. An experimental prototype of one system for accomplishing this was developed [8] for use on the IBM 7090 and demonstrated feasibility.

RE FERENCES 1. Wallace, V. L. and R, S. Rosenberg, RQA-1, The Recursive Queue Analyzer, Technical Report 2, Systems Engineering Laboratory, Department of Electrical Engineering, University of Michigan, Ann Arbor, February 1966. 2. Wallace, V. L. and R. S. Rosenberg, "Markovian Models and Numerical Analysis of Computer System Behavior," Proc. IFIPS Spring Joint Computer Conference, vol. 28, 1966, ppo 141-148. 3o Jackson, J. Ho, "Matrix Storage Scheme Suitable for System 360," Memo to 07449 File, Systems Engineering Laboratory, University of Michigan, Ann Arbor, December 3, 1965. 4. MTS, Michigan Terminal System, Computing Center, University of Michigan, Second Edition, December 1, 1967o 5. Newman, W. M., The ASP-7 Ring Structure Processor, Computer Technology Group Report 67/8, Imperial College, London, October 1967. S, Wallace, VO L., "Preliminary Description of a Free Core Manager, " Memo to 07842 File, Systems Engineering Laboratory, University of Michigan, Ann Arbor, November 9, 1967. 7. Sutherland, W. R., The On-Line Graphical Specifications of Computer Procedures, Lincoln Laboratory Technical Report 405, M.o I To, Lexington, Massachusetts, May 1966. (Appendix C, "The CORAL Language and Data Structure"). 8. Jackson, J. H,, "Internal Structure of the IBM 7090 Experimental Version of the Deferred Evaluation System ((DES-0), " Memo to 07842 File, Systems Engineering Laboratory, The University of Michigan, Ann Arbor, September 15, 1966. 90 Randall, L, S., I, S. Uppal, Go Ao McClain, Jo Fo Blinn, An Implementation of the Queue Analyzer System (QAS) on the IBM 360/67, Systems Engineering Laboratory Technical Report 43, Department of Electrical Engineering, University of Michigan, Ann Arbor, 1969. Concomp Project Technical Report 22, Computing Center, University of Michigan, Ann Arbor, 1969. 131

132 10. Wallace, V. L., On the Representation of Markovian Systems by Network Models, Systems Engineering Laboratory Technical Report 42, Department of Electrical Engineering, University of Michigan, Ann Arbor, 1969; also Concomp Project Technical Report 21, Computing Center, University of Michigan, Ann Arbor, 1969. 11o Jackson, Jo H., SELMA: A Conversational System for Graphical Specification of Markovian Queueing Networks, Systems Engineering Laboratory Technical Report 45, Department of Electrical Engineering, University of Michigan, Ann Arbor, 1969; also Concomp Technical Report 23, Computing Center, University of Michigan, Ann Arbor, 1969.

APPENDIX A Preliminary Description of a Free-Core Manager This is a brief proposal for a programming system which gives and collects blocks of free core during execution of list-manipulating programs. It is assumed here that three properties are required by the programs which use this system: 1. Blocks of core in use must be format free. In other words, there may be no reserved words or bits in blocks which are in use. 2. Blocks of arbitrary size may be requested or released, but certain sizes will be much more frequently used than others. 3o No relocation is possible for a block once it is put to use. This proposed system is believed to be a satisfactory compromise between time, storage efficiency, and programming effort under the above circumstances. The area in which the blocks are to be allocated will be considered a large, named vector. Thus, if there is reason to segregate blocks for economic or other reasons to different parts. of virtual memory, it is possible to exert such control, (For example. different parts of the list structures to be generated may be in use at different times, and it may be uneconomical to keep them all in virtual memory at once, ) 133

134 The first n words of each area should represent some number of categories (say eight). Half of each of these words will be pointers to a member of the category or back to itself if there are no members. That is, they each form the head of a ring. The other half word indicates the number of members in the ring. The members of the categories are blocks of free memory in a particular range of sizes. (Usually, most categories will consist of a single commonly used size, with one category being a "miscellaneous" category.) These free memory blocks will have the format shown in Figure A 1. Notice that one-word "blocks" have a special format. For this reason, it is necessary that one-word blocks always be in the first category. There should be at least three calls to the manager system ALLOC (AREA, SIZE) GET (SIZE, AREA, ERROR) FREE (LOC, SIZE, ERROR) Their functions will be as follows: ALLOC (AREA, SIZE) Here "AREA" is the name of the vector of length SIZE which is to be used by the manager as its working region. SIZE must be less than or equal to the dimension declared (elsewhere, in the using program) for the vector. ALLOC may be used as often as desired, setting up as many regions as necessary. ALLOC sets up the category heads in the vector suitably linked so that all categories are empty except "misc" which contains one large free block representing the

135 rest of the vector. Of course, ALLOC also puts the right head and tail words on this free block. GET (SIZE, AREA, ERROR) GET is a function which locates a free block of the specified size in the specified area. It has value equal to the address of the first word in the located block. If a block of the exact size is not available, GET splits a larger block. If no larger block is available a return is made to the specified error statement label. The second and third arguments are optional with default values "same as last specified in an ALLOC, GET or FREE call", and "system return", respectively. The procedure for GET is charted in Figure A2. The operations marked with an asterisk (*) are adjustable procedures which can be controlled so that the sizes of remainders after splits have a distribution close to that of expected requests. They should be under some control of the user, as also the choice of sizes in each category (which is made by a procedure in the FREE subroutine) FREE (LOC, SIZE, ERROR) FREE is a subroutine which places a block back into an appropriate category of free core. LOC is the address of the first word of the block to be released, SIZE is its size (an integer), and ERROR is the statement label to which return is made when the entire block is not contained in a current working regiono The latter argument is optional, with default value "system return".

136 In order to avoid splintering of free core, which would result after a long sequence of GET's and FREE's,. FREE joins the block being released to its neighbors if they are also free. The chart of Figure A 3 shows how this is accomplished. The symbols "F1(...) " and "F2(... )" represent the left half word and the right half word of. o, respectively. The operation marked with an asterisk (*) has a portion, loosely under user control, which decides which size blocks to put in which categories. It is through the "*" programs that the assignment strategies can be adjusted to minimize unnecessary splintering by taking account of statistical conditions of the user's list structure. For example, use of categories should be with approximately equal probabilities, and splits of large blocks.to assign smaller ones should generally produce remainder blocks of a size which is likely to be needed.

137 FI F2 il F2 MEMBER OF I SIZ I B- CATEGORY I I iSIZE -'I HEAD OF "CATEGORY FREE BLOCK JsIZE. i MEMBER OF CATEGORY ONE WORD FREE BLOCK Figure Al Free Block Formats

138 GET ENTRY FIND * APPROPRIATE CATEGORY LOOK IN FOUND CAF —gR RE F NOT FOUND PICK NEW SIZE RANGE 8 CATEGORY iUFOUND / LOOK IN FREE CATEGORY EXCESS NOT FOUND EXHAUSTED LOOP THRU (RETURN) vERR RETURN ALL CATEGORIES LARGER THAN DESIRED / LOOK IN _ CATEGORY /FOUND NOT FOUND Figure A 2 Flow Chart for GET Function

139 FREE (L,Z) ENTRY LET X L+Z+FI(L+Z) FOUND 0 LET Z=Z+FI(L+Z) FI()I (XYES SEARCH CATEGORY I NOT I ___________ ^^RING FOR L+Z FOUND - rFOUND/ SEARCH CATEGORY YS A PTR TO'A 2RING FOR CATEGORY L-FI(L-I) EAD? FOUND 1 LET 5 L- f l ( L- I ) <(LS L EARCH CATEGORY UIw L=L-F,(L-1) <-I)= I RING FOR L- I ~i m ~ FOUND (i2n @: LET SET HEAD AND TAIL,AND INSERT - IN APPROPRIATE 2 CARETURN Figure A3 Flow Chart for FREE Subroutine

UNCLASSIFIED Security Classification DOCUMENT CCNTRCL DATA - R & D (Securitv classifiration of titles body o.',,: r t.,'r: ir- k e.'..:,,..c*.j.'. r.:v a r.:O r.....:-...: ovcral! re:orr; cas's.','. 1. ORIGINATING ACTIVITY (Corporate author).?-~;< SEClRiTY CLASS FICAT ON THE UNIVERSITY OF MICHIGAN Unclass CONCOMP PROJECT. GROUP 13. REPORT TITLE A SYSTEM FOR THE SOLUTION OF SIMPLE STOCHASTIC NETWORKS D4. DESCRIPTIVE NOTES l'Tp' of repor:,rnd inciusive dates) Technical Report 14 5. AUTHOR(S) (First name, middle initial, last name) KEKI B. IRANI and VICTOR L. WALLACE 6. REPORT DATE -.. ToTAL.,iO. OF PA'GES.... NC. OF REFS September 1969, 139 I 11 Ba. CONTRACT OR GRF.NT NC. Oa. ORIGINATOR'S REPORT NUMBER(S) DA-49-083 OSA 3050 Technical Report 14 b. PROJECT NO.! 99b. OTHER REPORT NO(S) (Any other numbers that may be assigned c. this report) |isi | jSEL Technical Report 31 d. _.......... E 10. DISTRIBUTION STATEMENT Qualified requesters may obtain copies of this report from DDC..!'i 1. S'. - rEMN'...!T'-RY NOZES'2. SPONSOR)NG MILITARY ACT:V'TY Advanced Research Projects Agency 13. ABSTRACT This report details the data and program structures for a conversational programming system which translates commands describing a Markovian queueing network into a matrix of transition intensities, and which provides equilibrium distributions and related solutions of the network according to requested specifications DD ORv 1473 UNCLASSIFIED Security Classification

UNCLASSIFIED Security Classification 14. LINK A LINK B_ LINK C ________KEY WORDS__ ROLE WT ROLE WT ROLE WT data structures Markovian queueing networks networks mathematical modeling UNCLASSIFIED Security Classification