r ~
`~~
`~
`~
`~
`,
`~
`
`ri
`
`Conte ~s d'z Desi n
`
`~~.
`
`Glenn A. Gibson
`
`Facebook's Exhibit No. 1019
`Page 1
`
`

`

`Computer
`Systems
`
`Facebook's Exhibit No. 1019
`Page 2
`
`

`

`COMPUTER
`Concepts
`
`Electrical Engineering Department
`The University of Texas at El Paso
`
`PRENTICE
`
`Facebook's Exhibit No. 1019
`Page 3
`
`

`

`Library of Congress Cataloging-in-Publication Dula
`Gibson, Glenn A.
`Computer systems :concepts and design /Glenn A. Gibson.
`cm.
`p.
`Includes bibliographical references.
`ISBN 0-13-172958-6
`1. System design. 2. Computers—Design and construction.
`3. Computer software—Development. I. Title.
`QA76.9.S88G43 1991
`004.2'1—dc20
`
`89-77266
`CIP
`
`EditoriaUproduction supervision: bookworks
`Cover design: Bruce Kenselaar
`Manufacturing buyer: Lori Bulwin
`
`D 1991 by Prentice-Hall, Inc.
`A Division of Simon &Schuster
`Englewood Cliffs, New Jersey 07632
`
`All rights reserved. No part of this book may be
`reproduced, in any form or by any means,
`without permission in writing from the publisher.
`
`Printed in the United States of America
`10 9 8 7 6 5 4 3 2 1
`
`ISBN 0-1,~-1,7958- 6
`
`Prentice-Ha11 International (UK) Limited, London
`Prentice-Hall of Australia Pty. Limited, Sydney
`Prentice-Hall Canada Inc., Toronto
`Prentice-Hall Hispanoamericana, S.A., Mexico
`Prentice-Hall of India Private Limited, New Delhi
`Prentice-Hall of Japan, Inc., Tokyo
`Simon &Schuster Asia Pte. Ltd., Singapore
`Editors Prentice-Hall do Brasil, Ltda., Rio de Janeiro
`
`Facebook's Exhibit No. 1019
`Page 4
`
`

`

`~.
`';
`~s~:
`
`To my granddaughter, ,
`Ashley Elizabeth
`
`Facebook's Exhibit No. 1019
`Page 5
`
`

`

`Contents
`
`Preface xiii
`Acknowledgments xvii
`1 Introduction 1
`1-1 Computers and Their Applications 2
`1-1-1 Hardware 5
`1-1-2 Software 10
`1-2 About This Book 12
`2 Data Representations 16
`2-1 Text Data Types 18
`2-2 Numeric Data Types 20
`2-2-1 Non-negative Integers 21
`2-2-2 Signed Integers 24
`2-2-3 Range and Scaling 34
`2-2-4 Real Numbers 36
`2-2-5 Expression Evaluation 43
`2-3 Design Remarks 47
`References 47
`Exercises 48
`3 Computer Circuits 51
`3-1 Electrical Properties 52
`3-1-1 Circuit Effects on Timing 52
`3-1-2 Power Considerations 54
`
`vii
`
`Facebook's Exhibit No. 1019
`Page 6
`
`

`

`A
`
`f '
`
`3-2 Combinational Logic Implementations 57
`3-3 Important Combinational Circuits 64
`3-3-1 Multiplexers and Demultiplexers 64
`3-3-2 Comparators 66
`3-3-3 Adders and Subtractors 69
`3-3-4 Multipliers 74
`3-3-5 Parity Generation and Detection 75
`3-4 Important Sequential Circuits 77
`3-4-1 Counters and Frequency Dividers 77
`3-4-2 Registers 80
`3-4-3 Serial Adders and Subtracters 82
`3-4-4 Multipliers and Dividers 85
`3-5 Link Connections 87
`3-6 Integrated Circuits and Technologies 91
`3-7 Design Remarks 92
`References 94
`Exercises 95
`
`4 Fundamental Computer Operations 98
`4-1 Machine Language Instructions 102
`Instruction Types and Formats 103
`4-1-1
`4-1-2 Operation Codes 105
`4-1-3 Operand Fields and Addressing Modes 107
`Instruction and Instruction Set Design 112
`4-1-4
`4-1-5 Condition Flags and the PSW 117
`4-2 Assembler Language Instructions 119
`4-2-1 Transfer Instructions 122
`4-2-2 Arithmetic Instructions 124
`4-2-3 Branch Instructions 129
`4-2-4 Looping 132
`4-2-5 Logical Instructions 136
`4-2-6 Shift and Rotate Instructions 138
`4-2-7 PSW Instructions 141
`4-3 Stacks 142
`4-4 Procedures 145
`4-4-1 Calls and Returns 146
`4-4-2 Parameter Passing and Side Effects 149
`4-5 Macros 157
`Instruction Execution Time 159
`4-6
`4-7 Design Remarks 161
`References 162
`Exercises 163
`
`5 Program Creation 169
`5-1 Assemblers 170
`
`viii
`
`Contents
`
`~i
`
`Facebook's Exhibit No. 1019
`Page 7
`
`

