4,228,496
`[11]
`(19
`United States Patent
`
` (45) Oct, 14, 1980
`Katzman etal.
`
`[73] Assignee:
`
`{54] MULTIPROCESSOR SYSTEM
`[75]
`Inventors:
`James A. Katzman, San Jose; Joel F.
`Bartlett, Palo Alto; Richard M.
`Bixler, Sunnyvale; William H.
`Davidow, Atherton; John A.
`Despotakis, Pleasanton; Peter J.
`Graziano; Michael D. Green, both of
`Los Altos; David A. Greig; Steven J.
`Hayashi, both of Cupertino; David R.
`Mackie, Ben Lomond; Dennis L.
`McEvoy,Scotts Valley; James G,
`Treybig; Steven W. Wierenga, both of
`Sunnyvale, all of Calif.
`Tandem Computers Incorporated,
`Cupertino, Calif.
`[21] Appl. No.: 721,043
`{22] Filed:
`Sep. 7, 1976
`[51] Ent. C13 oer GO6F 15/16; GO6F 15/06
`[52] US. C1.cece teneeneereeneteneneenerectee 364/200
`[58] Field of Search ... 364/200 MS File, 900 MS File
`[56]
`References Cited
`U.S. PATENT DOCUMENTS
`
`ing basis. Use of each busis controlled by a special bus
`controller.
`The multiprocessor system includes an input/output
`system having multi-port device controllers and input-
`/output buses connecting each device controller for
`access by the input/output channels of at least
`two
`different processor modules. Each device controller
`includes logic which insures that only one port is se-
`lected for access at a time.
`The multiprocessor system includes a distributed power
`supply system which insures nonstop operation of the
`remainder of the multiprocessor system in the event of
`a failure of a power supply fora part of the system. The
`distributed power supply system includes a separate
`power supply for each processor module and two sepa-
`rate power supplies for each device controller. Either
`one of the two power supplies provides the entire
`powerfor the device controller in the event the other
`powersupply fails. The distributed power supply sys-
`tem permits any processor module or device controller
`to be powered downsothat on-line maintenance can be
`performed in a power-off condition while the rest of the
`multiprocessor system is on-line and functional.
`The multiprocessor system includes a memory system
`3,480,914
`Schlaeppi o...ueccscsssecseesseee 364/200
`11/1969
`in which the memory of each processor module is di-
`3,820,079
`6/1974 Berghetal.
`..
`364/200
`
`vided into fourlogical address areas—user data, system
`3,828,321
`8/1974 Wilber et al.
`.
`364/200
`data, user code and system code. The memory system
`3,886,524
`5/1975 Appelt .......
`364/200
`includes a map which translates logical addresses to
`
`4,001,790
`1/1977
`Barlow............
`364/200
`physical addresses and which coacts with the multipro-
`4,015,243
`3/1977
`Kurpaneketal.
`364/200
`cessor system to bring pages from secondary memory
`4,032,899
`6/1977
`Jenny etal.......
`364/200
`
`into primary main memory as required to implement a
`
`
`4,034,347 7/1977=Probert |W... ee 364/200
`
`virtual memory system. The map also provides a pro-
`. 364/200 X
`4,034,794
`10/1978 Matsumoto
`tection function. It provides inherent protection among
`
`7/1977 Moreton.......
`weve 364/200
`4,035,777
`users in a multiprogramming environment, isolates pro-
`4,040,028
`8/1977
`Paukeret al.
`. 364/200
`
`gramsfrom data and protects system programs from the
`....
`4,041,472
`8/1977
`Shah et al.
`. 364/900
`actions of user programs. The mapalso providesa refer-
`12/1978 Heart et ab. occ 364/200
`4,130,865
`ence history information for each logical page as an aid
`Primary Examiner—Mark E. Nusbaum
`to efficient memory managementby the operating sys-
`Attorney, Agent, or Firm—Donald C. Feix
`tem.
`[57]
`ABSTRACT
`The multiprocessor system includes in the memory of
`A multiprocessor system the kind in which two or more
`each processor module an error detection and correc-
`separate processor modules are interconnected for par-
`tion system which detectsall single bit and double bit
`allel processing includes two redundant interprocessor
`errors and which corrects all single bit errors in semi-
`buses dedicated exclusively to interprocessor communi-
`conductor memorystorage.
`cation. Any processor module may send information to
`any other processor module by either bus. The buses are
`shared in use by the processor modules on a time-shar-
`
`80 Claims, 42 Drawing Figures
`
`Google Exhibit 1030
`Google Exhibit 1030
`Google v. Valtrus
`Google v. Valtrus
`
`

`

`INTER -
`INTER -
`
`PROCESSOR+5S PROCESSOR+ 55
`CONTROL.
`CONTROL
`
`3B
`
`iA
`
`ey
`
`oct. 14, 1980
`
`Sheet 1 of 29
`
`4,228,496
`
`U,S. Patent
`
`MEMORY
`
`

`

`U.S. Patent
`
`oct. 14, 1980
`
`Sheet 2 of 29
`
`4,228,496
`
`
`
`1090104dSNEScGo
`
`LE“Oo
`
`OD
`in
`
`Is
`
`+ovaangxSP
`TOD0LO’dSNAS6S
`ON!ALTap+ AALShnVIVGSNeAZT
`
`
`NOJID3SNOUS
`
`>P
`
`|
`
`uty}
`
`

`

`U.S. Patent
`
`Oct. 14, 1980
`
`SATSOSY
`SOCSWONMOV
`
`
`ISSNOSYGNSS
`
`YyOSS3DO¥d €Old
`
`4,228,496
`
`ZS
`
`6S
`
`
`
`Sheet 3 of 29
`
`YOLVYSANSAD
`
`A4D01DSNE
`
`125135
`
`JISO7
`
`
`
`
`

`

