Note : Les descriptions sont présentées dans la langue officielle dans laquelle elles ont été soumises.
This invention generally relates to data processing systems and
more specifically to apparatus for interconnecting the various units com-
prising the system.
A digital data processing system generally comprises three basic
elements: a memory unit, an input/output element and a processor element.
The memory element stores information in addressable storage locations.
This information includes both data and instructions for processing the data.
The 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. The
input/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 power and speed have
increased, it has been suggested 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 there
fore necessary to pro~ide 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
priority. 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 bet~een a plurality of slave processors.
This arbitration may be determined by such factors as the length of time a
"~ ,,
slave processor wo~d have to access the memory elemen-t or the inputtoutput
element, the length of time since its last access, or the like. However, 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 if the requests ~or
access to the memory 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 connect-
ed 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. The interaction control unit does not prevent the pro-
cessing units themselves from operating while the~ 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. ~his 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 data processing sys-
tem having a minimum of control lines interconnecting the elements of the
system.
In conjunction with this apparatus, only one line is required to be
driven to indicate that the information transfer buses are in use instead o~
the usual plurality of lines between the various elements.
Thus, in accordance with a broad aspect of the invention7 there is
provided a data processing system including at least a first data means, a
~1~
second data means and interconnec-tion means includine a plurality of means
for conveying signals among said data means, and clocking means for eenerat-
ing clocking pulses, said first data means including means for inaicating
when it is to transfer information with said second data means along said
interconnection means,means connected to one of said conveying means and re-
sponsive to said one of said conveying means for determining wben said inter-
connection means iF. available to said first data means to permit it to effect
the transfer ~nd means connected to said indicating means, said one of said
conveying means and to said clocking means for asserting said one of said
conveying means f~or a predetermined number of clock pulses to indicate that
it is making an information transfer along said interconnection means; and
said second data means including means connected to said interconnection
means for determining that one of said data means is making an information
transfer with it and means connected to said one of said conveying means for
asserting said one of said conveying means after said predetermined number of
clock pulses to at the latest the end of the information transfer.
The invention is pointed out with particularity in the appended
claims. The above and further ob~ects and advantages of the invention may be
better understood by referring to the following description ta~en in conjunc-
tion with the accompanying drawings, in which:
Figure 1 is a block diagram of a digital data processing systemconstructed in accordance with this invention;
Figures 2A through 2C pictorially depict data types that are uti-
lized in conjunction with a specific embodiment of the inventionj
Figure 3 illustrates the lines and corresponding signa.ls that cQn-
stitute an interconnection for nexuses in the digital data processing system
in Figure l;
Figure 4 is a diagram aepicting the sequence for a read transaction
-- 3 --
~ ~0~
that can occur between nexuses sho~m 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;
Fi6ure 6 i5 a schematic diagram of a portion of the master nexus
shown in Figure 3; and
Figure 7 is a schematic dia~ram of a portion of a slave nexus shown
in Figure 3.
As exemplified in Figure 1, the basic elements of a data processing
system, in particular a multi-processor system, comprises a first central
processor unit 10, a second central processor unit lOA, memory units 11, and
input/output (I/0) units 12. A bus 14 interconnects the central processor
units 10 and lOA, memory unit 11 and I/0 units 12. More than two central
processor units may be connected to bus 14 in a multi-processor environment.
These would be connected bo bus 14 in the manner similar to processor units
10 and lOA.
The central processor unit 10 co~prises 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 unit,s
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
~llows 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 da-ta pro-
cessing system. Central processor unit lOA generally will include an opera-
tor's console (not shown).
In Figure l, the memory unit 11 includes a memory controller 20
which connects to a plurality of memory arrays 21.
Several types of I/0 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 operation
and transfer signals between the I/0 bus adapter 22 and the I/0 devices is
disclosed in part of United States Patent 3,710,324.
The two other I/O 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 is also shown
a second secondary storage bus adapter 26 and a tape drive 27. The inter-
connection of the secondary storage bus adapters 2~ and 26 and their respective
disk drives 25 and tape drive 27 is disclosed in United States Patent
3,999,163.
The bus interconnects the various units or elements of a data pro-
cessing system. Prior to describing the transfer of information 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.
I'Information'' is intelligence used to control and provide the basis
for data processing. It includes data and address, instruction and status
information. I'Datall includes information which is the object of or the re-
sult of processing.
Transfers of information between the units in the data processing
- 5 -
,
, ' ' ' '
system shown in Figure 1 occur over the bus 14 and in~olve transfers of dis-
crete information items. Each inforn~ation item has a characteristic size on
bus 14. Other elements may process information items having other sizes.
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 bin-
ary digits (or bits). Figure 2h depicts eight contiguous bytes. The next
larger data item size is a "word", as shown in Figure 2B. A word comprises
t~o contiguous bytes. Two contiguous words constitute a ~long word~l, as
shown in Fig~e 2C.
~he bus 14 can transfer all information in paralle:L as a longword.
In the t~o contiguous longwords shown in Figure 2A, byte O is the least sig-
nificant byte position for each longword. Word O and long word O are the
least significarlt word and long word position in Figures 2B and 2C respec-
tively. ~he following discussion assumes that corresponding alignments ar
maintained ~ithin the data processing system; however, there is no require-
ment that any such alignments be maintained.
If two elements are to exchange information o~er the bus 14 at
least two "bus transactions" are necessary. During a first bus transaction,
one element requests 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 exchange.
This completes a first bus transaction. During the second bus transaction,
the information to be exchanged passes over the bus 14.
Each element that connects to the bus 14 is called a nexus. The
specific system shown in Figure 1 includes 6 nexuses. A nexus is further
defined in terms of its func-tion during an exchange of information. During
such an exchange, the nexus that transmits command and address information on
to the bus 14 is called a "master nexus" 30A in Figure 3. The unit ~hich re-
-- 6 --
sponds to that co~mand and address information is called a "slave nexus" 30B.
Thus, if a central processor unit needs to retrieve data ~rom the memory con-
troller 20, the central processor unit beeomes a master nexus and transmits a
READ (or READ LOCK) eom~and and memory address during a first bus transac-
tion. ~lemory controller 20 becomes a slave nexus ~Ihen it receives and ac-
eepts the command and address information from the bus 14.
A nexus is also defined as a transmitting or receiving nexus. A
transmitting nexus drives the signal lines while the recei~ing nexus s~mples
and examines the signal lines during eaeh bus transaction. In the foregoing
example, the central processor unit is a transmittine nexus durin~ the first
bus transaction and a receiving nexus during the second bus transaction.
Similarly, the memory controller 20 is a receiving nexus cluring t~e first bus
transaction and is a transmitting nexus during the second bus transaction.
Similar transactions occur for information exchanges between any two nexuses.
Hc~ever, the memory controllers normally function only as slave nexuses while
central processor units normally function only as master nexuses.
In aeeordanee with the speeifie embodiment of this invention de-
seribed in this applieation, the bus 14 conveys a number of signals to and
from the various units that eonneet to it over eorresponding eonduetors.
These eonductors and signal~ ean be listed in three general elasses:
1. arbitration, over arbitration bus line 31;
2. information transfer, over the data~address bus lines 32 and 33;
and
3. eontrol, over eontrol bus lines 34-38.
Lines 31-38 eomprise bus 14. ~he data address bus or information
transfer bus ineludes information lines 32 and funetion lines 33. Instrue-
tions are sent over funetion lines 33.
The eontrol eonductors and signals inelude a STATUS line 34~ a HOLD
- 7 -
line 35, a WAIT line 36, a DBBZ line 37 and a CLOCK line 38. STATUS infor-
mation indicates whether the addressed memory location has the requested in-
formation and whether the information is valid. The HOLD signal, when in-
serted on the HOLD line 35, prevents ~ny of the nexuses from getting control
of the data/address bus. ~Iold signals may be used, for example, to allow
certain memories to control the rate at which ~rite transactions occur.
The WAIT signal asserted on the WAIT line 36, is involved in inter-
rupt transactions. The DBBZ sienal, or data/address bus busy signal when
asserted on the DLBZ line 37, indicates when a nexus is requestine in~orma-
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 U~LOCK. When a nexus issues a
READ instruction, it desires to read the contents of a location in memory
~hose address is transmitted over information transfer lines 32. A READ LOCK
instruction indicates that the commanding nexus desires to read the addressed
location in memory and prevent other nexuses from gaining access to the bus
with their own READ LOCK instructions until a WRITE UNLOCK instruction is
placed on the function bus. The READ LOCK instruction does not prevent an-
other master nexus from issuing a RE4D or WRITE instruction. The RE~D LOCK
command is used primarily to prevent other processors or nexuses from gaining
access to a memory ~hich may have invalid information in the memory or to
read possibly invalid information. This is possible if the processor that
originally issued the READ LOCK instruction has access to the memory and may
be modifying information held in memory at the same time the other processor
may be attempting to read from the same memory. To prevent this, the first
processor ~ill issue a READ LOCK instruction to insure that other nexuses are
prevented from gaining access to memory.
As mentioned above, t~o bus transactions are required ~or each READ
-- 8 --
~4aE~5~
transaction and for each ~ITE transaction. Fieures 4 and 5, respectively,
exemplify, for the illustrative embodiment disclosed in this application,
the transactions for a READ and the transactions for a WR~TE. In Fi~ures 4
and 5, the positive assertive signals are shown true, or asserted, when at a
high level for purposes of simplifying the explanation. Ground assertion
(i.e., asserted or true when low) circuits and signals normally implement
this logic. However, 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. ~he 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 from a slare nexus
such as memory, the master will assert its priority signal on the arbitration
bus 31. If its priority is the highest, and if the ~OID and DBBZ lines are
all at non-asserted levels, the master will obtain control of bus 14 by as-
serting DBBZ as shown at time B on Figure 4. The master asserts DBBZ for 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 shown from time C to time
D. ~o other nexus can obtain control o~ the bus while the slave is asserting
DBBZ. When the slave is ready to transmit information to the master, the
slave shifts DBBZ to a non~asserted level, and as shoun from time D to time
E, transmits the information on the data/address bus, and simultaneously re-
turns STATUS 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
_ g _
,
D. Durin6 this cycle it can asser-t its priority sign~1 and asser~ the DB~Z
line during the cycle beginning at ~ transmit address and control and begin
a new transaction. In this manner, the transactions can overlap by one
cycle, thereby reaucing 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.
~ his overlapping may be shown in part b~ the STATUS signal in Fig-
ure 4. The left most S~ATUS sien~9, 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
circuitry required to drive those lines is reduced.
Figure 5 exemplifies a WRITE transaction. A master desiring to
WRIÆ asserts its priority signal over the arbitration line 31. When the
HOLD line and the DBBZ line are both at a non-asserted 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 in-
formation on the S~ATUS line 3l~. The final cycle in this case begins at time
D. Since the DBBZ line is lo~, 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 respectivelg master and slave circuitry
for shifting the DBBZ line bet~een asserted and non-asserted levels.
-- 10 --
~a
llhe master circuit 50 shown in Figure 6 also provides ~eans for
preventing the master nexus 30A from 6aining access to the DBBZ line 37 with
a READ LOCK instruction iP another master has previously issued a READ LOCK
instruction that has not been unlocked by a ~ITE UNLOCK instruction.
Maste~ 50 includes an instruction decoder 51 that actuates circuit
50 in response to an instruction such as R~D, WRI~E, READ L0CK and WRITE
UNLOCK. If a READ L0CK instruction is issued, instruction decoder 51 sends
one input to MAND gate 52 high and one input to an AND gate 53 high. If, as
described hereinafter, the second input to NA~D gate 52 is low, the output of
NAND gate 52 will be high, and, if the ~IOLD signal is low (unasserted) if the
master's ARBITRATI0~ line is high (indicating that this master has priority)~
and if the DBBZ line is currently low (unasserted), the output of AND gate 53
will be high. On the next clock pulse from clock 54, the set output of D
flip-flop 55 will go high thereb~ shifting DBBZ line 37 to a high (asserted)
level. Inverter 54A then sends the output of AND gate 53 low. At the next
clock pulse flip-flop 55 is reset, shifting DBBZ to a non-asserted level.
The master, therefore, asserts DBBZ for one cycle, the time between the first
two clock pulses.
Circuit 50 includes an AMD gate 56 and a D flip-flop 57 that iden-
tifies the first cycle of a m~ster'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-flop 55 asserts DBBZ, the second input to
AND gate 56 goes high, and its Olltput also goes high. On the next clock
pulse, the flip-flop 57 is set, sending its reset output low, and sending ~ND
gate 56 low, A~ 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 bein6 initiated by this particular master. When the output of
-- 11 --
~4~i3
AND gate 53 goes high on the next clock pulse the set output o~ JK flip-~lop
58 will also go high (and the reset output of flip-~lop 50 will go low). By
sending the set and reset outpu-ts of flip-flop 58 high and low, respectively,
the transaction is indicated as having been initiated by this master.
Circuit 50 also includes a second JK flip-flop 59 that identifies
when a READ LOCK instruction has been issued on the function bus and when a
WRITE UNLOCK instruction has been issued. Flip-flop 59 also identifies ~hen
the previous READ LOCK ins~ruc-tion has been issued by this particular master.
If this master issued the READ LOCK instruction, it is not prevented from
issuing further READ LOCK instruction. Flip-flop 5g 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
be high. If the READ LOCK instruction is not being issued by circuit 50, the
reset output of flip-flop 50 will be high. The output of AND gate 60 will
therefore go high and on the next clock pulse, the set output of JK flip-flop
59 will go high. With the set output high, if a READ LOCK instruction is de-
coded by instruction decoder 51, NAND gate 52 is dri~en low, and circuit 50
cannot assert DBBZ. 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 WRITE UNLOCK in-
struction is issued on the function bus during an address cycle. In~erter
61A decodes this instruction and sends the function inputs to A~D gate 61
high. During the ADDRESS CYCLE, the output of A~D gate 56 will go high which
sends the output of 61 high. This resets flip-flop 59 sending the set out-
put low. The ~lip-flop remains reset until set again by a READ LOCK instruc-
tion. With the set output low, if a READ LOCK instruction is decoded by de-
coder 51, ~AND gate 52 will be high, permitting circuit 50 to assert D~BZ.
If, on the other hand, circuit 50 issues the READ LOCK instruction,
- 12 -
the reset output of flip-flop 58 ~ill be low as will the output of A~D gate
60. Flip~flop 59 will therefore remain reset and the set output will be low.
NAND gate 52 will pass a ~EAD LOCK instruction if the output of flip-flop 59
is lo~, which can occur only when a previous READ LOCK instruction has been
issued by circuit 50, or if the previous READ LOCK instruction has been can-
celled by the ~RITE UNLOCK instruction.
Figure 7 exe~plifies an imple~entation for a sla~e circuit 70 ~or
driving the DBBZ line. ~hen the master sends address in~ormation on the
data~address bus, the address decoder 71 decodes the address and identifies
this slave nexus as being the addressed slave. The address decoder 71 is con-
nected to one input of an AND gate 72. The output of AND gate 72 is connect-
ed to the J input on JK flip-flop 73, which drives DBBZ line 37. The DBBZ
line 37 in turn is connected to AND gate 76 and the D input on D flip-~lop
77. The reset output on flip-flop 77 is connected to the other input on AND
gate 76. The output o~ Al~D gate 76 is connected to the second input on A~D
gate 72. Flip-flop 77 identifies the first (address) cycle of the bus trans-
action in a manner similar to A~D gate 56 in the master circuit 50. ADDRESS
CYCLE will be asserted for one cycle, af~er which it will shift to a non-
asserted level. When ADDRESS CYCLE is asserted, flip-flop 73 will be assert-
ed, driving DBBZ line 37. During subsequent clock cycles, ADDRESS CYCLE andAND gate 72 will be low, flip-flop 73 will remain asserted, however, until,
as explained hereina~ter, the information is ready to be sent.
An instruction decoder 78 in the slave nexus identifies when the
data 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 lo~ which in turn drives the output of
AND gate 72 low.
Flip-flops 73 and 77 are both clocked by CLOCK 54.
- 13 -
On a WRITE -transaction, with reference to Figure 6, a READ LO~K
instruction will not be issued by instruction decoder 51. The ~EAD LOCK line
will be low (non-asserted) so the nexus can WRIrrE whether or not a RF~D LOCK
instruction i8 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
driving DBBZ line 37.
The slave on a WRI~E transaction asserts ~BBZ in a manner similQr
to a READ transaction. rrhe slave drives DBBZ line 37 until it receives an
instruction indicating that the next c~cle is the last c~cle. The slave's
instruction decoder 78 then drives the DATA REA~Y H line high, resetting
flip-flop 73. STATUS information is then transmitted by the slave to the
~aster along the STATUS line.
The foregoing description i5 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 ad-
vantages of this invention. Therefore it is the ob~ect of the appended
claims to cover all such variations and modifications which come within the
true spirit and scope of this invention.
- 14 -
