CA1185670A - Multiprocessor system - Google Patents

Abstract

Abstract of the Disclosure A multiprocessor system the kind in which two or more separate processor modules are interconnected for parallel processing includes two redundant interprocessor buses dedicated exclusively to interprocessor communication. 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-sharing basis. Use of each bus is 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 selected for access at a time. The multi-processor system includes a distributed power supply system which insures uninterrupted operation of the remainder of the multl-processor system in the event of a failure of a power supply for a part of the system. The distributed power supply system includes a separate power supply for each processor module and two separate power supplies for each device controller. Either one of the two power supplies provides the entire power for the device controller in the event the other power supply fails.
The distributed power supply system permits any processor module or device controller to be powered down so that on-line mainten-ance 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 in which the memory of each processor module is divided into four logical address areas -- user data, system data, user code and system code. The memory system includes a map which translates logical addresses to physical addresses and which coacts with the multiprocessor system to bring pages from secondary memory into primary main memory as required to implement a virtual memory system. The map also provides a protection function. It provides inherent protection among users in a multiprogramming environment, isolates programs from data and protects system programs from the actions of user programs. The map also provides a reference history information for each logical page as an aid to efficient memory management by the operating system.
The multiprocessor system includes in the memory of each processor module an error detection and correction system which detects all single bit and double bit errors and which corrects all single bit errors in semiconductor memory storage.

Description

~ 3~ 70917-2L

This application is a divisional of copending ~anadi-an Patent Applicatlon Serial No. 391,313 filed December 1, 1981 in the nama of Tandem Computers Incorporated.
This invention rela-tes to a multiprocessor computer system in which interconnected processor modules provide multi-processing (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 component failure can stop or contami-nate the operation of the system.
There are many applications which require on~line processing of large volumes of data a-t high transaction rates.
For example, such processing is required in retail applications for automated point of sale, inventory and credit transactions and in financial institutions for automated funds transfer and credit transactions.
In computing applications of this kind it is impor-tant, and often critical, that the data processing not beinterrupted. A failure of an on-line computer system can shut down a portion of the related business and can cause consider-able loss of data and moneyO
Thus, an on line system o-f this kind must provide not only sufficient computing power to permit multiple compu-tations 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 component of the systern fails.
The system should operate either in a Ea~l-safe mode (in which no loss of throughput occurs as a result of failure) or in a ail-soft mode tin 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 of the system. The system should provide fault-tolerant computing. For fault-tolerant com-puting all errors and failures in the system should either be corrected automatically, or if the failure or error cannot be corrected automatically, it should be detected, or if it cannot be detected, it should be contained and should not be permitted to contaminate the rest of th~ systemO
Since a single processor module can fail, it is obvious that a system which will operate without interrup-tion in an on-line application must have more than one processor module.
Systems which have more than one processor module can therefore meet one of the necessary conditions for non-interruptible operation. However, the use of more than one processor module in a system does not by itself provide all the sufficient conditions for maintaining the required pro-cessing capabilities in the event of component failure, as will become more apparent from the description ~o follow.
Computing systems for on-line, high volume, trans-action oriented, computing applications which must operate without interruption therefore require multiprocessors as a starting point. But the use of multiprocessors does not guarantee that all of the sufficient conditions will be met, and fulfilling the additional sufficient conditions for on-line ,~ .

- 2 -~` ~

1 systems of this kind has presented a number of problems ~ in the prior art.
j The prior axt approach to uninterrupted data 4 processing has proceeded ~Jenerally along two lines -- either 5 adapting two or more large, monolithic, general purpose ~ computers for joint operation or interconnecting a plurality 7 of minicomputers to provide multiprocessing capabilities.
8 In the first case, adapting two large monolithic g general purpose computers for joint operation, one conven-tional prior art approach has been to have the two compu~ers 11 share a common memory. ~ow in this type of`multiprocessing 1~ syste~ a failure in the shared memory can stop the entire 13 system. Shared memory also presents a number of other 14 p~àblems includingsequencing accesses to the common memory.
15 This system, while meeting some of the necessary conditions 16 for uninterruptible processing, does not meet all of the 17 sufficient conditlon5.
18 Furthermore, multiprocassing systems using large 19 general purpose computers are quite expensive because each -~0 computer is constructed as a monolithic unit in which all 21 components (including the packaging, the cooling system, 22 etc.) must be duplicated each time another processor is - -.
23 added to the system even though many of the duplicated 24 components are not required.

The other prior art approach of using a plurality of 26 minicomputers has (in common with the approach of using large 27 ~eneral purposa computers) suffered from the drawback of 28 ha~ing to adapt a communications link between computers 29 that were never originally constructed to provide such a 30 link. The required links were, as a result, usually made ~ r .

1 through the input/output channel. Connections through the 2 input/output channel ar~ necessarily slower than internal

3 transfers within thc processor itself, and such in~erprocessor

4 links have therefore provided relatively slow interprocessor S communicationO
6 Furthermore, the interprocessor connections 7 required special adapter cards that added substantially to 8 the cost of the overall system and that introduced the g possibility of single component failures which could stop 10 the system. Adding dual interprocessor links and adapt-er ~1 cards to avoid problems of critical single components failures 12 increased the overall system cost even more substantially.
13 Providing dual links and adapter cards between 14 a]l processors generally became very cumbersome and quite 15 complex frQm the standpoint of operation.
16 Another problem of the prior art arose out of the 17 way in which connections were made to peripheral devices.
18 ~ If a number of peripheral devices are connected to g a single input/output bus of one processor in a multiprocesso-20 system and that processor fails, then the peripheral devices ~1 will be unavailable to the system even thou~h the failed 22 processor is linked through an interprocessor connection to 23 another processor or processors in the system.
24 To avoid this problem, the prior art has provided an 25 input/output bus switch for interconnecting input/output busses 26 for continued access to peripheral devices when a processor ~7 associated with the peripheral devices on a particular input~
28 output bus fails. The bus switches have been expensive and also 29 have presented the possibility of single component failure 30 which could down a substantial part of the overall system.
. ' ' ' ' ' .
, 4 . , .

1 Providin~ sof~ re for the p~ior art multiprocessor 2 systems has also been a major problem.
3 Operating systems soft-.Yarc for such multiprocessinq 4 systems has tended to be nonexistent. Where soft~lare had been developed for such multiprocessor systems, it quite 6 often was restrieted to a small number of processors and 7 was not adapted for the inclusion of additional processors.
8 In many cases it was necessary either to modify the operating 9 system or to put some of the operatiny system functions into th~ user's own program -- an expensive, time-consuming 11 opexation. ...
12 - The prior art laeked a satisfactory standard operating 13 system for linking processors. It also did not provide an 14 oi~erating system Eor automatically aceommodating additional 15 proeessors in a multiproeessing system constructed to `
16 accommodate the modular addition of processors as increased 17 eomputering power was required.
18 A primary object of the present invention is to 19 eonstruet a multiprocessor system for on-line, transaction- -20 oriented applications which overcomes the problems of the 21 priol- art.
22 A basie objective of the present invention is to 23 insure that no single failure can stop the system or significantly ~4 affect system operation. In this regard, the system of 25 the present in~ention is eonstructed so that there is no 26 single eomponent that attaehes to everything in the system, 27 either mechanically or eleetrieally.
28 It is a elosely related objective of the present 29 invention to guarantee that every error that happens ean be 30 either eorrected, detected or prevented from contaminating the syst 1 It is another important objective of the present ~ invention to provide a system architecture and basic mode 3 of operation which free the user from the need to get involved 4 with the system hardware and the protocol of interprocessOr communication. In the present invention every major component 6 is modularized so that any major component can be removed or 7 replaced without stopping the system. In addition, the 8 system can be expanded in place (either horizontally by the g addition of standard processor modules or in most cases 0 vertically by the addition of peripheral devices) without system interruption or modification to hardware or software.

~6 ~5 ~6 3~

~\ ~

1 Sun~ary of the Invention 3 The multiprocessor system of the present invcntion 4 comprises multiple, independent processor modules and data

5 paths.

6 In one specific embodiment of the present invention 16 separate processor modules are interconnected by an interprocessor bus for multiprocessing and multiprogramming.
9 In this specific embodiment each processor module supports 0 up to 32 device controllers, and each device controller can 11 control up to eight periphexal devices.
~2 _ Multiple, independent communication paths and ports ~3 are provided between all major components of the system to 14 ir,ure that it is always possible to communicate between 15 processor modules and between processor modules and peripheral ~16 devices over at least two paths and also to insure that a 17 single failure wi:Ll not stop system operation.
~8 ~ These multiple communication paths ~nclude multiple 19 interprocessor busses interconnecting each of the processor 20 modules, multiports in each device controller, and input/output 21 busses connecting each device controller for access by at ~2 least two dif~erent processor modules.
23 Each processor module is a standard module and 24 includes as part or the module a central processing unit, a 25 main memory, ~n interprocessor cor.trol and an input/output 26 channelO
27 Each processor module has a pipelined microprocessor 28 operated by microinstructions included as a basic instruction 29 5et in each processor module.
~he basic instruction set in each .
l processor module reco~ni~es the fact that there is an 2 interprocessor ccmmunic~tions link; and when an additional 3 processor module is added to ~he system, the operating system 4 (a copy of which resides in each processor module) is informed 5 that a new resource is available for operation within the 6 existing operating system without the need to modify either

7 the system hardware or software.
To increase performance and to maintain very high 9 transaction rates each processor module includes a second 0 microprocessor which is dedicated to input/output operationsO
11 A dual port access to the main memory by both the 12 central processing unit and the input/output channel permits 13 direct memory access for the input/output transfers to also , 14 increase performance.
Each processor module is physically constructed 16 to fit on a minimum number of large printed circuit boards.
17 Using only a few boards for each processor module conserves 18 cpace for packaging and minimizes the length of the inter-19 processor bus required to interconnect all of the processor 20 modules. A relatively short interprocessor bus minimizes the ~L deterioration o~ the signals on the interprocessor bus and I ) - 22 permits high speed of communication over the interprocessor 23 bus.
24 Each interprocessor bus is a high speedj synchronous 25 bus to minimize overhead in interprocessor communications a~d 26 to enable the system to achieve high throughput rates.
27 A separate bus controller monitors all transmissions 28 over the bus. The bus controller includes processor select 29 logic for determining the priority of data transfer between 30 any two processor modules over the interprocessor bus. The , 1 bus controller also includes bus control state logic for 2 establishi~g a serlder-receiver pair of processor modules 3 and a time fra~e for a transfer of information over the bus 4 between the sender-receiver pair.
S Each bus controller includes a bus clock, and eac~.
6 central processing unit of each processor module has its own 7 separate clock. There is no master clock system subject to

8 a single component failure which could stop the entire

9 multiprocessor system.
0 Each processor module includes, in the interprocessor control of the processor module, a certain~amount of circui~y 12 on the printed circuit boards which is dedicated to communications 13 over the interprocessor buses.
14 ~ Each interprocessor control also includes fast buffers (inqueue buffers, and an outqueue buffer) which can 16 be emptied and filled by the central processing unit withou~
17 interfering with the interprocessor bus. This makes it 18 possible to sustain a higher data rate on the interprocessor 19 bus than could be sustained by any single pair of processors.
Several data transfers between pairs of processor modules 21 can be interleaved on an apparent simultaneous basis.

22 Because the interprocessor bus operates asynchronously 23 with each particular central processing unit, each inqueue 24 and outqueue buffer is clocked either by the processor module ~5 or by the bus controller, but not by both simultaneously.

26 Each inqueue buf-fer and outqueue buffer therefore 27 has associated with it in the interprocessor control some 2~ logic that operates in synchronism with ~le bus clock and ~9 other logic that operates in synchronism with the central processing unit clock. Logic interlocks qualify CertQin ; . ' .
: ' 9 ;~

1 transitions of the logic from one sta-te to another state 2 to prevent loss of da-ta in transf~rs between the asynchronous 3 interprocessor buses and proc~ssor module.
4 ~The logic is also arranged so that in the event a processor module is powering down, there will be no transient 6 effect on the interprocessor buses because the processor module 7 is losing control. The powering down of the processor module ~ on an interprocessor bus will therefore not disrupt any other g interprocessor bus activit~.
The bus controller and interprocessor control of e~ch processor module coact to perform all~interprocessor 12 bus management in parallel with processing by the central 13 processing units so that there is no waste of processing ~4 p~wer. This bus management is performed with low 15 protocol overhead in that it takes very few interprocessor 1~ bus cycles to establlsh a bus transfer -- what processor 17 bus module is sending and what processor module is receiving --18 relative to the amount of information actually transmitted.
19 The processor select logic of the bus controller 20 includes an individual select line which extends from the 21 processor select logic to each processor module. The select ; 2~ lines are used in three ways in the protocol of establishing 23 a sender-receiver pair of processor modules and a time 24 frame for transfer of information over the interprocessor 25 bus between the sender-receiver pair~ The select lines are - 26 used (l) in polling to determine which particular processor 27 module wants to send, (2) in receiving to inquire of a receiver 28 processor module whether the particular processor module wants to ~9 receive, and ~3) in combination with a send command to let the 30 sender processor module know the time frame ~or sending.

'- 10 1 The receiver processor module is qualified to ;~ 2 receive incoming data unsolici~ed by the receiver processor 3 module and ~lithout a soft.~are instruction.
4 Blocks of data between a sender-receiver pair of processor modules are transmitted over the interprocessor 6 bus in packets. At the end of each packet trarlsfer the 7 interprocessor control of a receiver processor module logically ~ disconnects from the interprocessor bus to permit the bus g control state logic to establish another sequence of a different sender-receiver pair of processor modules and a 11 time frame for making a packet transfer between the other 12 pair Df sender-receiver processor modules. Thus, as noted 13 abover several data block transfers between different sender-, 1~ receiver pairs of processor modules can therefore be interleaved 15 on the interprocessor bus on an apparently simultaneous ~asis 16 because of the faster clock rate of the interprocessor bus as 17 compared to the slower memory speed of the processor modules.

18 Each processor module memory includes a separate 19 buffer for each combination of a processor module and an 20 interproceSsor bus.

21 Each memory also includes a bus receive table for 22 directing incoming data from an interprocessor bus to a specified location in a related buEfer in the memory of a 24 receiver processor module. Each bus recei~e table provides 25 a bus receive table entry which contains the address where the 26 incoming data is to be stored and the number of words expected 27 from the sender processor module. The bus receive table 28 entry is updated by firmware in the processor module after 29 the receipt of each packet and is effecti~e with the firmware 30 either to provide a progxam interrupt when the entire data , .

~ r .

1 block has been successfull~ received or to provide an interrupt2 ~o the software program currently e~ecuting in the processor 3 module in response to the detection of an error in the course 4 of the transmission of ~he data over the interprocessor bus~
S Producing a program interrupt only at the comple~ion o the 6 data block transfer enables the transfer of data to be made 7 transparent to the software currently executing in the 8 processor module. The interxupt in response to the detec~ion 9 of an error provides an integrity check on the transmission of data.
11 The input/output subsystem of the multiprocessor 1~ system of the present invention is constructed to insure that 13 no single processor module failure can impair system operation.
14 ~ In addition, the input/output subsystem is 15 constructed to handle very high transaction rates, to 16 maximize throughput, and to minimize interference with 17 programs running in the processor modules.
18 ~ As noted above, each processor module includes a , 19 microprocessor which is dedicated to input/output operations.

The input/output system is an interrupt driven 21 s~stem and provides a pro~ram interrupt only upon completion 22 Of the data transfer. This relieves the central processing 23 unit from being dedicated to the device while it is transferring 24 data.

Each input/output channel is block multiple~ed to 26 handle several block transfers of data from several device 27 controllers on an apparent simultan~ous basis. This is 28 accomplished by interleaving variable length bursts o data Z9 in transfers between the input/output channel and stress 30 responsive buffers in the device controllers.

:

- ~ ~ ~

"~

1 As noted above, each device cont~oller has multiports, 2 and a separate input/output bus is connected to each port 3 so that each device controller is connccted for access by 4 at least two different processor modules.
The ports of each device controller are construct~d 6 so that each port is lo~ically and physicall~ independent - 7 of each other port. No component part of one port is also a 8 component of another port so that no sinqle component failure 9 in one port can affect the operation of another port.
Each device controller includes logic which insures ~1 that only one port is selected for access at a time so that 2 transmitting erroneous data to one port can never contaminate 13 anothex port.
.
14 The input/output system of the present invention 15 interfaces the peripheral devices in a fallsoft manner. The~e 16 are multiple paths to each particular device in case of a 17 failure on one path. And a failure of the device or a failure i8 of a processor module along one path does not affect the 19 operation of a processor module on another path to the device.

The input/output system of the present invention 21 is also constructed so that any type of device can be put 22 on the system, and the input/output system will still make 23 maximum usage of the input/output channel bandwidth.

24 The device controllers are buffered such that all 25 transfers bet~een the device controllers and the input~output ~6 channel occur at the maximum channel rate.

27 The device controller may transfer between itsel~
~. .
2~ and a peripheral device in bytes, but the device controller 29 must pack and unpack data to transfer words between itself 30 and the input/output channel.

Because the buffers are located in the device 2 controllers rather than in the input/output channel, the 3 present invention limits the buffering to only the buffering 4 required by a particular system configuration. The present inve~tion does not require a separate buffer for each peripheral 6 device in order to prevent overruns, as would be required 7 if the buffers ~ere located in the input/output channel 8 rather than in the device controllers as had often been the 9 practice in the prior art.
As noted above~ each buffer is a stress responsive ~1 buffer and this provides two advantages.
1~ First of all, each buffer can be constructed to 13 have an overall depth which is related to the type and number 14 O- devices to be serviced. Each device controller can therefore ~5 have a buffer size which is related to the kind of devices 16 to be controlled, 17 Secondly, the stress responsive buffer construction 1~ and mode of operation of the present invention allows the 19 buffers to coopexate without communicating with each other.
20 This in turn permits optimum efficient use of the bandwidth 21 Of the input/output channe]. ~ ' 22 The stress placed on a particular buffer is determined 23 by the degree of the full or empty condition of the buffer 24 in combination with the direction of the transfer with respec~
25 to the processor module. Stress increases as the peripheral 26 device accesses the buffer, and stress decreases as the input/
27 output channel means access the buffer.
28 Each buffer has a depth which is the sum of a 29 threshold depth and a holdoff depth. The threshold depth 30 is related to the time required to service higher priority 7~
1 device controllers, and the holdoff depth is related to the t 2 time required to servlce lower ~riorit~ de~ice controllers 3 connected to the s~me input/outpu~ channelO
4 The stress responsive buffer inclu~s control 5 logic for keeping track of the s~ress placed on the buffer.
The control logic is effective to make reconnect requests 7 to the input/output channel as the stress passes through a 8 threshold depth of the buf~er.
9 Each buffer having a reconnect request pending is

10 individually connected to the input/outpu~ channel in -

11 accordance with a polling scheme which reso~ves priority

12 among_all the device controllers havin~ a reconnect request

13 pending.
1~ ~ When the device controller is connected to ihe 15 input/output channel, the data is transferred between the 16 buffer and the input/output channel in a burst at or 17 near memory speed.
18 Thus, ~ecause the buffers transmit data to and 19 from the peripheral devices at the relatively slow device 20 speed and can transmit the data to and from the processor 21 modules at or near memory speed in burst transfers, and in 2Z response to buffer stress, the burst transfers can be time 23 division multiplexed so that individual bursts from several 24 device controllers can be interleaved to optimize efficient 25 use of the bandwidth of the input/output channel and also to 26 permit several block transfers from different device controllers 27 to be made on an apparent simultaneous basis.
Z~ Comprehensive error checks and provision for error 29 containment are provided for all data transfers over the data 30 paths of the multiprocessor s~stem.

!

~5~7~

The error checks include check summ1n~ and par-ity checks on the data pa-ths and error detection and correction in the main memory system.
The error checks also include time out limita-tions in the input/output channel.
`, ErrGr containment is provided in -the input/
- output system by an input/ou-tput con-trol table having a ~ two-word entry for each peripheral device'to define a : buffer area in the memory for the particular device controller and device. Each two-word entry describes the ~ buffer location in main memory and the remaining byte - count length to be transferred at any particular time for a particular data transfer to a device. The input/output control table is located in each processor instead of in the device controllers to contain the results of any failure in the countword or address word to the single processor module in which the countword or address word '1 is physically located. Each of the processor modules that is connected for access -to common device controllers and related devices contains its own copy of the input/output control table. The failure of a table entry in one pro-cessor module does not affect the other processor module because the other processor modu7e has its own correct - copy of the table entry.
The multiprocessor system of the present inven-tion includes a power supply system which distributes separate power supplies to the processor modules and device controllers in a way to insure uninterrupted operation of the remainder of the multiprocessor system in the event of failure of a power supply for part of the multiprocessor system.

i'7¢~

1 Any processor module or device controller can ke 2 powered down so that on-line maintenance can ~e performed in 3 a powered off condition while the rest of the multiprocessor ', 4 system is on~line and functional.
The power supply system includes a separate power 6 supply for each processor module and two separate power 7 suppiies for each device controller.

8 The two separate power supplies are operatively 9 associated with the device controller by a switch which permits one power supply to supply all of the power for the 1~ device controller in the event of a failure of the other 12 power supply.
13 The power supply system of the present invention

14 also produces a power failure warning signal which is ~' 15 effective to save the state of the logic in a processor module 16 in the event of a 'ailure of a power supply associated with ~7 that processor module. When po~er is xestored, the processor ~ 18 module is returned to operation in a state that is known a~d - 19 without the,loss of data.
The memory of the multiprocessor system of the 21 present invention is divided into four logical areas -- user 22 data, system data, user code and system code. This division 23 of memory into four separate logical address areas separates 24 code from data so that code can be made nonmodifiable and also separates operating system programs from user programs 26 50 that users cannot inadvertently destroy the operating 27 System.

28 The multiprocessor system of the present invention ~9 includes a memory map which performs a number of functions.

-, 17 1 One function of the map is to provide a virtual 2 memory system in which all code and data are inherently 3 relocatable so that the user need not be concerned wi~h the 4 actual physical location of either system or user programs 5 or the amount of physical memory attached to the system.
! 6 The map translates logical addresses to physical 7 addresses for pages in main memory and provides page fault 8 interrupts for pages not in main memory. The operating g system brings pages from secondary memory (i.e., memory stored in peripheral devices) into the primary main memory in the processor module as required to implement a virtual ~2 memory system in which the physical page addresses are invisible 13 to users and in which logical pages need not reside in 14 ccntiguous physical pages and need not be in physical main

15 memory but may be in secondary memory.

16 The map also provides a protection function and

17 a memory management function.

18 ~ The map provides a separate map for each ~eparate ~' 19 logical area of memory.
This provides protection by separating code from ~1 data and also by separating the user programs from the 22 system programs, as pointed above.
Xt also provides protection among users in a 24 multiprogramming environment because the ~ap which is in 25 effect for a particular user points only to the physical ~6 memory pages of that user's program~ This prevents one user from writing into a program page of another user's ~8 program~ This feature of a user map therefore protects, 29 without the need for protection registers, one user Erom 30 destroying another user's proyram.

' ~` ~

1 The map in conjunction with the operating systcm 2 performs a map memory management function to reduce o~er~ting 3 overhead in the management of the memory syst~m by (l~ making 4 pages available from secondary memory, (2) keeping track of frequency of use of physical pages in primary mernory, 6 (3) reducing virtual memory page input/output transfers, 7 and (4) reducing interrupts to the operating system. The 8 way that the map accomplishes these functions provides g an efficient virtual memory system.
The number of pages available in physical main -11 memory is limited. Physical pages must the,refore sometimes 12 be brought into physical main memory from secondary memory.
13 One important aspect of efflcient memory management 14 is to keep track of what pages in physical main memory are 15 being used frequently enou~h so as to need to be retained 16 in physical main memory.
;~ 17 , Another important aspect is to know whether any 18 particular pages in physical main memory can be written

19 over (overlaid) w:ithout having to be first swapped out to

20 secondary storage.

21 The map includes history bits as a part of the map

22 entry for each page. These history bits (which are physically

23 in the map entry) give a histogram of usage of the given

24 physical page over a period of time. And, in the present

25 invention, the history bits are periodically updated by

26 hardware without the need for program intervention.
' Each map entry also includes a "dirty bit" for ~8 indicating whether a particular page has been written into 29 since it was last brought in ~rom secondary storage.

. . , o 1 The map th~refore includes in ~he map itself~
`-~ 2 information which permits the memory mana~er to determine 3 whether a particular page in physical main memory is a good 4 candidate for being overlaid (~hen it is necessary to bring a page in from secondary storage ancl no empty page or code 6 page in physical main memory is available for an overlay) 7 and to determine also, if an overlay is required, whether '! 8 or not it is necessary to swap the overlaid page out to g seoondary storage before the page can be overlaid. Since 0 copies of all non-dirty pages are kept in secondary storage, 1l no swap is re~uired if the dirty bit is not on.
12 The map is contained in a part of the memory which ¦
13 is separate from the main memory. Each map is constructed to 14 ~~ovide significantly faster access than the access to physical main memory so that the map can be rewritter, in the ~6 time that a physical memory access is being accomplished.
17 The rewriting of the map therefore does not increase memor~
18 cycle ~ime.
19 As noted above, the memory includes dual port access for the central processing unit and the input/output channel.
21 The input/output channel can therefore access the memory 22 directly, without having to go through the central processing 23 unit, for data transfers to and from a device controller. ~Y
24 Central processing unit accesses to memory and input/output channel accesses to memory can therefore be in-terleaved in time.
26 All data transfers to and from memory by the

27 input/output channel are made by way of the system data map~

28 The system data map adds additional bits in the course of ~9 translating the logical addresses to physical addresses.
This permits a larger number of words of physical memory '7~

.
1 to be accessed by using a shorter lo~ical address to access 2 a larger physical space than the word width i~self would 3 normally allow.
4 The present invention also provides a syndrome 5 decoding method for detec~ing and correcting errors in 6 semiconductor memory modules.
7 The storage area of the semiconductor memory 8 module comprises words of 22 bits. Each word has a 16 bit 9 data field and a six bit check field.
~o Each memory module includes an error detector for simultaneously correcting all single bit and detecting all 2 double bit errors and detecting many of the errors of 3 bits 13 or more anywhere in the 22 bit word. The error correction 14 includes a check bit generator, a check bit comparator~ a~d 15 a syndrome decoderO
16 The check bit generator provides a code in which 17 each check bit is a linear combination of eight data bits 18 and in which each data bit i5 a component of exactly three 19 check bits.
The check bit comparator provides six output 21 syndrome bits. The input o~ each of the output syndrome 2 bits is eight data bits and one check bit.
23 The syndrome decoder interprets the value of the 24 six output syndrome bits and identifies the presence or 25 absence of errors and the type of errors, if any, in the ~ 22 bit word.
27 A data bit complementer is also provided for 28 inverting a single data bit error detected by the syndrome

29 decoder and thus correcting the error.

The semiconductor memory sys-tem is therefore tolerant of single bit Eailures and can be operated with slngle bit failures until such time as it is convenient to rapair the memory.
Multiprocessor system apparatus and methods which incorporate the structure and techniques described above and which are effective to function as described above constitute further, specific objects of this invention.
According to the present invention, there is provided an input/output system for a multiprocessor system comprising a plurality of separate processor modules~ each processor module having a central processing unit and a memory, each processor module being capable of performing work of substantially equal importance, at least two of the processor modules each having : an input/output channel, at least one device controller for controlling the transfer of data between a processor module and a peripheral device, at least two ports in each device control-ler, at least two input/output buses, a first of the input/out-put buses being operatively connected between the input/output channel of a first of the processor modules and a first of the ports and a second of the input/output buses being operatively connected between the input/output channel of a second or the processor modules and a second of the ports, at least two interprocessor bus means distinct from the input/output buses and operatively connected between at least two of the processor modulas for signaling and data transfer therebetween, and means in at least two of the processor modules for detecting that one such processor module has failed and Eor causing the other such processor module to take over the work of the failed processor module.
The invention will now be described in greater detail with reference to the accompanying drawings, in which:

-22~

'7~

.
Figure 1 is an isometric, block diagram view of a mu]tiprocessor system constructed in accordance with one embodiment of the present invention. Figure 1 shows several processor modules 33 connected by two interprocessor buses 35 (an X bus and a Y bus) with each bus controlled by a bus controller 37. Figure 1 also shows several dual-port device controllers 41 with each device controller connected - to the inpu-t/output (I/O) buses 39 of two processor modules;
Figure 2 is a block diagram view showing details of the connections of the X bus controller and the Y bus controller to the individual processor modules. Figure 2 shows, in diagrammatic form, the connections between each bus controller and the interprocessor control 55 of an individual processor module;
Figure 3 is a detailed diagrammatic view of the logic of one of the bus controllers 37 shown in Figure 2;
Figure 4 is a detailed diagrammatic view of the logic for the shared output buffer and control 67 in the interprocessor control 55 of a processor module as illus-trated in Figure 2;
Figure 5 is a view like Figure 4 but showing the logic for an inqueue buffer and control 65 of the inter-- processor control 55 for a processor module;

.",~

'7~

1 E`ig. 6 is a state diagram of the lo~ic 81 for 2 a ~us controller 37 a~d illustrates how the logic res-3 pond~ to the protocol lines goin~ into the bus controller 4 and ge~erates the protocol lines going out of the b~s 5 contr~ller to the processor modules;
7 Fig. 7 is a state diagram like Fig. 6 but - 8 show~g the logic 73 and 75 for the shared outqueue 9 ~uffex and control 67 of Fig~ 4;

il Fig. 8 is a state diagram like Figs. 6 and 7 1~ but showing the logic 93 and 101 for the inqueue buffer 13 and control 65 o~ Fig. 5;

Fig. 9 is a diagrammatic view showing the time 16 sequence for the transmission of a given packet between 17 a 5ender processor module and a receiver processor 18 mOdule;
.
~ g Fig. 10 is a logic diagram of the bus empty 21 sta~e logic section 75 and the processor fill state ~ logic sectlon 73 of the outqueue bu~fer and the control 23 67 shown in Fig. 4;

Fig. 11 is a listing of logic equations for 26 the logic diagram shown in Fig. 10;

28 Fig. 12 is a block diagram of the input/output 29 ~I/O) syst~m of the multiprocessor system shown in

30 Fig. l;

_~.

7~3 1 ~ig. 13 is a blocX diagxam of the input/output 2 (I/O) channel 109 of a processor module. Fig. 13 shows 3 the major components of the I/O channel and the data 4 path relating those component parts S .~
;~ 6 Fig. 14 is a detailed view showing the 7 individ~al lines in the I/O bus 39 of Fig. l;