`U.S. Patent
`
`Oct. 14, 1980
`
`Sheet 4 of 29
`
`4,228,496
`
`X BUS DATA
`16
`KH____—..
`5
`xX BUS PROTOCOL
`
`SELECT
`CLOCK
`
`SELECT
`CLOCK
`
`63
`
`61
`
`63
`
`61
`
`57
`coe
`
`M 16;
`
`_~Y BUS DATA
`Y BUS PROTOCOL
`
`79
`
`4
`
`77
`
`69
`
`
`
`
`
`BUS EMPTY
`STATE LOGIC [COUNT 15
`OUTO
`>
`BUF FER
`a(4!3/2/3
`73 fi] Ovi|ye
`PROCESSOR
`FILL
`
`7
`STATE LOGIC |EOUNT'S
`LOAD RECEIVE
`a RECEIVE
`
`| REGISTER
`
`
`
`wl aS]
`
`o
`
`x 5—0
`
`&
`lu
`=LW GS
`a)
`Wl OLE] o] ¥
`OQ}
`clols)o} a
`cl
`&} Shui
`i
`nt olacwOl
`ee
`4O O) UvC
`
`FIG. 4
`
`

`

`U.S. Patent
`
`Oct. 14, 1980
`
`Sheet 5 of 29
`
`4,228,496
`
`FIG.5
`
`|
`
`Ll
`
`me 5
`16/
`
`SELECT
`
`* BUS PROTOCOL
`7X BUS DATA
`4
`
`
`
`
`
`BUS FILL
`|
`STATE LOGIC
`
`
`
`
`93
`—
`a 4
`RESE
`
`9g
`
`COUNT15
`
`4
`
`INQ
`COUNTER
`
`INQ
`BUFFER
`
`|HY}101
`CLEAR
`
`PROCESSOR
`EMPTY
`STATE LOGIC|COUNTS
`
`oy,
`
`uw
`
`a Oe
`
`l
`
`6l=] 4
`=|
`vi
`&5] x| Sl Sl x
`Wy
`AF
`TO CPU
`
`K7 SND
`
`FIG6
`
`CONTROL
`SE LOGIC
`DIAGRAM .
`
`SNDACK
`SNDREQ
`SND,REQ | SND,ACK |
`|
`|
`!
`
`CNT15
`RCV ACK
`| NTIS
`|
`|
`|
`!
`
`
`
`
`¥
`|
` SNDCMD
`| RCVCMD
`| RCV SEL
`SND SEL
`BUS CONTROLLER
`!
`SND ADR
`
`SNDSEL
`
`RCV ACK
`
`% =INC SND
`
`CLOCK wa 2|oe 95
`
`
`
`B16
`
`©] O
`r|)
`am
`
`SENDER
`
`

