Note: Descriptions are shown in the official language in which they were submitted.
~9,4a~S~
This invention generally relates to data processing systems and
more specifically to apparatus for interconnec-ting the various units compris-
ing the system.
A digital data processing system generally comprises three basic
elements: a memory unit, and input/output element and a processor element.
The memory element stores information in addressable storage locations. This
information includes bot~ data and instructions for processing the dat~. ~he
processor element causes information to be transferred between it and the
memory element, interprets the incoming information as either data or in-
structions and processes the data in accordance with the instructions. Theinput/output elements also communicate with the memory element in order to
transfer input information to the system and to obtain processed information
from it.
Over the years, as the demands for computing po~er and speed have
increased, it has been sug~ested and is known to use several processor ele-
ments in a single processing system. In such multi-processing systems~ it is
normally desirable that each of the processors have partial or complete access
to the same memory elements and input/output elements. It is therefore nec-
essary to provide means to prevent the processors from accessing the same
element simultaneously. Several arrangements for this are known. In a first
arrangement, the processing elements are assigned priority levels whereby
processing units having a higher priority are permitted to access the memory
elements and input/output elements over processing units having lower prior-
ity. This inevitably slows the turnaround for programs being run on the
units having lesser priority.
A second arrangement is to provide a computer network including a
master computer system to arbitrate between a plurality of slave processors.
This arbitration may be determined by such factors as the length of time a
-- 1 -- ~.,
.
. ' ' ~ .
~4
slave processor would have to access the memo~ element or the input/outpu-t
element, the length of tiMe since its last access, or the like. Eowever, if
the master system malfunctions, the slaves are prevented from accessing the
memory or input/output elements until the master system is repaired. Fur-
thermore, the master system may create a bottleneck i~ the requests for
access to the me~ory or input/output elements are too rapid for the master
system to arbitrate, slowing the slave processors.
In a third arrangement an interaction control unit may be connected
between the processing units and the memory units and input/output units to
control access between the processing units and the memory units and the
input/output units. ~he interaction control unit does not prevent the pro-
cessing units themselves from operating while they are waiting to access the
memory units and input/output elements. This arrangement otherwise has the
same problems as the master-slave processing arrangement discussed above.
Furthermore, as the increase in demands for computing power have
increased, more and more control information has to be passed among the var-
ious elements of the system. This has required addition of a number of con-
trol lines among the elements, adding to the expense both for the control
lines themselves and for the additional electronic circuitry required to
interpret information on the lines and place information on the lines.
It is an obJect of this invention to provide a multi-processor data
processing system in which the various central processing units are prevented
from simultaneously accessing the memory elements and the input/output ele-
ments simultaneously.
It is in another ob~ect of the invention to provide a multi-pro-
cessing data processing system in which the multiple processors are prevented
from accessing the other elements of the system wi-thout the use of a pre-
assigned priority, or a master unit or interphase.
-- 2 --
In accordance witb this inventlon, a data processing system is pro-
vided in which all connections between the variolls elements are made on a
single bus. The bus includes lirles for arbitrution, for information trans-
fer and for control. The information transfer portion of the various ele-
ments includes apparatus for issuing a command for a loching operation which
is received by other processors in the system. ~his command prevents the
other processors from issuing the same type of locking command until an un-
locking command is issued. Any processor can issue such an unlocking com-
mand.
In conjunction with this apparatus, only one line is required to be
driven to indicate that the information transfer buses are in use instead of
the usual plurality of lines between the various elements.
Thus, in accordance with the invention, there is provided a data
processing system including a plurality of data means including a first data
means and means for interconnecting said data means including a plurality of
means for conveying signals among said data means, said first data means in-
cluding means for issuing instructions on said interconnection means, includ-
ing a LOCK instruction to permit said first data means to transfer informa-
tion onto said interconnection means and to prevent the other data means from
transferring information along said interconnection means with a LOCK in-
struction and an UNLOCE instruction for permitting the other data means to
transfer information along said interconnection means with a LOCK instruc-
tion, each of the data means including switching means connected to said
interconnection means responsive to a LOCK instruction previously issued by
said first data means for preventing its respective data means from trans-
ferring information on said interconnection means with a LOCK instruction,
each of said switching means being responsive to an U~LOCK instruction issued
by any data means for permitting its respective data means to transfer infor-
-- 3 --
mation on said interconnection means i~ the UNLOCK instruction is more recentthan a previous LOCK instruct;on.
The invention i5 pointed out with particularity in the impending
claims. The above and ~urther obJects and advantages of the invention may be
better understood by re~erring to the following description taken in con~unc-
tion with the accompanying drawings.
~rief Description o~ the Drawings
Figure 1 is a block diagram of a digital data proces9ing system
constructed in accordance with this in~ention;
Figures 2A through 2C pictorially depict data types that are uti-
lized in con~unction with a speci~ic embodiment of the invention;
Figure 3 illustrates the lines and corresponding signals that con-
stitute an interconnection for nexuses in the digital data processing system
in Figure l;
Figure 4 is a diagram depicting the sequence ~or a read transaction
that can occur between nexuses shown on Figure 3.
Figure 5 is a diagram that depicts sequences of operations for a
write transaction that can occur between the nexuses shown in Figure 3;
Figure 6 is a schematic diagram of a portion of the master nexus
shown in Figure 3; and
Figure 7 is a schematic diagram of a portion of a slave nexus shown
in Figure 3.
As exemplified in Figure 1, the basic elements o~ a data processing
system, in particular a multi~processor system, comprises a first central
processor unit 10, a second central processor unit 10A, memory units 11, and
input/output (I/O) units 12. A bus 14 interconnects -the central processor
units 10 and 10A, memory unit 11 and I/O ~mits 12. More than two central
processor units may be connected to bus 1~ in a mul-ti~processor environment.
-- 4 --
1$4
These would be connected to bus 14 in the manner similar to processor units
10 and lOA.
The central processor unit 10 comprises an operator's console 15, a
bus interface and other conventional circuits normally provided in the cen-
tral processor unit. Central processor unit lOA, and other central processor
units that may be attached to bus 14, may be similar to central processor
unit 10; however, all that is necessary is that the central processor units
have the capability to interface to bus 14. Interface circuit 16 receives
all data from the memory and performs all transactions for the other cir-
cuitry in central processor unit 10~
The operator's console 15 serves as the operator interface. It
allows the operator to examine and deposit data, halt the operation of the
central processor unit 10 or step it through a sequence of program instruc-
tions. It also enables an operator to initialize the system through a boot-
strap procedure and perform various diagnostic tests on the entire data pro-
cessing system. Central processor unit lOA generally will include an opera-
tor's console (not shown).
In Figure 1, the memory ùnit 11 includes a memory controller 20
which connects to a plurality of memory arrays 21.
Several types of I/O units 12 are shown. An I/0 bus adapter 22
interconnects several input/output devices 23, such as~ for example, tele-
typewriters or cathode ray tubes to the bus 14. The interconnection opera-
tion and transfer signals between the I/0 bus adapter 22 and the I/0 devices
is disclosed in part in United States Patent 3,710,324.
The two other I/0 units 12 shown in Figure 1 provide a secondary
storage facility for the data processing system. They include a secondary
,
'' '' '~' ' .
storage bus adapter 24 and a plurality of disk drives 25. There ~s also
shown a second secondary storage bus adapter 26 and a tape drive 27. The
interconnection of the secondary storage bus adapters 24 and 26 and their
respective disk drives 25 and tape drive 27 is disclosed in United Sta-tes
Patent 3,99~,163.
The bus interconnects the various units or elem~nts Or a aata pro-
cessing system. Prior to describing the transfer of in~ormation between dif-
ferent pairs of the units connected -to the bus, it will be helpful first to
establish some definitions for terms that have already been used and that
will be used throughout the remainder of this description.
"Information" is intelligence used to control and provide the basis
for data processing. It includes data and address, instruction and status
information. "Data" includes information which is the obJect of or the re-
sult of processing.
Transfers of information between the units in the data processing
system shown in Figure 1 occur over the bus 14 and involve transfers of dis-
crete information items. Each information item has a characteristic size on
bus 14. Qther elements may process information items having other si~es.
The most elementary information item is the byte. In one specific embodiment
to the data processing system shown in Figure 1, the byte includes eight bi-
nary digits (or bits). Figure 2A depicts eight contiguous bytes. l~e next
larger data item size is a "word", as shown in Figure 2B. A word comprises
two contiguous bytes. Two contiguous words constitute a "long word", as
shown in Figure 2C.
The bus 14 can transfer all information in parallel as a longword.
In the two contiguous longwords shown in Figure 2A, byte 0 is the least sig-
nificant byte position for each longword. ~ord 0 and long word 0 are the
least significant word and long word position in Figures 2B and 2C respec-
-- 6 --
tively. The following discussion assumes that corresponding alignments aremaintained within the data processing system; however~ there is no require-
ment that any such alignments be maintained.
If two elements are to exchange information over the bus 1~ at
least two "bus transactions" are necessary. During a first bus transaction,
one element re~uests the information exchange and transmits command and ad-
dress information on the bus 14. The other element, designated by the ad-
dress information, responds and prepares to complete the information ex-
change. This completes a first bus transaction. During the second bus
transaction, the information to be exchanged passes over the bus lL~.
Each element that connects to the bus 1~ is called a ne~us. The
specific system shown in Figure 1 includes 6 nexuses. A nexus is further
defined in terms of its function during an exchange of information. During
such an exchange, the nexus that transmits command and address information
on to the bus 1~ is called a "master nexus" 30A in Figure 3. The unit which
responds to that command and address information is called a "slave nexus"
30B. Thus, if a central processor unit needs to retrieve data from the mem-
ory controller 20, the central processor unit becomes a master nexus and
transmits a READ (or RF~D LO~E) command and memory address during a first bus
transaction. Memory controller 20 becomes a slave nexus when it receives and
accepts the command and address information from the bus 11~.
A nexus is also defined as a transmitting or receiving nexus. A
transmitting nexus drives the signal lines while the receiving nexus sa~ples
and examines the signal lines during each bus transaction. In the foregoing
example, the central processor unit is a transmitting nexus during the first
bus transaction and a receiving nexus during the second bus transaction.
Similarly, the memory controller 20 is a receiving nexus during the first bus
transaction and is a transmitting nexus during the second bus transaction.
-- 7 --
Similar transactions occur for information exchanges between any two nexuses.
Xowever, the memory controllers normally function onl~J as slave nexuses
while central processor units normall~ function only as master nexuses.
In accordance with the specific embodiment of this invention de-
scribed in this application, the bus 14 conveys a number of signals to and
from the various units that connect to it over corresponding conductors.
These conductors and signals can be listed in three general claBses:
1. arbitration, over arbitration bus line 31,
2. information transfer, over the data/address bus lines 23 and
33; and
3. control, over control bus lines 34-38.
Lines 31-38 comprise bus 14. The data address bus or information
transfer bus includes information lines 32 and function lines 33. Instruc-
tions are sent over function lines 33.
The control ccnductors and signals include a STATUS line 3l~, a HOLD
line 35, a WAIT line 36, a DBBZ line 37 and aCLOCK line 38. S~ATUS informa-
tion indicates whether the addressed me~ory location has the requested in-
formation and whether the information is valid. The HOLD signal~ when in-
serted on the HOLD line 35, prevents any of the nexuses from getting control
of the data/address bus. Hold signals may be used, for example, to allow
certain memories to control the rate at which write transactions occur.
The WAIT signal asserted on the WAIT line 36, is involved in inter-
rupt transactions. The DBBZ signal, or data/address bus busy signal when
asserted on the DBBZ line 37, indicates when a nexus is requesting informa-
tion or transmitting information over the data/address bus.
A number of instructions may be sent over the function lines 33,
including READ, READ LOCK, WRITE and WRITE UMLOCK. When a nexus issues a
READ instruction, it desires to read the contents of a location in memory
-- 8 --
whose address is transmitted over information transfer lines 32. A READ
LOCK instruction indicates that the commanding nexus desires to read the ad-
dressed location in ~emo~y and prevent other nexuses rrom gaining access to
the bus with their own READ LOCK instructions until a WRITE I~LOC~ instruc-
by c~ e ~ ~s
tion is placed on the function bus'. The RE~D LOCK instruction does not pre-
vent another master nexus from issuing a R~AD or l~RITE instruction. The
READ LOCK command is used primarily to prevent other processors or ne~uses
from gaining access to a memory which may have invalid information in the
memory or to read possibly invalid information. This is possible i~ the pro-
cessor that originally issued the READ LOCK instruction has access to thememory and may be modi~ying in~ormation held in memory at the same time the
other processor may be attempting to read ~rom the same memory~ To prevent
this, the first processor will issuea R~kD ~OC~ instruction to insure that
other nexuses are prevented ~rom eaining access to memory.
As mentioned above, two bus transactions are require2 for each
READ transaction and ~or each WRITE transaction. Figures 4 and 5, respec-
tively, exemplify, for the illustrative embodiment disclosed in this applica-
tion, the transactions for a READ and the transactions for a I~ITE. In Fig-
ures ~ and 5, the positive assertive signals are shown true, or asserted,
when at a high level for purposes o~ simplifying the explanation. Ground
assertion (i.e., asserted or true when low) circuits and signals normally
implement this lo~ic. Hcwever, the conversion between positive and ground
assertion logic, based upon de Morgan's theorem, is well known to those
skilled in the art.
Figure 4 exemplifies a READ transaction between two nexuses shown
in Figure 3. The CLOCK pulses identify and delimit the various bus cycles,
a new bus cycle starting on the leading edge of each positive-going pulse.
If the master nexus desires the use of the bus to read ~rom a slave nexus
3~;~
such as memory~ the master ~ill assert its priority signal on the arbitra-
tion bus 31. I~ its priority is the highest, and i~ the HOLD and DBBZ lines
are all at non-asserted levels~ the master will obtain control of bus 14 by
assertine DBBZ as shown at time B on Figure ~. The master asserts DBBZ rOr
one cycle and simultaneously transmit address and control information on the
data/address bus 32 and 33. The master will then shift the DBBZ signal to
a non-asserted level.
The addressed slave then asserts DBBZ as sho~n from time C to time
D. No other nexus can obtain control of the bus while the slave is assert-
ing DBBZ. ~en the sIave is ready to transmit information to the master, theslave shifts DBBZ to a non-asserted level, and as shown ~rom time D to time
E, transmits the information on the data/address bus, and simultaneously
returns STAqUS information on the STATUS line 34.
Since the DBBZ line is non-asserted after time D, another master
may attempt to obtain control of the bus during the cycle beginning at time
D. During this cycle it can assert its priority signal and assert the DBBZ
line during the cycle beginning at E transmit address and control and begin
a new transaction. In this manner, the transactions can overlap by one
cycle, thereby reducing the transaction time. In other words, more accesses
to memory may be attempted during a given time period than if the bus trans-
actions did not overlap.
This overlapping may be shown in part by the STATUS signal in Fig-
ure 4. The left most STATUS signal, sent during its bus cycle immediately
preceeding time B may be, for example, from a previous transaction.
By having both the master and the slave nexus assert DBBZ on the
same line, the number of bus lines is reduced. It has been the practice to
include a number of BUSY lines indicating the bus is in use. By reducing the
number of BUSY lines the total number of lines in the bus and therefore the
-- 10 --
circ~try required to drive those lines i5 reduced.
Figure 5 exemplifies a W~ITE transaction. A master desirine to
WRITE asserts its priority signal over the arbitration line 31. When the
HOLD line and the DBBZ line are both at a non-a6serted level and the master's
priority is the highest, it obtains control of the DBBZ line and asserts
DBBZ. It simultaneously transmits address and control information on the
data/address bus for one cycle. The addressed slave then asserts DBBZ and
receives the data on the data/address bus. At the beginning of the final
cycle, the slave shifts DBBZ to a non-asserted level and transmits STATUS
information on the STATUS line 31~. ~he final cycle in this case begins at
time D. Since the DBBZ line is low, another master can assert its priority
signal and, if the HOLD and WAIT lines are non-asserted~ can obtain control
of the bus by asserting DBBZ at time E.
Figures 6 and 7 exemplify respectively master and slave circuitry
for shifting the DBBZ line between asserted and non-asserted levels.
The master circuit 50 shown in Figure 6 also provides means for
preventing the master nexus 30A from gaining access to the DBBZ line 37 with
a READ LOCK instruction if another master has previously issued a R~AD LOCK
instruction that has not been unlocked by a WRITE U~LOOK instruction.
Master 50 includes an instruction decoder 51 that actuates circuit
50 in response to an instruction such as READ, WRITE~ READ LOCK and WRITE
U~LOCK. If a READ LOCK instruction is issued, instruction decoder 51 sends
one input to NAND gate 52 high and one input to an AND gate 53 high. If, as
described hereinafter, the second input to NAMD gate 52 is low, the output
of ~AND gate 52 will be high, and, if the ~IOLD signal is low (unasserted) if
the master's ARBI~RATIOM line is high (indicating that this master has pri-
ority), and if the DBB~ line is currently lo~ (unasserted), the output of A~m
gate 53 will be high. On the next clock pulse from clock 5~, the set output
- 11 -
. ~
of D flip-flop 55 will go high thereby shiftin~ DBBZ line 37 to a high
(asserted) level. Inverter 511A then sends the output of AND gate 53 low.
At the next clock pulse flip-flop 55 is reset, shifting DBBZ to a non-assert-
ed level. The ~aster, therefore, asserts DBBZ for one cycle, the time be-
tween the first two clock pulses.
Circuit 50 includes an A~ID gate 56 and a D ~lip-flop 57 that iden-
tifies the first cycle of a master's bus transaction. Before flip-flop 55
asserts DBBZ, the reset output of flip-flop 57 will be high, as will the one
input to AND gate 56. When flip- Mop 55 asserts DBBZ, the second input to
AND gate 5~ goes high, and its output also eoes high. On the next clock
pulse, the flip flop 57 is set, sending its reset output low, and sending A~D
gate 56 low, A~TD gate 56 is therefore high only during the first cycle,
otherwise called the ADDRESS CYCLE.
Circuit 50 includes a JK flip-flop 58 that identifies the bus
transaction as being initiated by this particular master. When the output of
AND gate 53 goes high on the next clock pulse the set output of JK flip-flop
58 will also go high (and the reset output of flip-flop 58 will go low). By
sending the set and reset outputs flip-flop 58 high and low, respectively,
the transaction is indicated as having been initiated by this master.
Circuit 50 ~lso includes a second JK flip-flop 59 that identifies
when a READ LOCK instruction has been issued on the function bus and when a
~ITE U~LOCK instruction has been issued. Flip-flop 59 also identifies when
the previous READ LOCK instruction has been issued by this particular master.
If this master issued the READ LOCK instruction, it is not prevented from
issuing further RE~D LOCK instruction. Flip-flop 59 accomplishes this as
follows~ When a READ LOCK instruction is placed on the function bus 33 dur-
ing an ADDRESS CYCLE, inverters 60A decode the function lines instruction and
set the function inputs to AND gate 60 high. The output of A~D gate 56 will
- 12 -
; .
~3~
be high. Lf the READ LOCK instruction is not being issued by circuit 50, the
reset output of flip-flop 58 will be high. The output of AND g~te 60 will
therefore go high and on the next clock pulse, the set output of JK flip-flop
5g will go high. With the set output high, if a READ LOCK instruction is
decoded by instruction decoder 51, NAND gate 52 is driven low, and circuit 50
cannot assert DBBZ. Note that if a WRITE UNLOCK instruction ls issued, the
cicuit 50 is not similarly inhibited; thus any nexus may issue a WRITE
UNLOCK instruction. The set output of JK flip-flop 59 remains high until the
K input is driven high at a clock pulse. This occurs when a WRII'E UNLOCK
instruction is issued on the function bus during an address cycle. Inverter
61A decodes this instruction and sends the function inputs to AND gate 61
high. During the ADDRESS CYCLE, the output of AND gate 56 will go high which
sends the output of 61 high. This resets flip-flop 59 sending the set output
low. The flip-flop remains reset until set again by a READ LOCK instruction.
With the set output low, if a READ LOCK instruction is decoded by decoder 51,
NAND gate 52 will be high, permitting circuit 50 to assert DBBZ.
If, on the other hand, circuit 50 issues the READ LOCK instruction,
the reset output of flip-flop 58 will be low as will the output of AND gate 60.
Flip-flop 59 will therefore remain reset and the set output will be low. NAND
gate 52 will pass a READ LOCK instruction if the output of flip-flop 59 is low,
which can occur only when a previous READ LOCK instruction has been issued by
circuit 50, or if the previous READ LOCK instruction had been cancelled by the
WRITE UNLOCK instruction.
Figure 7 exemplifies an implementation for a slave circuit 70 for
driving the DBBZ line. When the master sends address information on the data/
address bus, the address decoder 71 decodes the address and identifies this
- 13 -
slave nexus as being the addressed slave. The address decoder 71 is connected
to one input of an AND gate 72. 'I'he output of ~ND gate 72 is connected to
the J input on JK flip-flop 73, which drives DBBZ line 37. The
- 13a -
,
,' : - ' -
DBBZ lin& 37 in turn is connected to AND gate 76 and the D input on D flip-
flop 77. The reset o~rtput on flip-flop 77 is connected to the other input on
AND gate 76. The output of AND gate 76 i5 connected to the second input on
AND gate 72. Flip-flop 77 identifies the fi.rst (address) cycle of the bus
transaction in a manner similar to R~D gate 56 in the master circuit 50.
ADDRESS CYCLE will be asserted for one cycle, after which it will shift to a
non-asserted level. When ADDRESS CYCLE is asserted, flip-flop 73 will be
asserted, driving DBBZ line 37. During subsequent clock cycles, A~DRESS
CYCLE and A~D gate 72 will be low, flip-flop 73 will remain asserted, how-
ever, until, as explained hereinafter, the information is ready to be sent.
An instruction decoder 78 in the slave nexus identifies when thedata is ready to be transmitted along the data/address bus, the data ready
H line would go high, resetting flip-flop 73 and shifting DBBZ line 37 low.
This drives the output of AND gate 76 low which in turn drives the output of
AND gate 72 low.
Flip-flops 73 and 77 are both clocked by CLOCK 54.
On a WRITE transaction, with reference to Eigure 6, a READ LOCK in-
struction will not be issued by instruction decoder 51. The READ LOCK line
will be low (non-asserte.d) so the nexus can WRITE whether or not a READ LOCK
instruction is on the function bus. The MEMORY REQUEST H line is asserted
for a WRITE transaction which drives AND gate 53 high, setting flip-flop 55
drivine DBBZ line 37.
The slave on a WRITE transaction asserts DBBZ in a manner similar
to a READ transaction. The slave drives DBBZ line 37 until it receives an
instruction indicating that the ne~t cycle is the last cycle. The slave's
instruction decoder 78 then drives the DATA READY H line high, resetting
flip-~lop 73. STATUS information is then transmitted by the slave to the
master along the STATUS line.
- 14 -
., :
The foregolng description is limited to a specific embodiment of
this invention. It will be apparent, however, that this invention can be
practiced in data processing systems having diverse basic construction or in
systems that use different internal circuitry than is described in the spec-
ification with the attainment of some or all of the foregoing objects and
advantages of this invention. Therefore it is the obJect of the appended
claims to cover all such variations and modifications which come within the
true spirit and scope of this invention.