Fig. 15 is an I/O channel protocol diagram 10 showing the state changes of the T bus 153 for an execute `~ 11 input/output (EIO) caused by the microprogram 115 in the 12 C~U 105. The sequence illustrated is initiated by the 13 CPU 105 and is transmitted through the I/O channel 109 14 of the processor module 33 and on the T bus 153 to a 15 device controller 41 as shown in Fig. l;
- ~ 16 ' 17 Fig. 16 is an I/O channel protocol diagram ~8 showing ,the state changes of the T bus 153 for a reconnect 19 and data transfer se~uence initiated by the I/O channel 20 microprogram 121 in res~onse to a request signal from a 21 device controller 41i Fig. 17 is an I~O channel protoco~ diagram 24 showing the state changes of the T bus 153 ~or an 25 interrogate T/O ~IIO) instruction or an interrogate high 2~ priority I/O (HIIO) instruction initiated by the CPU
27 microprogram 115. The sequence illustrated is trans-2~mitted over the T bus 153 to a device controller 41 ~ 2~

ZS
:~

1 Fig. 18 ls a table identifying the functions 2 referred to by the mnemonics in Figs. 15 through 17;

4 Fig. 19 is a block diagram showing the 5 general structure of the ports 43 and a device controller 6 41 as illustrated in Fig. l;

8 Fig. 20 is a block diagram of a port 43 sho~
~ in Fig. 19. This Fig. 20 shows primarily the data paths ;~ 10 within a port a3;

12 Fig. 21 is a block diagram showing the data ~3 path details of the int5~rface common logic 181 of the 14 device controller 41 shown in Fig. 19;

16 Fig. 22 is a block diagram showing the component 17 parts of a data buffer 189 in the control part of a 1~ device controller 41 as illustrated in Fig~ 19;

Fig. 23 is a graph illustrating the operation 21 of the data buffer 189 illustrated in Figs. 22 and Fig. 19;

23 Fig. 24 is a timing diagram illustrating the - 24 relationship o SERVICE OUT (SVO) from the channel 109 2S to the loading of data into the port data register 213 26 (Fig. 21) and illustrates how the parity check is started , 27 before data is loaded into the register and is continued .,,: , .
28 until after the data has been fully loaded into the register;

3Q Fig. 25 is a schematic view showing details

31 of the power on circuit (PON) shown in Figs. 19 and 21;

26 ~

7~
1 Fig. 26 is a logic diagram cf the buffer 2 control losic 243 of the data buffer 189 (shown in 3 Fig. 22) of a device controller 41. Fig. 26 shows 4 how the buffer control logic 2~3 controls the hand-- 5 shakes on the data ~us and controls the input and output 6 polnters;

8 Fig~ 27 is a listing of the logic equations g fox the select register 173 shown in Fig. 20. These logic e~uations are implemented by the port control logic 191 shown in Fig. 20 13 Fig. 28 is a timing diagram showing the 14 operation of the two line handshake between the I/0 15 ~h~nnel 109 and the ports 43;

17 Fi~o 29 is a losic diagram showing the logic 18 for the general case of the handshake shown in Fig. 28.
g The logic shown in Fig. 29 is part of the T bus machine 20 143 of the input/output channel 109 shown in Fig. 13;

'` - 22 Fig. 30 is a block diagram of a power - 23 distribution system. Fig. 30 shows how a plurality of 1 24 independent and separate power supplies 303 are 25 distributed and associated with the dual port device 26 controllers 41 for insuring that each device controller has both a primary and an alternate power supply;

29 Fig. 31 is an enlarged, detailed view of 30 the switching arrangement ~or switching between a -1 primary power supply and an alternat~ supply for a 2 de~ice controller. The switching structure shown in 3 Fig. 31 permits both automatic switching in the event of a failure of ~he primary po~er sup~lv and manual 5 switching in three different modes--off, auto and 6 alternate;

~ ~ Fig. 32 is a block diagram showing details - 9 of one of the separate and independent power supplies 0 303 illustrated in Fig. 30 t 12 ~ FigO 33 is a block diagram view showin~
13 details of the verti.cal buses and the horizontal buses 14 for supplying power from the separate power supplies ~- ~ 15 303 shown in Fig~ 30 to the individual device controllers ~ 16 41. The particular bus arrangement shown in Fig. 33 ;; 17 permits easy selection of any two of the individual 18 power supplies as the primary and the alternate power 19 supply for a particular device controller;

21 Fig. 34 is a block diagram of the memory 2~ system and shows details of the memory 107 of a processor 23 module 33 shown in Fig. l;

Fig. 35 is a block diagram showing details 26 of the map section 407 or the memory 107 shown in 27 Fig- 34;

29 Fig. 36 is a block diagram showing the 30 organization of logical memory into ~our logical address . 2~ .

'7~

areas and four separate map sections corresponding to 2 the four logical address ar~as. Fig. 36 also shows 3 details of the bits and fields in a single map entry 4 of a map section;

6 Fig. 37 is a block diagram showing details 7 of one of the memory modules 403 illustrated in Fig. 34.
8 The memory module 433 shown in E'ig. 37 is a semiconductor 9 memory module;

il Fig~ 38 is a diagram of a check blt generator 12 used in the semiconductor memory module 403 shown in 13 Fig. 37. Fig. 38 also lists logic equations for two of 14 th~ eight bit parity trees used in the check bit register;

Fig. 39 is a diagram of a check bit comparator 1~ used in the semiconductor memory module 403 shown in lg Fig. 37. Fig. 39 includes the logic equation for nine 19 bit parity tree for syndrome bit zero;

~1 Fig. 40 is a diagram of a syndrome decoder 22 used in the semiconductor memory module 403 shown in 23 Fig. 37. Fig. 37 also lists the logic equations for 24 the operation of the logic section 511 of the syndrome ~5 decoder;

27 FigO 41 is a logic diagram of a hit complementer 28 used in the semiconductor memorv module 403 shown in 29 Fig. 37; and 29 _-~

'7~

1 FigO 42 shows the various states of a two 2 processor systcm running an application program which is 3 required to be running continuously. The diasrams f~ illustrate the two processors successively failin~ and 5 being repaired and the application prosram chan~ing its 6 mode of operation accordinsly.

1~ , ~ .

1,: .

~0 ~1 2~

2~

--: 30 ~
., .

, THE MULTIPROCESSOR SYST~M:
; Figure 1 is an isornetric diagrammatic view of a part of a mul-tiprocessor system constructed in accordance wi-th one embodiment of the present invention. In Figure 1 the multiprocessor system is indicated generally by the reference numeral 31.
The multiprocessor system 31 incl.udes individua].
processor modules 33. Each processor module 33 comprises a central processing uni-t 105, a memory 107, an input/ou-t-put channel lC9 and an interprocessor control 55.
The individual processor modules are inter-connected by interprocessor buses 35 for interprocessor ` eommunications.
In a specific embodiment of the multiprocessor system 31, up to si~teen proeessor modules 33 are inter-eonnected by two interproeessor buses 35 (indieated as the X bus and the Y bus in Figure 1).
. Each interproeessor bus has a bus eontroller 37 associated with that bus.

., 1 The bus controllers 37, interprocessor buses 35 2 and interprocessor controls 55 (Fis. 1), together with 3 associated microprocessors 113, micropro~rams 115 and bus 4 receive tables 1~0 (Fig. 2) provide an interprocessor bus system. The construction and operation of this interprocessor 6 bus system are illustrated in Figs. 2 - 11 and 42 and are 7 described in more detail below under the subtitle The 8 Interprocessor Bus System.

0 The multiprocessor system 31 has an input/output (I/O) system for transferring data between the processor ~2 modul~es 33 and peripheral devices, such as the discs 45, 13 termirals 47, magnetic tape drives 49, card readers 51, and 1~ l ne printers 53 shown in Fig. 1.

16 The I/O system includes one I/O bus 39 associated 17 with each I/O channel 109 of a processor module and one or 18 more multi-port device controllers 41 may be connected to 19 each I/O bus 39.

- 21 In the speci~ic embodiment illustrated, each device 22 controller 41 has two ports 43 for connection to two different 23 processor modules 33 so that each devlce controller is 24 connected for access by two processor modules.

26 The I/O system includes a microprocessor 119 27 and a microprogram 121 in the I/O channel 109 (See Fig. 12.) ~8 which are dedicated to input/output transfers.

- 32 ~5~i'7~3 1 As also dia~ra~atically illustrated in Fig. 12~
2 the microprocessor 113 and microprogram 115 of the central 3 processing unit 105 and an input/output control table 140 in - 4 the main memory 107 of each processox module 33 are operatively ~- 5 associated with the I~O channel 109.

7 The construction and operation of these and other ~ components of the I/O system are illustrated in Figs. 12 - ~9 - 9 and are described in detail below under the subtitle The ~o Input/Ou~put System and Dual Port Device Controller.
, ., ,, ....................... _........... -.Ll ' 12 -~ The multiprocessor system includes a power distribution 13 system 301 which distributes power from separate power supplies 14 t~ the processor modules 33 and to the device controllers 41 ~5 in a way that permits on-line maintenance and also provides redundancy of power on each device controller.

18 As illustrated in Fig. 30, the power distribution 19 system includes separate and independent power supplies 303.

21 A separate power supply 303 is provided for each ~2 processor module 33, and a bus 305 supplies the power from i 23 the power supply 303 to the central processin~ unit 105 24 and memory 105 oE a related processor module 33.

~ 28 .. 29 . 3 . . .

s ~ '7~3 ~, As also illustrated in Figure 30, each device controller 41 is connected for supply of power from two separate po~er supplies 303 through an automatlc switch 311. If one power supply 303 for a particular . device controller 41 fails, that device controller is supplied with power from the other power supply 303; and the changeover is accomplished smoothly and without any interruption or pulsation in the power supplied to the device controller.
- The power distribution system coacts with the dual port system of the device controller to provide continuous operation and access to the peripheral devices in the event of a failure of either a single port 43 or a single power supply 303.
The multiprocessor system includes a power on (PON) circuit 182 (the details o which are shown in Figure 25) in several components of the system to establish that the power to that particular component is within certain acceptable limits.
For example, the PON circuit 182 is located in each CPU 105, ' in each device controller 41, and in each bus controller 37.

~. .

, 20 ., .

~ `i .
~, .

~' ,. ,,; .
., ,, .

i7q~
.
l The purpose of the PO~ circuit is to present 2 a signal establishing the level of power applied to that 3 particular component; ~d if the power is not within 4 certain predetermined acceptable limits, then the signal output is used to direct7y disable the appropriate bus 6 signal of the compo~ent in which the PON is located.

8 The power-on circuit functions in Eour states --9 power of~; power going from off to on; power on; and power going from on to off.
~` 1~ .
~2 ~ The power-on circuit initializes all of the logic 13 states of the system as the power is brought up; and in ~4 t},e present invention, the power-on circuit provides an 15 additional and very important function o providing for 1~ a fail-safe system with on line maintenance. To do this, r' 17 the power-on circuit in the present invention is used in 18 a unique way to control the interface circuits which drive 19 all of the intercommunication buses in the system.

21 The construction and operation of the power ' 22 distribution system are illustrated in Figs. 30-33 and `~3 are described i~ detail below under the subtitle Power 24 Di5tribution System.

2~ The multip~-ocessor system includes a memory system 27 in which the physical memory is divided into four logical 28 address areas -~ user data, system data, user code and 29 system code (See Fig. 36.).

, ! 1 The memory system lncludes a map 407 and control 2 logic 401 tsee Fig. 34.) for translating all logical addresses 3 to physical addresses and for indicating pages absent from 4 primary storage bit present in secondary storage as required ~o implement a virtual memory system in which the physical 6 page addresses are in~isible to users.

8 The memory system incorporates a dual port access g to the memory by the central processing unit 105 and the 0 I/O channel 109. The I/O channel 109 can thereore access 11 the memory 107 directly (without having to go through t~e 12 central pxocessing unit 105) for data transfers to and from a device controller 41.

lS The construction and operation of the memory ~' 16 system are illustrated in Figs. 34-41 and are described in 17 detail below under the subtitle Memory System~

.,:, .
g An error detection system is incorporated in 20 the memory system for correcting all single bit and detecting 21 all double bit errors when semiconductor memory is used in 2Z the memory system. This error detection system utilizes a S~ 23 16 bit data ield and a 6 bik check ~ield as shown in Fig. 37 24 and includes a data bit complementer 487 as also shown in Fig. 37 for correcting single bit errors.

` 26 ; 36 1 Fiqs. 37 throuqh 41 and the related disclosure 2 illustrate and describe det2ils of the error detection 3 system.

S Before going into the detailed description of 6 the systems and components noted generally above, it should 7 be noted that certain terminology will have the following 8 meanings as used in this application.

1~ The term "software" will refer to an operating 11 system or a user program instructions; the term "firmware"
12 will refer to a microprogram in read only memory; and 13 the term "hardware" will refer to actual electronic logic 14 a d data storage.

16 The operating system is a master control program 17 executing in each processor module which has primary control 1~ of the allocation of all system resources accessible to 19 that processor module. The operating system provides a 2~ scheduling function and determines what process has use of 2~ that processor module. The operating system also allocates ~2 the use of primary memory (memory management), and it 23 operates the file system for secondary memory management.
24 The operating system also manages the message system.
25 This provides a facility for informati3n transfex o~er 26 the interprocessor buso 1 The operating system arrangement parallels 2 the modular arrangement of the mu7tiprocessor syste~
3 components described above, in that there are no "ylobal"
components.

6 At the lo~Jest level of the software system, 7 two fundamental entities are implemented--processes and 8 messages.

A process is the fundamental entity of control 11 within a system.
~ .
13 Each process consists of a private data space 14 an~ register values, and a possibly shared code set. A

15 process may also access a common data space.

17 A number of processes coexist in a processor 18 module 33.

The processes may be user written programs, or 21 the processes may have dedicated functions, such as, ~or 22 example, control of an I/O device or the creation and 23 deletion of other processes.

~4 A process may request ser~ices from another process, and this other process may be located in the same processor module 33 as a process making the request, or 28the other process may be located in some other processor zgmodule 33.

7~
1 The processes work in an asynchronous manner, 2 and the processes thereforc need a m~thod of communlcation 3 that will allow a request for services to be queued with~
4 out "races" (a condition in which the outcome depends 5 upon the sequence of which process started first)--thus 6 the need or "messages" (an orderly system of interprocessor .7 module communication described in more detail below).

9 Also, all interprocessor module communication 10 should appear the same to the processes, regardless of 11 whether the processes are in the same or in differen~-12 processor modules.

14 ` As will become more clear from the description 15 to follow, the software structure parallels the hardware;
16 and different processes can be considered equivalent to 17 certain components of the hardware in arrangement and 18 function.

For example, just as the I/O channel 109 21 communicates over the I/O bus 39 to the device controller 22 41, a user process can make a request (using the message . . .
23 system) to the process associated with that device controller 24 41; and then the device process returns status back 25 similar to the way the device controller 41 returns 26 information back to the I~O channel 109 ovex the IfO bus 39.

28 The other fundamental entity of the software 2g system, the message, consists of a request for service as 30 well as any required data. When the request is completed, ' . , .

: 39 .

1 any required values will be re~urned to the requesting2 process.

4 When a message is to be sent between ~rocesses 5 in two different processor modules 33, the interprocessor 6 buses 35 ar~ used. However, as noted above, all communication 7 between processes appears the same to the processes, 8 regardless of whether they are in the same or in different 9 processor modules 33.

~0 11 This software organi~ation provides a numbex 12 o benefits.

14 This method of structuring the software also ~5 provides for significantly more reliable so~tware. By 16 being able to compartmentaliæe the software structure, 17 smaller mcdule sizes can be obtained, and the interfaces 18 between modules are well defined.
~,9 The system is also more maintainable because 21 of the compartmentalization of function.

23 The well defined modules and the well defined 24 inter~aces in the software system also provide advantages , . .
~5 in being able to make it easily expandible~-as in the 2~ case o~ adding additional processor modules 33 or device ~7 controllers 41 to the multiprocessor system.
~g 29 Furthermore, there is a bene~it to the user 30 of the multiprocessor system and software system in that , . .
~

-1 the user, writing his ~ro~ram, need not be aware of either 2 the actual machine configuratlon or the physical location 3 of other processes.

Just as the hardware provides multiple function-6 ally equivalent modules with redundant interconnects, so 7 does the soft~lare.
., 8 9 For example, messages going between processes ~0 in different processor modules 33 may use either inter-processor bus 35. Also, device controllers 41 may be ~2 operated by processes in either of the processor modules 13 33 connected to the device controller ~1.
1~ -~5 The multiprocessor hardware system and software 1~ system described above enable the user to develop a 17 ault tolerant application system by virtue o lts 18 replic~ted modules with redundant interconnects.

'' 22 - ~3 27 - ..
~8 .~ ~9 . 3 ~ / ( 3'7~
.
THE I~IT~RPROCESSOR BUS S'fSTl~M:

3As pointed out above, the individual processor 4 modules 33 are interconnected by two interprocessor buses 5 35 (an X bus and a Y bus) with each bus controlled by a 6 related bu~ controller 37. Each interprocessor bus 35, in 7 combination with its bus controller 37 and a related inter-processor control 5~ in each processor module 33, provides g a multi-module communication path from any one processor 10 module to any other processor module in the system. The 11 use of two buses assures that two independent paths exist 12 between all processor modules in ~he system. Therefore, a 13 failure in one path (one bus) does not pxevent communication 14 bttween the processor modules~

16 The bus controller 37 for each interprocessor bus 17 35 is a controller which is, in a preferred form of the 18 invention, separate and distinct from the processor modules 33.
19 , . .
Each interprocessor bus 35 is a synchronous 21 bus with the time synchronization provided by a bus clock 2~ generator in the bus controllers 37. The interprocessor 73 control portions 55 of all of the modules associated with 24 the bus make state changes in synchronism with that bus 25 clock during transfers over the bus.

27 As will be describ~d in more detail below, the 28 CPU 105 operates on a different clock from the inter-29 processor bus clock. During the filling of an outqueue 30 or the emptying of an.inqueue in the interprocessor control 1 55 by the CPU, the operation takes place at the CPU clock 2 rate. However, transmission of pac~ets over the inter-3 processor bus always takes place at tne bus cloc~ rate.

S It is an important feature of the present 6 invention that the information transmitted over the inter-7 processox bus is transferred at high transmission rates 8 without an~ required correspondence to the clock rates of 9 the various CPUs 105. The information transfer rate over 10 th~ interprocessor bus is also substantially faster than li would be permitted by direct memory accesses into and out 1~ of the memory sections 107 at memory speed. This ensures 13 that there is adequate bus bandwidth even when a large number 14 o~ processor modules is connected in a multiprocessor system.

16 A benefit of usin~ separate clocks for each CPU
17 105 is that a ma~ter system clock is not required, and 18 this eliminates a potential source of single component , 19 failure which could stop the entire system.

Z1 ~he interprocessor control 55 incorporates logic 22 interlocks which make it possible to operate the inter~

23 processor buses 35 at one clock rate and each CPU 105 24 a~ its own independent clock rate without loss o data.

~= 26 The information transmitted over the bus is 27 transmitted in muLtiword packets. In a preferred form - 28 of the present invention each packet is a sixteen word 2g packet in which fifteen of the words are data words and 30 one word is a chec~ word.
, .

, ~3 ( '--1 The control logic ~ithin the bus contr~l~er 2 37 and the interprocessor controls 55 of the individual 3 modules 33 follows a detailed protocol. The protocol 4 provides for establishing a sender-receiver pair and a 5 time frame for the data packet transfer. A~ the end of 6 the time frame for the transmissioll of the data packet, 7 the bus controller 37 is released for another such sequence.
8 The specific manner in which these functions are carried 9 out will become more apparent after a description of the 10 structural features of Figs. 3-9 below.

li ., 12 X bus 35 is identical in structure to the 13 Y bus 35, so the structure of only one bus will be 14 de3cribed in detail.

16 As i~lustrated in Fig~ 2, each bus 35 comprises 17 sixteen individual bus data lines 57, five individual 18 bus pxo~ocol lines 59, and one clock line 61, and one 19 select line 63 fo:r each processor module 33.

21 As also illustrated in Fig. 2, the inter-22 processor control 55 of each processor module 33 includes 23 two inqueue sections 6~ (shown as an X inqueue section 24 and a Y inqueue section in Fig. 2) and a shared outqueue 25 section 67.

27 With the specific reference to Fig. 4, the 28shared outqueue section 67 includes an outqueue buffer 69 29which performs a storage function~ In a preferred form 3~the buffer 69 has sixteen words of sixteen bits each. The 1 buffer 69 is loaded by the CPU and holds the data until the 2 packet transmission time, at which time the data is gated 3 out to the bus, as ~ l be described in more detail below.

The outqueue section 67 also includes a receive 6 register 71, which in a preferred form of the invention ; 7 is a four bit register. This register is loaded by the 8 CPU with the number of the processor module to wnich the 9 data will be sent.
. 10 11 The control part of the outqueue section 67 12 includes a processor fill state logic section 73 which ~3 operates in synchronism with the CPU clock, a bus empty 14 s ate logic secti.on 75 which operates i~ synchronism with 15 the X or Y bus clock, and an outqueue counter 77. During 16 filling of the outqueue buffer 69 by the CPU, the out-17 queue counter 77 scans the buffer 69 to direct the data 18 input into each of the sixteen words o~ the buffer; and, 19 as the sixteenth word is stored into the outqueue buffer 20 69, the outqueue counter 77 terminates the fill state.
2~
22 ~he outqueue section 67 also includes an out-23 queue pointer 79 which connects the entire outqueue 24 section to either the X bus or the Y bus 35. The outqueue 25 pointer 79 allows the logic sections 73 and 7~ and the 26 buffer 69 to be shared by the X and Y interprocessor buses 35.

28 As illustrated in Fig. 3, the bus controller ~9 37 comprises a bus contlol state logic section 81, a 30 sender counter 83, processor select logic section 85, ~5 , ~, .

1 a recei~e register 87, a packet counter 89 and a bus 2 clock generator 91.

4 With reference to Fig. S,-each in~ueue section 5 65 comprises a bus fill state logic section 93 which 6 operates in synchronism with the bus clock, a sender 7 register 95, an inqueue buffer 97, an inqueue counter 99, 8 and a processor empty state logic sèction 101 which 9 operates in synchronism with the CPU clock.

11 FigO 6 is a state diagram of the bus contxol 12 logic 81 of the bus controller 37.

~3 14 ~ Fig. 7 is a state diagram of the logic sections 15 73 and 75 of the outqueue section 67.

~6 17 Fig.-8 is a state diagram of the logic sections 18 93 and 101 of the inqueue sections 65.

With reference to Fig. 7, the processor fill state 21 logic section 73 has basically four states--EMPTY, FILL, FULL

22 and WAIT--as indicated by the respective leyends. The bus 23 empty state logic.section 75 has basically four states--24 IDLE, SYNC, SEND and DONE -as illustrated by the lesends.

,: i .
. 26 Continuing with a description of the notation in 27 ~ig- 7, the solid lines with arrows indicate transitions 2g from the pre5ent state to the next state. Dashed arxows 29 ending on the solid arrows indicate conditions which must 30 be satisfied for the ind.icated transition to take place.

... .

l The synchronization of state machines running 2 off relatively asynchronous clocks require a careful 3 construction of an interlock system. ~hese important 4 interlocks are noted hy the dashed arrows in the state 5 diagxams. These interlocks perfo~ a synchronization 6 of two relatively asynchronous state machines. The .
7 dashed arrows in Fig. 7 and Fig. 8 running between the ~ state machines thus indicate signals which synchronize 9 (qual~fy) the indicated transistions of the state machines.

1i ,, . .

~ 25 . ~6 ~ 29 : 30 ' ~7 , ...
., ¢~

1 With reference to the FILL state fox the 2 logic section 73, it should be noted that the store 3 outqueue condition will not cause an exit ~rom the 4 FILL state until the outqueue counter 77 has advanced 5 to count 15 (on a count which starts with zero) 6 at which time the FILL state will advance to the FULL
7 state.

g Similarly, it should be noted that the SEND
10 state of the logic section 75 will not terminate on the select and send co~mand condition until thQ outqueue 12 countex 77 reaches count 15, at which time the SEND
. .
13 state advances to the DONE state.

14 ^

lS The asterisk in the notation o~ Fig. 7 16 indicates an increment of the outqueue counter 77.

18 Fig~ 6 shows the state diagram for logic 81 19 of the bus controller and illustrates that the logic 20 has b~sically four states--IDLE, POLL, RECEIVE and SEND.

22 The notation in Fig. 6 is the same as that 23 described a~ove for Fig. 7. A solid arrow line indicates 24 a state transition from one state to another and a 25 dotted arrow line to that solid arrow line indicates a 6 condition which must occur to allow the indicated .
~ 27 ~solid line arrow) transition to occur. An asterisk .
2g on a state transition in ~his case indicates that 29 sLmultaneously with the indicated transition the sender 30 counter 83 is incremented by one.

. .
~8 .
~ . ~
.,,,; .

l The dashed arro~ output lines in Fig. 6 2 indicate protocol commands issued from the bus 3 controller to the in~erprocessor bus.

Xn both Fig. 7 and Fig. 6 a dashed arrow 6 leaving a state indicakes a logic output from that 7 state such as a logic output signal to a protocol line (in the case of the bus empty state logic 75) or to a 9 status line or the processor module (in the case of the ~Q processor fill state logic 73~.

1~ .
l~ Fig. 8 shows the state diagrams for th2 bus ~3 fi1l state logic section 93 and the processor empty state 14 l~gic section lOl.
The state diagram for the logic section 93 ~ 17 includes four states--SYNC~ ACKNO~EDGE, RECEIVE and FUL~.

l9 The state diagram for the logic section lOl 20 includes our states~-RESET, READY, INTERRUPT and DUMP.

22 The notation ~solid line arrows and dashed line 23 ~rrows) is the same as described above for Fiy. 7 and ~iy. 6.
~ 24 j 25 The asterlsk in Fig. 8 indicates an increment ! 26 in the inqueue counter 39.

2~ Fig, 9 is a timing diagram showing the time 29 sequence in which the state changes given in Figs. 6, 7 30 and 8 occur.

.

1 The sequence shown in Fig. 9 accomplishes 2 the tran~mission of a pac~et from one processor module 3 to another processor module at the bus clock rate 4 (assuming that the intended receiver module is ready to S receive the packet).

7 Fig. 9 shows the time sequenses for a success-8 ful packet transfer with individual signal representations 9 listed from top-to-bottom in Fig. 9 and with time periods 0 Of one bus clock each shown ~rom left-to-right in the li order of increasing time in Fig. 9.

13 The top line in Fig. 9 indicates the state of 14 t~'e bus controller, and each division mark represents a lS clock period or cycle of the bus clock ~enerator 91 shown 16 in Fig. 3. Each time division of the top line carries 17 down vertically rhrough the various signal representations 18 listed by the legends at the left side o~ the figure.

~ ~,. . .
Taking the signals in the sequence presented 21 from top~to-bottom in Fig. 9, the first signal (below 22 the bus controller state line) is the SEND REQUEST signal 23 ~one of the protocol group indicate~ hy the reference 24 numeral 59 in Fig~ 3) and specifically is the signal 25 which may be asserted by the outqueue control logic 26 section 67 of any processox module 33. The signal is 7 transmitted to th~ bus control state logic section 81 2~ ~f the hUs controller 37 (see Fig. 3).

.

~ --~.

. ,~f ~, :
i'7~
1 The ne~t signal shown in Fig. 9 (the SELECT ~
2 signal) represents a signal which orlginates from the 3 processor select logic section 85 of the bus controller 4 37 and which is transmitted on only one at a time of the S select lines 63 to a related processor module 33.

7 The next signal represented in Fig. 9, the 8 SEND ACKNO~EDGE signal, may be asserted only by a particular processox 33 when that processor is selected and when its bus empty state logic section 75 is in he SE~D state (as illustrated in the- hird state of 12 Fig. 7). This SEND ACKNOWLEDGE signal is used by the 13 bus controller 37 to establish the identity of a processor 14 m~dule 33 wishing to send a packet.

16 The nex~ signal, the RECEIVE COMMA~D signal, repre-17 sents a signal from the bus controller 37 transmitted on one 18 of the protocol lines 59. This signal does two things.

First o all, this signal in combination with 21 receiver SELECT interrogates the receiver processor module 22 33 to find out whether this receiver module is ready to 23 receive (as indicated by the ACKNOWLEDGE state in Fig. 8).

Secondly, this signal has a secondary function 26 Of disabling the bus empty state logic section 75 of the 27 ~eceiving module so that the receiving module cannot gate 28 an intended receiver number to the data bus should the 29 out~ueue section of the intended xeceiver module 33 also 30 have a data packet of its own ready to send.

7~
1 In this regard, during the time that the 2 sender processor is asserting the SEND ACKrlO~LEDGE
3 signal it is also gating the receiver number to the ` 4 bus for use by the bus controller 37. The bus 35 S itself is, of course, a non-directional bus so that the 6 information can be gated to the data hus 57 by any module 7 for use by either the bus controller 37 for a control 8 function or for use by another processor for an information 9 transfer function.- It should be noted that a module 33 10 may gate data to the bus only when its SELECT line is 1~ asserted and the RECEIVE CO~ ND signal is~not asserted.

13 Duriny the time that the RECEIVE CO~AND signal 14 i~ asserted the bus controller 37 is yating the sender numbex to the data bus 57 for capture by the selected 16 receiver processor moduleO

18 The next signal line (the RECEIVE ACKNOWLEDGE
19 line in Fig. 9) represents a signal which is transmitted 20 from the 5elected receiving module's bus fill state logic - 21 section 93 to the bus contrsl state logic section 81 o~
22 the bus controller 37 (over one o the protocol lines 59) 23 to indicate that the selected receiver module is in the 24 AcKNowLEDGE state (as indicated by the legend in Fi~. 8) ,.~, ~ ~ 25 and thus ready to receive the packet which the sender .,~i .
26 module has ready to transmit.

`~ 28 If the RECEIVE ACXNOWLEDGE si~nal is not - 29 asserted by the receiver module, the sender SELECT, 30 the SEND COM~ ND and the time frame transmission of ~ 31 the data packet itself will not occur.

:, 5 . ~'-., ; , .

, . .

jt-~3 If the RECEIVE ACXNO~LEDGE signal is asserted, 2 then the sequence indicat~d by the SE~D COM~ND line 3 will occur.

S The- SEND CO~ND line represents a signal 6 whlch originates from the bus control state logic 7 section 81 of the bus controller 37 and which is trans-8 mitted to the bus empty state logic section 7S of the g sender processor module 33 over one of the protocol lines l~ 59.

~ In combination with a SELECT of the sender 13 processor module the SEND CO~AND signal enables the 14 se.der processor module to send a packet to the 15 receiver module during the six~een clock cycles bracketed by the SEND CO~ND signal.