`

`U.S. Patent
`
`Oct. 14, 1980
`
`Sheet 6 of 29
`
`4,228,496
`
`¥* =INC CNT
`
`|
`
`DIAGRAM
`
`SS
`MGT a SaR
`see
`RoE eT
`LOGIC
`
`
`
`
`| ! |Reeer aMACHINE
`
`
`BUS EMPTY
`75.
`\
`RESET” SAPEMP
`\
`
`
`*
`\ |
`STATE LOGIC
`“~\\
`/
`‘DIAGRAM
`
`\ oRECT/ees \
`
`\
`
`OUTQ
`
`FIG.8
`
`PROCESSOR
`EMPT*
`PTY
`STATE LOGIC
`DIAGRAM
`
`DIRECT
`RESET
`
`Q
`
`|
`
`/
`
`|
`
`
`
`101
`*
`K/INQ
`:
`
`
`
`7|
`3,
`{DIRECT /
`\
`INC CNT
`7° \RESET |
`BUS FILL
`
`STATE LOGIC
`DIAGRAM
`
`INQ
`
`|
`
`

`

`U.S. Patent
`
`Oct. 14, 1980
`
`Sheet 7 of 29
`
`4,228,496
`
`FIG.9
`LL
`RCV,
`SND!
`SND®,
`IDLE
`PO
`BUS
`li ytdA gh hed
`Nortat
`
`
`ONTROLLER-| \ | | \ |
`
`IPOLL
`STATE
`[OLE
`SNDO?
`SND2’
`SNO14
`IDLE
`
`SND REQ
`
`|
`ROM SNR!
`
`LS
`
`SELECT
`TOSNDR OS ToRCVR©:TO. SNDR
`SND ACK
`\e
`>
`FROM SNDR
`RCV_CMD
`ry
`\ —
`TO RCVR
`RCV ACK
`ft \
`FROM RCVR
`Lo
`SND_CMD
`J
`PATASe{yf
`PACKET
`FROM SNOR’
`‘FROM BC
`‘FROM SNDR
`
`TO SNDR
`
`1 DONE
`
`EMPTY
`FILL
`FULL
`WAIT
`
`IDLE
`O SYNC
`1 SEND
`
`

`

`U.S. Patent
`
`Oct. 14, 1980
`
`Sheet 8 of 29
`
`4,228,496
`
`FIG. 11
`
`_
`J(A) = SIRCV«B
`J(B) = A+CNT 15
`DONE
`K (A) = BCD) + CLOQ
`DLE
`K(B) = As(E-b) + CLOQ
`CLK (A)= CLK (B) = CPU_CLK
`RST(A) = RST(B)=CPU RST
`
`
`03\,
`
`(FULL)
`_
`yC)= Be (AsB)
`J(D)= C
`
`K(C)= D*CNT 15
`“WATT
`K(D)= G+(A+B)
`CLK(C)=CLK(D)= BUS CLK
`RST(C)=RST(D)= A+ B= EMPTY
`
`
`
`
`MICRO PROCESSOR
`
`"3
`
`
`INTERPROCESSOR CONTROL
`
`
`
`
`
`N55
`
`105
`
`105
`
`ne
`
`eene
`
`-_,
`
`:—e
`
`
`[i 3™N
` 1/0 CHANNELmaf" 109
`169
`
`
`
`
`
`CONTROL| MICRO PROGRAM Inara PATH LOGI
`LOGIC [MICRO PROCESSOR
`
`iC
`
`
`
`
`145,147,149,
`151, 153,155,
`157, 159171
`
`119
`
`
`43
`
`161163
`165 167
`
`
`—_R
`
`Re
`
`43
`
`Na
`olTRANSFERADDRESS
`
`
`P |ICH
`ERR
`
`m a,
`Ae)
`
`

`

`U.S. Patent
`
`Oct. 14, 1980
`
`Sheet 9 of 29
`
`4,228,496
`
`S30IARd
`
`SSayddv
`
`ONVAIAWOD
`
`voy2SAILDV
`
`:;VWGOEL
`
`SNIVLSHD
`
`GOL
`
`YOSSS00Ud
`
`-OYD|WSSSYQdV
`
`QW)D
`
`“TSANNVHD
`
`VIVOTSNNVH2DrtsngWIVoELVivaO/!ZAL
`MYOWAWOL€-VG6ELOL
`
`Serv.SSaydav
`
`AYOWAWLZél
`
`31907ot
`
`ALIdVd
`
`WHOINZO
`
`ZElE2l ELOls
`
`
`GE-SelRYOWSAN
`
`sngO7|NaSarINOVIVO
`
`
`
`
`

`

`U.S. Patent
`
`oct. 14, 1980
`
`Sheet 10 of 29
`
`4,228,496
`
`FiIG.14
`
`1/0 BUS LINE DESCRIPTION
`714
`lORST
`»
`RESET
`
`—153,___TBUS _*5%FuncTION
`ss.sa ae
`ras]
`
`eee_159, STI
`ee
`
`LINES HAND -_|FUNCTIONS157 SV
`
`
`163
`PARITY
`b DATA
`DATA
`.
`165,
`EOT
`
`__167,_ PADO.CCLDATA
`__169,
`PADI
`STATUS
`
`+149 HIR
`brequest DEVICE
`151
`RANK
`SPOLL
`REQUESTS
`
`39—_It
`
`161
`
`DATA BUS 6
`
`145
`147
`
`RCI
`LIRQ
`
`FIG. 15
`
`ETO
`
`HANDSHAKE- IL
`
`
`CPU
`HANDSHAKE- 2L
`
`
`
`INITIATION
`# (PARITY ERROR+TIMEOUT)
`ht7
`aw]
`
`|
`(Se)
`(ue)
`
`HANDSHAKE -2L.
`
`(SEE FIG 28 FORA
`TYPICAL HANDSHAKE)
` HANDSHAKE - 21 «
`
`
`(PARITY ERROR+TIMEOUT)
`
`
`HANDSHAKE -IL
`
`|
`|
`
`|
`HANDSHAKE- IL
`
`

`

`U.S. Patent
`
`Oct. 14, 1980
`
`Sheet 11 of 29
`
`4,228,496
`
`RECONNECT &
`——WANQstlanes?L
`FIG. 16 Bea TRANSFER
`SEQUENCE
`|
`
`
`
`
`HANDSHAKE-2L
`RESPONSE* HANDSHAKE-1L
`
`RESPONSE®*
`
`~ STi
`RESPONSE*
`HANDSHAKE-1L
`
`| HANDSHAKE=1L
`HANDSHAKE-1L
`
`
`
`HANDSHAKE-1L
`- EOT
`
`
`
`|
`
`
`RESPONSE
`HANDSHAKE-1L
`
`
`
`{
`
`HANDSHAKE2L9(STHEOT) 9=* ST!
`
` l
`
`*EQOT
`=
`
`HANDSHAKE -iL
`
`FIG.T/
`
`IlO (HII O)
`
`:
`
`HANDSHAKE-1L
`
`
`HANDSHAKE -1L *
`
`
`
`HANDSHAKE* RESPONSE
`
`
`RESPONSE
`HANDSHAKE-1L
`
`RESPONSE,
`
`||
`
`HANDSHAKE-1L*
`
`RESPONSE *
`HANDSHAKE -1L
`
`|
`HANDSHAKE -1L
`
`
`
`
`

