WIXLIB

THE DESIGN' OF A TIME SHARING COMPUTER SYSTEM USING IVERSON NOTATIONbyRobert E . ReinerA Thesis Submitted to the Faculty of theDEPARTMENT OF ELECTRICAL ENGINEERINGIn Partial Fulfillment of the RequirementsFor the Degree of'.MASTER OF SCIENCEIn the Graduate CollegeTHE UNIVERSITY OF ARIZONA1 9 7 0

STATEMENT BY AUTHORThis thesis has been submitted in partial fulfillment of r e quirements for an advanced degree at The University of Arizona and isdeposited in the University Library to be made available to borrowersunder rules of the Library.Brief quotations from this thesis are allowable without specialp e r m i s s i o n 9 provided that accurate acknowledgment of source is m a d e «Requests for permission for extended quotation from or reproduction ofthis manuscript in whole or in part may be granted by the. head of themajor department or the Dean of the Graduate College when in his jud g ment the proposed use of the material is in the interests of scholar ship.In all other instances, however, permission must be obtainedfrom the author.SIGNEDAPPROVAL BY THESIS DIRECTORThis thesis has been approved on the date shown below:

ACKNOWLEDGMENTSThe author wishes to express his appreciation to Dr. F . J . Hillfor his guidance and encouragement during the preparation of thist he s i s ,I w i s h :to thank Mrs. Freida Long and Mr. Charles Couch fortheir very able assistance in typing the thesis and Mr. Robert Danfordfor his illustrations.I also appreciate the understanding support ofmy wife, Janet, and I want to thank the U. S. Army Security Agency forits financial support of my graduate program.

TABLE OF CONTENTSLIST OF ILLUSTRATIONS*Page. . . . e e . . . . „ . . .LIST OF T A B L E S . .ABSTRACT. . . . . .„ . . » . . » ., . . . . 0. . . . . . . . . . . . . . . . .viiixx.-CHAPTER1INTRODUCTION2IVERSON NOTATION-. . . . . . . . . . . . .1.4. .General Rules . . . .Branching Operators. . . . . . . 1 . .Base Value Operators. . . . . . . . . . . . . . . . . .Binary and Unary Operators. . . . . . . . . . . . . . .Vector Operators. . . . . . . . . . . . . . . . . .46777. . . . . . . . . .Normal VectorsSpecial Vectors. . . . . . . . . . . . . . . . . . . Matrix Operations . . . .Special Iverson Operators. . . .„ . .,710. . . . . . . . . . .» . . . . . . . . . .1011Reduction Operators . . . . . . . . . . . . . . . . .Row by Row and Column by Column OperatorsSelection Operators . . . . . . . . .111112Description of Iverson Use3CONTROL DELAY USAGE4GENERAL SYSTEM DESCRIPTIONSystem Data Flow. . . . . . .System CharacteristicsWord S truct ure. . . . . . .General Iversori Description-. . . . . . . . .13. . . .17. . . . . . . . . .24. . .' . . . . . . . .iv. . . . . . . . . . . . . . . . . . . . . . . . . . * . *. . . . . . . ». * . . -. .26\ 3036 ., 37

VTABLE OF CONTENTS— ContinuedChapterPageRegister StructureInput D a t aDefinitions . . .0Concluding Remarks5. . ., « . .383940.» e ». » o40. . . . . .42.o. .o . . . e. . . .47Communications Supervisor. . . . . .System Supervisor . . . . . . . . . . . . . . . . . .Other Software Routines . . . . . . . . . . . . . . . . .ITU'Commands.Memory Organization 0 . . . . . . . . . . . . . . . . . . .4750515357MULTISHARE M A S T E R COMPUTER. . . . . . . . . . . . . . .58I n t r o d u c t i o n . .System Flowchart.Iverson Description . . . .586166. . . . . . . . . . . . . . . . . . . . . . . .» . . . . . .Teletype Input. . . . . . . . . . . . . .Communications Organization. . . . .S p e c i a l 3 Buffer and Output Service . . .Input Service . . . , . . . . . . . .Information Transfer Service., . . .Register Placement. . . . . .Control Delay8DescriptionMULTISHARE SLAVE COMPUTERCONCLUSIONS. . . . . . . . . . . . . . .666769727577. . . . . . . . . . . . . . .77. . . .82. . . . . . .828493.98Introduction'’ . * . . . . Iverson Description . . .Control Delay Description . .9424446. .7MULTISHARE SOFTWARE. » « . .Data Input Speed. . . . . .Maximizing ComputationProgram S i z e .6« . .*#. .DESIGN CONSIDERATIONS. . . . . . . . .«. . . . . . «. « . . . . . . . . . . . . . . . . . . . . .

