THE UNIVERSITY OF MICHIGAN SYSTEMS ENGINEERING LABORATORY Department of Electrical Engineering College of Engineering SEL Technical Report No. 34 OPTIMUM DESIGN OF COMPUTER DRIVEN DISPLAY SYSTEMS by James D. Foley March 1969 V, en _ X, i; t { t 2 L i) 4 J'4I r 5 a i under contract withL under contract with: ROME AIR DEVELOPMENT CENTER Research and Technology Division Air Force Systems Command Contract No. AF 30(602)-3953 Griffiss Air Force Base, New York

O James David Foley 1969 All Rights Reserved This report was also a dissertation submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy in The University of Michigan, 1969. Reproduction in whole or in part is permitted for purposes of the United States Government. Others may quote without permission passages of up to 200 words. This work was supported by Air Force Contract AF30(602)-3953.

ACKNOWLE DGMENTS Completion of the four and one -half years of graduate studies leading up to and including this dissertation was made possible by many people. It all started with the fine undergraduate program in Electrical Engineering at Lehigh University, and the inspiration provided by Dean Karakash. Then came two years of course work here at the University of Michigan, with financial support from NSF and NASA, and more inspiration and encouragement, this time from Dean Scott. Next was a very fruitful period of working with computer graphics under Professor Herzog, who brought to my attention the problems which this dissertation attempts to solve. Now, in the Systems Engineering Laboratory, with the direction and guidance of Professor Irani, and the financial support of Rome Air Development Center, contract AF30(602)-3953, I have endeavored to bring systems analysis and optimization techniques to bear on the problem of designing graphics systems. During this period the members of my doctoral committee have been most helpful with their various constructive comments: for their continuing interest I am most grateful. This final manuscript has been typed by Miss Linda Oakley. Earlier drafts were typed by Miss Sharon Bauerle, Miss Joyce Doneth, and Mrs. Joanne Aichler.

For her continuing support, encouragement, and understanding, the efforts represented by this dissertation are dedicated to my wife. James Foley Ann Arbor, Michigan March, 1969

TO MARYLOU V

TABLE OF CONTENTS Page LIST OF TABLES ix LIST OF FIGURES xi LIST OF SYMBOLS xiv ABSTRACT xxi Chapter I INTRODUCTION 1 1. 1 Why Computer Graphics 2 1.2 Historical Development 5 1. 3 Typical Graphics Applications 7 1.4 Definitions 9 1. 5 The Hardware System 12 1.6 Tradeoffs 16 1.7 Research Objectives 19 II A MATHEMATICAL MODEL OF DISPLAY SYSTEMS 22 2. 1 Display System Model 23 2. 2 Hardware Specification 28 2. 3 Application Specification 30 2. 4 Parameter Calculation 37 2. 5 Assumptions 46 2. 6 Cost 52 2.7 Analysis 54 2. 7. 1 Assignments of Interactions 57 2. 7. 2 Monotonicity of T 59 III ANALYSIS METHODS 64 3. 1 Simulation 64 3. 2 Markov Analysis 64 3. 3 Qualitative Comparison of Simulation and Markov Analysis 66 3. 4 Quantitative Comparison of Simulation and Markov Analysis 67 vi

TABLE OF CONTENTS (Continued) Chapter Page IV OPTIMIZATION PROCEDURE 78 4. 1 Problem Formulation 78 4. 2 Optimization Algorithm 81 V EVALUATION OF COMPUTING POWER 94 5. 1 Displayable Information 95 5. 2 Computing Power-Historical Approaches 102 5. 3 Computing Power —Display Instruction Mix 105 5. 4 Final Analysis 108 VI APPLICATION 116 6. 1 Display System Hardware 117 6. 1. 1 Data Link 118 6. 1. 2 Remote Computer Core Storage 118 6. 1. 3 Remote Computer Bulk Storage 121 6. 1. 4 Remote Computer-Display Control 123 6.2 Applications 130 6. 2. 1 Text Editing 130 6.2.2 Two-Dimensional Drawing 133 6. 2. 3 Three-Dimensional Drawing 133 6. 2. 4 General Network Analysis 138 6. 3 Optimization Results 145 6. 4 Comparison of Best and Worst Display Systems 175 6. 5 Interpretation of Results 178 6. 5. 1 Cost-Effectiveness 179 6. 5.2 Multiple Versus Single Console Systems 183 6. 5. 3 Guidelines 184 6. 5. 4 Hardware Aids for Multiplication and Division 187 6. 6 Division of Processing 187 6.7 Summary 190 VII CONCLUSION 192 7. 1 Review of the Research 192 7.2 Critical Evaluation 193 REFERENCES 195 vii

TABLE OF CONTENTS (Continued) Appendix Page A THE PREPROCESSOR PROGRAM, AND ITS INPUT DATA 201 B THE OPTIMIZATION PROGRAMS, AND THEIR INPUT DATA 2 12 C DATA FROM DISPLAY APPLICATIONS USING IBM 2250 DISPLAY SYSTEM AND MICHIGAN TERMINAL SYSTEM 233 viii

LIST OF TABLES Table Page 3-1 Analysis Results for One User (R = 1) 69 3-2 Analysis Results for Two Users (R = 2) 70 3-3 Analysis Results for Three Users (R = 3) 71 3-4 System Parameters Used for RQA and GPSS Analysis 75 3-5 Convergence of Simulation Results 76 4-1 Optimization Statistics 93 5-1 Display Instruction List 107 6-1 Michigan Intrastate Data Transmission Services 119 6-2 Remote Computer Core Storage 120 6-3 Remote Computer Bulk Storage 122 6-4 Remote Computer-Display Control Configurations 125 6-5 Possible Combinations of Display Controls and Display Consoles 126 6-6 Typical Remote Computer-Display Controls Selected for Use in Optimization 128 6-7 Text Editing Interactions 132 6-8 2 -D Drawing Interactions 134 6-9 3-D Drawing Interactions 136 6-10 Network Analysis Interactions 139 6-11 Display Instruction Mix 140 6-12 Display Weights Qi and Q min 143 ix

Table Page 6-13 Application Characteristics 144 6-14 Text Editing, One User 146 6-15 Text Editing, Two Users 148 6-16 Text Editing, Three Users 149 6-17 Two-Dimensional Drawing, One User 153 6-18 Two-Dimensional Drawing, Two Users 155 6-19 Two-Dimensional Drawing, Three Users 157 6-20 Three-Dimensional Drawing, One User 160 6-21 Three-Dimensional Drawing, Two Users 162 6-22 Three-Dimensional Drawing, Three Users 164 6-23 Network Analysis, One User 168 6-24 Network Analysis, Two Users 170 6-25 Network Analysis, Three Users 171 6-26 PM for the Most Cost-Effective Display Systems 189 C-1 Data Gathered for IBM 2250 Display Console Used for Graphics 236 C-2 Data Gathered for IBM 2250 Display Console Used as a Teletype 237 C-3 Data Gathered for Random Teletype Users 238 C-4 Data Gathered for Remote Display Terminal 239 C-5 Comparison of Statistics 240

LIST OF FIGURES Figure Page 1-1 Display System 15 2-1 Display System Model 24 2-2 Remote Computer and Queue 41 2-3 Remote Computer and Queue: Transformation I 42 2-4 Remote Computer and Queue: Transformation II 43 2-5 Remote Computer and Queue: Transformation III 44 2 -6 An Identity 45 3-1 Service Time Distributions 73 3 -2 Branching Distributions 74 4-1 Formation of the Set S 85 4-2 Minimization for One User (R=1) 90 4-3 Final Minimization 91 5-1 Alphanumeric Test Pattern 96 5-2 Weather Map Test Pattern 97 5-3 Graph Test Pattern 98 5-4 Architectural Drawing Test Pattern 99 5-5 Electronic Schematic Test Pattern 100 5-6 Balanced Display Configurations 110 5-7 Unbalanced Display Configuration 111 xi

Figure Page 5-8 Selection of Remote Computer-Display Controls 113 5-9 Example of Selected Remote Computer-Display Controls 114 6-1 Minimum Response Times, Text Editing 151 6-2 Minimum Response Times, Two-Dimensional Drawing 159 6-3 Minimum Response Times, Three-Dimensional Drawing 166 6-4 Minimum Response Times, Network Analysis 173 6-5 Best and Worst Average Response Times 176 6-6 Cost-Effectiveness 180 A-i Description of Display Applications 203 A-2 Description of Remote Computer-Display Controls 2 04 A-3 The PREPROCESSOR Program 209 B-1 Main Program 215 B-2 Input-Output Program 216 B-3 Typical Input Data 219 B-4 Optimization Program 221 B-5 Program to Evaluate T with RQA 224 B-6 Subroutines 22 9 C-1 Summary Data for Remote Display Terminal 244 C-2 Think Time Distribution 245 C-3 Response Time Distribution 246 xii

Figure Page C -4 Response Time Distribution 247 C-5 Distribution of Total CPU Time per Response Period 248 C-6 Distribution of Total CPU Time per Response Period 249 C-7 Distribution of CPU Processing Interval Times During Response Periods 250 C-8 Distribution of Output Line Lengths 251 C-9 Distribution of Number of CPU Intervals per Response Period 252 xiii

NO MENCLATURE This list contins the symbols which are used with some frequency in the following report. Symbol Meaning Page 7T Probability of service request type i 31 T. Time in microseconds needed by a remote computer-display control to execute a display instruction of type i 106 0.M Processing time needed by service request type i if performed by main computer 39 0.R Processing time needed by service request type i if performed by remote computer 39 Weight applied to display test pattern of type i 95 n(V) Numerical value of the binary sequence V 82 Pi Probability of accessing file i 34 t. Service time for server i 37 1 T tI Total average processing time per interaction for server 1 39 T t8 Total average processing time per interaction for server 8 39 w. Probability of executing display instruction type i 106 xiv

Symbol Meaning Page x Fraction of displayed information which differs between display consoles 102 A The vector which minimizes T(R, X, Z) 89 ARRIVE Arrival rate of user service requests 30 B.M Bulk storage accesses needed by service request type i if service performed at main computer 31 B.R Bulk storage accesses needed by service request type i if service performed at remote computer 31 Ci Cost of remote computer-display control i with no core memory 109 C(X) Total display system cost per month 53 C'(X) Display system cost per month, exclusive of main computer computation charges 53 C' Upper limit on C'(X) 84 max CE Cost-Effectiveness 179 CPUCST Monthly cost of using main computer, if it were used whenever display terminal is active 52 F Fraction of time that display terminal attempts to use the main computer 53 XV

Symbol Meaning Page MAXPAG Maximum number of pages or files of storage needed by display application 34 MSGLTH Length of messages sent over data link, in bits 36 N Number of display controls used at display terminal 109 N(. ) Cardinality of a set 88 N. Number of display instructions executed by an interaction of type i 31 N Average number of accesses to bulk storage made by interactions assigned to the main computer 39 N~ Average number of accesses to bulk storage made by interactions assigned to the remote computer 39 NPPPC Number of display instructions exe - cuted by remote computer for preprocessing or post processing 33 NT Number of types of service requests 31 PACESS(. ) Cumulative probability of accessing a storage file. 35 PAGCST Monthly cost of storing one file block at the main computer 53 xvi

Symbol Meaning Page PD Probability that bulk storage is accessed by the main computer following completion of a processing interval 40 PDRC Probability that a storage file is accessed by the remote computer following completion of a processing interval 46 PEND Probability that processing is ended at the remote computer when a processing interval ends 40 PM Probability that any interaction is assigned to the main computer 38 PMAIN Probability that a storage file is stored at the main computer 36 PRD Given that a storage file is not in core, the probability that it is stored on the remot& computer's bulk storage media 46 PREMOT Probability that a storage file is stored on the remote computer's bulk storage device 35 Qi Percentage of standard display test pattern i displayable by a display control 95 Minimum percentage of test patterns which must be displayable by a display control, for that control to be considered for an application 112 xvii

Symbol Meaning Page QTP Percentage of some special display test pattern displayable by a display control 101 QR Percentage of test patterns displayable on R display consoles by one display control 102 QRN Percentage of test patterns displayable on R display consoles by N display controls 109 R Number of display consoles served by a remote computer 23 S A set of feasible vectors 84 Si The i-th vector in S 90 I S' A set of feasible vectors 88 S.' The i-th vector in S' S The set of indexes of service request assigned to the main computer 38 SR The set of indexes of service requests assigned to the remote computer 38 SYSPAG Number of pages or files needed by the remote computer's core-resident executive system, plus a display file area and working area for each display console 34 T Average response time of a display system 54 Ti Service and queueing time of server i 54 ~~~1~~~~~xvi xviii

Symbol Meaning Page T Average response time of those service requests assigned to the main computer 54 M T. Response time of service request i if it were assigned to the main computer 57 TR Average response time of those service requests assigned to the remote computer 55 T.R Response time of service request i if it were assigned to the remote computer 57 TL A lower bound on T 56 TMIN The minimum value of T 89 TRIP The percentage of all bits sent over the data link which are useful information 29 UMC Instruction execution rate of the main computer 33 UMD File access rate of the main computer's bulk storage 28 URD File access rate of the remote computer's bulk storage 28 X A binary sequence 81 X A four-component vector 29 X1 Data link transmission rate, b. p. s. 29 X2 Blocks of remote computer core storage 29 xix

Symbol Meaning Page X3 Blocks of remote computer bulk storage 29 X4 Instruction execution rate of remote computer-display control 29 X* A binary sequence 82 X* A four-component vector 83 Z A vector describing a display application 56 XX

ABSTRACT A rigorous analysis of computer-driven display systems is undertaken. The type of system studied consists of a display terminal, which can include a small computer, core memory, bulk memory, and one or more display controls and display consoles. The display terminal is in turn usually connected via data-link to a large time-shared computing system. To facilitate the analysis, a mathematical model of a general display system is developed. The model's parameters are derived from characteristics of the display system's hardware and of the application implemented on the system. The model is used to predict the average response time which will be experienced by a user of the display system. Included in the model is an objective method of dividing display processing between the main and terminal computers. So that certain of the model's parameters can be specified, a method of evaluating the computational and display capabilities of a computer and display is developed. The evaluation criteria are also used to eliminate some computer-display controls from consideration for inclusion in a display system. The response time can be calculated in one of several ways. If there is only one display console, a closed expression is found. With more than one console, queueing can develop. Thus either xxi

simulation or queueing analysis can be used. Comparison of these two techniques shows that even though the conditions needed to use a queueing analysis may not exist, its results in this case are quite satisfactory. Also, queueing analysis is considerably less expensive than simulation. An optimization procedure is developed to find the display system hardware which, for a given application, minimizes average response time subject only to an upper limit on the amount of money to be spent. The optimization is designed to analyze the display system model as infrequently as possible, to save time. The optimization is used to find optimum display systems for various costs and for four different display applications: text editing, two-dimensional drawing, three-dimensional drawing, and network analysis. The optimum display systems are in turn used to study the cost-effectiveness of various display systems, to determine if single or multiple display systems are less expensive, to develop general design guidelines, to study the necessity of hardware multiplication and division capabilities at the remote computer, and to demonstrate the necessity of the work reported here. xxii

Chapter I INTRODUC TION The subject of the study reported here is the systems design of highly-interactive graphical display terminals for time-shared computer systems. The overall goal is to develop insight into how the choice of subsystems for a display system can affect the system's performance, and to develop methods of finding the combination of subsystems which will be optimum for any well-defined display application. Optimum will be defined so as to minimize a display system's response time subject to a cost constraint. Viewed in a slightly different way, display system design can be thought of as presenting a problem in resource allocation. The resource is a fixed number of dollars, which is allocated to the purchase of display subsystems in a manner which minimizes the total system's response time. But why so much interest in dollars and response times? The most important answers are first, that display system hardware costs can easily exceed $100,000; therefore, unwise allocation of so much money falls in the serious mistake category; and second, that improper allocation of the dollars can produce a display system whose response time will be shown to be orders-of-magnitude worse than what can be achieved with the optimum allocation.

2 This is significant because response time must, of course, be a prime concern in the design of any highly-interactive remote access computer system, and is even more important when considering the graphics terminals which often form part of such systems, because fully capitalizing on the potential interaction rates achievable with a graphics terminal demands good response time. The various sections of this chapter will attempt to justify the use of graphics terminals, present some pertinent historical information, define terms, and give a qualitative idea of the problem to be tackled. 1. 1 Why Computer Graphics? Dynamic interactive graphics display systems are becoming essential components of large current-day information processing complexes. These displays cannot only replace teletypes currently used in time-sharing computer systems, but can also greatly expand the sphere of computers' reach and usefulness. Thus in the future we can anticipate increasing utilization of display systems to facilitate man-machine interactions. The advantages of graphic input-output devices manifest themselves in two ways. Display terminals, be they used solely for alphnumeric textual material or for more general graphic presentations, provide an ideal match between the computer and its users. That is, a display terminal is able to accept input from a user at slow

3 keyboard speeds, but can also accept computer output at high speeds, and present it to the user as fast or even faster than he is able to read it. This is in contrast to the prevailing use today of various slow typewriter units, whose slow output speeds in many cases severely limit the realization of otherwise possible man-machine interaction rates. A highly desirable side effect of display terminals is a sharp drop in the proliferation of hard copy output. Many computer terminal uses, such as program preparation and browsing through data files, do not need hard output. The second justification of display terminals is that for many computer users, particularly engineers, graphics is a natural means of communications, and can bridge the broad chasm between the computer and its multitude of present and future users. This chasm exists because, until recently, computer users have been forced to approach computers in a very stilited and unnatural fashion, dictated more by the computer's input-output limitations than by the user's problem solving requirements. Engineers, and others, are now able to engage the computer in a graphical dialogue, oriented toward using the computer as a design and problem solving aid in a straightforward way. An excellent example of this chasm bridging exists in the area of computer aided electrical network studies, where analysis and synthesis programs have existed for some time [ 29]. The problem

4 with such programs is that a potential user must make a large initial investment of time by reading a manual (which may be hard for him to understand) and either preparing punched cards for input or learning to use a teletype terminal. Much more appropriate and suitable systems are now being developed, in which a circuit is actually drawn by the user on a CRT (Cathode Ray Tube) display, component values are specified, dependent and independent sources are defined, and certain currents or voltages are requested to be found [ 12, 13, 14, 50]. Then, in a few seconds, the desired outputs appear as graphs on the CRT. Given the results, the engineer can now either accept the existing design, or modify it. This is the analysis approach. Synthesis techniques, such as fitting a circuit to given amplitude and phase characteristics [ 56], are also evolving. But whatever the approach, it is now possible to study complicated electrical networks in a matter of minutes, in a manner more convenient than with either teletype-based remote access systems or card-based batch processing systems. The basic advantage of display systems over teletypes is not so much the speed increase as the convenience and ease of use for the practicing engineers. Teletypes greatly increase the computer's accessibility, but it is display terminals which brings the computer's power and capabilities to engineers, on engineers' terms, in engineers' language, for engineers' purposes.

5 Circuit analysis is just one of the many areas in which computer aided design is of maximnum benefit when implemented with display terminals. Other applications are discussed in Section 1. 3. We will not bring into our discussion graphics applications which are primarily oriented toward film or paper plotting devices. Now, having given some indication of the type of computer graphics of interest here, we will turn our attention to a few historic matters. 1. 2 Historical Development The first large-scale application of display equipment was the SAGE (Semiautomatic Ground Environment) air-defense system, initiated in the fifties. In this system, operators used light guns and function keys to instruct the computer, and monitored the results on display screens [31]. The development work for this was performed, at least in part, by Mr. Jay Forrester and his associates in M. I. T.'s Whirlwind-I Computer Group, where CRT's were used for man-machine communications as early as 1950 [ 2]. This early involvement of M. I. T. in computer graphics has proven to be very significant: the school and its associated laboratories continue to pace developments in computer graphics, particularly with respect to new hardware, but also in software. In fact, the second significant graphics contribution from M. I. T., following the pioneering work of the early fifties,

was the introduction in early 1963 of a comprehensive software package allowing easy, engineering-oriented man-machine interaction. This software, called Sketchpad[54], was developed by Dr. Ivan Sutherland on Lincoln Lab's TX-2 computer, and marked the beginning of serious efforts to develop sophisticated applications software for graphics work. Manufacturers also began developing the types of display hardware required by these emerging applications. Coming close on the heels of Sketchpad, the announcement of General Motors Research Laboratories' DAC-I (Design Augmented by Computers) System [23] helped give graphics work respectability and acceptance in industry. Both the academic and industrial worlds have continued to develop and use computer graphics since these early experiments. A great boon to graphics work has been the emergence of large time-shared computer systems, such as project MAC [8], the Multics System [7], SDC's Q32 System [48], and the Michigan Terminal System [57]. Their impact has been to permit relatively economical on-line graphics work. Before time- sharing systems were available, on-line graphics required a powerful dedicated computer; an expensive proposition indeed! Current graphics systems, along with a large time-sharing computer, use either a small cheap dedicated computer, or none at all.

7 1. 3 Typical Graphics Applications The common bond linking the many diverse graphics applications of interest here is that they all embrace a highly interactive graphics-oriented dialogue between a graphics console and its user. This is in marked contrast to uses in which the graphics equipment acts primarily as an output device, or as a sophisticated teletypewriter -like device. A typical currently implemented application, with widespread industrial usefulness, has been described by Prince [45]. It is a system for creating tapes for numerically controlled machine tools. A designer first draws on his CRT display a standard engineering drawing of a part, and then specifies the path, depth of cut, tool type, feed rate, etc. for the various cuts needed to shape the desired part from a solid piece of metal. The required control tape is then automatically generated. This system eliminates the tedious task of numerical control programming, and has the added advantage of immediate visual confirmation of the cutting tools' paths. Another interesting application is in the electronics industry, speeding the design of artwork for precision masks used in manufacturing integrated circuits [36, 39, 52]. An engineer can lay out on the CRT the various active and passive circuit components required, specify their characteristics, and indicate the desired

8 component interconnections. The computer then calculates the exact pattern dimensions required at each masking level for the resistors, capacitors, diodes, and transistors, sets up interconnection routings, and produces the required masks as output on a film plotter. The engineer can at any time intervene to modify the computed results, thus allowing the interjection of human judgment at any point in the design process; a highly desirable feature. Other current uses include textile design [42], biomedical research [ 46], and mathematical computations and curve plotting [63]. Of significant importance to the implementation of new graphics applications is the recent development of graphics programming systems imbedded in compiler-level languages such as FORTRAN [ 4, 28, 32, 58]. These systems provide both programming ease and some degree of hardware configuration independence, so that, coupled with increasing hardware availability, we can reasonably anticipate a much more rapid growth of display applications than has been seen in the past. One of the potential stumbling blocks in this progress, however, is the problem of inept display system hardware selection, which can result in systems not suited to their application costing too much and performing poorly.

What we need is a more disciplined approach than has been used in the past for matching display applications to the appropriate hardware. With this closing thought in mind, we will turn our attention to the evolution of present day graphics hardware, by first giving sormie definitions in Section 1. 4, and continuing in Section 1. 5 with some specific hardware details. 1. 4 Definitions Before proceeding further, it is necessary that we pause and clearly define certain essential terms so as to avoid later confusion. Particular attention should be given the differences between display terminal, display control, display console, and display. Display Console A display console is that piece of equipment which presents graphical information to a human. Current technology utilizes a CRT for this purpose. The console may also include a light pen, printer, function keys, a keyboard, or other similar devices. Display A display console presents a display on its cathode ray tube. The display consists of lines (vectors), points, and characters (alphanumerics) forming some meaningful picture, such as a mechanical drawing or a circuit diagram.

10 Display Control A display control (sometimes called a display generator) is the interface between a display console and an information processing system. As such, it performs several functions, the most important of which is to accept display commands and produce the appropriate voltages (currents) to drive the CRT's deflection plates (yokes). Sophisticated display controls perform other functions, such as sub-routining, conditional skips, jumps, light pen tracking, and matrix multiplication. Display Terminal A display terminal consists of display consoles and whatever computer system hardware has as its prime function the support of those consoles. A display terminal's hardware may include up to one computer, bulk storage devices, a data link interface, and I/O devices, and has a minimum of one display console and one display control. Display terminals are often connected to a large time-shared computer facility not dedicated primarily to use by the terminal. This facility provides back-up computing and storage support to whatever hardware is directly associated with the terminal. Remote Display Terminal A display terminal physically separated from the back-up, or main computer facility is remote from that facility: hence the name.

11 For our purposes, a terminal will be considered to be remote whenever the data link between the back-up computer and the terminal is more expensive than if the terminal were adjacent to the backup computer. Re mote Co mpute r A remote (or peripheral or satellite) computer is a computer which is part of a remote display terminal. Refresh Rate Refresh rate is the number of times per second that an image is traced on a volatile (non-storage) display surface. In order that the display maintain a steady intensity, a minimum refresh rate must be maintained. This minimum rate depends upon the decay rate of whatever physical phenomenon produces visible light. For CRT displays, this phenomenon is the secondary emission by phosphor bombarded with high energy electrons. Minimum CRT refresh rates vary from 10 to 60, depending upon the type of phosphor utilized. Flicker Free A flicker free display is one which is being regenerated at a rate greater than or equal to the minimum refresh rate, so that to the human eye the intensity of the display remains constant over time.

12 1. 5 The Hardware System DAC-1 and Sketchpad, the two early interactive graphical computer aided design systems, were both connected to somewhat unorthodox (at the time) computer systems. In the case of DAC-1, an IBM 7094 with two independent 32k core banks was used. One core held the batch processing job; the other, the graphics supervisor and applications programs. When display servicing was needed, control was given to the graphics supervisor which, when finished, reverted control back to the batch supervisor. Thus extensive swapping to a disk or drum is eliminated, and the CPU can be productive much of the time. Sketchpad is implemented on Lincoln Lab's vintage 1956 experimental TX-2 computer, which has 68k of core memory and 64 index registers. Memory reference instructions can be double indexed, allowing a multiprogramming capability to be implemented with relative ease, in a manner similar to current third generation practices. This of course means, as in the case of DAC-1, that the CPU, when not required by the graphics programs, can be involved in other productive data processing. As mentioned earlier, this is virtually an economic necessity when big computers are involved. The DAC-1 system helped to introduce the idea of a display buffer memory, because a second function of the 7094's added

13 core bank was to hold the instructions which actually drive the CRT display, thus eliminating any decrease in the instruction execution rate for the batch jobs. With the TX-2, both CPU instructions and display instructions are taken from the same core metnory, so that competition for core cycles does arise, thereby slowing the CPU execution rate. In TX-2, ten microseconds are taken to transfer an instruction to the display control, which in turn takes fronm 20 to 100 microseconds to execute the display instruction. During this execution, the TX-2 has access to its core memory to continue its normal program. In effect, then, the display degrades the computer's performance by 9%to 33%without a buffer memory. Buffer memories are important for a second reason. Whenever a CRT display console is more than several thousand feet distant from its supporting computer, the cost of the required high-speed data transmission facilities becomes prohibitive. This data link is needed to refresh the CRT display rapidly enough so as to avoid flicker. With a buffer memory at the display console site, a less expensive, lower speed data link becomes feasible. One of the early (1964) display terminals using as a buffer the core memory of a very small computer was Digital Equipment Corporation's Type 3 40 Precision Incremental Display. Several

14 configurations exist in whicn tre small computer used is a PDP-4 or PDP-7 [6, 9]. Following in 1965 came DEC's 338 Programmed Buffered Display, which included a PDP-8. This was really the first product line graphics terminal capable both of stand-alone operation for unsophisticated work, and use as a peripheral computer and terminal associated with a large time-shared computer for applications demanding either large amounts of bulk storage or computation. Since then many similar products have been introduced by Information Displays Incorporated, Systems Engineering Laboratory and Adage. Also available are a number of buffered and unbuffered graphic displays, as well as even more alphanumeric displays. While their ranks continue to swell, our attention will be confined to buffered displays, with or without an associated small peripheral computer. A general display hardware configuration is shown in Figure 11. The bulk storage device is included because in situations where a slow data link is used, the storage can potentially be very desirable and convenient. For many applications the remote computer is sorely needed. John Ward, from M. I. T.'s Electronic Systems Laboratory, remarks [61] that

DISPLAY CONSOLES BULK BULK STORAGE STORAGE SYSTEM SYSTEM DISPLAY IREMOTE DATA MAIN I CONTROLLER(S COMPUTER LINK Figure 1-1 Display System

16 Our experience over the past two years has indicated that even with the specialized computing capability of the [display] console, the associated real-time general-purpose data processing needed for display operation is an undue burden on the main computer. What is actually needed is a small, inexpensive, satellite computer interposed between the main computer and the display console. In matching the system in Figure 1-1 to a specific application, many questions arise. These relate to what type of satellite computer should be used, to the data link speed, and to the other hardware components of the display system. 1. 6 Trade-offs There exists a large number of hardware-hardware and hardware-software tradeoffs which can be exploited in specifying a display system for a particular graphics application. With respect to hardware-hardware tradeoffs, if we wish to maintain a specified response time at the display console and wish to decrease the data link speed, it is necessary to increase the "power" of the remote computer/display control, or the amount of core storage, or the amount of remote bulk storage, in order to compensate for the extra data transmission time. The converse also applies. Increasing remote computer power cuts computation time, while increasing core storage decreases bulk storage accesses, either at the terminal or at the main computer, and increasing remote bulk storage cuts down on data link usage.

17 In some cases, however, it may not be possible to completely compensate for a lower transmission rate. This will depend both on the decrease in transmission rate and on the relative usage of the four system components. Specifically, a small decrease in transmission rate for an infrequently used data link is far easier to accommodate than a large decrease in a heavily used link. Similar statements can be made with respect to each of the other system resources: a decrease in any one can be compensated for by increases in one or more of the other resources, within certain limits. There exist also certain hardware-software tradeoffs, related to the remote computer/display control. These center around the implementation of certain display-oriented functions normally performed at the remote display terminal by either the computer or display control. These functions are discussed below. When a position indicating device, such as a RAND tablet [11], is used at the display console, it is often necessary to correlate a position with an entity currently being displayed on the CRT. This can be done with software, or with display control hardware which continually compares the current CRT beam position with the indicating device's position [37]. The first method can consume much remote computer time, but costs nothing; the second method takes neither remote computer time nor display control time, but does take money for the extra hardware.

18 If, on the other hand, a light pen-type entity indicating device is employed, its position will frequently need to be known: this is the familiar light pen tracking problem. Once again, the work can be done with either special purpose hardware built into the display control, or with a program running on the remote computer. A current hardware implementation takes about 10% of the display control's time, decreasing by a like amount the quantity of flicker free material which can be displayed [53]. Software implementations of various pen tracking algorithms do not affect the display, but do require remote computer time to execute. One of the most demanding display functions is the rotation of a three dimensional object, which requires a matrix multiplication operation of six scalar multiplications and 4 scalar additions for each point and line of the display. Implemented in software, this can be very slow, and can limit the smoothness and rate of dynamic rotation. A first step toward improvement is adding hardware multiplication to the remote computer. A second step is implementation, in the display control, of the actual matrix multiplication. There are two current manifestations of this second possibility. One uses binary rate multipliers, followed by digital addition [53]. The second uses analog multipliers and analog addition [1].

19 Hardware facilities for display subroutining allow one display list to be used many times in the course of drawing a picture, and therefore avoids needless duplication in core of display instructions. This is all a direct parallel to subroutining for computer programs. Similar display control hardware-remote computer software tradeoffs exist with respect to problems of dashed lines, blinking lines, transfer of control, recursive subroutining, displaying lines, and displaying alphanumerics. 1. 7 Research Objectives With this multitude of tradeoffs between the various display system components, an important question arises: for a given display system application, and a given dollar cost, what combination of display subsystems will produce the best possible service for display users? The best hardware will produce the fastest, or minimum, average response time experienced by the display system's users. What is needed for use by display system designers is a rigorous objective method for evaluating the effects upon system cost and response time of the various tradeoffs discussed qualitatively in the previous section. By now the qualitative tradeoffs, which are in fact rather obvious, are well understoodo The trade - offs need to be quantified for the sake of intelligent systems design, because the consequences of using poor systems design are the

20 overloading of some subsystems, underutilization of other subsystems, and decreased productivity for the system's user. The purpose of the work reported here is to quantify the tradeoffs, and to create a rigorous quantitative approach to display system design. Of prime importance to the work is its continuing emphasis on optimal design. The important contributions of this research are considered to be: 1. Development of a mathematical model for the study of display systems and their applications. 2. Identification of those display system application characteristics which should be known in order to rigorously study the application. 3. Development of an objective approach toward dividing display application computations between the main and remote computers. 4. A comprehensive method to evaluate the capabilities of remote computer-display controls. 5. An optimization scheme to find the best display system of a given cost. This provides a means of studying specific display systems, as well as a way to develop item 7 below. 6. A cost-effectiveness criterion for selecting one of several display systems which are optimum for their respective costs.

21 7. General guidelines for display system designers.

Chapter II A MATHEMATICAL MODEL OF DISPLAY SYSTEMS The central theme of the work reported here is optimum design of display systems. In order that display systems be studied in a rigorous manner, particularly to find optimum display systems, a mathematical model or abstraction of how a display system operates is needed. To be useful, the model must reflect the varying capabilities of the four hardware components which comprise a general display system, as discussed in Chapter I; data link transmission rate, computation rate of the remote computer and display control, core memory included in the remote computer, and bulk storage associated with the remote computer. The model must also be sensitive to the varying computational, storage, and data transmission requirements of the many different applications which might be implemented with a display system. Furthermore, any explicit or implicit assumptions imbedded in the model must be tenable. Finally, the model, when appropriately analyzed, must yield some measure of system performance; specifically, the system's response time will be taken to be the most important performance measure. 22

23 In the following sections a model which satisfies these requirements will be presented, the process whereby parameters of the model are determined will be discussed, assumptions will be evaluated, and some preliminary analysis concerning response time will be performed. 20 1 Display System Model Figure 1-1 shows a typical display system with R display consoles being serviced by a single remote computer, which in turn is supported via a data link by a large time-shared computing system. The model, shown in Figure 2-1, represents an abstraction of the flows of information and control which are likely to occur in the total system. Each box in the model represents a server and when R > 1, a possible queue of tasks waiting to use the server. As can be seen, servers are the remote computer, its bulk storage, the data link, the main computer, and its bulk storage. It is often the case that several servers in the model refer to the same physical device, performing different functions. The best way to understand the model's operation is to follow a typical man-machine interaction as it passes through the system. An interaction is begun when a user at one of the R display consoles requests service by introducing information into the system. The user does this by typing on an input keyboard, depressing a function button, causing the light pen (or a similar

24 MAIN COMPUTER 9 BULK STORAGE 4 4 and 9 a MAIN 8 COMPUTER PRIORITY 3 PRIORITY 4 PRIORITY I PRIORITY 2 DATA I101 1 7 I LINK 5 3 PRIORITY 2 PRIORITY 3 REMOTE REMOTE COMPUTER: 11 6 COMPUTER: POST- PRE-, PROCESSING PROCESSING REMOTE PRD COMPUTER 2 BULK STORAGE.REMOTE I COMPUTER: PRIORITY I REMOTE PROCESSING PM I -PM USER SERVICE WAIT FOR NEXT REQUESTS WAIT FOR NEXT REQUEST REQUEST Figure 2-1 Display System Model

25 device) to sense a point on the display, or some similar action. The resulting service required by the user's action may be so trivial as adding an additional alphanumeric character to the information already in the display, or so difficult as analyzing a complex electrical network. Having received the input information, the remote computer's interrupt handling software is able to determine, in a time interval usually so short that the process is not modeled, whether the requested service will be performed by the remote computer or the main computer. The main computer will be used if it has been programmed to do what is needed; if not, the remote computer will have been programmed to perform the desired service. If the main computer is to be used, a task is entered in the queue of tasks waiting to use server 6 (when R = 1, queues never exist, so the task always begins service immediately), which is the remote computer in a pre -processing mode of operation. This pre - processing involves preparing a message for transmission to the main computer, giving it all the information needed to perform its task. The work involved may be as simple as requesting transmission of a previously-prepared message, or as complicated as creating a compact description of a display from its display file. Having finished pre -processing, a message is queued for use of the data link, server 7, and is eventually sent to the main computer, after which the job queues for attention by the main computer, server 8.