`

`U.S. Patent
`
`oct. 14, 1980
`
`Sheet 12 of 29
`
`4,228,496
`
`FIG.18
`
`T-BUS COMMANDS
`[MNEMONIC
`__ FUNCTIONS _
`~__
`N TION NOP
`SELECT OUT
`SEL
`DESELECT ee DSEL
`
`ABI
`
`LOAD PARAMETER
`ABID
`ABORT DATA TRANSFER
`TDATAOUT. UT
`HIGH PRIORITY INTERRUPT POLL
`LOW PRIORITY INTERRUPT POLL
`RECONNECTPOLL
`READ DEVICES ADDRESS & COMMAND
`READ DEVICE STATUS
`READINTERRUPT STATUS.
`READ INTERRUPT CAUSE
`DATA IN
`
`
`/O INTERFACE
`
`D-BUS FORMAT
`15
`T-BUS FUNCTION 0123456 789101112 13 14
`5
`LAC
`[COMMAND [| DEVICE NO]
`UNIT NO.
`ROST
`
`FIG.19
`
`1/0 INTERFACE
`
`OWNERSHIP
`LATCH
`
`
`
`INTERFACE
`181
`COMMON LOGIC
`
`
`
`CONTROL PART
`OF DEVICE
`
`
`
`CONTROL
`
`

`

`U.S. Patent
`
`Oct. 14, 1980
`
`Sheet 13 of 29
`
`4,228,496
`
`79
`
`DECODE|CONTROL
`LOGIC
`LOGIC
`
`DEVICE
`ADDRESS
`COMPARATOR
`
`
`
`| BUS «(0:3)
`UNOWNED STATUS,ONSET
`INTERFACE. COMMON LOGIC
`18
`FIG.21
`16
`SMA
`CiRemt
`OBUS O
`Ossi Sal reidter
`a7
`
`182
`
`O BUS
`
`205
`
`213
`
`| CONTROL O
`(209
`
`= 2|DEVAD 0 CONTROL
`
`
`Os
`|
`215
`
`
`& ©JCONTROL1 MUX
`
`
`@|DEVAD 1 211
`e
`211
`
`215A
`
`TAKE OWNERSHIP O
`207
`TAKE OWNERSHIP1
`207
`
`OWNERSHIP
`LATCH
`
`185
`
`Out
`DATA
`Pou] es { roa
`1 BUS
`16
`2524
`Py
`MUX
`& OO
`DEVAD
`OEE|COMMAND
`
`
`
`ays
`
`=O€|UNIT 4 219 220 201
`
`
`
`

`

`Oct. 14, 1980
`
`Sheet 14 of 29
`
`
`
`NIVLVG“Ot(WV)
`
`Elzcee
`
`€92
`
`TBNNVHD5AXOWSW
`SSeindLNOy¥3545N9Gqinovivag©ySOAS
`
`U.S. Patent
`
`E92
`
`
`
`YALNIOdLAdLNAO
`
`W139
`
`GeeTee\
`
`
`
`YSLNIOd LAdNI
`
`68L
`
`W1D
`
`LOOIN!
`
`Osls
`
`LOZ
`
`4,228,496
`
`()HId3G
`
`Ze€Sre
`
`
`KLaWSNaIJoe)1sanoau
`
`GIOHSSSH1LSSTuISYadine
`
`YSLNNODAONLNODXNWSOIASG
`
`(Q)H1d3d1SandayyeAgSle”ASNNVHO
`
`
`
`

`

`U.S. Patent
`
`Oct. 14, 1980
`
`Sheet 15 of 29
`
`4,228,496
`
` Ot
`
`
`
`SAASAOIARC
`
`STIHMwa44Ne
`
`‘O1F33s
`
`YhTI
`
`
`p—A__,TENNVHDAaQvW
`
`
`YSSNVULyISaNOSY1OSNNODSY
`
`SNOSea=Ag_NaasISSNOSY
`
`
`
`
`
`NOIWWYadOINdLNONVNONOILOVdsasdenEECOl
`
`
`
`ST1I4TSNNVHD
`
`350(10H
`
`(L)Hid3d
`CQOHSSaSHL
`
`AAOGIOH
`
`H1dsad
`
`44450NISQHOM
`
`
`
`(MHIdaGYA45NG
`
`

`

`U.S. Patent
`
`Oct. 14, 1980
`
`Sheet 16 of 29
`
`4,228,496
`
`FIG. 24
`SVO=
`
`PARITY WINDOW
`
`pre ERR REG IF PAR IS
`CLRPAROK,REG
`|
`|
`svope——-F—(ti‘“‘<‘<
`GATES paral
`Toares DATA
`
`TO REG
`
`OUT OF REG
`
`

`

`U.S. Patent
`
`Oct. 14, 1980
`
`Sheet 17 of 29
`
`4,228,496
`
`
`
`YEINIOdINdINOOL
`
`
`
`YHassnaINdLNOBV
`
`TOYLNOD
`d34sng
`
`21901
`
`9¢Old
`
`
`
`
`
`Useze6ez)‘G92
`
`
`
`LOseINdINO|eve
`
`
`
`ASOWSWYSAANGOL
`
`
`YHSLNIOdLAdN!“2
`Ciyez £€?¢)€92
`
`
`
`
`|Sve
`
`
`
`HyALIUM|
`
`avsy
`
`Sle
`
`
`
` (ee)edasandINNor—_OaASCa
`
`O3YHO
`
`
`
`StoreNNAye“4|(L172)XAWOL<p
`
`y¥AdO030
`
`aZve
`
`WD
`
`

`

`U.S. Patent
`
`Oct. 14, 1980
`
`Sheet 18 of 29
`
`4,228,496
`
`SELECT J=(LAC* ADD COMP: PAROKFE)SEL* OWN*ENABLE
`FIG.27
`RANK» PAROK FE*SELBIT)
`K= ENSTOPINs(DATAIN +DATA OUT)+ABTD+ABTI+DSEL +
`
`LAC*ADD COMP « PAROK+ SEL? RANK*SELBIT *PAROK
`
`CLK=SVO TE
`
`FIG. 28
`
`CHANNEL CLOCK ais “TW
`SVO(CHANNEL) eee
`
`SVI (DEVICE
`CONTROLLER)
`
`FIG. 29
`
`SVI
`
`START SVO
`
`DEVICE
`COMB. LOGIC
`0
`S
`CONTROLLER
`
`
`CONTROL PART
`(41)
`OF DEVICE
`CONTROLLER
`
`

`

`U.S. Patent
`
`Oct. 14, 1980
`
`Sheet 19 of 29
`
`4,228,496
`
`en
`FIG. 30
`
`182A 195|BeA bss|1B2A
`
`[reer]|[evory 27 |Erion
`
`
`7 7337 1707.—°337 107 107
`
`
`DEVICE
`CONTROLLER
`
`A 4
`
`[PON]
`Be ti 313
`
`
`
`
`T
`
`3a/7F b\343 [3ar/F 343 |
`TL339
`339/T 307
`307
`311
`£309
`3
`
`339
`
`309
`
`

`

`Oct. 14, 1980
`
`4,228,496
`
`Sheet 20 of 29
`
`U.S. Patent
`
`

`

`U.S. Patent
`
`Oct. 14, 1980
`
`Sheet 21 of 29
`
`4,228,496
`
`FIG.34
`
`MEMORY SYSTEM
`BLOCK DIAGRAM
`
`CPU
`105
`
`1/0 CHANNEL
`109
`
`SECTION|SECTION
`107 8
`
`cH
`Co
`TT
`
`| |
`
`wap
`
`MEMORY
`CONTROL
`
`29
`
`| Locic
`407|o@ (51 SECTION
`
`
`
`
`
`cane|Rat co] | 401
`
`! (
`
`18-BIT
`PHYSICAL
`ADDRESS
`BUS
`
`CONTROL (8 TOTAL)
`16-BIT
`16-BIT
`&
`DATA
`DATA
`FROM ERROR
`TO
`MEMORY MEMORY LINES
`BUS
`BUS
`
`

`

`U.S. Patent
`
`Oct. 14, 1980
`
`Sheet 22 of 29
`
`4,228,496
`
`FIG.35
`407
`
`MAP SECTION BLOCK DIAGRAM
`pmo
`|4e3
`6
`
`427
`
`REF BIT
`
`13,15)
`
`MEMORY
`
`13 (15)
`447
`13(15)
`
`TE
`
`Atl
`
`a
`415
`
`469
`
`Map
`WRITE
`STROBE
`
`
`
`———
`
`
`
`LOGICAL
`8
`
`Aa
`
`\
`453
`}
`LOGIC
`|
`5I
`foot
`MeMe
`|
`PARITY
`=a5)
`GENERATOR
`|
`449
`14(16)
`409)
`MAP
`|
`AGB7AUSER DATAO A
`{417
`A7INUSER CODE2 £}
`8
`|
`|
`4731SYS CODE 3 <|}o4
`[MapPAGE:
`|
`ae)
`fo
`/
`g
`4
`7
`|
`ABSENT
`1406)
`45h,__
`CHECKER L___ 1-.MAP PARITY
`|
`ERROR SIGNAL
`
`or
`
`16
`
`CMA
`
`Oe
`
`|
`|
`|
`|
`|
`|
`|
`|
`|
`forrser|
`WITHIN
`PAGE
`
`18
`
`10
`
`A19
`
`ACT
`
`
`
`|
`|
`[
`
`445 421LESS FR |RY
`
`MAP PARITY ERROR
`
`443
`
`1214)
`
`ci(16)
`
`q
`
`PAGE FAULT
`
`8
`
`
`
`eA
`(20)18-BIT
`PHYSICAL
`MEMORY
`ADDRESS
`
`