18 The final line (the data/16 line~ represents 19the in~ormation present on the data lines 57 during the . .
~ 20above-described sequence.
r .
~ 21 ~ i .
- 2~ The data is gated to the bus by the selected sender i 23processor module and is transmitted to the receiver processor module into the inqueue buffer 97 ~see Fig. 5~
during this sixteen clock cycle time frame. This assumes ~r-;~ 26that the RECEIVE ACKNOWLEDGE signal was received by the bus controller in response to the RECEIVE COMMAND signal.

~3 :-"~.
... . .

r~ ! ~

.
1 If the RECEIVE ACXNOWL~DGE signal had not 2 been received by the bus controller, then the SEND
3 CO~ D signal would not have been asserted and the 4 bus controller 37 would have resumed the POLL state ~: 5 as shown in Fig. 6.

: 7 With re~erence to Figs. 2,. 7, 10 and 11, a 8 typical operation of the outqueue buffer and control 67 9 of one processor module 33 will now be described.
~Q
11 As illustrated in Fig. 10, the processor fill ~2 state~lo~ic sectiGn 73 includes two flip-flops A and B, ; ~ 13 and the bus empty state logic section 75 includes two 14 1ip-flops C and :D.
~5 ,~ . 16 Summarizing the state assignments as shown by "; ,~, .
~ 17 the AB and CD tables in Fig. 10, the EMPTY state is .;~, .
; - 18 defined as A = 0, B - Q. The FILL state is defined as ~ . 19 A = 1, B - 0. The FULL state is defined as A = 1, B = 1;
'~';
20 and the WAIT state is defined as A = t B = 1.

~:, 22 Similarly, the corresponding com~inations of 23 the C and D state variables are deined to be the IDLE, ~- 24 SYNC, SEND and DONE states res~ectively. State assign ..~; i . ¦ 25 ments previously listed could also be given in form of --, 26 logic equations. For example, EMPTY = A B, and this !
::~ 27 notation is utilized in the FigO 11 logic equation : 28 listings.
, -: . 30 ' :

.54 , . . .

1 In operation and with specific reference to 2 Fig. 7, the initial state reached through power on 3 initialization or manual reset is the EMPTY state shown 4 in the top left part cf Fig. 7.

6 The EMPTY state of the processor fill state 7 logic 73 provides a ready signal to the central processor 8 unit (CPU) 105 to indicate the presence of that state, 9 as indicated by the dashed arrow RDY shown as leaving 10 the empty state in Fig. 7.
. . _ '~ :L ' 12 ~he CPU firmware (microprogr~m) in response to 13 that ready signal, when a transmission over the inter-14 processor bus is required, will provide a store recei~e 15 signal (shown by the dashed arrow incoming to the diagram 1~ in Fig. 7). This store receive signal qualifies (synchronizes) the 17 transitlon which advances the EMPTY state to the FILL
18 state.

The CPU firmware, to transer data into the 21 outqueue buffer 69, will provide a store outqueue signal 22 ~the dashed arrow entering the diagram in Fig. 7~ for .. . .
?~! 23 each word to be stored in the buffer 69.
j 2~
.. ~ .
Each occurrence o this store outqueue signal .~,. . .
26 wil~ advance the outqueue co1~nter 77, commencing with a 27 count of zero, until a count of 15 is reached.

29 On the sixteenth occurrence of the store out-30 queue signal a transition rom the FILL to the FULL state, ^ 55 1 as illustrated by the solid line arrow in Fig. 7, is 2 allowed.

4 The FULL state of the processor F'ILL state logic 5 provides a synchronization condition to the bus empty state 6 logic denoted by the dashed arrow leaving the EULL state 7 of lo~ic 73 and going down to the logic 75 in Fig~ 7.

g .9 The processor fill state logic 73 will remain 10 in the FULL state until the bus empty state logic 75 11 has subsequently reached the DONE stateO
... 12 13 Now, referring speciflcally to the bus empty . 14 st~te logic denoted by 75 in Fig. 7, the initial state, 15 IDLE~ for the logic section 75 in Fig. 7 is again pro-16 vided by power on initialization or manual reset.
` i 17 .18 The bus empty state logic 75 will remain in 19 the IDLE state until the transistion to the SYNC state is 20 allowed as shown by the dashed arrow from the FU~L state ~1 Of the processor fill 73.
., -22 - 23 The empty state logic 75 will proceed with no .~' ,24 qualification requirea from the SYNC state to the SEND
-~25 state. -. ~ .
~1 26 .
: :27 It is in the SEND state that the SEND REQUEST

~8 signal to the bus and to the bus controller is asserted ~9 (as indicated by the dashed arrow going down and leaving 30 the diagram 75 from the SEND state).

.
5~ .

1 In response to this SEND REQUEST signal, the 2 bus controller logic 81 (Fig. 6) will poll processor 3 modules successively until the sender is identlfied 4 tas discussed earlier with reference to Fig. 9).

s ~ The bus controller will issue a RECEIVE CO~AND
7 and SELECT to the intended receiver.processor module; and 8 upon receipt.of the RECF~IVE ACKNOWLEDGE signal will proceed 9 to the packet time frame (also identified in Fig. 9).

11 During the packet time frame the bus controller 12 asserts SELECT of the sender processox module and also 13 asserts the SEND COMMAND signal to the sender processor module.
1~
This SELECT signal and SEND COM~ND signal is 16 shown as entering the diagram and qualifying (synchronizing) 17 transltions leaving and entering the SEND state as noted 18 in Fig~ 7.

Each bus clock while SELECT and SEND COL~AND
21 are asserted will advance the outqueue counter 77 commenc-22 ing with a count of zero.
~3 24 On the sixteenth clock period of SELECT and SEND
25 COMMAND the transition terminating the SEND state and ad~
2~ vancing to the DONE state is qualified (synchronized as 27 shown by the dashed arrow allowing that transition).

29 When the empty state logic 75 has reached the 30 DONE state, a transition of the processor fill state logic ~\ ~

73 from FUI,L to ~IT is qualified (as denoted ~y the 2 dashed arrow leaving the done state~.

4 Next, the ~AIT state of the processor fill 5 state logic 73 qualifies a transition of the bus empty 6 state logic 75 from the DONE state to the IDLE state 7 (as denoted by a dashed arrow lea~ing the WAIT state and 8 qualifying the indicated transition~.

Yinally, the bus empty state logic 75, being in ~ the IDLE state, qualifies the transition of-the processor 12 fill state logic 73 from the W~IT state to the EMPTY state 13 (as denoted by the dashed arrow leaving the IDLE state).
1~
At this point a packet has been loaded into the 16 ou queue bufer 69 by the processor module and transmitted 17 over the bus 35 to the receiver processor module, and the 18 outqueue control processor fill state logic 73 and bus 19 empty state logic 75 ha~e returned to their initial states.

21 The above description relates to the transitions 22 and qualifications indicated in Fig. 7O The action of .~ .
23 the logic sections 73 and 75 involved in the above 24 description of operation of Fig. 7 will now be noted 25 with reference to the logic diagram of Fig. 10 and the 26 logic equation listi~g of Fig. ll.

~7 2~ With ~eference to Fig. 10, as noted above, the 29 flip-flops A and B are JX flip-Flops and are edge 30 triggered flip-flops in that state changes occur only 58 _~

. . .

. ~

1 on clock transitions (as indicated by the small triangular 2 symbols and legends on the lefthand sides of the flip-flops 3 A and B in Fig. 10).
S The primary significance of the logic 6 diagram in Fig. 10 is to ~llustrate the transition from 7 one state to ancther in the state machines shown in 8 Fig. 7. Thus, to illustrate the transition from IDLE
9 to SY~C in the empty state logic 75, the operation j 10 proceeds as fol~ows.
'11 12 To implement a change rom the IDLE state 13 to the SYNC state, the state variable C must be set.
1~ .
; j 15 ~he log:ic equation for the J input of state . j 16 variable C is as shown in Fig. 11 and is indicated by _ ~ 17 the reference numeral 103. In this equation the inter~
.
. 18 lock tshown by the dashed arrow from the full state of 19 the fill state logic 73 in Fig~ 7 to the transition) .~; 20 corresponds to the quantity ~A B) or ~FULL) in the ~ 21 equation .indicated by the reference number 103. The D
~,.. . .
22 or (IDLE) in the eguation indicated by reference numeral 23 103 in Fig. 11 corresponds to the IDLE state sho~n by the ~:¦ 24 legend in Fig. 7. ~he J in the equation corresponds to 25 the J input of the C flip-flop in Fig. 10. And the (C) :1 26 corresponds to the true output of the C flip-~lop in , 27 Fig. 10.
.. . .
' 2~ .

~9 Other state transltions of the Fig. 7 30 diagram will not be described in further detail with .: . .,~.
~ ~

~" ~

1 xeference to FigsO 10 and 11 since it lS ~elieved 2 that these transitions as carried out hy the logic 3 diagram in Fig. 10 and the logic equations in Fig. 11 ~re clear from the above examples of the transit}on from 5 IDLE state to SYNC state as described in detail above.
7 Figs. 10 and 11 show the logic diagram and 8 logic equations for the state diagram of the outqueue 9 buffer and control 670 Corresponding logic diagrams and logic equations have not been illustrated for the -~I inqueue buffer and control 65 or the bus controller 12 37 because such logic diagrams and equations are similar 13 to those shown in Fig. 10 and Fig. 11 and are easily 14 ohtainable from the state diagrams shown in Figs. 6 and 8.
~5 16 Each processor module 33 ~Fig. l) in the multi-17 processor system is connected to both interprocessor buses 18 35 (Fig: 1) and is capable of communicating with any pro-19 cessor module including itself over either bus. For each , . .
; 20 block data transfer, one processor module is the source ~- 21 or sender and another is the destination or receiver.
~2 23 Transmission of data by a processor module ç 2~ over one of the interprocessor buses is initia-~ed and ~- ~5 accomplish~d under software control by means of the SEND
.~,,,,: .
26 instructiono 28 In the SEND instruction the microprogram 115 29 tFig. 2j and the CPU microprocessor 113 (Fig. 2) interacts 30 with the shared outqueue section 67 of the lnterprocessor ., .

~` ~

1 control 55 to read a da~a block from memory 101, to break 2 it up into packets, tG calculate packet check sum words, 3 and to transmit the block one packet at a time over a 4 bus to the receiving processor module. Parameters supplied to the SEND instruction specify the number of 6 words in the block, the starting address of the block, i 7 which bus to use, the destination processor, and a 8 maximum initial timeout value to wait for the outqueue 9 67 (Fig. 2) to become available.

The SEND instruction terminates anly after the ~2 entire block has been transmitted; thus sending a block 13 is a single event rom the software viewpoint. However, 1~ t:e SEND instruction is interruptable and resumable, so that response Oc the operating system to other events is 16 not impaired by t:he length of the tim~ required to 17 complete a SEND instruction.

19 Recei~ing of data by a processor module over the interprocessor buses is not done by means of a soft-21 ware instruc~ion, since the arri~al times and sources . "
~ 22 of data packets cannot be predicted. The receiving of .
b 23 data is enabled but cannot be initiated ~ the receiver.
,~ 24 The CPU microprocessor 113 takes time out from 26 software instruction processing as required to execute 27 the BUS RECEIVE microprogram 115. This microprogram ~8 takes the received data packet from one of the inqueue 29 sections 65 (Fig. 2) o~ the interprocessor control 55, stores the data into a memory buffer, and verifies correct 31 packet check sum.

.,:. ~1 1 Reassembly of rec~ived packets into blocks ~ 2 is accomplished using the Bus Receive Table 150 (~RT) i 3 in memory. The ~RT contains 32 two-word entries, corres-4 ponding to the two ~uses îrom each of the sixteen pro-cessor modules possi~le in one specific implementation 6 of the multiprocessor system. Each BRT entry corres-7 ponding to a bus and a sender contains an address word and a count word. The addxess word specifies into which 9 buffer in the System Data are~ încoming data from that sender is to be stored. The eount word specifies how many li data words remain to complete the block transfer ~rom 12 that sender.

14 - As each data packet is received, the CPU micro-~ 15 processor 113 suspends processing of software instructions, s~ 16 and the bus receive microprogram 115 is activated. This 17 microprogram reads the address and count woxds from the 1~ sender's BRT entry, stores the data packet into the g specified area, verifies correct packet check sum, and 20 restores adjusted values of the address and count words 21 into the BRT entry. If the packet caused the eount to 22 reach zero or if the packet contained incorrect check sum, 23 the bus receive mieroprogram sets a completion interrupt ~4 flag to signal termination of the data block to the soft-2~ ware. The CPU microprogram then resumes software - 26 instruction proeessing at the point where it left off 27 with no disturbance except delay to the currently executing 28 program.

. 62 .

;13 ~I D ~

1 It is an important feature that data blocks -2 from several senders can all be assem~led concurrently 3 by a receivins processor module from data packets received 4 in any sequence. This interleaved assembly of blocks 5 from packets is carried on transparently to the soft-~ ware executing in the receiver processor. Only success-7 ul block completions or erroneous transmissions cause the 8 software to be interrupted.
g It is also important that a time sharing or -time-slicing of the interprocessor bus hardware has been ~2 achieved in two areas.

14 ^ First, each interprocessor bus and associated bus controller allow packets to be transmitted between -- 16 any sender and receiver as required~ The circular polling c 17 by a bus controller to identify a requesting sender 18 ensures that all processor modules have an equal opportunity g to send over that bus. Each bus provides a communication 2Q path which is shared in time in an unblased way by all 2L processor modules.
X~ -Secondly, each inqueue section 65 of the inter-processor control 55 of a processor module is shared in time by incoming packets from several senders. That is, 26 the inqueue logic and storage of a processor is not dedicated to a single sender for the duration of a block ~B transfer. Ins.ead, each packet received is correctly ~g directed into memory by the BRT entry corresponding to its sender and bus. Data blocks from several senders ~e ~1 1 are assembled correctly in the receiver's memory 2 independently of the order in which the send~rs make 3 use of the bus.

A processor module has two ways of controlling 6 its ability to receive packets over the X bus or the Y bus.

8 First, there is a bit in the CPV's intexrupt 9 MASK register corresponding to each interprocessor ~us.
10 When the ~SK bit is on, micro-interrupts for that bus ll are allowed. Micro-interrupts (activation of the BUS
1~ RECEIVE microprogram) occur when the Processor Empty 13 state logic lOl (Fig. 5) of an inqueue section 65 reaches 14 the MICRO-INT state after a packet has been received into an inqueue buffer. If the MASX bit is off when a 16 packet is received, the micro-interrupt and subsequent 17 processing of the packet into memory will be deferred 18 until the MASK bit is set on by a software instruction.

Software operations such as changing a BRT
21 entry are performed with micro-interrupts disabled to 22 avoid unpredictable results. No packets are lost wh:ile 23 micro interrupts are disabled. The first packet received 24 will be held in the inqueue buffer until the micro-interrupt is enabled. Subsequent packet transfers while 26 the inqueue buffer is full are rejected since the Bus ;
27 Fill state 93 logic will be in the FULL state and thus 28 unable to assert RECEIVE ACKNOWLEDGE in response to 29 SELEcT.

. .

~4 , 1 A second means of controlling its ability to 2 receive packets over the bus is the ~ction taken by a 3 processor module after an X bus or Y bus receive . 4 completion interrupt (activation of an operatlng system - ~ interrupt handler).

7 . When a check sum error is detected in a received 8 pac.ket or when the BRT word count remaining in a data g block reaches zero as a packet is stored into memory, the BUS RECEIVE microprogram sets the X bus or Y bus 11 completion interrupt flag. Otherwise, the mi.croprogram ; 12 issues the RINT signal (see Fig~ 8) to the inqueue 13 Processor Empty state logic 101 to allow another packet 14 t.o be recelved. When the completion flag is set, however, -' 15 the RINT signal is not issuedO
.' 16 ~1 17 It is thus the responsibility of the bus receive ,- 18 completion software interrupt handler to issue the RINT
19 signal ~by rneans of an RIR software instruction) to reenable the inqueue 65. Until this occurs, the inqueue Bus Fill 21 state logic 93 remains in the FULL state and no additional 22 packets will be received.
.i ~:~ 23 24 The completion interrupt signal can therefore 25 designate either a block data transfer tha. has been.sent 26 and received without error, or it can designate a partial 27 transfer in which a check sum error is detected, and in 28 which partial transfer of the completion interrupt is ~9 generated as a result of the check sum error detected.
30 In the latter case, the sender continues to send the data .,.q ~` ~

'7~

1 block but the receiver discards the data bloc~ after the 2 check sum error h~s been detected. This error shows up 3 in the bus receive table (BRT) count word as a negative 4 value. This will become more apparent from the description of the operation which follows.

7 The SEND instruction is an instruction that 8 requires four parameter words in the CPU register stack.

The first of the four parameter words is a 11 count of the number of words to be transEerred. This value 12 must match the number expected by the BRT in the receiver 13 processor module if the transfer is to complete success-14 f-lllly.

16 The second parameter word is the address, minus I7 one, in the System Data area in the sender processor's 18 memory where the data to be transferred is located.
.
~- . i9 , . ' ~he third parameter word is a timeout value 21 allotted to completing a single packet (fifteen data word) 22 transer. The timeout period is restarted for each packet 23 transferred by the SEND instruction.
.~.

~ 24 . j ' ~ 25 The fourth parameter word specifies the bus ~26 (whether the X bus or the Y bus) to be used and specifies ^- 27 the receiver processor module. The high order bit of the ~ 28 parameter specifies the bus and the low order four bits, --2g in one specific implementation of the invention, specify 30 the number of the receiver processor module.
... . .

/
~- 1 (- ~
``

1 At the completion of a SEND instruction, there 2 are two possible conditions.

The first condition is that a packet timeout occurred and the remaining packets were not transmitted 6 and the instruction was terminated at that pointO In 7 this event the remaining packets of the block are not 8 transmitted.

~0 The second condition is an indication tha~ a 1~ successful data block transfer has been completed.

`` ~2 13 Thus, in initial summary o~ the SEND operation, .
~4 the SE~D instruction fills the outqueue buffer 69 (Fig. 4) 15 with fifteen data words, appends an odd-parity check sum, 16 and signals the bus controller 37 that it has a packet 17 ready for transmissionO After each sixteen word packet 1~ is tran~mitted, execution of the SEND instruction resumes 19 at the point where it left off. If thP last packet of 20 the block has less than fifteen words, the remaining words 21 are filled in with zeros. The instruction texminates when ~2 the last packet is transmitted.

i ~
i ~4 Fig. 5 shows the logic diagram and Fig. 7 shows 25 the state diagram for the send hardware.

27 The first action o the SEND instruction 2~ sequence is to issue the S/RECEIVE signal to the processor ~ fill state logic 73 (Fig. 4) and to supply on the M Bus 30 (Fig, 4) the receiver processor number to the receive .

1 register 71. Simultaneously, the pointer o~ the outqueue 2 ~ointer 79 is set in acccrdance with the high order bit 3 of the rs Bus to connect the outqueue 67 to eithex the X
4 bus or the Y bus.

6 The store receive (S/RECEIVE) signal causes the 7 processor fill state logic 73 (which is initially in the 8 empty state as shown in Fig. 7~ to advance to the FILL
~ state as shown in Fig. 7. This state transition causes the receive register 71 (Fig. 4) to be loaded with the 11 receiver processor number.

13 At this point the outqueue section 67 is xeady 14 f,r the data pacXet to be loaded into the outqueue buffer 69. Now, up to fifteen words are read from memory and 16 are stored, by means of the M bus (Fig. 4), into the out-17 queue buffer 69. The store outqueue signal causes each 18 word on the M bus to be written into the outqueue buff~r 19 69 in a location specified by the outqueue counter 77.
2~ Each store outqueue signal also causes the outqueue counter 21 77 to be advanced by one.
..:;
~ 22 .: .
23 As the words are being read from memory, the Z4 address~word is being incremented by one, and the count Of the words to be sent is being decremented by sne.

~6 If the count reaches zero before fifteen words are read 27 from memory, the remainder of the outqueue buffer is 28 filled with zeros io pad out the data packet.

' ~ 68 i~;i ;' ' '1 .

~'L~
, 1 In addition, as the ~ords are b~ing loaded into 2 the outqueue buffer 69, the microprogram 115 (Fig. 2) is 3 calculating a modulo-two sum of the data words. After 4 the fifteenth data word h2s been loaced, this odd check-5 sum word is loaded into the ~i~teenth location of the 6 outqueue buffer 69.

8 At this time the outqueue counter 77 has a value 9 of count 15 and this value, in combination with the store outqueue signal, causes the processor flll state logic 73 to advance from the FILL state to the FULL state as shown 12 in Fig, 7.

14 - At this point the microprogram 115 has completed '15 loading of the data into the outqueue 69. The microprogram 16 now waits for the packet to be transmitted by testing for 17 occur.rence of the ready (RDY) signal shown in Fig. 7.

19 While waiting for the packet to be transmitted, the microprogram 115 increments a timeri and if the timer . . .
''',b' 21 runs out or expires before the ready (RDY) signal is ~'~ 22 'asserted, the microprogram issues the clear outqueue ~Y i 23 ~CLOQ) signal to the processor fill state logic 73 (see .~ 24 Fig. 4). This causes the processor fill state logic 73 ~-' 25 to return to the empty state as shown in FigO 7, and the ....
~`' 26 microprogram then terminates the SEND instruction with '~'' 27 the time out indication.

',, 28 ' 2g In normal operation, the FULL state of the ,.,, 30 processor fill state logic 73 qualifies the bus emp,ty ":~.'.f'.',,l . ' 6af j,.,~
-~

l state lo~ic 75 to advance from the IDLE state to the SYNC
2 state shown in Fig. 7. Ne~t, the SYNC state automatically 3 advances to the S~ state, a~d this state causes the 4 SEND REQUEST signal to be issued to the ~us controller 37.
The SEND REQUEST si~nal initiates a pac~et transfer 6 sequence described earlier.

8 As described earlier, when the sender processor 9 module has ~een identified by the bus controller 37 by 10 polling, and when the receiver processor module has -11 accepted the packet trans~er by means of t~e RECEIVE
12 ACKNO~LEDGE signal, the data packet is gated from the ~3 outqueue buffer 69 through the outqueue pointer 79 to 14 o~e of the data buses 57 for loading into the inqueue of 15 the receiver processor module.

17 As the si~teenth word is gated to the bus, the 18 value of the outqueue counter count 15, in combination with 19 the SEND COL~AND signal and the SENDER SELECT signal causes 20 the SEND state of the bus empty state logic 75 to advance 21 to the DONE state.

~3 The DONE state qualifies the FULL state of the 24 processor ill state logic 73 (as shown by the dashed line 25 arrow going from the DONE state to the indicated transition 2~ from the FULL state in Fig. 7) to advance to the WAIT state.

28 Next, the WAIT state qualifies the DONE state 29 to advance to the IDLE state as illustrated by the state 30 diagram in Fig. 7.

Final.ly, the IDLE state qualifies the ~AIT state 2 to advance to the E~IPTY state as also indicated in the 3 state diagram of Fig. 7.

. 4 S The EMPTY state, of the processor fill state 6 logic 73, provides the READY indication to the micro-.7 program 115.

?'~
g If the yacket just transmitted was the last 10 packet in the specifled data block, the SEND instruction i is terminated and the successful block transfer indication 12 is given.

14 ^ If the packet transmitted is not the last packet in a.data block, then the sequence described above 16 is repeated until all ~ords in the block have been trans-17 mitted, or un~il a timeout error has occurred.
. 18 19 The SEND instruction is interruptable and 20 resumable; however, the SEND instruction is only interrupt-i ~1 able between packets; and the interruption of the SEND
. ~,.
~?~ 22 instruction has.no effect on the data transmitted.

i ;,.
24 Thus, by means of a single software instruction ~the SEND instruction) a data block of up to 3 ,767 words ~- . 2~ is transmittable from a sender processor module to a : 27 receiver processor module, and accuracy of the transmission . 28 is checked by the packet check-sum. Also, the trans-... . .
29 mission occurs at a high data transfPr rate, because 30 the buffering provided by the outqueue buffer 69 of the , . 71 , ... . .

\

1 sender processor module enables the transfer to be made 2 at interprocessor bus speed independent of the memory 3 speed of the sender processor module. This allows efficient 4 use of this communication path between a number of pro-5 cessor modules on a time slicing basis.

7 As noted above, there is no instruction for 8 rèceive.

0 For a processor module to receive data over 11 an interprocessor bus, the operating system in that pro-12 cessor module must first configure an entry in the bus 13 receive table (BRT). Each BRT entry contains the address 14 wk~re the incoming data is stored and the number of lS words expected.

17 While the sender processor module is executing 18 the send instruction and sending data over the bus, the 19 bus receive hardwaxe and the microprogram 115 in the 20 receiver processor module are storing the data away 21 according to the appropriate BRT entry (this occurs inter-22 leaved with software program execution).

24 When the receiver processor module receives 25 the expected number of words from a given sender, the 26 currently executing pro~ram is interrupted, and that ~7 particular bus transfer is completed.

29 Fig. 5 shows the logic diagram and Fig. 8 shows 30 the state diagram for the bus receive hardware.

. .

.. . . . .

1 As previously pointed ou~, there are identical 2 X and Y inqueue sections 65 in each processor module for the 3 X bus and the Y bus. Only one of the inqu2ue sections : 4 will therefore be referred to the description which follo~ls.

~ .
6 After initial reset of a processor module, or 7 after a previous receive operation, the RESET state of the 8 processor empty state logic 101 advances to the READY
9 state. The READY state qualifies the SYNC state of the bus 10 fill state logic 93 to advance the logic to t~e ACKNOW~EDGE
1~ state.

3 In this ACKNO~EDGE state the inqueue section 65 4 rPturns RECEIVE ACKNOWLEDGE to the bus controller 37 in ~5 response to a SELECT 63 (see Fig. 2) or that processor 16 module 33. This indicates the readiness of the X inqueue 17 section 65 to receive the data packet.
18 .
~9 In the packet transfer sequence (described in 20 detai~ above) the combination of the SELECT of that 21 processor module and the RECEIVE COMMAN~ signal yualify 22 the ACKNOWLEDGE state of the bus ~ill state logic 93 and ~i .
23 to advance to the RECEIVE state~

~'~r', 25 Ak this state transition the sender register 95 .
~ ~ 26 (Fi~. 5~ is loaded with the number of the sending processor - 27 mOdule.

29 In khe RECEIVE state the data packet is loaded :~ .
30 from the data bus to the inqueue buffer 97 under control 31 of the inqueue counter 99.

, _~

1 As the sixteenth ~ord of the pac]e-t is loaded, 2 it causes the R~CEIVE state to ad~ance to the ~ULL state 3 (see Fig. 8).

Now the FUI.L sta~e qualifies the RE~DY st~te 6 of the processor empty state logic 101 to advance to 7 the MICROI~TERR~PT state as shown ln Eig. 8. The MICRO-8 INTERRUPT state presents an INQ~EUE FULL state to the 9 CPU interrupt logic. This INQUEUE FULL signal causes a 10 microinterrupt to occur at the end of the next software 11 instruction if the ~L~Sx bit corresponding to that bus is on.

13 The bus receive microprogram 115 activated 14 b~ the interrupt first of all issues a LOCK signal (see 15 Fi~. 5) to the processor empty state logic 101. This 16 causes the MICROI2JTERR~PT state of th2 processo- empty 17 state logic 101 to advance to the DUMP state.
1~
9 The LOCK signal also selects either the X
20 inqueue or the Y inqueue; subject, however, to the 21 condition if both inqueues are full and enabled, the X
22 queue is selected.

.~ .

24 Next, the microprogram 115 issues the K~SEND

25 signal which causes the sender register 95 c~ntents to be 26 gated to the K bus (as shown in Fig . 5 ) to obtain the 27 packet sender's processor number.

29 Using this processor number, the microprogram 30 115 reads the sender processor's BRT entry to obtain the 31 address and count words~

!

~-1 If the count word is zero or negative, the 2 packet is discarded; and in this case, the microprogram 3 llS issues a RINT signal which causes the processor 4 empty state logic 101 to advance from the DU~5P state to S the RESET state as shown in ~ig. 80 In this event there 6 is no further action. The microinterrupt is terminated, 7 and software instruction processing is resumed.

g If the count is positive, the microprogram 115 10 xeads words from the inqueue buffer 97 to the K bus by 11 means of the K/INQUEUE signal as shown in Fig. 5.

13 With each occurrence of the K/INQUEUE signal, 14 t~e inqueue counter 99 is incremented to scan through the 15 inqu~ue buffer 97 17 As each data word is read from the inqueue , ~ ~
18 buffer 97, the count word is decremented, the memory 19 address word is incremented, and the data word is stored il~?~l 20 into memory.
~, ,. . ~
3', ~1 ..' .
22 If the count word reaches ~ero, no more words 23 are stored in memory, a completion interrupt ~lag is set, 24 and the sender processor number is saved in a memory 25 location. In that event the fill state bus logic 93 stays ~ 6 in the FULL state until cleared by a software RIR instruction.

", .
28 Thus, when a data block has been completely 29 received, the count word will contain a value between minus -30 14 and zero. A~ter the completion interrupt occurs, no .. .

., ~ 75 .
. , 1 further tran_fers to the processor over the bus which 2 cause the interrupt are permitted until the inqueue is 3 cleared with an RIR instructio~.
4 ~
As the data words are s~ored into the memory, 6 a mo~ulo-two sum of packet data is calculated.

8 If the check sum is bad, the word count in the g BRT entxy is set to minus 256, a completion interrupt flag 10 is set, and the sender processor number is saved in memory.
11 As above, the bus rill state logic 93 stays in the FULL
1~ state until cleared by an ~IR instruction~

1~ ~ If the count word does not reach zero, and the check sum is good, the bus recelve microprogram 115 issues 16 the RINT signal to the processor empty state logic as shown 17 in Fig. 5 which causes the DUMP state of the processor 18 empty state logic 101 to advance to the RESET state as 19 shown in Fig. 8.
2~
21 The RESET state of the logic 101 quali~ies the 22 bus fill state logic 93 to advance from the FULL state to 23 the SYNC state as also shown in Fig. 8.

At this point, the logic has been returned to Z6 the state it was in before the packet was recei~ed, thus 27 enabling the receipt of more packets.

~9 ~6 1 These packets may be from the same sender, 2 completing that data block, or the pack~s may be from 3 some other sender.

~hls completes the action of the bus receive 6 microprogram 115 and the microprocessor 113 resumes pro-7 cessing of so~tware instructions.

.
~ When a bus receive completlon interrupt has 1~ occurred, the sof~ware interrupt handler obtains the sender 11 processor number from the memory location where that number was saved, and the soft~are interrupt handler can then ~3 detect if a check sum error occurred by examining that 14 sender processor's bus receive table count word.