26 One of two situations will usually prevail at the main computer. Either display terminal tasks are given priority over other tasks, such as those from teletype terminals, or they are not. In either case, the model's queue 8 contains only display tasks; however, in the priority case, the main computer's service time will be less (possibly substantially less) than when there are no priorities. That is, the fact that non-display tasks may be competing with display tasks for use of the CPU will be treated implicitly in the CPU's service rate, rather than explicitly by having non-display tasks in queue 8. No matter what the priority structure (or lack of it) may be, intervals of main computer service ensue, interspersed with bulk storage accesses to programs and/or data. Whenever processing ends, a message containing results is queued for transmission to the remote computer via server 10. Following transmission, the task queues to use the remote computer, server 11, for post-processing. During post-processing, results received from the main computer are interpreted and expanded into a display file, after which the user sees his results on the display console, and is able to generate a new service request. Several general observations concerning the model are appropriate. A very clear distinction is made between the two roles played by the main computer. The first role, that of a processor, is modeled by servers 8 and 9; the second role, that of storage for data and programs for the remote computer, by server 4.

27 Because several servers are in fact the same physical device, a system of priorities is included in the model. They are indicated in Figure 2-1. For example, if tasks are waiting to use the remote computer in both its pre- and post-processing roles, postprocessing is given priority. This is just an extension of the readbefore-write philosophy used in scheduling the paging drum of current time-shared computer systems [40, 57]1 The goal of course, is to keep response time down. In the case at hand reads are associated with post-processing and writes with pre-processing: since it is the "reads" which bring a task nearer to completion with more certainty than a "write." Indeed, in this example, postprocessing completes a task. Beyond this, however, remote processing (server 1) is given top priority for use of the remote computer. This helps the display terminal users maintain a high interaction rate while doing the ordinary work supported by the remote computer, for which the user expects fast responses. Interactions involving the main computer, for which users are usually prepared to wait a bit longer, are accordingly given lower priority. Priorities for use of the data link are assigned on the same basis, that is, "read before write" with preference given to the remote computer. Finally, it is important to remember that each of the R users can have only one task in the system at any time. This means that the maximumn queue length at any server is R-1 (one will be in

28 service), and that no more than R tasks can simultaneously be in the system. 2. 2 Hardware Specification Determining parameters of the model requires certain information about the hardware system. The parameters defined below are needed. UMD - accesses per second which can be made to the Main computer's Disk storage system. For this and the following definition, an access means reading or writing 12, 000 bits. If the main computer's filing system is such that storing or retrieving a block of information requires more than one physical access to the disk (such as first accessing a line directory and then accessing the line, as with the Michigan Terminal System [57], then UMD should account for this. Thus, UMD is the rate at which file blocks can be read or written. URD - accesses per second which can be made to the Remote computer's Disk storage system. It is assumed that the remote computer's filing system will be very simple, avoiding the necessity of multiple accesses to read or write a file

29 block. Therefore URD is the access rate for a single access. Xl = Data link transmission rate, bits per second. TRIP - Transfer Rate of Information Percentage, such that TRIB = X1 x TRIP, where TRIB is the actual transfer rate of information bits after accounting for factors such as coding redundancy, error rates, and non-information characters. TRIB is discussed in reference 38. X2 = Number of 12, 000 bit blocks of core storage available at the remote computer. A block of storage is defined to be 12, 000 bits as a matter of convenience. X3 = Number of 12, 000 bit blocks of bulk storage available at the remote computer. X4 - Instruction execution rate of remote computerdisplay control. The manner in which this can be determined is discussed in Chapter V. The parameters X1, X2, X3, and X4 each characterize a particular subsystem. The vector X = (X1, X2, X3, X4) specifies the essentials of a display system. The next section will discuss what display application characteristics must be known. Then, knowing the characteristics of both

30 the hardware and the application, the model's parameters will be determinable. 2. 3 Application Specification Characteristics of the particular application being implemented on a display system are needed to completely specify the display system model's parameters. The following characteristics must be known, or estimated. It should be understood that these are average characteristics. ARRIVE = Arrival rate of service requests from a user during the period that the system is awaiting commands from the user. This quantity is in fact just the reciprocal of the user's think time. It is clear that as the system's application varies from simple to complex, think time, that is, time required for the user to decide what should be done next, will also vary. Think time also is dependent upon the user's experience with the application and with using the display console. Each service request which is received from a console user necessitates performing some computations. Depending upon what has been requested, the computations may be very short, or they may be long and involve many bulk storage accesses. For each different type of service which may be desired by the console user, the 4-tuple

31 (Ni, 7i BiM, BiR) must be given. Let there be NT different types of service requests for the application under study. N. - Number of instructions which must be executed to complete a service request of type i. An instruction is not a machine-level instruction, but is rather a higher-level type which will be called "display instructions", and will be precisely defined in Section 5. 3. Any service request can be completed by executing some sequence of display instructions..=. - Probability that a service request of type i will i be made. The summation of the 7vi.'s is unity. B. = Number of accesses (or Branches) to bulk storage which will be required by a type i service request, given that the service request is processed at the Main computer. All of these accesses will be to the main computer's bulk storage. RA B. = Number of accesses (or Branches) to bulk storage which will be made by a type i service request, given that the request is processed at the Remote computer, with only one block of core storage available at the remote computer as a working area into which programs can be

32 brought to execute. These accesses can be to bulk storage at either the main or the remote computer. M R B. and B. will in general not be equal. This is primarily 1 1 because the main computer has more core storage than does the basic remote computer-display control, which as just noted has only one block for a working area. It is therefore quite unlikely that whatever program or data service request type i needs will be in the working area. The main computer in contrast has a large amount of core storage for a working area, so that many programs can be in core (or at least in virtual memory, on a fast drum rather than on slow disk) concurrently. It is thus likely that fewer accesses to bulk storage will have to be made by the main computer than by the remote computer. It is on the basis of this information that service requests will be assigned to either the main or remote computer. A recent article by Williams [62] contains a general discussion of a graphics system at SDC. It establishes just three types of interactions, which are then assigned to either the main or remote computer depending on the interaction's computational requirements. Section 2. 7. 1 presents a formalized objective method of making these assignments. Once the assignments are made, various parameters of the model can be calculated, as will be done in the following section. First, however, more information is needed.

33 NPPPC = Number of instructions performed by the remote computer when in either the pre- or post-processing mode of operation (corresponding to servers 6 and 11 in the model). The meaning of instructions was clarified above. UMC _ Instruction execution rate for the main computer. Instructions are defined in Section 5. 3. If tasks from the display system are given preemptive priority at the main computer, UMC is the true rate at which display instructions can be performed. If not, UMC must be degraded to account for those periods of time when a display task is eligible to execute but is waiting for a non-display task to complete execution, or when it must wait for core storage to become available. Note that the effect of competition for the CPU by several display tasks is explicitly modeled by use of a queue. It is only competition from tasks not originated by the display system being modeled which must be reflected in UMC. Another important application characteristic which is manifested in the application programming is the relative and absolute usage of the data and program files associated with the display

34 application Of specific interest here are all program and data files accessed by the remote computer, regardless of whether the files are stored at the main or remote computer. To delve further into this matter, additional definitions are useful. MAXPAG Maximum number of file Pages, or blocks, needed to store the above-mentioned files, when only one file is stored in a file block. In Section 2. 2 a block of storage was defined as 12, 000 bits. SYSPAG - Number of System Pages, or blocks of remote computer core storage used on a permanent resident basis by the executive system, the working area from which programs are executed, and the display file, when one display console is usedo Two blocks are added for each additional display console to provide the necessary program area and display file area, A Probability of accessing file number i, conditioned on a file access being needed by the remote computer in a display system with only SYSPAG blocks of remote computer core available. Furthermore, let the MAXPAG file blocks be numbered 1, 2,.., MAXPAG

35 such that P > > PMAXPAG That is, the Pi's form a monotonic nonincreasing sequence {Pi}. PACESSj) = J p. = probability of accessing file blocks i= 1 1,2,.., j, given that a file access is needed. Then if a display system has X3 blocks of bulk storage at the remote computer and X2 blocks of core storage, it is logical that the X2 -SYSPAG file blocks with the high - est relative useage, that is, the highest Pi's, be kept in core, the X3 next most frequently used file blocks be kept in remote bulk storage, and the least frequently used blocks be kept at the remote computer. This simply minimizes average file access time by placing frequently used files in a fast storage device and less frequently used files in slower storage devices. With this said, more definitions are possible. PCORE = PACESS(X2 - SYSPAG) - Probability that a needed file is in core. PREMOT = PACESS (X2 + X3 - SYSPAG) - PCORE = Probability that a needed file is in bulk storage at the remote computer.

36 PMAIN = 1 - PCORE - PREMOT - Probability that a needed file is in bulk storage at the main computer. MSGLTH - Message length, in bits, sent over the data link, corresponding in the model to servers 3, 5, 7, and 10. Summarizing, the following application parameters are to be estimated. ARRIVE, the arrival rate of user service requests. NT, the number of types of service requests. For i=1,..., NT; N., the number of instructions needed to complete service type i. 7ri, the probability of service type i. B., the number of bulk storage accesses needed by service type i if performed at the main computer. B.R, the equivalent of B. for service at the remote 1 1 computer. NPPPC, the number of instructions needed for pre- or post -processing. UMC, the main computer's instruction execution rate. MAXPAG, the maximum number of storage blocks needed by the remote computer. For i=l,..., MAXPAG; Pi' the probability of accessing file i. MSGLTH, the length of messages sent over the data link.

37 At this point it must be very evident that the foregoing parameterized application characterizations may, in fact, be very difficult to estimate, This is true. However, what is equally true is that the better an application and the programming and computational requirements of that application are understood, the easier will the estimating process be, and the better will the parameter estimates be, and the better will the response time estimate be. This model does not give something for nothing. It does not give an estimate of response time for an ill-defined application implemented on an illdefined hardware display system. On the other hand, the model will hopefully give an accurate estimate of the system response time for a well-defined application. Having clarified this, attention is turned to the next section, in which the model's parameters are actually found. 2. 4 Parameter Calculation Having described the display system hardware and applications, the model's parameters can now be computed. These parameters consist of the branching probabilities seen in Figure 2-1, the arrival rate of service requests as well as the average service time for each of the 11 servers. These service times will be designated as ti, i-=1 2,... Certain of the parameters are given explicitly. Thus the arrival rate of service requests, ARRIVE, is known, and t2 = 1/URD, and t4 - t9 - 1/UMD.

38 The time taken by the data link to send a message is just the message length, in bits, divided by the effective transmission rate, in bits per second. This rate is just (X1)(TRIP/100), so that t3= t5= t7= t10= MSGLTH/((X1)(TRIP/100)). (2. 1) The pre- and post-processing time is the number of instructions to be executed, divided by the remote computer's instruction execution rate, so t =t NPPPC (2. 2) t6 t11 X4 The remaining parameters are all dependent upon the division of processing between the main and remote computers. For now it is sufficient to assume some arbitrary division of tasks between the two computers. An optimum division will be discussed in Section 2.7. 1. Now suppose that the set SR contains the indices of those tasks, or service requests, which are assigned to the remote computer; and SM, those assigned to the main computer. The properties of S andSR are that SM S, the null set, andM US =S, the set of integers 1, 2,..., NT. In words, a task has as its processing unit either the remote or main computer, but not both (exclusive of the pre- and post-processing work), and a task always requires some processing. Then PM, the probability of using the main computer (the probability that a service request causes a task to use the main computer), is given by

39 PM- 7ri, i e SM The above properties of SM and SR imply that V. M 1- PM - 1 - j Tri, i e S R jTi., iE S From N., the processing time per interaction for service M N 1 R 1 request type i is easily seen to be 0. and 0. R for 1 UMC 1 X4 T T the main or remote computers, respectively. Defining t1 and t8 to be the total computation time per interaction provided by server 1 (remote computer), given that it is used, and by server 8 (main computer), given that it is used, respectively, it follows that T 7. R. N. R t = 0, iE S, and (2. 3) tT jPM- i M i e S (2.4) Division by 1- PM in the former and PM in the latter case is needed to form normalized probabilities. In a similar manner, NR and N the average number of bulk storage accesses per interaction made by the remote computer, given that it is used, and by the main computer, given that it is used, respectively, are R __ R R M T. M M N BO. Bi e S. N= -PM B Having found these intermediate results, the remaining model parameters are determinable. Because there are N bulk

40 storage accesses at the main computer, there are N + 1 processing intervals, the first NM of which end with bulk storage accesses, and the last of which end not with another bulk storage access, but with the sending of data back to the display terminal. Then t, and the probability of accessing bulk storage is given 8 N+ M by PD = -. This ratio can be thought of as successful attempts N M+ 1 divided by total attempts, where a success is interpreted as a storage access. The only parameters remaining to be defined are PRDC, PRD, and t1. These are most easily found by considering Figures 2-2 through 2 -6. The rectangle in each figure represents the remote computer, and the expression within each rectangle is the average time used by a task passing through the remote computer. Figure 2-2 shows that the remote computer (server 1 in the model) can comt T plete a job in a time of —; a direct parallel to the above discus1 + N sion concerning t8. The probability that a processing interval completes all needed processing is PEND = 1 + NR If processing is not done, a file access is made either to core with probability PCORE, or to the remote computer's bulk storage with probability PREMOT, or to the main computer's bulk storage with probability PMAIN.

41 PMAIN PREMOT PCORE \ 1- PEND tjT J+NR I I PEND-NC QUEUE REMOTE + NcEss COMPUTER Figure 2-2 Remote Computer and Queue

42 PMAIN(I-PEND) PREMOT(I -PEND) PCORE (I- PEND) J|I + NR |PEND QUEUE REMOTE COMPUTER Figure 2-3 Remote Computer and Queue: Transformation I

43 PMAIN PREMOT+MAIN PMAIN PREMOT + PMAIN 0 r-l -PEND II T I I-PCORE (I-PEND) QUEUE REMOT E COMPUTER PEND D= PCORE (I- PEND) D PMAIN + PREMOTE = I - PCORE Figure 2-4 Remote Computer and Queue: Transformation II

44 PMAIN PMAIN+PREMOT PREMOTE PMAIN PREMOTE I - PEND/D __ D(I+NR) QUEUE REMOTE PEND/D COMPUTER PDRC = I- PEND/D PRD = PREMOTE/(PMAIN + PREMOTE) D= I- PCORE (I - PEND) Figure 2-5 Remote Computer and Queue: Transformation III

C(~~D CD~~~~'';'Ili:z P-d.~~ 12~~~~

46 Figure 2-3 represents a merging of the two branching nodes from Figure 2-2 while Figure 2-4 is just a rearrangement of Figure 2-3. Using the identity shown in Figure 2-6 allows the transformation from Figure 2-4 to 2-5, which now is in direct correspondence with the model, so that if D = 1 - PCORE(1 - PEND), then PRDC = 1 - PEND/D, (2. 6) PRD = PREMOT/(PREMOT + PMAIN) (2. 7) tT t1 (2. 8) D(1 + NR) so that all the parameters are completely specified. 2. 5 Assumptions Various assumptions have explicitly and implicitly been made during the development of this model. Indeed, further assumptions will be necessary when the model is actually analyzed. At this point, however, only the former variety of assumptions will be discussed. The first of these is that the model requires that all remote computer pre- processing be finished before any information is sent to the main computer. This need not be the case; in a real system, information might be sent as it is extracted from the display file, and the main computer might begin processing received information while the remote computer is still processing as well. Other examples are easily seen. As a result, the response time as predicted by tho e model will e worse than might realistically be obtained from a system whose programmers make intelligent software design decisions to take advantage of any possible concurrent operations.

47 This is not as serious as it may seem to be, as a certain amount of concurrency is implicitly imbedded in the model. The most conspicuous example is that of sending or receiving data link messages. The actual transmission would be requested by an application program, but the word-by-word I/O operations would be handled either on an interrupt basis by the executive system, or possibly by a hardware block-transfer facility, while other application programs could be executing. Another assumption is that all actions associated with a particular service request must be completed before the user can ask for further action. A plausible counterexample is an application in which a user requests that a display be prepared for later offline plotting on a hard copy output device. In most cases there would be no logical reason that the ensuing computations not be performed in a low priority background mode of operation while the display console user proceeds with his graphical work. This assumption can be overcome by not including such cases in the estimates of computational requirements used to find the model's parameters. The basic structure of the model makes remote disk accesses in the pre- and post- processing operations impossible, while there is certainly nothing inherent in display applications to preclude the desirability of such actions. By eliminating the possibility of such accesses, the model will tend to underestimate the modeled system's response time if the system actually makes the accesses.

48 The model also allows only one level of bulk storage at the remote computer, specifically head-per-track disks or drums. This limitation is based on two premises. The first is that other reasonably priced bulk storage media which might be used at the remote computer (magnetic tape, for instance) are not as cost-effective as disks or drums, unless very large amounts (more than 800 or 1000 blocks) of on-line bulk storage are needed. The second is that if a large amount of on-line bulk storage is needed, there should still be included a disk or drum for storing the more frequently used files, to help maintain a reasonable response time. It has been explicitly stated that the estimated parameters forming the application specification are averages. To be more specific and more rigorous, suppose that a display application were actually implemented on a display system, and that the operation of the hardware were closely monitored. Now, if after a very long period of operation, the monitored information were analyzed, and the empirical probability distribution for each of the application parameters were found, the mean of each of the empirical distributions would be used as the corresponding application parameter. In the case of Pi, which is the probability of accessing storage file i, and ri' which is the probability that a service request is of type i is made, the probability distribution formed is just a count of the accesses and service requests, divided by the total number of accesses and service requests, respectively.

49 Using information gathered over a very long time span would insure that the mean of the empirical distribution would be very close to the true mean. That is, what is being sought in this way is the long term mean of a statistical process. The process is presumed to be stationary, although in practice this may not be so. For instance, a user's think time may in part depend on what portion of an application he is currently using. In an electrical network application, drawing a simple RLC circuit would probably require less think time per interaction than specifying a forcing function and the output(s) to be plotted. Similarly, differences can exist in the utilization of the remote computer and its memory devices during the different stages of an application. This is why the mean must be found from data taken over a long time span, so that all effects of this sort are taken into full account. This ensures that the means of the various empirical distributions will not be biased towards any particular phase of an application. Now obtaining data in the above manner is impossible until after a display system is installed and programmed, which is much too late to be of use in determining what type of display system to install and program. Accordingly, a further assumption being made is that the system designer is able to estimate all of the application parameters, using as an aid the above description of how the parameters would be found if it were feasible to do so.

50 A potentially important phenomenon not fully accounted for by the model is the reduction in "thrashing" which occurs as the amount of remote computer core storage increases. Thrashing occurs to some degree or another when not enough core is available to load a program to be executed, so that it must be loaded piece-by-piece as needed, with the strong possibility that some pieces be loaded many times before execution ends. Thrashing is reduced markedly by increasing core storage. In the model, bulk storage accesses are reduced by increasing core storage because the more active files can then be kept in core. However, there is no explicit mechanism to account for the thrashing reduction which occurs when enough core working area becomes available to hold in its entirety any program which might be initiated by a user interaction. This can be accomplished by making estimates of N.R large enough to reflect the thrashing which can occur at the remote computer, and by adjusting PACESS(.-) so that the first few file blocks have extremely high useages. Then the addition of the first few blocks of core storage will cause a large decrease in bulk storage accesses, as occurs when thrashing ceases to be a problem. Another assumption is that the main computer is not needed when the remote computer accesses the main computer's bulk storage. While this is not really true, the processing time needed will be small when compared with the storage access time, and is consequently neglected, thereby reducing the response time estimate.

51 Why have these assumptions been made? Why can't the model be bigger and more sophisticated so that the assumptions aren't needed? For several reasons: the most important is that as tile model becomes larger and more detailed, more and more must be known about the fine details of an application to determine the model's parameters. The model as it exists now is already quite detailed, and is rather demancding in what must be known about the display system application; asking for even more application parameters is most unreasonable and unrealistic. A second reason for limiting the model's size is limitations of the available analysis tools, i. e., as the model acquires more detail more computer time is needed for analysis. Because the model will be analyzed many times, the time for a single analysis must be kept within reasonable bounds. That is, a tradeoff exists between the model's complexity and the computer time needed for its analysis. A relatively simple model has been chosen, so that many points in its parameter space can be examined. An excellent example of the converse choice is work done by Nielsen [431, which uses a highly detailed model of the IBM 360/67 and TSS to predict user response time and system loading. Because of the model's detail and resulting long analysis time, only a single very haphazard optimization was possible. A final point is that the more detailed the model, the fewer will be the display applications which can be represented with the

52 model. Embedding more detail in the model will necessarily begin to bias it toward a particular class of application or computer operating system. This is undesirable. It is believed that the model contains enough detail to reflect the critical differences between applications, yet not so much detail as to scare off potential users. 2. 6 Cost The total cost of the display system includes the hardware's cost, plus the cost of whatever processing is done by the main computer bulk storage used by display system files. Cost is considered in terms of monthly rental charges, because some of the equipment must be leased rather than purchased. Equivalent rentals for purchased hardware are found by amortizing the purchase over 40 months, which is a commonly accepted depreciation period among computer purchasers. To find main computer usage costs, two quantities are here defined. CPUCST - central processing unit cost per month to the display console user if the display system were trying to use the main computer 100% of the time that the display system is in use. CPUCST will be lower for the nonpriority case than for the priority case; in the latter, the display system would actually use the main computer whenever needed, while in the former, because of competition from other jobs, a smaller

53 utilization would be attained. The exact decrease in CPUCST caused by competition from other jobs must be estimated or measured. PAGCST - the page, or file block, storage cost per month for files stored at the main computer. Now if F is the fraction of time the display system is in use that it actually tries to use the main computer. c(X) Total System Cost = Hardware Cost + (F)(CPUCST) + (PAGCST)(MAXPAG - X2 - X3). (2. 9) Also, C'(X) = Hardware cost + (PAGCST)(MAXPAG - X2 - X3). (2. 10) C'(X) represents those system costs which can be found without actually analyzing the display system model. That is to say, (F)(CPUCST) has been eliminated because F cannot be quickly determined when there is more than one display console sharing the display system. Hardware cost is the sum of monthly charges for the data link, remote computer core and bulk storage, and the remote computer -display control (including the display consoles), It is important to note that C' is a monotonic increasing function of X as long as the hardware cost of adding either a core or bulk storage page to the remote computer is greater than PAGCST. This will be the case because of economies of scale associated with bulk storage used at

54 the main computer. C' is also nonlinear - linear relations between computer equipment prices and their capabilities seem to be nonexistent. 2, 7 Analysis As mentioned at the beginning of this chapter, the display system model presented here will be used to determine system response time for user service requests. This response time is just the average time delay from when a users request for service is entered into the system using one of the display console's input devices until the service has been completed, results displayed, and the user permitted to request further service. If Ti, il, 2,..., 11 is defined as the average total time in queue for server i, including the actual service time ti, then it is clear that the response time T is just a weighted sum of the Ti's. That is, the weights will just be the average number of times per interaction that each server is used during the completion of a user's request. That is, if server i were used on the average twice per interaction, its contribution to the total average response time would simply be 2 T.. Average response time, as can be determined from Figure 2-2, can be written as T - TM(PM) + TR(1 - PM), (2. 11) where M T8 T9(PD) T =T6+ T7 + 1~I-D-PD + T10+ T11 (2.12)

55 is the time needed when the main computer is used for processing, and R T1 PDRC T (RD+ T + T D)T + + T5 )(1-PRD (2 13) is the time needed then the remote computer is used for processing. Equation 2. 11 simply applies the appropriate weights to the average processing times of the main and remote computers. If the main computer is used for processing, servers 6 7, 10 and 11 are each used once. Therefore T6, T7, T10, and T11 all have unity multipliers in equation 2. 12. However, the main computer and its bulk storage are used more often. The number of times the main computer is used is given by 1 + PD + PD2 + PD 3+.. 1PD Similarly, the number of uses of the main computer's bulk storage is given by PD + PD( + PD+ PDP +... ) = PD 1-PD This accounts for the multipliers of T8 and Tg. i -P 9PDRC In equation 2. 13, the multipliers 1-PDR and 1 PDRC - PDRC a -PDRC are found using the same infinite series, and applied to the remote computer's throughput time and its bulk storage system's throughput time, respectively. The bulk storage throughput time is in turn a weighted sum, with the weights PRD and 1-PRD applied to T2 and T3 + T4 + T5, respectively, reflecting the probability of their usages. Functionally, response time can be expressed as T(R, X, Z), with R, X, and Z defined below.

56 R - number of active display consoles attached to the remote computer. R > 1. X - (X1, X2, X3, X4) = description of hardware used in display system, where X1 indicates data link transmission rate; X2, core storage used at the remote computer; X3, bulk storage used at the remote computer; and X4, instruction execution rate for the remote computer-display control. Z = (z1, z2,. o Zn) = description of application implemented by the display system. It will not be necessary to associate each z. with a particular application parameter, nor to define n. It is important to note that for any two integers r! and r2 such that r < r2, then T(r, X, X, Z) T(r X, Z). This is really a formalized statement of the obvious, i. e., increasing congestion in the system (increasing the number of system users) also increases response time, all else being equaL A specific and useful instance of this occurs when r = 1, r2 > 1, for then T(1,X, Z)< T(r2, X, Z), or T(1, X, Z) < T(R, X, Z). That is, T(1, X, Z) is a lower bound on T(R, X, Z). We thus define T(1, X, Z) TL(R, X, Z). (2. 14) This result will be used in a later chapter.

57 Also notice that T is nonlinear in the variables X1, X2, X3, and X4. This will be important in formulating the display system optimization problem in Chapter IV. Two other results will also be needed: they are presented in the following two sections. 2. 7. 1 Assignment of Interactions An assignment algorithm which is both simple and reasonable is used to assign interactions to either the main or remote computer for servicing. Define T. as the time that would be required to process a type i interaction if it were assigned to the main computer and T.R as the time that would be required to process the same interaction if it were assigned to the remote computer, when just one disM R play console is in use. T. and T. are easily evaluated. Recall that I 1 for interaction type i, N. display instructions must be executed, and either B.M main computer or B.R remote computer bulk storage 1 1 accesses must be made. Then, by direct analogy with equations 2. 12 and 2. 13, and for R = 1, M t8 t9(PD) T t6 +t7 PD -PD + t + t B.M with PD - and 1+ B1 R tl PDRC i T 1-PDRC + 1-PDRC L t(PRD)+ (t + t + t )(1 -PRD] R with PDRC= - 1+ B.R I

58 An interaction of type i is assigned to the main computer if T.M < T.R; otherwise, the interaction type is assigned to the remote 1 1 computer. Clearly this assignment minimizes response time for the single user case, and consequently will be called the optimum assignment. Any other assignment will result in longer response time, and will be suboptimal by the definition being used here. There are, naturally enough, other definitions of optimal which might be used. Specifically, the current definition does not consider the costs associated with servicing interactions at the main or remote computer. In reality, assigning an interaction type to the main computer will be more expensive than using the remote computer, because the incremental cost of using the remote computer more is zero, while for the main computer it is very definitely positive. This suggests that before assigning an interaction type to the main computer, a relationship such as T.M(1+K) T. or T.R+ K < T.R should be satisfied, where K is some carefully selected positive constant. But now, of course, this introduces an additional parameter into the optimization: a parameter whose proper value is not at all evident. To avoid this additional complexity, then, the main computer will be used whenever T. < T. Thus, in fact, a design decision has been made. 1 1 It must be noted that the assignment does not take into account the data base distribution between the main and remote computers. For instance, it would be foolish to store data at the remote computer if the data is used only by programs at the main computer. Therefore

59 the questions of processing assignment and data distribution should be treated together. This has not been done here because of many additional complexities which would arise, and because an unreasonable amount of extra application information would be needed. When several consoles are active the assignment found as described above is not necessarily optimum, because T.M and T.R 1 1 evaluated for one user do not account for the queueing which can develop with multiple users. The problem is that evaluating T.M 1 and T.R for service request type i with several active users is difficult from a theoretical viewpoint and impossible for practical reasons. In the former case, the assignment of all service requests other than i would have to be known (or assumed) so that the computations needed by request type i would be delayed by the appropriate amount of congestion, whether they were done by the main or remote computer. Presumably, some iterative scheme could be developed using something of a trial-and-error approach to the assignments. In the latter case, as a practical matter, the actual evaluations would be so demanding of computer time as to create an impossible situation. Thus, although the assignment algorithm presented may not, in fact, produce optimum results for the multi-user case, it is the best that can be done. 2. 7. 2 Monotonicity of T To demonstrate the desired monotonic nonincreasing property of T with respect to each component of X, it will be necessary

60 to show that the partial derivatives of T, X. i=1, 2, 3, 4, are less than or equal to zero for positive X.. Turning first to X1, the data link transmission rate, it is MSGLTH known from Section 2. 4, equation 2. 1, that t3=t5=t7=t10- (X1)(TRIP/100) Furthermore T3 is related to t3 in such a way that a decrease in t3 at3 MSGLTH causes a decrease in T3. Now, - (X( (TRIP/ aT3 so —X1T is also negative. The same is true for t5, t7, and t10. Using equations 2. 11, 2. 12, and 2. 13, aT _ _7 aT10 PRDC aT3 aT = (PM)(a + + (IPM) DC )(1-PRD)( + 5 axi - aX1 ax 1 -(-PDRC ax1 ax 1 (2. 15) Now each of the four derivatives in equation 2. 15 is negative, so aT ar is negative. Continuing with X2, the size of the remote computer's core storage, the derivative of T is again found using equations 2. 11, 2. 12, and 2. 13. It is aT R a x2 = (1-PM)N (T2 - T3 - T4 - T5) X2 PACESS (X2 + X3 - SYSPAG) (2. 16) The derivative of PACESS (#) is positive, because increasing X2 increases PACESS (.). Thus, in order that 2. 16 be nonpositive, the inequality T2 < T3 + T4 + T5 must be satisfied. This is nothing more than requiring that the remote computer's bulk storage, including

61 queueing delays, be faster than the sum of data link transmission times and access to the main computer's bulk storage, including queueing delays. If this were not the case, there would be no justification for remote bulk storage, because using the main computer's bulk storage would be faster. There is, in fact, no difficulty satisfying the inequality, because the movable head disk pack storage units used at the main computer are considerably slower than the head-per-track disks which would be used at the remote computer. Thus, equation 2. 16 is nonpositive, and T is monotonic nondecreasing with with respect to X2. Turning now to X3, which is the size of the remote computer's bulk storage, equations 2. 11, 2. 12, and 2. 13 yield aT PDRC aPRD X3 = (1-PM) 1PDRC (T2 - T3 -T4 -T5) aX3 (2. 17) Now PRDX3 is positive, because increasing the amount of bulk storage inc reases the probability of its use, which is what PRD happens to be. But, as required in the preceding paragraph, T2 < T3 + T4 + T5, so that T2 - T3 - T4 - T5 is nonpositive. Therefore, 2. 17 is also nonpositive, so T is monotonic nonincreasing with respect to X3. Finally, turning attention to X4, first recall the two equations NPPPC t6 t X4, and (2. 2) tT D(1 D(1.~ ~~~~~~~( 8)

62 Using equation 2. 3 with 2. 8 yields R. N. t D1 1 i SR (2. 18) D(1+N ) (1-PM)(X4) Differentiating, at 7v.N. a11 1 R 1a -1 X iRi 2 i e S (2. 19) D(1+NR ) (1-PM)(X4) Just as T decreased when t3 decreased, so too with T1 and at1 aT1 t1. Therefore, since aX4 is negative, so is aX4' Also, differentiating 2. 4. 2 at at t6 11 NPPPC aX4 aX4 (X4) As was the case with T1 and tl, so with T6 and t6, and T11 and t11. aT6 aT11 Thus, aX4 and ax4 are negative. Now, again using equations 2. 11, 2. 12, and 2. 13, aT aT6 aTT 1 -PM T (2: PM ( + - >) + -— (2. 21) aX4 aX4 aX4 + -PDRC ax4 Each of the derivatives on the right of equation 2. 21 is negative; there - fore aX4 is negative and T is monotonic nonincreasing with respect to X4. The conclusion to be drawn from all this is that, since equations 2. 15, 2. 16, 2. 17, and 2. 21 are all nonpositive, T is monotonic nonincreasing with respect to each component of X = (X1, X2, X3, X4).

63 This means that whenever additional hardware is added to a display system, the system's response time will not increase.

Chapter III ANALYSIS METHODS In the preceding chapter a mathematical model of a display system was presented. The model attempted to abstract and solidify the essential salient characteristics of display system operation. The model in and of itself is not particularly useful, however, unless some helpful and pertinent results can be derived from it. In Section 2. 7 a closed-form solution for average response time with no queueing was developed. In this chapter two ways to find the average response time when queueing develops so that there is competition for the use of system resources will be discussed and compared. 3, 1 Simulation A simulation of a system or an organism is the operation of a model or simulator which is a representation of the system or organism. The model is amenable to manipulations which would be impossible, too expensive or impractical to perform on the entity it portrays. The operation of the model can be studied and, from it, properties concerning the behavior of the actual system or its subsystem can be inferred. [49 p. 9091 With this broad definition as a base, the definition of simulation can be further narrowed to the field of computer-based Monte Carlo analysis [10, Sec. 5. 41. A model, manifested as a computer program, is designed to act like a real system. The probabilistic, or stochastic, nature of the real system is reflected by use in the model of a random number generator. By conducting many trials, or simulations, statistics can be gathered concerning operation of the system. 64

65 Clearly a common question which must arise in simulation concerns the number of trials needed to give reliable results. If enough trials are performed, Bernoulli's law of large numbers can be invoked to guarantee that the simulation results are convergent to values truly representing characteristics of the model. The computer program needed to simulate a real system can be prepared in two ways. An assembler or compiler language can be used to write a program tailored to the particular system at hand This can be time consuming, and can result in an inflexible program in which subsequent system modifications are difficult to represent. However, the program can be tailored to the system being simulated, and thus should take less computer time for execution than a program prepared by other means. The second way to prepare a simulation program is by writing it in a simulation language. Such a language can resemble either assembly or compiler code. A variety of general purpose simulation languages are reviewed in a reference [551. While these languages are not necessarily easy to learn, once mastered they are easy to use, and can readily be made to reflect changes in the real system. This flexibility is obtained at the expense of greater computer time requirements than for special programs written to simulate a specific system.

66 3. 2 Markov Analysis Markovian analysis techniques, of which queueing theory is an important portion, are based on a well-developed mathematical framework. Of specific interest here is the mathematical entity called a continuous parameter Markov chain, which is described by Parzen [44]. In order that Markovian analysis be applied to the display system model, several restrictions must be applied. First, all service time distributions (for the computer, data link, etc. ) must be derivable from the simple negative exponential distribution. This then includes the hyper-exponential distribution. Second, the various branches in the flow of a job through the model must be strictly random (probabilistic), made without regard to where the job has been, or how many times the job has made the branch previously. If these restrictions are satisfied (how well they are or are not met is discussed later), the system's response time can be found using Markov analysis. This is accomplished by using the Recursive Queue Analyzer (RQA), a computer algorithm developed and implemented by the Systems Engineering Laboratory. [59, 60] 3. 3 Qualitative Comparison of Simulation and Markov Analysis Both simulation and Markov Analysis have good and bad features. Simulation and simulation languages can be very general, in terms of the allowable structure of a system, the service time distributions which can be specified, and the types of branches which

67 can be modeled. As mentioned in the previous section, Markov analysis is very restrictive of the permissible branches and service time distributions which can be modeled. Offsetting these restrictions, however, is the short computing time needed by RQA to analyze a queueing system. Specifically, when compared to GPSS (General Purpose Simulation System), the simulation language available at The University of Michigan, RQA needs between only 6 and 18% as much computer time to analyze the same system. The time factor is very important when conducting parameterized studies or performing an optimization (as will be done in this case), because the system model is analyzed not once, but many times. In addition, Markov analysis need not be concerned with the period and correlation coefficients of random number generation techniques, as is simulation [47, pp. 109-1111. Indeed, simulation results can fail to converge to the correct point as a consequence of an inappropriate random number generator, whereas Markov analysis and its embodiment in RQA are theoretically guaranteed to converge uniquely under certain non-restrictive conditions [60, pp. 6-71, and these results will be correct whenever the modeled system does in fact satisfy the assumptions presented in the previous section. 3. 4 Quantitative Comparison of Simulation and Markov Analysis What if a system is analyzed with RQA even though the necessary assumptions are not satisfied? Are the results still usable, or

68 must simulation be employed? Certainly the computational efficiency of RQA is an excellent motivation for attempting to extend its usefulness in the manner suggested by the preceding two questions. How is the appropriateness of RQA analysis for non-Markovian systems investigated? There are unfortunately no useful theoretical tools available: the alternative, but less satisfactory course of empirical investigation must be taken. This course is less satisfactory because no general statements can be made concerning when RQA can and cannot appropriately be used. Only statements about specific instances can be made. Thus it is necessary to analyze the display system model with RQA and GPSS for a set of typical parameter values, and carefully study the results. Tables 3-1, 3-2, and 3-3 present the results of many such RQA and GPSS analyses. For each analysis the long term average service rates and branching probabilities are the same; the corresponding probability distributions, however, are not the same. That is, the display system model has been analyzed several times with GPSS. Each analysis has used different service time distributions and branching distributions; only their averages have remained unchanged. In most cases the distributions do not satisfy the restrictions needed for a Markov analysis with RQA. Despite this, the averages for the various distributions have been used for a Markov analysis of the same model, but with the required negative exponential service time distributions and probabilistic branches.

69 d o CI) a)C, 1 GPSS Deterministic Probabilistic 878 -1. 6 1 GPSS Deterministic Deterministic 854 -4. 3 1 GPSS Uniform Probabilistic 884 -0. 9 1 GPSS Uniform Deterministic 885 -0. 8 1 GPSS Exponential Probabilistic 857 -3. 9 1 GPSS Exponential Deterministic 854 -4. 3 1 RQA Exponential Probabilistic 892 0. 0 1 Calculated from TL(R, X, Y) 892 0. 0 Table 3-1 Analysis Results for One User (R=1)

70 a), s - a~ ~rJ >-)c rCn rl Q 0 Q 0 a) 2 GPSS Deterministic Probabilistic 996 -3. 9 2 GPSS Deterministic Deterministic 1001 -3. 4 2 GPSS Uniform Probabilistic 1019 -1. 6 2 GPSS Uniform Deterministic 1019 -1. 6 2 GPSS Exponential Probabilistic 1028 -0. 7 2 GPSS Exponential Deterministic 1034 -0o 1 2 RQA Exponential Probabilistic 1035 0. 0 Table 3-2 Analysis Results for Two Users (R = 2)

71 rn o E o E ~.X - Cl) CrC l) -.aa Cl) Cl) - a) ~). QY 3 GPSS Deterministic Probabilistic 1138 -6. 1 3 GPSS Uniform Probabilistic 1179 -2. 7 3 GPSS Uniform Deterministic 1187 -2. 1 3 GPSS Exponential Probabilistic 1229 +1. 4 3 GPSS Exponential Deterministic 1223 + 0. 9 3 GPSS Hyperexponential Probabilistic 1264 +4. 3 3 GPSS Hyperexponential Deterministic 1288 +6. 3 3 RQA Exponential Probabilistic 1212 0. 0 Table 3-3 Analysis Results for Three Users (R = 3)

