Home
Patent Search
IMT Blog
REGISTER
|
SIGN IN
United States Patent
4817091
Katzman , ; et al.
March 28, 1989
Title
Fault-tolerant multiprocessor system
Abstract
In a multiprocessor system interconnected by a bus structure that provides communication and information transfers between the processor modules of the system, each processor broadcasts a central message to all the other processors of the system on a periodic basis. A processor module not receiving the control message from a sending processor module will assume the sending processor module has failed, and operate to take over the task of the failed processor module.
Inventors:
Katzman; James A.
(San Jose,
CA
)
, Bartlett; Joel F.
(Palo Alto,
CA
)
, Bixler; Richard M.
(Sunnyvale,
CA
)
, Davidow; William H.
(Atherton,
CA
)
, Despotakis; John A.
(Pleasanton,
CA
)
, Graziano; Peter J.
(Los Altos,
CA
)
, Green; Michael D.
(Los Altos,
CA
)
, Greig; David A.
(Cupertino,
CA
)
, Hayashi; Steven J.
(Cupertino,
CA
)
, Mackie; David R.
(Ben Lomond,
CA
)
, McEvoy; Dennis L.
(Scotts Valley,
CA
)
, Treybig; James G.
(Sunnyvale,
CA
)
, Wierenga; Steven W.
(Sunnyvale,
CA
)
Assignee:
Tandem Computers Incorporated
(Cupertino,
CA
)
Appl. No.:
052094
Filed:
May 19, 1987
Current U.S. Class:
714/8
714/11
714/55
Field of Search:
364/2MSFile,92MSFile 371/9,62
U.S. Patent Documents
3623014
November 1971
Doetz
3749897
July 1973
Hirvela
3786433
January 1974
Notley et al.
3908099
September 1975
Boulas et al.
3919533
November 1975
Einolf, Jr. et al.
3921141
November 1975
Wilber et al.
4012717
March 1977
Censier et al.
4099241
July 1978
Ossfeldt
Primary Examiner:
Chan; Eddie P.
Attorney, Agent or Firm:
Townsend and Townsend
Parent Case Text
This is a division of application Ser. No. 713,583, filed Mar. 18, 1985, now U.S. Pat. No. 4,672,535, which was a continuation of Ser. No. 543,809, filed Oct. 24, 1983 (abandoned), which is a continuation of Ser. No. 147,304, filed Apr. 6, 1980 (abandoned), which is a division of Ser. No. 721,043, filed Sept. 7, 1976, now U.S. Pat. No. 4,228,496.
Claims
We claim:
1. A multiprocessor system, comprising:
at least three separate processor modules, each processor module including a central processing unit, a main memory and an input/output channel;
at least two interprocessor buses, each bus coupling the separate processor modules to one another to transfer signals and data between the processor modules;
at least two device controllers operable to control data transfer between the processor modules and at least one related peripheral device connected to each device controller, each device controller including at least two separate ports;
a plurality of input/output buses separated from the interprocessor buses, each input/output bus being disposed between the input/output channel of a corresponding processor module and a one of the ports of the device controller so as to connect each device controller with at least two of the processor modules;
means in each processor module for transferring through a one of the interprocessor buses to an associated processor module information associated with an application program resident in the processor modules;
means in each processor module for sending a predetermined control signal to each other processor module through a one of the interprocessor buses;
means in each processor module for detecting when the predetermined control signal has not been received from the other processor module within a predetermined period and determining therefrom that the other processor module has failed;
means in each processor module responsive to the detection of the failure of receipt of the predetermined control signal within the predetermined period for initiating execution of a copy of said application program in the detecting processor module to thereby cause the detecting processor module to take over the work of the determined failed processor module; and
means in each processor module for controlling the related device controller through the input/output bus to control the related peripheral device so as to provide each of the peripheral devices with simultaneous operations.
2. A multiprocessor system comprising:
at least two separate processor modules, each processor module including a central processing unit, a main memory and an input/output channel;
interprocessor bus means connecting the separate processor modules to transfer signals and data therebetween;
at least one device controller between the processor modules and peripheral devices to control data transfer between each processor module and a related peripheral device, the device controller including at least two separate ports;
a plurality of input/output buses, separate from the interprocessor bus means, each input/output bus being disposed between the input/output channel of a processor module and a respective port of the device controller so as to connect one device controller with at least two processor modules;
means in at least first and second processor modules for transferring information from the first processor module to the second processor module through the interprocessor bus means, which information is associated with a program resident in the first processor module;
means in the first processor module for sending a predetermined control signal to the second processor module through the interprocessor bus means;
means in the second processor module for receiving the predetermined control signal from the first processor module, and for detecting, when the predetermined control signal has not been received from the first processor module within a predetermined period, that the first processor module has failed; and
means in the second processor module responsive to detection of the failure of the first processor module to initiate execution of a copy of said program, utilizing the transferred information, and to cause the second process module to take over the work of the first processor module.
3. A multiprocessor system as in claim 2, wherein said program is an application program.
4. A multiprocessor system comprising a first and at least a second separate processor module, each processor module comprising a central processing unit, a main memory and an input/output channel;
interprocessor bus means connected to the separate processor modules to transfer information between the processor modules;
at least one device controller adapted to be connected to peripheral devices to control data transfer between each processor module and the peripheral devices the device controller including at least two separate ports, each port being adapted for connection to a processor module;
a plurality of input/output buses separate from the interprocessor bus means, each input/output bus being disposed between the input/output channel of a corresponding processor module and an associated one of the ports of the device controller so as to connect one device controller with at least two processor modules;
means in the first and second processor modules for transferring information from the first processor module to the second processor module through the interprocessor bus means, which information is associated with a program resident in the first processor module;
means in the first and second processor modules for sending a predetermined control signal from the one processor module to the other processor module through the interprocessor bus means;
means in each of the first and second processor modules for receiving the predetermined control signal from the other processor module and for detecting, when the predetermined control signal has not been received from the other processor module within a predetermined period, that the other processor module has failed; and
means in each of the first and second processor modules responsive to detection of the failure of the other processor module to initiate execution of a copy of said program, utilizing the transferred information, and to take over the work of the failed other processor module.
5. A multiprocessor system, comprising:
a first and at least a second separate processor module, each processor module including a central processing unit;
interprocessor bus means connected to the separate processor modules to transfer information between the processor modules;
means in the first and second processor modules for transferring information from the first processor module to the second processor module through the interprocessor bus means, which information is associated with an active program resident in the first and a copy of said active program that is resident in at least the second processor module;
means in the first and second processor modules for sending through the interprocessor bus means, at intervals, from each processor module to each other processor module, a predetermined control signal indicative of continued operation of the sending processor;
means in each of the first and second processor modules for receiving the predetermined control signal from the sending processor module and for detecting, when the predetermined control signal has not been received from the sending processor module within a predetermine period that the sending processor module has failed; and
means in the first and second processor modules responsive to detection of the failure of the sending processor module for informing said copy of said active program that the sending processor module has failed, and to initiate execution of said copy of said active program, utilizing the transferred information, and to take over the work of the failed sending processor module.
6. The multiprocessor system of claim 5, wherein the predetermined control signal is in the form of a control message, the sending means in the first and second processor modules including means for periodically constructing and sending the control message through the interprocessor bus means.
7. A method for providing fault tolerant operation of a multiprocessor computer system wherein the multiprocessor computer system comprises a first and at least a second separate processor module and each processor module includes a central processing unit, comprising the steps of:
connecting together the separate processor modules to transfer information between the processor modules;
transferring information from the first to the second processor module, which information is associated with an active program resident in the first and an inactive copy of said active program that is resident in at least the second processor module;
sending, at intervals, from each processor module to each other processor module, a predetermined control signal indicative of continued operation of the sending processor module;
receiving at each of the first and second processor modules, the predetermined control signal from the other processor module;
detecting, when the predetermined control signal has not been received from the first processor module within a predetermined period, that the first processor module has failed; and
initiating, responsive to detection of the failure of the first processor module, execution of said inactive copy of said active program in the second processor module utilizing the transferred information to thereby cause the second processor module to take over the work of the failed first processor module.
8. The method of claim 7, wherein the predetermined control signal is in the form of a control message constructed and sent by the sending processor module.
9. A multiprocessor system comprising at least three separate processor modules, each processor module including a central processing unit, a main memory and an input/output channel,
at least two interprocessor buses, each bus connected to the separate processor modules to transfer signals and data between the processor modules;
at least two device controllers between the processor modules and peripheral devices to control data transfer between a processor module and a related peripheral device, each device controller including at least two separate ports each coupled to corresponding ones of the processor modules separately;
a plurality of input/output buses, separate from the interprocessor buses, each input/output bus being disposed between the input/output channel of a processor module and a respective port of a device controller so as to connect each device controller with at least two processor modules;
means in at least first and second processor modules for transferring information from the first processor module to the second processor module through one of the interprocessor buses which information is associated with a program resident in a first and a copy of said program resident in at least a second processor module;
means in each processor module for sending a predetermined control signal from each processor module to the other processor modules through an interprocessor bus;
means in at least two of the processor modules for receiving the predetermined control signal from each other and for detecting, when the predetermined control signal has not been received from the first processor module of the two within a predetermined period, that the first processor module of the two has failed; and
means in the at least two of the processor modules responsive to detection of the failure of the first processor module of the two for informing said copy of said program in the second processor module of the two that the first has failed, thereby to initiate execution of said copy of said program by the second processor module of the two, utilizing the transferred information and to cause the second to take over the work of the failed first processor module.
10. A multiprocessor system, comprising:
a plurality of separate processor modules, each processor module including means for formulating messages;
interprocessor bus means connected to the separate processor modules to transfer the messages between the processor modules;
means in each of the processor modules for transferring certain ones of the messages from such processor module to at least another of the processor modules through the interprocessor bus means, which certain ones of the messages contain information associated with an active program being executed in such processor module for an inactive copy of said active program that is resident in the another of the processor modules;
means in each of the processor modules for sending through the interprocessor bus means, at intervals, from each processor module to each other processor module, a control message containing information indicative of continued operation of the sending processor;
means in each of the processor modules for receiving the control message from the sending processor module and for detecting, when the control message has not been received from the sending processor module within a predetermined period that the sending processor module has failed; and
means in each of the processor modules responsive to detection of the failure of the sending processor module for informing said inactive copy of said active program that the sending processor module has failed, and utilizing the transferred information to initiate execution of said inactive copy of said active program to take over the work of the failed sending processor module.
11. A multiprocessor system, comprising:
a first and at least a second separate processor module, each processor module including a central processing unit;
interprocessor bus means connecting the separate processor modules to one another for transferring information therebetween in the form of messages;
means in the first and second processor modules for transferring messages of a first type from the first processor module to the second processor module through the interprocessor bus means, which first type messages contain information associated with an active program being executed in the first processor module for an inactive copy of said active program that is resident in at least the second processor module;
means in the first and second processor modules for sending through the interprocessor bus means, at intervals, from each processor module to each other processor module, a message of a second type that is indicative of continued operation of the sending processor;
means in each of the first and second processor modules for receiving the second type message from the sending processor module and for detecting, when the second type message has not been received from the sending processor module within a predetermined period, that the sending processor module has failed; and
means in each of the first and second processor modules responsive to detection of the failure of the sending processor module for initiating execution of said inactive copy of said active program, utilizing the transferred information to take over the work of the failed sending processor module.
Description
BACKGROUND OF THE INVENTION
This invention relates to a multiprocessor computer system in which interconnected processor modules provide multiprocessing (parallel processing in separate processor modules) and multiprogramming (interleaved processing in one processor module).
This invention relates particularly to a system which can support high transaction rates to large on-line data bases and in which no single component failure can stop or contaminate the operation of the system.
There are many applications which require on-line processing of large volumes of data at high transaction rates. For example, such processing is required in retail applications for automated point of sale, inventory and credit transactions and in financial institutions for automated funds transfer and credit transactions.
In computing applications of this kind it is important, and often critical, that the data processing not be interrupted. A failure of an on-line computer system can shut down a portion of the related business and can cause considerable loss of data and money.
Thus, an on-line system of this kind must provide not only sufficient computing power to permit multiple computations to be done simultaneously, but it must also provide a mode of operation which permits data processing to be continued without interruption in the event some component of the system fails.
The system should operate either in a fail-safe mode (in which no loss of throughput occurs as a result of failure) or in a fail-soft mode (in which some slowdown occurs but full processing capabilities are maintained) in the event of a failure.
Furthermore, the system should also operate in a way such that a failure of a single component cannot contaminate the operation of the system. The system should provide fault-tolerant computing. For fault-tolerant computing all errors and failures in the system should either be corrected automatically, or if the failure or 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 the system.
Since a single processor module can fail, it is obvious that a system which will operate without interruption 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 processing capabilities in the event of component failure, as will become more apparent from the description to follow.
Computing systems for on-line, high volume, transaction 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 systems of this kind has presented a number of problems in the prior art.
The prior art approach to uninterrupted data processing has proceeded generally along two lines--either adapting two or more large, monolithic, general purpose computers for joint operation or interconnecting a plurality of minicomputers to provide multiprocessing capabilities.
In the first case, adapting two large monolithic general purpose computers for joint operation, one conventional prior art approach has been to have the two computers share a common memory. Now in this type of multiprocessing system a failure in the shared memory can stop the entire system. Shared memory also presents a number of other problems including sequencing accesses to the common memory. This system, while meeting some of the necessary conditions for uninterruptible processing, does not meet all of the sufficient conditions.
Furthermore, multiprocessing systems using large general purpose computers are quite expensive because each computer is constructed as a monolithic unit in which all components (including the packaging, the cooling system, etc.) must be duplicated each time another processor is added to the system even though many of the duplicated components are not required.
The other prior art approach of using a plurality of minicomputers has (in common with the approach of using large general purpose computers) suffered from the drawback of having to adapt a communications link between computers that were never originally constructed to provide such a link. The required links were, as a result, usually made through the input/output channel. Connections through the input/output channel are necessarily slower than internal transfers within the processor itself, and such interprocessor links have therefore provided relatively slow interprocessor communication.
Furthermore, the interprocessor connections required special adapter cards that added substantially to the cost of the overall system and that introduced the possibility of single component failures which could stop the system. Adding dual interprocessor links and adapter cards to avoid problems of critical single components failures increased the overall system cost even more substantially.
Providing dual links and adapter cards between all processors generally became very cumbersome and quite complex from the standpoint of operation.
Another problem of the prior art arose out of the way in which connections were made to peripheral devices.
If a number of peripheral devices are connected to a single input/output bus of one processor in a multiprocessor system and that processor fails, then the peripheral devices will be unavailable to the system even though the failed processor is linked through an interprocessor connection to another processor or processors in the system.
To avoid this problem, the prior art has provided an input/output bus switch for interconnecting input/output busses for continued access to peripheral devices when a processor associated with the peripheral devices on a particular input/output bus fails. The bus switches have been expensive and also have presented the possibility of single component failure which could down a substantial part of the overall system.
Providing software for the prior art multiprocessor systems has also been a major problem.
Operating systems software for such multiprocessing systems has tended to be nonexistent. Where software had been developed for such multiprocessor systems, it quite often was restricted to a small number of processors and was not adapted for the inclusion of additional processors. In many cases it was necessary either to modify the operating system or to put some of the operating system functions into the user's own program -- an expensive, time-consuming operation.
The prior art lacked a satisfactory standard operating system for linking processors. It also did not provide an operating system for automatically accommodating additional processors in a multiprocessing system constructed to accommodate the modular addition of processors as increased computering power was required.
A primary object of the present invention is to construct a multiprocessor system for on-line, transaction-oriented applications which overcomes the problems of the prior art.
A basic objective of the present invention is to insure that no single failure can stop the system or significantly affect system operation. In this regard, the system of the present invention is constructed so that there is no single component that attaches to everything in the system, either mechanically or electrically.
It is a closely related objective of the present invention to guaranee that every error that happens can be either corrected, detected or prevented from contaminating the system
It is another important objective of the present invention to provide a system architecture and basic mode of operation which free the user from the need to get involved with the system hardware and the protocol of interprocessor communication. In the present invention every major component is modularized so that any major component can be removed or replaced without stopping the system. In addition, the system can be expanded in place (either horizontally by the addition of standard processor modules or in most cases vertically by the addition of peripheral devices) without system interruption or modification to hardware or software.
SUMMARY OF THE INVENTION
According to the present invention, therefore, a multiprocessor system comprises a plurality of independent processor modules interconnected by a bus structure for permitting information transfers therebetween. Each of the processor modules periodically sends to the other processor modules a control message to each of the other processor modules of the system, via the bus structure. Failure to receive the control message within an allotted time operates as an indication of failure of the sending processor module, and another of the processor modules will function to take over the task of the failed processor module.
The processor modules function principally to actively execute application programs, and secondarily as backups for other of the processor modules. Information transfers from the processor modules to their backup processor modules will take place periodically. If the backup processor module fails to receive the control message within an allotted time, it assumes that the active processor module is no longer functioning, and takes over execution of the application program of the failed processor module.
In an additional aspect of the invention, each of the processor modules is provided with an input/output path structure that is independent and separate from the bus structure. Multiported device controllers are configured to be accessed by two separate processor modules via their respective input/output path structure, thereby providing each processor module with at least two paths to any device.
Multiprocessor system apparatus and methods which incorporate the structure and technique described above and which are effective to function as described above constitute further, specific objects of this invention.
Other and further objects of the present invention will be apparent from the following description and claims and are illustrated in the accompanying drawings which, by way of illustration, show preferred embodiments of the present invention and the principles thereof and what are now considered to be the best mode contemplated for applying these principles. Other embodiments of the invention embodying the same or equivalent principles may be used and structural changes may be made as desired by those skilled in the art without departing from the present invention and the purview of the appended claims.
BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is an isometric, block diagram view of a multiprocessor system constructed in accordance with one embodiment of the present invention. FIG. 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. FIG. 1 also shows several dual-port device controllers 41 with each device controller connected to the input/output (I/O buses 39 of two processor modules.
FIG. 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. FIG. 2 shows, in diagrammatic form, the connections between each bus controller and the interprocessor control 55 of an individual processor module.
FIG. 6 is a detailed diagrammatic view of the logic of one of the bus controllers 37 shown in FIG. 2.
FIG. 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 illustrated in FIG. 2.
FIG. 5 is a view like FIG. 4 but showing the logic for an inqueue buffer and control 65 of the interprocessor control 55 for a processor module.
FIG. 6 is a state diagram of the logic 81 for a bus controller 37 and illustrates how the logic responds to the protocol lines going into the bus controller and generates the protocol lines going out of the bus controller to the processor modules.
FIG. 7 is a state diagram like FIG. 6 but showing the logic 73 and 75 for the shared outqueue buffer and control 67 of FIG. 4.
FIG. 8 is a state diagram like FIGS. 6 and 7 but showing the logic 93 and 101 for the inqueue buffer and control 65 of FIG. 5.
FIG. 9 is a diagrammatic view showing the time sequence for the transmission of a given packet between a sender processor module and a receiver processor module.
FIG. 10 is a logic diagram of the bus empty state logic section 75 and the processor fill state logic section 73 of the outqueue buffer and the control 67 shown in FIG. 4.
FIG. 11 is a listing of logic equations for the logic diagram shown in FIG. 10.
FIG. 12 is a block diagram of the input/output (I/O) system of the microprocessor system shown in FIG. 1.
FIG. 13 is a block diagram of the input/output (I/O) channel 109 of a processor module. FIG. 13 shows the major components of the I/O channel and the data path relating those component parts.
FIG. 14 is a detailed view showing the individual lines in the I/O bus 39 of FIG. 1.
FIG. 15 is an I/O channel protocol diagram showing the state changes of the T bus 153 for an execute input/output (EIO) caused by the microprogram 115 in the CPU 105. The sequence illustrated is initiated by the CPU 105 and is transmitted through the I/O channel 109 of the processor module 33 and on the T bus 153 to a device controller 41 as shown in FIG. 1.
FIG. 16 is an I/O channel protocol diagram showing the state changes of the T bus 153 for a reconnect and data transfer sequence initiated by the I/O channel microprograms 121 in response to a request signal from a device controller 41.
FIG. 17 is an I/O channel protocol diagram showing the state changes of the T bus 153 for an interrogate I/O (IIO) instruction or an interrogate high priority I/O (HIIO) instruction initiated by the CPU microprogram 115. The sequence illustrated is transmitted over the T bus 153 to a device controller 41.
FIG. 18 is a table identifying the functions referred to by the mnemonics in FIGS. 15 through 17.
FIG. 19 is a block diagram showing the general structure of the ports 43 and a device controller 41 as illustrated in FIG. 1.
FIG. 20 is a block diagram of a port 43 shown in FIG. 19. This FIG. 20 shows primarily the data paths within a port 43.
FIG. 21 is a block diagram showing the data path details of the interface common logic 181 of the device controller 41 shown in FIG. 19.
FIG. 22 is a block diagram showing the component parts of a data buffer 189 in the control part of a device controller 41 as illustrated in FIG. 19.
FIG. 23 is a graph illustrating the operation of the data buffer 189 illustrated in FIGS. 22 and FIG. 19.
FIG. 24 is a timing diagram illustrating the relationship of SERVICE OUT (SVO) from the channel 109 to the loading of data into the port data register 213 (FIG. 21) and illustrates how the parity check is started before data is loaded into the register and is continued until after the data has been fully loaded into the register.
FIG. 25 is a schematic view showing details of the power on circuit (PON) shown in FIGS. 19 and 21.
FIG. 26 is a logic diagram of the buffer control logic 243 of the data buffer 189 (shown in FIG. 22) of a device controller 41. FIG. 26 shows how the buffer control logic 243 controls the handshakes on the data bus and controls the input and output pointers.
FIG. 27 is a listing of the logic equations for the select register 173 shown in FIG. 20. These logic equations are implemented by the port control logic 191 shown in FIG. 20.
FIG. 28 is a timing diagram showing the operation of the two line handshake between the I/O channel 109 and the ports 43.
FIG. 29 is a logic diagram showing the logic for the general case of the handshake shown in FIG. 28. The logic shown in FIG. 29 is part of the T bus machine 143 of the input/output channel 109 shown in FIG. 13.
FIG. 30 is a block diagram of a power distribution system. FIG. 30 shows how a plurality of independent and separate power supplies 303 are distributed and associated with the dual port device controllers 41 for insuring that each device controller has both a primary and an alternate power supply.
FIG. 31 is an enlarged, detailed view of the switching arrangement for switching between a primary power supply and an alternate supply for a device controller. The switching structure shown in FIG. 31 permits both automatic switching in the event of a failure of the primary power supply and manual switching in three different modes--off, auto and alternate.
FIG. 32 is a block diagram showing details of one of the separate and independent power supplies 303 illustrated in FIG. 30.
FIG. 33 is a block diagram view showing details of the vertical buses and the horizontal buses for supplying power from the separate power supplies 303 shown in FIG. 30 to the individual device controllers 41. The particular bus arrangement shown in FIG. 33 permits easy selection of any two of the individual power supplies as the primary and the alternate power supply for a particular device controller.
FIG. 34 is a block diagram of the memory system and shows details of the memory 107 of a processor module 33 shown in FIG. 1.
FIG. 35 is a block diagram showing details of the map section 407 of the memory 107 shown in FIG. 34.
FIG. 36 is a block diagram showing the organization of logical memory into four logical address areas and four separate map sections corresponding to the four logical address areas. FIG. 36 also shows details of the bits and fields in a single map entry of a map section.
FIG. 37 is a block diagram showing details of one of the memory modules 403 illustrated in FIG. 34. The memory module 403 shown in FIG. 37 is a semiconductor memory module.
FIG. 38 is a diagram of a check bit generator used in the semiconductor memory module 403 shown in FIG. 37. FIG. 38 also lists logic equations for two of the eight bit parity trees used in the check bit register.
FIG. 39 is a diagram of a check bit comparator used in the semiconductor memory module 403 shown in FIG. 37. FIG. 39 includes the logic equation for nine bit parity tree for syndrome bit zero.
FIG. 40 is a diagram of a syndrome decoder used in the semiconductor memory module 403 shown in FIG. 37. FIG. 37 also lists the logic equations for the operation of the logic section 511 of the syndrome decoder.
FIG. 41 is a logic diagram of a bit complementer used in the semiconductor memory module 403 shown in FIG. 37.
FIG. 42 shows the various states of a two processor system running an application program which is required to be running continuously. The diagrams illustrate the two processors successively failing and being repaired and the application program changing its mode of operation accordingly.
DESCRIPTION OF THE PREFERRED EMBODIMENTS
THE MULTIPROCESSOR SYSTEM
FIG. 1 is an isometric diagrammatic view of a part of a multiprocessor system constructed in accordance with one embodiment of the present invention. In FIG. 1 the multiprocessor system is indicated generally by the reference numeral 31.
The multiprocessor system 31 includes individual processor modules 33. Each processor module 33 comprises a central processing unit 105, a memory 107, an input/output channel 109 and an interprocessor control 55.
The individual processor modules are interconnected by interprocessor buses 35 for interprocessor communications.
In a specific embodiment of the multiprocessor system 31, up to sixteen processor modules 33 are interconnected by two interprocessor buses 35 (indicated as the X bus and the Y bus in FIG. 1).
Each interprocessor bus has a bus controller 37 associated with that bus.
The bus controllers 37, interprocessor buses 35 and interprocessor controls 55 (FIG. 1), together with associated microprocessors 113, microprograms 115 and bus receive tables 150 (FIG. 2) provide an interprocessor bus system. The construction and operation of this interprocessor bus system are illustrated in FIGS. 2-11 and 42 and are described in more detail below under the subtitle The Interprocessor Bus System.
The multiprocessor system 31 has an input/output (I/O) system for transferring data between the processor modules 33 and peripheral devices, such as the discs 45, terminals 47, magnetic tape drives 49, card readers 51, and line printers 53 shown in FIG. 1.
The I/O system includes one I/O bus 39 associated with each I/O channel 109 of a processor module and one or more multi-port device controllers 41 may be connected to each I/O bus 39.
In the specific embodiment illustrated, each device controller 41 has two ports 43 for connection to two different processor modules 33 so that each device controller is connected for access by two processor modules.
The I/O system includes a microprocessor 119 and a microprogram 121 in the I/O channel 109 (See FIG. 12.) which are dedicated to input/output transfers.
As also diagrammatically illustrated in FIG. 12, the microprocessor 113 and microprogram 115 of the central processing unit 105 and an input/output control table 140 in the main memory 107 of each processor module 33 are operatively associated with the I/O channel 109.
The construction and operation of these and other components of the I/O system are illustrated in FIGS. 12-29 and are described in detail below under the subtitle The Input/Output System and Dual Port Device Controller.
The multiprocessor system includes a power distribution system 301 which distributes power from separate power supplies to the processor modules 33 and to the device controllers 41 in a way that permits on-line maintenance and also provides redundancy of power on each device controller.
As illustrated in FIG. 30, the power distribution system includes separate and independent power supplies 303.
A separate power supply 303 is provided for each processor module 33, and a bus 305 supplies the power from the power supply 303 to the central processing unit 105 and memory 105 of a related processor module 33.
As also illustrated in FIG. 30, each device controller 41 is connected for supply of power from two separate power supplies 303 through an automatic switch 311. It 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 nonstop 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 of which are shown in FIG. 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.
The purpose of the PON circuit is to present a signal establishing the level of power applied to that particular component; and if the power is not within certain predetermined acceptable limits, then the signal output is used to directly disable the appropriate bus signal of the component in which the PON is located.
The power-on circuit functions in four states--power off; power going from off to on; power on; and power going from on to off.
The power-on circuit initializes all of the logic states of the system as the power is brought up; and in the present invention, the power-on circuit provides an additional and very important function of providing for a fail-safe system with on line maintenance. To do this, the power-on circuit in the present invention is used in a unique way to control the interface circuits which drive all of the intercommunication buses in the system.
The construction and operation of the power distribution system are illustrated in FIGS. 30-33 and are described in detail below under the subtitle Power Distribution System.
The multiprocessor system includes a memory system in which the physical memory is divided into four logical address areas--user data, system data, user code and system code (See. FIG. 36.).
The memory system includes a map 407 and control logic 401 (See FIG. 34.) for translating all logical addresses to physical addresses and for indicating pages absent from primary storage bit present in secondary storage as required to implement a virtual memory system in which the physical page addresses are invisible to users.
The memory system incorporates a dual port access to the memory by the central processing unit 105 and the I/O channel 109. The I/O channel 109 can therefore access the memory 107 directly (without having to go through the central processing unit 105) for data transfers to and from a device controller 41.
The construction and operation of the memory system are illustrated in FIGS. 34-41 and are described in detail below under the subtitle Memory System.
An error detection system is incorporated in the memory system for correcting all single bit and detecting all double bit errors when semiconductor memory is used in the memory system. This error detection system utilizes a 16 bit data field and a 6 bit check field as shown in FIG. 37 and includes a data bit complementer 487 as also shown in FIG. 37 for correcting single bit errors.
FIG. 37 through 41 and the related disclosure illustrate and describe details of the error detection system.
Before going into the detailed description of the systems and components noted generally above, it should be noted that certain terminology will have the following meanings as used in this application.
The term "software" will refer to an operating system or a user program instructions; the term "firmware" will refer to a microprogram in read only memory; and the term "hardware" will refer to actual electronic logic and data storage.
The operating system is a master control program executing in each processor module which has primary control of the allocation of all system resources accessible to that processor module. The operating system provides a scheduling function and determines what process has use of that processor module. The operating system also allocates the use of primary memory (memory management), and it operates the file system for secondary memory management. The operating system also manages the message system. This provides a facility for information transfer over the interprocessor bus.
The operating system arrangement parallels the modular arrangement of the multiprocessor system components described above, in that there are no "global" components.
At the lowest level of the software system, two fundamental entities are implemented--processes and messages.
A process is the fundamental entity of control within a system.
Each process consists of a private data space and register values, and a possibly shared code set. A process may also access a common data space.
A number of processes coexist in a processor module 33.
The processes may be user written programs, or the processes may have dedicated functions, such as, for example, control of an I/O device or the creation and deletion of other processes.
A process may request services from another process, and this other process may be located in the same processor module 33 as a process making the request, or the other process may be located in some other processor module 33.
The process work in an asynchronous manner, and the processor therefore need a method of communication that will allow a request for services to be queued without "races" (a condition in which the outcome depends upon the sequence of which process started first)--thus the need for "messages" (an orderly system of interprocessor module communication described in more detail below).
Also, all interprocessor module communication should appear the same to the processes, regardless of whether the processes are in the same or in different processor modules.
As will become more clear from the description to follow, the software structure parallels the hardware; and different processes can be considered equivalent to certain components of the hardware in arrangement and function.
For example, just as the I/O channel 109 communicates over the I/O bus 39 to the device controller 41, a user process can make a request (using the message system) to the process associated with that device controller 41; and then the device process returns status back similar to the way the device controller 41 returns information back to the I/O channel 109 over the I/O bus 39.
The other fundamental entity of the software system, the message, consists of a request for service as well as any required data. When the request is completed, any required values will be returned to the requesting process.
When a message is to be sent between processes in two different processor modules 33, the interprocessor buses 35 are used. However, as noted above, all communication between processes appears the same to the processes, regardless of whether they are in the same or in different processor modules 33.
This software organization provides a number of benefits.
This method of structuring the software also provides for significantly more reliable software. By being able to compartmentalize the software structure, smaller module sizes can be obtained, and the interfaces between modules are well defined.
The system is also more maintainable because of the compartmentalization of function.
The well defined modules and the well defined interfaces in the software system also provide advantages in being able to make it easily expandible--as in the case of adding additional processor modules 33 or device controllers 41 to the multiprocessor system.
Furthermore, there is a benefit to the user of the multiprocessor system and software system in that the user, writing his program, need not be aware of either the actual machine configuration or the physical location of other processes.
Just as the hardware provides multiple functionally equivalent modules with redundant interconnects, so does the software.
For example, messages going between processes in different processor modules 33 may use either interprocessor bus 35. Also, device controllers 41 may be operated by processes in either of the processor modules 33 connected to the device controller 14.
The multiprocessor hardware system and software system described above enable the user to develop a fault tolerant application system by virtue of its replicated modules with redundant interconnects.
THE INTERPROCESSOR BUS SYSTEM
As pointed out above, the individual processor modules 33 are interconnected by two interprocessor buses 35 (an X bus and a Y bus) with each bus controlled by a related bus controller 37. Each interprocessor bus 35, in combination with its bus controller 37 and a related interprocessor control 55 in each processor module 33, provides a multi-module communication path from any one processor module to any other processor module in the system. The use of two buses assures that two independent paths exist between all processor modules in the system. Therefore, a failure in one path (one bus) does not prevent communication between the processor modules.
The bus controller 37 for each interprocessor bus 35 is a controller which is, in a preferred form of the invention, separate and distinct from the processor modules 33.
Each interprocessor bus 35 is a synchronous bus with the time synchronization provided by a bus clock generator in the bus controllers 37. The interprocessor control portions 55 of all of the modules associated with the bus make state changes in synchronism with that bus clock during transfers over the bus.
As will be described in more detail below, the CPU 105 operates on a different clock from the interprocessor bus clock. During the filling of an outqueue or the emptying of an inqueue in the interprocessor control 55 by the CPU, the operation takes place at the CPU clock rate. However, transmission of packets over the interprocessor bus always takes place at the bus clock rate.
It is an important feature of the present invention that the information transmitted over the interprocessor bus is transferred at high transmission rates without any required correspondence to the clock rates of the various CPUs 105. The information transfer rate over the interprocessor bus is also substantially faster than would be permitted by direct memory accesses into and out of the memory sections 107 at memory speed. This ensures that there is adequate bus bandwidth even when a large number of processor modules is connected in a multiprocessor system.
A benefit of using separate clocks for each CPU 105 is that a master system clock is not required, and this eliminates a potential source of single component failure which could stop the entire system.
The interprocessor control 55 incorporates logic interlocks which make it possible to operate the interprocessor buses 35 at one clock rate and each CPU 105 at its own independent clock rate without loss of data.
The information transmitted over the bus is transmitted in multiword packets. In a preferred form of the present invention each packet is a sixteen word packet in which fifteen of the words are data words and one word is a check word.
The control logic within the bus controller 37 and the interprocessor controls 55 of the individual modules 33 follows a detailed protocol. The protocol provides for establishing a sender-receiver pair and a time frame for the data packet transfer. At the end of the time frame for the transmission of the data packet, the bus controller 37 is released for another such sequence. The specific manner in which these functions are carried out will become more apparent after a description of the structural features of FIGS. 3-9 below.
X bus 35 is identical in structure to the Y bus 35, so the structure of only one bus will be described in detail.
As illustrated in FIG. 2, each bus 35 comprises sixteen individual bus data lines 57, five individual bus protocol lines 59, and one clock line 61, and one select line 63 for each processor module 33.
As also illustrated in FIG. 2, the interprocessor control 55 of each processor module 33 includes two inqueue sections 65 (shown as an X inqueue section and a Y inqueue section in FIG. 2) and a shared outqueue section 67.
With the specific reference to FIG. 4, the shared outqueue section 67 includes an outqueue buffer 69 which performs a storage function. In a preferred form the buffer 69 has sixteen words of sixteen bits each. The buffer 69 is loaded by the CPU and holds the data until the packet transmission time, at which time the data is gated out to the bus, as will be described in more detail below.
The outqueue section 67 also includes a receive register 71, which in a preferred form of the invention is a four bit register. This register is loaded by the CPU with the number of the processor module to which the data will be sent.
The control part of the outqueue section 67 includes a processor fill state logic section 73 which operates in synchronism with the CPU clock, a bus empty state logic section 75 which operates in synchronism with the X or Y bus clock, and an outqueue counter 77. During filling of the outqueue buffer 69 by the CPU, the out-queue counter 77 scans the buffer 69 to direct the data input into each of the sixteen words of the buffer; and as the sixteenth word is stored into the outqueue buffer
69, the outqueue counter 77 terminates the fill state.
The outqueue section 67 also includes an out-queue pointer 79 which connects the entire outqueue section to either the X bus or the Y bus 35. The outqueue pointer 79 allows the logic sections 73 and 75 and the buffer 69 to be shared by the X and Y interprocessor buses 35.
As illustrated in FIG. 3, the bus controller 37 comprises a bus control state logic section 81, a sender counter 83, a processor select logic section 85, a receive register 87, a packet counter 89 and a bus clock generator 91.
With reference to FIG. 5, each inqueue section 65 comprises a bus fill state logic section 93 which operates in synchronism with the bus clock, a sender register 95, an inqueue buffer 97, an inqueue counter 99, and a processor empty state logic section 101 which operates in synchronism with the CPU clock.
FIG. 6 is a state diagram of the bus control logic 81 of the bus controller 37.
FIG. 7 is a state diagram of the logic sections 73 and 75 of the outqueue section 67.
FIG. 8 is a state diagram of the logic sections 93 and 101 of the inqueue sections 65.
With reference to FIG. 7, the processor fill state logic section 73 has basically four states--EMPTY, FILL, FULL and WAIT--as indicated by the respective legends. The bus empty state logic section 75 has basically four states--IDLE, SYNC, SEND and DONE--as illustrated by the legends.
Continuing with a description of the notation in FIG. 7, the solid lines with arrows indicate transitions from the present state to the next state. Dashed arrows ending on the solid arrows indicate conditions which must be satisfied for the indicated transition to take place.
The synchronization of state machines running off relatively asynchronous clocks require a careful construction of an interlock system. These important interlocks are noted by the dashed arrows in the state diagrams. These interlocks perform a synchronization of two relatively asynchronous state machines. The dashed arrows in FIG. 7 and FIG. 8 running between the state machines thus indicate signals which synchronize (qualify) the indicated transitions of the state machines.
With reference to the FILL state for the logic section 73, it should be noted that the store outqueue condition will not cause an exit from the FILL state until the outqueue counter 77 has advanced to count 15 (on a count which starts with zero) at which time the FILL state will advance to the FULL state.
Similarly, it should be noted that the SEND state of the logic section 75 will not terminate on the select and send command condition until the outqueue counter 77 reaches count 15, at which time the SEND state advances to the DONE state.
The asterisk in the notation of FIG. 7 indicates an increment of the outqueue counter 77.
FIG. 6 shows the state diagram for logic 81 of the bus controller and illustrates that the logic has basically four states--IDLE, POLL, RECEIVE and SEND.
The notation in FIG. 6 is the same as that described above for FIG. 7. A solid arrow line indicates a state transition from one state to another and a dotted arrow line to that solid arrow line indicates a condition which must occur to allow the indicated (solid line arrow) transition to occur. An asterisk on a state transition in this case indicates that simultaneously with the indicated transition the sender counter 83 is incremented by one.
The dashed arrow output lines in FIG. 6 indicate protocol commands issued from the bus controller to the interprocessor bus.
In both FIG. 7 and FIG. 6 a dashed arrow leaving a state indicates a logic output from that state such as a logic output signal to a protocol line (in the case of the bus empty state logic 75) or to a status line of the processor module (in the case of the processor fill state logic 73).
FIG. 8 shows the state diagrams for the bus fill state logic section 93 and the processor empty state logic section 101.
The state diagram for the logic section 93 includes four states--SYNC, ACKNOWLEDGE, RECEIVE and FULL.
The state diagram for the logic section 101 includes four states--RESET, READY, INTERRUPT and DUMP.
The notation (solid line arrows and dashed line arrows) is the same as described above for FIG. 7 and FIG. 6.
The asterisk in FIG. 8 indicates an increment in the inqueue counter 99.
FIG. 9 is a timing diagram showing the time sequence in which the state changes given in FIGS. 6, 7 and 8 occur.
The sequence shown in FIG. 9 accomplishes the transmission of a packet from one processor module to another processor module at the bus clock rate (assuming that the intended receiver module is ready to receive the packet).
FIG. 9 shows the time sequences for a successful packet transfer with individual signal representations listed from top-to-bottom in FIG. 9 and with time periods of one bus clock each shown from left-to-right in the order of increasing time in FIG. 9.
The top line in FIG. 9 indicates the state of the bus controller, and each division mark represents a clock period or cycle of the bus clock generator 91 shown in FIG. 3. Each time division of the top line carries down vertically through the various signal representations listed by the legends at the left side of the figure.
Taking the signals in the sequence presented from top-to-bottom in FIG. 9, the first signal (below the bus controller state line) is the SEND REQUEST signal (one of the protocol group indicated by the reference numeral 59 in FIG. 3) and specifically is the signal which may be asserted by the outqueue control logic section 67 of any processor module 33. The signal is transmitted to the bus control state logic section 81 of the bus controller 37 (see FIG. 3).
The next signal shown in FIG. 9 (the SELECT signal) represents a signal which originates from the processor select logic section 85 of the bus controller 37 and which is transmitted on only one at a time of the select lines 63 to a related processor module 33.
The next signal represented in FIG. 9, the SEND ACKNOWLEDGE signal, may be asserted only by a particular processor 33 when that processor is selected and when its bus empty state logic section 75 is in the SEND state (as illustrated in the third state of FIG. 7). This SEND ACKNOWLEDGE signal is used by the bus controller 37 to establish the identity of a processor module 33 wishing to send a packet.
The next signal, the RECEIVE COMMAND signal, represents a signal from the bus controller 37 transmitted on one of the protocol lines 59. This signal does two things.
First of all, this signal in combination with receiver SELECT interrogates the receiver processor module 33 to find out whether this receiver module is ready to receive (as indicated by the ACKNOWLEDGE state in FIG. 8).
Secondly, this signal has a secondary function of disabling the bus empty state logic section 75 of the receiving module so that the receiving module cannot gate an intended receiver number to the data bus should the outqueue section of the intended receiver module 33 also have a data packet of its own ready to send.
In this regard, during the time that the sender processor is asserting the SEND ACKNOWLEDGE signal it is also gating the receiver number to the bus for use by the bus controller 37. The bus 35 itself is, of course, a non-directional bus so that the information can be gated to the data bus 57 by any module for use by either the bus controller 37 for a control function or for use by another processor for an information transfer function. It should be noted that a module 33 may gate data to the bus only when its SELECT line is asserted and the RECEIVE COMMAND signal is not asserted.
DUring the time that the RECEIVE COMMAND signal is asserted the bus controller 37 is gating the sender number to the data bus 57 for capture by the selected receiver processor module.
The next signal line (the RECEIVE ACKNOWLEDGE line in FIG. 9) represents a signal which is transmitted from the selected receiving module's bus fill state logic section 93 to the bus control state logic section 81 of the bus controller 37 (over one of the protocol lines 59) to indicate that the selected receiver module is in the ACKNOWLEDGE state (as indicated by the legend in FIG. 8) and thus ready to receive the packet which the sender module has ready to transmit.
If the RECEIVE ACKNOWLEDGE signal is not asserted by the receiver module, the sender SELECT, the SEND COMMAND and the time frame transmission of the data packet itself will not occur.
If the RECEIVE ACKNOWLEDGE signal is asserted, then the sequence indicated by the SEND COMMAND line will occur.
The SEND COMMAND line represents a signal which originates from the bus control state logic section 81 of the bus controller 37 and which is transmitted to the bus empty state logic section 75 of the sender processor module 33 over one of the protocol lines 59.
In combination with a SELECT of the sender processor module the SEND COMMAND signal enables the sender processor module to send a packet to the receiver module during the sixteen clock cycles bracketed by the SEND COMMAND signal.
The final line (the data/16 line) represents the information present on the data lines 57 during the above-described sequence.
The data is gated to the bus by the selected sender processor 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 that the RECEIVE ACKNOWLEDGE signal was received by the bus controller in response to the RECEIVE COMMAND signal.
If the RECEIVE ACKNOWLEDGE signal had not been received by the bus controller, then the SEND COMMAND signal would not have been asserted and the bus controller 37 would have resumed the POLL state as shown in FIG. 6.
With reference to FIGS. 2, 7, 10 and 11, a typical operation of the outqueue buffer and control 67 of one processor module 33 will now be described.
As illustrated in FIG. 10, the processor fill state logic section 73 includes two flip-flops A and B, and the bus empty state logic section 75 includes two flip-flops C and D.
Summarizing the state assignments as shown by the AB and CD tables in FIG. 10, the EMPTY state is defined as A=0, B=0. The FILL state is defined as A=1, B=0. The FULL state is defined as A=1, B=1; and the WAIT state is defined as A=0, B=1.
Similarly, the corresponding combinations of the C and D state variables are defined to be the IDLE, SYNC, SEND and DONE states respectively. State assignments previously listed could also be given in form of logic equations. For example, EMPTY=A.multidot.B, and this notation is utilized in the FIG. 11 logic equation listings.
In operation and with specific reference to FIG. 7, the initial state reached through power on initialization or manual reset is the EMPTY state shown in the top left part of FIG. 7.
The EMPTY state of the processor fill state logic 73 provides a ready signal to the central processor unit (CPU) 105 to indicate the presence of that state, as indicated by the dashed arrow RDY shown as leaving the empty state in FIG. 7.
The CPU firmware (microprogram) in response to that ready signal, when a transmission over the interprocessor bus is required; will provide a store receive signal (shown by the dashed arrow incoming to the diagram in FIG. 7). This store receive signal qualifies (synchronizes) the transition which advances the EMPTY state to the FILL state.
The CPU firmware, to transfer data into the outqueue buffer 69, will provide a store outqueue signal (the dashed arrow entering the diagram in FIG. 7) for each word to be stored in the buffer 69.
Each occurrence of this store outqueue signal will advance the outqueue counter 77, commencing with a count of zero, until a count of 15 is reached.
On the sixteenth occurrence of the store outqueue signal a transition from the FILL to the FULL state, as illustrated by the solid line arrow in FIG. 7, is allowed.
The FULL state of the processor FILL state logic provides a synchronization condition to the bus empty state logic denoted by the dashed arrow leaving the FULL state of logic 73 and going down to the logic 75 in FIG. 7.
The processor fill state logic 73 will remain in the FULL state until the bus empty state logic 75 has subsequently reached the DONE state.
Now, referring specifically to the bus empty state logic denoted by 75 in FIG. 7, the initial state, IDLE, for the logic section 75 in FIG. 7 is again provided by power on initialization or manual reset.
The bus empty state logic 75 will remain in the IDLE state until the transition to the SYNC state is allowed as shown by the dashed arrow from the FULL state of the processor fill 73.
The empty state logic 75 will proceed with no qualification required from the SYNC state to the SEND state.
It is in the SEND state that the SEND REQUEST signal to the bus and to the bus controller is asserted (as indicated by the dashed arrow going down and leaving the diagram 75 from the SEND state).
In response to this SEND REQUEST signal, the bus controller logic 81 (FIG. 6) will poll processor modules successively until the sender is identified (as discussed earlier with reference to FIG. 9).
The bus controller will issue a RECEIVE COMMAND and SELECT to the intended receiver processor module; and upon receipt of the RECEIVE ACKNOWLEDGE signal will proceed to the packet time frame (also identified in FIG. 9).
During the packet time frame the bus controller asserts SELECT of the sender processor module and also asserts the SEND COMMAND signal to the sender processor module.
This SELECT signal and SEND COMMAND signal is shown as entering the diagram and qualifying (synchronizing) transitions leaving and entering the SEND state as noted in FIG. 7.
Each bus clock while SELECT and SEND COMMAND are asserted will advance the outqueue counter 77 commencing with a count of zero.
On the sixteenth clock period of SELECT and SEND COMMAND the transition terminating the SEND state and advancing to the DONE state is qualified (synchronized as shown by the dashed arrow allowing that transition).
When the empty state logic 75 has reached the DONE state, a transition of the processor fill state logic 73 from FULL to WAIT is qualified (as denoted by the dashed arrow leaving the done state).
Next, the WAIT state of the processor fill state logic 73 qualifies a transition of the bus empty state logic 75 from the DONE state to the IDLE state (as denoted by a dashed arrow leaving the WAIT state and qualifying the indicated transition).
Finally, the bus empty state logic 75, being in the IDLE state, qualifies the transition of the processor fill state logic 73 from the WAIT state to the EMPTY state (as denoted by the dashed arrow leaving the IDLE state).
At this point a packet has been loaded into the outqueue buffer 69 by the processor module and transmitted over the bus 35 to the receiver processor module, and the outqueue control processor fill state logic 73 and bus empty state logic 75 have returned to their initial states.
The above description relates to the transitions and qualifications indicated in FIG. 7. The action of the logic sections 73 and 75 involved in the above description of operation of FIG. 7 will now be noted with reference to the logic diagram of FIG. 10 and the logic equation listing of FIG. 11.
With reference to FIG. 10, as noted above, the flip-flops A and B are JK flip-flops and are edge triggered flip-flops in that state changes occur only on clock transitions (as indicated by the small triangular symbols and legends on the lefthand sides of the flip-flops A and B in FIG. 10).
The primary significance of the logic diagram in FIG. 10 is to illustrate the transition from one state to another in the state machines shown in FIG. 7. Thus, to illustrate the transition from IDLE to SYNC in the empty state logic 75, the operation proceeds as follows.
To implement a change from the IDLE state to the SYNC state, the state variable C must be set.
The logic equation for the J input of state variable C is as shown in FIG. 11 and is indicated by the reference numeral 103. In this equation the interlock (shown by the dashed arrow from the full state of the fill state logic 73 in FIG. 7 to the transition) corresponds to the quantity (A.multidot.B) or (FULL) in the equation indicated by the reference number 103. The D or (IDLE) in the equation indicated by reference numeral 103 in FIG. 11 corresponds to the IDLE state shown by the legend in FIG. 7. The J in the equation corresponds to the J input of the C flip-flop in FIG. 10. And the (C) corresponds to the true output of the C flip-flop in FIG. 10.
Other state transitions of the FIG. 7 diagram will not be described in further detail with reference to FIGS. 10 and 11 since it is believed that these transitions as carried out by the logic diagram in FIG. 10 and the logic equations in FIG. 11
are clear from the above examples of the transition from IDLE state to SYNC state as described in detail above.
FIGS. 10 and 11 show the logic diagram and logic equations for the state diagram of the outqueue buffer and control 67. Corresponding logic diagrams and logic equations have not been illustrated for the inqueue buffer and control 65 or the bus controller 37 because such logic diagrams and equations are similar to those shown in FIG. 10 and FIG. 11 and are easily obtainable from the state diagrams shown in FIGS. 6 and 8.
Each processor module 33 (FIG. 1) in the multiprocessor system is connected to both interprocessor buses 35 (FIG. 1) and is capable of communicating with any processor module including itself over either bus. For each block data transfer, one processor module is the source or sender and another is the destination or receiver.
Transmission of data by a processor module over one of the interprocessor buses is initiated and accomplished under software control by means of the SEND instruction.
In the SEND instruction the microprogram 115 (FIG. 2) and the CPU microprocessor 113 (FIG. 2) interacts with the shared outqueue section 67 of the interprocessor control 55 to read a data block from memory 101 to break it up into packets, to calculate packet check sum words, and to transmit the block one packet at a time over a bus to the receiving processor module. Parameters supplied to the SEND instruction specify the number of words in the block, the starting address of the block, which bus to use, the destination processor, and a maximum initial timeout value to wait for the outqueue 67 (FIG. 2) to become available.
The SEND instruction terminates only after the entire block has been transmitted; thus sending a block is a single event from the software viewpoint. However, the SEND instruction is interruptable and resumable, so that response of the operating system to other events is not impaired by the length of the time required to complete a SEND instruction.
Receiving of data by a processor module over the interprocessor buses is not done by means of a software instruction, since the arrival times and sources of data packets cannot be predicted. The receiving of data is enabled but cannot be initiated by the receiver.
The CPU microprocessor 113 takes time out from software instruction processing as required to execute the BUS RECEIVE microprogram 115. This microprogram takes the received data packet from one of the inqueue sections 65 (FIG. 2) of the interprocessor control 55, stores the data into a memory buffer, and verifies correct packet check sum.
Reassembly of received packets into blocks is accomplished using the Bus Receive Table 150 (BRT) in memory. The BRT contains 32 two-word entries, corresponding to the two buses from each of the sixteen processor modules possible in one specific implementation of the multiprocessor system. Each BRT entry corresponding to a bus and a sender contains an address word and a count word. The address word specifies into which buffer in the System Data area incoming data from that sender is to be stored. The count word specifies how many data words remain to complete the block transfer from that sender.
As each data packet is received, the CPU microprocessor 113 suspends processing of software instructions, and the bus receive microprogram 115 is activated. This microprogram reads the address and count words from the sender's BRT entry, stores the data packet into the specified area, verifies correct packet check sum, and restores adjusted values of the address and count words into the BRT entry. If the packet caused the count to reach zero or if the packet contained incorrect check sum, the bus receive microprogram sets a completion interrupt flag to signal termination of the data block to the software. The CPU microprogram then resumes software instruction process at the point where it left off with no disturbance except delay to the currently executing program.
It is an important feature that data blocks from several senders can all be assembled concurrently by a receiving processor module from data packets received in any sequence. This interleaved assembly of blocks from packets is carried on transparently to the software executing in the receiver processor. Only successful block completions or erroneous transmissions cause the software to be interrupted.
It is also important that a time-sharing or time-slicing of the interprocessor bus hardware has been achieved in two areas.
First, each interprocessor bus and associated bus controller allow packets to be transmitted between any sender and receiver as required. The circular polling by a bus controller to identify a requesting sender ensures that all processor modules have an equal opportunity to send over that bus. Each bus provides a communication path which is shared in time in an unbiased way by all processor modules.
Secondly, each inqueue section 65 of the interprocessor control 55 of a processor module is shared in time by incoming packets from several senders. That is, the inqueue logic and storage of a processor is not dedicated to a single sender for the duration of a block transfer. Instead, each packet received is correctly directed into memory by the BRT entry corresponding to its sender and bus. Data blocks from several senders are assembled correctly in the receiver's memory independently of the order in which the senders make use of the bus.
A processor module has two ways of controlling its ability to receive packets over the X bus or the Y bus.
First, there is a bit in the CPU's interrupt MASK register corresponding to each interprocessor bus. When the MASK bit is on, micro-interrupts for that bus are allowed. Micro-interrupts (activation of the BUS RECEIVE microprogram) occur when the Processor Empty state logic 101 (FIG. 5) of an inqueue section 65 reaches the MICRO-INT state after a packet has been received into an inqueue buffer. If the MASK bit is off when a packet is received, the micro-interrupt and subsequent processing of the packet into memory will be deferred until the MASK bit is set on by a software instruction.
Software operations such as changing a BRT entry are performed with micro-interrupts disabled to avoid unpredictable results. No packets are lost while micro-interrupts are disabled. The first packet received will be held in the inqueue buffer until the micro-interrupt is enabled. Subsequent packet transfers while the inqueue buffer is full are rejected since the bus Fill state 93 logic will be in the FULL state and thus unable to assert RECEIVE ACKNOWLEDGE in response to SELECT.
A second means of controlling its ability to receive packets over the bus is the action taken by a processor module after an X bus or Y bus receive completion interrupt (activation of an operating system interrupt handler).
When a check sum error is detected in a received packet or when the BRT sum count remaining in a data block reaches zero as a packet is stored into memory, the BUS RECEIVE microprogram sets the X bus or Y bus completion interrupt flag. Otherwise, the microprogram issues the RINT signal (see FIG. 8) to the inqueue Processor Empty state logic 101 to allow another packet to be received. When the completion flag is set, however, the RINT Signal is not issued.
It is thus the responsibility of the bus receive completion software interrupt handler to issue the RINT signal (by means of an RIR software instruction) to reenable the inqueue 65. Until this occurs, the inqueue Bus Fill state logic 93 remains in the FULL state and no additional packets will be received.
The completion interrupt signal can therefore designate either a block data transfer that has been sent and received without error, or it can designate a partial transfer in which a check sum error is detected, and in which partial transfer of the completion interrupt is generated as a result of the check sum error detected. In the latter case, the sender continues to send the data block but the receiver discards the data block after the check sum error has been detected. This error shows up in the bus receive table (BRT) count word as a negative value. This will become more apparent from the description of the operation which follows.
The SEND instruction is an instruction that requires four parameter words in the CPU register stack.
The first of the four parameter words is a count of the number of words to be transferred. This value must match the number expected by the BRT in the receiver processor module if the transfer is to complete successfully.
The second parameter word is the address, minus one, in the System Data area in the sender processor's memory where the data to be transferred is located.
The third parameter word is a timeout value allotted to completing a single packet (fifteen data word) transfer. The timeout period is restarted for each packet transferred by the SEND instruction.
The fourth parameter word specifies the bus (whether the X bus or the Y bus) to be used and specifies the receiver processor module. The high order bit of the parameter specifies the bus and the low order four bits, in one specific implementation of the invention, specify the number of the receiver processor module.
At the completion of a SEND instruction, there are two possible conditions.
The first condition is that a packet timeout occurred and the remaining packets were not transmitted and the instruction was terminated at that point. In this event the remaining packets of the block are not transmitted.
The second condition is an indication that a successful data block transfer has been completed.
Thus, in initial summary of the SEND operation, the SEND instruction fills the outqueue buffer 69 (FIG. 4) with fifteen data words, appends an odd-parity check sum, and signals the bus controller 37 that it has a packet ready for transmission. After each sixteen word packet is transmitted, execution of the SEND instruction resumes at the point where it left off. If the last packet of the block has less than fifteen words, the remaining words are filled in with zeros. The instruction terminates when the last packet is transmitted.
FIG. 5 shows the logic diagram and FIG. 7 shows the state diagram for the send hardware.
The first action of the SEND instruction sequence is to issue the S/RECEIVE signal to the processor fill state logic 73 (FIG. 4) and to supply on the M Bus (FIG. 4) the receiver processor number to the receive register 71. Simultaneously, the pointer of the outqueue point 79 is set in accordance with the high order bit of the M Bus to connect the outqueue 67 to either the X bus or the Y bus.
The store receive (S/RECEIVE) signal causes the processor fill state logic 73 (which is initially in the 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 receiver processor number.
At this point the outqueue section 67 is ready for the data packet to be loaded into the outqueue buffer 69. Now, up to fifteen words are read from memory and are stored, by means of the M bus (FIG. 4), into the outqueue buffer 69. The store outqueue signal causes each word on the M bus to be written into the outqueue buffer 69 in a location specified by the outqueue counter 77. Each store outqueue signal also causes the outqueue counter 77 to be advanced by one.
As the words are being read from memory, the address word is being incremented by one, and the count of the words to be sent is being decremented by one. If the count reaches zero before fifteen words are read from memory, the remainder of the outqueue buffer is filled with zeros to pad out the data packet.
In addition, as the words are being loaded into the outqueue buffer 69, the microprogram 115 (FIG. 2) is calculating a modulo-two sum of the data words. After the fifteenth data word has been loaded, this odd check-sum word is loaded into the sixteenth location of the outqueue buffer 69.
At this time the outqueue counter 77 has a value of count 15 and this value, in combination with the store outqueue signal, causes the processor fill state logic 73 to advance from the FILL state to the FULL state as shown in FIG. 7.
At this point the microprogram 115 has completed loading of the data into the outqueue 69. The microprogram now waits for the packet to be transmitted by testing for occurrence of the ready (RDY) signal shown in FIG. 7.
While waiting for the packet to be transmitted, the microprogram 115 increments a timer; and if the timer runs out or expires before the ready (RDY) signal is asserted, the microprogram issues the clear outqueue (CLOQ) signal to the processor fill state logic 73 (see FIG. 4). This causes the processor fill state logic 73 to return to the empty state as shown in FIG. 7, and the microprogram then terminates the SEND instruction with the time out indication.
In normal operation, the FULL state of the processor fill state logic 73 qualifies the bus empty state logic 75 to advance from the IDLE state to the SYNC state shown in FIG. 7. Next, the SYNC state automatically advances to the SEND state, and this state causes the SEND REQUEST signal to be issued to the bus controller 37. The SEND REQUEST signal initiates a packet transfer sequence described earlier.
As described earlier, when the sender processor module has been identified by the bus controller 37 by polling, and when the receiver processor module has accepted the packet transfer by means of the RECEIVE ACKNOWLEDGE signal, the data packet is gated from the outqueue buffer 69 through the outqueue pointer 79 to one of the data buses 57 for loading into the inqueue of the receiver processor module.
As the sixteenth word is gated to the bus, the value of the outqueue counter count 15, in combination with the SEND COMMAND signal and the SENDER SELECT signal causes the SEND state of the bus empty state logic 75 to advance to the DONE state.
The DONe state qualifies the FULL state of the processor fill state logic 73 (as shown by the dashed line arrow going from the DONE state to the indicated transition from the FULL state in FIG. 7) to advance to the WAIT state.
Next, the WAIT state qualifies the DONE state to advance to the IDLE state as illustrated by the state diagram in FIG. 7.
Finally, the IDLE state qualifies the WAIT state to advance to the EMPTY state as also indicated in the state diagram of FIG. 7.
The empty state, of the processor fill state logic 73, provides the READY indication to the microprogram 115.
If the packet just transmitted was the last packet in the specified data block, the SEND instruction is terminated and the successful block transfer indication is given.
If the packet transmitted is not the last packet in a data block, then the sequence described above is repeated until all words in the block have been transmitted, or until a timeout error has occurred.
The SEND instruction is interruptable and resumable; however, the SEND instruction is only interruptable between packets; and the interruption of the SEND instruction has no effect on the data transmitted.
Thus, by means of a single software instruction (the SEND instruction) a data block of up to 32,767 words is transmittable from a sender processor module to a receiver processor module, and accuracy of the transmission is checked by the packet check-sum. Also, the transmission occurs at a high data transfer rate, because the buffering provided by the outqueue buffer 69 of the sender processor module enables the transfer to be made at interprocessor bus speed independent of the memory speed of the sender processor module. This allows efficient use of this communication path between a number of processor modules on a time slicing basis.
As noted above, there is no instruction for receive.
For a processor module to receive data over an interprocessor bus, the operating system in that processor module must first configure an entry in the bus receive table (BRT). Each BRT entry contains the address where the incoming data is stored and the number of words expected.
While the sender processor module is executing the send instruction and sending data over the bus, the bus receive hardware and the microprogram 115 in the receive processor module are storing the data away according to the appropriate BRT entry (this occurs interleaved with software program execution).
When the receiver processor module receives the expected number of words from a given sender, the currently executing program is interrupted, and that particular bus transfer is completed.
FIG. 5 shows the logic diagram and FIG. 8 shows the state diagram for the bus receive hardware.
As previously pointed out, there are identical X and Y inqueue sections 65 in each processor module for the X bus and the Y bus. Only one of the inqueue sections will therefore be referred to the description which follows.
After initial reset of a processor module, or after a previous receive operation, the RESET state of the processor empty state logic 101 advances to the READY state. The READY state qualifies the SYNC state of the bus fill state logic 93 to advance the logic to the ACKNOWLEDGE state.
In this ACKNOWLEDGE state the inqueue section 65 returns RECEIVE ACKNOWLEDGE to the bus controller 37 in response to a SELECT 63 (see FIG. 2) of that processor module 33. This indicates the readiness of the X inqueue section 65 to receive the data packet.
In the packet transfer sequence (described in detail above) the combination oft he SELECT of that processor module and the RECEIVE COMMAND signal qualify the ACKNOWLEDGE state of the bus fill state logic 93 and to advance to the RECEIVE state.
At this state transition the sender register 95 (FIG. 5) is loaded with the number of the sending processor module.
In the RECEIVE state the data packet is loaded from the data bus to the inqueue buffer 97 under control of the inqueue counter 99.
As the sixteenth word of the packet is loaded, it causes the RECEIVE state to advance to the FULL state (see FIG. 8).
Now the FULL state qualifies the READY state of the processor empty state logic 101 to advance to the MICROINTERRUPT state as shown in FIG. 8. The MICROINTERRUPT state presents an INQUEUE FULL state to the CPU interrupt logic. This INQUEUE FULL signal causes a microinterrupt to occur at the end of the next software instruction if the MASK bit corresponding to that bus is on.
The bus receive microprogram 115 activated by the interrupt first of all issues a LOCK signal (see FIG. 5) to the processor empty state logic 101. This causes the MICROINTERRUPT state of the processor empty state logic 101 to advance to the DUMP state.
The LOCK signal also selects either the X inqueue or the Y inqueue; subject, however, to the condition if both inqueues are full and enabled, the X inqueue is selected.
Next, the microprogram 115 issues the K/SEND signal which causes the sender register 95 contents to be gated to the K bus (as shown in FIG. 5) to obtain the packet sender's processor number.
Using this processor number, the microprogram 115 reads the sender processor's BRT entry to obtain the address and count words.
If the count word is zero or negative, the packet is discarded; and in this case, the microprogram 115 issues a RINT signal which causes the processor empty state logic 101 to advance from the DUMP state to the RESET state as shown in FIG. 8. In this event there is no further action. The microinterrupt is terminated, and software instruction processing is resumed.
If the count is positive, the microprogram 115 reads words from the inqueue buffer 97 to the K bus by means of the K/INQUEUE signal as shown in FIG. 5.
With each occurrence of the K/INQUEUE signal, the inqueue counter 99 is incremented to scan through the inqueue buffer 97.
As each data word is read from the inqueue buffer 97, the count word is decremented, the memory address word is incremented, and the data word is stored into memory.
If the count word reaches zero, no more words are stored in memory, a completion interrupt flag is set, and the sender processor number is saved in a memory location. In that event the fill state bus logic 93 stays in the FULL state until cleared by a software RIR instruction.
Thus, when a data block has been completely received, the count word will contain a value between minus 14 and zero. After the completion interrupt occurs, no further transfer to the processor over the bus which cause the interrupt are permitted until the inqueue is cleared with an RIR instruction.
As the data words are stored into the memory, a modulo-two sum of packet data is calculated.
If the check sum is bad, the word count in the BRT entry is set to minus 256, a completion interruprupt flag is set, and the sender processor number is saved in memory. As above, the bus fill state logic 93 stays in the FULL state until cleared by an RIR instruction.
If the count word does not reach zero, and the check sum is good, the bus receive microprogram 115 issues the RINT signal to the processor empty state logic as shown in FIG. 5 which causes the DUMP state of the processor empty state logic 101 to advance to the RESET state as shown in FIG. 8.
The RESET state of the logic 101 qualifies the bus fill state logic 93 to advance from the FULL state to the SYNC state as also shown in FIG. 8.
At this point, the logic has been returned to the state it was in before the packet was received, thus enabling the receipt of more packets.
These packets may be from the same sender, completing that data block, or the packets may be from some other sender.
This completes the action of the bus receive microprogram 115 and the microprocessor 113 resumes processing of software instructions.
When a bus receive completion interrupt has occurred, the software interrupt handler obtains the sender processor number from the memory location where that number was saved, and the software interrupt handler can then detect is a check sum error occurred by examining that sender processor's bus receive table count word.
In the case of a transmission error, the count word has been set to minus 256. Otherwise, the count word will contain a value between minus fourteen and zero.
As mentioned above, it is thus the responsibility of the bus receive completion software interrupt handler to issue the RINt signal (by means of an RIR software instruction) to reenable the inqueue 65.
In summary on the receive operation, just as the sending of a data block by a sender processor module is viewed by software as a single event, the receiving of data by a receiver processor does not cause a software interrupt of the receiver processor module until the entire data block has been received or until an error has has occurred. Also, the inqueue 65 serve as buffers to allow the transmission of data to occur at bus transmission rates while allowing the storing of data into memory and the checking of the data to occur at memory speed. This ability to use the high transmission rate on the bus insures adequate bus bandwidth to service a number of processor modules on a time slicing basis. Finally, the provision of a check sum word in each data packet provides a means in the receiver processor module for checking the accuracy of the data received over the multiprocessor communication path.
Information sent over the interprocessor bus is sent under the control of the operating system and is sent from one process in one processor module 33 to another processor in another processor module 33. A process (as described in detail above in the description of the Multiprocessor System) is a fundamental entity of control in the software system; and a number of processes coexist in a processor module 33. The information sent over the interprocessor bus between processes in different processor modules consists of two types of elements, control packets and data.
The control packets are used to inform the receiving processor module 33 about message initiations, cancellations, and data transfers.
In this regard it should be noted that, while the interprocessor buses 35 interconnect the processor modules 33, a process within a particular processor module 33 communicates with another process or with other processes within another processor module 33 through bus traffic between two processor modules 33 will therefore contain pieces of interprocess communications that are in various states of completion. Many interprocess communications are therefore being interleaved on an apparently simultaneous basis.
The hardware is time slicing the use of the interprocessor bus 35 on a packet level, and multiple processes are intercommunicating both within the processor modules 33 and to the extent necessary over the interprocessor buses 35 in message transactions which occur interleaved with each other. Under no circumstances is an interprocessor bus 35 allocated to any specific process-to-process communication.
Data information is sent over the interprocessor bus in one or more packets and is always preceded by a control packet and is always follwed by a trailer packet.
The control packet preceding the data packets is needed because a bus is never dedicated to a specific message, and the control packet is therefore needed to correctly identify the message and to indicate how much data is to be received in the message.
This information transfer (control packet, data information, trailer packet) is made as an indivisible unit once it is started. The sender processor module sends the data block as an individual transmission (consisting of some number of data packets) and sends the trailer packet as an individual transmission; and only then is the sender processor module able to send information relating to another message.
The trailer packet serves two purposes.
First of all, if there is an error during a data transmission (and therefore the rest of the data block must be discarded), the trailer packet indicates the end of the block.
Secondly, if the sender attempts to send too much data (and against the block must be discarded), the trailer packet provides a means for recognizing data has been transmitted and the data transmission has completed.
The information transmitted is either duplicated over different paths (so that it is insured that the information will get to the receiver) or a receiver acknowledgment is required (so that the information is repeated if necessary). Any single bus error therefore cannot cause information to be lost, and any single bus error will not be seen by the two processes involved.
The bus receives software interlocks with the bus receive hardware (the inqueue section 65 shown in FIG. 2) by controlling the transfer of information from the inqueue into the memory 107.
This allows such operations as changing the bus receive table information to be done without race conditions (synchronization problems).
Once the bus receive table information has been updated, the interlock is removed by clearing the previous completion interrupt and by reenabling the bus receive microinterrupts by setting on the bus makes bit in the mask register.
This does two things. It allows the inqueue hardware to accept a packet into the inqueue, and it also enables the bus receive microprogram to transfer the information from the inqueue into memory.
The hardware/software system is so constructed that no information is lost on a system power failure (such as a complete failure of AC power from the mains) or on a line transient that causes a momentary power failure for part of the system.
This hardware/software system coaction includes a power warn signal (see line 337 of FIG. 3) supplied to the inqueue section 65 (see FIG. 2) so that, at most, one further packet of information can be loaded into the inqueue after the receipt of the power warn signal.
The software action in this even includes a SEND instruction to force the inqueues to be full. The after the process or module 33 has received its power warn signal, so that the state of every transfer is known when logic power is removed.
The interprocessor buses 35 are used by the operating system to ascertain that other processor modules in the system are operating. Every N seconds, each of the processor modules 33 sends a control packet to each processor module 33 in the system on each interprocessor bus 35. Every two N seconds, each processor module 33 must have received such a packet from each processor module 33 in the system. A processor module that does not respond is considered down. If a processor module does not get its own message, then that processor module 33 known that something is wrong with it, and it will not longer take over I/O device controllers 41.
FIG. 42 diagrammatically illustrates how a particular application program can run continuously even though various parts of the multiprocessor system can become inoperative.
Each of the separate views shown in FIG. 42 illustrates a multiprocessor system configuration which consists of two processor modules 33 connected by dual interprocessor buses 35 (indicated as an X bus and a Y bus), a device controller 41 which controls a number of keyboard terminals, and another device controller 41 which controls a disc.
The individual views of FIG. 42 indicate various parts of the multiprocessor system rendered unserviceable and then reintroduced into the multiprocessor system in a serviceable state.
The sequence starts with the upper left hand view and then proceeds in the order indicated by the broad line arrows between the views. The sequence thus goes from the condition indicated as (1) Initial State to (2) CPU 0 Down to (3) CPU 0
Restored to (4) CPU 1 Down to (5) CPU 1 Restored (as indicated by the legends above each individual view).
In the initial state of the multiprocessor system shown in the view entitled "Inititial State" at the upper left hand corner of FIG. 42, one copy (PA) of the application program is active. This copy makes a system call to create the copy PB as a backup to which the application program PA then passes information. All of the I/O is taking place by way of the processor module 0. In this initial state either interprocessor bus 35 may fail or be brought down (as indicated by the bars on the X bus) and can be then reintroduced into the multiprocessor system without producing any effect on the application program PA.
In the next view (the view entitled "CPU 0 Down") the processor module 0 is rendered unserviceable. The multiprocessor system informs the application program PA that this has happened, and the application program PA no longer tries to communicate with the program 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 nonstop without interruption over the I/O bus 39
connecting 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 multiprocessor system, as illustrated in the center top view of FIG. 42 and entitled "CPU 0 Restored", the processor module 0 is now brought back into service by way of a console 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 application program PA tells the multiprocessor system to create another copy of the application program in the processor module 0. This other copy is designated as PC. The terminals continue nonstop without interruption.
Next, the processor module 1 is rendered inoperative, as illustrated 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 automatically performs all of the I/O by way of the processor module 0. The terminals continue nonstop without interruption.
Finally, as indicated by the top right hand view of FIG. 42 entitled "CPU 1 Restored", the processor module 1 is rendered operable by way of a console command and is reloaded with the multiprocessor system from the disc by way of the processor module 0. The application program PC is informed that the processor module is now 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.
It is an important features of the multiprocessor 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 interprocessor buses but also for all elements of the multiprocessor system, such as power supplies, fans in the rack, etc. The multiprocessor system 31 thus is a true nonstop system.
THE INPUT/OUTPUT SYSTEM AND DUAL PORT DEVICE CONTROLLER
The multiprocessor system 31 shown in FIG. 1 includes a input/output (I/O) system and dual port device controller 41 as noted generally above.
The general purpose of the I/O system is to allow transfer of data between a processor module 33 and peripheral devices.
It is an important feature of the present invention that the data transfer can be accomplished over redundant paths to insure fail soft operations so that a failure of a processor module 33 or a failure of a part of a device controller 41 will not inhibit transfer of data to and from a particular peripheral device.
Each device controller 41 has dual ports 43 and related structure which, in association with two related I/O buses 39, permit the redundant access to a peripheral device as will be described in more detail below.
The I/O system of the present invention also has some particularly significant feature in terms of performance. For example, one of the performance features of the I/O system of the present invention is the speed (bandwidth) at which the input/output bus structure operates. The device controllers 41 collect data from peripheral devices which transmit data at relatively slow rates and transmit the collected data to the processor modules in a burst multiplex mode at or near memory speed of the processor modules 33.
As illustrated in FIG. 1, each processor module 33 is attached to and handles a plurality of individual device controllers 41; and this face makes it possible for each device controller 41 to be connected (through dual ports 43) to more than one processor module 33 in a single multiprocessor system.
With reference now to FIG. 12 of the drawings, each processor module 33 includes, in addition to the interprocessor control 55 noted above, a central processor unit (CPU) part 105, a memory part 107 and an input/output (I/O channel part 109.
As illustrated in FIG. 12 and also in FIG. 1, each device controller 41 controls one or more devices through connecting lines 111 connected to a star pattern, i.e. each device independently connected to the device controller.
In FIG. 12 a disc drive 45 is connected to one device controller 41 and a tape drive 49 is connected to another device controller 41.
With continued reference to FIG. 12, each CPU part 105 includes a microprocessor 113. A microprogram 115 is associated with each microprocessor 113. A part of the microprogram 115 is executed by the microprocessor 113 in performing I/O instructions for the I/O system. The I/O instructions are indicated in FIG. 12 as EIO (execute I/O), IIO (interrogate I/O), HIIO (interrogate high priority I/O); and these instructions are illustrated and described in greater detail below with reference to FIGS. 15, 16 and 17.
The microprocessor 113 has access to the I/O bus 39 by way of the I/O channel 109 by a collection of paths 117 as illustrated in FIG. 12.
With contained reference to FIG. 12, the I/O channel 109 includes a microprocessor 119, and a microprocessor 121 is associated with the microprocessor 119.
The microprogram 121 has a single function in the multiprocessor system, and that function is to perform the reconnect and data transfer sequence illustrated in FIG. 16 (and described in more detail below).
The I/O channel 109 of a processor module 33 also includes (as shown in FIG. 12) data path logic 123.
As best illustrated in FIG. 13, the data path logic 123 includes a channel memory data register 125, an input/output data register 127, a channel memory address register 129, a character count register 131, an active device address register 133, a priority resolving register 135 and parity generation and check logic 137.
The path 117 shown in FIG. 12 includes two buses indicated as the M bus and the K bus in FIG. 13.
The M bus is an outbus from the microprocessor 113 and transmits data into the input/output data register 127.
The K bus is an inbus which transmits data from the data path logic 123 into the microprocessor 113.
With reference to FIG. 12, a path 139 connects the data path logic 123 and the memory subsystem 107.
This path 139 is illustrated in FIG. 12 as including both a hardware path 139A and two logical paths 139B and 139C in the memory subsystem 107 of a processor module 33.
Logical paths 139B and 139C will be described in greater detail below in connection with the description of FIG. 16.
The hardware path 139A includes three branches as illustrated in FIG. 13.
A first branch 139A-1 transmits from memory into the channel memory data register 125.
A second path 139A-2 transmits from the channel memory address register 129 to memory.
And a third path 139A-3 transmits from the input/output data register 127 to memory.
With reference to FIG. 12, the input/output channel of a processor module 33 includes a control logic section 141.
This control logic section 141 in turn includes a T bus machine 143 (see FIG. 13) and request lines RECONNECT IN (RCI) 145, LOW PRIORITY INTERRUPT REQUEST (LIRQ) 147, HIGH PRIORITY INTERRUPT REQUEST (HIRQ) 149 and RANK 151 (see FIG. 14).
The I/O bus 39 shown in FIG. 14 and FIG. 12 also includes a group of channel function lines 153, 157 and 159. See also FIG. 13. The TAG bus (T bus) 153 consists of four lines which serve as function lines, and there are three lines SERVICE OUT (SVO) 155, SERVICE IN (SVI) 157, and STOP IN (STI) 159 which serve as handshake lines as indicated by the legends in FIG. 14.
As shown in FIG. 14 and FIG. 12, the I/O bus 39 also includes a group of data lines 161, 163, 165, 167 and 169.
The DATA BUS lines 161 and PARITY 163 are bidirectional and serve as data lines and as indicated in FIG. 14, there are sixteen DATA BUS lines 161 and one PARITY line 163 in this group.
The lines END OF TRANSFER (EOT) 165, PAD OUT (PADO) 167 and PAD IN (PADI) 169 serve as data status lines, and indicate special conditions that may occur on the data lines 161 and 163 from time-to-time.
Finally, the I/O bus 39 includes a reset line (IORST) 171 as also shown in FIG. 14 and in FIG. 12.
Each T bus command illustrated in FIG. 18 requires some specific format on the data bus 161 while a T bus command is valid. This specific data bus format is illustrated for the T bus functions load Address and Command (LAC) and Read Device Status (RDST) shown in FIG. 18, for the preferred embodiment.
In the case of the T bus function LAC, the data or field transmitted on lines .0. to 5 of the data bus 161 specify the operation to be performed; the field transmitted on lines 8 to 12 of the data bus specify the device controller 41 (or more precisely the port 43 of that device controller which is attached to the data bus 161) to which the command is addressed; and the field transmitted on data bus lines 13 to 15 specify which device attached to the device controller is to be operated on by that device controller 41 in response to this command.
In the case of the T bus function RDST, data bus bits .0., 1, 2 and 3 indicate ownership error, interrupt pending, device busy, and parity error respectively. Bits 4 to 15 return device dependent status.
The functions on the T bus are transmitted in three sequences, shown in FIGS. 15, 16 and 17 and described in detail below.
Each T bus function is asserted by the channel and a handshake sequence is performed between the channel 109 and the device controller 41 using the handshake lines 155, 157 and 159 to acknowledge receipt of the T bus function. Control of the T bus and handshake is the function of the T bus machine 143 in FIG. 13.
FIG. 28 is a timing diagram showing the operation of the handshake between the I/O channel 109 and the ports 43.
As illustrated in FIG. 28, line 155 terminates the service out signal (SVO) and line 157 transmits the service in signal (SVI).
The channel clock cycle is shown in vertical orientation with the SVO and SVI signals.
As illustrated in FIG. 28, the service in (SVI) signal is not synchronized with the channel clock and may be asserted at any time by the device controller in response to a service out signal from the I/O channel 109.
Before asserting service out (SVO), the channel 109 asserts the T bus function and, if required, the data bus.
The channel then asserts a service out signal as indicated by the vertical rise 279 in FIG. 28; and, SVO remains true until the device controller responds with service in (SVI) (218), acknowledging the channel command; SVI remains true until the channel drops SVO.
When the device controller 41 asserts the service in (SVI) signal, the channel 109 removes the service out (SVO) signal (as shown by the vertical drop 283 in FIG. 28) in a time period typically between one and two clock cycles; and in response, the device controller drops service in (SVI) as shown by the vertical drop 285 in FIG. 28.
When the device controller drops the service in (SVI) signal, the channel 109 is free to reassert a service out signal (SVO) for the next transfer; however, the channel will not reassert SVO until SVI has been dropped.
The arrows 281A, 283A and 285A in FIG. 28 indicate the responses to the actions 279, 281, 283 respectively.
The handshake is completed at the trailing edge of the vertical drop 285 as shown in FIG. 28.
On an output transfer, the interface data register 213 of the controller accepts the data at the leading edge of service out (vertical rise 279) and transfers the data to the control part of the device controller 187 at the trailing edge of the service out (the vertical drop 283).
On an input transfer the channel 109 accepts data from the service controller at the trailing edge of service out (the vertical drop 283).
Thus, a two line handshake is used to interlock transfer of information between the channel 109 and its device controller 41, since they act asynchronously.
This is the general handshake condition, indicated as handshake 2L in FIG. 15, 16 and 17.
In addition, two special handshake considerations occur, when appropriate.
First, channel commands used to select a device controller are not handshaken by SVI, since no single device controller is selected during this time.
These commands include (as shown in FIG. 18):
SEL--Select;
LAC--Load Address & Command;
HPOL--Hi Priority Interrupt Poll;
LPOL--Lo Priority Interrupt Poll; and
RPOL--Reconnect Interrupt Poll.
Also, commands used to terminate a sequence are not handshaken by SVI since they cause a selected device controller to deselect itself.
These commands include (as also shown in FIG. 18):
<