16 In the case of a transmission error, the count 17 word has been set to minus 256. Otherwise, the count word ` 18 will contain a value between minus fourteen and zero.

2Q As mentioned above, it is thus the responsibility 21 Of the bus receive completion software interrupt handler 22 to issue the RINT signal (by means of an RIR software 23 instruction) to reenable the inqueue 65.

i 24 In summary on the receive operation, just as 2~ the sending of a data block by a sender processor module 27 is viewed by software as a single event, the receiving of ~8 data by a receiver processor does not cause a sof-tware 2g interrupt of the receiver processor module until the 30 entire data block has been received or until an error has , ' .

,, .

1 has occurred. Also, the inqueues 65 serve as buffers to 2 allow the transmission of data to occur at bus transmission 3 rates while allowing the storing of data into ~,emory and 4 the checking of the data to occur at memor~ speed. This 5 ability to use the high transmission rate on the bus insures 6 adequate bus ba~dwidth to service a number of processor modules 7 on a time slicing basis. Finally, ~he provision of a check - ~ sum word in each data pac~et provides a means in the receiver ~ processor module for checking the accuracy of the data 10 received over the multiprocessor communication path.
11 ~ .
~2 Information sent over the interprocessor bus is 13 sent under the control of the operating system and is sent 14 from one process in one processor module 33 to another pro~
15 cess in another processor module 33~ A process ~as described 1~ in detail above in the description of the Mult~processor - 17 System) is a fundc~ental entity of control in the software 8 system; and a number of processes coexist in a processor - 19 module 33. The information sent over the interprocessor bus 20 between processes in different processor modules consists 21 of two types of elements, control packets and data.

¦ 23 The control packets are used to in~orm the 24 receiving processor module 33 about message initiations, j ~5 cancellations, and data transfers.

27 In this regard it should be noted that, while 2~ the interprocessor ~uses 35 interconnect the processor 29 modules 33, a process within a particular processor 30 module 33 communicates with another process or with 31 other processes within another processor module 33 through 32 a method o~ multiple~ing the interproc~ssor bus 3S. The 1 bus traf~ic ~etween t-"o processor modules 33 will there-2 ore contain pieces of interprocess cc~munications 3 that are in ~arious states of completion. ~any inter-4 process communications are therefore ~eing interleaved 5 on an appaxently simu~taneous basis.

7 The hardware is time slicing the use of the 8 intexprocessor bus 35 on a packet level, and multiple 9 processes are intercommunicating both within the pro-10 cessor modules 33 and to the extent necessary over the -11 interprocessor buses 35 in message ~ransactions which 12 occur interleaved with each other. Under no circumstances 13 is an interprocessor bus 35 allocated to any specific 14 pr~cess-to-process co~munication.
16 Data information is sent over the interprocessor 17 bus in one or more pac]cets and is always preceded ~y a ~8 control packet and is always followed by a trailer packet.

The control packet preceding the data packets ~, .
- 21 is needed because a bus is never dedicated to a specific ~ .
~` 22 message, and the control packet is there~ore needed to 23 correctly identify the message and to indicate how much -1~ 24 data is to be recei~ed in the message.
~5 ^ l 26 This information transfer (control packet, data '~:. .I
! 27 information, trailer packet) is made as an indivisible 28 unit once it is started~ The sender processox module 2g sends ~he data block as an individual transmission ~con-30 sistin~ of some number of data packets) and sends the :, .

7~

1 trailer pac~et as an individual transmission; and only 2 khen is the sender processor module able to send 3 information relati~g to another messa~e.

S ~he trailer packet serves two purpose~.

7 First of all, if there is an error during a data 8 txansmission (and therefore the rest of the data block must Il 9 be discarded), the trailer packet indicates the end of ¦ 10 the block.
~}.
12 Secondlyl if the sender attempts to send too 13 much data (and again the block must be discarded), the 14 trailer packet provides a means for recognizing data has 15 been transmitted and the data transmission has completed.

"`~I 1~ The information transmitted is either duplicated ` ' 18 over different paths ~so that it is insured that the ~9 information will get to the receiver) or a receiver acknowledg-20 ment is required (so that the information is repeated .if 21 necessary). Any single bus error therefore cannot cause 22 information to be lost, and any single bus error will not . ., ~ . . .
~,, 23 be seen by the two processes involved.
~! 24 ' 25 The bus receive software interlocks with the ~;1 26 ~us receive hardware (the inqueue section 65 shown in -~ 27 Fig. 2) by controlling the transfer of information from . 28 the inqueue into the memory 107.

, _,, .,~ .
."

1 This allows such op~rations as changing the 2 bus xeceive table information to be done without race 3 conditions 5synchronization problems).

Cnce the bus receive table information has 6 been updated, the interlock is removed by clearing the 7 previous completion interrupt and by reenabling the 8 bus receive microinterrupts b~ se~ting on the bus mask 9 bit in the mask register.

11 This does two things. It allows the inqueue 12 hardwa-re to accept a packet into the inqueue, and it also 13 e~ables the bus receive microprcgram to transfer that 14 information from the inqueue into memory.

16 The hardware/software system is so constructed ~ `................... ..
17 that no information is lost on a system power failure (such - 18 as a complete failure of AC power from the mains) or on a 19 line transient that causes a momentary power failure for ! ~ 20 part of the system.
~v 21 ~2 This hardware/software system coaction includes 23 a power warn signal tsee line 337 of Fig. 3) supplied to 24 the inqueue section 65 (see Fig. 2) so that, at most, one 25 further packet of information can be loaded into the in-26 queue after the receipt of the power warn signal.

28 The software action in this event includes a 29 SEND instruction ~o force the inqueues to be full. The 30 net ef~ect is to insure that no transmissions are completed . 81 .

,, ti~

l after the processor module 33 has received its power 2 warn signal, so that the state of every transfer is 3 Xnown when logic power is removed.
The interprocessor buses 35 are used b~ the 6 operating system to ascertain that other processor 7 modules in the system are operating. Every N seconds, 8 each of the processor modules 33 sends a control packet 9 to each processor module 33 in the system on each 10 interprocessor bus 35. Every two N seconds, each pro-Il cessor module 33 must have received such a packet from 12 each processor module 33 in the sys~em. A processor 13 module that does not respond is considered down. If a 14 processor module does not get its own message, then that 15 processor module 33 knows that something is wrong with 16 it, and it will no longer take over I/O device controllers 17 41.

. j 19 Fig. 42 diagrammatically illustrates how a 20 particular applica~ion program can run continuously even 21 though various parts of the multiprocessor system can : ,22 become inoperative.
~ 23 -~ ;24 ~Each of the separate views shown in FigO 42 .. . .
-~ 25 illustrates a multiprocessor system configuration which , 26 consists o~ two processor modules 33 connected by dual - - 27 interprocessor buses 35 ~indica~ed as an X hus and a Y bus~, ~- 28 a device controller 41 which controls a number of keyboard ` 29 terminals, and another device controller 41 which controls ;- ~30 a disc.

, ~ . .

1 The individual views of Fig. 42 indicate various 2 parts of the multiprocessor system re~dered unserviceable 3 and then reintroduced into the multiprocessor syst~m in a serviceable state.

6 The se~u~nce starts with the upper left hand 7 view and then proceeds in the order indicated by the broad line arrows between the views. The sequence thus g goes from the condition indicated as (1) Initial State 10 to (2) CPU 0 Down to (3) CPU 0 Restored to (4~ CPU 1 Down 11 to (5) CPU 1 Restored (as indicated by the legends above 12 each individual view).

14 In the initial state of the multiprocessor system ~5 shown in the view entitled "Initial State" at the upper 16 left hand corner of Fig. 42, one copy (PA) of the application 17 program is active. This copy makes a system call to create 18 the copy PB as a backup to whi~h the application program 19 PA then passes information. All of the I/0 is taking 20 placè by way of the processor module 0. In this initial 21 state eithex interprocessor bus 35 may fail or be hrought 22 down (as indicated by the bars on the X bus) and can be 23 then reintroduced into the multiprocessor system without 24 producing any effect on the application program PA.

z~
.,~ . . . . .

` ~8 ~9 3~

., .

..

In the next view (the view entitled "CPU 0 Down") the processor moclule 0 is rendered unserviceable.
The mul-tiprocessor system informs the applica-tion pro-gram PA that this has happened, and the application program PA no longer tries to communicate with the pro-gram PB. All of the I/O is switched by the multiprocessor system to take place by way of the processor module 1, and the application program continues to service the terminals without interruption over the I/O bus 39 eonnect-ing the processor module 1 with the device controllers 41 (as indicated by the solid line arrow on the right hand I-/O bus 39).
In the next state of operation of the multi-processor system, as illustrated in the center top view of Figure 42 and enti.tled "CPU 0 ~estored", the proeessor ,j module 0 is now brought baek into serviee by way of a eon-`::
sole command. The processor module 0 is reloaded with the multiprocessor system from the disc by way of the processor module 1. The application program PA is informed that processor module 0 is now serviceable and the applica-tion program PA tells the multiprocessor sys-tem to create another eopy of the application program in the processor module 0.
This other eopy is designated as PC. The terrninals con-tinue in operation without interruption.

Ne~t, the processor module 1 is rendered inoperative, as illus-trated in the view entitled "CPU 1 Down". The application program~PC
is informed of this fact by the multiprocessor system and the application program PC takes over the application. The multiprocessor system auto-matically performs all of the I/O by way of the processor modu]e 0.
The terminals continue without interruption.
Finally, as indicated by the top right hand view of Figure 42 entitled "CP~) 1 Restored", the processor module 1 is rendered . operable by way of a console command and is reloaded with the multi-processor system from the disc by way o the processor module 0. The application program PC is informed that the processor module is llOW
available, and it tells the multiprocessor system to create another copy of itself (application program PD) in the processor module 1. All elements of the multiprocessor system are now operable.
, During the whole of this time both interprocessor buses and both ;, processor modules had been rendered unserviceable and reintroduced into the system, but the application program and the terminals continued without a break.

.

,,;
. ~ . .

7 ~1~

It is an important feature of -the multi-processor system that not only can -the application program continue while something has failed, but also that the failed component can be repaired and/or replaced while the application program continues. This ' is true not only for the processor modules and inter-processor buses but also for all elemen-ts of the multiprocessor sys-tem, such as power supplies, fans in the rack, etc. The multiprocessor system 31 thus is a true continuously operating system.

. ~ . .
.

.
.

., . .

~ - 86 -' .
. j, .

,,, f, ~ ~

1 THE INPUT/OUTPUT S'l'STE~ D DU~L PO}'~T D~:VICE COMTROLLE~:

3 The multiprocessor system 31 shown in Fig~ 1 4 includes an input~output (I/O) system and dual port device controllers 41 as noted generally above.

7 - The general purpose of the I/O system is to 8 allow transfer of data between a processor module 33 and g peripheral devices.

1~ It is an lmportant feature of the present 12 invention that the data transfer can be accomplished over redundant paths to insure fail soft operations so that 1~ a failure of a processor module 33 or a failure of a ~5 part of a device controller 41 will not inhibit transfer 16 Of dat2 to and frorn a particular peripheral device.

; 17 18 Each dev:;ce controller 41 has dual ports 43 19 and related structure which, in association with two 20 related I/O buses 39, permit -the redundant access to a 21 peripheral device as will be described in more detai~ below.

'A''" 23 The I/O system of the present invention also ., ,;. -24 has some particularly significant features in terms of 25 perormance. For example, one of the performance 26 features of the I/O system of the present invention is 27 the speed (bandwidth) at which tlle input/output bus 28 structure operates. The device controllers 41 collect 29 data from peripheral devices which transmit data at 30 relatively slow rates and transmit the collected data 1 to the processor modules in a burst multiplex mode at 2 or near memory speed of the processor modules 33.

4 As illustrated in Fig. 1, each processor 5 module 33 is attached to and handles a plurality of 6 individual device c~,ntrollers 41; and ~his fact ma~es 7 it possible for each device controller 41 to be 8 connected (through dual poxts 43~ to mor2 than one g processor module 33 in a single multiprocessor syStem~

~i With reference now to Fig. 12 of the drawings, 12 each processor module 33 includes, in addition to the 13 interprocessor control 55 noted above, a central processor 1~ unit ~CPU) part 105, a memory part 107 and an inpu-t/output 15 tI/0) channel part 109.
,;
,i 16 17 As illustrated in Fig. 12 and also in Fig. 1, 18 each device controller 41 controls one or more devices 19 through connecting lires 111 connected in a star pattern, i 20 i.e. each device independently connected to the device 21 ~ntroller.
22- ~
23 In Fig. 12 a disc drive 45 is connected to one 24 device controller 41 and a tape drive 49 is connected to 25 another device controller 41.

27 With continued reference to Fig. 12, each CPU
28 part 105 includes a microprocessor 113. A microprogram 29 115 is associated with each microprocessor 113. A part 30 of the microprogram 115 is executed by the microprocessor 8~

., . _ .

1 113 in performing I/O instructions for the I/O system.
2 The I~O instructions are indicated in Fig. 12 as EIO
3 ~execute I/O), IIO (interro~a-te I/O), HIIO (interroyate 4 high priority I~O); and these instructions are 5 illustrated and described in greater detail below with 6 reference to Figs. 15, 16 and 17.

8 The microprocessor 113 has access to the I/O
9 hus 39 by way of the I/O channel 109 by a collection lO of paths 117 as illustrated in Fig. 12.

11 .
12 With continued reference to Fig. 12, the I/O
13 channel 109 includes a mi.croprocessor 119, and a micro-14 program 121 is associated with the microprocessor 119.

16 The microprogram ~21 has a single unction 17 in the multiprocessor system, and that function is to 18 perform the reconnect and data transfer sequence 19 illustrated in Fig. 16 (and described in more detail 20 ~elow).

22 The I/O channel 109 of a processor module 33 23 also includes (as shown in Fig. 12~ data path logic 123.
2~
As ~est illustrated in Fig. 13, the data path 26 logic 123 includes a channel memory data register 125, 27 an input/output data register 127, a channel memory 28 address r~gister 129, a character count register 131, 29 an active device address register 133, a priority resolv-30 ing register 135 and parity generation and check logic 137.

8~

~"

7 :3 1 The path 117 sho~m in Fig. 12 includes two buses 2 indicated as the M bus and the K bus in Fig. 13.

4 The M bus is an outbus from the microprocessox 113 and tr~nsmits data into the input/output data 6 register 127.

8 The K bus is an inbus which transmits data g from the data path logic 123 into the microprocessor 113.
1~ . , .
~1 With reference to FigO 12, a path 139 connects 12 the data path logic 123 and the memory subsystem 107.

1~ This path 139 is illustrated in Fig. 12 as including both a hardware path 139A and two logical paths 16 139B and 139C in t:he memory subsystem 107 of a processor ., 17 mOdule 33.
1~ ' 19 Logical paths 139B and 139C will be described in greater detail below in connection with the 21 description of Fig. 16.

: : 23 The hardware path 139A includes three branches ! 2~ as illustrated in Fig. 13.
! ¦ 25 ¦ 26 A f.irst branch 135A-l transmits from memory 27 into the channel mPmory data register 125.

29 A second path 139A-2 transmits rrom the channel 30 memory address register 129 to memory.

~. 1 And a third p~th 139A-3 transmits from the 1 2 input/output data register 127 to memory.

4 With reference to Fig. 12, the input/output 5 channel of a.processor module 33 includes a control logic 6 section 141.
. ~

8 This control logic section 141 in turn includes 9 a T bus machine 143 (see Fig. 13) and request lines 10 RECO~NECT IN (RCI) 145, LOW PRIORITY INT~RRUPT REQUEST
1~ (LIRQ) 147, HIGH PRIORITY INTERRUPT P~QUEST (HIRQ) 149 12 and RANK 151 tsee Fig. 14).

~4 The I/O bus 39 shown in Fig. 14 and Fig. 12 .15 also includes a group of channel unction line~ 153, 157 16 and 159. See also Fig. 13. The TAG bus (T bus) 153 17 consists of four l.ines which serve as function lines, and lg there are three lines SERVICE OUT (SVO) 155~ SERVICE IN

;

19 (SVI) 157, and STOP IN (STI) 159 which serve as handshake 20 lines as indicated by the le~ends in Fig. 14.

22 As shown in Fig. 14 and Fig. 12, the I/O bus ~339 also includes a group of data lines 161, 163, 165, 167 ~4and 169.

26 The DATA BUS lines 161 and PARITY 163 are bi-27directional and serve as data lines and as indi.cated in 28Fig. 14, there are slxteen DATA BUS lines 161 and on~
2gPARITY line 163 in this group.

, 7~3 The lines E~lD OF T~NSFER (EOT) 16S, PAD O~T
2 (PADO) 167 and P~D IL~ ~P~DI) 169 serve as d~ta status 3 lines, and indicate special conditio~s that may occur on the data lines 161 and 1~3 from time-to-time.
,5 6 Finally, the I/O bus 39 inclu~es a reset 7 line (IORST~ 171 as also shown in Fig. 14 and in Fig. 12.

g Each T bus command illustrated in Fig. 18 10 requires some specific format on the data bus 161 ~hile 11 a T ~us command is valid. This specific da~a bus forma-t 12 is illustrated for the T bus functions Load Address and 13 Command (LAC~ and Read Device Status (RDST~ shown in 14 Fig. 18, for the preferred embodiment.

16 In the case of the T bus f~nction LAC, the 17 data or field transmitted on lines 0 to 5 of the data 18 bus 161 specify the operation to be performed; the field 19 transmitted on lines 8 to 12 of the data bus specify 20 the device controller ~1 ~or more precisely the port 43 21 of that device controller which is attached to the data 22 bus 161) to which the command is addressed; and the ~ield 23 transmitted on data bus lines 13 to 15 specify which 24 device attached to the device controller is to be 25 operated on by that device controller 41 in response to 26 this command.

~8 In the case of the T bus function RDST, data 29 bus bits ~, 1, 2 and 3 indicate ownership error, interrupt 30 pending, device busy, and parity error respectively.
31 Bits 4 to 15 return device dependent status.

7~3 1 The functions on the T bus are transmitted 2 in three sequences, shown in Figs. 15, 16 ~nd 17 ~nd 3 described in detail belo~l.

Each T bus function is asserted by the channel 6 and a handshake secuence is performed between the channel 7 109 and the device controller 41 using the handshake lines B 155, 157 and 159 to acknowledge receipt of the T bus 9 function. Control of the T bus and handshake is the 10 function of the T bus machine 143 in Fig. 13.

l~
1~ Fig. 28 is a timing diagram showing the operation 13 Of the handshake bet~een the I/O channel 109 and the ports 43.
~4 As illustrated in Fig. 28, line 155 transmits 1~ the service out signal (SVO) and line 157 transmits the , 17 service in signal (SVI).

~9 The channel clock cycle is shown in vertical ~0 orientation with the SVO and SVI signals.

Z2 As illustrated in Fig. 28, the service in 23 (SVI) signal is not synchroni~ed with the channel clock 24 and may be asserted at any time by the device controller 25 i~ response to a service out signal from the I/O channel 26 109.

28 Befoxe asserting service out (SVO), the channel 29 109 asserts the ~ bus function and, if required, the data 30 bus.

g3 _ , The channel then asserts a service out signal 2 as indicated by the vertical rise 279 in Fig. 28; and, 3 SVO remains true until the device controller responds 4 with service in (S~I) (281), acknowledging the channel 5 command; SVI remalns true until the channel drops SVO.

7 When the de~ice controller 41 asserts the s 8 service in (SVI) signal, the channel 109 removes the ~ service out (SVO) signal (as shown by the vertical drop 10 283 in ~ig. 28) in a time period typically between one 11 and two clock c~cles; and in response, the device controller 12 drops service in ~SVI) as shown by the vertical drop . 13 285 in Fig. 28.

~ .
When the device controller drops the service .; .
1~ in ~SVI) signal, the channel 109 is free to reassert a 17 service out signal ~5~70) for the next txansfer; howe~er, 18 the channel will not reassert SVO until SVI has been 19 dropped.

21 The arrows 281A, 283~ and 285A in Fig. 28 - 22 indicate the responses to the actions 279, 281, 283 23 respectively.

The handshake is completed at the trailing 26 edge of the vertical drop 285 as shown in ~ig. ~8, ~7 28 On an output transfer, the interface data register 29 21~ of the controller accep~s the data at the leading edge 30 of service out ~vertical rise 279) and transfPrs the data ' L

1 to the control part of the device controller 187 at the 2 trailing ed~e of the ser~ice out (the vertical drop 283).

4 On an input transfer the channel 109 accepts 5 data from the device controller at the trailing edge of 6 service out ~the vertical drop 283).

8 Thus, a two line handshake is used to interlock 9 transfer of information between the channel 109 and its 10 device controller 41, since they act asynchronously.

11 ' 12 This is the general handshake condition, ; 13 indicated as handshake 2L in Figs. 15, 16 and 17.

In addition, two special handshake considerations 16 occur, when appropriate.

~8 First, channel commands used to select a l~ device controller are not handshaken by SVI, since no 20 single device controller is selected during this time.

22 These commands include (as shown in Fig. 18)~
23 SEL - Select;
~4 L~C - Load Address & Command;
HPOL - Hi Priority Interrupt Poll;
.2~ LPOL - Lo Priority Interrupt Poll; and ~7 RPOL - Reconnect Interrupt Poll.

~9 Also, commands used to terminate a sequence are 30 not handshaken by SVT since they cause a selected device 31 controller to deselect itself.

, ~o 1 These ~ommands include ~as also shown in Fi~. 18):
2 DSEL - D~-Select;
3 ABTI - Abort Instruction ~I/O); and 4 ABT~ - A~ort Data.

6 For all of the com~ands noted above which are 7 not handshaken, the channel asserts SVO (155) for a givcn ~ period of time (e.g., two clock cycles) and then the 9 channel removes SVO. This type of handshake is referred 10 to as aandshake lL in FigsO 15, 16 and 17.
1i ' '' 12 Second, data transfer is handshaken normally 13 except that when a de~ic~ controller wishes to signal that 14 it does not require further service~ it returns stop-in (STI) instead of SVI. When SVO is next dropped by the 16 channel, the port deselects itself. STI otherwise hand-17 shakes in the same manner as S~I.

19 As a further condition on all handshakes, when 20 the channel prepares to assert SVO, it initiates a timer 21 ~part of T bus machine 143 in Fig. 13~ which times out 22 and posts an error if the next handshake cycle is not 23 initiated and completed within the period of time set 24 by the timer. If the tImer ~imes out, an error is 25 posted at the appropriate point in the sequence, and 26 either ABTI (EIO, IIO or HIIO sequence) or ~BTD
27 (reconnect sequence) is sent to the device controller 41 28 (see discussions of Figs. 15, 16 and 17).

3~

.

~ t~

1 Fig. 29 shows the logic for the handshake shown-2 in Fig. 28. The logic shown in Fig. 29 is part of the 3 T bus machine 143 shown in ~ig. 13 . The logic shown in 4 Fig. 29 is the logic which is effective for the general 5 handshake condition noted above.

7 The logic shown in Fig. 29 includes a service 8 out flip-flop 287 and a service in synchronization flip-9 flop 289. As illustrated by the dividing lines and 10 legends in Fig. 29, the flip-flops 287 and 289 are ll physically located within the channei 109.

1~ - , 13 The device controller 41 includes combinational 14 logic 291 and a transmitter 293 which transmits a service 15 in signal (SVI) back to the D input of the flip-flop 289.
1~ .
17 The fiunctioning of the logic shown in Fig.
18 29 is as follows.

The channel 109 asserts servicP out by turning Z1 on the J input of the flip-flop 287; and when the next 22 clock cycle starts, the service out signal is transmitted 23 by a transmitter 295 to the device controller.

Wh2n the combinational logic ~91 in the device 26 controller is ready it enables the transmitter 293 to 27 return the service in signal (SVI) to the flip-flop 28g~
28 This completes the handshake.

1 Turning now to ~he dual port device controller, 2 as illustrated in Fign 19, each or the dual ports 43 in 3 a device controller 41 is connected by a ph~sical 4 connection 179 to interface common logic 181 (shown in 5 more detail ln Fig. 21) and each of the ports 43 is 6 also associated through a logical connection 183 to the 7 inLerface co~on logic 181 as determined by an ownership 8 latch 185.

As shown by the connecting line 180 in Fig.

19, the interface common logic 181 is associated with 12 the control part 187 of the device controller 41. Th.e control part 187 of the device controller includes a 14 buffer 189.

~5 ~6 The dual ports 43 shown in block diagram form 17 in Fig. 19 (and in more detail in Fig. 23) are inportant parts of the multiprocessor system of the present 19 invention because the dual ports provide the failsoft 20 capability for the I~O system.

22 The ports 43 and related system components are 23 structured in such a way that the two ports 43 of one 24 device controller 41 are logically and physically 25 independent of each other. As a result, no component 1 26 part of one port 43 is also a component of the other 27 port 43 of a particular device controller 41; and no single 2~ component failure (such as an integrated circuit failure) 29 in one port can affect the operation of the other port.

~ \

'7~3 1 Each port 43 functions to interface (as 2 indicated by the legend in Fig. 19) a processor module 3 33 ~ith a ~eVice co~ oller~ and ultimately with a 4 particular device, through the device controller ~1.

5 The port-43 is the entity that communicates with the 6 processor module and communicates with the control part 7 of the device controller 187 (conditional on the state 8 of the ownership latch 185).

1~ That is, the port itself makes the connection . 11 to a processor module (dependent upon instructions ~2 received from the I/O channel 109 as discussed in more 13 detail below) by setting its select bit 173.

1~
.Each of the individual ports 43 in a particular 16 device controller 41 can be connected independently to 17 a processor module 33 and at the same time as the other 18 port in that device controller i.s connected to a different i 19 module. However, the ownership latch 185 establishes 20 the logical connection between the control part of the ~1 de~ice controller and one of the dual ports 43 so that 22 only one port has control of the device controller at any :~ 23 one point in time.

. The decode logic determines what function 26 is being transmitted on the T bus 153 at any particular time~

28 The control logic combines T bus functions 29 to perform specific port functionst for e~ample, set 30 select bit, clear select bit, read interrupt status.
., .

. 99 :

.
~ t~
- 1 The functioning of the control logic is 2 illustrated in the logic equations set.out in Fig. 27.

4 When a connection sequence (to be described 5 later in reference to Figs. lS, 16 and 17) is transmitted 6 over the I/O bus 39, one of the ports 43 ~and only the 7 one port 43 in a device con~roller al attached to that 8 I~O bus 39) connecis ~in a logical sense) to the bus 39 9 by setting its selec-t bit 173.

11 This logical connection i5 determined by part 12 of the data transmitted in that connection sequence.
13 When connected, that particular port 43 subsequently 14 responds to channel protocols in passing information lS between the channel a.nd the control part of the device 16 controller. The device address comparator i93 is the 17 component part of the port 43 t~at determines the port's 18 unique address.

The device address comparator 193 determines 21 the unique address for a particular port 43 by comparing 22 the device address field on the data bus 161 during a 23 LAC T bus function, with device address jumpers associa-ted 24 with a particular port 43. When the address transmitted 25 by the channel 1~9 matches the address determined by the 26 jumpers on a particular port 43, the term ADDCOMP (see 27 Fig. 27) is generated and the select bit 173 for that 28 port is set (assuming that the other conditions set out 29 in Fig~ 27 allow the select bit to be set). The port 30 43 then responds to all T bus operations until the sequence 31 terminates by clearing the select bit.

.

1 3l ~
1 The abbxeviations used in Fig. 27 include 2 the following:
3 ~d~ Comp - Address Compare (Device Address~;
4 PAROXFF - Parity OK Flip-Flop;
SFL - Select;
6 O~ - Ownership; and 7 SELBIT - Select Bit.

1~
. 11 .
~ .
`' 12 1~ ' 1~ ' , .

~4 ~6 ' 10i . ' 1 The ~arity check register 177 is related to 2 the parity generator and ~heck logic 137 of Fig. 13 in 3 that on output the parity generator logic 137 generates 4 the parity to be checked by the parity checker 177 of : 5 the port 43,.and this parity must check or the operation S will ~e aborted by the I/O channel 109 of the processor 7 module 33. On input, the interface com~on logic 181 8 ~enerates parity to he checked by the channel parity 9 check logic 137 in a similar fashion.

11 As shown in Fig. 24, the parity check is .
12 started before data is loaded i}ltO the register, and ~3 the parity check is continued until after the data has 14 been fully loaded into the register. That is, the 15 parity on the D bus is checked by the port parity 16 resister whenever the channel asserts SVO with an output 17 T bus function, and the parity is monitored for the 18 duration of SVO to i~sure that the data on the D bus is g stable for the duration of SVO while the port transfers 20 the data into the data register 213.

22 ~his parity check occurs on each transaction ~3 in a T bus sequencei and if a parity erxor occurred during 24 any transaction in the sequence, the error is returned as a status bit in response to a T bus function during a ~6 sequence. For example, in an EIO sequence tFig. 18 and 27 15) the P bit return for RDST indicates that the port 28 determined a parity error during the EIO sequence.
~ . .

.. . .. .. .. .. . . .

;

1 As illustxated in Fig. 18, -the parity errOr 2 bit is a bit number 3 on the D bus in response to a 3 RDST function on the T ~us.

If a parity error occurs at some time other 6 than during an EIO sequence, the parity error is reported 7 during the read interrupt status ~RIST) T bus function 8 similar to the manner described above or the RDST T
9 bus function.

11 The parity error is cleared at the besinning 12 of an EIO, IIO, HIIO or reconnect sequence as shown 13 in Fig. 24.

~5 If a parity error is detected during any 16 se~uence it is recorded by the parity check register 17 to be returned on the D bus in response to a RDST or 18 RIST T bus function. -With continued reference to Fig. 20, the ~1 function of the enable latch 175 in the port 43 is to 22 allow the I/O system to recover from a certain class of 23 errors that would otherwise render inoperative both of 24 the I/O buses 39 attached to a particular device controller 25 41. The enahle latch 175 accomplishes this by not allow-26 ing the port 43 to place any signals on the I/O bus 39.

28 The enable latch 175 is cleared by a specific 29 disable command. This is a load address and command (L~C) 30 T bus function with a specific operation code trans-31 mit~ed on the D hus 161.

7~1 1 Once _he enabl~ latcr. 175 is cleared, thls 2 enable latcn cannot b~ program~laticall~ reset~
4 The poxt 43 includes a status multlplexer 195.
5 The status multiple~er 195 returns the ownership error 6 mentioned above i the device controller 41 i5 logicall~
7 connected to the other port ~3 of that device controller, 8 to indicate that the device controller is owned by the 9 other port and commands to this port will be ignored.
11 The port 43 includes an inter~ace transceiver 12 ~97 for each input line (i~e., SVI, STI, Data Bus, Parity, 13 PADI, RCI, LIRQ, HIRQ) of the I/O bus 39 shown in Fig. 14.
14 The transc~ivers 197 transmit data from the port 43 to 15 the I/~ channel 109 when the port select bit 173 is 16 set and the T bus function on the T bus 153 requires 17 that the device contxoller 41 return information to the I8 channel. The transcei.vers 197 pass information from the 19 data bus 161 into the port 43 at ali times.
21 It is a feature of the present invention that 22 the power on circuit 182 acts in association with the 23 transceivers 197 to control the behavior of the trans-24 ceivers as the device controller 41 is powered up or 25 powered down, in a w~y which prevents erroneous signals 26 from being placed on the I/O bus while power is going up 27 or down. This feature is particularly significant from 28 the standpoint of on line maintenance.
~9 7~

1 As shown ln Fig. 20, each transceiver 197 2 comprises a receiver 198 and a transmitter 200.

4 The transmitter is enabled by an enable line 5 ~02.

7 ThPre are several terms ~hich are on the enable 8 line 202. These include the select bit 173, a required 9 input function on the T bus, and a signal from the PO~T
10 circuit 182.

12 The signal from the PON circuit, in a particular 13 embodiment of the pr~sent invention, is connected in a 14 "wire or" connection to the output of the gate which 15 co~bines the other terms so that the output of the PON
16 circuit overrides the other ten~s by pulling down the 17 enable line 202. This insures that the transmitter 200 --18 5in one specific embodiment, an 8T26A or 7438) is placed 19- in a high impedence state until the PON circuit detects 20 that the power is at a sufficient level that the integrated 21 circuits will operate correctly. The PON circuit output 22 stage is designed to take advantage of a property of the 23 specific transceiver integrated circuit used. On this 24 particulax type IC if the driver enable line 202 is held 25 below two diode drops above ground potential, the trans-.26 mitter output transistors are forced into the off state ~7 regardless of the leveL of power applied to the integrated 28 circuit. This ensu~es that the driver cannot drive the bus.
... . .

: , 2g 3~
. . .

~`r ~ r 7a~

1 Th~ particular combinatlon of features provides 2 a mode of operation wherein the output of the integrat~d 3 circuit is controlled as power comes up or goes down, ,, 4 whereas normally the output of an integrated circuit is ~ 5 undefined when power ~rops below a certain level~

.! 6 7 This same circuit is used on the ~ and Y buses 8 of the interprocessor bus system to control the transceivers g and control signals generated by the interprocessor control 10 55. As indica~ed in Fig. 30, each central processor unit 11 (CPU) 105 has a PON circuit 182 which is similar to the 12 PON circuit 182 in the device controller~ The PON circuits 13 therefore control the transmit~ers for all of the device 1~ controllers 41 and all of the interprocessor controls 55.

16 Details of the power-on (PON) circuit are shown 17 in Fig. 25 where the circuit is indicated generally by the 18 ~eference numeral lB 2 .

The purpose of the POW circuit is to sense two 21 different voltaye levels of the five volt supply.

23 If powex is failing, the circuit senses the 24 point at which power drops below a certain level which 25 renders the logic in the device controller or CPU an 26 inde~erminate state or condition~ At this point the 27 circuit supplies signals to protec~ the system against 2~ the logic which subsequently goes into an undefinable state. ..

;, .

The Se~Olld voltage level wl~ich ~he PON circui~s will sense is a value th;lt is perceived wllen po~er is coming up. This second level at wllich power is scnsed ~iill be grcater than ~he first level by roughly 100 millivolts to provide hysteresis for the system to eliminate an)~ conditions of oscillation.
The PON circuit stays in a stable condition after it senses one of the voltage cor.ditions ~mtil it senses the other voltage condition at whicll point it changes state. The state at which the PON circuit is in at any particular time determines the voltage level at which the transition to the other state will be made.
The power on circuit 182 thus presents a signal establishing an indication that the power is within predetermined accep-table operating limits for the device controller 41. If the po~er is not within those predetermined acceptable operating limics, the signal output of the power-on circuit 182 is used to directly disable the appropriate bus signals of the device controller 41.
The output of the PON circuit 182 is a binary output. If the output is a one, the power is within satisfactory limits. If the output of the PON circuit is a zero this is an indication that the power is below the acceptable limit.