72 Figure 3-1 illustrates the four types of service time distributions used, and Figure 3-2 illustrates the two distributions used for branching processes. The branches following completion of a remote computer and main computer processing intervals are the only branches to which the deterministic distribution was applied. Also given in Figures 3-1 and 3-2 are the means (m) and standard deviations (a) for each distribution. Note that a varies from 0 (deterministic) to 2m (hyper-exponential) for the various service time distributions, thus covering a wide range of variability. The important results are in the column headed "Percentage Deviation from RQA Analysis" of the three tables. Here can be seen that for exactly the same system, with exponential servers and probabilistic branches, the difference between RQA and GPSS analysis varies from -3. 9%to +1. 4 %. This is essentially an error built into the analyses techniques by factors such as RQA's convergence error [60, pp. 7-81 and GPSS's linear interpolation and truncation vis-a-vis continuous functions [27, p. 281. Very little of the GPSS error can be attributed to an insufficient number of samples: Table 3-5 shows that after 10, 000 interactions with the display system had been simulated, various statistics obtained from the simulation converged nicely. As can be seen from the first three tables, the deviations for all cases are quite small, the worst being 6. 3% It is thus very reasonable to conclude that for this model, and for parameter values of the order used in the model and given in Table 3-4, it is appropriate

73 I.O P[t _ T] l =O 0.0 m T (a) Deterministic Distribution 1.0 P[t S T] / m 0.O. m T (b) Uniform Distribution 1.0 P[ <T] o'=m 0.0 _ m T (c) Negative Exponential Distribution 1.0 P [t< T] = 2m 0.0... m T ( d ) Hyperexponential Distribution t = Service Time Figure 3-1 Service Time Distributions

74 1.0 m=n P[n<N] o| 0O 0.0 n N 1.0 I-p P [nN] mP I-p 0.0. p p= Probability of Not Accessing Bulk Storage n= Number of Accesses to Bulk Storage Before Service Complete Figure 3-2 Branching Distributions

75 t = 150 msec. t2 = 300 msec. t3 = 100 msec. t4 = 90 msec. t5 = 100 msec. t6 = 50 msec. t7 = 100 msec. t8 = 400 msec. t= 90 msec. t10= 100 msec. t = 50 msec. PM =.5 PDRC =. 5 PRD =. 5 PD =.5 Table 3-4 System Parameters Used for RQA and GPSS Analysis

76 a) a) r-4 a 400 7 163.,4.0 z~ 0 0 0 0 6000 786 163 67 38 8000 786 163 66 38 10000 788 163 66 39 Table 3-5 Convergence of Simulation Results Convergence of Simulation Results

77 to substitute a short inexpensive RQA analysis for a longer, more expensive GPSS analysis, even though the model being analyzed may not always satisfy the conditions for RQA analysis. Similar conclusions for another mathematical model are reported in a reference [201. These differences in average response time are small because of the relatively low level of congestion and queueing in the model, even with three users (Table 3-3). With little queueing, the response time just is not sensitive to changes in second order statistics of the service time and branching distributions. If there were more queueing, the differences in response times would be larger, so that use of RQA might not then be justified unless it were known that the various distributions satisfied the Markov requirements. However, in the work which follows, it is possible to use only RQA for analysis.

Chapter IV OPTIMIZATION PROCEDURE The goal of this chapter will be to develop an optimizatbn procedure which, together with the previously introduced display system model, can determine which one of many display systems is best for a particular application. The model, when analyzed with the Recursive Queue Analyzer (RQA) as discussed in Chapter III, gives a prediction of response time for a specific display system. The optimization procedure, by judicious use of RQA, will find optimum display systems. An optimum display system is one which minimizes response time, subject only to a dollar cost constraint. In Section 4. 1 the exact nature of the optimization is examined, while Section 4. 2 presents the actual optimization algorithm. 4. 1 Problem Formulation The optimization problem being confronted here is one in four dimensions, corresponding to the four subsystems of a display system, namely the data link, the remote computer's bulk storage, its core storage, and the remote computer-display control. Associated with each of these subsystems is a variable. These are denoted X1, X2, X3, and X4, as defined in Section 2. 2, and are collectively designated as X= (X1, X2, X3, X4). Four functions of X have been defined. They are C'(X) (equation 2. 10), the monthly hardware and main computer storage costs for a display system; C(X)(equation 78

79 2. 9), the total monthly costs of a display system; TL(R, X, Z) (equation 2. 14). the lower bound on system response time; and T(R, X, Z), (equation 2. 11), the system's actual response time. Also, R is the number of active display consoles attached to a remote computer, X is a vector describing the system's hardware, and Z is a vector describing the system's application. In Section 2. 6, C'(X) was shown to be monotonic nondecreasing with respect to each component of X under very mild restrictions. T(R, X, Z) was demonstrated in Section 2. 7. 2 to be monotonic nonincreasing, also under reasonable restrictions. Thus the situation is such that decreasing response time increases cost, and vice-versa. This is clearly the basis for an optimization. The manner in which the optimization is approached must be very strongly influenced by the amount of computer time needed to calculate a display system's response time. That is, when more than one display console is serviced by a remote computer, the Recursive Queue Analyzer (RQA) must be used to find response time. While RQA is faster than GPSS, as discussed in Section 3. 3, it is still time consuming. A single analysis of the display system model can take as much as 40 seconds of CPU time and cost $3. 00. It is therefore necessary to devise an optimization algorithm which minimizes the number of response time evaluations, without compromising' in any way the final solution's accuracy.

80 While seeking out a convenient way to handle the optimization, it is necessary to determine if it should be performed in the domain of discrete or continuous variables. A bit of thought reveals several very persuasive arguments favoring discrete variables. First, the optimization is meant to deal with real currently available subsystems. There is not available a continuous spectrum of data link speeds, memory sizes, or computing powers. Rather, only very specific capacities can be procured, and this will be just as true in the future as it is now. A second consideration is the nonlinearity (Sections 2. 6 and 2. 7) of the functions being dealt with. If they were linear, the problem could be solved using continuous variables and linear programming, and then rounding up or down elements of the solution in various combinations to find an optimum. But because of the nonlinearities there is absolutely no guarantee that this method, used here, would yield an optimum solution. Thus it seems best to approach the discrete optimization head-on. This can be done in one of three ways. The first is to minimize cost while imposing a constraint on response time, the second is to minimize response while constraining cost, and the third is to minimize some function of both cost and response time. Of these three, only the second can be considered as satisfactory because it permits an implementation which minimizes the number of times RQA must be used, if the cost of C'(X) rather than C(X)

81 as a cost constraint is satisfactory. This must be accepted, because determining C(X) first requires use of RQA, which is not realistic to do, as C(X) would be evaluated quite often, and using RQA just once takes from 10 to 30 seconds of CPU time. In any event this issue is not of particular importance, because experience indicates that the difference between C(X) and C'(X) is quite small. 4. 2 Optimization Algorithm With this background material in mind, an appropriate optimization algorithm will be presented, the first part of which is an adaptation of work done by Lawler and Bell [411. Recalling that X = (Xl, X2, X3, X4), let each Xi be bounded such that O< Xi<Xi, -- - -:max where Xi is, in turn, exactly one less than a power of two. It max is not necessary that all Xi be equal. This bound is quite reasonmax able because in practice there are only a finite number of each subsystem available. Now let X be the binary vector formed by concatenating the binary representation of the Xi's, including leading zeros, if any. If Ximax = 15 for all i, and X = (5, 12, 9, 15), then X=(0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1). Eliminating the commas, this is written X = (0101110010011111). Four definitions are now made. Definition 1: Given X and Y, any four component vectors such that 0<Xi<Xi, and also given X and Y, formed - - max from X and Y as prescribed above. If each bit of X is less

82 than or equal to each bit of Y, then X<Y. This defines a "vector partial ordering" of X and Y. Example: (1011011) < (1111011), and (0111011) (1011011). Definition 2: If V = (v1, v2,..., vn) is a binary vector, n-i n-2 then the numerical value of V, n(V), is v12 n-1+ v22 + +v 2. n Example: If V = (1011001), n(V) = 64 + 0 + 16 + 8 + 0 + 0 + 1 = 89. Definition 3: If the numerical value of X is less than or equal to the numerical value of Y, n(X) < n(Y). This defines a "numerical ordering" of X and Y. Example: n(111001) < n(111100), and n(1100101) n(0111010). Note: X < Y ==> n(X) < n(Y). Definition 4: If Y is such that n(X) < n(Y) but X~ Y, and there exists no other vector, say Y', for which n(Y') < n(Y) and X<Y', then Y will be called X*. That is, X* is the first vector numerically larger than X which is not also larger in the vector partial ordering sense. Example: If X = (0101100), X* = (0110000). If X = (0101011), X* = (0101100). This X* can be readily computed by taking the bit-by-bit logical'or' of X with X-l, and then adding 1, with the exception

83 that if X = (00... 0), X* = (00 o 0. 1). Addition and subtraction on the vector X is handled by performing the operation on n(X), and converting back to a vector. Lemma 1: By definition 4, X* is the first vector numerically larger than X which is not also larger in the vector partial ordering sense. Therefore X* - 1 is larger than X in the vector partial ordering sense. Just as X is derived from X, there is also an X* from which X* derives. The same is true for X* - 1. Having said this, the following theorem, adapted from reference 28, can now be stated and used. Theorem 1 If X = (X1, X2, X3, X4) and X*-1 = (X1', X2', X3', X4') then Xi< Xi' for i= 1, 2, 3, 4o Proof: By Lemma 1, it is known that X<X*-1 in the vector partial ordering, and therefore that each bit of X is less than or equal to the corresponding bit of X*-lo Now each Xi and Xi' is represented in binary form as a sequence of corresponding bits in X and X*-1, respectively. Let these sequences be denoted as u. and vi, respectively. Then 1 1 each bit of u. is less than or equal to the corresponding bit of vi, so that n(ui) < n(vi). But Xi = n(ui) and Xi'=n(vi), so that Xi< Xi', for i=1, 2, 3, 4.

84 Associated with Theorem 1 is Corollary 1: C'(X) < C'(X*-1), and T(R, X, Z)> T(R, X*-1, Z). Proof: C'(X) and T(R, X, Z) are monotonic nondecreasing and nonincreasing, respectively, with respect to each component of Xo From Theorem 1 it is known that each component of X is less than or equal to the corresponding component of X*- 1. This corollary is useful in the algorithm of Figure 4-1. With C' an upper limit on C' (X), the purpose of this algorithm, max which is just a portion of the entire optimization, is to find a set S of vectors, such that if C'(X*-1) < C'max then X*-1 e S; if not, but C'(X) < C'max, then X e S. Thus, every vector in S is feasible (that is, for Y e S, C'(Y) < C' ), but not every feasible vector - -max is in S. For instance, if X= (011000000000) and X*-1=(011111111111) and X*-i is feasible, none of the hundreds of vectors (all of which are feasible) in the vector partial ordering between X and X*-1 will be in S; only X*-1 itself will be. This can be done because T(R, (011111111111), Z) is known to be no greater than the response time obtained from display systems represented by any of these intermediate vectors, and it will, in fact, usually by less. Thus it is seen that the algorithm in Figure 4. 1 depends for its success on the number of vectors falling between X and X*-1 when X*-i is feasible. The more intermediate vectors there are,

85 Figure 4-1 Formation of the Set S

86 START X=(000000...O) x T F C'(X) < C' — >....- - max X = XI'~;i- [= X* - i PUT X INTO S ~T ~IF Figure 4-1

87 the smaller will S be. However, if X*-1 is not feasible, the interval between X and X*-1 must be reduced to smaller intervals and searched. The definition of X* used here gives a reasonable balance between successfully eliminating large intervals of vectors and efficiently conducting a finer search over intervals which cannot be eliminated. There is another definition of X* which would be equally suitable here, and which might provide an even more efficient search. It is obtained by redefining vector partial ordering and numerical value. Define X < Y if Xi < Yi, i = 1, 2,..., 4. This is the vector partial ordering. Also, define n(X) = X1(M 3) + X2(M2 ) + X3(M 1) + X4(M ), with M = max fXi}. This is the numerical value. Now with these redefinitions, Definition 4 for X* can be used, with the result that if: X= ( 1, 0 0), X*= (1, X2 X3 ax X4ma) X= (3, 6, 5, 1), X*= (3, 6, 5, X4max) X= (3, 6, 5,0), X*= (3, 7, X3, X4 ). max max The usefulness of this alternate definition has not been explored, because no matter what definition of X* might be used, the following step in the optimization will yield the same result. Now, if nothing else were known about the problem, the optimum solution could be found by an exhaustive search with RQA over the set S, whose elements are feasible solutions. This in

88 itself is far better than searching over all feasible solutions with RQA. However, further improvements can be made. Specifically, the next theorem further exploits the monotonicity of T. Theorem 2: If, for X, V E S, Xi < Vi for i=1, 2, 3, 4, then T(R, X, Z)> T(R, V, Z). Proof: In Section 2. 7. 2 it was shown that T(R, X, Z) is monotonic nonincreasing with each element of X. Then, since each component of X is less than or equal to the corresponding component of V, the monotonic property of T means that T(R, X, Z)> T(R, V, Z). Theorem 2 results in Corollary 3: If for X, V S, Xi < Vi for i = 1, 2, 3, 4, then X can be deleted from S. Proof: By Theorem 2, T(R, X, Z) > T(R, V, Z). Thus there is no reason to keep X in S, because the goal is to minimize T. By systematically comparing each vector in S to every other vector in S, and by eliminating vectors whenever appropriate, a new set S' can be formed, such that N(S')< N(S), where N () represents the cardinality of a set. The number of comparisons needed lies between [N(S)][N(S) - 11 and [N(S?) - 1]IN(st) - 2] + [N(S) - 1]. Given an arbitrary ordering 2 of S, the upper limit is found by assuming that no vectors can be eliminated from S. Then the first vector is compared to N (S) - 1