`

`5-1-1 Data-related Directives 171
`5-1-2 The Assembly Process 177
`5-2 Compilers 184
`5-3 Linking and Address Adjustment 191
`5-4 Loading and Address Adjustment 195
`5-5 Design Remarks 196
`References 197
`Exercises 198
`
`6 Input/output Programming 200
`6-1 Programmed UO 202
`6-2 Interrupt UO 207
`6-2-1 The Interrupt Process 208
`6-2-2
`Interrupt Masking 210
`Interrupt Example 211
`6-2-3
`6-2-4
`Interrupt Management 214
`6-3 Direct Memory Access 220
`6-3-1 Programming Block Transfers 221
`6-3-2 Double and Triple Buffering 224
`6-3-3 Multichannel Controllers 224
`6-4 UO Elements 227
`6-4-1 Keyboards and Monitors 227
`6-4-2 Printers and Plotters 231
`6-4-3 Timer/Event Counters 232
`6-4-4 A/D and D/A Converters 234
`6-5 Design Remarks 236
`References 239
`Exercises 239
`
`7 Processing Elements 243
`7-1 Macroinstruction Execution 246
`7-2
`Internal Bus Transfers 249
`7-3 Detailed Internal Architecture Example 252
`7-3-1 Macroinstruction Execution 253
`7-3-2 ALU and PSW Design 257
`7-3-3 BCL Logic 261
`7-3-4 Control Bus 261
`7-4 Microcontrol 265
`7-4-1 Hardwired Control 265
`7-4-2 Microprogrammed Control 271
`7-5 Reduced Instruction Set Computers 283
`7-6 Packaging 285
`7-7 Other Design Remarks 288
`References 291
`Exercises 291
`
`Contents
`
`ix
`
`Facebook's Exhibit No. 1019
`Page 8
`
`

`

`8 Links and Interfaces 294
`8-1 System Buses 296
`S-2 Interfaces 300
`8-2-1 Bus Control Logic 301
`8-2-2 Link to Link Interfaces 310
`8-3 Data Links 320
`8-3-1 Signal Formats 322
`8-3-2 Local Data Links 326
`8-3-3 Data Link Standards 327
`8-3-4 Packets 330
`8-4 Summary 332
`References 333
`Exercises 334
`
`9 Memory Hierarchy 337
`9-1 Mass Storage 339
`9-1-1 Magnetic Tape Units 340
`9-1-2 Movable Head Disk and Diskette Units 345
`9-1-3 Fixed Head Disks and Drums 350
`9-1-4 Magnetic Bubble Memory 351
`9-2 Main Memory 352
`9-2-1 Static RAM 358
`9-2-2 Dynamic RAM 359
`9-2-3 Read Only Memory 361
`9-2-4 Memory IC Timing 363
`9-2-5 Memory Module Interfacing 366
`9-3 Multiple-port Memory 369
`9-4 Cache Memory 371
`9-5 Hierarchy Design 380
`References 383
`Exercises 384
`
`10 Memory Management 388
`10-1 Mass Storage Management 389
`10-2 Main Memory Management 399
`10-3 Memory Management Hardware and Virtual Memory 405
`10-3-1 Paging 407
`10-3-2 Segmentation 413
`10-3-3 Paging Versus Segmentation 416
`10-3-4 Memory Management Remarks 417
`References 419
`Exercises 419
`
`11 Operating Systems 422
`11-1 Uniprogramming Systems 423
`11-1-1 Memory and File Management 426
`
`X
`
`Contents
`
`~!
`
`Facebook's Exhibit No. 1019
`Page 9
`
`

`