1 The power-on circuit 182 shown in Fig. 25 and 2 to be described in detail belcw is used wlth the device 3 controller 41 and has seven output driver stages which 4 are used in the application of the power-on circult 182 5 to ,he device controller 41. How~ver, the same power-on 6 circuit 182 is also used with the CPU 105 and th~ bus 7 controller 37, but in those applications the power-on 8 circuit will have a lesser number of output driver stages.

As illustrated in Fig. 25, the PON circuit 182 11 comprises a current source 184 and a differential amplifier 12 1~6.

14 The differential amplifier 186 has, as one 15 input, a temperature compensated reference ~ol~age input 16 c~ a line 188 and has a second input on a line 190 which 17 is an indication of the voltage that is to be sensed by 18 the powe,r-on circuit.

The reference voltage on line 188 is established 21 by a zener diode 1920 23 The differential,amplifier 186 comprises a 24 matc~ed pair of transistors 194 and 196.

26 The voltage applied on the line 190,is 27determined by resistors 198, 200 and 202. The resistors 28198, 200 and 202 are metal film xesistors which provide 29 a high degree of temperature stability in the PON

30 circuit.

' ' 108 -1 The outputs on lines 204 and 206 of the 2 differential amplifier 186 are applied to a thrce -. 3 transistor array (the transistors 208, 210 and 212), 4 and this three transistor ar.ray in turn controls the S main output control transistor 214.

7 The main output control transistor 214 8 dri~es all output drivers that are attached. For e~ample, g in the appllcation of the PON circuit 182 for the device 10 controller 41 (as illustrated in Fig. 25~, the main out-11 put transistor ~14 drives output stages ~16 through 228.
''4 12 The output stage 216 is used to clear the logic, the out-13 put stages 218, 220 and 222 are used in combination with 14 the interface devices of one port 43 of the device controller 15 41, and the output s.:ages 224, 226 and 228 are used in 16 combination with the interface device of the other port 17 43 of the device controller 41 19 Finally, the PON circuit 182 includes a 20 hysteresis control 230. The hysteresis control 230 21 includes resistors 232, 234 and a transistor 236.

~3 In operation, assuming that operation is 24 started from a power off state to a power on condition, 25 the power lS applied through the current source ~82 to 26 the differential amplifier 186 and to the main output 27 control transistor 214. At this time the volta~e on ; ~8 ~he line 190 is less.than the voltage on the line 188 2~ so the differential amplifier 186 nolds the output of 30 the main output control transistor 214 in the off state~

', 109 7~
~lis, in turn, ~ orce tlle Outp~lt stages 216 through ~ ~ S o11 .
This asserts the OlltpUt of the PC~ circùit lS2 in ~he zero state, the state indicating that power is not ~ithin acceptal)le limits.
A~ voltage rises, the input voltage on line 1'~0 ~ill increase until it equals the reference voltage on line 18S. At this point the differential amplifier 186 drives the main output control transistor 214, turn-110 ing it on. ~lis removes the base drive from the ou-tput stages 216 through 22~, forcing these output stages off. The output of tne PON circuit 182 is then a one, indicating that the power is within acceptable limits.
At this point the hysteresis control circuit 230 comes into play. l~lile power was coming on, the transistor 236 of the hysteresis control circuit 230 was on. When the transistor 236 is on, the resistance value of the resistor 202 appears to be less than the resistance value of this resistor 202 is when the transistor 236 is off.
The point at which the main output control transistor 214 turns on is the point at which the hysteresis transistor 236 turns off. T~lrning off the hysteresis transistor 23G causes a slight voltage jump in the line 190 which further latches the differential amplifier 186 into the condition where the differential ~ 3~ ~

amplificr lSIj sustains the maill out~llt tr~lnsistor 214 in tllc on statc.
Tlle state of the PO~ circuit will remain stable in this condition with the maill output control transistor 214 on and the output drivers 216 through 22g off until the plus five volts lrops below a lower tl~resllold point, as determined by the voltage applied on the line 190.
As the voltage on the line 190 decreases below the reference voltage on the line lS8, ~because the five volts supply is going down in a power failure condition), then the differential amplifier 186 turns off the main output control transistor 214. This, in turn, turns on the output driver stages 216 through 228.
Since the hysteresis transistor 236 was off as power dropped, the voltage applied to the input of the PON circuit 182 must drop somewhat farther than the point at which the PQN circuit 182 sensed that power was witllin the acceptable limits during the power-up phase of operation.
This differential or hysteresis is used to inllibit any noise on the five volt power supply from causing any oscillation in tl-e circuit that would erroneously indicate that power is failing.
The PON circuit 182 shown in Figure 25 provides very accurate sensing of the two voltages used by the -- lll -!

1 PON circuit to determlne its state (whether a on~ o~
2 zero output of the PON circuit).

4 In order to sense these two volta~es vcry 5 accurately the PON circuit must have the c~pabilit~
compensating ~or initial tolerances of the diff~rent ~ 7 components and also the capahility to compensate for ; 8 cha~es in temperature during operation. In the Po~
9 circuit 182, the zener dlode 192 is the only c~itical 10 part that must be compensated for because of its ini~ial 11 tolerance, and this compensation is provided by selecting ~ 12 the resistor 198.
.$ 13 14 Temperature compensation is achieved because 15 the æener diode 192 is an active zener diode and i5 16 not a passive zener diode. Effective temperature 17 compensation is also achieved because the two transistors 18 in the diferential amplifier 186 are a matched pair of ; 19 transistors and the resistors 198, 200 and 202 are metal 20 film resistors.

22 Each port 43 includes a number of lines which 23 are indicated by the general reference numeral 179 in 24 Fig. 20 and Fig. 19. This group of lines 179 includes 25 the indivlaual lînes 201 (sixteen (16) of which make up 26 the Input Bus - I Bus), device address lines 203, Output ~7 Bus lines 205 (of which there are sixteen), a take owner~
28 ship line 207 and general lines 203 which transmit such 29 si~nals as parity, the T bus, and other similar lines 30 which are required because of the particular hardware 31 implementation.

_,.
.

1 These particular lines 201, 203, 205, 207 and 2 209 correspond to the lines with the same numbers in 3 Fig. 21, which is the block diagram of the interrace 4 common logic. However, there are two sets of each of these lines in Fig. 21 because the interface common 6 lo~ic ].81 is associated with each of the dual ports 43 7 in a device controller 41.

9 With reference to Fig. 21, the interface common 10 logic 181 lncludes the ownership latch 185 ~see also ll Fig^ 19~. This ownership latch determines the logical 12 connection between the interface common logic 181 and 13 a port 43 from which TAKE O~E.RSHIP signal has been 14 received over the line 207.

16 As noted a~ove, the TAKE OWNERSHIP signal is 17 derived b~ the port hard~laxe from a load address and 18 command tLAc) T bus co~mand (see Fig~ 18) with a particular 19 operation code in the command field on the D bus~ When 20 the port receives the function LAC on the T bus from the 21 channel, the port logic examines the command field (the 22 top six bits) on the D bus. Then, if the command field 23 contains a code specifying a take ownership command, the 24 port hardware issues a signal to set the ownership 25 latch to connect the port to the interface common logic 26 and thence to the contxol part of the device controller.
27 If the command field specifies a kill command, the port 28 hardware issues a signal to clear the port's enable latch.
29 This operation happens only if the device address field 30 on the D bus matches the portSs device address jumpers, i'7~

1 and no parity error is detected durlng the col~mand.
2 That is, no commands (inciuding the iake ownership, -3 kill, etc.) are executed if a parity error is detected ,. .
4 on the LAC.

6 As a consequence, the I/O channel 109 issuing the Take Ownership command gains control of the 8 device controller 41, and the other port 43 ls logically g disconnect2d. Take Ownership may also cause a hard 1~ clear of the controller's internal state~

12 ~he state of the ownership latch 185 deter-mires which port may pass information through the multi-14 plexer 211. Once the ownership latch 185 is set in a 15 given direction, it stays in that state until a Take 16 Ow~ership command is received by the other port.
17 ~ssertion of the I/O reset line (IORST~ will also cause 18 ownership to be given to the other port af-~er the internal ~9 state of the device controller has been cleared.
2~
~1 , 3 ~7 Control signals are chosen by the state of the ownershi.p register 185 and from the appropriate one of the ports 43 and are transmitted by ;: the multiplexer 211 to ~he control part 187 of a device controller on a set of control lines 215. Data are selected from an appropriate one of .; the ports 43 on lines 205 and are loaded into the data register 213 and presented to the controller on an O~ltput Bus (0 bus) 217.
Some of the control lines 215 (the lines 215A) are used to control the multiplexer 220 in selecting information from the controller - as transmitted on lines 219, to be returned by the input bus (I bus) , 10 201 to the ports ~3 (Figure 20) and then to the channel 109 of a proces-i sor module 33~ A line 221 returns the device address from the appropriate port 43 to the I bus 201 and thence to the I/0 channel 109.
The data buffer 189 shown in Figure 19 is illustrated in more . detail in Figure 22.
In accordance with the present invention many of the device ~ controllers 41 incorporate a multiword buffer for receiving information .~ at a relatively slow rate from a peripheral device and then transmitting that information at or near memory speed to the processor module to maximize channel bandwidth utilization.
In the buffer design itself it is important that the device controllers ~I be able to cooperate . . .

, . . .
.,., - .

; -115-'7~

1 with each other i~ gaining access to the channel 109 2 to avoid error conditions. In order for the device 3 controllers 41 to cooperate properly, the multi~iord 4 buffers 189 are constructed to follow certain guide1ines.

:
' S '' 6 These guidelines include the following:

8 First of all, when a device controller makes g a reconnect request for the channel 109 it must have 1~ enough burfer depth left so that all higher priority 3 11 de~ice controllers 41 and one lower priority device 12 controller 41 may be serviced and the reconnect latency 13 of the reconnect request can occur without exhausting 14 the remaining depth of the buffer. This is called Buffer .~5 Threshold t abbreviated T in Fig. 23.
~6 17 Secondly, after the buffer has been se.rviced, 18 it must wait long enough to permit all lower priority 19 device controllers 41 to be serviced before making 20 another reconnect request. This is called HoldoffO
21 The buffer depth (D in Fig. 23) is the sum of the holdoff 22 depth plus the threshold depth~

24 - The holdoff and threshold depths are a 25 function of a number of variables. These include the 26 device rate, the channel rate, the memory speed, the 27 reconnect time, the number of controllers of higher priority - 28 on that I/O bus, the number o~ controllers of lower priorlty 29 on that I/O bus, and the maximum burst length permissible.

_. ~

r~ . , -1 A controller at high priority on an I/O bus has 2 more controllers of lower priority associated with it on the 3 same I/O bus than another controller at lo~er priority on ~ ~ the same I/O bus, and therefore the'higher priority controller - 5 requires more holdoff depth than the lower priority controller.
- 6 Similarly, a controller at low priority on an I/O bus requires 7 more threshold depth than a controller at,higher priority.
8 The bufer 1~9 in a controller is constructed to take advantage g of the fact that as holdoff requirement increases the 10 threshold requirement decreases, and as the threshold - 11 requirement increases the holdoff requirement decreases. This 2 is accomplished by making the stress at which a reconnect 13 request is made be ~7ariable, the actual setting depending 14 on the characteristics of the c'ontrollers at higher and 1~ lower priority in a particular I/O channel configuration.
'~ 16 The buffer depth is therefore the maximum of the worst-case ,` 17 threshold depth or worst-case holdoff depth requirement, ~8 rather than the sum of the worst~case threshold depth and 19 worst-case holdoff depth. This allows the buffer depth to be minimized, and shortens the time required to fill or 21 empty the buffer, ' 22 , . .

~2S

27, ~9 116a .. , . ~

G~

'75 .~ .
1 A number of these param~ters are graphically 2 illustrated in Fig. 230 In Fig. 23 time has been ~lottecl 3 on the horizontal a~is versus words in the buffer on 4 the vertical axis for an output operation.
6 Starting at point D on the upper left hand 7 part of FigO 23 (and assuming a buffer filled to the full .i 8 bu~fer depth), data is transferred to a device at a rate 9 indicated by the line of slope -RD and this data transfer 0 continues without any reconnect signal beins generated 11 until the buffer depth decreases to the threshold dep-th 12 as indica.ed by the intersection of the line of slope ~RD
13 with the threshold depth line ~ at point 223.

At this point the reconneck request is made 1~ to the channel 109 as indicated by the legend on the 17 horizontal axis in Fig~ 23.

19 . The transfer of data continues from the buffer 20 at the rate indicated b~ the line of slope -RD and the 21 request is held off by higher priority device controllers 22 41 until point 22S at which point the request is honored 2~ by the channel 109, and the I/0 channel begins its 2~ reconnect sequence for this device controller.

K~ .
26 At point 227 the irst data word has been trans 27 mitted by the channel 109 to the device controller buffer 28 189, and the channel 109 then transfers data words at 29 a rate indicated by the line of slope RC into the buffer 30 1~9.

. 117 --~\

1 At the sa~e time the device controller 41 2 continues to transfer data words out of the buffer at 3 the rate -RD so that the overall rate of input to the 4 buffer 189 ~s indicated by the line of slope RC ~ RD
5 until the buffer is again filled at the point 229. At & 229 the buffer is full, and the device controller dis-7 connects from the channel 109, and the data trans~er 8 continues at the rate indicated by the slope line -Rc.

.9 The notation tr in Fig. 23 indicates the time ~1 required for the polling and selection of this device 12 controller and the transf~r of the first word. This will 13 be discussed again b~low in relation to Fig. 16.

The letter B in Fig. 23 indicates the burst ~6 time. The burst time is a dynamic parameter~ The length 17 Of any particular burst is dependent upon the device 1~ transfer rate, the channel transfer rate, the number of 19 devices with transfers in progress and the channel ?0 reconnect time. The maximum time permitted for a burst 21 is chosen to minimize the amount of buffer depth requlred 22 while accomodating high device transfer rates and also 23 tha number of devices that can transfer concurrently.

Fig. 22 is a block diagram of a pax-ticular 26 embodiment of a buffer 189 constructed in accordance 27 with the present invention to accomplish the holdoff 28 and threshold requirements illustrated in Fig. 23.

' ' ' ' .

1 The buffer 189 shown in Fig. ~2 comprises an ~ input buffer 231, a buffer mcmory 233, an output buffer 3 235, an input pointer 237, an output pointer 239, a 4 multiplexer 241, buffer control logic 243 ~descrlbed in 5 more detail in Fig. 26), a multiplexer 245 connected to 6 the buffer control logic 243 and a stress counter 247.

8 As also illustrated in FigO 22, two groups of g data input lines (lines 217 and ~49) are fed into the ~o inpuk buffer 231.

12 One group of data input lines include sixteen 13 device data input lines 249.

The other group of input lines include si~teen 16 Output Bus lines (O bus lines) 217.

18 One or the other of these two groups of input ~9 signals is then fed from the input buffer 231 to tne 20 buffer memory 233 by a group of lines 251. There are 21 sixteen of the lines 251.
2~ _ ~3 Data is taken from the buffer memory 233 and 24 put into the output buffer 235 by a group of lines 253.

25 There are sixteen of the lines 253.

~7 The output buffer 335 transmits the data . ~ .
28 back to the interfac~ co~mon logic 181 (see Fig. 19 ~9 and Fig. 21) on a group o~ six~een lines 219 and to 30 the devices 45, 47 (such as 49, 51, 53 shot~ in Fig. 1) 1 on a group of si~teen lines 255 as indicated by the 2 legends in Fig. 22.

4 The input and output pointers 237 and 23g S function with the multiplexer 241 as follows.

7 When data is being transferred from the 8 input buffer 231 to the buffer memory 233, the input 9 pointer 237 is connected to the buffer memory 233 10 through the multiplexer 241 to determine the location ll into which the word is written.

13 When data is being transferred out of the 14 buffer memory 233 into the output burfer 235, the output 15 pointer 239 is connected to the buffer memory 233 through 16 the multiplexer 241 to determine the location from which 17 the word is takenn ~1 , ~4 ~20 1 The purpose of the buffer control logic 243 2 illustrated in Fig. 22 and Fig~ 26 is to keep track of 3 the stress placed on the buffer 189. In this regard, 4 the degree of the full or empty condition of the buffer 5 in combination with the direction of the transfer with 6 respect to the processor module (whether input or output) 7 determines the degree of stress. Stress increases as the 8 device accesses the buffer and decrèases as the channel 9 accesses the buf~er.

11 In the implementation shown in Figs. 22 and 26 ~ the stress counter measures increasing stress from 0-15 13 on an input, and decreasing stress from 0-15 on an out-14 put- Another implementation ~not shown in the drawings) 15 would add the direction of transfer in the buffer control 16 lo~ic such that two new lines would access the pointers 17 237 and 239 and the stress counter would always measure 18 increasing stress.

With continued reference to Fig. 22, a channel 21 re~uest line 215 (seTe also Fig. 21) and a device request 1 line 2S7 (coming from the control part 187 of the Z device controller) are assexted to indicate access to 3 the buffer 189.

S The multiplexer 245 chooses one of these lines Ç as a request to increase the buffer fullness and chooses 7 the other line as a request to decrease the buffer full-8 ness based on the direction of the transfer (whether 9 input or output) with respect to the processor module.

11 The line chosen to increase buffer fullness 12 is also u5ed to load data from the appropriate data 13 lines 249 or 217 (see Fig~ 22~ into the input buffer 14 231 by means of the line 259.

16 The channel and the device may access the 17 buffer 189 at the same time, and the buffer control 18 logic 2'43 services one request at a time. The buffer 19 control logic 243 chooses one of the lines for service 20 and holds the other line off until the buffer control 21 logic 243 has serviced the fixst request, then it 22 services the other request.
~3 24 The servicing of a request by the buffer 25 control logic 243 includes the following.
~6 27 First of all, ik determines the dixection of 28 kransfer (into or out of) the buffer memory 233, and it 29 asserts line 261 (connected to the multiplexer 241) as 30 appropriate to select the input pointer 237 or the output 31 pointer 239 through the rnul~iplexer 241.

.-3'~J~
. ~
1 Secondl~;, on an output request, the buffer cont~cl 2 logic 243 asserts line 263 which does three thin~.
3 (A) It writes the word from the input buffer 231 4 into the buffer memory 23~ at the l.ocation determined by 5 the input polnter 237 and the ~ultiplexer 2~
6 (B) It increments the stress counter 24~.
7 (C) The buffer control logic 243 increments the ~ input pointer 237.

i;

lQ Thixdly, on an output transfer, the buffer control 1~ logic 243 asserts line 265 which accomplishes the following 12 three operations.

13 (A) The buffer control logic 243 writes the word ~4 being read from the ~uffer memory 233 as determined by the output pointer 239 and multiplexer 241 into the output buffer 235.

, 16 ~B) The buffer control logic 243 decrements the 17 stress counter 247.

18 (C) The buffer control logic 243 increments the 19 output pointer 239.

2~

: 21 The stress counter 247 determines when the buffer ~2 189 is full (D), or at threshold depth (T) as shown by the 23 output line legends in Fig. 22.

The output of the stress counter is decoded, and any 26 one of the decoded values may be used to specify that the buffer 27 is at threshold depth. In the preferred embodiment, wire jumpers 28 are used to select one o sixteen possible stress values, and 29 a reconnect request is made to the channel 109 when the stress 30 on the buffer 189 reaches that value.

1 The control part 187 of the device controller 2 uses these three signals (which correspond to the lecJends 3 in Fig. 23) to make reconnect requests and disconnect 4 requests on respective lines 145 (see Fig. 14 and Fig. 12) 5 and 153 (see ~ig. 1~ and Fig. 12).

The STI tstop in) signal transmitted on line 159 shown ~ in ~ig. 14 and Fig. 12 is related to the buffer depth (~), the g full or e~pty conditions of the bufLer and the direction of transferi and the RCI (reconnect in) signal on line 145 of Fig. 14 and Fig. 12 is related to the threshold depth (T) indication from the stress 12 counter 247 in Fig. 22. Thus, the STI signal is asserted when 13 the buffer 189 reaches a condition or minimum stress (full on output 14 and empty on input). The STI signal si~nals the channel 109 that the controller 41 wishes to terminate the burst data transfer.
16 When the burfer passes through its threshold, it asserts the RCI
17 signal on line 145 to indicate to the channel 109 that the buffer 18 wishes ~o transfer a burst of data.

Fiy. 26 shows details of the multiplexer 245, the ~ 21 buffer control logic 243 and the stress counter 247 of the i 22 buffer 189 shown in Fig. 22.

24 In Fig. 26 the multiplexer 245 is shown as two sets of 25 gates 245A and 245B, request flip-flops 267A and 267B, a clock 26 flip-flop 269, request synchronization flip-flops 271.~ and 271B~ a 27 priority resolving gate 273 and request execution gates 275A and 275 29 The stress counter 2~7 comprises a counter section 30 247A and a decoder section 247B as indicated by -the legends 31 in Fig, 26.
' 12 1 As illustrated in Fig. 26, the two sets of 2 gates 245A and 245B have used the channel request signal 3 (line 215) and the device request signal (line 257) 4 and the read and write signals to determinP which of the I 5 channel or the device is putting dat~ onto the buffer 6 189 and which is taking data out of the buffer 189.

8 The request flip-flops 267A and 267B store the 9 requests until the control logic has serviced the request.
- .
11 The clock flip-flop 269 generates a two phase 12 clock used by the request synchronization flip-flops 271A
13 and 271B and the request execution gates 275A and 275B.

The reauest synchronization flip-flops 271A
1~ and 271B synchronize the request to the clock generation 17 flip-flop 269 and stabilize the request for execution.
lB
19 The priority resolving gate 273 picks one 20 of the requests for execution and causes the other 21 xequest to be held off.
,. 22 ~3 The request execution gates 275A and 275B
24 execute the requ~sts in dependence on the synchronized 25 request.

27 Each output signal on the lines 263 and 265 28 performs the functions described above (incrementing 29 and decrementing the stress counter, updating the 30 buffer memory or output bu~fer, and updating the input 31 pointer or output pointer).

`di'~

1 In addition, each signal clears the appropriate 2 request flip-flop through the lines 277~ and 277 3 illustrated in Fig. 26.

As noted above, Figs. 15, 16 and 17 show 6 the three sequences of operation of the I/O syst~m.

8 In the operation of the I/O system, the normal 9 data transfer ~etween a processor module 33 and a ~0 particular device, such as a disc ~5, includes an EIO
1~ sequence to initiate the transfer.
~2 13 The EIO instruction selects the particular 14 device controller and device and specifies the operation to be performed.

17 The device controller 41 initiates the I/O
18 between the device controller 41 and the particular 19 device.

21 The device controller 41 periodically 22 reconnects to the channel 109 and transfers data 23 between the device controller 41 and the channel 109.
24 The periodic reconnection may be for the purpose of either transferring data from the channel to the device 26 or for the purpose of trans~erring data from the device 27 to the channel.

29 ~hen the transfer of data is complete the device controller ~1 interrupts the CPU 105, which 31 responds by issuing an IIO or an HIIO sequence~

, -The IIO seque~ce det~rmines the ide~tit~ of 2 the interrupting ~evice an.d collditions under which th~
3 transfer completed.

The HIIO sequence is similar to the IIO
6 sequence but is issued in response to a hi~h priorit~
7 I/O intexrupt.

9 The "Execute I/O" CPU instruction (EIO) is 10 defined by the T bus state changes shown in Fig. 15.

12 The first state sho~l in Fig. 15 (the state 13 fa,thest to tne left) is the no-operation (NOP) or 14 idle state. The other states are t~e same as those 15 listed in Fig. 18 by the coxresponding mnemonics--load 16 address and command (LAC)~ load parameter (LPRM), read 17 device status (~DST), deselect (DSEL) and abort 18 instruction (ABTI)~

As in the state changes shown in Figs. 6, 7 ~1 and 8~ the solid line arrows indicate a state change, 22 and a dashed lin2 arrow indicates a condition which must 23 occur before a state change can occur.
2~
The EIO instruction and execution shown in 26 ~ig. 15 is directly under control of the microprocessor '~7 113 ~see Fig. 12) of the CPU 105.

29 This CPU initiation is shown as transmitted 30 to the state machine in Fig. 15 by the llne 117; the .

i7~

. .
ir.~tia-tlcn signal is accepted only when the T bus is 2 in the idle state.

4 Once the CPU initiation signal is applied, the T bus goes from the NOP (idle) state to the LAC
~ state.

8 In the LAC state or function a word is taken g from the top of the register stack 112 in the CPU 105 (see Fig. 12) and is put on the D bus 161 (see Fig. 14).
1 1 ....
12 As described above, this word is used to select a particular device controller 41 and a particular 14 peripheral device 45, 47, 49, 51 or 53 (see Fig. 1), and the word is also used to specify the operation to 16 be performed.

18 In the next T bus cycle the T bus goes to 1~ the LPRM state.

21 In the load parameter state (LP~`1~ the word 22 just below the top of the register stack in the CPU
23 105 (see Fig. 12) is put on the T bus 161 (see Fig.
24 14) by the I/O channel 109 and is passed to the device controller 41 selected during the previous LAC state.

27 At the conclusion of the handshake cycle, 28 as sho~m by the dashed line arrow in Fig. 15, the T
29 bus goes to the RDST state. In this state the device 3Q controller 41 returns the device status (the status of 12~ -1 a particular device selected and comprising the set 2 of signals describing the s~ate of that device) from 3 the device controller 41 and places it on the top of 4 the register stack 112 in the CPU 105.
6 During the load parameter and read device 7 status state several errors may have occurred. These 8 include parity error, handshake time out, and an error 9 indication in the status word. If an error did occur, ~0 then the r bus machine 143 (Fig. 13) goes from the 11 RDST state to the abort instruction (ABTI) state.
12' ~3 The AB~I state instracts the device controller 14 41 to ignore the previous LAC and LP~I information passed to it by the I/O channel 109 and then the T bus 16 (channel) returns to the,NOP tidle~ state.

18 If, after the RDST state no error was detected, 1~ tas shown by the dashed line arrow 11~' in the top branch of Fig. 15), the T bus goes to the deselect state (DSEL), 22 With the T bus in the deselect state, the device 23 controller 41 clears its select latch 173 and responds to 24 the instructlon issued to it (passed to it during the LAC
state) and-the T bus returns to the NOP (idle) state.
'26 27 In the operation of the I/O system there are 28 a number of device request signals that can happen 29 asynchronously. For example~ a reconnect signal may be 30 generated after an EIO sequence to request that the !

channel transfer data to the controller. Or the device controller 41 may assert an interrupt request line under a number of diEferent conditions, e.g. to signal the com-pletion of an EIO sequence or to report an unusual condition in a peripheral device.
The device request lines are common to all device controller ports 43 attached to a particular I/O ~us 39.
The channe] 109 responds to reconnect requests made on the line RCI (145 of Fig. 14), and the CPU 105 res-ponds to requests made on the LIRQ line 147 (see also Fig.
14) with an IIO sequence, and to a request made on the HIRQ
line 149 with an HIIO sequence.
The first thing that the channel 109 or CPU 105 does in response to a Device request signal is to determine the identity of the highest priority device controller 41 asserting a request. That is, there may be several device controllers 41 asserting a request to the channel 109 at one time, and the channel will select a particular device con-troller in accordance with a predetermined priority scheme.
In a particular embodiment of the present inven-tion up to thirty-two device contsollers 41 can be connected to a single channel 109, 7~
- 1 The thirty-tt~o d~vice ~ontrollers are 2 connected in a star ~oll using the sixteell bit data 3 bus 161. One additional line 151 is used to divide , 4 the thirty-two device controllers into two groups of sixteen each. One group of sixt~er device controlle~s 6 is assigned priority over the other group; and pricrity 7 is also ~ssigned among the si~,een within each group.
8 The device responding on bit zero of the D bus during a polling sequence has the highest priority within a rank, and the one responding on bit 15 has the lowest 11 priority.
~2 13 In initial intrcduc~ion, it may be noted that 14 polling (which will now be described) involves the state descriptions shown :in Fig. 16 and 17 up to and including ~1~ that,handshake which occurs during the select (S~L) state 17 iIl each figure~
;~ 18 19 With continued general reference to Figs. 16 and 17, the channel 109 sets the rank line to zero and 21 then presents the T bus function RPOL (Fig. 16) if the - 22 response is to a reconnect request, while the CPU 105 23 presents an LPOL ~Fig. 17) T bus function if the CPU is 2~ responding with an IIO sequence, or an HPOL T bus ~unction if the CPU is responding with an HIIO sequence. This 26 is the only major point of difference between the show-27 ings in Fig. 16 (the channel response) and Fig. 17 (the 28 CPU response) with regard to polling.