89 vectors, the second to N(S)-2, etc. This is just the finite sum [N(S)-11 + [N(S)-21 +... + [1] [N(S)[N(S)-]. For the lower 2 limit, assume that comparing the first vector to the N(S)-1 other vectors results immediately in reduction in cardinality to N(S'). Then the second vector in S' is compared to N(S')-2 vectors, the third to N(S')-3, etc., for a total of [N(S)-11 + [N(S')-2] + [N(S')-31 +.. + 1 = [N(S)-i] + [N(S)-[N(S)-2] 2 Once again, if nothing more were known about the problem, an exhaustive search of S' with RQA would be necessary. This could be a very time-consuming process. Still further improvements are possible. The algorithm of Figure 4-2 can now be utilized to find the vector in S' which minimizes TL(R, X, Z). TL(R, X, Z) is easily calculated, as RQA is not needed. Call this vector A. Unfortunately, A does not necessarily also minimize T(R, X, Z), unless R=i, in which case the optimization is complete. However, experience indicates that it often comes close to doing so. The optimization is completed with the algorithm in Figure 4-3. TMIN is set equal to T(R, A, Z). This gives a good upper bound on the true TMIN. RQA need be used only when TL(R, X, Z) < TMIN. If it happens that T(R, X, Z) < TMIN, then TMIN becomes T(R, X, Z) and A is replaced by X. Note that whenever T or TL is calculated, the interaction assignment procedure of Section 2. 7. 1 must first be performed. When 5' has been

90 START T F T F TMIN >TL(R,2i IOZ TLMIN =TL(R,S i, Z) A=Si i = i-FI Figure 4-2 Minimization for One User (R=l)

91.... i = I T F T.1 IN<TL(R'SI'Z) T F A=Si T MIN=T (R, Si, Z) ) Figure 4-i=i+l Figure 4-3 Final 1Minimnization

92 exhaustively searched, A represents the display system which minimizes response time for a cost C'(A) < C'max Appendix B presents a complete discussion of the optimization programs. In this procedure steps have been taken to make the initial value of TMIN as small as possible. This is because the smaller TMIN is, the less often will the use of RQA be called for. The statistics in Table 4-1 are indicative of the very real success achieved in using RQA as infrequently as possible. Note that the number of RQA runs is less than N(S'), which is, in turn, less than N(S), as is desired.

93 Total Number N(S) N(S') RQA Runs of Systems 1280 6 4 1 1280 704 26 3 1280 931 12 1 1280 159 5 2 1280 800 23 4 1280 874 13 3 960 3 3 1 960 190 17 2 960 706 6 1 640 2 2 1 640 138 16 2 640 379 14 1 640 156 16 4 Table 4-1 Optimization Statistics

Chapter V EVALUATION OF COMPUTING POWER A critical necessity in the optimization discussed in Chapter 4 is the creation of a suitable data base of hardware subsystems from which an optimal display system can be chosen. This can rather easily be done for all subsystems except the remote computerdisplay control subsystem for which not just computing power, but also display capability must be determined. Display capability must be known because not every display control can display the same amount of information. Only those able to display more than some minimum amount of information can even be considered for inclusion in a display system; this minimum amount of information is application dependent. Having eliminated unacceptable display controls, the remaining display control-remote computers must be rated according to their computational capabilities. In Section 5. 1 a method of evaluating the display capability of various display controls will be discussed. Section 5o 2 reviews past approaches to measuring computing power, while the next section builds on these approaches to develop a technique for measuring a remote computer-display control's power. Section 5. 4 combines the results of the preceeding sections, applying both computing power and display capability criteria to remote computer-display controls0 94

95 5. 1 Displayable Information Differing technologies, techniques, and design criteria have resulted in display controls with a wide range of display and computational capabilities. The intent in this section is to present a means of measuring display capabilities for comparative evaluation purposes. The evaluation can be performed in the manner employed by Adams Associates in The Computer Display Review [2]. The exact method is to define five different display test patterns which are intended to be representative of as many different applications, specifically, alphanumeric work, weather mapping, mathematical graphing, architectual drawing, and circuit analysis. A display control is rated in terms of the percentage of each pattern which can be presented flicker free. This will be denoted Qi' i=1, 2, 3, 4, 5. The resulting figures (some or all can be greater than 100o%) represent a quantitative rating of the display control. Figures 5-1 through 5-5 show the actual test patterns. To obtain a single rather than multiple rating for a display control, a weighted average of the five individual ratings can be taken, with the weights based on the relation of each test pattern to the application for which the equipment is being evaluated. The more typical of an application a test pattern is, the higher the weight. These weights, of course, must sum to unity. They will be denoted by, i=, 2,..., 5.

96 BURNER SYSTEM SYSTEM VALVES SYSTEM STATUS SYSTEM SIGNALS SUPERHEATER C *TRIPPED* STEAM PRESSURE N REHEATER C FURNACE PRESSURE N MAIN GAS SHUTOFF 0 GAS TEMPERATURE N VENT 0 COMBUSTION M MAIN OIL SHUTOFF C FORCED DRAFT FAN R RETURN C AIR HEATER 0 NORTH C SOUTH C IGNITOR CHARGED Y GAS READY Y IGNITOR SHUTOFF 0 VENT C OIL READY N DUAL PERMISSIVE N PENTHOUSE NO. 1 0 NO. 2 0 MODE SWITCH C VENT 0 PURGE REQUIRED Y BURNERS 1 2 3 4 5 6 7 8 9 10 STATUS - - S * * * I - - - IGNITOR FLAME - - TRANS - - - - - - - - - - SHUTOFF C C C C C C C C C C MAIN FLAME - - N F F F GAS SHUTOFF C C 0 0 0 0 C C C C OIL SHUTOFF C C C C C C C C C C UNIT 0 0 0 0 0 0 0 0 0 0 ATOM I I I I I I I I I I PURGE C C C C C C C C C C COOL C C C C C C C C C C DAMPER 0 0 0 0 0 0 0 0 0 0 CONTROL IGNITOR - - - - - - - - - - GAS - - X X X X X - - - OIL - - - - - DUAL - - - OFF X X - - - X X X Figure 5-1 Aipnanunieric Tcst Pattern CopyrigltL 1967, Adams Associates - Used lby Permission

97 Figure 5-2 Weather Map Test Pattern Copyright 1967, Adams Associates - Used by Permission

98 / - / )_ (D -c) \ ciV~)~~) \/ /z? 1 1.,.I 1, LL 0 0 0 0 0 0 0 0 In tq t0 q rq SVII0ioo JO SONVSfOHI Figure 5-3 Graph Test Pattern Copyright 1967, Adams Associates - User by Permission

99 BOILER FUEL C 4'O X 5'6 a 4'O0X5'2' 22'SO FT 21 SQ FT ~AUI.DRY,C. 0eBATHROOM 3'6% 5'1r6 3n W 1 42 SQ FT KITCHEN S o20 SO FT 20, SO FT? zrU CUP B OAR0 102 SO FT B 1'81 X 3Y2" PASSAGE ~ 5 SO FT 154 SQ FT HALL DININIG ROOM LIVING ROOM. 15 S 9'OmX 9'6' 13'6'X 15'6' 85 SQ FT 209 SQ FT 0 BEDROOM IO'O'X 14'6" ~~~~~~~~~~~N ] _ ~145 SQ FT TOTAL FLOOR AREA 8T5 SQ FT CIRCULATION 189 SO FT 22% Figure 5 —4 Architectural Drawing Test Pattern Copyright 1967, Adams Associates - Used by Permission

100 o, i I — Figure 5-5 Electronic Schematic Test Pattern Copyright 1967, Adams Associates - Used by Permission

101 In the case that none of the test patterns is really representative of the application, appropriate patterns can be generated and evaluated. Before taking this step, however, a second look at the test patterns is in order, because some of them may really represent an application quite well without using the application's terminology. For example, the weather mapping pattern, Figure 5-2, has a structure similar to that of both geographical or mathematical contour mapping, as well as sheet metal styling. Likewise, the circuit analysis pattern, Figure 5-5, is not unsimilar to certain mechanical analysis systems. If unhappily, it does become necessary to create new test patterns, their evaluation in terms of various display controllers is a simple, albeit tedious, task. All that is required is the generation of the list of display commands corresponding to the new test pattern, and a summation of the plotting times for each of the individual display instructions. If this time is Tp milliseconds, and the refresh rate needed for a flicker free display is f per second, then the percentage of the test pattern which can be displayed flicker-free is QTp = 100% (1000). Because most display controls (~,Tp have similar display commands, virtually the same display file can be used to evaluate many display controls. QTp is found here in precisely the same way that the ratings Qi were found, and is meant to replace the use of the Qi's when they are not applicable.

102 This analysis method is easily extended to cases where more than one display console is to be driven by a single display control. If the R display consoles which are to be driven all display the same information, there is no resulting loss of display control capacity on a per display basis. At the opposite end of the spectrum, when all R consoles present different information, each can, on the average, present just 1/R times the quantity of information presented with only one console. In general, for applications where only a fraction x of the information in each display is different, the displayable information per console becomes QR - (R-1)+ 1 (5. 1) where Q = E 2i Q i in the case that the Adams Associates test patterns are used, and Q = QTp if a new test pattern has been developed. 5.2 Computing Power - Historical Approaches Evaluation of the computational power of a display controlremote computer is a more difficult process than the preceding one. A wide range of capabilities exists in display controls, and an evaluation technique must cover all possibilities. For instance, hardware used by the Electronic Systems Laboratory at MIT includes hardware rotation, scaling, and pentracking capabilities [53], while most other equipment includes none of these facilities. Specifically, the evaluation must be sensitive to all hardware features which may

103 be implemented in the display control and remote computer, so that the hardware -software tradeoffs discussed in Chapter 1 can be quantitatively treated. Furthermore, it is necessary to evaluate the computational speed of the computer -control combination assuming that infinite core memory is available, thereby eliminating I/O delays. This is because the display system model which has been postulated in Chapter 2 treats I/O delays explicitly, rather than lumping them with computing time. It is also desirable, of course, that the evaluation technique be as simple as possible, while still being accurate and taking into account the application to be implemented on the remote display terminal. Many evaluation methods are available [5]. Perhaps the best known, and most controversial, is Grosch's Law [3, 33, 34, 35, 51], which states that within a group of technologically similar computers, computing power varies as the square of the computer's cost. This law has been proven and disproven several times in the past. Unfortunately, there still remains the necessity of evaluating the power of at least one computer as a basis for the law, and furthermore, there is no evidence that small computer-dispaly controls obey the law. A second problem is separating the cost of the logical portion of a display control from that of the deflection circuitry.

104 Both Knight [33, 34, 35] and Gruenberger [21] have proposed formulae which attempt to relate a computer's design characteristics to its processing power. The formulae, however, include variables such as the amount of core storage and I/O speed, which are not being considered here. Once again, also, another evaluation technique is required to verify the formulae's applicability. Benchmark [24, 301 problem testing is often the best evaluation method, because it involves actually running typical programs on real hardware. This is fine for existing systems with existing software, but virtually impossible for evaluation of proposed systems. The quandary of defining a typical problem can be very serious in scientific and graphical applications, so that this method must be discarded for these multiple reasons. Machine language instruction mixes provide an accurate evaluation technique, and are well-suited to comparing machines of similar design [5]. Difficulties arise when comparing machines with different word lengths, indexing schemes, and number of accumulators. This method is based on determining the frequency with which the various machine instructions are executed, and calculating the time required to execute a fixed number of instructions. Consequently, the machine's application can be accounted for by varying the instruction frequencies. The difficulties mentioned above, however, make this method unsuitable.

105 Another good technique, kernel problem comparisons, involves calculating the execution time for an algorithm deemed' typical of the computer's intended application [5]. This means producing an approximation to the machine code required to implement the algorithm, and a subsequent timing analysis which, for the case at hand, ignores I/O delays. The resulting execution time is then useful to the extent that the kernel problem is truly representative of the overall application. As with benchmark problem evaluation, defining a typical problem is easier said than done. The problem should exercise the various machine capabilities with the same frequencies which will occur in practice. While this may be easy for many business applications, it will probably be difficult for most graphical applications. In the next section a more satisfactory means of evaluating computing power will be proposed. 5o 3 Computing Power - Display Instruction Mix A combination of the machine instruction mix and kernel problem analysis, by bringing together the two methods' good points while minimizing their bad points, seems feasible. This proposed new method will be called the display instruction mix technique. The first step in its implementation is to define an exhaustive set of basic operations, named display instructions, which might be performed during a graphical man-machine interaction. These display instructions

106 are at a level higher than machine code, thereby removing the generality constraints implicit in the instruction mix approach, but still are at a low enough level so that their selection can remain independent of the data structure and executive system and not involve extensive machine language coding. Also, because there are many display instructions, a broad spectrum of display applications are representable with a good display instruction mix. Table 5-1 is one possible list of display instructions. A display application is characterized by a set of weights {wi} which sum to unity and represent the relative execution frquency for each display instruction. Now to evaluate the computing power of a particular display control-remote computer, machine instruction sequences are written to implement each display instruction, and their execution times T. calculated. Then the hardware's average instruction execution rate, defined as the variable X4 in Chapter 2, is given by X4 = (5. 2) i(w i.) This method does in fact require that some machine coding be done; most of it, however, will be very straightforward, and of course does not have to be debugged. What is needed, clearly, is a close approximation to the number of machine instructions

107 Initialize Display Start Display Check Status of Display Stop Display Insert x or Ax Insert y or Ay Insert sign Insert intensity bit Insert jump address Pentracking Rotation Translation Line blink Change Intensity Push jump Pop jump 10 bit addition 10 bit sbutraction 10 bit multiply 10 bit divide Address addition Address subtraction Test bits Set bits Shift (6 places) Save computer status Dispatch interrupt Restore computer status Set up teletype I/O Set up dataphone I/O Set up disk or drum I/O Set up paper tape I/O I/O Conversions ASCII to Integer ASCII to Display Code Integer to ASCII Ite rate Move a word Obtain current X and Y position Floating point (30 to 40 bits) Add Subtract Multiply Divide Table 5-1 Display Instruction List

108 required by each display instruction. Whether the instructions are completely correct is actually irrelevant. This method also requires that the weights {wi} be determined, which necessitates an excellent knowledge of the proposed display application and the manner in which a user will interact with the display console. As was first emphasized in Section 2. 3, the better these weights are estimated, the better will be the results produced by the display system model. Put another way, "You can't get something for nothing. " One of the nicest features of this method is the ease with which hardware features added to a display control-remote computer are accomodated. For example, if hardware light pen tracking is implemented, T. for tracking becomes zero, because no processing time is then taken to perform that function, and the instruction exe - cution rate for the equipment increases accordingly. And of course none of the other T's are affected. It is through this method that hardware-software tradeoffs are quantitatively treated. 5. 4 Final Analysis The purpose of this section will be to unify the evaluation techniques discussed in Sections 5. 1 and 5. 3. Using these techniques it is possible to evaluate any display control remote computer to determine its effectiveness with respect to a specific application. In addition, it will be possible to include in the evaluation configurations

109 with multiple consoles and display controls; specifically R consoles and N display controls, with N< R. The display controls will be constrained to be identical, which is certainly desirable for reasons of programming, interfacing, and maintenance. Also, only certain display control-remote computer configurations, called "balanced display configurations", will be acceptable. A balanced display configuration occur's when each display control drives an equal number of display consoles. Other configurations are termed "unbalanced". Figures 5-6 and 5-7 illustrate both cases for R = 4. Unbalanced configurations are not considered because they would normally not occur in practice for non-experimental systems. QR, the quantity of information displayable on R consoles has been defined by eqn. 5. 1. 1. Now for each display controlremote computer being considered, and for each balanced configuration, a characteristic 3-tuple (Cj, QRN., X4j )is formed. C. is the equipment's cost in dollars per month excluding core memory, QRN. is the amount of information displayed on R consoles using N display controls, and X4j is the instruction execution rate from equation 5. 2. It will be assumed that X4j is the same for a particular remote computer-display control, whether there be one, two, three, or four display controls used with the remote computer. This is not strictly true, because multiple display controls will tend to simplify some of the processing which must be done by

110 Remote Computer Display Controls CRT's (a) (b \ Figure 5-6 Balanced Display Configurations

CRT's Display Controls Remote Computer Figure 5-7 Unbalanced Display Configuration

112 the remote computer. Also, the effect on X4j of core memory cycle stealing by the display control has not been considered. The third quantity, QRNj, is found from equation 5. 1 with R replaced by R/N, because each display control drives only R/N display Q consoles. That is, QRN.= R for configuration j. X-N -1)+ 1 Certain of these 3-tuples can be eliminated from further consideration on the basis of cost-effectiveness and also for not meeting requirements. Let Qmin be the minimum acceptable information displayed per console for a specific application, based again on the method of Section 5. 1. Then for all display controlremote computer subsystems for which QRNj< Qmin' 3-tuple j must be discarded. Also, if Cj> Ci and X4.< X4., 3-tuple j is I J- 1 discarded because 3-tuple i describes a subsystem which costs less, yet has a higher instruction execution rate than subsystem j. If in addition it should happen that Cj Ci, X4. = X4., and QRN.< QRNi, subsystem j can be eliminated because subsystem i provides more display capacity for the same price. This algorithm is illustrated in Figure 5-8. Those subsystems remaining will be such that Ci> C.jX4.>X4.. This means that an increase in cost implies an increase in instruction execution rate. An example of such subsystems is given by Figure 5-9, for which x= 1, R= 3, Qu.= 60% with all five of the test patterns

113 START FIND(Ci, QRNj, x4j)FOR EACH REMOTE COMPUTERDISPLAY CONTROL HAVING REQUIRED NUMBER OF CONSOLES I=i OUTPUT ELIMINATE F,TUPLE i m o F =i+g I >Ciand xC4j x4i ELIMINATE 3-TUPLE j F nd QRNi >QRNj and Figure 5-8 Selection of Remote Computer-Display Controls

X5 O POINTS HARDWARE CONFIGURATION J.05 o~ I DEC 340 Display, PDP-8 2 DEC 340 Display, PDP-8, Hardware Multiply-Divide.04 - 3 DEC 350 Display, PDP-9,.X404 Hardware Multiply-Divide 4< I X4 DEC 338 Display (IncludesPDP-8), Hardware Multiply-Divide z 0 X 3 5 DEC 339 Display(IncludesPDP-9), -.03 Hardware Multiply-Divide L w o.202 X2 (n.01 I 800 900 1000 700 800 900 1000 MONTHLY COST PER CONSOLE, DOLLARS Figure 5-9 Example of Selected Remote Computer-Display Controls

equally weighted, and all w. equal. The specific hardware for each configuration is tabulated. Only DEC display units and computers were considered in this example. One of the subsystems found in this manner will be subsequently selected for inclusion in an optimal display system by the optimization algorithm presented in Chapter 4. A computer program, called PREPROCESSOR, has been written to implement the above procedure. This program accepts as inputs a description of many remote computer-display controls, and a description of a display system application. These descriptions are in terms of the parameters discussed in the preceding sections; Qi' i= 1, 2,.., 5;, i= 1, 2,..., 5; R; N; x; Ti, i= 1, 2,..., 42; and wi, i= 1, 2,..., 42. The output is in a form suitable for input to the optimization programs. A complete discussion of PREPROCESSOR is available in Appendix A.

Chapter VI APPLICATION In the preceding chapters several tools were developed. In Chapters II and III, a display system model was presented. The model can be used to predict the response time of a particular display system when certain characteristics of both the system's hardware and application are known or can be estimated. An optimization algorithm was developed in Chapter IV. This algorithm uses the display system model, along with a description of a display system's proposed application and a selection of hardware subsystems, to configure a display system which minimizes response time subject to a cost constraint. Finally, Chapter V describes a means of evaluating the large number of available remote computers and display controls so that only those which are ade - quate for a given application will be considered in the optimization. In this chapter these previously developed tools will be used to select optimum display hardware configurations for several diverse applications. The results of the optimizations will be useful in several ways. First, the wide range in system response time of optimal versus nonoptimal display systems will be illustrated. One of the motivations for the work reported here is that since this range exists, display systems' designs should be on the fast response side of the range. Second, the use of the tools in providing 116

117 cost-effectiveness information for use in selecting which or several optimum (for different costs) display systems to install will be shown. Third, it will be shown that using multiple display consoles per remote computer can result in lower per console cost with equal response times. Fourth, an attempt will be made to deduce from the results some general guidelines or statements which will be useful in and of themselves to designers of graphical display systems. One point which will be dwelt on is determining under what circumstances the use of special-purpose hardware for image rotation is justified. Finally, the division of processing between the main and remote computers will be discussed. 6. 1 Display System Hardware In this chapter, display systems will be designed by selecting four subsystems (data link, core storage, bulk storage, remote computer-display control) from among many alternatives. A set of four subsystems is represented by the vector X=(X1, X2, X3, X4). This section will describe the various possible subsystems and discuss their capabilities and costs. Mention of certain manufacturers' products in this and later sections is not to be considered an endorsement. The author has simply used as examples products with which he is familiar.

118 6. 1. 1 Data Link A broad spectrum of data transmission facilities are available from The Michigan Bell Telephone Company. Similar services are also available for interstate service over the nation-wide telephone system. The pertinent information concerning these services can be found in Table 6-1. Also included in the table is the total cost of a ten mile data transmission link. This link includes two modems plus the actual transmission line required. As can be seen, the lowest and highest transmission rates are separated by three orders of magnitude in speed, and by two orders of magnitude in cost. The optimization program uses entries in the "maximum bit rate/sec" column as X1, the data link transmission rate. 6. 1. 2 Remote Computer Core Storage Most small computers, such as those which will be described in Section 6. 1. 4, are capable of using up to 32, 768 words of core storage. The prices of additional core storage for Digital Equipment Corporation's PDP-8 computer have been taken as typical. On a monthly basis, the prices are approximately $250 for the first additional core modules (4096 12-bit words), and $200 for the remaining modules. This information is given in Table 6-2. Notice that at least the first four blocks of storage (equivalent to a core module) are always included in the display system; otherwise the remote computer would have no core storage at all, and could not

Approximate Transmission Total Monthly Modem Maximum Bit Modem Cost Line Cost Cost of Ten Type Rate/Second Per Month Per Month Mile Link 103 300 $ 25 $8. 75 per station plus tolls $ 67. 50 202 1200 $ 40 $8. 75 per station plus tolls $ 97.50 201A 2000 $ 70 $8. 75 per station plus tolls $ 157. 50 201B 2400 $ 70 $3. 00 first 1/4 mile* $1. 00 additional 1/4 miles $ 182. 00 Telpak A 40, 800 $ 250 $15/mile* $ 650. 00 Telpak B 75, 000 $ 400 $20/mile* $1000. 00 Telpak C 125, 000 $ 550 $25/mile* $1350. 00 Telpak D 500, 000 $1300 $45/mile* $3050. 00 Table 6-1 Michigan Intrastate Data Transmission Services * leased line

120 storage monthly cost capacity, description blocks 200 4 1 core module 450 8 2 core module 650 12 3 core module 850 16 4 core module 1050 20 5 core module 1250 24 6 core module 1450 28 7 core module 1650 32 8 core module Table 6-2 Remote Computer Core Storage

121 operate. At least these first four blocks are an integral part of any small computer. It is the next four blocks which constitute the first additional core module. Accordingly, the incremental cost of going from four to eight blocks is $250. The optimization program assigns values from the "storage capacity, blocks" column to the variable X2. 6. 1. 3 Remote Computer Bulk Storage Only a subset of possible bulk storage devices are considered for use with the remote computer. These are the fixed head-pertrack rotating storage media of drums and disks. Their fast access time and low cost (for small units) make them ideal for storing at the remote computer frequently used program and data files. Tape storage units are much slower (and often more expensive), while their larger capacity is usually not needed. Inexpensive small movable head disk units are not available, as such devices are economically feasible only for storing quite large amounts of information. A quick survey of available disk and drum storage devices reveals that those marketed by Digital Equipment Corporation are among the less expensive. Table 6-3 gives information on four inexpensive disk memories with a wide range of capabilties. Entries in the column "storage capacity, blocks" are assigned to the variable X3 by the optimization program. Because the remote computer

122 Monthly Storage Capacity, Description Cost Blocks 0 0 No bulk storage 150 32 DEC DF32 225 64 DEC DF32 plus 1 expander 300 96 DEC DF32 plus 2 expanders 350 512 DEC RS08 Table 6-3 Remote Computer Bulk Storage

123 might not have any bulk storage, the first entry in Table 6-3 allows for this possibility. 6. 1. 4 Remote Computer-Display Control There are currently available several dozen small computers which might be used as a remote computer in a display system. There are also available at least a dozen display controls, each of which could conceivably be used with any remote computer. Furthermore, the computers and display controls more often than not have many optional features, such as hardware multiply-divide. Taking all equipment combinations together amounts to hundreds or even thousands of possibilities. However, many small computers are fortunately functionally (and economically) very similar. The same is true of display controls. Accordingly, subsets of each group have been chosen for use here. Individual computers considered are the PDP-8 [171 and PDP-9 [151. The display controls studied are the DEC340 [161], IDI 10000 [251, and IDI11000 [251. In addition, the DEC 338 [18], DEC 339 [18], Information Displays, Inc. IDIIOM [26], and Adage's AGT-10 [1], AGT -30 [11, and AGT-50 [11 combined remote computer-display controls are included. Optional features chosen for study are hardware multiplication and division in the remote computer (often called extended arithmatic element, or EAE), and analog three dimensional rotation-translation hardware in the

124 display control (often called a matrix multiplier). These options are actually standard equipment for the Adage equipment. The rotation-translation equipment is not offered for any but the Adage systems. It was assumed that it could be made available by the other manufacturers for $10, 000. The combinations of this equipment result in 39 different remote computer-display controls, each having unique characteristics. Table 6-4 lists each of the combinations. However, this is still not the end of the matter. Each remote computer-display control can drive several display consoles. Indeed, one remote computer might have attached several display controls, each in turn driving one or more display consoles. This matter was first discussed in Section 5. 4. Allowing no more than four display consoles, the eight possibilities tabulated in Table 6-5 arise. Combining these eight combinations with the S9 of Table 6-4 should yield a grand total of 8 x 39 = 312 combinations. This is not quite the case, as certain of the remote computer-display controls are not available in all eight configurations. After accounting for this, a total of 284 combinations remain. It is the function of the program PREPROCESSOR, discussed initially in Section 5. 4 and in greater detail in Appendix A, to determine which of these 284 possibilities should be considered by the optimization program for inclusion in a display system for a specific application. A typical set of results

125 0)0 0 ct DECU 338 No No DEC 338 No No DEC 338 No Yes DEC 338 Yes No DEC 338 Yes Yes DEC 339 No No DEC 339 No Yes DEC 339 Yes No DEC 339 Yes Yes PDP-8 DEC 340 No No PDP-8 DEC 340 No Yes PDP-8 DEC 340 Yes No PDP-8 DEC 340 Yes Yes PDP-9 DEC 340 No No PDP-9 DEC 340 No Yes PDP-9 DEC 340 Yes No PDP-9 DEC 340 Yes Yes PDP-8 I:DI10000 No No PDP- 8 IDn oo0000 No Yes PDP- 8 IDII 0000 Yes No PDP-8 IDI1 0000 Yes Yes PDP-8 IDlooo1000 No No PDP-8 IDI1 G000 No Yes PDP-8 IDIloo000 Yes No PDP- 8 IDI 1 000ooo Yes Yes PDP-9 IDI 0000oooo No No PDP-9 IDI1 0000 No Yes PDP-9 IDI10000 Yes No PDP-9 ID11 0000 Yes Yes PDP-9 IDl1000 No No PDP-9 IDn 1000 No Yes PDP-9 IDI1 1 000 Yes No PDP-9 IDI 1000 Yes Yes IDIIOM No No IDIIOM No Yes IDIIOM Yes No IDIIOM Yes Yes AGT-10 Yes Yes AGT-30 Yes Yes AGT-50 Yes Yes Table 6-4 Remote Computer-Display Control Configurations

126 - a) o - 0 CO o o o 0 a) a Q S z; z ~~~~1 1 2 1 3 1 4 2 2 2 4 3 3 4 4 Table 6-5 Possible Combinations of Display Controls and Display Consoles

127 from PREPROCESSOR are given in Table 6-6. The optimization program uses the reciprocal of quantities in the "Average instruction execution time, isec" as the variable X4, which is then the average instruction execution rate for the remote computer-display control. The remote computers and display controls studied here cover a range of capabilities. A brief description of the equipment follows, so that the reader can be familiar with a few specifics. The PDP-8 is a 12-bit computer with a 1. 5,isec core cycle time. While 32, 768 words of core can be used, only 4096 are directly addressable. This can create time-consuming problems with programs requiring more than 4096 words of instructions and data. Because of the small word size, there are only six memory access instructions. There are no index registers, although certain core locations are automatically incremented after being used as an indirect address. There are many instructions to manipulate the accumulator. The PDP-9, on the other hand, is an 18 bit machine with 1. 0 /sec core cycle time. The long word length allows convenient referencing of up to 32, 768 core locations, and also permits a goodly number of memory access instructions. Indexing is similar to the PDP-8.

128 Cost Per Average Instruction Month Execution Time, Iisec Description 1175 272 PDP-8 and DEC 340 1862 271 PDP-8 and DEC 340 and EAE 1925 164 PDP-9 and DEC 340 2107 137 IDIIOM 2170 136 IDIIOM and EAE 3407 112 Adage AGT 50 Table 6-6 Typical Remote Computer-Display Controls Selected For Use in Optimization

129 The DEC 338 display terminal uses a PDP-8 and a display control with an extensive set of instructions allowing the control to operate independently of the PDP-8 between user interactions. Its capabilities include display subroutining, conditional transfers, and several display modes. Vector generation, however, is by slow digital means, so that the quantity of displayed information is limited. The DEC 339 system uses a PDP-9 in place of the PDP-8, but the display control is essentially unchanged, and it uses only 12 bits from each 18 bit PDP-9 word. The Adage AGT-10, AGT-30, and AGT-50 display terminals all use the same 30 bit, 2 isec computer. Both hardware multiply-divide and graphical translate-rotate are standard equipment, as is an indexing facility. On the AGT-1 0 and AGT-30, the display control does nothing but draw individual points or lines. The computer must continually load several output registers to keep the display operating. This takes at least fifty percent of the computer's time whenever a display is being generated. The AGT-50's display control, on the other hand, can display any sequence of lines or points which are stored contiguously in the computer's core memory. Fast analog vector generation is used in all three models. The IDIIOM display terminal uses a 16 bit, 1. 8 /isec computer with two accumulators and an index register. The display

130 control's instruction set is nearly as powerful as the DEC 338's, and a fast analog vector generation system is used. Of the three separate display controls considered, the DEC 340 uses digital vector generation, and the IDI1 0000 and IDI 11000 use analog vector generation. Of the two IDI display controls, the 1 0000 is the faster. Both IDI controls were assumed to be versions essentially program compatible with the DEC 338. The DEC 340 is slightly less powerful than the DEC 338, and it can draw flicker free somewhat less information than the 338. Detailed statistics on all of these systems can be had in Appendix A. 6. 2 Applications Four display system applications have been selected for close examination. They are text editing, general two-dimensional drawing, general three-dimensional drawing, and general network analysis. These applications were chosen for their differences. That is, they each use the facilities of a display system in different ways. Short descriptions of each follow, to point out their characteristics. 6. 2. 1 Text Editing In this application the display console and an associated typewriter keyboard is used first to enter text into the computer system, and then to scroll through the text to make corrections, additions, and deletions. The light pen is used to indicate what

131 words or letters are to be modified, much as a cursor is used in some systems. As this is a very simple application, none of the more sophisticated remote computer-display controls' extra capabilities are used, and many of the display instruction mix's instructions are not used, as is seen in the appropriate column of Table 6-11. This Table gives an estimate of the probability of using each of the 42 display instructions. These probabilities are used to calculate the average display instruction execution time for these remote computer-display controls being considered for use in the optimization, as was discussed in Section 5o 4. Because only text is displayed on the display console, the weights Q2i (Section 5. 1) listed in Table 6-12 have been picked accordingly. Also in this Table is Qmin (Section 5. 4) for each application. These weights and Qmin are used to determine a particular display control's suitability for a given application. Table 6-13 lists other pertinent characteristics of the text editing application. These are input parameters to the optimization for use with the display system model. Finally, Table 6-7 lists the various interactions which a user of the display system would be expected to create. The accompanying tabulation of the quantities N., i., BiM 1 1 i and B.R (Section 2. 3) are used to determine parameters of the dis1 play system model. The three rightmost columns are results which will be discussed in Section 6. 6.

M R. N. i. B. B. DESCRIPTIONS o 1000.001 1 1FILE & DISPLAY R 1000. 001 4 6 CALL UP A FILE & DISPLAY R R R 100.010 3 4 SCROLL R R R 300. 359 2 3 ADD LINES TO DISPLAY & FILE R R R 1000. 030 0 0 USE L. P. TO INDICATE LINE AND R R R TEXT TO EDIT 300. 600 2 3 ENTER REPLACEMENT TEXT R R R Table 6-7 Text Editing Interactions

133 It is important to note that none of the quantities listed in these tables has been measured; they have been estimated. The point has been made before, and it is made again here: the better the estimates, the better the optimization results will be. This is true for all parameters and all applications, the second of which follows. 6. 2. 2 Two-Dimensional Drawing This application is intended to provide a general two-dimensional drawing capability for a multitude of users. The user can either recall an old drawing from a library and do modifications, or start with a blank screen, build up a picture, name it, and store it in the library. Pictures consist of elements, which can be points, lines, text, or arcs of circles. These elements can be individually positioned into place, temporarily deleted, or permanently deleted. In addition, the entire picture can be translated, and its size can be arbitrarily scaled up or down. The light pen, naturally, is used for indicating elements and positions. A keyboard is used for entering text elements and picture names. Statistical information concerning this application is available in Tables 6-8, 6-11, 6-12, and 6-13. 6. 2. 3 Three-Dimensional Drawing Aside from the addition of a third dimension, the only substantial external difference between this and the previous application

aR ) a) a N. m. B. DESCRIPTION 1 ~1 1 1 0 H H 10.001 0 1 TERMINATE EXECUTION R R R 50. 005 0 1 DELETE CURRENT PICTURE R R R 100. 005 1 2 GET MENU OF EXISTING PICTURES M M M 100. 005 2 3 PICK PICTURE FROM MENU M M M 1 00. 005 2 3 CREATE NEW PICTURE M M M 200. 005 1 2 NAME NEW PICTURE M M M 1 00. 005 4 6 SAVE CURRENT PICTURE M M M 50.100 0 0 ENTER POINT R R R 60. 369 0 0 DRAW LINE FROM PREVIOUS POINT R R R 200. 050 0 1 ENTER TEXT ELEMENT R R R 2000. 025 0 1 ENTER ARC OF CIRCLE M M M 100. 075 0 0 DRAW NEW LINE R R R Table 6-8 2 -D Drawing Interactions

E) M R C ~ N..i B. B. DESCRIPTION o E 1 1 1 1 1 00. 050 0 1 DELETE ELEMENT FROM PICTURE R R R 110. 030 0 1 TEMPORARILY ERASE ELEMENT R R R 500.010 0 1 REDISPLAY ALL TEMP ERASED ELEMENTS R M R 3000. 025 0 1 SCALE PICTURE M M M 200.025 0 1 TRANSLATE PICTURE R R R 200.070 0 11 MOVE ELEMENT R R R 50.150 0 0 IDENTIFY ELEMENT R R R Table 6-8 (continued) 2 -D Drawing Interactions

M R N. 7. B. B. DESCRIPTION 0 H H 1 1 1 1 10,001 0 1 TERMINATE EXECUTION R R R 50. 005 0 1 DELETE CURRENT PICTURE R R R 100. 005 1 2 GET MENU OF EXISTING PICTURES M M R 100. 005 2 3 PICK PICTURE FROM MENU M M R 100. 005 2 3 CREATE NEW PICTURE M M R 200. 005 1 2 NAME NEW PICTURE M M R 100. 005 4 6 SAVE CURRENT PICTURE M M M M 75.100 0 0 ENTER POINT R R R 85. 309 0 0 DRAW LINE FROM PREVIOUS POINT R R R 225. 050 0 1 ENTER TEXT ELEMENT M R R 3000. 025 0 1 ENTER ARC OF CIRCLE M M R 125. 075 0 0 DRAW NEW LINE R R R 100. 050 0 1 DELETE ELEMENT FROM PICTURE R R R Table 6-9 3 -D Drawing Interactions

m Ra MI R 0) a) N. w. B. B. DESCRIPTION 1 1 1 0 H H 110.030 0 1 TEMPORARILY ERASE ELEMENT R R R 500.010 0 1 REDISPLAY ALL TEMP ERASED ELEMENTS M R R 3000. 025 0 1 SCALE PICTURE M M R 225. 025 0 1 TRANSLATE PICTURE M R R 4000. 050 0 1 ROTATE PICTURE M M R 225.070 0 1 MOVE ELEMENT M R R 100.150 0 0 IDENTIFY ELEMENT WITH L. P. R R R Table 6-9 (continued) 3-D Drawing Interactions

138 is the capability to rotate a solid object in three dimensions. Computationally, however, more effort is needed to keep track of the third dimension. Specifics can be found in Tables 6-9, 6-11, 6-12, and 6- 13. 6. 2. 4 General Network Analysis This is meant to represent any one of many network analysis programs. The network elements might be electrical components such as resistors, inductors, capacitors, transistors, and sources, or they might be mechanical devices such as springs, masses, and dashpots, or they might represent the stochastic service system elements of queues, servers, branches, and blocks. Whatever the case, the user progresses through several phases. First, a network consisting of elements and their connections is constructed. Elements are chosen from a menu and moved into place with the light pen, and connections drawn. Changes and deletions are made as required. In the next phase, numerical attributes are assigned each element. For electrical networks, this would correspond to ohms, henrys, farads, or a transistor type. In the third phase, the desired analysis results are specified. The network is then analyzed by whatever numerical techniques are appropriate to the type of network drawn, and finally, the requested results are plotted.

N. 7. B.M B.R DESCRIPTION 1 1 1 1 100. 038 1 2 PICK PHASE FROM MENU M M M 75.125 0 1 PICK ELEMENT FROM MENU R R R 200 o125 0 1 MOVE ELEMENT INTO PLACE R R R 50. 250 0 10 IDENTIFY AN ELEMENT WITH L. P. M M M 200 o 186 0 1 CONNECT PORTS OF IDENTIFIED R R R ELEMENTS 100. 025 0 1 DELETE CONNECTION R R R 1 00. 025 0 1 DELETE AN IDENTIFIED ELEMENT R R R 200. 050 0 1 MOVE WHOLE NETWORK (TRANSLATE) R R R 200.125 0 1 ASSIGN VALUE TO IDENTIFIED ELEMENT R R R 100 o 012 1 2 PICK DESIRED OUTPUT FROM MENU M M M 200. 012 0 1 INDICATE OUTPUT NODE(S) ON NETWORK R R R 1 00000.012 3 10 SOLVE PROBLEM M M M 20000. 012 1 12 PREPARE OUTPUT M M M Table 6-10 Network Analysis Interactions

-4H -) dn s Q C Initialize Display. 01. 01. 0063. 0067 Start Display. 01; 01.0063.0067 Check Status of Display. 01. 01. 0063.0067 Stop Display.01.01. 0063.0067 Insert x or Ax. 01.0025.0015.0016 Insert y or Ay.01.0025.0015;0016 Insert Sign; 0. 0025;0015; 0016 Insert Intensity Bit. 0. 0025.0015.0016 Insert Jump Address o 02. 0025. 0015; 0016 Pentracking.1;52;3245.3476 Rotation 0; 0. 0625.0 Translation;0.001; 0007.0007 Line Blink. 0.0; 0.0 Change Intensity. 0;0.0.0 Table 6-11 Display Instruction Mix

Push Jump.0.0.0.0 Pop Jump.0 o0.0.0 10 Bit Addition 05. 015. 0094.01 1 0 Bit Subtract ion: 05. 015.0094.01 10 Bit Multiply. 0 005;0031: 0033 10 Bit Divide. 0.0.0. Address Addition 0 025 005 0 0031. 0033, Address Subtraction. 025;005. 0031;0033 Test Bits.025.02.0126.0134 Set Bits. 025.02.0126 o 0134 Shift (6 places). 0 o 02. 0126; 0134 Save Computer Status o 1.065. 0413; 044 Dispatch Interrupt. 1. 065. 0413. 044 Restore Computer Status.1 o 065. 0413 o 044 Table 6-11 (continued) Display Instruction Mix

Set Up Teletype I/O o 1.01. 0063.0067 Set Up Dataphone I/O o 01. 01. 0063 o0067 Set Up Disk or Drum I/O. 01. 01. 0063.0067 Set Up Paper Tape I/O. 0. 0 o 0.0 ASCII to Integer.0 o 0 o 0 O ASCII to Display Code. 1. 005. 0031 o 0033 Integer to ASCII.0 o 0.0 o 0 Iterate. 03. 765 o 0478 o 051 Move a Word. 03 o 01 o 0063.0067 Obtain Current X and Y Position. 04. 01. 0063. 0067 Floating Add 0.0 0781 0833 Floating Subtract. 0. 0 o 0781 o 0833 Floating Multiply. 0. 0. 0781. 0833 Floating Divide. 0 0 0. 0781. 0833 Table 6-11 (continued) Display Instruction Mix

143 co n H~s z Ev c~ cn Z Alphanumeric Test Pattern (Figure 5-1) 1o 0 0. 0 0. 0 0. 1 Weather Map Test Pattern (Figure 5-2) 0. 0 0. 0 0. 0 0. 0 Graph Test Pattern Figure 5-3) 0. 0 0. 0 0. 0 0. 2 Architectural Drawing Test Pattern (Figure 5-4) 0o 0 0. 5 0. 5 0. 0 Electronic Schematic Test Pattern (Figure 5-5) 0. 0 0. 5 0. 5 0o 7 Qmin 100 0 75. 0 150.0 60. 0 mi n Table 6-12 Display Weights Qi. and Q min 1 min

144 ~d,.., ~ ~c,, HE cz NPPPC 500 100. 00 200. 00 3000. 00 MSGLTH 1280 500. 00 800. 00 4000. 00 MAXPAG 200 200. 00 200. 00 200. 00 SYSPAG 2 3. 00 4. 00 4. 00 ARRIVE 2 0.20 0.20 0.10 UMC 1 0.25 0.25 0.25 -x -x -x -x PACESS(x) 1 -e 201 -e 1 -e 1 -e Table 6-13 Application Characteristics

145 The application's statistics are contained in Tables 6-10, 6-11, 6-12, and 6-13. Note in Table 6-11 the heavy use of floating point operations, which is a consequence of the network analysis. 6. 3 Optimization Results The optimization program was used for the display subsystems and applications presented in Sections 6. 1 and 6. 2, for one, two and three display consoles. Thus twelve cost versus minimum response time curves have been generated. It was felt that very little incremental knowledge could be gained from studying four console display systems. They were therefore not considered, even though the appropriate output information from PREPROCESSOR exists. Tables 6-14, 6-15, 6-16, and Figure 6-1 give results for the text editing application. Tables 6-17, 6-18, 6-19, and Figure 6-2 report the two-dimensional drawing results, while Tables 6-20, 6-21, 6-22, and Figure 6-23 have the three-dimensional drawing results. Finally, the network analysis results are found in Tables 6-23, 6-24, 6-25, and Figure 6-5. In each case the tables give optimum display systems, with their average response time and monthly cost. In the tables following the description of each remote computer is a pair of digits. The first is the number of display controls; the second, the number of display consoles used with the computer. The figures graphically present per console cost versus minimum

MONTHLY COST, AVERAGE RESPONSE TIME, EQUIPMENT COMPLEMENT DOLLARS SECONDS 1505 8. 494 103 SERIES DATA LINK 1 CORE MODULE NO BULK STORAGE DEC 338 REMOTE DISPLAY TERM. 153 5 2. 286 SWITCHED LINES - ASYNCHRONOUS 1 CORE MODULE NO BULK STORAGE DEC 338 REMOTE DISPLAY TERM. 159 5 1.458 SWITCHED LINES - SYNCHRONOUS 1 CORE MODULE NO BULK STORAGE DEC 338 REMOTE DISPLAY TERM. 1,1 1963 0. 073 SWITCHED LINES - ASYNCHRONOUS 1 CORE MODULE DEC RF08 + RS08 DISK UNIT DEC 339 1,1 2980 0. 035 103 SERIES DATA LINK 6 CORE MODULES DEC RF08 + RS08 DISK UNIT DEC 339 Table 6-14 Text Editing, One User

MONTHLY COST, AVERAGE RESPONSE TIME, EQUIPMENT COMPLEMENT DOLLARS SECONDS 3892 0. 027 PRIVATE VOICE GRADE LINES 8 CORE MODULES DEC RFO8 + RS08 DISK UNIT IDI INPUT OUTPUT MACHINE (IDIIOM) 1,1 Table 6-14 (continued) Text Editing, One User

MONTHLY COST, AVERAGE RESPONSE TIME, EQUIPMENT COMPLEMENT DOLLARS SECONDS 2430 8. 493 103 SERIES DATA LINK 1 CORE MODULE NO BULK STORAGE DEC 338 REMOTE DISPLAY TERM. 2,2 2460 2. 286 SWITCHED LINES - ASYNCHRONOUS 1 CORE MODULE NO BULK STORAGE DEC 338 REMOTE DISPLAY TERM. 2,2 3421 0. 058 PRIVATE VOICE GRADE LINES 3 CORE MODULES DEC RFO8 + RS08 DISK UNIT DEC 339 2,2 4417 0. 030 PRIVATE VOICE GRADE LINES 8 CORE MODULES DEC RFO8 + RS08 DISK UNIT DEC 339 2,2 Table 6-15 Text Editing, Two Users

MONTHLY COST, AVERAGE RESPONSE TIME, EQUIPMENT COMPLEMENT DOLLARS SECONDS 3604 8. 497 103 SERIES DATA LINK 2 CORE MODULES NO BULK STORAGE DEC 338 REMOTE DISPLAY TERMINAL 3,3 3634 2. 289 SWITCHED LINES - ASYNCHRONOUS 2 CORE MODULES NO BULK STORAGE DEC 338 REMOTE DISPLAY TERMINAL 3,3 3694 1.461 SWITCHED LINES - SYNCHRONOUS 2 CORE MODULES NO BULK STORAGE DEC 338 REMOTE DISPLAY TERMINAL 3,3 3972 0. 086 PRIVATE VOICE GRADE LINES 2 CORE MODULES DEC RF08 + RS08 DISK UNIT DEC 338 REMOTE DISPLAY TERMINAL 3,3 4485 0. 063 SWITCHED LINES - ASYNCHRONOUS 5 CORE MODULES DEC RF08 + RS08 DISK UNIT DEC 338 REMOTE DISPLAY TERMINAL 3,3 Table 6- 16 Text Editing, Three Users

MONTHLY COST, AVERAGE RESPONSE TIME, EQUIPMENT COMPLEMENT DOLLARS SECONDS 5342 0. 035 PRIVATE VOICE GRADE LINES 8 CORE MODULES DEC RF08 + RS08 DISK UNIT DEC 339 3,3 Table 6-16 (continued) Text Editing, Three Users

Figure 6-1 Minimum Response Times, Text Editing

5000 On c~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~o r o 4000 oq C3 03 c~ 0 i &- o 3000 3~ 2 —-.3 100 2000... S. _ 0~MINIMUM AVERAGE RESPONSE TIME, SECS

MONTHLY COST, AVERAGE RESPONSE TIME, EQUIPMENT COMPLEMENT DOLLARS SECONDS 1330 0. 281 103 SERIES DATA LINK 1 CORE MODULE NO BULK STORAGE PDP-8 + DEC 340 DISPLAY 1,1 1420 0. 191 SWITCHED LINES - SYNCHRONOUS 1 CORE MODULE NO BULK STORAGE PDP-8 + DEC 340 DISPLAY 1,1 1474 00 076 103 SERIES DATA LINK 1 CORE MODULE ONE MODULE, DEC DF32 PDP-8 + DEC 340 DISPLAY 1,1 1922 0. 025 PRIVATE VOICE GRADE LINES 1 CORE MODULE DEC RFO8 + RS08 DISK UNIT ADAGE AGT 10 1,1 2390 0. 017 TELPAK A 1 CORE MODULE DEC RFO8 + RS08 DISK UNIT ADAGE AGT 1, Table 6-17 Two-Dimensional Drawing, One User

MONTHLY COST, AVERAGE RESPONSE TIME, EQUIPMENT COMPLEMENT DOLLARS SECONDS 2998 0. 013 TELPAK A 4 CORE MODULES DEC DF32, 1 DS32 EXPANDER ADAGE AGT 1,1 3986 0. 012 TELPAK B 7 CORE MODULES DEC RFO8 + RS08 DISK UNIT ADAGE AGT 1O,1 Table 6-17 (continued) Two - Dimensional Drawing, One User

MONTHLY COST, AVERAGE RESPONSE TIME, EQUIPMENT COMPLEMENT DOLLARS SECONDS 2329 0. 282 103 SERIES DATA LINK 2 CORE MODULES NO BULK STORAGE PDP-8 + DEC 340 DISPLAY 2,2 2359 0. 102 SWITCHED LINES - ASYNCHRONOUS 2 CORE MODULES NO BULK STORAGE PDP-8 + DEC 340 DISPLAY 2,2 2473 0. 076 103 SERIES DATA LINK 2 CORE MODULES ONE MODULE, DEC DF32 PDP-8 + DEC 340 DISPLAY 2,2 2967 0. 029 SWITCHED LINES - ASYNCHRONOUS 2 CORE MODULES DEC DF32, 1 DS32 EXPANDER IDHOM + EXTENDED ARITHMETIC 1,2 3474 0. 018 TELPAK A 3 CORE MODULES DEC DF32, 1 DS32 EXPANDER PDP-9 + DEC 340 DISPLAY 2,2 Table 6-18 Two-Dimensional Drawing, Two Users

MONTHLY COST, AVERAGE RESPONSE TIME, EQUIPMENT COMPLEMENT DOLLARS SECONDS 3959 0. 015 TELPAK A 4 CORE MODULES DEC RFO8 + RS08 DISK UNIT IDJIOM + EXTENDED ARITHMETIC 1,2 4997 0. 013 TELPAK A 3 CORE MODULES DEC RF08 + RS08 DISK UNIT ADAGE AGT 50 1,2 5945 0. 012 TELPAK A 5 CORE MODULES DEC RF08 + RS08 DISK UNIT ADAGE AGT 50 1,2 Table 6-18 (continued) Two-Dimensional Drawing, Two Users

MONTHLY COST, AVERAGE RESPONSE TIME, EQUIPMENT COMPLEMENT DOLLARS SECONDS 3079 0. 294 103 SERIES DATA LINK 2 CORE MODULES NO BULK STORAGE PDP-8 + DEC 340 DISPLAY 3,3 3194 0. 173 PRIVATE VOICE GRADE LINES 2 CORE MODULES NO BULK STORAGE PDP-8 + DEC 340 DISPLAY 3,3 3493 0. 048 PRIVATE VOICE GRADE LINES 2 CORE MODULES DEC DF32, 1 DS32 EXPANDER PDP-8 + 340 DISPLAY + EXTENDED ARITHMETIC 3,3 3992 0. 029 103 SERIES DATA LINK 2 CORE MODULES DEC DF32, 1 DS32 EXPANDER DEC 339 3,3 Table 6-19 Two -Dimensional Drawing, Three Users

MONTHLY COST, AVERAGE RESPONSE TIME, EQUIPMENT COMPLEMENT DOLLARS SECONDS 4474 0. 021 TELPAK A 3 CORE MODULES DEC DF32, 1 DS32 EXPANDER PDP-9 + DEC 340 DISPLAY 3,3 4973 O.O15 TELPAK A 4 CORE MODULES DEC DF32, 1 DS32, EXPANDER DEC 339 3,3 5962 0. 014 TELPAK B 7 CORE MODULES DEC RF08 + RS08 DISK UNIT DEC 339 3, 3 Table 6-19 (continued) Two-Dimensional Drawing, Three Users

sujmawI(I IeuoO!SuoUa(- OAL'samu&L asuodsoa nunmumuil z-9 aenaln MONTHLY COST, DOLLARS 0 0 0 0 0 0 0 0 o. I' I' 0 C m. 0 z Pl II I tn Ne.e,U N_

MONTHLY COST, AVERAGE RESPONSE TIME, EQUIPMENT COMPLEMENT DOLLARS SECONDS 2082 10553 103 SERIES DATA LINK 1 CORE MODULE NO BULK STORAGE IDI INPUT OUTPUT MACHINE (IDIIOM) 2112 00 433 SWITCHED LINES - ASYNCHRONOUS 1 CORE MODULE NO BULK STORAGE IDI INPUT OUTPUT MACHINE (IDIIOM) 1, 1 * 2196 0. 246 PRIVATE VOICE GRADE LINES 1 CORE MODULE NO BULK STORAGE IDI INPUT OUTPUT MACHINE (IDIIOM) 1, 1 2471 0. 072 PRIVATE VOICE GRADE LINES 1 CORE MODULE DEC DF32, 1 DS32 EXPANDER IDIIOM + EXTENDED ARITHME ARITHMETIC Table 6-20 Three-Dimensional Drawing, One User

MONTHLY COST, AVERAGE RESPONSE TIME, EQUIPMENT COMPLEMENT DOLLARS SECONDS 2977 0. 029 TELPAK A 1 CORE MODULE DEC RFO8 + RS08 DISK UNIT IDH1OM + EXTENDED ARITHMETIC 3962 Oo 021 TELPAK C 1 CORE MODULE DEC DF32, 1 DS32 EXPANDER PDP-9 + IDI 10000 + EXTENDED ARITHMETIC 1,1 4954 0. 017 TELPAK B 3 CORE MODULES ONE MODULE, DEC DF32 ADAGE AGT 50 Table 6-20 (continued) Three-Dimensional Drawing, One User

MONTHLY COST, AVERAGE RESPONSE TIME, EQUIPMENT COMPLEMENT DOLLARS SECONDS 4101 0. 739 103 SERIES DATA LINK 2 CORE MODULES NO BULK STORAGE DEC PDP-8 + IDI 10000 2,2 * 4131 0. 235 SWITCHED LINES - ASYNCHRONOUS 2 CORE MODULES NO BULK STORAGE DEC PDP-8 + fII 10000 2,2 4192 0. 175 SWITCHED LINES - SYNCHRONOUS 2 CORE MODULES NO BULK STORAGE DEC PDP-8 + IDI 10000 2,2 4985 0. 038 TELPAK A 2 CORE MODULES DEC DF32, 1 DS32 EXPANDER PDP-8 + IDI 10000 + EXTENDEDARITH. 2,2 5867 0. 021 TELPAK C 2 CORE MODULES DEC RFO8 +RS08 DISK UNIT PDP-9 + IDI 10000 + EXTENDED ARITH. 2,2 Table 6-21 Three-Dimensional Drawing, Two Users

MONTHLY COST, AVERAGE RESPONSE TIME, EQUIPMENT COMPLEMENT DOLLARS SECONDS 6964 O. 020 TELPAK C 5 CORE MODULES DEC RF08+RSO8 DISK UNIT PDP-9 + IDI 10000 + EAE + MATRIX 2,2 Table 6-21 (continued) Three-Dimensional Drawing, Two Users

MONTHLY COST, AVERAGE RESPONSE TIME, EQUIPMENT COMPLEMENT DOLLARS SECONDS 5738 1.631 103 SERIES DATA LINK 2 CORE MODULES NO BULK STORAGE DEC PDP-8 + IDI 10000 3, 3 5768 0. 467 SWITCHED LINES - ASYNCHRONOUS 2 CORE MODULES NO BULK STORAGE DEC PDP-8 + IDI 10000 3, 3 5997 0. 108 SWITCHED LINES - ASYNCHRONOUS 2 CORE MODULES ONE MODULE, DEC DF32 PDP-8 + IDI 10000 + EX. ARITH. 3, 3 6978 0. 024 TELPAK A 3 CORE MODULES DEC RFO8 + RS08 DISK UNT PDP-9 + IDI 10000 + EX. ARITH. 3,3 7967 0. 021 TELPAK C 5 CORE MODULES ONE MODULE, DEC DF32 PDP-9 + IDI 10000 + EX. ARITH. 3, 3 Table 6-22 Three-Dimensional Drawing, Three Users

MONTHLY COST, AVERAGE RESPONSE TIME, EQUIPMENT COMPLEMENT DOLLARS SECONDS 8826 0. 020 TELPAK C 5 CORE MODULES DEC RFO8 + R508 DISK UNIT PDP-9 + IDI 10000 + EAE + MATRIX 3,3 Table 6-22 (continued) Three-Dimensional Drawing, Three Users

166 Figure 6-3 Minimum Response Times, Three-Dimensional Drawing

5000 (/) 4000 c.0 3000 C) "lb Io 2000 I000,.03.1.3 1.0 3.0 MINIMUM AVERAGE RESPONSE TIME, SECONDS

MONTHLY COST, AVERAGE RESPONSE TIME, EQUIPMENT COMPLEMENT DOLLAR SECONDS 1557 8. 906 103 SERIES DATA LINK 1 CORE MODULE NO BULK STORAGE ADAGE AGT 10 1,1 1588 2. 426 SWITCHED LINES - ASYNCHRONOUS 1 CORE MODULE NO BULK STORAGE ADAGE AGT 1 1, 1 1648 1. 562 SWITCHED LINES - SYNCHRONOUS 1 CORE MODULE NO BULK STORAGE ADAGE AGT 10 1,1 1672 1. 346 PRIVATE VOICE GRADE LINES 1 CORE MODULE NO BULK STORAGE ADAGE AGT 10 1,1 1925 0. 201 PRIVATE VOICE GRADE LINES 1 CORE MODULE DEC RF08 + RS08 DISK UNIT ADAGE AGT 10 1, 1 Table 6-23 Network Analysis, One User

MONTHLY COST, AVERAGE RESPONSE TIME, EQUIPMENT COMPLEMENT DOLLARS SECONDS 2840 0.114 TELPAK A 3 CORE MODULE S DEC RF08 + RS08 DISK UNIT ADAGE AGT 10 1,1 3836 0. 072 TELPAK A 8 CORE MODULES DEC RF08 + RS08 DISK UNIT ADAGE AGT 10 1,1 4536 0.069 TELPAK C 8 CORE MODULES DEC RF08 + RS08 DISK UNIT ADAGE AGT 10 1, 1 Table 6-23 (continued) Network Analysis, One User

MONTHLY COST, AVERAGE RESPONSE TIME, EQUIPMENT COMPLEMENT DOLLARS SECONDS 2663 9.704 103 SERIES DATA LINK 2 CORE MODULES NO BULK STORAGE IDI INPUT OUTPUT MACHINE (IDIOM) 1,2 * 2694 2. 884 SWITCHED LINES - ASYNCHRONOUS 2 CORE MODULES NO BULK STORAGE IDI INPUT OUTPUT MACHINE (IDIIOM) 1,2 3491 0.181 PRIVATE VOICE GRADE LINES 4 CORE MODULES DEC RF08 + RS08 DISK UNIT IDIIOM + EXTENDED ARITHMETIC 1,2 43 59 0. 100 TELPAK A 6 CORE MODULES DEC RFO8 + RS08 DISK UNIT IDIIOM + EXTENDED ARITHMETIC 1,2 5499 0. 075 TELPAK B 8 CORE MODULES DEC RF08 + RS08 DISK UNIT PDP-9 + IDI 10000 + EX. ARITH. 1,2 Table 6-24 Network Analysis, Two Users

MONTHLY COST, AVERAGE RESPONSE TIME, EQUIPMENT COMPLEMENT DOLLARS SECONDS 5738 10. 218 103 SERIES DATA LINK 2 CORE MODULES NO BULK STORAGE DEC PDP-8 + IDI 10000 3, 3 5769 3.157 SWITCHED LINES - ASYNCHRONOUS 2 CORE MODULES NO BULK STORAGE DEC PDP-8 + IDI 10000 3, 3 * 5853 1. 978 PRIVATE VOICE GRADE LINES 2 CORE MODULES NO BULK STORAGE DEC PDP-8 + IDI 10000 3, 3 5991 1. 697 103 SERIES DATA LINK 2 CORE MODULES DEC RF08 + RS08 DISK UNIT DEC PDP-8 + IDI 10000 3, 3 6978 0. 155 TELPAK A 3 CORE MODULES DEC RF08 + RS08 DISK UNIT PDP-9 + IDI 10000 + EX. ARITH. 3, 3 Table 6- 2 5 Network Analysis, Three Users

MONTHLY COST, AVERAGE RESPONSE TIME, EQUIPMENT COMPLEMENT DOLLARS SECONDS 7974 0. 093 TELPAK A 3 CORE MODULES DEC RFO8 + RS08 DISK UNIT PDP-9 + IDI 10000 + EX. ARITH. 3, 3 Table 6-25 (continued) Network Analysis, Three Users

173 Figure 6-4 Minimum Response Times, Network Analysis

V-9 a.nS2T MONTHLY COST, DOLLARS 0 0 0 0 0 0 0 0 0 0 ~z~~ mr C) -u 0 0 ILI

175 response time for each application implemented with a one, two, or three display console system. 6. 4 Comparison of Best and Worst Display Systems One of the purposes of this chapter, as stated in the opening discussion, is to demonstrate the usefulness and necessity of providing tools and guidelines for display system designers. It was stated that the difference in response times of optimal and nonoptimal systems can be quite significant~ Therefore, display systems should be designed using methods such as those presented in the preceding chapters, the alternative being poor response time for the number of dollars invested. Figure 6-5 shows just how severe the penalties of using a nonoptimal design can beo The figure plots response time versus cost for the network analysis application with three users0 Both optimum and worst case response times for various values of cost are plotted0 The worst case response time is the maximum response time of those display systems entered into the set S' during the optimization (Section4. 2 ) It may be helpful to recall that S' contains only those display systems which, on the basis of their cost, are expected to provide good response time. There usually exists, however, display systems not in S' (therefore costing less than those in S') which can give better response time than the worst case response time0 The graph's interpretation is that, for instance, if $2340 per month is

