Selma(ID:7041/sel012)
Markov network analysis system
- Country: us
- Began: 1969
- Type:Markovs
- Sammet:SPC
for Systems Engineering Laboratory's Markovian Analyzer
Related languages
CORAL |
=> |
Selma | |
Incorporated some features of |
References:
Wallace, V.L. and R.S. Rosenberg, "Markovian Models and Numerical Analysis of Computer System Behavior" pp141-148 view details
in [AFIPS] Proceedings of the 1966 Spring Joint Computer Conference SJCC 28 view details
Irani, Keki B. and Victor L. Wallace "A System For The Solution Of Simple Stochastic Networks" University of Michigan, Ann Arbor, MI 1969
view details
Extract: INTRODUCTION 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 use. The problem descriptions will be constructed in network diagram form on a re mote 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 solutions. It is the purpose of this report to generally specify the central 360/67 programs and data structures which accomplish this latter feat. These programs will be referred to here as the Queue Analyzer System (QAS). 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 Wallace and Rosenberg (1966).
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 required. This translator, called the network compiler, is the central, and most difficult, operation carried out by this system.
In addition, there are four other major operations which the system must perform. It must gnenerate the network description, which is the input to the compiler, from information contained in commands supplied by the console. 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 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 operations. 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 terminology). It will send its responses to the remote computer as an output file (*SINK*). 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 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 net works consisting wholly of queues, 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.
Extract: The Basic Compilation and Calculation Philosophy 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 calleci states. If the set of states is mapped by a one-one function h onto a set of integers {0, 1, ..., Ns}, and if the equilibrium probability of the state mapped to the integer k is represented by ðk, then the vector ð = < ð0, ð1, ..., ðNs> of these probabilities is a solution of the equation ðU= 0 ( [ Equation No. ] 2.1) where U is a matrix of transition intensities descriptive of the Markov chain. An efficient procedure 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 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 ð 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 E of elements and a set C of connections. N = ( [ Equation No. ] 2.2)
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 network9 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, ..., Ns}. 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 must 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
(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, etc. The sum total of all these commands defines the network. 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). 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 desired results are being specified (phase 5), 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 file.
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 2.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 arrived. Thus, QAS operates asynchronously with SELMA, lagging be hind it more or less depending upon 360 scheduling, rate of SE:LMA 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.
Extract: The Generate Program 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 sophisticated.
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 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 area9 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 command, 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.
Generation Routine Name | Input Arguments | Operations Performed | Error Conditions |
---|
Create Element | Element Name, element type, generation parameter list. | Create element block and associated structure, and joins to network block. Places name into symbol table. | Failure to specify sufficient generation parameters | Connect | Connection type, generation parameter list element name, port number, etc. | creates connection block and associated structure, joins it to designated ports. | Failure to specify sufficient generation parameters. Attempt to connect to already connected port. No such port. | Assign Parameter Values | Element or connection name, parameter list. | Merges new parameters with parameter list block (). | None | Disconnect | Element name, port number. | Destroys connection block and associated structure for connection joined to designate port. Replaces ports on unconnected port set R. | None | Destroy Element | Element name | undoes "create element" | Failure to previously disconnect all ports of element. | Alter generate parameter | Element name, parameter number. | Changes generation parameter, regenerates associated structure of element preserving existing values and joinings. | None | Table 3.2 generation Routines -- Summary
|
---|
Extract: SELMA Implementation SELMA Implementation
During this reporting period nearly all programming effort on the 339 remote console has been directed toward SELMA, a collection of programs which operates in conjunction with QAS in the IBM 360/67. The organization of SELMA may best be described by partitioning it into three sets of programs:
(1) The set of graphics programs which are initiated by display interrupts. (2) The set programs which interpret the keyboard. (3) The set of programs which communicate with QAS via the dataphone.
Throughout the time that SELMA is being executed, the keyboard interpreter programs and QAS communication programs are running in a multiprogramming fashion. Whenever a display interrupt occurs, one of the short programs which service display interrupts is begun. Unlike the keyboard interpreter programs and QAS communication programs, a program initiated by a display interrupt terminates after a short time.
Whenever the data set is not connected to another party, the QAS communication programs reroute all command output to the teleprinter, and enable a keyboard command which permits simulated QAS input on the keyboard. Since all graphical support for SELMA is provided from within the 339, this feature permits complete debugging and/or demonstration of SELMA while the IBM 360/67 is not avialable.
The operation of SELMA may be described with the aid of Figures 1-24. When SELMA is begun, the title and light buttons shown in Figure 1 are placed on the screen. Whenever these light buttons are present, SELMA is said to be in the "construction state," since a queueing network diagram may be constructed or modified in this state. The other two states of SELMA are the "documentation state" and the "results state." These two states are entered via the light buttons DOCUMENT and RESULTS. The documentation state, which has not yet been implemented, will provide for the saving and retrieval of data generated by QAS during the various stages of the solution process. The results state presently provides for the plotting and typing of results, as indicated by its light buttons, which are shown in Figure 2. The TRANSLATE light button provides for the movement of the "75*75" "paper" under the screen so that large diagrams may be drawn. A reference to the QUEUE, SERVER, SOURCE, or EXIT light button will produce a tracking cross, together with a copy of the symbol for the appropriate element. The symbol may be positioned by moving the light pen to the desired position. (This "menu" of element symbols is table driven so that dynamic augmentation may be easily implemented, if a decision to do so is made in the future.)
The construction of a model has been begun in Figure 3. The diagram shows an infinite source connected to an exponential server, and a connection in process from the server to a queue. In Figure 4, the connection has been completed by the light pen "seeing" the input port of the queue. Constraints within SELMA align the queue with the server to keep the diagram neat. A set of connected elements such as the one shown in Figure 4 is called a "fragment" and it may be moved as a unit by pointing to any element symbol within it and moving that element to the desired position. A symbol which belongs to a non- trivial fragment (i.e., one which contains more than one symbol) may not be deleted -- it must be disconnected from the fragment first. A symbol which is in a trivial fragment is deleted by stroking vertically across it with the light pen, and it is moved by pointing to it and making a deliberate motion to the desired position with the light pen. A connection is deleted by stroking vertically across it.
In Figure 5, an exit has been created, and a connection between the server and the queue has been converted from a simple connection to a priority branch, the low priority branch of which is shown being connected to the exit. (The conversion of the simple connection to the priority branch was accomplished by a special motion about the simple connection.) In Figure 6, the completed priority branch connection is shown. (At this point, the infinite source, server, priority branch, and exit constitute a Poisson arrival process.) Figures 7, 8, 9, and 10 show steps needed to complete the network diagram. (The other branch shown is a ransom branch.)
In Figures 11 and 12, parameter values are assigned to the network diagram. Each parameter value is typed on the keyboard, and then the appropriate unassigned parameter designator (dot) or parameter value to be replaced is referenced with the light pen. (Parameters associated with queues are maximum queue lengths, those associated with servers are mean service rates, and those associated with the random branch are probabilities.)
In Figure 13, SELMA has been placed in the results state. If the light pen is pointed at a symbol for either an element or connection, the name assigned to that element or connection appears. In Figure 13, the queue of maximum length 3 is identified as element 5 in this manner.
Requests for results (plots or typed tables of probability vs. state) are generated by pointing to either the PLOT or the TYPE light button (PLOT has been referenced in Figure 14), and then to either the ENTIRE MODEL or ONE ELEMENT light button (ONE ELEMENT has been referenced in Figure 15). If ENTIRE MODEL was referenced, display activity is disabled until a plot can be received or until the PLOT, TYPE, ENTIRE MODEL, and ONE ELEMENT light buttons are restored, depending on the type of request. Otherwise, the light pen must be pointed at the element symbol for which results are to be obtained before this action is taken.
Figure 16 shows the plot obtained for the queue of length 8, Figure 17 shows the plot obtained for the queue of length 3, and Figure 18 shows the plot obtained for the server which follows the queue of length 3. (Labels and units will be added to these plots by modifications to SELMA and QAS in the near future.) Figure 19 shows typed tables for these elements and for the servers connected to the top and bottom branches of the random branch, respectively.
After a particular model has been solved, it may be modified or destroyed via a keyboard command. Figures 20-24 show the major steps required to modify the model by removing the top branch of the random branch and leaving all other conditions the same. (The ratio of probabilities in the bottom two branches is the same before and after the change. The sum of all probabilities assigned to a random branch must be unity.)
in [AFIPS] Proceedings of the 1966 Spring Joint Computer Conference SJCC 28 view details
Jackson, J.H., "SELMA: A Conversational System for Graphical Specification of Markovian Queueing Networks" Concomp Technical Report 23, Computing Center, University of Michigan, Ann Arbor, 1969. view details
Abstract: This report discusses the design and use of the Systems Engineering Laboratory's Markovian Analyzer (SELMA) system for a DEC 339 computer display terminal. This system provides interactive graphics support for a program which was developed concurrently for the IBM 360/67 to analyze a class of Markovian queueing networks. Special features of the system include handling of all graphic operations at the terminal and recognition of patterns of motion of the light pen to provide a human-oriented drawing capability.
Extract: Introduction Introduction This report discusses the design and use of the Systems Engineering Laboratory's Markovian Analyzer (SELMA) system for a DEC 339 computer display terminal. The purpose of this system is to provide interactive graphic support for the QAS program L2 ] , which was developed concurrently for the IBM 360/67 to analyze a class of Markovian queueing models. SELMA consists of a set of user tasks which are executed in a multiprogrammed fashion under the control of the SEL Executive System
A simplified representation of the tasks which comprise SELMA is shown in Figure 1. Each task is represented by a rectangle, whereas each of the major display structures is represented by a circle. Each directed path on the diagram represents a flow of information from one unit to another.
Whenever SELMA is operating, both the command exchanger task and the keyboard interpreter task are continuously executed. The function of the command exchanger is to communicate with the QAS program in the IBM 360/67 via a 201A dataphone. Because the bandwidth of this dataphone is somewhat limited (2000 bits/sec), all graphic operations are performed locally in the display terminal, and all data sent to QAS or received from (?AS are formatted into blocks called commands. Each command represents a macroscopic operation, such as creating or destroying an element, and it contains only the required control information, rather than an excessive amount of graphic information. The basic function of the keyboard interpreter is to provide a direct path between the user and the command exchanger for certain relatively infrequent operations such as destroying the current model or terminating execution.
The other tasks which are shown in Figure 1 are scheduled for execution in response to user inputs. The TYPE and PLOT tasks are scheduled in response to references to light buttons whose function is to request results from QAS. These tasks do not modify the diagram of the current model; they merely instruct the command exchanger to send appropriate commands to QAS. The CREATE task is scheduled in response to a reference to any one of several light buttons, each of which is used to create an element of a particular type. This task must both give the command exchanger information to send to QAS and modify the diagram to include the symbol for the created element. The other functions which are required in order to draw the network are handled by the light pen interpreter task. This task is scheduled in response to a reference to any part of the diagram with the light pen. The function which it performs is determined by the part of the diagram which is referenced, and, in many cases, by recognition of subsequent patterns of light pen motion. This recognition of patterns of light pen motion allows the user to express his intentions in a human-oriented fashion, and it eliminates the need to clutter the screen with other light buttons or to sequence through a large set of light button menus. The TRANSLATE task and the push button interpreter task are used to modify the behavior of the light pen interpreter. The TRANSLATE task, which is invoked by a light button, modifies the behavior of the light pen interpreter so that the entire 75"x 75" "paper" on which the diagram is drawn may be moved under the display screen. In this way, a diagram which is larger then the display screen may be drawn. The push button interpreter accepts numerical parameter values from the push buttons and modifies the behavior of the light pen interpreter so that these values may be assigned at various attachment points on the diagram.
In the sections which follow, usage of the system, as well as the operations performed by the various tasks, is described. In Section 2, usage of the system is described, together with the operation of the light pen interpreter. The command exchanger is described in detail in Section 3, and, in Section 4, the display structure which is interrogated in order to form many of the commands which are sent to QAS is described. In Section 5, a feature of the command exchanger which should be useful while implementing future modifications of SELMA and/or QAS is described, and some forseeable modifications are discussed in Section 6. A listing of SELMA is supplied as an appendix.
Extract: Usage of SELMA and QAS Usage of SELMA and QAS
Whenever SELMA is to be used in conjunction with QAS, the command to run QAS must be given to the central time-sharing system before SELMA is started. This restriction is necessary because the SELMA command exchanger contains no provision for communicating with the command language interpreter of the time-sharing system. SELMA may then be started by scheduling and running the single task at the location whose address appears on the SELMA binary tape. (This address is not specified here because it is subject to change without notice.)
Just after SELMA is started, the light buttons shown in Figure 2a appear on the screen. When these light buttons are present, SELMA is said to be in the construction phase, and the light pen interpreter is adjusted so that a diagram of a queueing model may be drawn or modified. The other two phases indicated in Figure 2 are the results phase (Figure 2b) and the plot phase (Figure 2c). The results phase allows the user to request results, whereas the plot phase displays a graph of the last requested result and allows the user to expand sections of the graph and to request labels for points of interest on the graph.
Transitions between SELMA phases are depicted by Figure 3. In this figure, each phase is represented by a circle, and the light buttons which produce transitions between phases are indicated by labels on directed paths between phases.
element that so with appears cross tracking A type. its denotes which 2a) (Figure screen of corner right-hand upper in button light selecting by created is An created. must one least at performed, can construction steps other Before model. new a begin user'started it when phase placed >SELMA>The various elements which may be created are shown in Figure 4. The interpretation of each of these elements has been described previously
. Each element symbol includes one or more ports, i. e., attachment points for connections to other elements. In addition, an element symbol may have a body and one or more numerical parameters. Since no value is assumed for the parameter of an element when the element is created, the position of each parameter in a newly created symbol is indicated by a dot, called a parameter dot.
The creation of new symbols is the only operation required for the construction of a model which requires the use of light buttons. All other operations are performed with the aid of the light pen interpreter. As mentioned in the introduction, the action to be taken by the light pen interpreter is determined from the part of the diagram which is referenced and often from a recognition of subsequent patterns of motion of the light pen. The part of the diagram which is referenced is easily determined from the display structure (Section 4) through the use of subroutines available in the executive system. However, since the executive system provides no facility for recognizing patterns of light pen motion, this latter determination is made completely within SELMA.
The method employed by SELMA to recognize patterns of light pen motion may be described with the aid of Figure 5. Whenever a light pen reference is made to a part of the diagram which requires that subsequent patterns of motion of the light pen be recognized, tracking is started at the coordinates of the light pen, and one or more threshold patterns, i. e., patterns of imaginary lines of the form shown in Figure 5, are placed on the screen. The number of patterns and the coordinates and size of each pattern are determined by the part of the diagram which is referenced. ( The size of each pattern is specified by a parameter d. )
Whenever an element symbol is referenced with the light pen while SELMA is in the construction phase (and the light pen interpreter has not been modified by the TRANSLATE task or the push button interpreter), two threshold patterns are placed at the coordinates of the symbol as shown in Figure 6a, and a tracking cross is placed at the coordinates of the light pen. If the symbol has connected ports, the fragment of the diagram which consists of this symbol and all connections and symbols associated with it are moved with the tracking cross. Otherwise, the symbol may be either moved or deleted, depending on subsequent motion of the light pen. In Figure 6a, the significant regions of the screen which are bounded by the lines of the threshold pattern and/or the edge of the screen are labeled A, B, or M. The decision to delete or move the symbol is made by recognizing transitions among these regions. The symbol is deleted if the pen is stroked vertically across the symbol as shown in Figure 6b. This motion is recognized as a sequence of five transitions between the A and B regions without entering an M region. The symbol is moved with the light pen if the light pen is moved into a M region. This latter motion is depicted in Figure 3c.
In the above discussion of deleting and moving symbols, a reference to a symbol with the light pen was assumed to be a reference to any part of the symbol other than an output port. When an unconnected output port is referenced on any symbol (regardless of whether or not the symbol has connected ports), the drawing of a connection line is begun as shown in Figure 7a. A threshold pattern is established at the coordinates of the output port. The connection line is continuously updated as shown until the light pen is moved into either a U or D region, at which time a new vertical segment is added to the connection line (Figure 7b). A smaller threshold pattern is then established at the coordinates of the output port. The original threshold pattern is moved to the newly created corner of the connection line. If the light pen is now moved into the E region, the vertical segment of the connection line is deleted, the smaller threshold pattern is deleted, the larger threshold pattern is moved to the coordinates of the output port, and action proceeds again as depicted in Figure 7a. If the light pen is moved into an L or R region, a second horizontal segment is added to the connection line as shown in Figure 7c. The small threshold pattern is moved to the next to last corner, and the larger threshold pattern is moved to the newly created corner. Again, if the light pen is moved into the E region, the last segment of the connection line is deleted and action proceeds according to Figure 7b. If the light pen is moved into a U or D region, a second vertical segment is added to the connection line. The operation proceeds in this manner until the drawing of the connection line is terminated by either of the following events: 1. The connection line is deleted by loss of tracking, 2. The connection line is used to form or modify a connection.
Connection lines may be used to form the following five types of connections: 1. Simple connection, 2. Random branch, 3. Priority branch, 4. Random merge, and 5. Priority merge. The first of these, the simple connection, associates an output port of an element with an input port of either the same or another element. An item flows from the output port through the connection to the input port whenever an item is available at the output port and the input port can accept it. A branch associates one output port with several input ports. Whenever an item is available at the output port and at least one input port can accept it, it flows through the branch to one of the input ports which can accept it. If the branch is a random branch, no input port can accept the item unless all input ports associated with the branch can accept it. Whenever all of these ports can accept the item, one of them is selected randomly in accordance with probabilities assigned to each of them. If the branch is a priority branch, an available item flows through the branch if any input port can accept it, and priorities assigned to the input ports determine which port receives the item. A merge associates several output ports with one input port. Whenever the input port can accept an item and an item becomes available at at least one output port, one of the available items flows through the merge to the input port. If the merge is a random merge, an item is not available at an output port unless items are available at all output ports which are associated with the branch. Whenever an item is available at all of these output ports and the input port can accept an item, one of the available items is selected randomly in accordance with probabilities assigned to each output port. If the merge is a priority merge, an available item flows through the merge if the input port can accept it, and priorities assigned to each output port determine which item is selected.
For both branches and merges, selection of ports on the basis of probability is indicated in a SELMA diagram by a dot (. ), and selection of ports on the basis of priority is indicated by a diamond ( <> ) . Some examples of branches and merges which are drawn with these symbols are shown in Figure 8. (The arrowheads on each branch are actually connected input ports, which differ in appearance from unconnected input ports. ) In Figure 8a, whenever the server has finished servicing an item and neither of the queues is full, the item from the server is placed in the top queue with probability 0.3 or in the bottom queue with probability 0.7. The server in Figure 8b cannot hold an item after it has been serviced, for there is always an input port which can accept it. If the top queue is not full and the server finishes servicing an item, the item is placed in the top queue. Otherwise, if the top queue is full and the bottom queue is not, the item is placed in the bottom queue. If both queues are full, the item leaves the system through the sink. In Figure 8c, whenever the server is empty and no queue is empty, an item is placed in the server from the top queue with probability 0.2, from the middle queue with probability 0.5, or from the bottom queue with probability 0.3. Whenever the right-hand queue in Figure 8d is not full, an item is placed in it from the bottom left-hand queue if the bottom left-hand queue is not empty, or from the top left-hand queue if this queue is not empty and the bottom left-hand queue is empty.
All connections which are drawn with SELMA are originally generated as simple connections, which later may be extended to form branches or merges. A simple connection is drawn by starting a connection line at an unconnected output port and terminating it at an unconnected input port by passing the light pen over the input port while drawing the connection line. SELMA will then stop tracking the light pen and will convert the connection line to a simple connection.
Whenever a simple connection is to be converted to a branch, the type of branch (i. e., random or priority) must be established. This is accomplished by recognizing a pattern of light pen motion. In addition, a simple connection may be deleted by stroking vertically across it in the same manner that one would use to delete an element symbol. The threshold patterns which are involved are shown in Figure 9. When the light pen is aimed at a connection, a dot appears on the connection at the coordinates at which the light pen was detected. If the connection is a simple connection and the light pen is then moved into an M region without entering a W, an X, a Y, and a Z region or moving back and forth five times between A and B regions, a connection line is started at this point, and the dot remains to indicate that the connection is to be converted to a random branch. The conversion is performed when the connection line is completed by passing the pen over an unconnected input port. This operation is shown in Figure 10a. If the light pen enters a W, an X, a Y, and a Z region without entering an M region or moving back and forth five times between A and B regions, the dot is converted to a diamond to indicate that the connection is to be converted to a priority branch. When the light pen is subsequently moved into an M region, a connection line is started in the center of the diamond. This operation is indicated in Figure 10b. If the light pen is moved back and forth five times between A and B regions without entering an M region or a W, an X, a Y, and a Z region, the connection is deleted. This action for deleting simple connections is the same as that for deleting symbols, and it applies to branches and merges as well.
A merge, like a branch, is also formed by adding a connection line to a simple connection. However, the connection line to be added is drawn from an output port to the simple connection, rather than from the simple connection to an input port. The type of merge (i. e., random or priority) is determined by recognizing light pen motion as the connection line is terminated. The thresholds involved in this operation are shown in Figure 11. If the light pen enters the W, X, Y, and Z regions without entering an M region, tracking of the light pen is terminated by SELMA, and a priority merge is formed. If the user removes the light pen near the simple connection without entering an M region, a random merge is formed. These operations are shown in Figure 12. If the light pen is moved into an M region, the threshold pattern is removed, and drawing of the connection line continues as through no simple connection had been encountered.
Once a branch or a merge is formed, more element ports may be associated with it by drawing additional connection lines. A connection line to be added to a branch is drawn from the branch to an input port, whereas a connection line to be added to a merge is drawn from an output port to the merge. No threshold pattern is required to determine whether a dot or diamond is to be placed at the intersection of the new connection line with the branch or merge, since the type of branch or merge is already established.
The values of the probabilities and priorities which are associated with branches and merges, as well as the values of the parameters which are associated with certain symbols, are assigned through the use of push buttons. Push buttons 0 through 9 represent the decimal digits 0 through 9, respectively. Push button 10 represents a decimal point, and push button 11 is used to delete erroneous parameter values. A parameter value is specified by supplying a sequence of from one to four characters. The value is displayed in the lower right-hand corner of the screen as it is inputted, and the light pen interpreter is modified so that all parameter dots and parameter values, but no other parts of the diagram, are sensitive to the light pen. If the light pen is now aimed at a parameter dot or parameter value, the parameter dot or parameter value is replaced with the new parameter value which was obtained from the push buttons, and the light pen interpreter is restored to its original state.
Two modes of parameter values may be assigned: integer and real. The function of each parameter value in the diagram determines its mode, e. g., a queue length must be an integer, a probability must be a real parameter, etc. SELMA refuses to accept a parameter value of the wrong mode.
Occasionally, a model will be so complex that its diagram will not fit onto the display screen. For this reason, the diagram is considered to be drawn on a 75"x 75" piece of "paper" which may be moved to various positions under the screen. The TRANSLATE light button is provided in the lower left-hand corner of the screen in the construction phase to provide this function. When this light button is referenced with the light pen, the light pen interpreter is put into a translate mode, and the TRANSLATE light button is modified to indicate this fact. A subsequent reference to this light button will restore the light pen interpreter and the TRANSLATE light button to their original states. (The creation of a new element will also produce this effect. ) When the light pen interpreter is in the translate mode, a subsequent reference I to a point on the diagram causes tracking to be started and the corresponding point on the "paper" to be affixed to the tracking cross. The "paper" may then be moved by moving the light pen.
When a diagram is thought to be complete, SELMA may be put into the results phase (Figure 2b) via a reference to the RESULTS light button. When SELMA is in this phase, the user may request a steady-state probability density function either for any single element I or for the entire model. The light pen interpreter is modified when this phase is entered so that the only function which can be performed I by referencing the diagram without further modifying the light pen interpreter (via the TRANSLATE light button or by assignment of parameter values) is the identification of elements.
When a density function is to be requested for a particular element, that element may be identified by referencing it with the light pen. A box of dotted lines is placed around the element and a one-character alphabetic name is assigned to the element as shown in Figure 13. If a different element is subsequently selected before the result request is completed by referencing either the PLOT or TYPE light button (described below), the box is moved to that element, and the name associated with the box is changed to the name of the new element. A reference to the box with the light pen will remove it from the diagram. When no box appears around any element, the entire model, rather than any particular element, is identified.
The probability density function for the item (i. e., either the entire model or a particular element) identified in this manner may be obtained in either of two forms: (1) as a histogram on the display screen, or (2) as a table on the teletype. A histogram is obtained through a reference to the PLOT light button, and a typed table is obtained through a reference to the TYPE light button.
When a result is requested, it will not be returned if the diagram is not complete or if contradictory parameter values exist. The diagram is not complete under either of the following conditions: (1) At least one port in the diagram is not connected, or
(2) At least one parameter dot remains on the diagram.
Contradictory parameter values exist if either of the following conditions is true: (1) Two equal priorities are assigned to one priority branch or merge, or
(2) The probabilities assigned to a random branch or merge do not sum to 1.0. If any of these four conditions is true, SELMA is forced into the construction phase, a large flashing arrow is placed on the screen to indicate the location of the error, and an appropriate comment is typed on the teletype. The flashing arrow disappears from the screen when the error is corrected. However, if the error involves contradictory parameter values, the arrow may not point to the value which the user decides to change to correct the problem. In this event, the parameter which is being indicated should be reassigned the same value to delete the arrow and thus avoid confusion on subsequent errors.
If the result which was requested was a histogram and none of the above errors is present in the diagram, SELMA enters the plot phase (Figure 2c) . The diagram is removed from the screen, and axes for the graph are displayed, together with a label for the abscissa. For the example in Figure 13, this result is shown in Figure 14b.
Only the maximum and minimum values of the abscissa and ordinate which could be represented without scaling the graph are represented on the final plot. However, the user may request numerical values from QAS for any particular bar in the histogram by pointing to that bar with the light pen. (Subsequent references to other bars will erase previous values so that only the last one is displayed. ) The result of pointing to the fourth bar in Figure 14b is shown in Figure l5a.
In addition to facility for obtaining numerical values for points on the graph, facility is also provided for looking at various sections of the graph. This facility is necessary because a maximum of 50 abscissa values may appear in one graph (limited by local storage and resolution of the display) and some results require more than 50 abscissa values to plot in their entirety. It is also a convenience, since detailed examination of a graph with a wide range of ordinate values or a large number of abscissa values is more difficult without it. Various sections of the graph may be displayed through the use of the RIGHT, LEFT, and DETAIL light buttons. If the RIGHT light button is referenced, and then the bar at a particular abscissa is referenced, the plot is modified so that that abscissa, together with all abscissas of greater value (up to a total of 50 abscissa values) is plotted. In similar manner, a plot involving an abscissa, together with all abscissas of smaller value (up to a total of 50 values) may be obtained through the use of the LEFT light button. For example, the graph obtained by applying the LEFT light button to the abscissa 2 in Figure 15a is shown in Figure 15b. The DETAIL light allows the user to specify the maximum and minimum abscissas he wishes to plot. After the DETAIL light button is referenced, these two abscissas are specified by referencing the two bars of the graph which correspond to them. For all of these operations, the fact that a particular light button has been selected is indicated by the removal of all other light buttons from the screen until the new graph is completely specified.
As indicated by the above discussion, all of the very common operations which are involved in the specification of a queueing model, with the exception of parameter value input, are performed with the light pen only. This type of operation was chosen because the user can usually generate faster input with the light pen than with any other input device. (input of parameter values with the light pen was found to be awkward, so push buttons were used for this purpose. ) However, there are some operations which are performed very infrequently, and, should they be performed accidentally, compensating for their effect would be difficult. In particular, destroying the current model in order to begin a new model, and terminating SK: LMA are such operations. These operations are performed through the use of the keyboard, which is a relatively inaccessable device to the user. In this way, accidental performance of these operations is less likely than it would be if these operations were invoked with the light pen.
All operations performed from the keyboard are initiated by commands which are invoked by a single character. The keyboard interpreter responds to each command by typing a word or phrase which is a more complete description of the command. A command may be deleted before it is effective by typing a rubout in place of any subsequent character. The command which destroys the current model in preparation for beginning a new one is the following: CLEAR? OK
(The underlined characters are those typed by the user.) Although the character "C" would be sufficient for specifying this operation, a confirmation (accomplished by typing "O") is required to help avoid accidental performance of this operation. The fact that the confirmation is required is indicated by the question mark (?) . If the user wishes not to confirm the operation, he may type "N" for "NO". Similarly, the following command, which terminates SELMA (and QAS), requires confirmation: ESCAPE ? OK
Two other keyboard commands which represent infrequent operations which cannot easily be reversed once they are performed are saving the current model on a file at the IBM 360/67 and retrieving a queueing model from a file. These two commands are the following: SAVE ON FILE ____ GET FILE _____ Each command is completed by typing a file name, or a file name followed by a space, in turn followed by the word "ALL". (The command is terminated by a carriage-return typed on the keyboard. ) In the former case, any results which have been computed are not saved, but in the latter case they are saved. The user is prevented from performing any other operations while a model is being saved or retrieved. Retrieval of a model effects a "CLEAR" command before the model is actually retrieved.
Although saving or retrieving a model is costly to perform accidentally, no provision for explicit confirmation is provided. The file name which is required to complete each command serves as a confirmation. If an illegal file name is specified, a comment to this effect will be typed, and QAS will ignore the command.
Some users have found the keyboard, rather than the push buttons, to be a more suitable device for inputting parameter values. For this reason, a command to substitute the teletype for the push buttons and a command to specify a parameter value from the keyboard are provided. The device from which parameter values are to be obtained is specified by the command
VALUES FROM | PUSH BUTTONS | TELETYPE | (The default device is the push buttons. ) While the teletype is the input device for parameter values, the following command may be given to specify a parameter value: PARAMETER: ____ This command is completed by typing a number which consists of from one to eight characters, followed by a carriage return. All of the characters are sent to QAS, but only the first four are displayed if more than four are specified. Real values are restricted to be less than or equal to 999.9999 to avoid misrepresentation of the decimal point on the display.
Two other keyboard commands are provided for purposes of debugging SELMA and/or CAS. However, these commands are not normally available to the user, since they deal with dataphone commands between SELMA and QAS. They are described in Section 5, following a detailed description of the command exchanger in Section 3 and a description of the data structure used to represent the topology of the network in Section 4.
Extract: The Command Exchanger 3. The Command Exchanger
In order to be effective, the frequently used operations described in the previous section must provide rapid response to user inputs. If all programmed operations were performed in sequence, the low data rate of the dataphone would pose a threat to this response time in that the transmission of commands to inform QAS of certain inputs might delay responses to subsequent inputs. For this reason, the response task for each user input which requires communication with QAS merely places the commands to be sent to QAS into a buffer. A separate task, the command exchanger, then reads commands from this buffer and sends them to QAS. Since the command exchanger and response tasks for user inputs are executed asynchronously, the rate of dataphone transmission does not seriously affect the rate of response to user inputs.
Since the dataphone under consideration is a half-duplex dataphone, SELMA and CAS must not transmit simultaneously. For this reason, SELMA and QAS alternately transmit records, with QAS sending the first record. Since CAS sends the first record, QAS need not be executing before SELMA is started. Since a record directed to the SELMA command exchanger is not acknowledged by the SEL executive system until the command exchanger has removed it from the dataphone input buffer, SELMA need not be executing before execution of QAS begins.
Each dataphone record which is sent from SELMA to QAS or from QAS to SELMA contains exactly one command. The general format of a command is shown in Figure 16. The command is delimited by bytes whose value is FF16, and all other bytes in the command have values less than FF16. (Although the beginning and end of the record are sufficient to delimit the command, the two delimiting bytes were included in the format to facilitate a possible future program modification to permit transmission of multiple commands per record. ) The first byte after the initial delimiter specifies the "phase" of the command, and the byte which follows it identifies the command within that phase. (The command phase is not related to the phase of SELMA. ) The combination of the phase and command bytes identifies the command, and, consequently, specifies the format of the data bytes.
The formats of the commands which are accepted by QAS are indicated by Figure 17, and the formats of the commands which are accepted by SELMA are indicated by Figure 18. The abbreviations for various groups of data bytes are interpreted as follows:
- CN
- Connection name. A number between 129 and 254 which identifies a
particular connection. (1 byte)
- CPN
- Connection port number. A number between 1 and 254 which specifies a
particular port of the connection specified by an associated connection name. (1 byte)
- CT
- Connection type. A number between 129 and 254 which specifies the type of
connection (e.g., simple - connection, random branch or merge, priority branch or merge). (1
byte)
DW Display file word. Two bytes, each of which has a value from O through 127. These two bytes are decoded to form an 18-bit word to be loaded into core by SE LMA according to the following scheme: (1) The low-order 7 bits of each byte are concatenated to form a 14-bit number. (2) The two high-order bits of the 14-bit number are placed into positions 0 and 1 of the 18-bit word, and the remaining 12 bits are placed into positions 6-17 of the 18-bit word. Positions 2 - 5 of the 18-bit word are set to zero.
EN Element name. A number between 1 and 127 which identifies a particular element. (1 byte)
EPN Element port number. A number between 1 and 254 which specifies a particular port of the element specified by an associated element name. (1 byte)
ET Element type. A number between 1 and 127 which specifies the type of element (e. g., queue, server, or source or exit). (1 byte)
FN File name. A sequence of bytes whose values are 6-bit character codes [ 3 p. 17 ] which represent a file name. (1 to 16 bytes) GPN Generation parameter number. A number between 1 and 254 which identifies a particular generation parameter (i. e., parameter which modifies an element or connection type) . ( 1 byte)
GPV Generation parameter value. A number between 1 and 254 which represents the value of a generation parameter . ( 1 byte)
IL Iteration limit. Two bytes, each of which has a value between O and 127. A number between 1 and 16, 383 which represents the maximum number of iterations which will be performed whenever a model is solved is obtained by concatenating the low-order 7 bits of the two bytes.
LET Local element type. A number between 1 and 254 which identifies a graphical symbol for an element type. This number is not necessarily the same as the corresponding element type, for several graphical symbols may be associated with one element type (e. g., source and exit represent the same element type) . ( 1 byte)
PN Parameter number. A number between 1 and 254 which identifies a parameter for an element or connection. (1 byte) PV Parameter value. A sequence of bytes whose values are 6-bit character codes which represent a non negative real or integer number. (1 to 8 bytes)
SC State count. A number between 1 and 254 which represents the number of points to be plotted on a graph by QAS. Fifty points are plotted if this number is either zero or greater than 50. (1 byte)
SN State number. A number between O and 16, 383 which represents an abscissa on a graph plotted by QAS. This number is coded in the same way that an iteration limit (IL) is coded. (2 bytes)
T Text item. A sequence of bytes, the first of which has a value which is the number of bytes which follow it, and the remainder of which are 6-bit character code s. (2 -16 byte s)
WC Word count. A number between 1 and 16, 383 which represents the size of storage block required to load a connection leaf when retrieving a model from a file. This number is coded in the same way that an iteration limit (IL) is coded. (2 bytes)
XC An abscissa between -8192 and 8191. This coordinate is coded in the same way that an iteration limit (IL) is coded. However, the 14-bit number represented is interpreted as a two's complement number, rather than as an unsigned positive number. (2 bytes)
YC An ordinate between -8192 and 8191. This number is coded in the same way an abscissa is coded. (2 bytes)
Extract: Special Command Exchanger Feature Special Command Exchanger Feature
In addition to those features described in Section 3, a special feature is included in the command exchanger to facilitate testing of future modifications to SELMA which affect the command repertoire. Whenever SELMA is started, but the dataphone is not connected to another party, the teletype is substituted for the QAS program. This is accomplished by the addition of a command to the keyboard interpreter to permit simulated input from QAS and by the routing of all command output to the teleprinter (to be typed in hexadecimal format).
The command which is added to the keyboard interpreter is of the following form: QAS: [ ____ ] The command is begun by typing the letter "Q" on the keyboard. A command is then typed (except for delimiter bytes) on the keyboard in hexadecimal notation. If a carriage return is typed instead of the command, a null command is assumed. Otherwise, an even number of hexadecimal digits must be typed, followed by the carriage return. (In all cases, the right bracket is typed in response to the carriage return. ) If a phase byte is explicitly inputted, a carriage return will be ignored until the command byte is inputted. The command may be deleted at any time before it is completed by typing a null character .
Because the command exchanger actually interprets the QAS keyboard command, commands between the user and SELMA via teletype are subject to the same restrictions that govern commands between QAS and SELMA. The first command via teletype must be inputted by the user, and only one command is typed by SELMA until the next command is inputted via keyboard. For example, assume that SELMA is started with the data set disconnected. Only after the user'supplies the command QAS: [ 0000 ] does SELMA respond by typing SELMA: [ 0005 ]
to indicate that QAS should be initialized. (The zeros in the QAS keyboard command were not underlined here because it is assumed that all null commands are inputted simply by typing a carriage return.) If the user then again inputs a null command, no response from SELMA is produced until the user performs some action which generates one or more commands. The first of these generated commands is then typed, and the others are retained until more QAS commands are inputted.
Since the only communication between SELMA and QAS is in the form of commands, the feature described above permits complete testing of new versions of SELMA without the use of the IBM 360/67. This feature of the command exchanger is intended only for this purpose, and should not be used by users who are attempting to solve queueing models.
Extract: Foreseeable Modifications 6. Foreseeable Modifications The system described in this report was designed to demonstrate the usefulness of graphical input for the specification of queueing networks to a computer. It was not intended to be a tool for the queueing analyst. However, with a few modifications, the system could serve the latter purpose as well. The elements which are available in SELMA (i.e., queue, server, source, and exit) may not be sufficient for the specification of many models. In fact, various users may disagree on what elements are sufficient. Since a universally acceptable set of elements is difficult, if not impossible, to derive, a definition capability for elements is desirable in SELMA. Since the ,"menu" of elements in SELMA is table-driven, the inclusion of this facility in SELMA would not be difficult. However, a corresponding definition facility for QAS might be difficult to implement. Another type of definition facility could allow definition of elements which would be equivalent to existing fragments. This definition facility could be supported exclusively by the display terminal, since the creation of a copy of such an element could be described to QAS by the sequence of commands required to generate the corresponding fragment. Each element defined in this way could be represented by a symbol such as one which is used to represent an element in the current version of SELMA. Much larger models than can presently be accommodated in the display terminal could then be accommodated because the detail of each fragment which represents a composite element would not have to be stored locally once the equivalent element was defined. For SELMA/ QAS to be a useful tool, results should be available in forms other than probability distributions for individual state variables. A suitable generalization of this type of result might be a conditional probability distribution for an algebraic function of state variables, where the algebraic function and the conditions which affect the distribution are specified by the user. Such distributions could be further processed by QAS to produce conditional expectations of functions of state variables.
in [AFIPS] Proceedings of the 1966 Spring Joint Computer Conference SJCC 28 view details
Jackson, J.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 view details
in [AFIPS] Proceedings of the 1966 Spring Joint Computer Conference SJCC 28 view details
Jackson, James H. "SELMA: A Conversational System for the Graphical Specification of Markovian Queueing Networks" view details
in [AFIPS] Proceedings of the 1966 Spring Joint Computer Conference SJCC 28 view details
|