, 131 q-~

1 ~eferring s~ecifically to ~ig. 16 and the 2 response of the channel 109 ~o assertion of the RCI
3 line 145 (see Fig. l4), all devices ~ h a reconnect 4 request pending that ~Jould respond on rank zero place a cne bit response on the D bus. That is, all these 6 devices assert a line of the D bus 161 correspondins 7 to their priority within the ran~.
9 The channel 109 transfers the D bus response 1~ into the priority resolve register 135 (see Fig. 13).
~ 11 This priorlty resolve register 135 output determines :~ .
12 which device controller has the highest priority (in 13 accordance with the sche~e described above~ and asserts 14 the appropriate bit back onto the D bus 161, if there is a bit asserted in rank zero by the attached device 16 controllers.

18 I~ there are one or more devices asserting a ., 19 response to the priority resolve register on rank zero, 20 the output of the priority resolve register is presented 21 to all device controllers attached, along with the select 22 function (SEL) on the T bus, and the device controller .~
23 whose priority on rank zero matches the output of the 24 priorlty resolve register sets it select bit 173 (see Fig.
25 l9), and then that port will respond to subsequent states ~ in the se~uence. This is the mode of operation indicated 27 by the solid line arrow going from the state indicated - 28 by ~POL with ~ rank equals zero to select (SEL).

:

7~
1 If the priorl~y resolving register 135 2 determines that no device responded when the r~nk li~e 3 equalled zero, then th~ channel 109 sets the rank line 4 to one and xeissues the RPOL T bus command. Then, if 5 the priority resolving regis~er determines that a 6 response occurred on rank 1, the channel asserts the T
7 bus select function as be'ore.

g However, if the priority resolving register 135 de~ermines that no response was made on rank 1, 11 the channel returns to the idle state indicated by 12 state NOP in Fig. 16.

1~ This latter event is an example of a failure which might occur in one port 43 and which would result 16 in the system 31 accessing th2t particular device 17 controller 41 through the other port 43.

l9 As noted above, the action of the priority resolving xegist~r 13S in response to an IIO or an HIIO
21 sequence initiated by the CPU 105 is the same as the 2~ response of the priority resolving register 135 to a 23 reconnect sequence initiated by the channel in response ~4 to a reconnect in on the line 14S from a device ~5 controller 41.

27 With continued reference to Fig. 16, the 28 resonnect sequence begins with the poll sequence described 2g above for reconnecting the highest priority device controller 41 making a request.
' ' . .

, 1 The next st~p in the reconncct sequencc is 2 to determin~ the actual device controller number contained 3 in the device address comparator 193. As noted a~ove, 4 the device addres~ comparato~ 193 include~ jumpers to determine a physical device controller num~er. These 6 are the same jumpers that are used on a LAC ~ bus 7 function during an EIO sequence to determine a particular 8 port. Tn the reconnect sequence the address determined 9 by these ~umpers is xeturned to the I/O channel via the D bus during the T bus ~AC state to access a table de-11 fining the buffer area for this device.

13 It i9 also necessary to determine the direction 14 f the transfer (whether an input or output transfer to the processor module). To accomplish this determination 16 Of the direction or the requested transfer and the device . . .
17 address, the channel asserts the R~C T bus function and 18 the device controller 41 returns the device controller .: .
19 address and the transfer direction.

21 The channel uses the device address returned 22 by the device controller 41 to access a two word entry ' 23 (1423 in an I/O control table (IOC) 140 (Fig. 12) which 24 defines a buffer area 138 in the memory 107 for this particular device controller and device.

- 27 The format of a two word entry 142 is shown 28 enlarged in Fig. 12 to show details of the fields of the 29 two words.

: 13 1 There is a two word entry 142 in th~ IOC
2 table 140 fox each of the ei~ht possi~le devices of c~ch 3 of the thirty-two possible device controllers 41 4 attached to an I/O bus 39 associated ~ith a particular S processor module 33, and each processor module 33 has 6 its own ICC table.
8 Each two word entry describes the buffer 9 location in main memory and re~aining length to be 10 transferred at any particular time for a particular 11 data transfer to a particular device. Thus, as 12 indicated by the legends in Fig. 12, the upper word 13 specifies the transfer address to ox from which the 14 transfer will be made by a burst; and the lower ~ord 15 specifies the b~te count specifying the remaining length 16 of the buffer are2 and the s~atus of the transfer.

18 , The fields representiny the status of the 19 transfer include a protect bit P and a channel error 20 field CH ERX. The channel exror field comprises three 21 bits which can be set to indicate any one of up to 22 seven numbered errors. I
23 ?
24 The transfer address and byte count are up-25 dated in the IOC table 140 at the conclusion of each 26 reconnect and data transfer sequence (burst). The 27 transfer address is counted up and the byte count is 28 counted down at the conclusion of each burst. The 29 amount reflects the number of bytes transferred during 30 the burst.

,7~
1 The second word also contains ~1) a field in 2 which a~y error encountercd during a reconnect and dat~
3 transfer sequence may be posted for later anal~lsis, ~nd 4 (2) a protect bit to specify that the buffer area in 5 memory 107 may be read from but not written into.

7 The protect bit serves to protect the processor 8 memory 107 from a failure in the device controller 41.
9 That is, when the de~ice controll~or 41 returned the 10 transfer direction to the channel 109 during a read 11 address and command (RAC) T bus function, a failure in J 12 the device controller 41 could cause the 2evlce controller 13 to erroneously specify an input transfer. Th~n the 14 channel woula go to the IN state and transfer data from 15 th~ device controller into memory, thus causing data in _. .
~6 the buffer 138 to be lost. The protect bit allcws t~e 17 progxa~ to specify that the channel may not write into 18 this bu~fer area; that is, the device may only specify 19- an output transfer.

21 The transfer address specifies the logical 22 path 139B (see Fig. 12).

24 The channel places the transfer address in 25 the channel memory address register 129 tsee Fig. 13) 26 and places the byte count in the character count register 27 131 (see Fig~ 13~.

29 l' 3~ t , , ' . I

S~

Depending upon the direction of the transEer, (which the channel retrieved from the device during the RAC
state shown in Fig. 16), the channel puts the ~1 bus in either ~he IN state or OUT state and transfers data between the device controller 41 and memory 107 using the channel memory address register 129 to specify the logical path 139C
tsee Fig. 12). The channel memory address register 129 and character count register 131 are updated with each word transferred during the burst to reflect the next address in the buffer and the number of characters yet to be trans-ferred. At the conclusion of a burst the contents of the channel memory address register 129 and of the character count register 131 are wr;tten into the IOC table 140.
In operation, for each word transferred in from the device on an in transfer, the channel 109 accepts the word by the handshake mechanism described above and places the word in the I/O data register 127 (see Fig. 13) and then transfers the word to the buffer area in memory defined by the logical path :L39C (see Fig. 12).
On an out transfer the channel 109 takes a word from the buffer area over logical path 139C and transfers the word to the channel memory data register 125. The channel then transfers the word into the I/O data register 127 (Fig. 13) and handshakes with the device controller which accepts the word into its interface data register 213.

~; ~d.'' i'7~

1 The high speed of the I/O ch~nnel is 2 accomplished b~ pipelining where the word in the I/O
3 data register 127 is handshaken to the device while the 4 channel concurrently requests and accepts the next word in the transfer fxom memory 107 and places it in 6 the channel memory data reqister 125. Since it takes 7 just as long to put a word out to the device as it does to accept a word from memory for the device, the two g operations can be overlapped.
~0 ll During the burst, the channel decremented the 12 character count register by two for every word transferred, 13 since there are two by~es in every word.
' 1~ . .
The burst trans.er can terminate in two ways.
1~ The burst transfer c:an terminate normally or 17 the burst ~ransfer can terminate with an error condition.

19 In the normal case there are two possibilities.

~1 In a first condition of operation, the 22 character count register 131 can reach a count of either 23 one or two bytes remainin~ to be transferxed. In this 24 situation the channel puts up EOT (line 165 as shown in Fig. 14) signifying that the end of transfer has 26 been reached. If the count reaches one, then the channel 27 asserts EOT ~nd PAD OUT ~line 167 of Fig, 14) signifying 28 the end of txansfer with an odd byte.

3~

., .

b If the character count reaches two, the channel puts up EOT, but PAD OUT (PADO on line 167 of Figure 14) is not required because both bytes on the bus are valid.
In either case, the device controller 41 responds by asserting STOP IN tSTI) on line 159 (see Figure 14), and the device controller 41 also asserts PAD IN (PADI ) on line 169 (Figure 14) if the channel asserted PAD O~T (PADO) .
In this first case of normal termination, the transfer as a whole, not just the burst, is terminated by ].0 the channel 109, The other normal completion i5 when the device controller 41 ends the burst by asserting STOP IN (STI3 in response to the channel SE~VICE OUT (SVO). This signifies that the buffer 189 (see Figure 19) has reached a condition of minimum stress (as indicated by poin~ 229 in Figure 23).
The STOP IN (STI) can occur on an output transfer or on an input transfer.
On an input transfer, if the device controller 41 wishes to terminate the transfer as well as the burst, the : 20 device controller 41 can assert STOP IN (STI); and, to signify an odd byte on the last word, the device controller 41 can also assert PAD IN (PADI).

1 As shown in FigO 16 ~ when the transfe~ is 2 terminated by a non-error condition ~STI OR EOT) on 3 either an output transfer or an input transfer (a~ shown 4 by the balloons ou~r and IN in Fig. 16~, the channel 109 updates the IOC table entries as noted above, and 6 .returns to the idle (NOP) state shown in Fig. 16.

8 As noted above, the transfer can also be 9 terminated by an error condition.

~ During the burst several errors may occur as follows.

~ First, the device controller 41 may request an input transfer into a buffer whose protect bit P is 16 set in the IOC table as mentioned above.

18 .5econd, the device controller 41 may not 19 return a PAD IN ~PADI ) signal in response to a PAD OUT
(PADO) signal from the channel 109.

22 Third, the channel 109 may detect a parity 23 error on the D bus 161.

Fourth, the device controller 41 may not 26 respond ~o a S~RVIOE OUT (SVO) signal from the channel 27 109 within the allotted time as mentioned a~ove in the 28 discussion on handshakes.

. ~ ~

3~
1 Fifth, the buffer area spccified by the IOC
2 table entries may cross into a page whose map mar~s it 3 a~sent (see the discussion of the mapping scheme in 4 the memory system).

6 Sixth, a parity error may be detected in 7 accessing the map while accessing the memory during 8 the reconnect in and data transfer sequence. See the 9 description in the memory system relating to th~ parity 10 error check.

~2 Seventh, the memory system may de~ect an un-13 correctable parity error when the channel 109 accesses 14 the memory. See the description of the memory s~stem for 15 this parity error check.

17 Xf any of these error conditions occur, 1~ the channel 109 goes to the abort data transfer state 19 tABTD) as shown in Fig. 16. This instructs the device 20 controller 41 that an error has occurred and that the 21 data transfer should be aborted. 1'he channel 109 then 22 goes back to the idle state which is (NOP) as shown in 23 FigO 16.

When an error occurs, the channel 109 updates 26 the XOC table entries and puts an error number indicating 27 one of the seven errors noted above in the error field ~8 Of the second word of the IOC table entry as mentioned . .
~9 above.

1~1 : _, l Thus, if a single error occurs, the number of 2 that error is entered in the error fi.eld of the IOC
3 table entry.

If more than one erxor occurs, the channcl 6 103 selects the error from which recovery is least 7 likely to occur and enters only the number of that error 8 in the error field of the IOC table entry.

There is one other type of error that can 11 occurO The device controller 41 may try to reconnect 1~ to the channel when the count word in the IOC table is 1~ zero. In this event, the channel will not let the 1~ device cont.roller reconnect and the channel goes through the sequence as descri~ed above with reference 16 to Fig. 16~ but when the channel determines that the 17 count word in the IOC table is zero, the channel 109 ~8 goes directly to the abort (ABTD~ state~ This is an ~9 important feature of the present invention because it 20 protects the processor memory from being overwritten by 21 a failing device.

23 If the count is ze.ro in the byte count count z4 of the 5econd wora of the IOC table entry 142 or a 25 paxticular device, and if the device controller 41 26 attempts to reconnect to the channel 109, the channel 27 issues an abort (ABTD) to the device controller 41 as z~ noted above and leaves the channel errox ield of the 29 two word entry 142 at zero.

1~2 F

tj j1 ~

1 In response to an a~ort data (ABTD~ T bus 2 function, the device controller 41 makes an interrupt 3 request on the line HI~Q or LIRQ (lines 149 or 147 as 4 shown in Fig. 14~ to the channel 109.

6 The device controllers 41 may at any time 7 request an interrupt on these two lines.

9 An interrupt generally indicates that a 10 data transfer has been completed or terminated by an 11 abort from the channel ~an ABT3 from the channel) or 12 by an error condition within the device controller 41 13 or attached device, or that a special condition has 14 occurred within the device controller or an attached 15 device. For example, when the power is applied and the 16 PON circuit indicates tha~ power is at an acc~Qptable 17 level, the device controller interrupts the processor 18 module to indicate that its internal state is Reset 19 because power was off or had failed and has been reset 20 by the PON circuit.

22 In response to an interrupt, the program 23 runnin~ within the processor module 33 issues an interrogate 24 I/O instruction (IIO) or an interrogate high priority 25 I/O instruction (HIIO) over the I/O bus 39 27 The IIO instruction is issued in response to Z8 a low priority I/O interrupt, that is, one issued on 29 the low priority interrupt request (LIRQ~ line 147 (see 30 Fig. 14~.

~ .

1 The IIIIO instruction is issued in response 2 to a high p~iorit~ I/O interruptt tha~ is, one re~uested 3 on a high priority interrupt requcst (~IIRQ~ line 149 4 ~see Fig. 14).

6 The microprocessor 113 (see Fig. 12) executes 7 the EIO, IIO or HIIO instruction by taking control of 8 the channel control logic 141 and data path logic 123.
g ~ The sequence for these instructions is -illustrated in Fig. 17; and, as noted above, the sequence 1~ starts with a polling se~uence.
~3 14 The IIO instruction polls in a sequence using the T bus function low priority interrupt poll (LPOL) 1~ while the HIIO instruction polls in a sequence using 17 the T bus function high priority interrupt poll ~HPOL).

19 The polling sequence which is also described above completes b~ selecting the appropriate device ~1 controller 41 by using the T bus function select (SEL) 22 as shown in Fig. 17.

24 The appropriate device controller 41 selected is that device controller which has the highest priority 26 and is ma~ing an interrupt request.

2g The sequence continues with a read interrupt 29 cause (RIC) T bus function as shown in Fig. 17. The 30 device controller 41 responds by returning device 31 dependent status on the D bus 161 (see Fig. 14).
~4~
. F

76~
] The microprocessor 113 (Fiy. 12) reads the 2 status from the D bus 161 and places the status on the 3 top of the register stack 112 (Fig. 12).

S The sequence then continues with a read ~ interrupt status (~.IST) T bus function as sho~ in 7 Fig. 17. The device controller 41 responds to this RIST
8 T bus function by returning the device controller number, 9 the unLt number and four dedicated status bits on the D bus.
11 ' 12 Of the four bit status field, two of the bits 13 indicate respectively, abort (ABTD) and parity error 1~ (which parity error may have occurred during a reconnect and data transfer sequence~.

17 The microprocessor 113 copies the content o~
18 the ~ bus--the contxoller number, the device number 19 and the interrupt status--and places that content on the 20 top of the register stack 112.

22 . If no error occurred during the sequence, then 23 the sequence continues with the deselect ~DSE~) state 24 which deselects the device controller 41; and then the 25 sequence goes into the idle (NOP) state as indicated by 26 the line at the top of Fig. 17.

~8 If an error did occur ~and the error can be 29 a parity error detected by the channel or a handshake 30 time out3, the channel goes from the RIST state to the 1~5 7~
abort instruction (ABTI) 6t~e as s~o~ in Figure 17. This deselects the device controller 4l, and then the channel 109 goes back into the idle (NOP) state as shown by the bottom line in Figure 17.
As noted above, an I/O operation between a pro-cessor module and an I/O device typically consists of a group of sequences, e.g. an EIO followed by some number of reconnect and data transfer sequences terminating with an IIO sequence. Sequences from several different I/O opera-tions may be interleaved, resulting in apparent si~ultaneous I/O operation by several devices. Thus, a large number of devices may be accessed concurrently; the exact number depends on the channel bandwidth and the actual bandwidth used by each device.
The I~O system and dual port device controller architecture and operation described above provide a number of important benefits.
These benefits include (a) flexibility to inter-~ace a wide variety of devices, ~b) a maximum usage of resources, (c) a fail soft environment in which to access peripheral devices in a multiprocessor system, (d) on line maintenance and upgrade of the multiprocessor system capa-bility, and (e) maximum system through put (as opposed to i emphasizing processor through put or I/O through put exclusivelyl in an on line transaction system in which a large number of concurrent transactions must be processed by the I/O system and CPU.

, .

~ ..

1 Flexibility ~o int~rface a wide vaxiety of ~ devices is achieved because the system of the present 3 invention does not presuppose any inherent characteristics 4 of a device type. Instead, the presen-t invention provides 5 a structure and operation which can accon~odate a wide 6 variety o device operations.

8 ~he present invention provides for a maximum 9 usage o resources, primarily by maXing a maximum usage 10 of memory bandwidth. Each device uses a minimum of the 11 memory bandwidth. This allows a relatively large number 12 of devices to be associated with the particular I~O bus.
13 Because of the inherent speed of the I/O bus, and the 14 bufering technique of the present invention, each 15 particular transfer is made at a relatively high speed 16 limited only by memory speed. Because the transfers are 17 in a burst mode, the overhead associated with each trans-18 fer is minimized. This maximizes the use of the channel 19 bandwidth and also permits the use of high speed devices.

21 The present invention provides for failsoft 22 access to peripheral devices. There are redundant paths 23 to each peripheral device, and contalnment of failure 24 on any particular path. Failure of a particular module 25 in one path does not affect the operation of a modul~
26 in another path to that device~

28 There are comprehensive error checks for 29 checking data integrity ovex a path, sequence failures 30 and timing failures.

1~7 Protection features prevent a peripheral device from - contaminating its own buffer or the memory of the system.
These protection ~eatures include a separate count word in each IOC table and a protect bit in the IOC table. The IOC table is accessible by the channel, but not by the device. This is a second level of protection to prevent the device from accessing any memory not assigned to that device.
The present invention requires only a small number of lines in the I/O bus to provide a flexible and powerful I/O
system.
rrhe operation of the device controller is well defined as power is turned on or off to protect the I/O bus from erroneous signals during this time and also to permit on line maintenance and system upgrade.
The present invention uses stress to allow the buffers to cooperate without cornmunicating with each other.
An on line transaction system is obtained through overlapped transfers and processing.
Multichannel direct memory access provides inter-leaved bursts to give overlapped transfers and minimum waitsfor accesses to a device. Each burst requires a minimum memory overhead and allows the processor to make maximum use of the memory. This combination allows maximum use of the I/O band-width and minimal tie up of the processorc - 148 ~

7~ -1 POWER DISTRI3UTION SYST~
3 The multiprocessor syste~ of the present 4 invention incorporates a power distribution system that 5 over comes a.numher of problems associated with prior 6 art Systems.

.
8 In many prior art systems it was necessary to g stop the processor system in order to perform required 0 maintenance on a component of the system. Also, in many pr.ior art systems, a failure in the power supply could ~ stop the entixe processor system.

14 The power distribution system of the present 15 invention incorporates a plurality of separate and 16 independent power supplies and distributes the power 17 from the power supplies to the processor modules and to ~8 the device controllers in a way that permits on-line 19 maintenance and also provides redundancy of power on ~o each device controller.

~4 ~8 1 In this regard "on-line" is used in the sense 2 that when a part of the system is on-line, that part of 3 the system is not only powered on, but it is also function-4 ing with the system to perform useful work.

6 The term "on-line maintenance" therefore means 7 maintaining a part of the system (including periodic 8 preventative maintenance or repair work) while the 9 remainder of the system is on-line as defined above.
~ .
In the present invention any processor module 12 or device controller can be powered down so that on-line 13 maintenance can be performed in a power off condition 14 on that processor module or a device controller while the lS rest of the multiprocessor system is on-line and functional.
16 The on-line main~enance can be performed while fully 17 meeting Underwriters Laboratory safety requirements.

lg ~9 150 ~---1 Also, in the power distribution system of 2 the present invention each device controller is connected ~
3 for supply of power from two separate power supplies 4 and by a diode switching arrangement that permits the 5 device controller to be supplied with power from both 6 power supplies when both power supplies are operative and to be supplied with power from either one of the power 8 supplies in the event the other power supply fails; and 9 the changeover in the event of failure of one of the 10 power supplies is accomplished smoothly and without any 11 interruption or pulsation in the power supply so that an 12 interrupt to a device controller is never required in 13 the event of a failure of one of its associated power 14 Sllpplies.

16 A power distribution system for insuring both 17 a primary supply and an alternate power supply for each 8 indivi~ual dual port de~ice controller 41 is illustrated 1~ in Fig. 30. The power distri.bution system is indicated 20 generally by the reference numeral 301 in Fig. 30.

22 . The power distribution system 301 insures 23 that each dual port device.controller 41 has both a 24 primary power supply and an alternate.power supply.
25 Because each device controller does have two separate 26 and independent sources of power supply, a failure of 27 the primary power supply for a particular device controller 28 does not render that device controller (and all of the 29 devices associated with that con~roller) inoperative.
30 Instead, in the present invention, a switching arrange-, f~
- ~\

ment provides for an automatic switchover to the alternate power supp]y so that the device controller can continue in operation. The power distribution system thus coacts with the dual port system of the device controller to provide continuous operation and access to the devices in the event of a failure of either a single port or a single power supply.
The power distribution system 301 shown in Figure 30 provides the further advantage that each processor module 33 and associated CPU 105 and memory 107 has a separate and independent power supply which is dedicated to that processor module. With this arrangement, a failure of any one power supply or a manual disconnection of any one power supply for repair or~servicing of the power supply or asso-.;................................................. ~ .
ciated processor module is therefore limited in efect to only oneparticular processor module and cannot affect the operation of any of the other processor modules in the multiprocessor system.
~ The power distribution system 301 shown in Figure 30 thus -`1 works in combination with the individual processor modules and the ~ dual port device controllers to insure that a failure or disconnec--' tion of any one power supply does not shut down the overall system or " 20 make any of the devices ineffective.
The power distribution system 301 includes a plurality of separate and ind~pendent power supplies ' .

:``
."''' ~' . . .

i ~152 ... . .

1 303, and each power supply 303 has a line 305 (actually 2 a multiline bus 305 as shown in ~ig. 33) whicn is 3 dedicated to supplying power to the CPU and memory of 4 a particular~ related processor module.
. :
6 Each device controller 41 is associated with 7 two of the power supplies 303 throu~h a primary line 307 8 and an alternate line 30g and an automatic switch 311.

A manually operated switch 313 is also associated with each device controller 41 between the 1~ device controller and the primary line 307 a~d the 13 alternate line 309.

The switches 311 and 313 are shown in more 16 aetail in Fig. 31.

18 FigO 32 shows details of the component ~g cons~ruckion of a power supply 303.

21 As shown in Fig. 32, each power supply 303 22 has an input connector 315 for taking power ~rom the 23 mains. The input 315 is connected to an AC to DC
24 converter 317, and the output o~ the AC to DC converter 25 provides, on a line 319, a five volt interruptable 26 power suppl~ (IPS). This five volt interruptable power 27 supply is supplied to the CPU 105, the memory 107 and 2~ the device controller 41. See also Fig. 33.

- The AC to DC converter 317 also pro~ides on a second input line 321 a sixty volt DC output which is supplied ~o a DC to DC con-verter 323. See Figure 32.
The DC to DC converter in turn provides a five volt output on a line 325 and a twelve volt output on a line 327.
The outputs from the lines 325 and 327 are, in the system of the present invention, uninterruptable power supply (llPS) outputs in that these power supply outputs are connected to the CPU and memory when semi-conductor memory is used. The power supply to a semi-con-ductor memory must not be interrupted because a loss of power to asemiconductor memory will cause loss of all data stored in the memory.
The five volt interruptable power supply on line 319 is con-sidered an interruptable power supply because this power is supplied to parts of the multiprocessing system in which an interruption of power can be accepted. Thus, the five volts interruptable power is supplied to parts of the CPU other than semiconductor memory and to only those parts of the memory which are core memory (and for which a loss of power does not cause a loss of memory) and to the device con-troller which (as will be described in more detail below) is supplied with an alternate source of power in the event of a failure of the primary power supply.

. ~ .
.

' '~ ' -15'~-.''1 .

- 1 Since the power supply on lineS 325 and 327 2 m~st be an uninterrupt~ble power suppl~, _hc ~rcscnt : 3 invention provides a battery back-up for the inr)ut to 4 the DC to DC converter 323. This battery back-up 5 inclùdes a battery and charger module 329. The module 6 329 is connected to the DC to DC converter 323 by a . 7 line.331 and a diode 333.

g In a particular embodiment of the present 10 invention the battexy 323 supplies power at 48 volts ~1 to the converter 323, which ls within the input range 12 Of the converter 3230 1~ The diode 333 insures that power from the 15 battery is supplied to the converter.323 if the voltage 16 on the line 321 crops below 48 volts. The diode 333 17 also stops the flow of current ~rom the battery and 1~ the line 333 when the output of the AC to DC converter . 19 on line 321 exceeds 48 volts.

21 Each power supply 303 also includes a power 22 warning circuitry 335 for detecting a condition in the AC power input on line 315 that would result in in-24 sufficient power out on the output lines 319, 325 and 25 327. The power warning cixcuit 335 transmits a power 26 failure warning signal on a line 337 to the related 27 CPU 105.

~9 Because of the capac.ity storage in the power : 30 supply 303, there is enough time between the power warn-., :. .

'7~ .
b 1 ing signal and the loss of the five volts int~rru~t~ble 2 power on line 319 for the CPU to save its s~a~e - 3 before the power is lost.
S However, the uninterruptable power sup~ly on 6 lines 325 and 327 must not be interrupted, even for 7 an instant of time; and the battery back-up provided 8 by the arrangement shown in Fig. 32 insures that there g is no interruption in the power supply on lines 325 10 and 3~'7 in the event of a power failure in the input 11 line 315.

13 One particular power supply 303 itself can 14 fail for some reason with the other power supplies 303 15 skill operating. In that event, the power distribution 16 system 301 of the present invention limits the effect ~, 17 of the failure o the power supply 303 to the loss of 18 one particular, associated CPU and memory; and the auto-19 matic switch 311 provides for an aut~matlc swi~chover ~: 20 from the failed power supply to the alternate power 21supply to keep the associated device controller 41 in 220peration. The device controller 41 which haA been ~; 23connected to the failed power supply therefore continues 24in operative association with the other processor modules - 25and components of the multiprocessor system, because the 26required power is automatically switched ln from the 27alternate power supply-28 .
29 As best illustrated in Fig. 31, each automatic ;30switch 311 includes two diodes--a diode 341 associated with - ~56 - ~r c 1 the primary power line 307 and a diode 343 associated with 2 the alternate power line 309.

4 The function of the diodes 341 and 343 is to per-S mit power to be supplied to a device controller 41 from 6 either the primary power line 307 and a related power supply 7 303 or the alternate power line and its related power supply 8 303 while keeping the supplies isolated. This prevents a 9 failed power supply from causing its associated al~ernate 70 or primary from failing.

12 In normal operation each diode permi-ts a certain ~3 amount of curren~ to flow through the diode so that the 1~ power to each device contrcller 41 is actually being 15 supplied by both the primary a~d alternate power supplles 16 for that device controiler.

18 ' In the event that-one of the power supplies 19 fails, the full power is supplied by the other power supply, 20 and this transition occurs without any loss of power at all.

22 Since there is a small voltage drop across the ! 23 diodes 341 and 343, the voltage on the lines 307 and 309 24 must be enough higher than five volts to accomodate the 25 voltage drop across the diodes 341 and 343 and still 26 supplv exactly five volts to the device controller 41.
27 The lines 305 are in parallel with the lines 307 and 309, 28 and the power actually received at the CPU in memory must 29 also be five volts; so balancing diodes 339 are located 30 in the lines 305-to insure that the voltage after the diodes 31 339 as supplied to each CPU is exactly ~ive volts.

'7~3 The manual switch 313 permits a device controller 41 s~ to be disconnected from both the primary and the alternate power sources when the device controller needs to be discon-nected for removal and service.
Details of the construction of the switch 313 are shown in Fig. 31. As shown in E`ig. 31, the switch 313 includes '9 a manual switch 345, a transistor 347, a capacitor 348 and a resistor 350 and a resistor 352.
The manual switch 345 is closed to turn on the tran-- 10 sistor 347 which then supplies power to the device control-ler 41.
It is important that both the turn on and the turn off of power to the device controller 41 be accomplished in a smooth way and without fluctuations which could trigger the PON
circuit 182 more than once. The feedback capacitor 348 acts in conjunction with the resistor 352 to cause the required smooth ramp build-up of power when the switch 345 is closed to turn the transistor 347 on.
When the transistor 347 is turned off by opening the switch 345, the feedback capacitor 348 acts in conjunction with resistor 350 to provide a smooth fall off of power.

.~

In a preferred embodlment of the invention all of diodes 341, 343 and 339 are Schottky diodes which have a very low forward voltage drop, and this reduces power dissipation.
As noted above in tlle description oE the I/O system and dual port device controller 41, each device controller 41 does have a power on circuit (PON) 182 for detecting when the five volt power is below specifications. The PON circuit 182 is shown in more detail in Figure 25 and resets the device controller 41 to lock everything off of the device controller and holds the device controller itselE in a state that is known when the power is turned off by the switch 313. The PON cir-cuit 1~2 also releases the device controller and returns it to operation after the power is turned on by switch 313 and five volt power supply at the proper specification is supplied to the device controller ~1.
Further details of the power on circuit 182 shown in Figure 25 are described above in relation to the I/O and dual port controller system.
With reerence to Figure 33, the power from each power supply 303 is transmitted to a related CRU by the vertical bus 305, and each vertical bus 305 is a laminated bus bar which has five layers of electrical conductors.

. . .

r,~, ~.