176 Figure 6-5 Best and Worst Average Response Times

AVERAGE RESPONSE TIME, SECONDS o I "'1 Iz C,,> 0 oc0 I,,, 0 - 0 0 n0

178 to be spent on a display system, the response time can range from o 155 seconds (Point A) to 3o 92 seconds (Point B)o These times differ by a factor of 25. Also, the graph can be interpreted to show that if a response time of. 1 seconds is needed, the display system's monthly cost can vary from about $2600 (Point C) to about $3400 (Point D). This represents an unnecessary expenditure of up to $800 per month! There are other interesting aspects of the graph. Any display system selected from the set S' will fall within the bounded area in the graph, no matter what C' might have been used to max find S'o In addition, the worst case curve and optimum curve meet at points E and F, because for their costs there was only one display system in S', so the one system gives at once the optimum and worst case response timeso In conclusion, the differences between optimum and worst case display systems are significant, with respect to both cost and response time. Therefore, display system designers must have at their disposal means of making intelligent design decisions, because the consequences of making bad decisions are too serious. 6. 5 Interpretation of Results The results presented in Section 6. 2 can be used in several ways: as cost-effectiveness information, to tell when multipleconsole systems should be used, and in the formulation of design guidelines0 These three will be treated in turn0

179 6. 5o 1 Cost-Effectiveness Any of the individual curves in Figures 6-1, 6-2, 6-3, and 6-4 can be interpreted from a cost-effectiveness viewpoint by a simple transformation. Let cost-effectiveness be defined as the number of user-display interactions/second obtained for each dollar spent. Then 1 TMIN + I/ARRIVE cost-effectiveness= CE TMIN + 1/ARRIVE (6. 1) TMIN + 1/ARRIVE is the time in seconds needed to complete one interaction; its reciprocal is the number of interactions per second. C(X), defined in Section 2. 6 is the display system's cost, and is divided by the number of users R to place the calculations on a peruser basis. The results of applying equation 6. 1 to the optimum display systems found for the 3-D drawing application (Figure 6-3) with one, two, and three display consoles are shown in Figure 6-6. The peaks in cost-effectiveness determine which of several optimum (in the sense of minimum response time) display systems is optimum in the cost-effectiveness sense. The three most cost-effective systems occur at costs of $2180, $2065, and $1999 per display console. This is again a reflection of economies of scale: for more users, the most effective system costs less, and provides more interactions/second/dollar. In Tables 6-14 to 6-25, an asterisk denotes the most cost-effective display systems.

180 Figure 6-6 Cost -Effectiveness

1.1 1.0.9 o.82 cM RC D.3.2. I 2000 3000 4000 5000 MONTHLY COST, DOLLARS

182 A more sophisticated cost-effectiveness analysis would also take into account the monthly cost of the system's user, which would probably fall between $2000 and $3000. A display system judged best on the basis of equation 6. 1 and having a response time of 30 seconds wastes a lot of human time which, if taken into consideration, would force selection of a faster and more expensive display system. On a more intuitive basis, Figures 6-1 to 6-4 all show that starting with the slowest responding systems, very small incremental expenditures (less than $200) result in order-of-magnitude improve - ments in response time. As more and more money is invested, however, the returns become less and less significant. Indeed, there exists on many of the graphs a rather distinct breakpoint at which the slopes of the minimum response time curves become distinctly negative. This emphatically signals a diminishing returns situation, in which more expensive display systems give back relatively little in return for their increasing prices. The curves seem to say that it is wise to spend somewhat more than the necessary minimum, but not too much more. What should be purchased beyond a minimum system is discussed in Section 6. 5o 3. Before that, however, other information will be extracted from the results.

183 6. 5, 2 Multiple Versus Single Console Systems When a display application is to be implemented for several simultaneous users, a systems design problem is created. If R display consoles are needed, should R separate display systems be obtained, or should a display system have multiple consoles? Tne immediate answer might be that economies of scale and sharing the display subsystems among several users should favor using multiple consoles. In most instances this is indeed the case. In the network analysis application, however, this is not true. As can be seen by examining Figure 6-4, the two console system is least expensive, on a per-console basis. Both the one and two console systems are less expensive than the three console system, except for response times less than. 15 seconds. Although the three console system would be expected to be most economical, it is not. The explanation for this is very simple. For the particular application considered here, only the most expensive remote computer-display controls were suitable for a three console system. Considerably less expensive units were useable for the one and two console systems, but because of the application's display requirements, they were not extendable to the three console system. For the other applications, the display requirements were such that this situation never arose.

184 The point to be remembered here is that the obvious is not always true: a single three console display system is not necessarily less expensive than three display systems each with one consoleo This can be so because lack of appropriate equipment hampers realization of normally intrinsic economies of scaleo 6. 5. 3 Guidelines General guidelines for display system designers are like Homer's Sirens: very desirable and very dangerous. They are desirable to help the designer carry out his work; they are dangerous because they can be improperly used and impart to the designer a false sense of security. While it is not necessary to deafen the crew to resist their temptations, design guidelines do need to be approached with a word of caution0 Guidelines are not absolutes, they are aids to be used in context. That is, guidelines can be used only within the context of applications for which they are intended. The applications studied here have been selected to provide a reasonably broad base on which to establish guidelines, so the guideline's usefulness can go across (but not necessarily beyond) the base. The implicit danger with guidelines is that it is easy to use them where they do not apply: it is easy for a designer to become little more than a cookbook technician, merely looking up guidelines and indiscriminately applying them. Having given this warning, the optimization

185 results in Tables 6-14 to 6-25 will be examined in an attempt to deduce general guidelines for display system designers. The most striking phenomenon noticed in these tables is that as additional money is spent, the first subsystem to be upgraded is the data linko This is because small amounts of additional money yield large improvements in data link transmission rate, which are in turn reflected in significant improvements in average response time. Note that this might not be the case with applications making less use of the data link than the applications studied here. Once the data link has been upgraded to the synchronous switched line or private voice grade line level (2000 or 2400 bps), additional speed increases become considerably more expensive, as seen from Table 6-1. For the applications being studied, small incremental amounts of money must therefore either go toward more core memory, bulk storage, or a faster remote computerdisplay control. In every instance bulk storage is added, and in some cases the computer-display control is improved (only in cases when an improvement is inexpensive). Only twice is core memory added. In some cases, the data link speed is decreased, because adding bulk storage decreases data link traffic and thus makes a fast data link less important. This is particularly evident in the text editing (Tables 6-14 to 6-16) and the two-dimensional drawing (Tables 6-17 to 6-19) applications, for which

186 response times on the order of 80 milliseconds are obtained with data links no faster than private voice grade lines. For threedimensional drawing, about a 100 millisecond response is obtained, and for network analysis, about 200 milliseconds. The next step beyond these response times is taken with Telpak A service, providing a transmission rate of 40, 000 bps, and also providing a substantial increase in cost. By consulting the graphs of Figures 6-1 to 6-4 it is seen that the response times mentioned above correspond in general to points beyond which the returns on expenditures for Telpak A and other equipment decrease significantly. However, if better response time is needed, the results show that both Telpak A service and additional bulk storage are the most rewarding; significantly increasing core storage and remote computer-display control capability are relatively less important. The general guidelines might thus read as follows: "A satisfactory inexpensive display system uses a voice grade data link, no bulk storage, little or no core storage beyond the absolute minimum needed, and the least expensive remote computer-display control. For little additional expenditure, the addition of a significant amount of bulk storage provides better response time. Inexpensive increases in the remote computer-display control's capabilities are also helpful. Further response time decreases are achieved with broad band data link speeds and more bulk

187 storage. Additional response time improvements are obtained (at high cost) first by improving the remote computer-display control and then by using more core storage. " 6. 5. 4 Hardware Aids for Multiplication and Division The use of a hardware matrix multiplier for rotation of objects in the three-dimensional drawing application doesn't seem to be worth the projected price ($10, 000 or $250 per month). For one, two, and three users, addition of the matrix multiplier (for one user, as part of the AGT-50) occurs only after most of the other display subsystems are at or near their maximum capability (Tables 6-20 to 6-22)o The improvement in average response time ranges from 1 to 4 milliseconds - small indeed0 The use of hardware multiply-divide facilities, however, is another matter0 For the three applications (all but text editing) which make use of fast multiplication and/or division, this capability is usually added at the level of expenditure where the general guidelines require the addition of bulk storage. This is just one of the inexpensive improvements in the remote computer-display control called for by the guidelines. 6. 6 Division of Processing In Section 2. 7. 1 one means for dividing processing of various interaction types between the main and remote computers

188 was devised. It is desirable to answer two questions concerning this area: 1. Is the division of processing method better than the less sophisticated alternative of using a predetermined fixed division no matter how the display system be configured? 2. Are the results reasonable? An experiment was designed to answer the first question. Using an application virtually identical to two dimensional drawing, an optimization was performed. During the course of the optimization, the division of processing algorithm produced several different values of PM, the display terminal's dependence on the main computer (Section 2. 4). Among these values were 0. 0, 0. 055, and 0. 105. The optimum display system occurred for X = (1, 3, 7, 4) with PM = 0. 0. Next, optimizations were performed with a display system model using a fixed processing division, one optimization for each of the three PM's mentioned. The results were for PM = 0. 0, X = (1, 3, 7, 4), T =.02; PM = 0. 055, X = (6, 1, 6,3), T =. 04; and PM = 0. 105, X = (6, 1, 6, 3), T = 05. The first important result here is that the X's are not all the same. If they had been, there would be little justification for calculating the optimum division of processing, as the results would be independent (at least in this instance) of the exact division. The second

189 One User Two Users Three Users Text Editing.0.0.0 Two Dimensional Drawing.075.085.075 Three Dimensional Drawing.28.125.005 Network Analysis.324.324.324 Table 6-26 PM for the Most Cost-Effective Display Systems

190 important result is that the smallest T occurred for PM = 0. 0, showing that the optimum division really does minimize response time. The second question can be answered by examing Tables 6-7 to 6-10. The three rightmost columns show, by using M for main computer and R for remote computer, the division of processing for the display systems chosen in Section 6. 5. 1 as most cost-effective. These tables show that the relatively more demanding interaction types are processed by the main computer, while the remaining types are processed by the remote computer. This is as it should be. To complete the picture, Table 6-26 gives PM for each of the twelve systems. 6. 7 Summary The goals set forth at the start of this chapter have been met. The techniques developed in earlier chapters have been applied to several display applications, and the results have been interpreted so as to justify the search for display system design guidelines. These guidelines have been stated. Of course these guidelines must be used in the proper perspective, first because parameters on which they are based were only estimated, and second because the relative costs of the subsystems studied might change in the future. The next and concluding chapter will present an overview

of what has been done, and will attempt to place the work reported here in the proper perspective,

192 Chapter VII CONCLUSIONS 7. 1 Review of the Research The purpose of this research has been to develop aids for the analysis and design of highly interactive graphical display systems. These aids are needed because inept design decisions can be very wasteful. To provide a framework within which to work, a mathematical model of a display system was developed in Chapter II. The model was a description of the system's application and hardware to predict response time. So that the model wuld be simple enough to facilitate quick analysis, and to make it realistic to use, the level of detail is relatively crude. Along with the model, a method was proposed for dividing display processing between the main and remote computers so as to help minimize response time. This method is an aid for making one of the more important design decisions associated with display systems, namely, how much should the main computer do, and how much should the remote computer do? Chapter III was devoted to a discussion of the relative merits of two analysis methods which could be used with the display model, simulation and numerical queueing analysis. It was shown that numerical queueing analysis is much faster (in terms of computer time) than simulation, and produces equally satisfactory results.

193 In Chapter IV an optimization technique was developed. It very efficiently finds an optimum display system having no more than a given cost. This optimization, which in turn uses the display system model, is the primary analytical tool developed in this research. All else is subsidiary to it. The optimization can be used by display system designers as a tool in itself. It is used here to study several display applications, and to find design guidelines. Chapter V presents a methodical procedure for ranking various remote computer-display controls on the basis of their display and computational capabilities. This procedure is useful to display system designers in and of itself, and also is used here with the display system model. The usefulness of all this work becomes apparent in Chapter VI. The characteristics of four different display system applications are estimated (not measured), and many optimum display systems are found. These results are used to demonstrate the necessity for system design aids, and to develop some guidelines for system designers. 7. 2 Critical Evaluation What are the good points of this research? First and foremost, it provides system analysts and designers with a conceptual basis on which their efforts can be established. The steps required for designing display systems on an objective basis have been illustrated. Second, the specific mathematical tools developed

194 here have been shown to be useful. Finally, the design guides should prove helpful to system designers. What is wrong with the research? First, it is most difficult to evaluate the effect of the various simplifications and assumptions which have been made to develop the display system model. Second, the model's output is only as good as its inputs - the application and hardware specifications. Because the appropriate data is not available, the application specifications have been estimated. They may or may not be satisfactory. The taking of detailed data on display applications, rather than the general data available in the appendix, would be most helpful. As time goes by, costs of the display subsystems will change. The guidelines will therefore also change: they are not lasting and enduring, although the techniques used to find them are. Despite these weaknesses, and because of the strong points, it is felt that this research is a solid beginning toward the Analysis and Design of Interactive Graphical Display Systems, on which others can build.

RE FERENCES [1] Adage, Inc. System Reference Manual - Adage Graphics Terminal, Boston, 968. [2] Adams Associates, The Computer Display Review, Bedford, Massachusetts, 1968. [3] Adams, Charles W., "Grosch's Law Repealed, " Datamation 8, 7 (July 1962), pp. 38-39. [4] Annerman, Anne B. et.al., Displaytran - A Graphical Display Oriented Conversational Fortran Facility for an IBM 360/40 Computer, Technical Memo. No. K-39/67, U.S. Naval Weapons Laboratory, Dahlgren, Virginia, July 1967. [5] Arbuckle, R. A., "Computer Analysis and Throughput Evaluation," Computers and Automation 15, 1 (Jan. 1966), pp. 12-15, 19. [6] Ball, N. A. et.al., "A Shared Memory Computer Display System, " IEEE Trans. on Elec. Comp. 15, 5 (Oct. 1966), pp. 750-756. [7] Corbato, F. J. and V. Ao Vyssotsky, Introduction and Overview of the Multics System, Proc. FJCC, Spartan Books, Washington D. C., 1965, pp. 185-196. [8] Corbato, Fo J. et.al., An Experimental Time-Sharing System, Proc. SJCC, National Press, Palo Alto, California, 1962, pp. 335-344. [9] Cross, P., "A Logic Drawing Board for the PDP7/340," The Computer Bulletin 11, 3 (Dec. 1967), pp. 237-245. [10] Cox, D. R. and Walter L. Smith, Queues, John Wiley and Sons, Inc., New York, 1961. [11] David, M. R. and T. O. Ellis, The RAND Tablet; A Man-Machine Graphical Communication Device, Proc. FJCC, Spartan Books, Washington D. C., 1964, pp. 325-331 [12] Dawson, D. F. et.al., "Computer-Aided Design of Electronic Circuits - A User's Viewpoint," Proc. IEEE 55, 11 (Nov. 1967), pp. 1946-1954. 195

196 [13] Dertouzos, Michael L. "An Introduction to On-Line Circuit Design," Proc. IEEE 55, 11(Nov. 1967), pp. 1961-1971. [14] Dertouzos, Michael L., "CIRCAL: On-Line Circuit Design," Proc. IEEE 55, 5 (May 1967), pp. 637-654. [15] Digital Equipment Corporation, PDP-8 User Handbook, Publication F-95, Maynard, Massachusetts, 1968. [16] Digital Equipment Corporation, Precision Incremental CRT Display Type 340, Maynard, Massachusetts. [17] Digital Equipment Corporation, Small Computer Handbook, Publication C-800, Maynard, Massachusetts, 1968. [18] Digital Equipment Corporation, 338 Buffered Display Instruction Manual, Publication DEC-08-H6AA-D, Maynard, Massachusetts. [19] Display Techniques Branch, Rome Air Development Center, Compendium of Visual Displays (Second Revision), Rome Air Development Center, Rome, New York, 1967. [20] Foley, James D., "A Markovian Model of the University of Michigan Executive System," Comm. ACM 10, 9 (Sept. 1967), pp. 584-588. [21] Gruenberger, Fred, "Are Small Free-Standing Computers Here to Stay?, " Datamation 12, 4 (April 1966), pp. 67-68. [22] Gruenberger, Fred et.al., Computer Graphics, Thompson Book Co., Washington, D. C., 1967. [23] Hargreaves, et.al., Image Processing Hardware for a ManMachine Graphical Communication System, Proc. FJCC, Spartan Books, Washington, D. C., 1966, pp. 363-386. [24] Hillegass, John R., "Standardized Benchmark Problems Measure Computer Performance, " Computers and Automation 15, 1 (Jan. 1966), pp. 16-19. [25] Information Displays, Inc., Modular Graphic CRT Displays Available from Information Displays, Inc., IDI Data Sheet 127367, Mount Kisco, New York, 1967.

197 [26] Information Displays, Inc., The New IDIIOM, IDI Data Sheet 148-767, Mount Kisco, New York, 1967. [27] International Business Machines Corporation, General Purpose Simulation System/360 User's Manual, IBM Publication H200326, White Plains, New York. [28] International Business Machines Corporation, S/360 General Program Library, GPAK, An Online System/360 Graphic Data Processing Subroutine Package with (VlM1) Realtime 2250 Input and Display, White Plains, New York..9] International Business Machines Corporation, "1620 Electronic Circuit Analysis Program (ECAP)," User Manual, IBM Report 1620-EE-02X, White Plains, New York. [30] Joslin, Edward O. and John J. Aiken, "The Validity of Basing Computer Selections on Benchmark Results," Computers and Automation 15, 1 (Jan. 1966), pp. 22-23. [31] Karplus, Walter J. (ed. ), On Line Computing, McGraw-Hill, New York, 1967. [32] Kennedy, James R., A System for Time-Sharing Graphic Consoles, Proc. FJCC, Spartan Books, Washington, D. C., 1966, pp. 211-222. [33] Knight, Kenneth E., A Fast Sort of Country, Unpublished Ph. D. Dissertation, Graduate School of Industrial Administration, Carnegie Institute of Technology, Pittsburgh, Pennsylvania. [34] Knight, Kenneth E., "Changes in Computer Performance," Datamation 12, 9 (Sept. 1966), pp. 40-57. [35] Knight, Kenneth E., "Evolving Computer Performance, 1963-1967, " Datamation 14, 1 (Jan. 1968), pp. 31-35. [36] Koford, J. S. et. al., Using a Graphic Data-Processing System to Design Artwork for Manufacturing Hybrid Integrated Circuits, Proc. FJCC, Spartan Books, Washington, D. C., 1966, pp. 229-246. [37] Konkle, K. H., "An Analog Comparator as a Pseudo-Light Pen for Computer Displays, " IEEE Trans. on Elec. Comp. 17, 1 (Jan. 1968), pp. 54-55.

198 [38] Kucera, John J., "Transfer Rate of Information Bits, " Computer Design 7, 6 (June 1968), pp. 56-69. [39] Lathrop, Jay W. et. al., "A Discretionary Wiring System as the Interface Between Design Automation and Semiconductor Manufacture," Proc. IEEE 55, 11 Nov. 1967), pp. 1988-1997. [40] Laver, Hugh C., Bulk Core in a 360/67 Time-Sharing System, Proc. FJCC, Thompson Books, Washington, D. C., 1967, pp. 601-609. [41] Lawler, E. L. and M. D. Bell, "A Method for Solving Discrete Optimization Problems, " Operations Research 14, 6 (Nov. - Dec. 1966), pp. 1098-1112. [42] Lourie, Janice R. and John J. Lorenzo, Textile Graphics applied to Textile Printing, Proc. FJCC, Thompson Books, Washington, D. C., 1967, pp. 33-40. [43] Nielsen, Norman R., "The Simulation of Time Sharing Systems," Comm. ACM 10, 7 (July 1967), pp. 397-412. [44] Parzen, Emanuel, Stochastic Processes, San Francisco, Holden-Day, 1965. [45] Prince, David M., "Man-Computer Graphics for ComputerAided Design," Proc. IEEE 54, 12 (Dec. 1966), pp. 1698-1708. [46] Pryor, T. Allen and Homer R. Warner, "Time Sharing in Biomedical Research, " Datamation 12, 4 (April 1966), pp. 54-63. [47] Ruiz-Pala, E. et.al., Waiting Line Models, Reinhold Publishing Corporation, New York, 1967. [48] Schwartz, J. I., E. G. Coffman, and C. Weissman, A General Purpose Time-Sharing System, Proc. FJCC, Spartan Books, Baltimore, 1964, pp. 397-411. [49] Schubik, Martin, "Simulation of the Industry and the Firm," American Economic Review L, 5 (Dec. 1960), pp. 908-919. [50] So, Hing C., "OLCA: An On-Line Circuit Analysis System," Proc. IEEE 55, 11 (Nov. 1967), pp. 1954-1961.

199 [51] Solomon, Martin B., Jr., "Economies of Scale and the IBM System/360, " Communications of the ACM 9, 6 (June 1966), pp. 435-440. [52] Spitalny, Arnold and Martin J. Goldberg, "On-Line Graphics Applied to Layout Design of Integrated Circuits, " Proc. IEEE 55, 11 (Nov. 1967), pp. 1982-1988. [53] Stotz, R. H. and J. E. Ward, Operating Manual for the ESL Console, ESL Internal Memorandum 9442-M-129, MAC Internal Memorandum MAC-M-217, Massachusetts Institute of Technology. [54] Sutherland, Ivan E., Sketchpad, A Man-Machine Graphical Communication System, Proc. SJCC, Spartan Books, Washington, D. C., 1963, pp. 329-346. [55] Teichroew, Daniel and John F. Lubin, "Computer Simulation - Discussion of the Technique and Comparison of Languages, " Communications of the ACM 9, 10 (Oct. 1966), pp. 723-741. [56] Temes, Gabor C. and Donald A. Calahan, "Computer-Aided Network Optimization - The State-of-the-Art, " Proc. IEEE 55, 11(Nov. 1967), pp. 1832-1863. [57] University of Michigan Computing Center, Michigan Terminal System, (2nd Ed. ), Ann Arbor, Michigan, 1967. [58] Vorhaus, A. H"., "General Purpose Display System, " Datamation 12, 7 (July 1966), pp. 59-64. [59] Wallace, Victor L. and Richard S. Rosenberg, Markovian Models and Numberical Analysis of Computer System Behavior, Croc. SJCC, Spartan Books, Washington, D. C., 1966, pp. 141-148. [60] Wallace, Victor L. and Richard S. Rosenberg, RQA-1, The Recursive Queue Analyzer, Systems Engineering Laboratory Technical Report no. 2, The University of Michigan, Ann Arbor, Michigan, 1966. [61] Ward, John E., "Systems Engineering in Computer-Driven CRT Displays for Man-Machine Communication, " IEEE Trans. on Systems Science and Cybernetics 3, 1 (June 1967), pp. 47-54.

200 [62] Williams, T. G., Time Sharing System Organization for Computer Graphics, Proc. Second Hawaii International Conference on System Sciences, Western Periodicals Company, 1969. [ 63] Wood, L. H. et. al., "The Amtram Input-Output Terminal, " Computer Design 7, 3 (March 1968), pp. 68-74.

201 Appendix A THE PREPROCESSOR PROGRAM, AND ITS INPUT DATA The purpose of this appendix is to discuss the PREPROCESSOR program, and its required inputs. This program is used to determine which of many remote computer-display controls are appropriate for a display application. The decision is based on each unit's cost, instruction execution rate, and display capability, as was outlined in Figure 4-8. In the program the reciprocal of X4, instruction execution rate, is used in place of X4, and is called T. Therefore certain of the inequalities in Figure 4. 8 are reversed in the program. Naturally, only units with the required number of display consoles are considered. There are two sets of input data for PREPROCESSOR. The first, loosely called SOFTWAREDATA, describes the display application to be implemented. These parameters are R, the number of required display consoles; Qmin' the minimum acceptable quantity of display material; x, the fraction of displayed information shared among all consoles; Qi, i=l, 2,..., 5, the weights to be applied to the five standard display test patterns; and wi, i=l, 2,..., 42, the relative usage of each display instruction. An example of this data is shown in Figure A-1. A second set of data, called HARDWAREDATA, describes all the remote computer-display controls which are being considered.

202 Each remote computer can be used in up to eight different display control-display console configurations, as in Table 6-5. Accordingly, the description of each remote computer-display control consists of first an alphanumeric description of the unit, and quantities called CRT(I, K) and CNT(I, K), K=1, 2,..., 8, which are the number of display consoles and controls in each of the eight possible configurations. I is used to index the various remote computer-display control types. Next is the total dollar cost of each configuration (without any core memory), and finally, the time (in microseconds) taken by this unit to execute each of the 42 display instructions. The complete remote computer-display control data base can be seen in Figure A-2. Aid in interpreting it can be had by examining the READ statements and their FORMATS in Figure A-3, which is a listing of the PREPROCESSOR program. HARDWAREDATA and SOFTWAREDATA input is via unit 5, and output data is on unit 6. A typical output of the program is shown by Table 6-6. The two digits following the unit's alphanumeric description are the number of display controls and display consoles, respectively.