`11-1-2 Input/Output 427
`11-1-3 Operating System Services 429
`l 1-1-4 Systems Programs 429
`11-1-5 Overlapping I/O and Processing 430
`11-2 Multiprogramming Systems 431
`11-3 Organization of a Multiprogramming System 435
`11-3-1 Process Scheduling 435
`11-3-2 Memory Management and Process Loading
`11-3-3 I/O Handling 440
`11-4 Sharing Resources 443
`11-5 Areas for Further Study 447
`References 449
`Exercises 450
`
`438
`
`12 Parallel Processing 452
`12-1 Multiprocessing 454
`12-1-1 Bus Topologies 456
`12-1-2 Non-bus Topologies 461
`12-1-3 Synchronization and Resource Sharing 464
`12-2 Pipelining 469
`12-2-1 Pipeline Performance 472
`12-2-2 Pipeline Design 476
`12-3 Vector and Matrix Processing 482
`12-3-1 Vector Addition 482
`12-3-2 Summing Elements of a Vector 483
`12-3-3 Inner Products 484
`12-3-4 Matrix Operations 486
`12-4 High Performance Computing Summary 487
`References 489
`Exercises 490
`
`Appendix A Number Systems and Conversions 494
`Exercises 498
`
`Appendix B Logic Level Design 499
`B-1 Elementary Logic Gates 500
`B-2 Combinational Logic Design 508
`B-3 Elementary Sequential Circuits 522
`B-3-1 Clocks 524
`B-3-2 Monostable Multivibrators 524
`B-3-3 Flip-flops 526
`References 532
`Exercises 532
`
`Appendix C X16 Summary 537
`
`Index 549
`
`Contents
`
`f .
`
`'~
`=j
`
`xi
`
`Facebook's Exhibit No. 1019
`Page 10
`
`

`

`MOVH
`MOVH
`MOVH
`AGAIN MOVH
`ADDA
`ADDH
`ADDH
`BRNE
`
`~
`
`#100,R5
`#X,RO
`~Y~R1
`[RO],[R1]
`$2,R0
`~2,R1
`#-1,R5
`AGAIN
`
`l
`}
`
`>
`1
`}
`~
`>
`
`Initialization
`
`Processing
`
`Modification
`
`Testing and branching
`
`Figure 4-30 Transfer of an array using a loop.
`
`this loop, because its repetition depends only on whether or not a single quantity
`has reached 0, testing and branching can be done with one instruction.
`Because loops are so important to the operation of a computer, it is worth-
`while to examine ways of making their implementation more efficient. It is most
`important to improve the efficiency within the loop (as opposed to the initialization
`component) because it may be repeated several times. This improvement is made
`by reducing the number of instructions in the modification, testing, and branching
`components of the loop. In the example in Fig. 4-30 four instructions were included
`in these components—two were for updating the addresses, one for decrementing
`the count, and one for testing .and branching.
`By far, the most prevalent use of loops is to operate on arrays in an orderly
`manner. This operation involves incrementing or decrementing the array indices
`by a fixed amount. One way of eliminating the extra instructions for modifying
`tl~e indices would be to enhance the register indirect addressing mode so that the
`registers used for addressing are automatically incremented or decremented by
`the appropriate amount whenever they are accessed. Addressing modes that are
`derived from register indirect addressing in this way are called the autoincrement
`and autodecrement addressing modes.
`Let us now extend the X16 to include autoincrement and autodecrement
`addressing modes by using two of the unused addressing mode bit combinations.
`The combinations 111 and 101 will be used for autodecrementing and autoincre-
`menting, respectively. The assembler language notation for indicating these modes
`will be — [Register] for autodecrementing and [Register] + for autoincrementing,
`e.g.,
`
`The size of the increment or decrement will be one for byte operations and two
`for halfword operations. For autodecrementing the register is decremented first
`and then provides the address; but for autoincrementing, the register first provides
`the address. Therefore,
`
`and
`
`134
`
`MOV
`
`[R1]+,RO
`
`MOV
`
`R0, -[R1]
`
`Fundamental Computer Operations
`
`Chap. 4
`
`Facebook's Exhibit No. 1019
`Page 11
`
`