!, - As indicated by the legends in Figure 33, each vertical bus 305 has two different conductors connected to ground.
One conductor provides the ground or both the five volt interruptable power supply (PS) and the five volt uninterruptable power supply (UPS).
A separate conductor provides a ground for the memory voltage.
This separate ground for the memory voltage insures that the relatively large fluctuations in current to the memory will not have any effect ~ on either the five volt IPS or the five volt UPS supplied to the CPU.
'i 10 The horizontal bus 307J 309 includes the primary and alternate ~, .
~' power supply lines 307 and 309 (as indicated by the reference numerals in Figure 30). In a particular embodiment of the presént invention the bus 307, 309 is actually a nine layer laminated bus which has a single ground and eight voltage layers (Vl through VS as indicated by the legends and no~tations in Figure 33).
~ Each voltage layer is connected to the five volt interruptable " output of a different power supply 303. Thus, the layer Vl is connec-'1' ted at 351 to the five volt IPS power for the power supply 303 and re-lated processor module farthest to the left as viewed in Figure 33, O and the 1ayer V2 is conn-cted ae 353 to the five volt IPS powe~ supp1y ~' ' ' '.

., .
.

! -160 ' - 303 for the processor module at the center as viewed in Figure 33, and so on.
Since there are eight layers (Vl through V8) and a common ground available to each dcvice controller in the horizon-tal bus, upstanding vertical taps 355 to these eight layers at spaced intervals along the horizontal bus permit each device controller 41 to be asso-ciated with any two of the power supplies 303 merely by connecting the primary line 307 and the laternate line 309 to a paTticular set of taps, By way of example, the device controller 41 on the lefthand side o~ Figure 33 is shown connected to the taps V2 and V3 and the device controller 41 on the righthand side of Figure 33 is shown connected to ,~
the taps V2 and V3.
Thus, any device controller 41 can be connected to any two of the power supplies 303 with any one of the power supplies serving as the primary power supply and any one of the other power supplies serving as the alternate power supply.
The power distribution system of the present invention thus ` provides a number of important benefits.
'r The power distribution system permits on line maintenance to be performed because one processor module or device controller can be powered down while the rest of the multiprocessor system is on line and functional.

,~ .

-161_ f t;~

1 The power distrlbution s~stem full~ meets all 2 Underwriter Laboratory safety requirements for doing on 3 line maintenance of a powered down component while the 4 rest of the multiprocessor system is on line and in 5 operation.

7 Each device controller is associated with two 8 separate power supplies so that a failure in one of the g power supplies does not cause the device controller to stop operation. Instead, the electronic switch arrange-ment of the present invention provides such a smooth 12 transition of power from the two power supplies to only 13 one of the power supplies that the device controller is 4 maintained in continuous operation without an interrupt.

19 ..

2~ _ 2~
zg , ..

, . . .

.. .

~ f 1 M~IOP~Y SYST~
c 2 3 Each processor module 33 (see Fig. l) in thc 4 multiprocessor system 31 contains a memory.

: .
6 This memory is indicated by the general 7 reference numeral 107 in Fig~ l and is shown in greater 8 detail in Fig. 34.

The memor~ 107 of each processor module 33 ~1 is associated with both the CPU 105 and the I~O channel l2 109 of that module. There LS a dual port access to 13 the memory by the CPU and the channel. Tha~ is~ the 14 CPU 105 (see Fig~ 1 and Fig. 34) can access the memory 15 for program or data references, and the I/O channel 16 109 can also access the memory directly (without having 17 to go through the CPU~ ~or data transfers to and from a 18 device controller 4:L. This dual access to the memory l9 is illustrated in Fig. 34 and will be described in 20 greater detail below in the description o the Fig. 34 21 structure and operation.

23 One beneit of this dual access to the 24 memory is that CPU and channel accesses to the memory ~5 can be interleaved in time. There is no need for ~S either the CPU or the channel to wait for access to 27 the memory, except in the case where both the CPU
28 and the channel are trying to access the memory at ~9 exac~ly the same time. As a result, both the CPU and 30 the channel can be performing their separate functions ~3 , 1 simultaneously, subject .o an occasional wait by the 2 CPU or channel if one o~ these units is accessing 3 the memory at the e~act time the other unit needs to 4 aceess the memory.

6 The dual port access also allows bac]:ground 7 I/O operation. The CPU 105 needs to be involved with 8 the ehannel 109 only in the initiation and termination g of I/O data transfers. The CPU ean be performing other functions during the actual I/O data transfer itself.
11' 12 The memory 107 shown in Fig. 34 comprises a 13 physieal m~mory whieh eonsists of up to 262,144 words 14 O~ sixteen data bits eaeh.

~6 In addition to the sixteen data bits, eaeh 1~ word in memory has an additional parity bit if the ~8 memory is a eore memory or six additional error eorreetion 1~ bits- if the memory is a semieonduetor memory.

21 The parity bit permits deteetion of single 22 bit errors.
~3 24 The six error eorreetion bits permit deteetion 25 and eorreetion of single bit errors and also permit 26 deteetion of all double bit errors.

28 The physieal memory is coneeptually subdivided 29 into eontiguous blocks of 1024 words eaeh (which are 3~ ealled pages). The pages in physieal memory are numbered 16~ F

~ ~ f 1 consecu~ively from paqe zero, starting at physlcal 2 location zero. The address range of physical memory 3 in one specific e~bcdiment of the present invention, 4 which address range is zero through 262,143, requires eighteen bits of physical address information.
` 6 7 The basic architecture of the present 8 invention is, ho~ever, constructed to accom~odate and ~ utilize twenty bits of physical address information, as 10 will become more apparent from the description to follow.
11 ' ' .
12 In one specific embodiment or the lnvention 13 the physical memory is physically divided into physical 14 modules of 32,768 words. Thus, eight of these modules provide the 262,143 words noted above.

7 All accesses to memory are made to one of 18 four logical address areas--user data, system data, user 19 code and system code areas. All CPU instructions deal 20 with these logical (as distinct from physical) addresses 21 exclusively. Thus, a programmer need not be concexned 22 with an actual physical address but can instead write 23 a pro~ram based entirely on logical addresses and the 24 logical addresses are translated by the map section of 25 memory system into physical add:resses ~7 The range ~af addressing in any given logical 2~ address area is that of a sixteen bit logical address, 29 zero through 65,535. Thus, each logical address area 30 comprises sixty-four logical pages of 1024 words each.

.

.... . .

f -l In the memory system of the present 2 invention there is no required corres~ondence between 3 a logical page and a physical page. Instead, the 4 various logical pages comprising an operating syst~m 5 program or a user ~rogram need not reside in conti~uous physical pages. In addition, the logical pages necd 7 be in physical main memory but may be in secondary 8 memory, such as on a disc.
.~ .

This allows implementation or a virtual 11 memory scheme.
1:~ , 13 Virtual memory has two benefits.
1~ .
First, virtual memQry allows the use of a physical ~ç main memory space which is smaller than the logical address .. .
17 areas would require~ because the physical memory can be 18 supplemented by a secondary physical memory.

Secondly, virtual memory permits address spaces 21 Of a plurality o~ users (multiprogramming~ to share the 22 physical memory, and each user does not have to be con- ~
23 cerned with the allocation of physical memory among the 2~ operating system, himsel , or other users.

26 The memory system of the present invention 27 provides protection between users in the multiprogramming 28 environment by guaranteeing that one user program cannot 29 read from ox write into the memory space of another 30 user program. This is accomplished by ~he paging and . .

7~7~ ' 1 mapping system. When one user program is running, the 2 map for th2t user proyram p~ints only to the m~mory pages 3 (up to sixty-four pages of code and sixty-fo~r pages of 4 data) for that particular user prosram. Th2t particular -5 user program cannot address outside its own logical 6 address space and therefore cannot ~rite into or read 7 from the memory space of another user program.

9 The fact that code pages are non-modifiable 10 also prevents a user program from destroying itself.
lL
12 Thus, there are two levels of protection for 13 user programs operating in a multiprogram~ing environment--14 the ~act that each user map points only to its own pages 15 in memory and the fact that code payes are non-modifiable~
16 Also, in the present invention, this protection is 17 achieved without protection lLmit registers or by protection 18 keys as'often used in the prior art~

The required translation of a sixteen bit 21 logical addres to an eighteen bit physical address is 22 accomplished by a mappiny scheme. As part of this 23 mapping scheme, a physical page number is obtained by 24 a look-up operation within a map. This physical page 25 number is then combined with the address within a page 26to form the complete physical memory address.

.;. ' .

~ ~ ~f 7~

1 Only the page number is translated. The 2 offset or address ~ithin a pa~e is never chanqed in 3 the mapping.

In the present invention there are four ~ map sections. Each map section corresponds to one 7 of the four logical addressing areas (user data, 8 system data, user code and system code).

~ 9 The separation of the logical address into 1~ these four separate and distinct areas provides ~2 significant henefits.

14 The separation provides isolation of programs from data so that programs are never modified. The 16 separation also provides isolation of system programs i 17 and data from user programs and data, and this pro~
t- 18 tects the operating system from user errors.

2Q The four map sections are designated as 21 follows 23 Map ~--user data map. A11 addresses to 24 variable user data areas are translated through this user data map.

27 Map 1 -system data map. The s~stem data ~8 map is similar to the user data map and in addition, 29 all memory references by either the I/O channel, the interprocessor bus handling microprogram, or the interrupt .f .r--1 handling microprogram specifies this map. ~he system 2 data map provides channel access to all of physical 3 memory via only a si~teen bit address word.

Map 2- user code map. This map defines the -6 active user program. ~11 user instructions and constant 7 data are obtained via this user code map.

9 Map 3--system code map. This map defines 10 thP operating system program. All operating system 11 instructions and constant da~a are obtained via this 12 system code map.

14 Each map section has sixty-four entries 15 corresponding to the sixty-four pages possible in 16 each logical address area. Each entry contains the 17 following information.

19 tl) The physical page number field (which 20 can have a value of zero through 255).

22 (2) An odd parity bit for the map entry.
23 The parity bit is generated by the map logic whenever 24 a map entry is written.

Z6 t3) A reference history field. The 27 reference history field comprises reference bits, 28 and the high order bit of the reference bits is set 29 to a "one" by any use of the page corresponding to 30 that map entry.

,, , _.=

1 ~4) A dirty bit. The dirty bit is set to 2 a "one" when a write access is made to the correspond-3 ing memory page.
.
The reference bits and the dirty bit are 6 used by the memory manager function of the operating 7 system to help select a page for overlay. The dirty bit also provides a way to avoid unnecessary swaps of data pages to secondary memory.
~0 11 (5~ An absent bit. The absent bit is 12 initially set to a 'lone" by the operating sys~em to - 13 flag a page as being absent from main memoryO An 14 access to a page with this bit set to "one" causes 15 an interrupt to the operating system page fault interrupt l~ handler o activate the operating system virtual memory 17 manager function. The absent bit is also used as a 18 protection mechanism to prevent erroneous access by a 19 program outside its intended logical address area for 20 either code or data.

22 Three instructions are used by the operating _~
23 system in connection with the map. These three 24 instructiOnS are SMAP, ~M~P, AMAP.
2~
26 The SMAP ~set map entry~ instruction is used 27by the memory manager function of the operating system 28to insert data into a map entry. This instruction 2gre~uires two parameters--the map entry address and - 30the data to be inserted.

. ' .

f ?~ .
The ~ ~P (read map en~r~) instruction is 2 used b~ the memor~ manager functior. of the operating 3 system to read a map entr~. This instruction requires 4 one parame er, the map en~ry address, and thc result returned by the instruction is the map entry content.

7 The A~P (age map entry) instruction causes 8 the reference history field o~ a map entry to be shifted 9 one position to the right. This is used by the memory 10 manager function of the operating system to maintain rererence history information as an aid in selecting a 12 page for overlay.

14 A page fault interrupt provided by the absent ~5 bit occurs when a reference is made to a page that does not 16 currently reside in main memory or which is not part of the 17 logical address space of the program or its data. When a .
18 pa5e fault is detected, an interrupt through to the operat-1~ ing syslem page fault interrupt handler occurs.

21 The page fault interrupt sequence includes 22 the following events:

~3 .
24 1~ An address reference is made to a page ~5 that is absent from physical memory (absent bit - "o~e").

27 2. The page fault interxupt occurs. The 28 interrupt handler microcode places an interrupt para-~g meter indicating the map number and the logical page 30 number in a memory location known to the operatin~

, l system, Then the current environment is saved in an 2 interrupt stac~ mar~er in memory.

4 3. The page fault interrupt handler e~ecutes.
5 If the page fault occurred because of a reference out-6 side the logical address space of the program, then the 7 program is termina~ed with an error condition. On the 8 other hand, if a page fault occurred because the logical 9 page was absent from physical main memory (but present in 10 secondary memory~, an operating system pxocess executes 11 to rPad the absent page from the secondary memory (usually 1~ discj to an available page in primary memory . ~hat ~3 physical page information and a zero absent bit are inserted 1~ into the map entxy. When this memory management function 15 completes, the environment that caused the page fault is 16 restored.
, ~ ~
.J ~ .
~, 18 4. The instruction previously causing the page 19 fault is reexecuted. Since the absent bit in the map 2~ entry of the logical page has now been set to a "zero", 21 a page fault will not occur, the page address is trans-22 lated to the physical page just brought in from secondary 23 memory, and the instruction completes.

As noted abo~e, the I/O channel has access 26 to the memory through its own port.

28 Data transfers to and from memory by the I/O
~: ................................................................ ..
29 channel are via the system data map. That is, the six-30 teen bit logical addresses provided by the I/O ohannel ~, 31 are translated to an eighteen bit physical address by 32 means of the system data map.

~ ~5~
Thus, the mapping scheme allows I/O access 2 to more words of physical memory than its address 3 counter ~ould normally allow.

S In one specific embodiment of the present 6 invention 262,144 words of physical memor~ (for an 7 eighteen bi' address) can be accessed with only a 8 sixteen bit logical address ~y going through the map.
g The extra address information ~the physical page information) is contained in the map and is supplied Y ~he operating system before each I/O transfer is ini~iated.

13 As will become more apparent from the 14 detailed description to follow, the present invention is also readily extendible to a twenty bit physical address.

ig. 34 is a bloc'~ diagram showing details 19 Of the memory 107 of â processor module 33 and showing al5o connections fxom the memory 107 to the CPU 105 21 and the I/O channel 109 of that processor module.
~2 , 23 As illustrated in Fig. 34, the memory system 24 107 pro~ides access ports for both the CPU 105 and the I/O channel 109 to the memory 107, and the I/O channel 26 109 therefore is not required to access the memory 27 through the CPU 105.

29 The memory 107 includes map memory control logic 401 which controls initiation and completion . .
31 of access to physical memory modules 4n3.

'7~
1 The memory 107 also includes a data path 2 section 405 containing registers (as indicated by 3 the legends in Fig. 34 and described in detail below) 4 whlch supply data to ~e written to memory and which S hold data read from memory.

7 The memory 107 also includes a map section 8 407. The map section 407 includes logical address 9 registers from both the CPU and the channel and a map 10 storage 409 from which physical page numbers are obtained.

2 The map section ~Oi thus contains a processor 13 memory address (P~A~ register 411 and a channel memory 14 address (CMA) resister 129.

16 These two registers are connected to an 17 address selector ~15.

19 The address selector 415 is connected to the 20 map 409 by a logical page address bus 417, and the address 21 selector 415 is also connected d~rectly to the memory 22 modules by a page offset bus 419.
~3 24 As indicated by the numerals 8 and 10 adjacent 25 to the buses 417 and 419, the logical page address bus ~6 ~17 txansmits the eight high order bits to the map 409 27 for translation to a physical page number, and the page 28 ofset bus 419 transmits the ten low order bits (of an 29 eighteen page address from the address selector 415) to 30 the memory modules ao3.

~7 .

1 An output ~us 421 supplies the physical page 2 address to the modules 403. This output bus 421 con-3 tains the translated eight high order bits for the 4 address of the physical page.

6 The data path section 405 contains the follo~-7 ing registers: A processor memory data (PMD) register 8 423; a channel memory data (CMD~ register 425; a next 9 instruction (NI) xegister 431; a memory data (MD) 0 xegister 433; and a channel data (CD) regis~er 125.
~` 11 , i 12 The outputs of the PMD and C~D registers 13 are supplied to a data selector 427. This data 14 selector 427 has an output bus 429 which supplies data 15 to be written to memory in the modules 403.

. 17 Data read out from one of the memory modules . 18 403 is ~read into one of the three data registers NI, :,.............................................. .
19 MD and CD over a bus 437.

21 As illustrated in Fig. 34, the map memory 22 control logic 401 is also connected with each of the 23 memory modules 403 by a bus 439. The bus 439 comprises 2~ command lines which initiate read or write operations, 25 completion signals from the memor~- modules, and error ~6 indicators or flags.

~7 28 With reference now to Fig. 35, the map section 29 407 includes, in addition to the map 409, a map page register 30 441, a map output latch 443, a map memory data (~D) '' ~` f-f 1 register 445, a map data selectcr 447, a ~ap parity 2 generator 449, a map parity checker ~51, reference 3 bit logic 453, and dirty bit logic 455.

The map memory con~rol logic 401 is shown 6 in Fig. 35 as associated with the map section 407 by 7 control signal lines 457.

9 The map memory control logic 401 controls 10 the loading of registers and selectlon of registers by ll-the selectors, controls (in conjunction with map absence 12 and parity error outputs) the initiation of memory 13 modules 403 operations, and provides interrupts to the 14 CPU 105 (as indicated by the page fault and map parity 15 error interrupt signals indicated by the legends in 16 Fig. 35)--all as will be described in more detail below.

18 In a particular embodiment of the invention the l9 memory system shown in Figs. 34 and 35 utilizes a physical 20 page address field of eight bits and a page offset of ten 21 bits which combine to give a total eighteen bits. As noted 22 above, the numbers 8, lO, 12, 13, 14 and 18 which are not 23 in parenthesis on certain bus lines in Fig. 34 and Fig. 35 24 relate to this specific eighteen bit implemented embodi-25 ment of the present invention. ~owever, the memory system 26 is easily expandable to a twenty bit implemented embcdi-27 ment (with a physical page address of ten bits) and this 28 is indicated by the numbers (lO~, (123, (14), (15), ~16) 29 and (20) which are within parenthesis on the same bus 30 lines of Fig. 35.

~ f 1 Fig. 36 illust~ates the organi,atio~ of 2 lcgical memory in four separate and distinct losical 3 address areas 459, 461, ~63 and 465. These four 4 logical address areas are: user data area 459;
system data area 461; user ccde area 463; and system ~ code area 465.

.7 8 Fig. 36 also illustrates the four map sections g corresponding to the logical address areas.
~0 .~
11 Thus, the user data map section 467 corres-12 ponds to the logical user d~ta address area 459, the 13 system data map section 469 corresponds to the logical 14 system data address area 461, the user code map section 471 corresponds to the logical user code address area 16 463 and the system code map section 473 corresponds to 17 the logical system code address area 465.

18 c lg As also illustra~ed in Fig. 36, each map . .
section has sixty-four logical page entries (page zero 21 through page sixty-three), and each map entry comprises 22 sixteen bits tas illustrated by the enlarged single Z3 map entry in Fig. 36).

As indicated by the legends associated with 26 th~ enlarged map entry shown in Fig. 36, each map 27 entry comprises a ten bit physical page number field, 28 a single parity bit P, a refexence history field 29 comprising three reference bits R, S and T, a single dirty bit D,and a single absent bit A.

~f 1 The physical page number field provlded by 2 the ten high order bits provides the physical pacJe 3 num~er corresponding to the logical page called for 4 by the program.

S
~ The parity bit P is always generated as odd 7 parity to provide a data integrity check on the map 8 entry contents.
g The reference history field bits R, S and T
11 are used by the memory manager function of the operating 12 system to maintain reference history information for 13 selecting the least recently used page for overlaying.

The R bit is set to a one by any read or 16 write operation to that logical page.
~7 18 The S and ~ bits are storage bits which are 19 manipula~ed by the ~ age a map entry~ instruction.

21 The dirty bit D is set to a one by a write access 22 to that logical page. The operating system uses the dirty -~
23 bit to determine whether a data page has been modified 2~ since it was last brought in from secondary memory.

26 The absent bit A is set to a one by the operat-27 ing syst~m to flag a logical page which is absent from 28 main memory but present in secondary memory or to flag 29 a page which is outside the logical address area of 3Q that user.

., .. .

k~
l The two high order bits for the map entry 2 shown in Fi~o 36 are not used in the specific embodiment 3 of ~he invention illustrated ln the drawings, bu~ these 4 two bits are used when the full twe~ty bit physical ! s addressin~ is used.
: 6 7 As noted above, three instructions are used 8 by the operating system in connection with the map.
9 These three instructions are: S~P, RMAP and ~AP.

11 The SMAP lnstruction is used ~y the memory 12 manager function of the operating system to insert data 13 into a map entry like that illustrated in Fig. 36.

~he SMAP instruction is implemented by the 16 microprogram 115 (F-g. 12~ in ~he CPU 105. The micro-17 program interacts with the map memory control logic 401 18 (see ~ig. 34), first of all, to select (with the first 19 instruction parameter)a location in the map 409 and ~0 then, second, to insert in -that location the second 21 instruction parameter -the new map entry data.

~3 In operation, and referring to Fig. 35, in 24 the first step in the sequence the microprogram llS
loads the new map entry data into the processor memory 26 data ~PMD) register 423.

28 In the next step in the sequence, the map 29 address, including two high order bits for map selection~
are loaded into the processor ~emory address (PMA~
31 register 41l.

.

~_ \ r~

1 At this poin-t the two instruction parameters 2 containing the map entry address and the data to be 3 .inserted have been loaded in their respective regist~rs 4 411 and 423.

6 Next, the microprogram 115 in th~ CPU i05 7 initiates a map write operation sequence of the map 8 memory control logic 4~1. This map write operation 9 seguence is initiated after any previous memory operations 10 have been completed.
~
12 The steps noted above in the operation 13 sequence have all been performed by the microprogram 14 (the firmware).
16 The remaining actions of the S~P instruction 17 are performed under the control o~ the map memory control 18 logic. Thus, the remaining actions are all performed 19 automatically by hardware.
~0 21 In the map write ope~ation sequence, the map 22 address is transmitted from the P~ register through the 23 address selector 415 over the bus 417 to the map 409.
24 Only the eight high order bits (the map select and map 25 address) are used in this operation.

27 The two hi~h order bits specify the map 28 selection--whether user data, system data, user code 29 or system code.

, 1~0 , . .
., 1 The tcn low order bits of the logical 2 address bus from the address selector (~S~Lj 415 3 (which bits are the offset within a page for a memory 4 read or write access) are not used 1n this operation.

6 As the map is being addressed as described 7 above, the new map data is transmitted from the P~ID
8 register 423 through the map data selector 447 to the g map parity generator 449 and to the map 4 0 9 . ~he map 10 parity generator computes odd parity on the new map ~ data and supplies this parity bit ~o the map.

13 Now, at this point, the map memory control 14 logic 401 generates a map write strobe signal ton one 15 Of the lines indicated by ~57 in Fig. 35~ to the map 409 16 which causes the new data and parity to be written into 17 the selected map section at the specific map entry 18 selected by the logical page address on the bus 417.

'lg This completes the SMAP instruction sequence.
~1 22 At the end of this SMAP instruc-tion the proper 23 map section has been selected, the particular logical 24 page entry on that map section has been selected, the 25 data and computed odd parity have been supplied to the 26 map, and the map write strobe has caused that data to be 27 written at the desired map entry.
2g 1~1 ,, ~-~ .
.. . .

~5~'7~
.
1 The SMAP instruction (5~P~ is used by the 2 operating system to initialize each losical page entry 3 in each of the four map sec~ions as required.

One use of the set map instruction is there-6 for to insert a physical page address for a logical 7 page to provide for translation of logical page numbers 8 to physical page numhers after a page has been swapped 9 in from secondary memory.

......
11 Another use of the set map instruction is to 12 set on an absent ~it for a logical page swapped out to 13 secondary memory.

The read map (~P) inslruction is used by I6 the memory manager function of the operating system to 17 examine the content of a map entry.

19 In this ~P instxuction the microprogram 115 20 in the CPU 105 interacts with the map memory control 21 logic 401 to select twith the instruction parameter) a 2210cation in the map 409 and to return to the register 23stack 112 (see FigO 123 as a result of the content of 24that map entry.

26 In the operation of the read map (RMAP) ~7instruction, referring to Fig. 35, the microprogram .~ ..
28115 loads the map addxess, incluAing the two high order ~9 ~\ f q~

1 bits fox the map selection, into the PMA register 411.

2 The micropro~ram 115 then initiates a map read operation 3 sequence of the m~p memory control lcsic 401 4- , Thi.s se~uence is then carried out by the hard-ware, and in this sequence the map address is transmitted 7 from the PM~ register 411 through the address selector 8 415 to the map 409. Again, only the map select and page g address bits are used in this operation.

11 . The content of the selected map entry is ~2 transmitted from the map 409 to the map parity checker 13 451 tsee Fig. 35) and to the map output latch 443. The 1~ map parity checker 451 compares the parity bit from the map entry with the odd parity computed on the data.

.. ...
1~ If the parity is incorrect, the map address .' 18 is loaded into the map page register 441; and the map . 19 parity error signal sets an error flag which causes a map parity error interrupt to the CPU 105.

22 Otherwise, in the case o~ correct parity, 23 the map entry data is loaded from the map output latch ~ 24 443 into the map memory data register (~) 445.

26 Finally, the.R~P instruction micrGprogxam 27 returns the data in the map memory data (~ID) register 28 445 to the registex stack 112 (see Fig. 12) as the result 29 O~ the instruction.

-' 7~3 1 At the end of the read map (~P) instruction 2 the proper map section has been selected, the particular 3 logical page entry on that map section has been selected, 4 and the content of that map entry has been read out ~ro~
the map and returned as an instruction result to the CPU's 6 register stack.

8 T~e uses of the RMAP instruction include the 9 following.

';. 10 11 The main function of this read map (RMAP) 12 instruction is to allow the operating syste~ to examine 13 the referenc~ history field and dirty bit of a map 14 entry (see the map entry format shown in Fig. 36) to determine a page for overlaying (as will become more 16 apparent from the description of the operation to follow).

18 ' The read map (RMAP) lnstruction is also used 19 in diagnostics to determine whether the map storage is 20 functioning properly.

~1 .
22 The age map tAMAp) instruction is used by the 23 memory manager function of the operating system to maintain 24 usefui reference history information in the map. This 25 reference history information is maintained in the map 26 by map entries (the R,Sand T bits o~ the map entry 27 format shown in ~ig. 36) within a map sect~on which are 28 typically "aged" after each page fault interrupt occurrence 29 in that map section.

. .

.
' 7~
1 This AM~P instruction has just a single para-Z meter which is the map address specirying the map 3 location to be ased.

S In the operation of the age map (P*~P) 6 instruction, the microprogram 115 in the CPU 105 selects 7 a map location with the instruction map address parameter.
8 The microprogram 115 loads the map address parameter in~o 9 the PMA register just as in the RMAP instruction.

1~ At this poin~ a map-read operation sequence 12 of the map memory control logic 401 is initiated, and 13 this sequence proceeds identically as in the ~ ~P
1~ instruction descrlbed above~
~5 16 The microprogram 115 (Fig~ 12) reads the 17 content of the map entry from the ~D register 445 (Fig.
! . .
18 35) extracts the reference history field (the R, S and T

19 bits 10, 11 and 12 shown in Fig. 35), shifts the field 20 right one position, and reinserts the field to form the 21 new map entry data. Thus, a zero has been entered in 22 the R bit, the R bit has been shifted into the S bit, 23 the S bit has been shited into the T bit, and the old 24 T bit is lost.

26 Now the microproyram 115 takes the modified 27 map entry and loads this new data into the PMD register 28 423 ~Fig. 34) and writes the new map entry data back into 29 the selected map entrv (similar to the SMAP sequence).

., .

. , ' j This completes the age map (~P) 2 instruction.

4 As a result of the age map (AMAP) instruction, a map entry has been read from the map, its reference 6 history field has been shifted, and this modified entry 7 has been reinserted into the selected map location.

g As previously noted, the R bit is set to one 1~ by any memory relerence to the corresponding logical page, 1~ so ~hat when this bit is a one, it is an indication 12 that this page has been used since the last set map 13 (S~P) or age map (AM~P) operation instruction.

This setting of the R bit in conjunction with 16 the age map (AMAP~ instruction provides a means for 17 maintaining frequency of use information in the reference 18 history field of the map.

The reerence history field of all of the map 21 entries in a given map are typically aged after a page 22 fault interrupt. Thus, the value of the three bit 23 reference field in a map entry is an indication of the 24 fre~uenc~ of access since the previous three page fault interruptS.

27 For example, a binary value of seven ~all 28 three reference bits set at one), indicates accesses in 2~ each of the intervals between the proceeding page fault 30 interrupts~

7~

1 A binary value of four in the reference history 2 field (the R bit set at one and the S and T bits set 3 at zexo) indicates an access in the interval since the 4 last page fault int~rrupt and indicates that there were 5 no accesses in the intervals previous to the most recent 6 page fault interrupt.

8 As a final example, a binary value of zero for 9 the three bit reference field indicates that that logical ,~ 10 page has not been accessed in any of the three intervals 11 since the last three page fault interrupts.
,~ ~2 ~3 Thus, the higher the binary number represented " 14 by the three bit reference history field, the higher the 15 frequency of recent accesses to that logical page.
' 16 17 . This reference history information is main-18 ~air.ed so ~hat when it is necessary to select a page for ~, 19 overlay, a page whic~ has been infrequently used in the 20 ~ecent past can be identified. A page infrequently ~; 21 accessed in the recent past is likely to contlnue that 2~ behavior, and that page will therefore probably not ha~e~3 to be swapped bac~ into memory after being overlayed.
'~ 24 - 25 This frequency of use history is used by the 26 memory manager function of the operating system to select 27 infrequently used pages for overlay so as to minimize 28 swapping from secondary memory to implemen~ an efficient 29 Virtual memory System.

'; ,'' 187 ' ' 1 As noted above, memory may be accessed by 2 the CPU or by the I/O system.

4 The action of the memory system and map during 5 a CPU me~ory access sequence will now be described.
~ The access sequence is similar for the various CPU
7 memory accesses such as ~riting ~a~a, reading data, or 8 reading ins~ruc~ions from memory.
g The CPU memory access sequence is started ll either by the CPU microprogram 115 or by the CPU
12 instruction-fetch logic. In either event, the CPU 105 13 loads an eighteen bit logical address into the P~

14 re~ister 411 and initiates a data read, data write, or ~5 instruction read operation sequence of the map memory s 1~ control logic 401.

~ The eighteen bit logical address is composed 19 of two high order logical address space select bits and ~0 sixteen low order bits specifying a location within that 21 logical address space. The two select bits may be 22 specified by the CPU microprosram 115 or may be auto-23 matically generated i~ the CPU, based on the contents of 24 the instruction (I~ and environment (E) registers~

26 The eighteen bit logical address also includes, 27 in addition to the two high order logical address select 28 bits, six bit5 which specify the logical page within the 29 selected map and ten low order bits which specify the 30 offset within the page in the selected map.

1 In the data read, data write, or instruction ~ read operation sequence of the map memory control logic 3 401, after any previous map or memory operations have 4 completed, the eighteen bit address in the ~2~A register 5 411 (Fig. 35) is transmitted through the address selector 6 415 to the buses 417 and 419 (see Figs. 34 and 35).

8 The hus 419 trarsmits the page offset portion 9 of the address. This page offset portion of the address is transmitted directly to the physical memory modules 11 403 (Fig- 403) by the bus 419 13 ~he bus 417 transmits the loyiczl page address 14 por',ion (which must be translated to a physical page address) to the map 409.
.. , .lU
17 - ~he map entry selected by the logical page 18 address is read out from the map 409 to the map memory 19 control logic 401 (Fiy. 34), the map parity checker 451 ~Fig. 35), and the map outpu~ latch a43.

22 If the absent bit is a one, the logical page 23 address i5 loaded into the map page register a41, a 24 page faul~ interrupt signal is transmitted to the CPU
25 105, and the map memory control logic 401 terminates 26 the memory access sequence.
~7 2~ Similarly, if the parity checker 451 detects 29 incorrect parity in the map entr~, the logical page 30 address is loaded into the maD page register 441, a map 1 parity error signal is transmitted to the CPU, and the 2 memory access sequence is terminated.

4 Otherwise, if there is no error, the physical page address is transmit ed ~rcm the ~lap output l~tch 6 443 over the bus 421 to the physical memory modules 403;
7 and the map memory control logic 401 issues a command over the bus 439 to cause the selected memory module 403 to perform a read or write operation.

~0 - .
11 In a CPU write operation the data to be written 12 is transmitted from the PMD register 423 through the 13 data selector 427 to the memory module over the blls 429.

1~ .
i5 ~hile the memory module is performing a read 16 or write opexation, the map memory control logic 401 17 causes the map entry data to be modified and rewritten.

19 The map entry data, without the parity bit 20 P or ~he reference bit R, is transmitted Lrom the map 21 output latch 443 to the dirty bit logic 455 (see Fig.
22 35) and ~o the map data selector 447.

24 - In this operation the physi~al page field 25 of a map entry (shown in enlarged detail in the lower 26 righthand part of Fig. 36) and the S and T bits of the 27 reference field and the absent bit are always rewritten 2B without modification.

.

1 If a C~U data ~rite operation is being 2 performed, the dirt, bit D supplied to the map d,ta 3 selector i5 set to a one by the dirty bit lo~lc 455.
4 Otherwise, the dirty bit is not modlfied.

6 The reference blt R supplied to the map data 7 selector by the reference bit logic 453 is set to a one 8 in either a read or a write operation.

The physical page field and the S, T and A
11 bit5 are not modified, as noted above.
~2 13 The map data selector ~47 supplies this new 14 map data to the parity generator 449 and to the map 409.

16 An odd parity bit P is yenerated from the 17 new data by the parity generaior 449 ~see Fig. 35).
~8 19 A map write stxobe from the map memcry con~rol 20 1O51c 401 then causes the new data and parity to be 21 wri~ten in~o the map entry selected by the logical page 22 addxess bus 417.

24 Thus, the logical page has been translated 25 through the map entry, and the map entry has been 26 rewritten with updated parity, reference,and dirty bits.

2~ When the physical memory module 403 completes 29 its read or write operation, it sends a completion signal ..
30 to the map memory control logic 401 over the bus 439 31 (see Fig. 34).

, ~ .
~ r~r~.r~rr~~~ ~r~r~r~r~~rr~ vrx~ ~-o~r~.~
_ ~ t7~

! In a read operation the memory module 403 ~ gates the memory data to the bus 437 (Fis. 34).

4 In a data read ope~aticn sequence the data is loaded into the MD register 433 (Fig. 34) for use 6 by the CPU 105.

8 In an instruction read operation sequence g the data is loaded into the NI register 431 (Flg. 34) for subsequen~ execution by the CPU 105.

1~ .,..... i The CPU memor~ accesses of data read, data write and instruction read are thus completed as 14 described above.

16 An I/O channel access to read or to write 17 data to memory proceeds similar to a CPU memory access 1~ as des~ri~ed above except for the following.

2~ The channel memory address (C~) register 21 129 (Fig. 34) is used to provide the logical address, 22 and this register always speci~ies the system data map 23 469 (see Fig. 35). .

The channel memory data (G~ID) register 425 2~ (Fig . 34 ) is used to supply data to memory in a write 27 Operation.

29 The channel data tCD) register 125 tFig. 34) is used to receive data from memory in a read operation.

1 In an I/O channel 109 memory access, the 2 access is always a read or write data to memory access, 3 and there is no instruc'ion read access as in the case 4 of a CPU access.

6 In addition, map parity and absent conditions 7 are transmitted to the I/O channel 109 if they occur in 8 an I/O channel access to memory.

1~ As noted at several pcints~above, either ll semiconductor memory core memory is used for the memory 12 modules ~03.

14 When the memory is core memory, errors are 15 detected by a pari.y error detection system. The parity 16 error detection system for core memory modules is 17 effective to detect all single bit errors. Conventional 18 parity error generation and checking techniques are used, ... .
19 and details of the core memory will therefore not be 20 illustrated.
~1 22 The probability of failures in semiconductor 23 me~ory is great enou5h to justify an error detection 24 and correction system, and the present invention provides 25 a detection and correction system which inccrporates a 26 six bit checX field for each sixteen bit data word. Figs.
27 37-41 and related Table 1 (set out below) illustrate 28 details of an error detection and correction system used ~g when the memox~ modules 403 are constructed with semi-30 conductor memor~.
, . . .
lg3 F
, , ~ .

1 The six bit check field error det~ction and 2 correction system of the present i~vention is, ~s ~
3 be described in de-tail below, capable of ~etecting and 4 correctins all single ~it errors and is also capable of detecting all double bit errors. In addition, rnost 6 errors of three or more bits are detected.

8 While the error detection and correction g system will be described with reference to a semi-10 conductor memory, it should be noted that the system 11 is not limited or restricted to semieonductor memory 12 but is instead useful for any data stoxage or trans-13 mission application.

An impoxtant benefit of the error detection 16 and eorrection system of the present invention results 17 from the faet that not only are single bit errors 18 eorreeted but also that any subsequent double bit errors 19 are reliably detected after a singie bit has failed.

21 The multiproeessor system incorporating the 22 error deteetion and eorreetion system of the pLeSent 23 invention is thereore tolerant of single failures and 24 ean be operated with single bit failures in semiconductor 25 memory until sueh time as it is convenient to repair 26 the memory.

28 The error deteetion and correetion system 29 utilizes a systematic linear binary eode of Hamming di.s-30 tanee four. In this eode eae~ eheck bit is a linear 37 eombinatior of eight data bits (as shown in E'ig. 38).

--5~

1 Also, each data bit is a component of exactly three 2 check bits (as also shown in Fig. 38). ~n advanta~c of 3 this code is that uniform coverage of the data bits 4 by the chec~ bits is obtained.

6 The error correction and detection system 7 embodies a syndrome decoder which provides the 8 ccmbination of fast logic speed and low parts count.

In initial summary, the error detection and 11 correction system of the present invention operates to 12 add six check bits to each data word written into stox-13 age. When a data word is subsequently read out of memory, 14 the eheck field portion of the storage word is used to lS identif~ or to detect the loss of information in that 16 word since khe time it was stored.
~7 ,. .
18 ~ In semieonductor memory there are two possible 19 mecnanisms for loss of information (error~. Gne is hard 20 failure of a memory device which makes that device 21 permanently unable to retain information, and the other 22 is soft failure ln whieh electrical noise can cause a 23 transient ldss of information.

2~ The deteetion of errors is accomplished by a 26 eheck bit comparator whieh produces a six bit syndrome.

27 The syndrome is the difference between the check field 28 obtained from tne stored word and the check field which 29 would normally correspond to the dzta field obtained from 30 the stored word~

.

r~ ~, 1 This syndrome is then analyzed (decoded) to 2 deterr.line ~hether an error has occurrcd and, if an error 3 has occurred t to determine what type of correction is rec;uired.

; 5 In the case of singl.e data bit errors, the 6 syndrome decoder output causes a data bit complementer 7 to invert the bit that was in error; and this corrected 8 data is supplied as the output of that memory module.

If the syndrome decoder indi~ates a multiple ll error~ then the ~act of the multiple error is communicated .
12 to the map memory control section by means of one of 13 the cont.rol and error lines to cause an interrupt to the CPU.

With reference ncw to Fig. 37, the memory 16 module 403 includes a timing and control logic section 17 475 and a semiconductor storage array 477. The storage 18 array 477 provides storage for 32,768 words o~ tWent~J-19 two bits each. Each word has (as illustrated in Fig. 37) ,; .
20 a sixteen bit data field and a six bit check field.

22 Each semiconductor memory module 403 also 23 has, as illustrated in Fig. 37, an output latch 479, 24 a check bit generator 481, a check bit comparator 483, 2S a syndrome decoder 485 and a data bit complementer 487.

27 The memory module 403 interfaces to the rest 2~ of the system through the signal and data paths illustrated 29 in Fig. 37. These paths include: 429 (data to memory bus), 30 439 (control and error lines to the map memory control . .
19~ .

- 1 section 401), 419 and 421 (physical addr~ss bus), and : 2 437 (data rom memory ~us)~ These sig~al and data paths 3 are also shown in Fig. ~4.

With continu~d reference to Fi~. 37, the 6 content of ~he output latch 479 is transrnitted on a 7 bus 489 to both the check bit co~parator 483 and the S data bit comparator 487.
g 0 The output of the check bit comparator 48~ is ll transmitted on a syndrome bus 491 to both the syndrome 12 decoder 485 and the timing and control losic section 475.
~3 14 The output of the syndrome decoder 485 is trans-15 mitted on a bus 493 to the data bit complementer 487.

17 . Other outputs of the syndrome decoder 485 18 are txansmit~ed on llnes 495 and 497 to the timing and 19 control logic section 475. The line 495 transmits a 20 SINGLE ERROR (correctakle error) sisnal, and the line 21 497 transmi~s a MULTIPLE ERROR ~uncorrectable error) signal.

23 The timing and control logic 475 provides : 24 control signals on a control bus 499 to the semi-25 conductor storage array 477 and also to the output latch 26 479.

28 The output of the check bit generator 481 is ~ 2g transmit~ed to the storage ~rray 477 by a bus 501.

., C~
1 With refere~ce to Fi~. 38, the check bit ~ generator 481 includes six separate elght-bit parity 3 trees 503.

: 5 As shown in Fig. 39, the check bit com~arator "
6 483 includes six separate nine-bit parity trees 505.

~ As shown in ~ig. 40, the syndrome decoder 9 485 includes a decoder section 507 and a six-bit parity 10 tree 509.
11.
12 With continued reference to Fig. ~0, the out-13 puts of the decoder section 507 an2 six-bit parity tree 14 509 are combined ln error identification logic indicated 15 generally by the reference numeral 511.

17 As illustrated in Fig. 41, the bit complementer 18 437 comprises sixteen exclusive-or gates 513.

~0 In operation the sixteen bit data word is 21 supplied by the bus 429 to the storage array 477 a~d also 22 to the check bit generator 481 (see Fig. 37).

2~ The check bit generator 481, as best 25 illustrated in Fig. 38, ~enerates six check bits CO
26 through C5 by means of the six eight-bit parity trees 27 503.
2g ' ' ..
29 As also illustrated in Fig. 38, the eight-30 bit parity tree 503 farthest to the left generates _-.~
.. . ... . .. .... .. . ... .... ..

1 check bit ~ero (CO) as specified b~ the lo~ic equation 2 for CO as set out at the lower part of Fig. 38. Check 3 bit zero ~CO) is therefore the complement of the modulo-4 two sum of data bits 8 through 15.
6 By way of further e:-~ample, the chec}- bit C3 7 is generated by an eight bit parity tree 503 as specified 8 by the logic equation for C3 set out at the lower part 9 of Fig. 38. Cneck bit three (C3) is the modulo-two 10 sum of data bits 0, 1, 2, 4, 7, 9, 10 and 12 as shown 11 by th~ logic equation and as also illustrated by the 12 connections bet~Jeen the eight bit parity tree and the 13 corresponding data bit linzs in the logic diagram in the 14 upper part of Fig. 3S.
16 Similarly, each of the other check bits is 17 generated by a modulo-two addition of eight data bits 18 as illustrated in the logic diagram in the top part of 19 Fig. 38.
~0 21 To accomplish a memory write operation, these 22 six check bits, as thus generated by the check bit 23 generator 481, and the sixteen data bits, as transmitted 24 on the data bus 429, are entered in a particular locat:ion 25 in the storage array 477. As illustrated in Fig. 37, the 26 six check bits and the sixteen data bits are entered 27 in the storage array 477 under the control of the timing 28 and control logic 475 and the physical address information on 29 the physical address bus 419, 421.

, ~`
i'7Q
1 Every word stored in the storage array 477 2 has a six bit check fleld generated for that word in 3 a similar manner. This check field is retained with 4 the stored woxd in the storage array 477 until the time 5 when that location in the storage array is suksequently 6 accessed for a read operation.

,. . .

8 When a particular word is to be read out of 9 the storage array ~77, the timing and control logic 475 10 and the address on the physical address bus 419, 421 11 causes the content of the selected storage location to 12 be loaded into the cutput latch 479. The output latch 13 is twenty~two bits wide to accommodate the si~teen data 14 bits and the six bit check field.

16 From the output latch 479 the s.ixteen data 17 bits and the six bit check field are transmitted by a i' 18 bus 489 to the checX bit comparator 483.
1~
2a As illustrated in Fig. 39, the check bit 21 comparator 483 forms six syndrome bits SO through S5.

2~ Each syndrome bit is the output of a nine-bit 24 parity tree 505 whose inputs are eight data bits and one 25 check bit. Each syndrome bit is related to a correspond-26 ingly numbered check bit. Thus, check bit zero is used 2~ only for computing syndrome bit zero, check bit one is 28 used only for computing syndrome bit one, and so forth.

3~

. .
~00 ..

AS an example, syndrome bit zero (SO) is the comple-ment of the modulo-two sum of check bit zero and data bits 8 through 15 (as shown in the logic equation at the bottom of Fig. 39)-Similarly, each of syndrome bits S 1 through S 5 isgenerated from the modulo two sum oE a corresponding check bit and eight of the data bits, as shown by the connections to the particular data bit :Lines for each syndrome bi-t in the logic diagram part of Fig. 39~
The presence or absence of errors and the types of errorsr if any, are identified by interpreting the value of the six syndrome bits on the bus 491.
Table 1 enumerates the sixty-four possible values of the six bit syndrome code and gives the interpretation for each possible value.

~' - TABI,E 1 SYNDRO~IE CODES
S0 Sl S2 S3 S4 S5 ERROR IN S0 Sl S2 S3 S4 S5ERI'OR IN
0 0 0 0 0 0(No Error) 1 0 0 0 C0 0 0 0 0 0 1 C5 0 0 0 1 ~Double) 0 0 1 0 C4 0 0 1 () (Double) 0 0 1 1 (Double) 0 0 1 1 D8 O 1 0 0 C3 0 1 0 0 (Double~
-~ 0 1 0 1 (Double) 0 1 0 1 D~
0 1 1 0 (Double) 0 1 1 0 D10 0 0 0 1 1 1 D0 1 1 1 (Double) 0 0 1 0 0- 0 C2 1 0 1 0 0 0 ~Double) 0 0 0 1 (Double) 0 0 0 l Dll J - 0 0 1 0 ~Double) 0 0 1 0~Multi-Rll 0's) ` O 0 1 1 ~Multi) 0 O 1 1 ~Double) 0 1 0 0 ~Double) 0 1 0 0 D12 0 1 0 1 Dl 0 1 0 1 ~Double) . 0 1 1 0 D2 0 1 1 0 ~Double) : 0 1 1 1 ~Double) O 1 1 1 ~.ulti) . 20 0 1 0 0 0 0 Cl 1 1 0 0 0 0 (Double) . 0 0 0 1 (Double) 0 0 0 1 D13 O O 1 0 ~Double) O O 1 0 D14 0 0 1 1 D3 0 0 1 1 (Double) `~ 0 1 0 0 ~Double) 0 1 0 O (Multi) 0 1 0 1~Multi-All l's) 0 1 0 1 (Double) ; 0 1 1 0 D~ 0 1 1 0 (Double) 0 1 1 1 (Double) 0 1 1 1 ~Multi) 0 1 1 0 0 0 ~Double) 1 1 1 0 0 0 D15 0 0 0 1 D5 0 0 0 1 (Double) 0 0 1 0 D6 0 0 1 0 (Double) 0 0 1 1 ~Double) O O 1 1 ~Multi) 0 1 0 0 D7 0 1 0 O ~Double) : 0 1 0 1 ~Double~ 0 1 0 1 (MUlti) 0 1 1 0 (DOuble) 0 1 1 0 (Multi) ~- 0 1 1 1 (~lulti) 0 1 1 1 ~Double) THUS ~NU~IBER OF l's IN SYNDRO~IE) O BITS - NO ERROR 3 BITS - DAT.~\ BIT OR MULTI
1 BIT - CIIEC~ BIT ERROR 4 BITS - DOUBI.E
2 BITS - DOUBI,E 5 BITS - MUL'rI
6 BI'I'S - DOUBLE
2n i'7¢~

1 For e~ample, if all of the syndrome bits S 0 2 through S 5 are zero, there is no error in ~ither thc 3 data field or the check field. This is the condition 4 illustrated at the upper left of Table l.

6 The presence or absence of errors and the 7 type of error is sum~.arized at the bottom of Table l.
`. 8 9 In this summarization, when all six syndrome 10 bits are zero, there is no error, as noted above.
1~
~; 12 . 17 lg ` 20 5, 23 ' ~

~` Z7 . ~9 ... 30 ., .

