Note: Descriptions are shown in the official language in which they were submitted.
``` 1~3~
:~ ,
SPECIFIC~ION FOR OUT-OF-CYCLE ~RROR CORR~:CT~ON APPARATUS
BY ROBERT E. SUELFLOW ~ND EDWARD M. DROBNY ;.
BACKGROUND OF TIIE INVENTION
1. Field of the Invention
05 ~ This invention relates generally to clata process-
ing sys-tems, and more particularly, to a method an~
apparatus for transmitting an accurate data group from
: an execution unit control store to the instruction
buffer of a central processing unit hy means of two
:: 10 three-sta-te data buss~es. .
: . 2. Description of the Prior Art ~ -
In data processing systems:wherein various sub- :`
: systems must communlcate with each other, errors, Eor
example those caused hy the presence o:E noise, some- .;.
times result in the receipt of data which is not the
same as that which was transmi-tted. Specifically, data ~;~
processing systems generally employ, as a means of
communication, signals corresponding to a high level and .
: a low level~state, often xeferred to as logic states
"1" and "0" respectively. Noise or e~uipment.fatllts
may cause receipt of a "1" or 1l0l' when in fact a l'0" or .~
"1" has been transmitted~ ` :
A data group or word consists of a plurality of ls :~
and 0s. For example, the code group 101 may correctly ~
represent the quaniity 5. If~an error is introduced . -~ .
: . during transmission, the code group may be received as :
the binary code 100, corresponding to the quantity 4. `-~
While well known par;.ty checkin~ techniques provide a
- conveni.ent means for detecting an error in.a sinqle blt,
~ 520277~
3~
such a parity check fails i.f two bits are in error. Cyclic
codes were developed and represent a marked .i.mprovement over ~:
the parity approach in that multiple errors can he detected. : `~
detailed treatment of error correction techniclues ~ay be
found ln llamminy, "Error Detecting and Error Correcting
Codes" Bell System Technical Journa~, Volume 29, 1950,
pacies 1~7 150. Irhe applical.iorl oE llammili(J's work permitted :~
the detecti.on and correct.ion oE randomly occurrin~J errors
within a single bit of received code word.
I-t i.s well known to employ error de-tect.ion and correc-
tiOIl (l~ C) apparcltll9 to check and correct data extracted
from a main memory system and hound for other s~lbsystems in
the data processing sys-tems, for example, the central .
processing uni.t. Ilowever, in the past, such apparatus was : .
not employed to verify and correct microinstructions from
the instruction unit control store to an execution buffer, .;.
the process would simply be aborted and re-execu-ted since
it was generally felt that the error was the result o a ~.
transient transmisslon problem.
SUMMARY OF THE IN~ENTION
It is an object of the present invention tG provide, .:
in a data processing system, error detection and correction
apparatus within the central processiny uni.t itself to
insure that accurate data groups are forwarded from the
execution uni-t control store to the execution buffer~
It is the further object of the invention that the
presence of the error detection and correction apparatus ~
neither delay transmission of data groups from the control .
store to the execution buffer, nor require an excessive ~`
amount of additional hardware. -
~ccording to a broad aspect of the invention there is .
provided in an execution controi store unit of a data :
processing system of the type including a system clock, an
apparatus for providing an accurate data group to the
instruction buffer of said execution control store unit, ~-~
compri.sin~ memory means coupled to said instruction buffer; :~
~~~ error correction and detection means coupled to sai.d
' .
5?02774 `:~
instruction buffer and to said memory; first means for retrieving
a data group from said memory and applying during a first clock
cycle said data group to said instruction buffer and to sa.id error
correction and detection means for determining if there is an
error in said data group during a first clock cycle, said error
correction and detection means correcting said error in said data
group; and second means for applying corrected data to said in-
struction buffer during the next clock cycle if said error is
correctable.
According to a further aspect of the invention there is
provided a method of pro~iding an accurate data group to an
instruction buffer of a data processing system execution control
store unit, comprising: retrieving data from a memory in said
execution control store unit; applying said data group to said
instruction buffer during a first system clock cycle; applying
said data to error detecting and correction circuitry during said
first system clock cycle; determining if there is an error in
said data group and if said error is correctable during said first
system clock cycle; correcting said error in said data group by
said error detecting and correcting circuitry; and applying
corrected data to said instruction buffer during the next system
clock cycle if said error is correctable.
The above and other objects of the present invention will
be more clearly understood from the following detailed descriptions
taken in conjunction with the accompanying drawings, in which:
Figure 1 is a block diagram of a data processing system; ;.
Figure 2 is a functional diagram of a portion of the
central processing unit;
, .. . - . . - : : . : . : .. - : :.: : ... , .. .: : :
:. ~ . : :. :: : . ; .::~
- ~ , : :: -: : : :
3~
Figure 3 ls a block diagram of an arrangement employing
in-cycle EDAC according to the prior art;
Figure 4 is a block diagram of an arrangement employing
out-of-cycle EDAC according to the present invention.
Figure 5 is a functional block diagram of an inventive
part of the execution unit; and
Figures 6 and 7 are more detailed di.agrams of the
arrangement shown in Figuxe 3.
Figure 1 is a block diagram of an improved data process~
ing system 10 into which the present invention is
:
-3a-
3~
incorporated. Data processing system 10 has two SIU's,
12a and 12b. Each SIU has fifteen ports identified by
letters A thru K plus four additional memory ports; local
memory port 0, (LMO), local memor~ port l, (LMl), and two
05 main memory ports in which the main memory control function
or controllers (MMC'n and MMC1) are located, To certain
pairs of ports ~uch as G and 1l and E and F, a pair of
locked I/O processors ~IOP) 14a, 14b, 14c, and 14d can be
attached. Up to four central processing units (CPU's~ 16a,
16b, 16c and 16d two to each SIIJ, can be attached to any
two of the ports A, B, C, Dj E, F, G, or H. Local memory
(MMo) 22a, 22c and (MMl) 22b, 22d can be connected to the
main memory controller ~MMo) 24a, 24c and (MMl) 24b, 24d
of the SIU's 12a and 12b. Each of the main memories 20a
1~ and ~Ob also has two ports which are cross-connected to
permit commullications to occur between devices and memories
attached to the respective SIU's 12.
Eac}l of the main memory controllers M~IC024a, 24c, MMCl
24b, 24d of SIUIs 12a, 12b in addition to writing data into
a main memory M~lo 22a, 22c, or ~Ml 22b, 22d and to reading
data out of MMo or MMl also has certain communication
control functions.
Communications betw~en SIU7s can be from a main memory
controller such as MMCo ~4~ of SIU 12a to the main memory
MMo22c of SIU 12b. MMo 22c communicates or transmits the
~essage to its main memory controller MMCo 24c of SIU 12b.
M~Co24c in turn directs the communication to the designated
port of SIU 12b to which is attached a processor such as
IOP 14c or CPU 16c, for example, of SIU 12b, the processor
to which the communication is directed. ` ~1
A CPU such as 16a in the course of performing an sp-
plication program wiil reach a point where an operation `~
is required either to bring in from a periph;eral~device `;
data stored in the peripheral device or to read out from ,
memory information to be transferred to a pe~;pheral device.
When the need for an I/O operation occurs, or more broadly,
whenever one processor needs to communicate with another
5202774
processor includiny itself, the operating system of the data processing
system 10 will cause an instruction to be transmitted to a CPU such as 16a.
The contents of the operational field of the instruction word is such as
to indicate or designate a specific type of communication is to be
05 performed or executed. The operating system will also provide 16a
with a data word, a designed field of which will identify the processor
to which the communication is to be sent.
Figure 2 is a block diagram of the llardware elements of a CPU 16
which will be described below only to the extent necessary to set the
proper stage for a description of the present invention.
Referring to Figure 2, instructions are received over an instruction
buffer ~IB 26 from a main memory controller such as MMCo 24a and are
transmitted through ZIB switch 28 to RBIR 30 for storage therein. lhe
control unit control store word which is stored in control unit control
store CCS32 comprises 32 bits. A 13 bitsfield consisting of bit
positions 0 thru 12 is the address oF the starting location for the
microprogram specified by the operation code of the instruction word in
instruction register RBIR 30 or the address of the initial microinstruc-
tion of the microprogram. When the operation code from an instruction
is applied ~o CCS 32 ~rom RBIR 30, the control unit control word stored
at the address corresponding to the OP code, the contents of bit position
0 thru 12 will be applied to the execution unit control store (ECS) 34
thru switch CCS-ADP 36. The receipt of the address of the microinstruction
by ECS 34 causes the microinstructions stored at that address to be
transferred to the execution buffer 38 where selected fields of the
microinstruction are decoded by decoder 40 to provide the necessary
control signals or information to the various subsystems, or components,
of a CPU such as CPU 16a.
-~,
5202774
.
..
1~3~
To avoid pro~idi.ng unn~ sary detall~, the ¢lock ~nd ~.
the conductors tllat apply the clock signals to the various
components of the CPU 16a are not illustrated .i.n F;.gure 2.
When the first microinstruction has been loaded into
oS the execution buffer 38, and during the next clock period,
I:he nl:i.croills~rllct;on w:i.l.l l~c c~co(le(l .i.n deSco(l(?r ~0 to
prov.i~e the necessary information and c~ntrol s:i.gnals to ~;
cause a scratchpad memory (not shown) to be addressed and
a portion of its contents to be transferrecl, store.d and
operated UpO~
The next or second microinstruction which is produced
as a result o~ thè address of the first microlnstruction ~:
which is stored in microinstructi.on register llIC 42 being
incremented by one by adder 44 and applied thru switch
UIC+l, 46 will cause the second microinstructj.on to be
transferred to execution buffer 38.
Figure 3 illustrates EDAC function orientati.on in a .~
data processing system ~eE~R~ to~the prior art. An out-- :
- put from memory 61 is applied to data swltch 65 and -to EDAC
circuitry 63.; Data switch 65 then selects whe-ther data ~:
~rom:memory 61 or corrected data from EDAC 63 will be for- ~`
warded to the CPU. ` ::
.
In the arrangement shown in Figure 4, data from memory
67 is applied to the CPU and to EDAC 69 simultaneously. If
an error is detected and is not correctable, the operation `~
in progress is aborted~ If no error is detected, utiliza~ ~.
tion of the data proceeds uninterrupted. This arrangement ~.:
. . .
reduces control store access time by about 40% over that :~
of M-cycle EDAC (Figure 3). This results i.n a 60% increase
in system clock rate. Out-of-cycle EDAC permits simultaneous :~
activities; i.e. the next memory request may be processed
while the previous request is undergoing EDAC scrutiny. .
: Additional speed enhancernent is accomplished by a 3-sta-te
bus implementation described below. ~ ~:
Figure S is a functional block diagram of a portion of -~
the execution control store (34 in Figure 2) which is the
subject of the:present .invention. Two separate but inter-
related -three state data busses are used The flrst
520277
~3~Z~
~`
referred to as the memory data bus, is connected between
the output of memory 52~ the input of three state device 54,
the output of memor~ 52 and the input of execution ~uEfer 38
(Figure 2). The second hus referred to as the backpanel
05 bus, is connected between the output of three state devic'es
56, 62 and 54, ancl between the inputs of data register 60,
AND function 66 ancl three state device 50. It should be ~`
understood that while each of the busses are shown as a ;'
single line, each is composed of a plurality of lines for
handling the parallel transfer of a plurality of data bits. '~
The error detection and correction (EDAC) employed is
out of cycle detection and correction. To accomplish this,
data from memory 52 to'execution buffer 38 is assumed
correct for any current cycle and is strobed into the ~''
execution buffer by the system clock. ~uring the following
cycle, this same data is check'ed for errors in EDAC cir-
cuitry 58. '~f a correctable error is detected, a signal is
sent to another portion of the CPU and corrected data is
placed on the bus to be restrobed into the execution buffer
on the following clock. Any uncorrectable errors result in
a system abort. ~'
Two critical timing paths are involved in this scheme.
t is first necessary to get data from memory 52 to the
execution buffer before the system clock occurs. The second -
involves making an error signal and the corrected data avail-
able to the execution buffer before the following clock.
The output of memory 52 is coupled to execution buffer
38. The same output is likewise coupled to the input of a
three state buffer 54, for example, of the type manufactured
3Q by Texas Instruments and bearing part number 74S240, for
transmission of the data to EDAC circuitry 58 via data '
register 60. During this time, three state buffer 54 is
enabled by a read signal which originates in another portion
of the CPU. Simultaneously, three state buffers 50, 56 and
62 are disabled and pres~ent a high impedence to their re-
spective busses. That i5, three state buffer 62 is disabled
.~ by the absence-of write signal on its input. Likewise, the
-
5~ 77~1
.'
abs~nce of a write signal at a second input of AND function
66 prevents data bound for the EDAC circuitry from re-enter-
ing memory 52 via AND function 66. Similarly, three state
bufers 50 and 56 are disabled by the absence of a send -
05 corr&ct data signal whicll originates in EDAC circuitry 58.
Thus, data may be transmitted from three state huffer 54
t:o the ~ C circuitry withoul: interference.
I)urincJ a correction cycle, the s~me two bi-directlonal
busses transmit data from three state buffer 56 to the
execution buffer via three state buffer 50. Duriny this
time, buffer 62 and ~ND function 66 are disab]ed ~y the
absence of the write signal and three sta-te buffer 54 and
memory 52 are disabled by the absence of a read signal. ;~
Buffers 50 and 56 are enabled by a corrected data signal and
transmit data from the EDAC circuitry 58 to the execution
buffer. It should be noted that the memory data bus which
connects buffers 50, 54 and memory 52 to the execution unit
eliminates the need for a conventional data switch which
would represent an extra staye of delay in the data path to
the remainder of the CPU for either memory data or corrected
data.
During wrlte cycles, data frm buffer 64 is transmitted
to memory 52 via buffer 62 and AND function 66. During this -;
operation, three state buffers 50, 54 and 56 are disabled
as described above.
The arrangement shown in Figure 5 is shown in more
detail in Figures 6 and 7. While the arrangement in Figures
6 and 7 is shown as being capable of handling 8 bits of data,
it should be clear, that this is given by way o example
only, and that the arrangement can be expanded to include a
much larger number of data bits.
The data-in buffers 64 (Figure 5) are shown as AND
gates 7C-77. Three state buffers 62 (Figure 5) is shown as
plurality of three state gages 80-87 in Figure 6. One
three state gate is required for each data line. As des-
cr,ibed earlier, the three state device, when enabled, will ~;
pass the data applied to its input Oll to its destination.
~~ That is, when the write signal which i.5 shown coupled to
~,. .
~ 5202774
-, - , ~ .. ~ - , ., . : . -,:, ,. . ; , . ,. , ,, . . ., ;:, .
- ~
g ,
each of the three state devices 80-87 is on, data applied
to three state devices 80-87 via AND gates 70-77 will pass
on thru the three state devices to the clata bus li.nes B0-B7.
When the write signal is disabled, the three state devices
80-87 appear as a high impedence node.
nurin~.a write cycle, data to be wri.tten i.nto the :~
memory is applied to one input each oF AND gates 70-77.
This data passes thru AND gates 70-77 when an enable signal
coupled to a second input of each of the AND gates 70-77 is .
activated. Referring now to Figure 7, what was shown as a
single AND function in Figure 5 is shown as a plurality of
AND gates 90-97 each oE which have one input coupled to the ..
data bus lin.es B0-B7 and a second input coupled to a write ::
enable signal. When the write enable signal is activated,
the data on data bus lines so-s7 passes thru ~ND gates 90-97 .
to memory 52 where it is stored therein by write control 51. :
During a read cycle, the write signal is disabled pre-
ven-ting data from passing through three s-tate buffers 80-87 .;
and AND gates 90-97. When memory 52 has a.read control - ~
signal 53 and an address applied theréto, the memory~:outputs
the data stored in that addr~ess.~ This data travels two paths~
The first is to the remainder of the CPU as is shown by lines .l:
100-107i Sim~ltaneously, the:data from memroy 52 is applied
to the three state devices 110-117. Each of three state
devices 110-117 also has applied to an input a read enable .:
signaI ~1hich, when activated, allows data ~o pass through ~
the three state devices 110-117 appears a high.impedence ~-
node.
Assuming the read signal is enabled and the write signal
disabled, data~from memory.52 passes through three state
devices 110-117 and is applied to the inputs o-f data registers .
60 (Figure 6~ over the data bus lines B0-B7. The data in .
data register 60 is applied to the EDAC circui:try 58 as des-
crobed above where it is determined if there is an.error in .-
the data and whether or not the error is correctable. Two :~
signals are sent from the EDAC circuitry to another portion
of the CPU. These signals are shown as an error signal and
.:
, ~
. . ~
520277~
36~
an error correctable signal which indicates that while there is
an error, the error is correctable.
With respect to a correctable error, the (incorrect)
data in the execution buffer is held until it is overwritten by
corrected data, and then transferred out of the execution bu~fer.
If there is a non-correctable error, the CPU receives only the
error signal indicating that the data in the execution buffer is
in error and cannot be used. The response of the CPU is not to
transfer the data out of the execution buffer, while performing ~ -
various housekeeping functions that cause the program in progress
to abort. ;
If the error is correctable, the same correct data
signal is applied to three state devices 120~127. The corrected
data is likewise applied to three state devices 120-127 and passes
therethru to the inputs of three state devices 130-137 over bus
lines B0-B7. During this period of time, the write signal is
disabled thus preventing the data from passing thru AND gates
90-97 back to memory 52.
The same correct data signal, described previously, is
applied to three state devices 130-137 to enable pas~age of the
data on bus lines B0-B7 to the CPU via lines 100-107. During this
period of timel the read signal is disabled to prevent the correct-
ed data from passing thru three state devices 110-117.
Thus, the above described arrangement permits three
electrical functions to be performed on one line referred to as
the backpanel bus~ These functions are transmitting memory data
to the EDAC circuitry, transmitting corrected data from the EDAC
circuitry to the data output circuits and transmitting input data
--10--
---` $%~;Z
to the memory.
The memory data bus permits transmission of data to
both the CPU and the EDAC circuitry. In addition, the memory
data bus provides for transmission of corrected data from the
EDAC circuitry to the CPU. Both busses minimize the need for
any additional gates or switches and thus presents the fastest
possible data paths where critical timing is involved.
s~
.. : :~ . : -. . . - :