Figure A-i Description of Display Applications $LIST SOFTIAQEOATA I DESCRIPTON CJF %rEAEiAL 2-nI1FNSI0NAL DRAWING APPLICATION 2 1.Ali75 ____. __ ____ ___ _ __ _ __ _ __ _ _ _ __ _ 4 l~Cui~n, 6). 0 1.Cl.0I.01 0025.0C25.CC25.0025.0025.52.001 7.C15.019.CC5.CC5.005.02.02.02.065.065.065 8.01.01.C1.005.C765.1.01 2 9 E 5CPIPTRI0N C F A GENERA -ThYLN51L al CRAWING APPLICAT ION 10 1 - 11 0150 __ ____ _ _ _ __ _~_ ~_ __ ___ __ __ __ __ 12 1.C 13.0 0C.0.5.9 14.0063. 0063.0063.0063.0015.00 15.015.0015.0015.3245.0625.0007 _I5~________ ffC~i? ~ 09.ft00403L 1 ___G C03-1.- 0 0Q3 1. 0 1 2 6,.0 1 26. 0 1 2 6. 0 4 1 30 4 3.0413 16.0063.0063.0063.0031.C478.CC63.0063.0781.0781.0781.0781 -17 ___ ___0ESCRIPTN CF A CGENEPAL NETICRK ANALYSIS PPCCRAM___ _ 18 1 19 0060 C 20 1.0 21.0iCC.,CC7.20CC.0QCC.70C0'22.0067.0C67.C067.0067.0016.0CC16.016.0016.0016.3476.0007 3_23 ___ —_ -FI.0 I 0__03.0033.033.00-3.0134-. 0134.-0134.044.044.044 24.0067.0067.0067.0033.051.CC67.0067.0833.0833.0833.0833 25 DESCRIPTICN OF A TEXT-[CITINC APPLICATION 26 1 37 __0I_ _ _-_ 28 1.0 29 999 91 L. X0 EC_ 00QC. FQO _ 30.01.01.01.01.CL.01.02.1 31.05.05.C25 C025.025.025.1.1.1 32.1.01.01.1.03.03.04