~\ ~
7~

1 If ~nly one or the si~ syndrome bits is on, 2 this indicates an error in the correspondin~ c~leck bit.
3 It should be noted at this point that check bit errors are single bit errors which do not require correction 5 of the data word.

7 As also illustrated in the s D ary at the 8 botto~ of Table 1, when two bits are on there is a 9 double bit error; and the two errors could be (a) one 10 error in a data bit and one error in a check bit or 11 (b) two errors in the data bits or (c) two errors in ~-the check ~its.

1~ When three bits are on in the si~ Dit syndrome 15 code, that condition can correspond to either a single 16 data bit error o~ a multiple error.

18 As an example of a single bit error in a data 19 bit, see the syndrome code 111,000 indicating a single 20 bit error in data bit D-15 in the 10~7er right hand part 21 of Table 1. As will be described in more detail below, 22 the s~ndrome decoder 485 (Fig. 37 and Fig. 40) will cause 23 the incorrect value of data bit 15 to be inverted .~ .
24 ~corrected).

2~ The syndrome decoder 485 provides two functions.

27 First, the syndrome decoder 485 provides an 28 input to the data bit complementer 487 (see Fig. 37) by ~9 way of the bus 493 in the case or sinsle data bit errors, 30 which input causes the erroneous bit to be inverted with-31 in the data bit complementer 487.

20~

f~

1 Secondly, -the syndrome decoder 485 provides 2 one of two error signals in the cvent ~f an error.

4 A single data or check bit error is transmitted 5 on the SINGLE ERROR line ~.95 to the timiny and control 6 logic 475.

A multiple error indication ls transmitted on 9 the MULTIPLE ~PROR line 497 to the timing and control 10 logic 4j5, 11 ' 12 A MULTIPLE ERROR signal is generat~d in the ~3 case of all double bit errors and most three or more 1~ bit errors. This MULTIPL ERRO~ signal, as noted above, 15 causes an interrupt to the CPU 105 (see Fig~ 34).

~3 17 ~he construction of the syndrome decoder 485 18 is shown in detail in Fig. 40. The syndrome decoder 485 19 comprises a decoder 507, a six bit parity tree 509 and ~o error identification logic 511.
~1 22 The decoder 507 decodes five of the six syndrcme 23 bits ~bits S1 through S5) to provide sufficient information 2~ (thirty-two outputs) to generate both the error types 25 (whether single errors or double or multiple errors) and ~6 the sixteen output lines required for inversion of data 27 bit errors in the si~teen data bits. These sixteen output 28 lines required for inversion of data bit errors are 29 indicated generally by the bus 493 and are identified 30 individually by T0 through T15 in Fig. 40.

., .

1 Th~ decoder 507 outputs which are not connected -2 to the OR gate S12 correspond to errors in the six check 3 bits. Errors in ! ~e six check bits do not need to be 4 corrected (since the errors are not data bit errors), and these outputs o the deco~er ar~ therefore not used.

7 The remaining outputs (the outputs connected 8 to the OR gate 512) represen~ double or multiple errors g and are so indicated by the legends in Fig. 4G. All of 1~ these cases are collected by the OR gate 512 and are one 11 component of the multiple error signal on the line ~97 12 at the output of the error identification loyic 511.

14 As also illustrated in Fig. 40, the syndrome 15 decoder 45 includes a parity tree 509 which forms the 16 modulo-t~lo sum of syndrome bits S0 through S5.

18 The resultiny even or odd output of the parity g tree 509 corresponds to the er_or classes shown at the 20 bottom of Table 1.

22 Thus, the EVEN output 514 corresponds to syndromes 23 containing no bits on, two bits on, four bits on, or six 24 bits on.

26 The EVEN syndrome corresponding to no bits on 27 ~no error) is excluded from the MULTIPLE ERROR output signal 2~ 497 by an AND gate 515 which excludes the zero syndrome 29 case ~the other input from decoder 507 to the gate 515).

, 7~

Syndromes containing two bits on, ~our bits on 2 or six bits on are thus the onl~ remalninc~ EVEL~ syndromes ~
3 which in combination with the MULTI~LE signal constitute 4 multiple errors as transmitted on the output line MULTIPLE
5 ERROR (497).

7 An output is desired on the SINGLE ~RROR
indicator line 495 only for sin~le bit errors. Since 9 the odd output on the line 510 of the parity tree 509 10 corresponds to one bit on (check bit error), three bits 11 on (data bit error or multibi~ errors), or five bits on 12 (multibit exrors) in the six-~it syndrome (as indicated in 13 the summary at the bottom of Table 1), the odd output on 1~ line 510 ~ust be qualified so that only single bit errors are transmitted through the logic 511 to the line 495.
16 Those three--bit syndrome codes corresponding to multibit ,s 17 errors and all of the five-bit syndrome codes must there-18 fore be excluded so that only the single bit exrors are 19 transmitted on the line 495. This is accomplished by an 20 inverter 517 and an AND gate 519.

22 A SI~GLE ERROR output is generated on the line 23 495 for syndrome codes containing a single one bit (check 24 bit errors) and also for those syndrome codes containing 25 three one bits corresponding to data bit errors~ As noted 26 above, the odd output of the parity tree 509 indicates 27 syndxomes containing one, three or five bits on. The 28 inverter 517 and the AND gate 519 exclude multiple error ~9 three bit syndromes and all five bit syndromes. Thus, 30 the SI~GLE ERROR output 495 includes only single check "

.

~~ ~r; .

1 bit errors and single data bit errors. Single check 2 bit errors do not need to be corrected, and sinsle data 3 bit errors are corrected by the bit complementer 487.

~ 5 The logic equations for M~'LTIPLE ERROR and s 6 for SINGLE ERROR listed on the bottom of Fis. 40 ' 7 represent the operation described above.

~ There are some errors of three or more bits 1~ which are not identified as multiple errors and in fact 11 can be incorrectly identified as no errors or as single 12 blt errors (correctable errors). However, the normal 13 pattern of error generation is such that the deterloration 14 of storage is normally de~ected before three bit errors 15 occur. For example, the normal pattern of deterioration 16 of memorv storage would first involve a single bit error 17 from noise or component failure, then would later involve ~8 a double,bit error fxom additional failure, etc.; and the ~double bit errors would be detected before the three or ~o more bit errors could develop.

22 ' The function of the data bit complementer 487 23 (see Fig. 37) is to invert,data bit errors as detected 24by the syndrome decoder 485.

2~ Fi~. 41 shows details of the construction of 27the bit complementer 487. As illustrated in Fig. 41, 2~the bit complementer ~S7 is implemented by exclusive-or 2ggates 513. Each of these gates 513 inverts a given data 30bit on a line 4S9 when a corresponding decoder outpu~
31 on a line 493 is asserted, (--~ ~

7~
1 The corrected output is then transmitted on an 2 output line 437 of the bit co~pl~menter ~1~7 as the out-3 p~t of that physical memory module.

~his com~letes the description of the error 6 detection and correction system.
8 The memory system or the present invention 9 provides a number of significant features.

11 First of all, the memory map provides four 12 separate and distinct logical address spaces--system 13 code, system data, user code and user data--and provides 14 for a translation of logical addresses within these 15 address spaces to physical addresses.

17 The division of logical memory into four 18 address spaces isolates the system programs from the 19 ~ctions of the user programs and protects the sys~em 20 programs from any user errors. The divisicn into four 21 logical address areas also provides for a separation of 22 code and data for both user code and data and system 23 code and data. This provides the benefits of non-24 modifiable programs.

26 ~here are specific fields within each map 27 entry for this page address translation and for other 2~ specific conditions.
~9 One field permits translation of logical page 31 addresses to ph~ysical page addresses.

1 Anothe~ fleld pro~ides an absence indication, 2 This field is an absence bit which allcws implementation 3 of a virtu~1 me~.or~ sche~e where logical pages may reside 4 in a secondary memory.
. .
6 Another field is a reference history field.
7 This reference histo-y field allows frequency of use 8 information to be mair.tained for use by the memory manager ~ function of the operating system to make the virtual 1~ memory scheme an efficient scheme. Frequently accessed 11 pages are retained in primary memory, and infrequently 12 used page~s are sel~cted for necessary overlaying.

14 A dixty bit field is maintained in each entry 15 of the system data map and the user data map so that 16unmodified data pages can be identified. The unmodified ~7data pages so identified are not swapped out to secondary memory because a valid copy of that data page is already present in secondary memory.

~1 The memory system includes map memory control 2210gic which automatically maintains the reference and 23dirty bit infoxmation as CPU and I/0 channel accesses 24are made to memory, 26 The memory system of the present invention pro-27vides for three CPU instructions--S~P, ~AP and A~P--~gwhich are used by the operating system's memory manager ~unction to maintaln and to utili~.e information in the 3cmap .

. . ~ ~

~ . .

t'-J~
1 The me~ory system of the present invention 2 includes a dual port access to the memory. The memory 3 can be accessed separately by the CPU and by the I/O
4 channel. Accesses to memory by the I/O channel do 5 not need to involve the CPU, and the CPU can be per-Ç forming other functions during the time that an I/O
7 data transfer is ~eing made into or out of ~emory.

9 The operation of the dual port access ~o 10 the memory also involves arbitration by the map memory ? ~1 control logic in the event that the CPU and the I/O
~2 channel attempt a simultaneous access to the memory.
13 In the case of simultaneous access, the I/O channel i 1~ i5 given priority and the CPU waits until that particu1ar 15 I/O channel access has completed.

17 Physical memory is expandible by the modular ~8 addition or physical memory modules.

The physical memory modules incorporate, in 21 the case of semiconductor memory, error detection and 22 correction under certain conditions. Single errors 23 are detected and corrected so that operation of the 24 CPU ana I/O channel can be continued even in the event 25 of a transient or permanent failure within the physical 26 memory module. The error detection and correction 27 system comprises a t~enty-two bit word within the stora~e 28 medium. Sixteen bits represent the dat~ and six bits 2g proYide an error detection and correction checX field.
30 The six ~it check field allows the detection and , . .

7~
l correction of all single errors and the detection of 2 all dou~le errors.

4 The core memor~ includes parity for the 5 detection of single errors.
- .
7 In the overall multiprocessor system of the 8 present invention each processor module incorporates its g own primary memory system.

11 Since each processor module has its own memory ~2 system, problems of shared memory in a multiprocessing system are avoided.

The problems of shared memory in a mulLiprocessing 16 system include reduced memory bandwidth available to a particular processol. because of contention, and this 1~ reduction of available memory bandwidth becomes more 19 severe as additionaL CPU's are combined with a single ~o shared memory.

~1 .
22 ~he problems of interlocks relating to the communication between CPU's by means of areas within a 24 shared memory are avoided by the present invention which 25 does not include shared memory and which does, instead, 26 provide for communlcation between processor modules by 27 an interprocessor bus communication system.

29 An additional problem of shared memory is 30 that a failure in the shared memory can result in ~12 .

7~

1 simultaneous failure of some or all o the C~U's in 2 tne system. That is, in a shared memory system, a 3 single memory failure can stop all or part of the system;
4 but a memory failure ~ill not stop the multiprocessor 5 system of the present invention.

7 The dual port access by the CPU and the I/O
~ channel to the memory utilizes and is permitted because g of separate address registers and separate data registers to and ~rom memory.

11 .
12 ~hP CPU has a specific register (the NI register) 13 specifically for receiving instructions frcm memory. This 1~ separate and specific register allows overlapped fetch-lS ing of the next instruction during execution of the 1~ current instruckion (which may involve the reading of 17 data from memory). As a result, at the end of a current ~8 instruction, the next instruction can be initiated immedi-l9 ately without waiting for an instruction fetch.

21 ~he map is constructed to provide significantly 22 faster access than the access to physical main memory.
23 This provides a number of benefits in the translation cf 24 addresses throug~ the mapn 26 As one result, in the memory system of the 27 present invention, the map can be rewritten in the time 28 that the physica~ memory access is ~eing accomplished.
:29 . . .

Because the rewriting is so fast, the rewriting of the map does not increase mernory cycle time.
Also, the high speed at which the map can be accessed reduces -the overall time including paye trans-lati~n required for a memory access.
Parity is maintained and checked in the actua]
map stor~ge iself. This provides immediate indication of any failure in the map storage before resulting in-correct operation in the processor module can occur.

' . .
..

.

~ .
, .

;,~, .
, '

Claims

THE EMBODIMENTS OF THE INVENTION IN WHICH AN EXCLUSIVE
PROPERTY OR PRIVILEGE IS CLAIMED ARE DEFINED AS FOLLOWS:

1. An input/output system for a multiprocessor system comprising a plurality of separate processor modules, each processor module having a central processing unit and a memory, each processor module being capable of performing work of sub-stantially equal importance, at least two of the processor modules each having an input/output channel, at least one device controller for controlling the transfer of data between a processor module and a peripheral device, at least two ports in each device controller, at least two input/output buses, a first of the input/output buses being operatively connected between the input/output channel of a first of the processor modules and a first of the ports and a second of the input/out-put buses being operatively connected between the input/output channel of a second of the processor modules and a second of the ports, at least two interprocessor bus means distinct from the input/output buses and operatively connected between at least two of the processor modules for signaling and data transfer therebetween, and means in at least two of the proces-sor modules for detecting that one such processor module has failed and for causing the other such processor module to take over the work of the failed processor module.