viTABLE OF CONTENTS— ContinuedChapterPageAPPENDIX I:DESIGN OF A CONTROL DELAY ELEMENT. . .APPENDIX II:NOTATION CHART .103APPENDIX III:MACHINE LANGUAGE INSTRUCTIONS FOR MULTISHARESYSTEM.106APPENDIX IV:IVERSON DESCRIPTION OF COMPUTER PROCESSORAPPENDIX V:MULTISHARE SYSTEMS COMMANDAPPENDIX VI:MULTISHARE MEMORY STRUCTUREAPPENDIX VII:. . . . . . . . ./ .99. 112.DESIGN OF A ROM TRANSLATION TABLELIST OF REFERENCES.117118,:. . . 119.122

LIST OF ILLUSTRATIONSFigurePage2-1Machine Registers for. Simple.Computer2-2Data Flow for Simple Computer S y s t e m .3-1Control Delay3-2. . . . . . . . . . . . . .Timing F l i p - F l o p14*. .„. . .1518183-3Branching I n s t r u c t i o n .193-4Control Sequence Flow Chart203-5Data Flow in a Computer System Using Control DelayElements. 224-1Information Diagram for M u l t i s h a r e .254-2Flowchart forModified Multishare System284-3Basic MachineWord for Multishare4-4Register Configuration5-1Parameters of Storage Devices'.6-1ITU Command Matrices7-1Register Configuration for the Multishare MasterComputer. . . . . . . . .,. , . 6 . « o» . . . » » for !TM o d e l !! Computer. . e oSystem«38. . .39. . . . . . . . . . . . . . . . . . . . . . .Information Flowchart for Multishare Master Computer7-3Master Control Diagram //I . . . . . . . . . . . . . . .4554. . .7-26062.79. . . . . . .807-4Master Control DelayDiagram #2. . . . .7-5Master Control DelayDiagram #3. . . . . . . .8-1. . .81Register Configuration for the Multishare SlaveComputer. . . . ». . . . . . . . . . . . . .83vii