Figure A-2 Description of Remote Computer-Display Controls SLIST HARCI40ECA4T. 1 4 2 1.1 039; L EC 3_23_9 PEI VCT I 0 ISpLAY TERIP INA L 2 1121314122421344 4E0C _ 6 2700 7C 54 CC.eICC.50, C~L 114400 1220C00 A5900C 4 115 "1I 120 51 24 IS 5 1 14 14 14 29 450 1160 28 11 15 6 C 14 15 275 270 11 13 11 VS 5 31 35 40 2 25.- __225 25 25 C 90 -16... 142 IC 8 30 192 192 5.9G C__49_0 0 8 CEC 338 + [E7658FL2 AP lu-MATTC __9__.1121a_1412242 33 4 10 51405 44200 75900 9160C 88800 117900 1255CC 162500 11 115 14 48 120 51 12 26 15 5 16 16 14 14 2c 450 175 2 II 135 2 I 4 V 40 40 11 13 11 15 5 31 35 40 14 25 29 25 2 5 1; " 142 1 C 8 3 0 19 1 q2 150 1 5( 19 DEC 33q 14 1121314122423344 17 55')0CC 6c700 ~240C 951Cr 02000 12140 120000 166000 115 216 48 120 51 - 18 6 lo 10 10 7 7 1 7 250 652 18 5 8 20 18 19 21 21 4 7 6 8 3 21 30 28 4-6 A61 -4 VS 1 6 4 4 2. 12 12 0 70C 700 22 DEC 339 + u-TENT ED 01ET61'AT1C 23 I1 21 14I 12242344 24 70000 73700 46/0C 09100 9600 125400 133000 170000 25 115 216t _ 12 - 5126 18 6 IC 1 7 7 17 2 0 P. 18 5 8 27_ i 10 21 21 4 7, 8 3 21 30 28 28 16 1 16 1 56 10C 3 4 4 27 120 120 100 100 29 POP-8 + CE 34C 019PL86 30 1121714 1i~42V 4i 31 7 C C 71400 P48410 7100C I106 4 0 031I000C 1 3 1 0 CC 32 20 4 44 l 52 33 _000 26 7 145 140 14 14 13 5CO 1565 110 70 15 34 75 80 14 15 275 270 1 1 1 11 15 5 31 35 40 42 25 28 OQ 16 142 10 8 30 12 102 9C0 000 36 PUP-8 + 340 CISPI,A + E X P 178. 37 112131412242?Q44 38 44800 42200 74900 8700C 7450C 10000 104500 134500 19 -3__ _ 84 _ 4 _ 44 1 52 40 0002 8 1 7 145 14 0 14 14 13 500 480 110 70 15 41 75 40 14 15 40 40 11 13 11 15 5 31 35 40 42 25 25 25 25 cc 16 142 10 8 30 102 192 150 150 _432____~. P-P -9 +060EC 430 P199618 Y 44 1321314122423144 45 47020C 447 r 0T 7 90100 77007 112400 117000 147000 46 84 2)4 64 100 52 47 1P 6 101 7 7 7 3CO 844 66 31 8 48 56 F5 14 1 0 I 150 7 8 3 21 30 28 40 14 I1 16 56 10 93 4 4 24 120 120 700 700 5 OP-9 + 01EC 34(' 01SPLAY + EX. 8ITF 5l 11217141024231,44 C~2 e;1000 r8700 7 14'00 c41? 4100 116r400 1?107 15I1030 43 44 2 0 4 64 1 0 0 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 54 18 4 91 101 3 7 7 300 281 64 31 8 -- VS86 55 1" P; 21 21 5 1 6 8 3 21 3 2 56 16 14 14 14 56 10 83 4 4 24 120 120 100 100

Figure A-2 (continued) Description of Remote Computer-Display Controls 5LDf__ fik0_ AiPC- 8 _ _IDL~IIO _0 -0l- __c_ 58 1121314122423344 59 76430 91936 1C7430 1229C0 14186C 17286C 2C7290 272721 60 1. 5 87! 157 312 124 ~26_____ _......_... _~15.2 8 1~........ _16....!_ __ __61_4 1_! 4....2~4 5_4S_1G1 1 281 __4ZO 6 28 I _1 5 62 0 0 14 15 275 270 11 13 11 15 5 31 35 40 63 _2 __....02.5...25____.2.. 28 9000 C. ___.!. ___ 192 1.2_. 900 900 64 PDP-P + I10 10000 + EXTENDEO APITH. 65 1121314122423344 66 7093C 05430 110C30 12640n 145360 176360 210790 276221 6 -7_ _!J__ 05............ 3871 15- 3 312 124:8 26 8 15 5 16 16 14 14 29 450 175 28 11 15 __~.9____.............. 14 l....15__ 40 40 I I 3.. 14 15 5 _3 1 35. 40 70 25 25 25 25 90 16 142 1C 8 30 192 192 150 150 71 DEC PDoP- + 101D 1100 72 112131412242?344..7.3 6....._0.260 _ 76410 R456 C 92710 124520 14C8 20 180780 237040 74 116 200 60 152 18 75 26 8 15 5 -16 16 14 14 29 450 1160 28 11 15 76 0 0 14 15 275 270 11 13 11 15 5 31 35 40 77 25 25 25 25 90 16 142 l~ 8 30 192 192 900 900 78 P[UP-P + TCI ll10 + EXTENDED APITH. 7 - 1121314122423344 80 7176C 79q91c PQ06C 5621C 126020 144320 184280 240540 ___P___..........16- 3..80...C..152_...8. 82 26 8 19 5 16 16 14 14 29 450 175 28 11 15 83 14 15 _ 4C 40 11 13 11 15 5 31 35 40 84 25 25 25 25 90 16 1? I 8 30 192 1G2 150 150 __5 P P-9 + II. 12 0 0086 1121314122423344 S. 87..... 8~25,00 985qQ_ 114500( 13250c 147000 177000. 211500 286000 88 105 971 157 31? 124 Po 18 6 1i 5 IC 1C 7 7 17 250 652 18 5 8 C0 I I 21 21 6 7 6 8 3 21 30 28 91 6 16 16 16f I 56 1]C 3 4 4 27 120 120 700 700 9 P2-0- + 101 C' 00 + EXTENDED APITH. 53 1121314122423244 94 865Cf 102500 118500 1 345CC 15100 1591000 215500 290000 0"~~5 105 971 157 312 124 96 1E 6 1C c 10 1C 7 7 17 250 89 18 5 8 97. 1 1 21 21 6 7 6 8 3 21 30 28 98 16 16 1 6 1/: IC 8r 3 4 4 27 820 120 100 100 c9 PDP-9 + IL1 11C000 100 1121314122423344 101 7426C P2410 6q 6C 7 1 c 170520 146920 186780 243040 102 116 20C,. 152 18 -. C3! 8_ I 1 C IC 7 7 17 250 652 18 5 8 104 1P 1 21 21 6. 7 6. 3 21 30 28 lJ5...16116. 16.6 10 -3 4 4 27 120 120 700 730 106 PDP-9 + I11 I1]1nO + EXTE1DEC ARIT,. 107 1121314 122423344 108 7826C 86410 q466C 10271r 134522 15082C 190780 247040 _lW.... -.... 1 _.?_PC 62 _ 152 18 110 18 6 1 5I 1 80 7 7 1' 250 8c 18 5 AL_.111 1 - 21 21 f 7 6 8 3 21 30 28 112 16 16 16 18 56 10r P 4 4 27 120 12 IC 100 113 IDI INPL T 1 LTNLT VACHINE (IC IC01 114 112131410C00C0CC 115 - 71000(_ P4r0C 760C IltICC 116 1r0 7?1 1%" -1 12~

Figure A-2 (continued) Description of Remote Computer-Display Controls _L1li 1 ___I~ 9IL12 _2_ 1L dL_.1_1il 4 - 7 Z5 0 7 5~_2Z _I4__IA~4____ 118 50 50 14 14 I 10 14 14 14 14 3 27 4 30 119 7 7 7 7?C5 16 249 5 7 14 200 20C 900 900 120 1 TDIICP + EXTENCEC AR ITFATIC 221 -11 2 1 3 1 4 1 0 ___- _ -_ ___ ___-___ 122 735CC 868CC 101CC 113400 123 - - 7 6L ifi 3 103 __J19 _ _ 124 14 9 13 2 ii 11 13 14 7 25C 102 22 14 14 1 2 50 80 14 14 18 27 14 14 14 14 3 27 4 30 126 7 7 7 7 205 16 249 5 7 14 200 200 172 270 iL ADAGF AfT L0_-_ - 128 11213141CCCCC0C L12 li~_ 00fi6 24111. _2~ 10C_ -3~C ____~ _~ ___ -... -. __ _____-__ ___. 130 130 525 200 220 65 131 24 5 F 20 20 16 16 1 200 144 16 20 8 132 40 45 28 28 40 4C 24 24 20 28 6 40 10 52 0 20 2 26 208 4 0 320 -16 16 24 144 144 126 126 134 ADAGE ACT 30 135 1000~0000 - _ ____ - - -11 CC 136 95000 106300 117600 128900 137 130 525 200 220 65 138 101 11 8 20 20 16 16 1C 200 1 16 20 8 139____ 40O 45 28 28 40 40 24 24 20 28 6 40 10 52 140 200 2C 20 26 208 40 320 16 16 24 144 144 126 126 A A D A C EACT 50 - - _ --- ___ _ _142 1121314100000000 143 125000 136300 1476CC 158900 144 160 6890 250 270 80a _L4 5 6 4 20 20 16 16 10 200 1 16 2C 8 146 40 45 14 14 20 20 12 12 10 14 3 20 5 26 L47__ 100 Ic IC _i__C I 1C4 20 1(C 9 8 12 _ 72 - 72 - 63 63 201 D LC 338 1TH VATRIX tMPY 202 1121314122423144 203 58000 72700 54 0 98100C I8000 134400 152000 199000 20_4_____ ~____~3_ U5 168 - 120 51 205 26 8 15 5 16 16 14 14 29 480 1 28 1i 15 0-0 14 15 2 7 5 27C 1 I 1 3 1 1 1 5 5 31 3 5 40 207 25 25 25 25 90 16 142 10 8 30 192 192 900 900 208 CEC_338_+EAE 4 MATREX IX_ 209 1121314122423344 210 _ 615CC 76200 CC 900 10160 1C85CC 137900 1555CC 202500 211 115 216 68 120 Si 212 26 -1 5 _ 16_ 16 _614 14 29 450 1 28 11 15 213 14 15 40 40 11 13 11 15 5 31 35 40 214 25 25 25 28 90 16 142 1C 8 30 192 192 150 150 215 DEC 339 + IATPIX 217 65000 79700 92400 105100 112000 141400 159000 206000 2I8~ - 115i ~2~- 63__ 120 __ 51 219 18 6 10 5 10 10 7 7 17 250 1 1 8 8 220 18 10 21 21 6 7 6 8 3 21 30 28 221 16 16 16 16 56 10 83 4 4 27 120 120 700 700 222 CEO 339 + EAE + MAT IX 223 1121314122423344 224 69Cr P- 73C1 C6404 CI9100 116000n l4541 163200 210220 225 118 216 65 120 51 226 1 6 10C 5 1 10 7 7 17 2t0 1 19 5 8 227 IF 1 21 21 6 7 2 n 3 2 3 25 328____ i<.r~ _J~~26___e 1 56 10 1 I 3 4 4 27 120 120C I0 100 229 POP-F + CEC 240 + N1TP1I

Figure A-2 (continued) Description of Remote Computer-Display Controls __30~...... Li! 31 4! 224 2l134 34 4- 4 231 5100CC F: 7 C P140C 9410C q1000 126400 131000 17100C 232 4 204,4 (:4 1 n 52 233 CCC26 13 7 145 IC6 14 14 13 500 1 IIC 7C 15 _.234... 5....EC - 14! 275 270 11 17 _ 11 15 5 31 35.40 235 255 2 25 25 90 16 142 10 q 30 192 19q2 900 900 _23_6 C-P 4+ EC 34P + F A -4 tATR1IX 237 1121314122423344 238 545CC 722C C q40 O 976 0 c450Q 129900 1 24502 174500, 2 q q4?n4 64 1 n 5? 24_67 _...C.r26 I3 7 145 150 14 14 13 5CC 1 110 7C 15 241 75 p 14 I 40 40 11 13 11 15 5 31 35 40 24+22. 2.25 2_ q 25 c 1; 142 1C 8 3C 102 1? 150 150 243 PDP-9 + [EC 34 + +AT Tx 244 1121314 122427344 245 570C0 747CC P740c 1LCCm0C 7e0o 132400 147000 187000 246C _- 94 24 64 I10 52 247 1P 6 9 - 1 1C1 7 7 7 300 1 66 31 8 248 56 56 19 10 10 150 6 7 6 8 3 21 30 28 249 16 166 6 1 56 1C 83 4 4 24 12C 120 7CC 700 259 POP-9 + CEC 34C + [AE + MATPT' 251 112131412?423144 252 61 "CC 797C 01400 C I41C 10100in 13640 151000 191000 253 P4 274 64 10o 5? _54 1 9 6 c 6 q1 ICl 7 7 7 C00 1 66 31 8 25= 56 55 1P 1C 21 21 6 7 6 8 3 21 30 28 256 16 I6 16 16 6. 1C P3 4 4 24 120 20 1C 100n 257 DEC Pl.)P-8 + Ir0!n + 4ATVY X 258, 1121314177422334 14 25q 8643C 101C30 117430 1329Cr'I 6 1- 296C 237290 3C2721.2.T0 10t5 -q71 1 7 312 124 261 26 8 ~ 5 16 16 14 14 29 450 1 29 Il 15 26? 0 1 4 1, 275 7 i0 11 13 11 15 5 31 35 40 263 255 2 5?2 n 16 142 10, 3C 192 192 900 m00 264 P0P-8 + 1C0 100U) + [AC + "ATRI 785 1121314172423"44 266 _8c99 1 C5430 1 2 0q30 136400 16 53 6 l 6 1 6 I37 240790 306221 267 105 921 157 31 124 268 26 15 5 16 16 14 14?9 450 1 11 15 26', 14 15 40 40C I I 11 15 5 3t 35 40 270 25 25 25 6 C I6 142 1 8 3 192 1 150 150 271 EC P'CP-8 + I1FT 1 100 + 4ATPIX a7e-2..121314122427344 273 3926C P410 04560 1C2710 14452, 16C02C 21C780 277040 274 116 2. 0 60 152 18 275 26 8 15 6 6 16 14 14 29 450 1 28 11 15 27.6 0 0 14 I, 275 270 II 13 11 15 5 31 35 40 277 25 25 25 25 0 10 16 14 C 1 3C 1? 192 q0 900 278 POP-8 + [1 11003 40FAE + AIFIT 279 1! 21314 1 2423244 280 8176C 9Cl.1 cq0A C 1C 0'10 146I2' 1 - 32rq 214280 32C540 281 11 2:0 6C 1 5 18 _?_2 26 8 16 5 1( 1 14 14? 45C, 1 28 11 15 283 14 4 4 11 13 1! 15 5 31 35 42 284 25 25 2P OP cC 1 142 lr 8 3 7 32 15 0 150'CS p> o-C + 101 PF? + A~T 266 1121312 12242?44 ___ ___4__ __ 26P7 q2~ 1 6 0 0 < 124'"l42'0 1(7I 17 7 It II?7, 241620?60,C7 78, 1 21 157' 1 124 29 I 1 10 1 7 17 2 0 1

Figure A-2 (continued) Description of Remote Computer-Display Controls 7C~. 18 1(' 1 21 F 7 6 9 2 21 3 - z8 291 16 1I 16 r 0 3 4 4 27 120 120 7CC 700 202 pr f P- + 11 F I I - +r' F A + VYFAJ- X?s3 1l2l3I4l22~4 2 44 2C'4 6 5 (I I 1 12 2 H 1 C 144C00 171 0 C 21000 245500 330000 295 1"" ~ 71 167 I12 124 2c6 16 10 1 oI 7 7 17 2 0 1 18 5 - I8 297 1F I 21 21 6 1 6 9 3 21 30 28 2CPI IL> Iffi6 J _6 L E3 _ _ 4 4 27 17C 12C ICC 100 2q 0P + I 11 1 O 10 + MATRIX 300 11 1I2131241 24 74 4 301 94266C C-41 1C5 6 C 109710 15C5?C 16 620 216780 283040 302 116 q 69 16 18 - -n3 1 P 6 I C 1C 10 7 7 17?50 1 18 5 8 4C4 1CO1 21 7 6 8 3 21 30 28'305 16 1~ 1r 16 56 10 63 4 4 27 120 120 7CC 700 pF0-C + I f7 IICIC + [7F + 8ATi TX 307 11713111 4 2 iz44'Cp ~~ 862 C 10's 6 I C 11 717 14520 170620 220780 297040 309116 269 60 I 18 30" 6f! t6 1> I 5 I C C 7 7 17 250 1 8 5 9 311 1 21 1 21 7 6 8 3 21 30 28 7I 16 I 16 16 16 1 6I 4 4 27 120 12C 100 109 313 V1 I FCN + AU T IX 314 1l213141~00C00~r 31 5 210CC 94300 U 07C99 17 C90I tC3 316 109 Lil 15C 31 1 29 317 14 9 I'.2 11 Il 13 14 7 250 1 22 14 14 316 5I 50 14 14 1 C 160 14 14 14 14 3 27 4 30 7 7 7 7 2'S 16 24~ q 7 14 200 200 9CC 900 320 I10110 [ vA4 + V AT 1Ty 321 1 12?1 ",1 4 1? eC 2000 0 32 I I I 1 I ~ I I" I 3 2 2 L 0 C 6 9 0 C ~ L I 2 i h 4 0 C_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 323 109 761 19 M C 129 324 14 9 1 11 Il 17 14 7 250 1 22 14 14 325 50 50 14 14 16 27 14 14 14 14 3 27 4 30 326 7 7 7 7 205 16f- 2 4 7 14 200 200 172 270 [ NC C0 FIlE

Figure A-3 The PREPROCESSOR Program $LI1 FPCOESS/S -1 C, 0 1. IV P L I ICIT I NICEP (A-Z) 11 NCEN S ION O, (q) i (42),C 12C,, C PP (1C,, IET( 12,42),CC 12C i) 17" u r t~~ ~~ n IYFNSIC CP!T ( 1' C 6t _,C-I\T (1.2_0 01 8 LH~ZL Q R R ( 1220 T 120 ) 1LINLNSFN CCSf(12C) 1 0 E L I, X, TI TWE 1ININ - ___ I____T_ _I C FIRSI PFA IN INFCPAICEN CN HAPEWARE -___ —_- ____P E EA (5,IC) NINST,NCC1MF 17C C NINST IS N\MFEP OF CISPLAY INST'LCTICNS 171 0 NCCNP IS NONELN OF C0IPUTEF/CCNTPCLS EE INC CCNSICRECR 175 1 FCPNAT (12/13) 1 F CO 30 I=ltnCNp (L ICC- P E t - (5- FNo6OC I(CPT( I J )CNT ( I,J),J=1,8, 200C 1 (0c0c41 _,j0 j I,,) IJ=,FI(O PPI I,J ),J=1,5), I ICI( IJ),J=1-NIIN ST 210 C C IS 4/N LESCRIPTI(N CF CCNFLTER AN\ CISPLAY CCNTRC L 2 2 C CPT IS N P[R OF CRT'S IN T I-I CC NfILFAI ICNUPATI___ 23C C CNT IS N LIE F 0F [ISPLAY CCNTFCLS IN THIS CCNFIGURATIGN 240 C CC IS COST OF THIS CFNFICLAT[ICN 250 C CFR IS CEIFLAYAPL[ PFPCENTkCE CF TEST PATTERNS C ILC T ICTS INSIOCTION FXHCUTICN TiNE 27C 5C FCP'AT (9A4/l6I1/~ IE(/51C/ l4U/1 415/14I 5) 2 50 30 C C N 1Nlt _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 2CC 60 CCNTINLF 3CC NANFLJST /NA'NI/ NCCPF,KINST - __ 310 kRITF ((,NAVl). C NRAL- IN 1NO"ENrtTIC'N FOP A FAPTIICULLA APPLICATIC-N 340 5 CCNTITNU 34 5. PEAC (5,11) A 346 19 FORNAT (A4) 0D 3F. REA: (5,2C) P [CCT. 351 20 F[RPAT (Ii) IcO C PQO021 IS NURPER C F [ISPLAY ( NSCLES NEECEE IR) RELA (5,21) 0C 3I2 21 FCRPN.T (14) 400 C OP IS THE OUJA TITY OF INFCRNATIEN IHIOC NUST EF DISPLAYED 401 EAC (5,2?, 2 402 22 -OCFAT (FM.5) C 4 T - S FPAOTI PF (: TISPLAY CIFFERFNT FOR EACH CCNSCLE 411 PFPC (5,23) (CE(J),J=I,5) 412 23 FEPMIT (SF5.4) 42C C CL APE NEICFTS FOP 9 TEST FATIEFNS 42-1 R C ( -, 24 ) I ( 1kN (J ),_J=1, N-IN-ST-) 422 24 FOMPWT (14F5.4/14F'.4/14Ft.4) 430 C I(N APC P CIOH-TS F CR TCE NIN SI T (SPLAY IKSTRLCTIC \ FOR THIS APPLICATIC 450 C 4-6 C I0L NL I FINE N HIC- I F ANY, CISPLAY CONTROLC N CISPLAY ENCUC)470 C INFCRVATICO 4 1 0C C - - - _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 40 CC 11 I I=TNOONF 5-c-c- [C=0 510 00 70 J=1,5 520 70 O=C+( P4, - _ _ __________ 53? C C IS PNOrtlOT [ISPtAYABLEL ON 1 [PT PY. CENTCLLER 540 NINJ=_ 550 Y IPCST= 1000000 560~ [0.__~_____. C LC J=1, 5/C IF(CPT(IJ).NF.PCCCPl) CO TO 10 5 c I F (CFT( IJ)_.C.) 00 TOC P;C 5C l CN0=0/) X* (CT 1(1,J)/CNT (1,0- )+I.()

Figure A-3 (continued) The PREPROCESSOR Program C T[- F -Ic ^:I S L t I FL Y i' L Lt CF L L C' IT' C ( [ C-L lo' 3: I.') (r' C T rF" r ~. — r' ~ rf T:~;N _,-' L._._.~.J. __.__..LLY. P. y L C L h,(: C.' C FlTr IF I T1I. c'II IlN I 7lI[LS CCSI FCR I - I (CL( I ) CT I, CS) CC TIC 7__'-C F [INJ=J h7C'I lC.=e T E tr 775. C N _! _Le__ _ __ _ a5-.C 7 CC CCIN IL 7CO C CC! NCT F 7If' IF I NJ.CT.)J GC TC C 5 7('4 C L S'I ( I)=r 7'-r CC Tr ] Flr 7"C CC 1( I )= INC_ 77?( kI D, ( I): -INJ 3- r C IF CC(ST I S ZlP,-,'FA.NS FC' I 1F1L4E WAS NC SLI3TABLE CCNFIC-URAITICN P1' C IFlC~ (Il SAYv- I rF ~ C C CF FSSJEL F CCN FIC:URA1IClS bAS SELECTFC 8,- ___ _I_ __T_______i____.____ A' 1 OI I IF:I I V+ I'..,( I I[T ( I, ) 5r I ( I )=T T I,' 8/'C C TlIS IS NCI^ tVCE CFf INTSTPLCT TIC EECTIC 1TME _ __ a7r l1C CCTIT Nlh..___S____S.. _.FIC. LaT1C' FCR.F.CH I 91i' LC I C J= I NCCv 2C I C r (CC T ( J ). C S I ). L. T ( J.CE.T(I)) C C T J =C _ _ 930 C J CCST C'E AtNC TCK N'f('< E EXECUTICh TIE-, SC CLT IT CCES c. __ _ J F (..i C ( i ). E_...) IC I 1 ^' f 950 IU(CC,( I I.u(.CCSTIJ).ANTL.CN(l).GT.CRQI(JI.ANC.I( I).L.T(J) O-C. 1 CC'ST(J)=C c7C C J CIS FLAV LESS tINC TtKES LCNC-tE, SC 1 C(CE CLT'C CLNTINLE. 9g? 1 4C CCN T I hLF LOC; _C C:,_NL'. PrIAL'CY I L VI1i T CLT VCUT IL CCNFIGURATICT NS IN ASCENCINC PRiICE l 1C NL-'CLTT= 102r' 145 (:LT I=r 10-C T!vX=C.= IC4/0 CC 15C I=1,INCr-F 10 50 I F (C II). ).C. Cl TC 15C _6l _ IFl_.(T ( I )I. L E. lT AiAX ) CC TC ISC 107C l AX=T( I) 01F0 FLTI=I, 1 C 15C CChTINLF lCC IF{CLTI.tC.C) CC TC 2CC 1113 CCS1l(CLTI)=UCST(CUT)I)/4C 112 _- JJ=- ICH (C LT I ) 113C D"ITC (l,16') CCSTIFLTI ),I( tLT,(C(CTUII,J),J=I,q),CNIT(CUTI,JJ), 1140 1 CFTIrFLTII, JJ) _ ___ _, _ 115C 16C F(CZ' T ( I5S vYI L 1C, X,ca4,I2,', I 1) 1160 hCL LI =rt,.'ClT+ I ~1165 L ICC5 LTII): _117C CC Tr l= TE 110p 2.C I-(ntCHLl. (F.lc. t C-r TC?CC 11P IFW I. i- _ _I" _ __ _ 114' CC ZIC I =,TE1 F

Figure A-3 (continued) The PREPROCESSOR Program 1200 210 WRITE (6,22C) 1210 220 FCPMAT (''9999 99s99999S CUMPY TC PAD OUTPUT') 1220 300 GC TO 5 1230 ENC _ENC CF FILE

212 Appendix B THE OPTIMIZATION PROGRAMS, AND THEIR INPUT DATA There are five principal program modules associated with the optimization. The first is a main program, which does little more than call upon two of the four other program modules. They are the input-output subroutines, and the optimization subroutine. The optimization routine in turn calls a subroutine which finds T(R, X, Z). If R> 1, the fifth program module, RQA, is called to evaluate T. The main program is aware only of R and NCOST, the number of maximum costs (C' ) for which the optimization is to be permax formed. These are obtained from the input subroutine, INMOD. For each cost, an optimization is performed with R=1, to find the vector A which minimizes TL(R, X, Z) according to the algorithm of Figure 4-2. If R is in fact 1, A is optimum. If not, the optimization is called via OPT2(R) to find the true optimum, using the algorithm of Figure 4-3. OUTMOD is called to print results. The main program is listed in Figure B-i. The input subroutine, INMOD, is part of the input-output module. It reads all the necessary input data, and calls initialization entries to several subroutines so that the input data is available to them. The output subroutine, OUTMOD, prints out a list of optimum display systems, and the corresponding vectors X (in hex), their costs, and response times.

213 The I/O module is listed in Fugure B-2. Figure B-3 is a typical input data set, wnich, by use of the program's READ statements and FORMATs, can quickly be correlated with the various program variables, the significance of which are thoroughly documented in the listing. In most cases, variables in the program bear the same name used in this report's text. Outputs from this program have been shown in Tables 6-14 to 6-25. Input is from unit 5, and output to unit b. The optimization subroutine implements the algorithms in Figures 4-1, 4-2, and 4-3. The set S' is stored in XARRAY. To conserve storage space, the set S is never actually formed; the comparisons used to reduce S to S' are made between each new X and the current S' before entering X into S'. The program is listed in Figure B-4. Output device 7 is used by this and other programs for diagnostic information. The fourth program module, Figure B-5, evaluates T(R, X, Z) using RQA if required. It calculates the model's parameters from the input information. This includes the division of processing calculations described in Section 2. 7. 1. The array TIME holds the quantities t. (Section 2. 4). If RQA is used, it ultimately holds Ti (Section 2. 7). TIME is used to calculate T in the internal function TIMEF. The RQA program module is documented in a University of Michigan Systems Engineering Laboratory internal

214 memo by I. S. Uppal, dated 18 September 1968, titled, "IBM 360 Version of RQA-1. " A number of subroutines are called by the above programs, and are listed in Figure B-6. The first is STATE, which implements a mapping from the 11-dimensional state space of the display model to a uni-dimensional state index. It, in turn, uses BINCOF to find certain binary coefficients stored in an array. The array is initially calculated by the program FCTSET. DELT finds the change in the state index caused by a change in the 11-dimensional state space, by calling STATE. SETX converts from X to X (Section 4. 2), and XSTAR finds X* (Section 4. 2) from X. COST finds C'(X) (Section 2. 6) for any vector X. Finally, PACESS finds the file storage x access probability 1 - e (Section 2. 3).

Figure B-i Main Program SLIST MAINSOURCE 10 C MAIN PROGRAM Tr PERFORM CISPLAY SYSTEM SYNTHESIS 20 C 3C IMELICIT INTECER (5-Z) 40 RUN=l _ 50'3 kR TT (6.1C) PUN 60 10 FCPMAT ('1',T40,'CPTIMUM DISPLAY SYSTEM CESIGN PROGRAM,' 70 1' RUN NUMPER'.12/I/I) 80! C OC C NCl GET INPUT CATA 100 C 110 R=INMCC(KCQST) 120 C 130 C NCCST IS NUMBER OF SEPARATE CPTIMIZATIONS WHICH WILL BE DONE 140 C 150 1=1 __ __ 160 20 IF(I.CT.NCOST) GO TO 30 170 T=CPT(1lI) ____ 180 IF(T.EC.1) GC TC 25 190 C TRANSFER MEANS XARRAY IN OPT TOO SPALL. GO ON TO NEXT COST 2CC IF(R.EC.1) GO TC 25 210 T=CPT2(R) 220 25 1=1+1 23C GO TO 20I. 240 C 250 C NCW PRINT OUT RESULTS 260 C 270 30 TRASH=CUTMQC0R) 280 PLN=PUN+I 2 GOTO_5 5__ 300 ENC END Of FILF

Figure B-2 Input-Output Program SLIST IDMOCULESOUR 10 C 20 C FUNCTION CALLEC BY "R=INMOC(NCOST)" ro PASS R AND NCOST EASILY 30 f40 FUNCTION INMCC(/NCCST/) 50 IMPLICIT INTEGER (A-Z) 60 PEAL ARRIVELRCUPOUMCIPAGCSTCPUCSTIRTIMETRIPEPSI 65 REAL PROB(100),BM100Q)9BR(lOC) 70 DIMENSION CLINK(16),RLINK(16),NMLINK(16910) 80 DIMENSION CC ORE (16_),SZCCRE(16)NMCORE(1691) 90 DIMENSION CEULK(16),SZULK( 16),NMBULK(16,10) 100 D MENSICN CCCMP(16),TCDMP(16k NMCOM PA6,10) 110 DIMENSION RCOST(50),RESULT(5C),RTIME(50),X(4) 120 DIMENSION XMASK(4),X SHIFT(4) 125 DIMENSION NINST(100),C(ICC,10) _130_f__ c__ _ __ __ 140 C ARRIVE IS ARRIVAL RATE CF JCES FROM EACH USER 160 C URD IS SERVICE RATE OF REMOTE BULK STORAGE UNIT 170 C UMO IS SERVICE RATE OF MAIN BULK STORAGE 180 C UMC IS SERVICE RATE OF PAIN COMPUTER, 190 C FOR AN ENTIRE INTERACTION CYCLE 210 C PAGOST IS COST OF ONE PACE-MONTH OF DISK STORAGE AT MAIN 220 C COMPUTER 230 C CPUCST IS COST OF CPU IF IT WERE USED ALL THE TIME THE 240 C DISPLAY TERMINAL IS IN USE, ON A MONTHLY BASIS 250 0 CLINK.CORE.,CEULK.AND CCCMP APE ALL COSTS OF VARIOUS HARDWARE 260 C PLINK IS DATA LINK TRANSMISSION RATES, IN BITS PER SECOND 270 0 SZCORE IS CORE SIZE, IN UNITS OF 12000 BITS 280 0 SZOULK IS SAMEBUT FOR BULK STORAGE AT REMOTE COMPUTER 290 C TCCMP IS WEIGHTED EXECUTE TIME FCR REMOTE COMPUTER, 300 C IN MICROSECONDS 310 0 NMXXXX IS 40 CHARACTER DESCRIPTION LF ECUIPPENT 320 0 RCOST(I) IS ARRAY OF MAXCCSTS TO BE USED IN OPTIMIZATION, 330 C WHILE RESULTHI) AND RTIME(I) ARE RESULTS OF THAT OPTIMIZATION 340 0 AFTER OPTIMIZATION, COSTII) IS THE ACTUAL COST 350 C NCOST IS NUMBER OF ENTRIES IN THE COST VECTOR 370 C SECONDS, DONE AT REMOTE COMPUTER 380 C NPPPC IS CORRESPONDING NUMBER, BUT FOR PRE- AND POST- PROCESSING 390 0 MODE 400 C MSGLTH IS DATA LINK MESSAGE LENGTH, IN BITS 410 C NXXXX IS THE NUMBER OF HARDWARE TYPES READ IN. IT MUST 420 C BE A POWER OF TWO, 430 C R IS NUMBER OF TERMINALS ATTACHED TO REMOTE COMPUTER 440 C MAXPAC IS MAXIMUM NUMBER OF UNITS OF STORAGE EVER NEEDED 450 0 XMASK IS MASK FOR Xl...X4, AFTER X SHIFTED RIGHT BY XSHIFT 460 C THAT IS, AS FAR RIGHT AS X WILL GO WITHOUT LOOSING BITS OF 470 C XII) 471 C NT IS NUMBER OF DIFFERENT INTERACTION TYPESEACH OF WHICH IS 472 C DESCRIBED BY A FOUR-TUPLE, CDNSISTINT OF NINSTPROBBMBR. 473 0 NINST IS THE NUMBER OF INSTRUCTIONS REQUIRED 474 C PROB IS THE PROBABILITY THAT THIS INTERACTION TYPE WILL OCCUR 475 C BM IS THE NUMBER CF BRANCHES TO MAIN COMPUTER BULK STORAGE, 476 C IF PAIN COMPUTER IS USED. 477 C BR IS THESAMEFORTHEREMOTECOMPUTER __ 480 C 490 READ (5.10) NLINK.NCORENELLKNCOMP 500 10 FORMAT 1412) 510 WRITE_(6,11) 520 11 FORMAT ('1',T28,'AN OPTIMUM DISPLAY SYSTEM WILL BE CHOSEN'

Figure B-2 (continued) Input-OutDut Program 530 1,' FRCM AMONG TE FOLLOWINC- SUBSYSTEMSl' __ 540 WRITE (6,?2) 550 22 FCR.MAT ('0'''O'/TT1O,'DATA LItK CCST. $'.T35.'TRANSMISSIO N' 560 1' RATE, ePS',T75,'DESCRIPTICN/'/'') 57C 1=1 580 24 IF(I.CT.NLINK) GC TO 23 590 15 RFA,,20) CLINK ( I ) RLINt K I ).NK I), J t 1=C) _ __) 600 20 FORMAT ( 155X,I 10,10X,10A4) 610 WRITTF (6,21) C.IINK(III, RI K(I,(NMtLINK(III.J=1.10 620 21 FCRMAT 1'',T15,15,T40,110,T65,10A4) 630 I=I______________ ___ 4__1__ _ 64C GC TO 24 650 23 WRITE (626 _ __ _ 660 26 FORMAT (' C'/'C'/TO,'CORE STCRAGE CCST, S',T35, 670 1'STORAGE CAPACITY',T75.'DESCRIPTION') 680 I=1 690 27 IF( I.GT.NCORE) GO TC __ __ 700 REPD (1520) CCORE(I )),SCCRE(I),(NMCORE(IJItJ=l,10) 710 WRITE (6,21) CCCRE ( I,SZCCRE( I ) (NMC0RE(I, J J=llO) 720 I=1+1 73C GC TC 27 740 29 WRITE (6,30) 750 30 FORMAT'C'/'O'/TIO,'BULK STORAGE COST, $',T35t 760 1'STCRAGE CAPACITY',T75,'OESCRIPTION'/'O') 770 I=1 780 32 IF(I.GT.NBULK! GO TO 35 790 REAC (5.20) CRULK(I),SZBULK(I).(MRBULK(I.J).J=1.10) 800 WRITE (6,21) CBULK( I),SZBULK(l),(NMBULK(I,J),J=l,10) 810 I=I1+1l 820 GO TO 32 830 35 WRITE (6,36 _ 840 36 FORMAT ('O'/'C'/TIO,'REMOTE CCMPUTER COST, $',T35, 850 1I'AVERAGE INSTRUCTION EXECUTICN TIME',T75E'DESCRIPTION') 860 I=1 870 40 IF(II.GT.NCOMP) GC TC 50 880 READ.(5,20) CCOMP(I),TCOMP(II,(NPCOMP(I,J),J=1,10) 890 WRITE (6,21) CCCMP(I) TCOMPLI IbiNMCOMP(J),_jJ=I10) ___ 900 I=I+1 910 GC TO 40 920 50 READC (5,55) (XSHIFT( I),I=1,4}(XMASK(I),I=1,4),ENCeIT 930 55 FORMAT (412/4Z4/Z4)__ q31 REAC (5,100) NT 931.1 100 FORMAT (I2) ____ q31.2 1=1 9a1.3 SC IF(I.GT.NT) GO TO 111 931.5 READ (5,101) NINST(I),PR]B(I),BM(I),BR(I ),(C(I,J),J=1,10) 931.6 101 FCPMAT_ _L 10O. 3,2F10.0,T45, 10A4) 931.7 I=1+1 931.8 GC T 90 _ __ 932 111 CONTINUE 932.5 WRITE (6.110) 933 WRITE (6,120) (NINSTI I) PROCB ( I, eM( I ), BR I ) (CI,J) J=, 10), 933.5 1I=lNT) ------ 934 110 FORMAT ('l',T28,'APPLICATICN CHARACTERISTICS'/////T1O,'TASKS', 935 1' PERFORMED IN RESPCNSE TC USER REQUESTS //T5,_'INSTRUCTIONS', _ __ 936 2T2C,'PROPABILITY',T35,'MAIN CCMP ACCESSES',T60,'REMOTE COMPUTER', 936.5 3' ACCESSES'//) 937 12C FCRMAT ('',T3,I1C,T20,F7.4T4F100,4T65,F10O.O,T80,10A4) 938 WRITE (6,56) __ __ __ 939 56 FCRNAT ('1',T1O,?'ETHER CFARACTERISTICS ARE...'///

Figure B-2 (continued) Input-Output Program 940 NAMVELIST / n 1 NPPPCMSGLTHt RMAXPAGSYSPAG 950 NA~IELIST /NAt-'?/ ARRIVE,URC,UMC,UM C,PAGCSTCPUCST,TRIP 955 NAMELIST/,AM3/ MXITER,EPSI 960 READ (5,NAMI) 970 hRITE (6,hA'llJ 980':'=D (5,NAM2) 990 t. PITE (6t NAM2) 994 iLAE ( r NAN3) 996 _ L (f ~.hAM3) 1000 RtMr (5,45) NICOST 1002 45 _ F.PA1 (12) 1005 REAr (5,46) (RCCST(I),I=1,NCCST) 1010 46 FCR~NAT (15) 1020 C NCN CALL CTHER FUNCTICS TC INITIALIZE THEM 1030 TRASH=SETXI(XMASKXSHIFT) 1040 TRASH=CPTI(RCCST,RESULT,RTIME,CPUCST,ENCBIT) 1050 TRASH=COSTI(CLINK CCOREsCEULK CCOMP,PAGCST,MAXPAC-,SZCORE,SZBULK) 1060 TRASH=RQARNI(RLINK,SZCORE, SZBULKTCOMPARRIVE,URCUMODUMC 1070 1,NPPPCMSGLTHPAXPAGCFUCSTTRIPIMXITER, EPSI 1075 2,NINST,PROB,BM,BR,C,NT,SYSPAG) 1080 INPOD=R 1090 RETURN 1-100 ENTRY CUTMOC(CUMMY) 1110 WRITE (6,60) 1120 60 FCRMAT('I',T30,'RESULTS CF CFTIMIZATION'/''0T5, TN 1130 1'MONTHLY COST, $',T35,'AVERAGE RESPONSE TIME, SECONDS', 1140 2T70.'X'.T75,'ElUIPMENT CCOPLEMENT',./') 0) 1150 I=1 1160 65 IF(I.GT.NCOST) GO TO 8C. 1170. TRASH=SETX(X,R ESULT(I)) 1180 WRITE (69.70) RCOST(I),RTIME I),RESULT( I),(NMLINK(X( 1) J) 1190 1 J=lt10), (NMCORE(X(2),J),J=l1lO ), (NMBULK(X 3),J),J=1l10), 1200 2(NMCCRP(X(4J, ).J=1.10) 1210 70 FORMAT ('O',T10lO 5,T40,FlO.3,T68,Z4,('',T7510A4)q) 1220 I=I+1 1230 GO TO 65 1240 80 OUTMOD=O 1250 RETURN 1260 END END OF FILE

Figure B-3 Typical Input Data $LIST INPUTDATA(100) 100 Of80f 0 8 20 W-_ LD1RAWI. NG 101 00068 0000000300 103 SERIES DATA LINK ___102 ____.Q00098_ _000.0001200 __ _ SW I TCHED__ LINES -_SASYNCHR ONOUS__ 103 00158 0000002000 SWITCHED LINES - SYNCHRONOUS ____04___ 00182....0000002400 _ _ PR I VATE_ VOICE GRADE _LINES _ 105 00650 0000040000 TELPAK A 106 01000Q 000750000 TELPAK B 107 01350 0000125000 TELPAK C._. _1 8 _.......03050 _ _000500 000Q..... TELPAK D 109 00200 4 1 CORE MODULE _ 11]0...____-Q00450 -8 _ ___ 2 CORE_ MODULES_ -.. ___ 111 00650 12 3 CORE MODULES 112 00850,6 4 CORE MODULES 113 01050 20 5 CORE MODULES _ 114. 01250. 24 6 CORE MODULES — __ 115 01450 28 7 CORE MODULES 116 01650 32 8 CORE MODULES 117 00000 0 NO BULK STORAGE 118 00150 32 ONE MODULEt DEC DF32 119 00225 64 DEC DF32, 1 DS32 EXPANDER 120 00300 ______ _ 96 _ O EC_ DF32, 2.S__.S 32__ EXPANDERS_ ___ 121 00350 512 DEC RFO8 +RS08 DISK UNIT 122 99999 _ _ _ _ DUMMY TO PAD OUTPUT _ __ _ _ 123 99999 DUMMY TO PAD OUTPUT 124 99999 DUMMY TO PAD OUTPUT 125 1025 272 PDP-8 + DEC 340 DISPLAY 1. 2_6___ 1112 _ 271 _ POP-8 + 340 DISPLAY + EX. ARITH. 11 _.. 127 1175 164 PDP —9 + DEC 340 DISPLAY,1 __ 28 1250 117 ADAGE AGT 10l,1_ _ 129 3125 112 ADAGE AGT 50 1,1 130 99999 999999999 DUMMY TO PAD OUTPUT 131 99999 9999999999 DUMMY TO PAD OUTPUT ___13_2__99999. — -9999999999 DUMMY TO PAD OUTPUT 133 00030609 XSHIFT __134 __000700C700070007 XMASK 135 OFFF 136 19 137 10.001 0 1 TERMINATE EXECUTION 138 __ 50 -.005 0 1 DELETE CURRENT PICTURE 139 100.005 1 2 GET MENU OF EXISTING PICTURES 140 100.005 _ 2 3 PICK PICTURE FROM MENU 141 100.005 2 3 CREATE NEW PICTURE 142 200.005 1 2 NAME NEW PICTURE 143 100.005 4 6 SAVE CURRENT PICTURE 144 _ ~___ 50. 100 0. _ __OENTER POINT ____ ____ 145 60.369 0 0 DRAW LINE FROM PREVIOUS POINT il....146&_......... 200.050 0 1_ ENTER TEXT ELEMENT.. 147 2000.025 0 1 ENTER ARC OF CIRCLE 148 LQ _. 075... _. 0 ___ 0 DRAW NEW LINE 149 100.050 0 1 DELETE ELEMENT FROM PICTURE 5 _ __110. _ _..030_. 0._ __._ _ 1 TEMPORARILY ERASE ELEMENT 151 500.010 0 1 REDISPLAY ALL TEMP ERASED ELEMENTS __ 152 __ 3000.025 _ 0 1. SCALE PICTURE __ _ 153 200.025 0 1 TRANSLATE PICTURE 154 200.070 0 1 MOVE ELEMENT 155 50.150 0 0 IDENTIFY ELEMENT _156 ___ ~_NAML _.. - - 157 NPPPC=100'

Fiogure B-3 (continued) Typical Input Data 158. MSGLTH=500 159 R=1 160 MA XPAG-20Q _ 161 SYSPAG=3 162 &END 163 &NAM2 164 ARRIVE=.2 165 URD=30. _16___.UMD=i 3.___. __... 167 UMC=.25 168 PAGCST=.19 169 CPUCST= 10000. 170 TRIP=1.C 171 &END 172 AN _AM _ __.. 173 MXITER=100 174 EPSI=.005 175 &END 176 03 176.1 01335 176.2 _Q137 ___ _ 176.3 01440

Figure B-4 Optimization Program $LIST OPTSnURCE 1] FlUNCTION OPT T ( RCST RFS T,RTIF,.CPlOESTNCB IT 20 IMPLICIT INTEGER (A-Z) 30 DIMENSION RC OST(50 ),P ESULI5,RTIME(50),S (11 ),XX(4). X XX4 40 DIMENSION XAPRAY(5C0),XARTI(S5C0) 50 RFAL RTIMEXA RTI,MITIM ___ _ _ _ __ 55 REAL MINF,,CPUCST,XTIME,RUNRCA 1{ I nOCICl f, Q,TFST,FNTRY 70 OPII=C 8f' RFIURN _ 90 C RCOST HAS SYSTEM COSTS IN IT 1 O C _ R EULl HAS SYSTEM CrON EIt l G__ M___ ___ 110 C RTIME HAS SYSTEM RESPONSE TIMES IN IT 120 C XARRAY HAS FEASIBLE SCLUTlCNS IN IT 130 C XARTIM HAS LCWER PCUPC CN RESPCNSE TIME FOR FEASIBLE SOLUTIONS 140 ENTRY OPT(R,CIN EX! __ _ __ __.._ _ __-_._.___._ 150 C R IS NUMBER OF TERMINAL USERS I6O0 C CINDEX IS INCEX INTC COST VECTCR __ __ 170 C INITIALIZE VARIABLES FIRST 180 SSI7F=O 19C SZXARR=O 195 DATA ALLCNE/_FFFFFFFF/ __ __ _ 200 XMIN=ALLCNE E 210 SPSI=o _ _ _ 22C OPT=O 230 C 240 C FIND ALL CCNFIGURATICONS WFICH ARE FEASIBLE (MEET CCST RESTRAINT) 250 1=0 270 5___ F__ XT EP:XSTAR ( X) - _ 280 CX=CCST(X) 290 CXTEMP=CCST ITEMP) 300 C CETERMINE WHEPE CCST CF X LIES 31C I F t CXL:. PC0ST C I EX _LLC TC L ___ _______ _ 32C X=XIEMP 330 _ GO TO 60_ ____ __._ _ __ - 340 C TRANSFER MEFANS CX TOC FICE 350 C IF STILL HERE, CX NOT TOC FIGH. NOW SEE IF CXTEMP=C(X*-l) IS LOW 360 C ENOUGH: IF SO, WILL TRY TO INCLUCE XIEMP AS FEASIBLE POINT IN 370 C XAPRRAY. IF NO-T_ — WILL TRY TC PUT X INTO XARPAY 380 1C IF(CXTEMP.CT.9CrST(CINCEX}) CC TC 20 390 X=XTEMP_ _ __ _400 20 TRASH=SETX(XX,X) 410 SSIZE=SSIZE+I 420 SW=.TRUE. 430 C Sh SAYS X NOT YET PLACE[ INTC XARRAY _ 440 SAVEI=C, 450 C i-EN SAVEI NOT- )_IT PCINTS TP AN AVAILABLE LOCATION IN XARRAY 460 C BEGIN SEAPCHING XARPAY FCPR PLACE TO PUT I 470 I1=1 48C 30 IF(I.CT.SZXARR) CC TO 52 485 DATA EMPTY/ZFnOOCCCC/ 490 IF(XARRPY(I).EQ.FPTY) GO TC 48 500 TRASH=SFTX ( XX tXAPRAVY I ) _ _ _ ___ _ _ _ __ 510 IEST=XX ( 1 ).GE. XxX ( 1).AC.XX ( 2.G. XXX ( 2).ANO.XX ( 3.GE.XXX( 3 520 1.ANC.XX(4).GF.XXX(4) 530 C TEST TRUE IF X SUeSUMES A ENTPY NOW IN XARRAY 540 I- F NT. TEST -_GCC _TQ5.O. _ 550 IF(.NC, T.Si) Cr TO 46

Figure B-4 (continued) Optimization Program 5f0C~~~~ T~~AN5FER J ALPEACY PLAO F0 IN'XARRM _ 570 C HERE PUT X INTn XARRAY(1) 580 XAPRAY(I)=X 590 SN=.FALSE. -G-l.TI.50__ 610 46 XARPRA(I)=EMPTY _62C 1 50- - - _ 630 48 SAVE(=i 64C 50 1=I+I 650 CC Tr 30 660 C CC-CK TO MAKE SURE X COT STOREC 670 52 IF(SAVEI.OT.O.ANG.SW) CC TO. 53 675 C TRANSFER PFANS CAN PUT X tT SAVFI 68LI 0 IF(.NOT.SI6 ooC rC 60 6P2 C TPANSFER VFANS Y 5TOPEC EARLIER 6F4 C STAYINC MEANS PUT X AT ENC CF XARRAY 600 S7XAPP=S7XARR+ I 700 IF(SZXARP.L[.5CC) GC TC 56 710 ~ %RITE (6,55) 720 55 FCPRAT (9 ****TrC MANY POINTS IN XARRAYV) 730 CPT=l 710 RETURN 742 53 XARRtY(SAVEI)=X 744 CO TO 60 750 56 X APRY (SZIARR AR ) =X -_ 760 6C IF(X.OE.EN08lT) GO TC 62 77C X=Y+1 7 E0 00 TO S 750ct)_ _ _~~_~ 62 IFT(X.E.ENQD IT) CTC 64- __ -___ - ____ __-_ _ ___ 800 C X GREATEP THAN ENOBIT PATTERN: SOMETHINGG WRONG HERE -8i0__ — CALL ERRCP _ __ ___ 82C STOP 00011 830 64 WRITE (7,66) SZXARR.(XAPPAY(I).l=l.SZXARR) 840 66 FCRMAT ('C XAPRAY(I) TC XARPAY(',I3,')'//(8(lXZP))) 8 5_0Q ____ M INT IM=100000." __- -- 860 GC TO 70 __8107~ C — __r__ 880 C TRY ALL FEASIRLE POINTS TO FINE REST ONE 89C C __'00 ENPTY CPT2(R) 910 ________ __ SPS 77E =0 920 CPT 2=C 930 C THIS SECOND ENTRY IS USED ONCE XMIN HAS 8FEN OBTAINEDUSING 940 C nPT(,CI.NNEX) 945 IMI=PINX_ 950 MINTIV=RtlNRQA(R,XNIN,F _____ -- SPSIZE=1 - __ - -____ ________ - ____ _.___.___ 970 MINhF=F q 7 C IE 17,63) F IN,=INTI F 980 6P FCRMAT I' AT ENTRY TO CPT2, XMIN=l'Z5,' MINTIM=',F10.4) 9CC 70 1=I 1000 72 IE(IM.T.SZXAPRP) 0 TO 76 10 9_a_ —- - JF(XAPPAY( I) E.E'dPT Y.T CARRAAY ( IIEQ,_XM!I-N ) 00 T C75 7 1020 C EITHER IS OU MY FNTPY CR HAS eEFN EVALLATEC AS XMIN 1030 IF(P.CT.1) O'7 TO 73 1040 XTIMF=PUNRUA (I,YARRAY( I) I) 1050 XARTIM1(1)=XTIV 1060 CC IC 74 __23?O0 723 IF(XAPT I-)f).CF.MINTIH CC T0 c 75 1060 C TRANSFEP REANS NC HOPF CF GE TTINr A NEk MINIMUM HERE

Figure B-4 (continued) Optimization Program 1090 n P Sill= SPRS 17ZF++1 1100 X1IME=RUNRQA(RXARRAY(H),F) 1110 74 TF(XT1VF.CFFMlNT1M) Gf Tr 75 1120 C HAVE FCUND SCMETHING EETTER 1130 ~~~ INT 1 — XLLuE ___ __________________________________ 1135 MIKF=F 1140 M IN NY=AA RAYAML __ 1150 75 1=1+1 160n Gr IC 72 1170 76 RCCST(CIKDEX) =CCST(lIN)+F*CPUCST I70___ RFcUL T(C LhL=~EXffi=MIC ____ - ___R______ -t__llN 1190 RTINE(CINCEX)=MINTlM AL2 CQI~~ LTELL,7818)'JINX.MINTIP7,PCCNI SV P T(CINDEX),R __R 1210 78 FCRMAT ('1**SUCCESSFUL OPTIVIZATICN'f' X=',Z5/'RESPONSE TIME 1220 1FlC.4/'CCST='.15/'P='1 1) 1230 12 A0- - I F(R.E C R C80 _._ __ I ___ _________ ___ 1250 WRITE (6,80) CINDEXSSIZEEKCBIT,SPSIZE 1-2 6 0 80 F 0C R A1 (T OPI M I T IZ AT ION,1 3',,13, 0 oF A POSSIBLE'E1 5, 1270 1' CNF IURRATIN S WERE FEASIBLE',I 4,' WERE EXAMINED WITH RQA ) 1280 WPITE (6,83) 1290 83 FCRMAT (/11/' SUROPTIMUP SYSTEMS ARE'///) 13C0 CC 100 1=1,SZXARR 1310 I(XARRAY(I).E Q.E(PTY) GC IC 100 1320 TR SA=SETXH XX XARRAYL )) 1330 WRITE (6,84) (XX(J),J=l,4),XAPTIM4I) 1340 -84 FCRMAT (' XL=' I' X2=' 12.' X3:=.I2,' X4=' I?2.' T='.F10.5) 1350 100 CONTINUE 1360 82 RETURN _ _ 1370 ENC ENC CF FILE E_

Figure B-5 Program to Evaluate T with RQA $LIST RCARUNSOURCE S C THIS IS INITIALIZATICN ENTRY 6 C 10 FUNCTION RQARN IL INK SZCORE.SZBULK,TCOMPARRIVE.URD,UMDUMC, 20 lNPPPC,MSGLTH,AXPAG, CFUCST,TR I P, MXITER,EPS I,NINST, PROB,BM,BR, 30 2C NT,SYSPAG) 40 C 50 C PRCGRAM TC CETERMINE RESPONSE TIME FOR A CISPLAY SYSTEM 60 C INITIALIZATICN IS AT RCARNI,CALLED FROM INMD0 70 C RGARUN IS THE MAIN ENTRY PCINT,AND IS CALLED BY THE OPTIMIZATION 80 C PROGRAM. 90 C 100 IPFLICIT INTEGER (A-Z) 110 DIMENSION NINST(100),C(100,10) 120 DIMENSION XX(4),S(11),BEGINIll),INCREM(ll) 13n C I MENSION RLINK ( 16) SZCCRE(16 }),SZBULK(16),TCOMP( 16) ARRAY( 16t16) 140 REAL nACESS,UMD,TRIP,EPSI 150 REAL UCLURCPPPFRCPCRC 160 REAL ARRIVE, PN,URD,UMC,PD,CPUCST, PCORE,PL,P2, PEND 170 REAL CENCt,TEMPTIMEF,RUNRCA,ACC 180 REAL PROB(100),BM(1OC),BR (100),TIMEM,TIMER,TRC,TMC,PMC,BMC,BRC 190 - REAL TRANS(8192) V(1400,2) 200 REAL P(7,11),CUEUE(11),TIWE( 11) 210 -REAL F,T1.T2,T3,T4,T5,T6,T7,T8,T9Tl10,T11 220 EQUIVALENCE (S(l),Sl), (S(2),S2), (S(3),S3), (S(4),S4), 230 1 (S(5).S5). (S(6).S6) S(7),S7),(S(8).S8),(S(9).5S9). 240 2 (S(10),S10),(S(ll),S-l ) 250 ECLIVALENCE (TIME(I).Tl). (TI E(2).T2),(TIME(3) T3),(TIME(4,T4I) [3 260 1,(TIME(5),T5), ( TIME6),T6),( TIME(7),T7), ( TIME(8),TB) 270 2,( IME(9).T9 ), (TIE(10),TIO), {(TIME( 11),Tll ) 280 INTEGER*2 TABLE(3,8192) 290 DUMFCT(ABCDEF)=ABCDEF 300 TIMEF(UNIQUE)=(1.0-PN)/( 1.0-PDRC)*(Tl+PCRC*(PRD*T2+( 1.0-PRO)* 310 1(T4+2.0*T5)))+PN*(2.0*T6+2.0*T5+T8/(1.0-PD) 320 2+PC/{ l.O-PD )*T9 ) 330 RUN=O 340 INIT=O 350 RQARNI=O 360 TRASH=STATE I(S,R) 370 TRASH=CELTI(S,T ) 380 TRASH=BIN(R,S,ARRAY) 390 TRASH=FCTSET(ARRAY) 400 RETURN 410 C 415 C THIS IS ENTRY FOR EVALUATION CF RESPONSE TIME. IF R=1, THE 416 C CLOSED FORM SOLUTION FCR RESPCNSE TIME IS USED 417 C IF R>1, RQCA IS USED. IF R=ICC, THE DIVISION OF PROCESSING 418 C IS PRINTED, AND RQA IS NOT USED. 420 C 430 ENTRY RUNRQA(R,X,/F/) 440 TRASH=SETX( XX,X) 450 C FIND BRANCHING PROBABILITIES 451 IF(SYSPAC.LE.SZCORE(XX(2))) GC TO 5 452 RUNRQA=1000000. 0 453 F=1.0 454 RETURN 455 5 CONTINUE 460 PCORE=PACESS(SZCCRE(XX(2 ) )-SYSPAG) __ __ __ _ 470 PI=PACESS(SZCCRE(XX(2) )+S ZUL ( XX ( 3 ) ) -SYSPAG)-PCORE

Figure B-5 (continued) Program to Evaluate T with RQA 480 P2=I.C-PI-PCR E 490 TIME(2)= 1.O/URC 500 TIMF(3)=MSC[ITH/(RL INKXX(1 ))*TRTP) 510 TIME(4)=1.0/UMD 520 IE (5)=TIME(3) 530 TIME(6)=TCOMP(XX(4))*NPPPC*1E-6 540 TIME (7)=T IME (3) 550 TIME(9)=1.0/UMD 560 TTMlF (10=T IF(3) 570 TIME( 11 )=T IM(E( 6 ) 574 NAMELIST LNAM1l/ T2,T3,T4,T6/NAM12/ T9,P1,P2.PCORE 575 NAMELIST /NAM13/ Tl,TE,PN 580 TRC=O.0 590 TMC=O0.0 600 PMC=0.0 61C BMC=O.O _ 620 BRC=0.0 625 NAMELIST /NAMIO/TRCTMC,PRC,BPC/NAM9/PMC 630 CC 37 K=1,NT 64C PEND= 1.0/(1.C+BR(K)) 650 DENOM=1.0-PCORE*( 1.0-PEND) 660 IF(BR(K).GT.O) C-O TC 10 670 PENC=1.0 680 CENCM=1.0 690 10 IF(APBS(P1+P2).LT..000001) GC TO 20 700 PRD=P1/(P1+P2) 710 PCRC=1.O-PED/EFNCM 720 GO TO 30 730 20 CONTINUE 740 PRC=0.5 750 PCRC=OC 760 30 CONTINUE 764 C 765 C DIVISICN CF PROCESSING CALCULATEO HERE 766 C 770 TIMEM=T6+T7+T10+T1ll+INST(K)/(UMC*1000000.)+T9*BP(K) 780 TIMER=(NINST(K)*TCOMP(XX(4 ) )/1000000. + PCRC/(1.O-PDRC)* 790 l(PRC*T2 + (1.0-PRD)*(T3+T4+T5)) 800 IFITITER-TIMEM) 35,35,36 810 C GC TO 35 IF REMCTE COUPUTEP IS FASTER 820 35 TRC=TRC+PRB0 (K)*(NINST(K)*TCCMP(XX(4))) 830 FRC=BRC+PROR (K) *P( K ) 840 IF(R.EQ.100) WRITE (6,40) (C(KI),I=lO10) 850 40 FORMAT (' REMOTE COMPUTER;',10A4) 860 GG TO 37 870 36 TPC=TMC+NINST (K)* (PRCB (K)/UMC) 880 PMC=PMC+PCB (K) 890 EMC=BMC+PRCB(K) ( K ) 900 IF(R.EQ.lO0) kRITE (6,41) (C(K,I),I=l,10).910 41 FCRMAT (' PAIN COMPUTER;',0lA4) 920 37 CONTINUE 960 PN=PPC 965 IF(PN.EQ.O.OOO.CR.PN.EC.1.OCC) GC TC 46 966 C SKIP IF NCRMtLIZATICK NCT NEECED 970 TRC=TRC/( 1.O-PC ) 980 TPC=TPC/PMC 99(0 BpC=BFC/PMC 1000 BRC=BRC/(1.0-PC ) 1005 46 CCNTINLUE __ 1010 PD=BMC/( 1.O+BMC)

Figure B-5 (continued) Program to Evaluate T with RQA 1020 NACESS=BRC 8C_ 1024 1RITE (7,NAM9} 1025 WRITF (7,NA1LC) 1026 IF(R.EQ.1.CQ.P.FC.100) WRITE (6,47) PN,(XX(KK),KK=1,4) 1027 1.___f MAL'_ PN- F LE].9,' X=',41)l 1030 C NCW DC PRCBABILITIES FOR TFE FINAL ANALYSIS 1031 ___IF(R.NLL C1 ~_C T_45__]___ 1032 RCARLN=O 103 R FT!RN 1034 45 CENTINlJE o104 _ PEND=I1.0/( 1.O+NAC SSE _ 1050 DENCM=1.C-PCORE*(1.0-PEN ) 1060 IF(NACESS.CT.0) GO TO 11 1070 PEND=1.O 1080 DENCM=1.0 10'0 11 IF(ABS(P1+P2).LT..0000Q 1) GC TO 21 _110 PRD=P1/iP+P?) __ _ ____ 1110 PCRC=1.O-PEND/DENOM 1120 GO TO 31 __ 1130 21 CCNTINUE 1140 PRD=.,5 1150 PCRC=0.O 1160 31 CONTINUE 1170 l = (TRC*PENC)/( CENM*I COOCCC. ) 1180 8=TMC* (1.0-PD)/1000000.0 1182 IF(PN.EQ.1.C) TL=1.O 1184 IF(PN.EO.O01 T8=1.0 1190 IF(R.GT.I GC TC 50 1J200 RUNRA=T I MEF( OUMMY 1210 F=PN*T8/ PUNRCA+I.O/ARRIVE) 1220 RETURN 1230 C 1240 C 1250 C BECAUSE R>1, MLST SET UP FCR AN RQA RUN 1260 C 1270 C 1280 50 RUN=RUN+ l 1290 NAMELIST /NAM2/TIME/NAM3/PCCRE,P1,P2,DENOM 1300 WRITE (7.NAM2) 1310 WRITE (7,1AM3) 1320 CALL SETUP(TRANSTABLE,V.8192 1400, 1l RUN) 1330 UDL=1.O/TIME(3) 1340 URCPPP=1.0/TIME(6) 1350 WFERE=1 1360 DO 60 1=1.11 1370 BEGIN( I=O 1380 S ( I ) =0 1390 6C INCRE!M(I)=1.1400 70 T=STTIE{ CUMMY) _ __} 1410 GC TO (10C,200),WHERE 1420 100 CONTINUE 1430 C 1440 C SET UP QLtORUPLES 1450 C 1460 STSUM=R-S 1-$2- S 3-S4-S 5-S6 — 7-S8- S9- SlO-S 11 _ 1470 IF(STSUM.EQ.O) GO TO 110 1480 CALL OUAD ARR IVE*STSUMt *,I.C-PN ). T 1 ) 1490 CALL QUAC(ARRIVE*STSUM*PNIT,CELT(0,6 ) 1500 11i CONTINE 1510 IF(S1.EQ.O) GO TO 120

Figure B-5 (continued) Program to Evaluate T with RQA 1520 CALL QUAOIIPR LcCRC)/TIME ( T1DEMLT(1.22)) 1530 CALL QUAD ( 1.0-P0RC)/IIE( 1),TTOELT 1,O)) 1540 CAL OIIAIP((PCRC*I1.o-PRD)I/TIMF(I).T.OELT(I.3)) 1550 120 CCNTINCE 1560 1F(S2.GT.O) CALL CUA (URC.J,OELT(2.1)) 1570 IF(S3.GT.0.AN.SS5.EQ.0) CALL CUAC(UCLTOELT(3,4)) 15po IF(54.GT0) CALL CUAD(UPEO19CELT'(495)) 1590 IF(S5.GT.O) CALL CUAO(U0L,7,CELT(5,1)) 1600 TF S(ST6 0AN.S;11+S II-FO-I CALL QUADIURCPPP.T.DELT16.7 1 1610 IF(57.GT.0.ANO.S3.S5+S1C.EC.0) CALL QUAMCUCLT9DELT(718)) 1620 IF(SP8EQ-O) CC- TO 130 1630 CALL QUtC(PC/TIME(8),TCELT(8,9)) 1640 CALL UA(I (.1C-p0)/TI TE8) T.DELT taI_1) 1650 130 CONTINUE 1660 IFS9O5TI0) CALL CUAC(UMET*TCELT(9.8)) 1670 IF(S1O.GT.0.AN.S55+S3.EQ.C) CALL CUAO(UCL9TELT( 1011)) 1680 1FISI. GT.0,AN.O.S1.EC.0h CALL QUAD(RCPPPT,DELT(11,0)) 1690 GO TO 300 1700 2CC ACC=ACC+V(TLL __ 1710 300 D0 400 1=1,11 1720 S(I)=S(I)+INCREP(I) 1730 IF(Sl+S2.S3*S4+S5.S6.S7+Se+SS+Sl0+S11.LE.R) GO TO 70 1740 IF(S511GT.R) GO TO 410 1750 400 S(I)=0EGIN(I) 1760 410 GO TO 1100092000)tWHERE 1770 1000 CONTINUE 1780 r 1790- C HAVE NOW SET UP CUAMPUPLES, AR READY TO USE RQA 1800 C 1810 CALL CIAG(NTRANS) 1850 CALL SCLVE(NTRANSMXITER.EPSIMXSTATINIT) 1880 INIT=I 1890 00 1010 1=1.11 1900 1010 QUEUE(I)=0.0 1910 C 1920 C NCW COMPUTE MARGINAL DISTRIEUTIONS ANC QUEUE LENGTHS 1930 C 1-940 WHERE=2 1950 USERNO=0 1960 CLENO=1 1970 2010 00 2020 1=1911 1980 8EGIN(I)=0 1990 S(I)=0 2000 2020 INCREMMI)=1 2010 RFGIN(CUENC)=USFRN0 2020 S(CUENC)=USERNC 2030 INCREPM(OUENO)=100 2040 ACC=0.0 2050 GO TO 70 2060 C 2070 C RETURN BACK FERE AFTER COMPUTING A FARGINAL DISTRIBUTION IN ACC 2080 C 2090 2000 P(USERNO+1,CUENC)=ACC 2100 QUEUE(CUENO)=CUEUE(QUENO)+ACCEUSERNO 2110 ACC=O.0' 2120 USERNO=USERNO+l 2130 IF(LSEPNO.LE.R) GO TC 2010 ~ 2140 USERNO=0 2150 QUENC=QUENO+1 2160 IF(CUENO.LE.11) GO TO 2010

Figure B-5 (continued) Program to Evaluate T with RQA 2170 C 2180 C DOCNE. NCI SET UP TIME(I) AS TOTAL THRCUGHPUT TIME 2190 C IN ORDER TO FIND RESPENSE TIME 2200 C 2210 DO 2050 1=1,11. 2215 IF(P(1,I).EQ.1.0) GO TC 2C5C 2220 TIME( I)=(TIME( I)*CUEUE(El)l)/(1.O-P(1 I) ) 2225 2C50 CONTINtE 2230 RUNRQA=TIMEF( UMMY) 2240 F=PN*TS/(RUNRA6+1.0/ARRIVE) 2270 3000 FORMAT (6(2X,F1O.6)/) 2280 RETURN 2290 END ENO OF FILE C0

Figure B-6 Subroutines $LIST STATESOUJRCE+PINSFURCE+FACTSET+OELYSCPCEE+SETXSCURCF+XSTARSOURCE+COSTSCURCE+PEXP/S 4 F 5 FLNCTICN STPTEIIS,/R/) _10 C STAlE LPEN CUE1IL _____- _I_._ _._ ___..... 11 C - INITIALIZEC FRCN CPT 1 5 _' _ FLI C I ITGL_ LEG_ R _1L A-Z 1_ 20 DIMENSION S(l1) 25 STATF T-0 30 RETURN 3__3_1 — _ __ _ _ 3? C MA IN ENTRY HEPE 35 FNTRY STATE(CUMYY) 45 SS=O 50 11=2 55 _10 IF(II.CT._1).C_ TC 4C. _ 60 SSS=O 65 JJ1 _ __ 70 20 IF(JJ.T.SII )) GC T'.C 75 SSS=SSS INCF JJ, I I ) P5 JJ=JJ+1 S O GO T 20 _ _ __ _____ 95 3n CCNTINUE 100 Q S + = ___ _ ____ __ ____ 11C I11=I+1 11 r;G TC 10 120 4C CCNTINLE 125 STATE=+S(I)+SS__ __ ____ 130 FETURN 13 5 E N C ___ ___________ _____ __ 1 C INITIALIZEC FROC CPT 2 C FUNCTICN TC CEMPUTE A TERP IN SUMMATION FOR STATE INDEX 3 C CALCULATTCN. BINCM(I+1,J41) IS J THINGS CRAWN FROM I. __4 C INITItIL _ATICN ENITRY FER _ ___ _ _ 5 FLNCT IN PIN(/R/S,B INCM ) 25 1 PIPL ICI TLINTFGF R (_A-Z_ __ 30 DIMENSION S(11),BINM(16,16) 41 EIN=O 43 RETURN 44 C MAIN ENTRY HERE__ 45 ENTRY PINCOFIJJ,II) 5 C SLM=O 55 INCEX=l 60 10 IF(INEEX.CT.(I — II) GCC TC 20 65 SLt=SUM+S(12-INOEXJ 70 INCEX=-NCfX+l _ __ _ _ _____ __ _X+]_ 75 GC TO 1080 20 CCNTINU'E _ ____ _ _ _ 9P TCP=R-JJ+I -StJM 9^ B I NCCF=B INC(TCPF+1, I I 95 RETURN 100 __ ENC _ __ - -- 1 C FLNCTICN TC CCvPUTE e INCMI L CCFF ICIEN TSPUT THEM 2 0 INT ARr A IP "I1RAY I+1,J+1 5 C 1( FLUNCTION FCTSET (APRAY) 15 IMPLICIT INTEGEP (A-Z) 20 C FUNCTION TO CODPUTE B INMCIAL CfOEFFICIFNTS,PLT T THEM 30 C INTC RQAY( I *1+,J+I

Figure B-6 (continued) Subroutines 4() CI MENS ION ARPAY ( 1 _____ _ ___ __ 41 CIMENSInN FACT(8) 43 DATA FACT/1.2,6.24'.12C,720.5040.403?0/ 60 N=O 70 1 =C _____ _ __ F8' 11 IF(M.FC.N) GC TC 7 c:' ~_ _ _ __ T —____ _ _ _ _________ 110 IF(NM.OT.\-P) GO TC 212 0 Tl= 140 2 P=l 15 0......_ _... _ - __..... 160 3 IF(I.fF.1 ) G TO 4 1 70 _- _ -_ - =P* (F- ) ____ _ _ — ____ _ - 180 1=I+l Ic0 G fI TC 200 4 IF(T.EQ.0) T=1 201 P_4_Y_ N~L, N + LL= F _ACT _... 202 ARRAY M+1 N+1 ) =ARRAY + 1 205 _ ___ ANSWER=_ARP AY (N+ 1Ml ) __ __ _ __ 225 GO TO 8 230 7 ARRAY(N+1,M+1)=1 240 8 M=,+I 250 IFIM.LE.N) GE TC 11 __ __ 260 S N=N+I 270 E IF(_N.LF, 1) -GC TO _ _ 280 FCTSET=0 O 2cQ RPFTCRU CRN 300 ENC 0 5 C 1o C SURPOUTINE TO FIND CHANGE IN STATE INDEX. 15 C PARA ANC PARe SPECIFY WHICH STATE INDEX (S) TO EECREMENT 20 C AND INCREMENT, RESPECTIVELY. IF ZERO, MEANS DO NEITHER. 25 C T IS THE CURRENT VALUE CF TFE LINEAR STATE INDEX 30. C DELTI IS ENTERED ONLY NCCE, TO SET UP S ADDRESSING 35 C 40 FLNCTICN CELTI(S,/T/) 45 IPLICIT INTEGER (A-Z) 50 DIMENSION S(11) 55 DELTI=O 60 RETURN 62 C 63 C MAIN ENTRY 64 C 65 ENTRY DCELT(A,B) 66 PPRA=A 67 PR=:E 70 IF(PARA.EC.O GCTC 30 _ 75 IF(PARA.LE.l11 CC TO 2C o80 10 WRITE (6,15) 85 15 FCRMAT(' ****PARA CR PARB TCC LARGE IN FUNCTICN CELT') 90 DELT=1000CO 95 STOP 00001 105 20 S (PARA)-=S PARA)-1 _ 110 30 IF(PARE.EC.O) GO TC 40 115 I FPAR.T. 11) G TO 1C _ __ _ _ 120 S(PARP)=S (PARR)+1 125 4C TEMP=STATE(TRASP) 130 IF(PARA.NFE.O) S (PARA )=S(PAR)+l 135 F_ IFPAR. NE.0) S(PARe)=SJPARE)-l_ _I 140 DELT=TEMP-T

Figure B-6 (continued) Subroutines ~~__LR TUR _ _ _ _ _______ _ _ _ _ _ _ _ _ ___ __ 190 INC 1 r.'C 5 C X IS TO FE 99CKEN CCWN INTI ITS CCPPONENTS ANC PLACED 1 C 91~ S IFL&AYIICMli' _LL 1A13~_~f~RIf~. hJ_ LS H1~X~EI91EE~AS I TL ___ __?0 C WIIH XVASK _25 C.~____I LN JIF LPL TZAI T.H ~ EO LNTRYLLPL. — _ __-_ ____.~_- _~.-__ -___ 26 FLFNCTIN SFTXI(XVASKXSHIFT) 27 1PFI C1 INTFGFP (A-7) 35 DINIFSIC N XMASK(4),XSHIT(,4), XV(4) _~~L__. ___S Sc~I ___i. __C. -._____ _ SC RETURN S2 __? r _._ __ _ -- _ _ _ _ _ _ _ _ _ _ _ _ _ __ _ _ 53 C PAIN ENTRY HERE r,-5 ENTPY SETX(XVX) 60 1=1 L5___4C_ __1C_ ~__ XVT 11= L AN iI(X~A5I E~,- FPAT I (, X cl- I F T I) ) 1 70 1=1+1 7 75 If I L F.4 C CI) ~C TC I P If ~ -- (L.~ - E - -- - ----- -- - - ---- — ___ --- 87 SETX= X Iq RETURN 95 ENO C 2 C SLBPeIRTINE TC FINC X* ___ CXTC I h_ICN ~l 91 L 4PAXI ___ ___ ___ ___ ___ __ 10 IXPLICIT INTECEP (A-Z) 15 IF IXI 2Q,10.20 20 10 XSTAR=1 2.5__- ___ 1E -C-P K _ - -___ -__ ____ ___ ______ 30 2C XSTAR=?= RIXX-1+Il _39 __CliR___ -- __- _ ___40 END 10 C EROOPAM T1 CALCULATE CCSTS OF HAPOWARE CCNFICURRAT IONS 20 C INITIALIZED AT CCS11 FPCI INI'C 40 C._4.1_ ___ C; __ INITIALI IJATIOKh ENiTRY JIEPE42 C 45 FLUCITON CCSTI(CLINKCCCRFCPULK.CCC'PPPAGCST.I'AXPAG. 46 LSZCOPFS7PLK ) 50 ___ A 10)1 INTCFP L-A-Z) - - _ ___ 60 PFPL PAGCSTT 70 CIVENSICN CLINK(16 ICCCPE(1f )C I6 CCCmP( PO CImFNSIrN YX(4),SZCCPF(lI6),S7ULK(16) 100 1O5TT=0 110 PFTUPN, 11~lt __ C___ _____~ ~ -- _ -. - -___ ____ __ ___~ _ _._ __ 115 C VAIN FNTY HERE 12l ENTRY COSTMY) 130 TRASH=SFRT (X,.) 14n TERF=VAXPA0-S7CORF(XX(2)I-S7IJULK(XX(3)) 150 C LiRP IS UMRE C F I ES STPREO AT NAIN C0N'PUTER 160 T=TYP*kC C ST 170 C T TS COST IN_ COLARS FCR STCPACE ATV MAIN CUPPUTER 1i0 TE M P T LqO CES-CLLIEKK(XX(I)),CCCRE(XI (2 ))+CBULK(XX(3))+CCOMIP(XX(4))+TEMIP 234 ROTLRN 4 C

Figure B-6 (continued) Subroutines 5 ~ ___ rfl ____~Z ~L i I~?I ~htJTC CALCU L AT F r TE A r. E ACC FS-S PP C EB IL IT T 6 C IC FtNCTICN PACESS(INT) 2 r) ARC = -INT/2C7. _ 3 ________~_Fp _ ~I~~SA CSU — EY-PI(-A PC 40 RFTUPN - OFCFI__L ENUC CF FILE

233 Appendix C DATA FROM DISPLAY APPLICATIONS USING IBM 2250 DISPLAY SYSTEM AND MICHIGAN TERMINAL SYSTEM In this appendix data taken on different display applications will be presented. The purpose of this data is to compare the computational requirements of various display (and non-display) applications. The data has been collected for jobs running on the University of Michigan's IBM 360/67, using the Michigan Terminal System [57]. Imbedded within MTS's executive system is an efficient data collection system, the use and operation of which have been documented by T. B. Pinkerton in a University of Michigan CONCOMP Project Memorandum entitled "The MTS Data Collection Facility," dated June 1968. Basically, a data item is recorded (on tape) whenever an event pertaining to specified jobs occurs. Examples of the events are 1) the start of a CPU processing interval, 2) the end of a CPU processing interval, 3) page read in or page read out start and end, 4) acquiring or releasing virtual memory pages, and 5) I/O to terminals, printers, or tapes. A program has been written to analyze the data for any job and produce a series of probability distributions and summary data for the following quantities. 1. User think time. This begins when the computer system is ready to accept new input from the user, and ends

234 when the input is completed with an end-of-line indication. 2. CPU time used during the think period. 3. Computer system response time. This begins at the completion of an input line, and ends when all output has been finished and the computer system is again ready to accept input. 4. Processing interval lengths during response periods. During a processing interval a job has exclusive use of the CPU, except for supervisor functions. 5. Number of processing intervals during a response period. 6. Number of characters in input lines. 7. Number of characters in output lines. When the analysis program was originally conceived and implementect, some of its results were intended to be used as part of the application specification required by the display system model. A serious deficiency in the data collection facility became evident and frustrated this aim. The problem is that input-output information is gathered only at the MTS level. The display service routines for the IBM 2250 display console do not use the MTS I/O routines once a graphics application program has been loaded and started from the console until it has been terminated. Therefore to the data collection facility, running a graphics program appears as one

235 long response time, despite the many user interactions generated with the light pen and function buttons. Because this was the case, gathering much in the way of useful statistics for display applications became impossible. All of use that can be garnished from the display applications statistics is CPU untilization during response periods, and also averaged over think and response periods. While this information will be shown to be useful, it is not what was anticipated. This information is in Table C-1. The first application referred to in the table, Michigan's Own Mathematical System (MOMS) is used to manipulate and plot mathematical functions. All interaction is via the light pen. The second application, text editing, uses the light pen and keyboard to modify text displayed on the console. The 2250 display console could also be used in MTS as a teletype, with a screen instead of printer and paper. Table C -2 shows pertinent data from this mode of operation. The first three applications consist of general program preparation, correction, and debugging. The last application, running the system program *TASKS, gives a listing of jobs active in MTS. The data collection facility was also used to monitor all MTS users for about one hour. The statistics gathered from a random sampling of the monitored teletype terminals are given in Table C-3. Finally, a small amount of data was collected from a remote display terminal using MTS. The system consists of a DEC 339

o v] o p "o [U U) Text Editing 2. 30% 2. 40% 5080 116. 0 5116 Text Editing 2. 80% 3. 30% 2380 66. 0 5038 Table C-1 Data Gathered for IBM 2250 Display Console Used for Graphics Text ditig 2.80% 3.3 (7), 2380 6 Table C - DataGathred or IM 220 DiplayConsle Ued fr Grphic

F3, E CR Q~U) ) Q4~) bt) 0 U) a E bl ha~~~~~~~~~~~~ O NO S Q4) U)( U ) 0~~~~~~~~ a) 0 0 ~~~4co;~ to SQ. a5 Uc a) a)e a)P;PI UC>. U)' ca )0 a) a) bj) r 4a) $) 4a Application u Q~ O o, k o~ Q o E Program Preparation and Testing 1. 10% 4. o% 1280 14.0 42.0 13.70 6518 Program Preparation and Testing 0. 75% 9.8% 2360 17. 7 20. 9 0.98 4780 Program Preparation and Testing 4.55% 12.5% 2650 121.0 22.2 10.00 7634 Executing *TASKS 0. 37% 11. 4% 247 0. 9 47. 0 1.05 5092 Table C-2 Data Gathered for IBM 2250 Display Console Used as a Teletype