`

`U.S. Patent
`
`Oct. 14, 1980
`
`Sheet 23 of 29
`
`4,228,496
`
`FIG.36
`
`LOGICAL MEMORY
`
`LOGICAL
`
`LOGICAL
`PAGE NO.
`
`ADDRESS o
`
`CSeo
`PHYSICAL PAGE NO
`(0-255)
`
`
`
`
`
`P=PARITY BIT FIELD
`
`RST=REF HISTORY FIELD
`
`D=DIRTY BIT
`
`A=ABSENT
`
`

`

`U.S. Patent
`
`Oct. 14, 1980
`
`Sheet 24 of 29
`
`4,228,496
`
`FIG.37
`
`3
`
`Na
`AOR oT Me
`BUS
`
`A775
`
`CONTROL
`RERROR
`LINES
`
`14,
`439)
`
`myn
`_|CONTRCL
`
`MODULE
`COMPARE
`15
`
`PHYSICAL 1&
`ADDRESS
`BUS
`
`421,419
`
`Ace
`SEMICONDUCTOR
`STORAGE ARRAY)
`
`_
`
`16
`
`481
`CHECK BIT’
`GENERATOR
`-
`
`16- BIT DATA
`
`
`
`6
`FIELD
`—16 - DATA BitsrheCHECK
`BITS
`bee
`6-BIT
`WOR
`CHECK
`SBOS
`FIELD
`22-BITS
`EACH
`
`16
`
`479
`;Puy
`489
`
`6
`
`6
`
`
`
`
`
`A483
`1G|CHECK BIT
`437
`COMPARATOR
`
`SYNDROME
`DATA
`
`
`DATA FROM, 16,|_ BIT BUS 6
`
`MEMORY
`COMPLE-
`"101
`
`BUS 437|MENTER
`
`
`493
`1
`
`SINGLE
`ERROR 495
`MULTIPLE
`ERROR
`
`
`SEMICONDUCTOR MEMORY
`MODULE BLOCK DIAGRAM
`
`

`

`U.S. Patent
`
`Oct. 14, 1980
`
`Sheet 25 of 29
`
`4,228,496
`
`Ore
`
`Oo
`
`On
`
`opo -
`
`{JO O-
`
`2zq@oid@606@24087dcdG10®€®Og=D
`
`Gq@®ria@ca@za©lla®OdGS6dG8AOD
`
`
`SNHL
`
`YOLVYSNADL!8MOSHOBEO)|4
`
`am
`
`n|P
`
`RaIAu
`
`y
`
`PB
`
`A
`
`= |
`
`OaamaNOnanl aww o
`
`Li9VIVO
`
`4 L
`
`O O
`
`wt
`O
`
`” U
`
`COLOQO
`
`O
`
`
`
`PPrrereepeerecceocccoree Ccartcepctterecetce
`
`
`EEECULTUREDTCUCTALTUTEUETEUtethtt
`
`
`

`