viiiLIST OF ILLUSTRATIONS— ContinuedFigure8-2PageFlowchart for Multishare Slave Computer.„858-3Control. Delay Diagram(Slave #1)948-4Control Delay Diagram(Slave #2)958-5Control Delay Diagram(Slave #3)9-6Control Delay Diagram (Slave #4)1-1Timing Chart for Control Delay Circuit1-2Primitive Flow T a b l e .1-3Implication Table. .1-4Maximum Compatible.«. . «.» » , .«1-5Minimal Flow Table. . . . . . . . . . .1-6Transition Distance Cube and1-7Excitation-Output Table1-8. . . . . .Operations InstructionsIII-210 InstructionsIII-3System MicroinstructionsVII-1o , . . . . . .». . . . . . . . . . o96. .9799. . . . .Transition TableControl Delay C i r c u i t .III-l.99. . . . . 100. 1001. .101„ . « « . . .101. » . .» . «». .«. . . * . » » '» « «102102. e . .« » « » » 107. . . . . . . . . . . . . . 108110Truth Table for Gray Code to Binary CodeTranslationo.‘ VII-2R O M for Gray Code-Binary Code TranslationVII-3Exclusive Or Function. . »0 „. »» „ * « « « « 120. .120» . . , 121

LIST OF TABLESTable . . . .PageIUnary Operators.IIBinary O p e r a t o r s . * . .8. . « » , . . « « o . .8

ABSTRACTThe Multishare time sharing system uses two separate computers,called the master computer and the slave computer, to accept and processdata from each of forty input terminals The master computer is respondsible for systems communications with the input terminal and for theassignment of programs to the operating part (the slave computer) of thesystem.The master periodically checks each input terminal and, if in put is on line, accepts and decodes the available information.Thisinformation is either stored in the file or used as a command thatcontrols system operation.Inputs from each of the input terminals arehandled separately on a time sharing basis to facilitate maximum accessfor each user.Operation requests from each input terminal are assignedto a queue table and are transmitted.to the slave computer following apriority algorithm.The slave computer accepts the assigned programsand is responsible for their compilation and operation.The slave isthe part of the system that effects the input terminal requests; it, astasked by the priority algorithm, gives each terminal user his requiredinformation on a timely basis.

CHAPTER 1INTRODUCTIONThis thesis is a hardware description, using Iverson Notation,of a sample time sharing computer system.The system,called M u l t i s h a r e ,is modeled after software features of currently available time sharingmachines.An attempt will not be made to fully describe Multishare asthis would require the design of a great deal of software such as execu tive programs,compilers,spare time programs, e t c * ; but rather the focusof the paper will be on a data transfer description of the system*Thenecessary software will be briefly mentioned;in order to give continuityto the paper but the main topic of the paper is data transfer*The Iver son Notation language, which will be reviewed in Chapter 2, has beenchosen as the tool for the paper because it enables a knowledgeable read er to easily follow data t r a n s f er.It is thought that the use of this .language will give the reader a clear picture of the system concepts, andwill help h i m to gain a concise understanding of the data transfer inMultishare *Computer time sharing can be thought of as the application ofmass distribution to data processing.It allows real time computerpower to be distributed to a large number of users and it gives eachuser the feeling that he is a very preferred customer*The real timepower provided by time sharing is a type of return to the beginning ofthe computer age,for then it was common to have all operations done on

a. real time ba s i s .The programmer used the machine personally and indoing so ? tied up the computional capability of the equipment, until hewas-finished.As larger machines evolved, it became more costly to tieup a machine and the inherent waste became excessive.This led direct ly to a closed shop, batch-processing-oriented method of operation.This method proved very efficient and greatly increased the amount ofinformation that could be processed in a day, thus becoming a boon tocomputer operations,But the system had one major difficulty; it forcedthe users to queue for use of the machine and made it i m p o s s i b l e , u n d e rnormal circumstances, to obtain results of more than two or three runsa day.This caused certain programmers a great deal of inconvenience informing and using their programs and wasted a great deal of time.Apartial answer to this problem was found with the advent of the manysmall computers becoming available; but this w a s n ’t the complete answeras these computers were limited in capacity and software.The answerto this problem was, of c o u r s e , found in the techniques of time s h a r i n g .In this manner an individual operator could have real time contact withthe machine b u t , at the same t i m e , he did not unnecessarily tie u p .thecomputational abilities of the equipment.Time sharing h ad its b e ginnings with small systems such as JOSS developed by RAND Corporation.These small systems formed the base for larger systems, examples ofwhich are CTSS commissioned b y MIT, Project MAC at MIT, and systemsdeveloped by Systems Developement Corporation and Dartmouth U n i v e r s i t y .Currently there are a large number of sophisticated time sharing sys tems on the market such as the IBM 360/65 , the RCA Spectra 70/46 , theSDS Sigma 5, and the Systems Engineering Laboratory Systems 86.

3More detailed information on time sharing systems can be found in G l aser51964; Hassitt,1967; General Electric,1966; Yates, 1962; and Ziegler,1967.The paper will begin with a brief functional description of theIverson Notation language.It will subsequently explain a diagramaticflow notation which will further illustrate the data flow concepts ofMultishare.After the background material is described, a general intro ductory hardware description of the system will be presented.This willbe followed by a discussion of system design concepts and an outline ofMultishare s o f t w a r e „The paper will.then describe in detail the h a r d ware operations of the Multishare master computer, and will concludewith a discussion of the data flow in the Multishare slave computer.