238 o Em 0 0 oQ Or V V z m = ~ ~ ~~H Cl m o 0> ~ ~.a 0a 0 oSs: SHE>. oa a) CjR ) a) a;bfl.d Cl 0 MA~ a H 3. 50% 4.8% 1525 53. 0 0. 85 1.84 6103 1. 80% 3. 1% 578 10. 2 25. 00 31.90 3316 1. 20% 2. 4% 297 3. 7 16. 10 15. 8 0 5275 0. 15% 4.4% 4760 7. 0 194. 00 4.6 0 5837 2. 40% 4.5% 512 12. 3 14.60 15.5 0 3998 4.50% 9.8% 779 34. 7 42.60 35.2 0 5782 O. 70% 1. 2% 207 1. 5 12.10 39.8 0 3947 1. 10% 1.5% 83 0. 9 14. O00 28.6 0 4610 2.10% 2. 90o 356 7. 6 25. 30 63.6 0 3462 1.10% 1. 8j 1580 17.5 24. 10 36.7 0 4454 O. 20%o 1. (Oo 3610 7.1 35.90 5.7 0 3438 0. 900/0 3. 3%7 2930 25. 2 44.60 14.1 0 4807 Table C-3 Data Gathered for Random Teletype Users

239 Average Use of CPU by Display Terminal 7. 30% Average Use of CPU by Display Terminal During Response Time 13. 30% Elapsed Time, Seconds 800. 00 CPU Time, Seconds 58. 50 Average Display Terminal "Think Time, " Seconds 2. 50 Average Response Time, Seconds 2. 96 Average Processing Interval Length, Microseconds 6007. 00 Table C-4 Data Gathered for Remote Display Terminal

240 Application Average Use Average User Average Response Class of CPU Think Time Time Teletype 1. 05% 22.8 24. 40 2250 Display Used as Teletype 2. 36% 23. 0 6. 40 2250 Display Used for Graphics 3. 03% * * Remote Display Used for Graphics 7. 30 o * 2. 96 * Not Applicable Table C-5 Comparison of Statistics

241 with 16, 384 words of core storage, connected to the main computer via a 2000 bits per second data link. The application is queueing network analysis, in which the user draws on the display a queueing network, and can then see various probability distributions pertaining to the network. All graphics work is done by the display terminal the main computer merly solves the network for the required results. The data is in Table C-4. Only a very simple queueing network was analyzed. It can be expected that for more complicated and realistic models, the average CPU utilization of 7. 3 % would increase. Note here that "Think Time" does not refer to the user, but to the remote display terminal. Thus an average of 2. 5 seconds after receiving a reply from the main computer, the remote computer sends a new request for service to the main computer. Table C-5 compares and summarizes some of the more important statistics from the four modes of using MTS reported on in Table C-1 through C-4. Several points should be noted. First, using a display in lieu of a teletype reduces response time by a factor of 4, with think time remaining nearly constant. This is a consequence of the fast rate of output attainable with the display console. The input rate (and consequently think time) is unaffected because a keyboard is used in both cases. Second, the faster output rate results in higher CPU use by the terminal, because more computation is done in less time. This means that a display terminal

242 user gets more done in unit time than does a teletype terminal user, and the display user should therefore have a shorter connect time. Third, the 2250 display used for graphics work takes more CPU processing than when it is used as a teletype. Last, the remote display terminal uses more CPU processing than any other application class. However this final point, being based on just one data set, must at best be regarded as tentative. Also, the 360/67 hardware configuration in use when the remote display data was taken differed from the hardware in use when the other data was taken. All this data, then, gives very positive confirmation to the idea that displays in place of teletypes use the CPU more and increase response time, and that graphics-oriented work requires more CPU time than does teletype-oriented work. Figures C-1 through C-9 show some of the probability distributions and the summary data found from the remote display terminal statistics. They are shown here because of their relevance to the work reported here. Superimposed on the original data points (indicated by asterisks) are various distribution functions. In the cases of Figures C-2 through C-7, the distribution is hyper-exponential, with means and standard deviations equal to those of the experimental data. The hyper-exponential distribution is used because it satisfies the requirements for queueing analysis, and can be matched to both the first and second order statistics of the data.

243 In Figure C-8, a negative exponential distribution was used, with mean equal to that of the data. Because the data's standard deviation is less than its mean, the hyper-exponential distribution could not be used. Also, Figure C-9 uses a geometric distribution, which satisfies the requirements for queueing analysis, in that it represents a random branch determining the number of CPU intervals during a response period. The purpose of showing these superimposed distributions is to visually compare some experimental distributions with those which are theoretically required to perform a queueing analysis. It is because of the differences seen between the theoretical and experimental distributions that the work reported in Chapter III was undertaken. It was shown there that the distribution can be much less important than its mean.

MEAN SIGMA SAFPLES 2'51643.C'.4S C2.C 145 KTt4IK TIME ______ 7f43.CE 3523.5 145 TOTAL CPU TIME USED DURING THINK PERIODS 2S62184.0 ICC451eE.C 144 RESPONSE TIME 3___ 367C.6 146e383.C 144 CPU TIMES DURING RESPONSE PERIODS 6CC7.1;SSC.4 S437 CPU INTERVALS CURING RESPCNSE PERIODS 65.5 25 EC 144 NUMPBER CF CPU INTERVALS CURING RESPONSE PERIODS 5.8 I.E 145 INPUT MESSAGE LENGTHS -___ ~ 22.7 144 -fUPUT MESSAGE LENGTHS TIMES ARE IN MICROSECONDS MESSAGE-LENGTHS ARE IN CHARACTERS Figure C-i Summary Data for Remote Display Terminal

1.000 * —---------------- ---- ----- --------- ------- - - - - - - ___ __ I I I 1 __ __. I I I I I I I I 1 1 1 SS~tSS++~ I _ _ _ _ _ _ _ _ _ I _ _ _ _ _ I _ _ _ _ _ I _ _ _ _ _ I _ _ _ _ _ I * 4 * * l * * * * * * * * * * * * * * * * * * * * * * * * * * * 1 _ _ _ _ I I I I I I I I I I: I I I _ _ _ _ _ _ _ _ _ I _ _ _ _ I _ _ _ I _ _ _ _ _ ~ I * * I _ _ _ I ~ ~ _ _ I _ _ _ _ if _ _ _ I _ _ _ _ I I I I ** 1 I I I I I 1- _ _ _ _ 1 I _ _ _ _ _ -. 1I _ _ _ _ L. _ _ L _ _ I _ _ _ _ _ 1 1 1 I ***J I I I I I _ _ _ _ _ _ _ _ _ _ _ _ I _ _ _ _ _ I _ _ _ _ _ _ _ * * * * I _ _ _ _ _ I _ _ _ _ _ I _ _ _ _ I __ I.956 ------------------------------ - --------- 4 —---- _ _ _ _ _ _ _ _ _ I _ _ _ _ _ _ I _ _ _ _ _ 1 _ _ _ _ _ I _ _ _ _ _ I I I _ ~ I I I I I I I I I I I I I I A Ai C I I 41 I I I I I I U ~ ~ ~ __ _ _ _ II __ _ _ _ _ I _ _ _ _ I _ _ _ _ _ _ 1 _ _ _ _ _ I _ _ _ _ _ _ _ I I I -E~~~~~~~~~~~~~~~~~~~~~~~~-~ I I I * * I I I I I I I I _ _ _ I __ _ I~ _ I~ 1 __ _ I _ __I _ __I __ I _I I I I I I I I I 1 1 1.779 ------------- + ---- -— ~ —------ + ---- I _ _ _ _ I _ _ _ _ I _ _ _ I _ _ _ _ I _ _ _ _ I LL I I _ _ _ _ I I V ~ ~ ~ ____ I ____ I _______ I ______I ____ I I I I I ~I I I I I 1 1 1 1 I I I I I I I I P I I I I I I I I I I I 8 I 1~T T I I I I I = 1 1 I 8.868 + —-----— +- ~ —-* ~ * —--------------- ~ -~ * —--------— + ~ —4 —-----— * ~ + 8~ ~~~~~T~N T I I*~ UII = 1/2 SECr rhCu Figure 0-2 Think Time Distribution

I IIIII IIIIIIIIIII AI IIIIIIIIII T.800 -- - - - - - - - -- - - - - - - -------------— ~ —~ ---— ~ 4 —-~ —------------ __ _ _ _ _ _I_ _ _I _ _ _ _ NIII I I I I I I I I L I I *i _ _ II JI IIIII ~~~L __IRSPNS A MP NI ICO ILII-E INIS V I I I I I~igur ICI I3 ~~ I I 1Resp nseime istibut___ion _ ~ ____ ____l __

000 ---------------------------------------- ------------------- I I I I I I I _ I_ _ I I I I I I I I I I I I I - I I I II I i I I _I I I I I 1 1 1 I I I I I I I ~I I I I I I I I 1 1 41 I I I I I I I I I I I I J __ _ _ _ _ I __ _ __ _ I I I I I I I I I I.976 + —------- + —-----— + —---------------------------------------- I I I 44444*4444 I I I ____ ___I I I I I - -1 I I I I _ _ _ _ _ I _ _ _ _ _ _ _ _ _ _ I I I 4*4* I I I I I I I I I I I I I I I I I O t ___ I -_ I _ ___ 11 _ 1 I I __ M 1 1 1 I I I I i I I I U 1 1 I I I _ _ I I I L I 1 144 1 1 I I I /rI A I _ _ _ I _ _ _ _ _ _ _ _ L _ _ _ _ _ I I I1 I T.953 + —------- + —----------------— + —------------------ - --------- ------ I _ _ _ _ _ _ _ I 1 4 4~ I 1 1 1 1 I 1 _ I I I I I I r I i I I44444I I I I I I /(I I _ _ _ _ _ I _ _ _ _ 1 _ _ __L _ _ _ _ _ _ 1 _ _ _ _ 1 _ _ _ _ _ _ _ II _ _ _ I _ _ _ P I 41 I I I I I I i I I _ _ _ _ _ _ _ _ _ I _ _ __ I _ _ _ _ _ I ___ _ _ _ _ d_ _ ~ _ _ _ _ I. _ _ _ _ _ _ 1 I _ _ _ 8 1 1 1 1 I I I I. I I I B.92882 -------------------------- ---- -------------------- _______ 1 0 19 I______ I _______I-C 1.0 4.0 1C 67 I_____9_1 I____10 19 I I I I I I I i I I I __ _ _____ I ___ 1 __ __ I ___ r__ Ir_ li __ 1 1 _~_____~ I~. 1 I_ __ V I I I1 I = II I I I I 1 1I 1 1 I I I/ I I I I 1 _ _ _ _ 1 _ _ _ I _ _ _ I _ _ _ _ I _ _ _ _ _ _ I _ _ _I_ _ _ _ _ _ _ _ _ 1 4 I I I I 1I I I I I -_ _I ~ 4 I I I I 1I I 1 _ I I I I I I I I I I i 1 I _ _ _ _ _ _ _ _ I _ _ _ _ I _ _ _ _ _ _ _ _ I 1 _ _ ___ _ ~i _ _ _ I 44 I 1 I I I I I I I I 1 II K I I I i 1 1 I I I / I I I 1 1.882 ****~4-+- --— + —~~~ -— + —-~ —---— c —-*~+-~~ 0.000 9.900 19.800 29.1CC 39.600 49.500 59.4CC 69.300 79.200 89.100 99.000 RESPONSE TIP'E, UNIT = 1 SECC ______________________ Figure C-4 Response Time Distribution

.903 --------- + —-----— + —-----— + —---------------- -------- I I I I 1I _ _ _ _ _ _ _ _ I _ _ _ I I I I I I I I I I I I I I I I _ _ _ _ 1 _ _ _ _ I _ _ _ _ _ I _ _ _ _ I I I I I II I I I I I: I I I I I I _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ I _ _ _ _ _ I I _I I I I I I I I I I I I I I I I _ _ _ I _ _ _ I _ _ _.1 _ _ _ 1 _ _ I I I I i I I I I I I I I.903 + —------------------------— + —-------- --- - --- ---- - I ** I I I I V___ I __ -I I I I I I I I I I I I, I I I I ___ I -_ _I I C 1* I I I I I I I I I _U~ ~ 1 1 I _ I I __-__ I I ___ B I I I I I I I I I I I U I I I I I _ _ _ 1 _ __ I _ - _ _ _ I _ I 1* 1 ~ 1 1 I I C I I I I.7C8 ----------------— 0 —------------— + —-----— + —------ ---------- I _ _ _ _ _ I I _ _ _ _ _ I _ _ _ _ I I_ _ _ _ _ I _ _ _ _ I _ _ _ _ _ I _ _ _ _ V~~ I~ I I I I I I I I I 0 _ _ _ _ I _ _ _ _ I. _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ B I I I _ _ _ _ _ _ _ _ I _ _ _ _ _ _ __ _ ___ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ 78 -------— + —-----— + —------- - -- --------------- L I I r PLTIE SE CRIG E CKE E CCv N1 =ICMILIECNC T ~ ~ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 1 1 I ~ I r Y i I I I I ~ ~ ~ ~ ~~~~~~~~~~~~~~~I I I I i i I I i ~ ~ ~ ~ ~~~~~~~i I I _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ I I I r I r r I I I I ~ ~ ~ ~ ~~~~~~~~~~I I I _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ I II I I/ I I I ~ ~ ~ ~ ~~~~~~~~~~~~~I I I _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _I I I I _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ I I I I /I I r I I I r ~ ~ ~ ~ ~~~~~~~~~~I I I I /I I I I I I I ~ ~ ~ ~ ~~~~~~~~~~I I I I /I ~ ~~I I I I I I I I I 0.000 9.900 19.80C 29.7CC 39.600 49.500 59.400 69.300'19.200 89.100 99.00CC OPI TIME USED CURING RESPONSE PERIODS, UNIT i C MILLISECONCS Figure C-5 Distribution of Total CPU Time per Response Period

I I I I I, I,I, I. I. I I I I I I I I I I I I I I!.. I I I.......I I I I I I I I I I ****~*** I I I I I 1 I I I I I I I I I! 1 I I I I I I I I I I I I I I.. I I I _I __ I I I I I I I I *~* I I I I I I I! I I I I I I I I 1.982 4..........+.........+.........+.........+........+.........+..........+.........~.........,,. —-— ~ —4 I! i I [ i [ I I _ I__~ I I I T I, I ~ ~ i --— 1....... i~ I [ I! I I I! I,/I 1 c i I I I I i z,, /, ~ __~....... I i ~ I I........._I......., I I./ I l i~ I! I! I I.... i- i -- I/!'i O I I I I I I I I ~P' I [ t I I I I I I I' [ /I I /~ I I I **** I I I I / I I I T oq64,I..........4-..........t...........I,.........+.........+.........+.........,I. —-— ~ —- + —........~.........I. _l I I I I I I I /! I I [i v I I I i ~ ~ F —~ ~ i i i i; i I I i' t/ I t x P I I I I I,, I I /1 I I I R I I I I I I I /I I I I __~_ L__.I I I I! [ _,['! I!_! B I I I I I [ I / I I I I A I I I I I I I /. I I I I a.9~,6 +.........+..........+.........+.........~..........;.........+ —-/ —-'-';.........;....... —'.;-.......; tO'I I. I I I I / I I! ~' I I. I I I I I I I / I I I I __I...............I! [..............I I I _ _I/' I I I!_ 1' I I I I I ~ ]/ I I I I __X! I I I I I fi_ I I I I I i I ~ i i /i I I I I I I I I.! I /I I I.....I I I I I! I I I I I I I I I I I I I I I I I.928 +......... / I +.........+.........+....+ +....-~ —-- + —,'.........+........+........~ i I I I i I / ~ ~ I I l I I I I I I / I I, I I _I I I I I I I / I! I I I _ I I _.! i i I ~ I i I I I i ~ t........~' i l~"i I I z"' I'" ~ ~" I -~ X? —~ —-~ —-' —--— ~, ~ —,, I I I I ~ glO ******** —+.........+..........+.........+'-'.....J+.........+-........+........+ —.....+....~ 0.000 g.qO0 ].q. 80C 2g.TOC 3g.600 4g.500 5g.4CC 69.300 7~.200 89.100 99.000 CPU T__._IFE t~SEC ~UI~II~C- I~E~PGI~SE PERICES! UNI1'" 20C ~ILLISECONOS Figure C-6 Distribution of Total CPU Time per Response Period

1.000 +.. —...-+ —-----— + —-----— + —*************************************** I I I I **************t*********** I I I 1 1 I I ***4** I! I I I I I I I. I I I I I I I I I I*** I I I I I I I I _ _ 1 1 **I I.. I... II I I t* I I I I I I I I I. **. I I / I. I I I I I I I I * I I I I I I I I 1 __ _. [ * I I I I I I I I.863 +........., -__+I I I / IIII. I _ I I I * 1 1 / I I 1 I I I I I I r I I I I I I I I C I I I 1 1 I I I I! M I * I I I I I I I I1 I _. I. * I I I I I I _ I I I I L I I I I I I I I I I I _ I * I I I I I I I I I I T 72 + —------ -----— + —--— + —--------— + —--— + — ---------— +~ —-----— + I I _ I I I I I I I I 9 I 11 I I I I I I I I I I I _ I I I I I I I I I P I I I __ _ __I I l x ~ I | I I I I I I I I I Cf I /_ I I! I I I....I.........I1_ I a I / I I I I I I I I I I _A _. _ ___ I 1 1 I P I *. I I 1 1 1, I I... I I cn L I I II I I I I I I I~ _I I I I I I I I I I I I ___ _1 |.I. I _I I I _. I _...__ I _ _I __._ 8.588 + — * —- -+.........+.............+ —---.....,..............+..... +..... I I I I I. II,I I I, I. I C__ | I I I I I I I I I I I C) I I | I I I I I 1 I I I I ___Y L I I I I I I I I I.451 t + * + —-— ~~~~~~~~~~~-~ —-+ —-_____________ I I I I I I I I I I I I I I I l I I I 1 1 I I I I I I I I I I I I ___ _ i —- - j I I_ I I I I I _ I I I I I I I I I I I I I I I t I I I I I I I I I I I I I I I I I _I _ I IL! II I I I I 1 I I I I I I I I I I I I I I I I I I I I l I I I I.313 *.......+ * + + +........+............~... OoOOO 9.900 lS. eC 2S.7CC 3q.tCC 49.500 59.40C 69.300 79.200 89.1C0 99.000 __ CPU INTERVAL.TI'ES CLRIkG RESPONSE PERICOS! U. NI = 1 FImISECIjh0 Figure C-7 Distribution of CPU Processing Interval Times During Response Periods

1.000,......~......,......~......~.............~......*......,......*...... I.I _I I.. I I I i [ **** I I I I I I I I I I! ___ ~ ~I I __ I I I I I __I__ I 1 I I I I I I I I I I _ _ I I I I I I I I I I I I I I. I. i i I I I II I ***** I I II ~- _~__ I... [ I I I I i I.8C~ +....... — **************-,+..... ~.....+........ ~.......... __ ~_~_ I___ I I I I I I I I I! I I I I I I I I I I I I I I I { c I I [ I i ~_ II I I i I,......... I[Irr _ I I** I._ I [ I I _U_. - I - I- - - -- I -,,"I- I - -~ I- I- I I [ — --- - L I I I I I I I I I A I *** * I. I I I I! I I I.6CO + —---------........ / I —-------— + — 6 II* I // I I I I I I I I...... I —- - -- I -- - I - I ~ - I- --- I I ~ -~~ I V ~ ~ ~ ~~~~~ I I [ I I I I I {3 [_ I~.I~tZ I I I [ I I I I......I_ — a~ ~ ~ ~ ~...i- -— i —--- -~ —---- C-, —--,- I- I, AI I I! I I I I I II L I I I I I I tI I I I "a I I I I I I I I I I I I I I I I! I I I I I d ~ ~ ~ ~ ~ ~~ ~ ~ ~ i I I I I I I I I I II. I I. {![ I I u I /I I I I II I I II I_. __I __ I[_ I__. I __I _ I I I_ I____~~__!~ I_~___~ ~___.20 +.... -...............................................+.... I I I I I I I I I I I I I I I I I I I I I I I I!.! 1 II {I.I I I I I I I I I I I I I t I I I I I I I I I _I I I I I I! I I I I ~- - -- - - -- - - -- - - -- - - -, I- - I I ~ ~ ~ ~ ~~I I [ I I I I I I I ~ ~ ~ ~~~ ~~ I I I I. I I I I C~. 0 **..................................................... C.000 q.900 lC].O 80C q.'CC 3S.60C 4q.500 5q.4cC 6q.300?S.200 89.1C0 c9q.000 NUeERl CF CP~RACTE laS I1~ CUIPUT LINvE Figure C-8 Distribution of Output Line Lengths

1 *ooo + +,- + +.-Y-i —-+. --—,~.-+ -— ~ —-~ — ~ -UI —-+ -~~-H +~-~~ + —r-i~~+. —-~~+ ~ H~rr I 11 __ I I I I I 1 I I -I I I I. I I. 1 I I i I I I I I I. —- II I t_ [ I. I } I I I I t I I I I I I. I I I I 1 I I II I i / I 1 1 1 _ 1 I I I i I / t I I I I I i I - I I I I I II I I I I I I! I 1 I I I I I / I I I I I I I I I I If I I I I I I U I I I I I I I I I I I _ t I 1 1 I I I I I I I I U _ I I I I _ r I I I I I I L T t I I... *...+S.....' —— + AI I I /I... I I I I 1 7.944 + — --— ~ —-------— + —----— _+ —- +___*+____-_ —-+_-___ —— ** ** * ********wt~z**tj** —-+ —--- _l I I I. I I I I I I Y I I I I / I i i ---— I I I I I P I.. I I -....I. I I I I I I I I I / I I I I I I I P I. -I II S***S** _ I I I I I R _ I I t J I I I I I.. I Q1 l I _ l I I _~ I____ I II B I I I I f I I I I I I I _ _____ I I I I I I I I ----— ~~~~~~~~~~~~~~~~~~~~~~~t,. B.917 +.......+.........+..4 —+ —-—. —-' —'.'-' —-—.-' —--- C.71 L I I I I 1 I I I I I I _1 _ I~ $**Sr*~*~)***+*~*+*$+****+* l |I_ I I I I I I T I I! I | I I I I I _I I *** I II I I I _ I I I I I - I I I I I I I I I I It I I I 1 I I l I I I Ii I I I I I I t I I I I I I I I I I 1 I ** I I I I I I I I I I I I II _ I 1 _t I I I I I I I I I I I I I I I I l I I. I I I I I I I I I I I I.... I_ I Il I ~ I. I ~~~~~~~~~I... I I. I I I I I I I I I I -I I I I I I I I I I' 1-.861 *....... —- +.............+........+........ _....+-.... —..++ 0.000 9.900 19.800. 29o7C0 39.600 49.500 59~40~ 69.300 7T<200 89-1100 99.00C NUPBER OF CPU INTERVALS CURING RESPCISE PERIOD! UNIT=5 Figure C-9 Distribution of Number of CPU Intervals per Response Period

UNIVERSITY OF MICHIGAN 3 9015 02826 6099