`U.S. Patent
`
`Oct. 14, 1980
`
`Sheet 26 of 29
`
`4,228,496
`
`Sig®pid®cla®2a®11d©O1G@6G@BASGOD*OSSAHL
`
`
`
`
`
`rerrrete.yeeeerretcerreeecececes gecccen—gececceUT
`
`
`
`trrett._ecrrere seererer _gecrecegenceeectst
`SSvSesesiSOS
`ELECTTULULUCTT ULLULCTELUCUeetICAL,
`
`
`
`
`—prererereerreretee—ereecerreeceeereeeTT|P—peerecereeeereeeee—eeeeecereIrceeeeeeceeeeeeeePp—ereereeee
`
`YOLVYVdWODLIdMOSHO6Old
`
`|:
`
`a
`
`Al|
`
`PY
`
`|
`
`i a
`
`On-amynonaoes
`
`6Ssv11aVvivd
`
`ild-6
`
`AlleeALIavd
`
`118-6
`SOG
`
`(ANOYQNAS)
`
`“
`eer
`
`O-nnTtTw
`
`L1GADSHD
`
`
`
`

`

`U.S. Patent
`
`oct. 14, 1980
`
`Sheet 27 of 29
`
`4,228,496
`
`FIG. AO
`
`SYNDROME. DECODER 48 S1 S3 $5
`
`ERROR
`
`
`514
`
` 510) QpD
`(135 BIT SYNOD)
`
`|
`__
`ODD-EVEN-S50® S1@ S20S53@S84 @S5
`MULTIPLE. ERROR=MULTIPLE+EVEN « Sl « S20 S3« S4e0S
`SINGLE ERROR= ODD» MULTIPLE
`
`_
`
`

`

`U.S. Patent
`
`Oct. 14, 1980
`
`Sheet 28 of 29
`
`4,228,496
`
`FIG 41 BIT COMPLEMENTER
`487
`
`489
`
`493
`
`CORRECTED
`BATA BIT
`
`EROM MEMORY 437
`OMnNOMBWH-O
`
`

`

`U.S
`
`. Patent
`
`Oct. 14
`
`, 1980
`
`Sheet 29 of 29
`
`4
`
`228,496
`
`(
`
`LNODDSIO
`
`NMOGLbAdD
`
`NMOdONdD
`
`Q3YO1S3Y|Add
`
`Q3SYyOLSSYONdD
`
`
`
`SivlSTVILIN!
`
`
`
`

`

`1
`
`MULTIPROCESSOR SYSTEM
`
`4,228,496
`
`BACKGROUNDOF THE INVENTION
`
`This invention relates to a multiprocessor computer
`system in which interconnected processor modules
`provide multiprocessing (parallel processing in separate
`processor modules) and multiprogramming(interleaved
`processing in one processor module).
`This invention relates particularly to a system which
`can support high transaction rates to large on-line data
`bases and in which no single componentfailure can stop
`or contaminate the operation of the system.
`There are many applications which require on-line
`processing of large volumes of data at high transaction
`rates. For example, such processing is required in retail
`applications for automated point of sale, inventory and
`credit transactions and in financialinstitutions for auto-
`mated funds transfer and credit transactions.
`In computing applications of this kind it is important,
`and often critical, that the data processing not be inter-
`rupted. A failure of an on-line computer system can shut
`down a portion of the related business and can cause
`considerable loss of data and money.
`Thus, an on-line system of this kind must provide not
`only sufficient computing power to permit multiple
`computations to be done simultaneously, but it must
`also provide a mode of operation which permits data
`processing to be continued without interruption in the
`event some componentof the system fails.
`The system should operate either in a fail-safe mode
`(in which no loss of throughput occurs as a result of
`failure) or in a fail-soft mode (in which some slowdown
`occurs but full processing capabilities are maintained)in
`the event of a failure.
`Furthermore, the system should also operate in a way
`such that a failure of a single component cannot con-
`taminate the operation ofthe system. The system should
`provide fault-tolerant computing. For fault-tolerant
`computing all errors and failures in the system should
`either be corrected automatically, or if the failure or
`efror cannot be corrected automatically, it should be
`detected, or if it cannot be detected, it should be con-
`tained and should not be permitted to contaminate the
`rest of the system.
`Since a single processor modulecan fail, it is obvious
`that a system which will operate without interruptionin
`an on-line application must have more than one proces-
`sor module.
`Systems which have more than one processor module
`can therefore meet one of the necessary conditions for
`noninterruptible operation. However, the use of more
`than one processor module in a system doesnotbyitself
`provideall the sufficient conditions for maintaining the
`required processing capabilities in the event of compo-
`nent failure, as will become more apparent from the
`description to follow.
`Computing systemsfor on-line, high volume, transac-
`tion oriented, computing applications which must oper-
`ate without interruption therefore require multiproces-
`sors as a starting point. But the use of multiprocessors
`does not guarantee thatall of the sufficient conditions
`will be met,and fulfilling the additional sufficient condi-
`tions for on-line systems of this kind has presented a
`numberof problemsin the prior art.
`Theprior art approach to uninterrupted data process-
`ing has proceeded generally along two lines—either
`adapting two or more large, monolithic, general pur-
`
`5
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`53
`
`60
`
`65
`
`2
`pose computersfor joint operation or interconnecting a
`plurality of minicomputers to provide multiprocessing
`capabilities.
`In the first case, adapting two large monolithic gen-
`eral purpose computers for joint operation, one conven-
`tional prior art approach has been to have the two com-
`puters share a common memory. Now in this type of
`multiprocessing system a failure in the shared memory
`can stop the entire system. Shared memoryalso presents
`a numberof other problems including sequencing ac-
`cesses to the common memory. This system, while
`meeting some of the necessary conditions for uninter-
`ruptible processing, does not meet all of the sufficient
`conditions.
`Furthermore, multiprocessing systems using large
`general purpose computers are quite expensive because
`each computer is constructed as a monolithic unit in
`which all components (including the packaging,
`the
`cooling system, etc.) must be duplicated each time an-
`other processor is added to the system even though
`many of the duplicated components are not required.
`The other prior art approach of using a plurality of
`minicomputers has (in common with the approach of
`using large general purpose computers) suffered from
`the drawback of having to adapt a communicationslink
`between computers that were never originally con-
`structed to provide such a link. The required links were,
`as a result, usually made through the input/output chan-
`nel. Connections through the input/output channel are
`necessarily slower than internal transfer within the pro-
`cessor itself, and such interprocessor links have there-
`fore provided relatively slow interprocessor communi-
`cation.
`the interprocessor connections re-
`Furthermore,
`quired special adapter cards that added substantially to
`the cost of the overall system and that introduced the
`possibility of single component failures which could
`stop the system. Adding dual interprocessor links and
`adapter cards to avoid problemsofcritical single com-
`ponents failures increased the overall system cost even
`more substantially.
`Providing dual links and adapter cards between all
`processors generally became very cumbersome and
`quite complex from the standpoint of operation.
`Another problem ofthe prior art arose out of the way
`in which connections were made to peripheral devices.
`If a numberof peripheral devices are connected to a
`single input/output bus of one processor in a multipro-
`cessor system and that processorfails, then the periph-
`eral devices will be unavailable to the system even
`though the failed processor is linked through an inter-
`processor connection to another processor or proces-
`sors in the system.
`To avoid this problem, the prior art has provided an
`input/output bus switch for interconnecting input/out-
`put busses for continued access to peripheral devices
`when a processorassociated with the peripheral devices
`on a particular input/output bus fails. The bus switches
`have been expensive and also have presented the possi-
`bility of single component failure which could down a
`substantial part of the overall system.
`Providing software for the prior art multiprocessor
`systems has also been a major problem.
`Operating systems software for such multiprocessing
`systems has tended to be nonexistent. Where software
`had been developed for such multiprocessor systems, it
`quite often was restricted to a small numberof proces-
`
`

`

`4,228,496
`
`3
`sors and was not adapted for the inclusion of additional
`processors. In many cases it was necessary either to
`modify the operating system or to put some of the oper-
`ating system functions into the user’s own program—an
`expensive, time-consuming operation.
`Thepriorart lacked a satisfactory standard operating
`system forlinking processors.It also did not provide an
`operating system for automatically accommodating
`additional processors in a multiprocessing system con-
`structed to accommodate the modular addition of pro-
`cessors as increased computering power was required.
`A primary object of the present invention is to con-
`struct a multiprocessor system for on-line, transaction-
`oriented applications which overcomes the problems of
`the priorart.
`A basic objective of the present inventionis to insure
`that nosingle failure can stop the system or significantly
`affect system operation.In this regard, the system ofthe
`present invention is constructed so that thereis no sin-
`gle componentthat attaches to everything in the sys-
`tem, either mechanically or electrically.
`It is a closely related objective of the present inven-
`tion to guarantee that every error that happens can be
`either corrected, detected or prevented from contami-
`nating the system.
`It is another important objective of the present inven-
`tion to provide a system architecture and basic mode of
`operation which free the user from the need to get
`involved with the system hardware and the protocol of
`interprocessor communication. In the present invention
`every major component is modularized so that any
`major component can be removed or replaced without
`stopping the system.
`In addition, the system can be
`expanded in place(either horizontally by the addition of
`standard processor modules or in most cases vertically
`by the addition of peripheral devices) without system
`interruption or modification to hardware or software.
`SUMMARYOF THE INVENTION
`
`The multiprocessor system of the present invention
`comprises multiple, independent processor modules and
`data paths.
`In one specific embodimentof the present invention
`16 separate processor modules are interconnected by an
`interprocessor bus for multiprocessing and multipro-
`gramming. In this specific embodiment each processor
`module supports up to 32 device controllers, and each
`device controller can control up to eight peripheral
`devices.
`independent communication paths and
`Multiple,
`ports are provided between all major componentsof the
`system to insure that it is always possible to communi-
`cate between processor modules and between processor
`modules and peripheral devices over at least two paths
`and also to insure that a single failure will not stop
`system operation.
`These multiple communication paths include multiple
`interprocessor busses interconnecting each of the pro-
`cessor modules, multiports in each device controller,
`and input/output busses connecting each device con-
`troller for access by at least two different processor
`modules.
`Each processor module is a standard module and
`includes as part of the module a central processing unit,
`a main memory,an interprocessor control and an input-
`/output channel.
`
`4
`Each processor module has a pipelined microproces-
`sor operated by microinstructions included as a basic
`instruction set in each processor module.
`The basic instruction set in each processor module
`recognizes the fact that there is an interprocessor com-
`munications link; and when an additional processor
`module is added to the system, the operating system (a
`copy of which resides in each processor module) is
`informed that a new resourceis available for operation
`within the existing operating system withoutthe need to
`modify either the system hardware or software.
`To increase performance and to maintain very high
`transaction rates each processor module includes a sec-
`ond microprocessor which is dedicated to input/output
`operations.
`A dual port access to the main memory by both the
`central processing unit and the input/output channel
`permits direct memory access for the input/output
`transfers to also increase performance.
`Each processor module is physically constructed to
`fit on a minimum numberoflarge printed circuit boards.
`Using only a few boards for each processor module
`conserves space for packaging and minimizes the length
`of the interprocessor bus required to interconnectall of
`the processor modules. A relatively short interproces-
`sor bus minimizes the deterioration of the signals on the
`interprocessor bus and permits high speed of communi-
`cation over the interprocessor bus.
`Each interprocessorbus is a high speed, synchronous
`bus to minimize overheadin interprocessor communica-
`tions and to enable the system to achieve high through-
`put rates.
`A separate bus controller monitors all transmissions
`over the bus. The bus controller includes processor
`select logic for determining the priority of data transfer
`between any two processor modules over the inter-
`processor bus. The bus controller also includes bus
`control state logic for establishing a sender-receiver
`pair of processor modules and a time frame for a trans-
`fer of information over the bus between the sender-
`receiver pair.
`Each bus controller includes a bus clock, and each
`central processing unit of each processor module has its
`own separate clock. There is no master clock system
`subject to a single componentfailure which could stop
`the entire multiprocessor system.
`Each processor module includes, in the interproces-
`sor control of the processor module, a certain amount of
`circuitry on the printed circuit boards which is dedi-
`cated to communications over the interprocessor buses.
`Eachinterprocessor control also includesfast buffers
`(inqueue buffers and an outqueue buffer} which can be
`emptied and filled by the central processing unit with-
`out interfering with the interprocessor bus. This makes
`it possible to sustain a higher data rate on the inter-
`processor bus than could be sustained by any single pair
`of processors. Several data transfers between pairs of
`processor modules can be interleaved on an apparent
`simultaneousbasis.
`Because the interprocessor bus operates asynchro-
`nously with each particular central processing unit,
`each inqueue and outqueue buffer is clocked either by
`the processor module or by the bus controller, but not
`by both simultaneously.
`Each inqueue buffer and outqueue buffer therefore
`has associated withit in the interprocessor control some
`logic that operates in synchronism with the bus clock
`and other logic that operates in synchronism with the
`
`25
`
`35
`
`350
`
`55
`
`60
`
`65
`
`

`

`_ 5
`
`25
`
`§
`central processing unit clock. Logic interlocks qualify
`certain transitions of the logic from onestate to another
`state to prevent loss of data in transfers between the
`asynchronousinterprocessor buses and processor mod-
`ule.
`The logic is also arranged so that in the event a pro-
`cessor module is powering down,there will be no tran-
`sient effect on the interprocessor buses because the
`processor moduleis losing control. The powering down
`of the processor module on an interprocessor bus will
`therefore not disrupt any other interprocessorbusactiv-
`ity.
`The bus controller and interprocessor control of each
`processor module coact to perform all interprocessor
`bus managementin parallel with processing by the cen-
`tral processing units so that there is no waste of process-
`ing power. This bus managementis performed with low
`protocol overhead in thatit takes very few interproces-
`sor bus cycles to establish a bus transfer—what proces-
`sor bus module is sending and what processor moduleis
`receiving—relative to the amountof information actu-
`ally transmitted.
`The processor select logic of the bus controller in-
`cludes an individual select line which extends from the
`processor select logic to each processor module. The
`select lines are used in three ways in the protocol of
`establishing a sender-receiver pair of processor modules
`and a time frame for transfer of information over the
`interprocessor bus between the sender-receiver pair.
`The select lines are used (1) in polling to determine
`which particular processor module wants to send, (2) in
`receiving to inquire of a receiver processor module
`whether the particular processor module wants to re-
`ceive, and (3) in combination with a send command to
`let the sender processor module know the time frame
`for sending.
`The receiver processor moduleis qualified to receive
`incoming data unsolicited by the receiver processor
`module and without a software instruction.
`Blocks of data between a sender-receiver pair of pro-
`cessor modules are transmitted over the interprocessor
`bus in packets. At the end of each packet transfer the
`interprocessor control of a receiver processor module
`logically disconnects from the interprocessor bus to
`permit the bus controlstate logic to establish another
`sequence ofa different sender-receiver pair of processor
`modules and a time frame for making a packet transfer
`between the other pair of sender-receiver processor
`modules. Thus, as noted above, several data block trans-
`fers between different sender-receiver pairs of proces-
`sor modules can therefore be interleaved on theinter-
`processor bus on an apparently simultaneous basis be-
`cause ofthe faster clock rate of the interprocessorbus as
`comparedto the slower memory speedof the processor
`modules.
`Each processor module memory includes a separate
`buffer for each combination of a processor module and
`an interprocessor bus.
`Each memory also includes a bus receive table for
`directing incoming data from an interprocessor busto a
`specified location in a related buffer in the memory of a
`receiver processor module. Each busreceive table pro-
`vides a bus receive table entry which contains the ad-
`dress where the incoming data is to be stored and the
`number of words expected from the sender processor
`module. The bus receive table entry is updated by firm-
`ware in the processor module after the receipt of each
`packet andis effective with the firmware either to pro-
`
`4,228,496
`6
`vide a program interrupt when the entire data block has
`been successfully received or to provide an interrupt to
`the software program currently executing in the proces-
`sor module in response to the detection of an error in
`the course of the transmission ofthe data over the inter-
`processor bus. Producing a program interrupt only at
`the completion of the data block transfer enables the
`transfer of data to be made transparentto the software
`currently executing in the processor module. The inter-
`rupt in response to the detection of an error provides an
`integrity check on the transmission of data.
`The input/output subsystem of the multiprocessor
`system of the present invention is constructed to insure
`that no single processor mo