Note: Descriptions are shown in the official language in which they were submitted.
1~7s5~l
This invention relates to improvements in memory access management in
the operation of data processing machines that employ a cache.
The data processing machine of the present invention has a central
processor, a main memory controlled by a memory controller, and a number of
peripheral processors (running such equipment as terminals, printers, telecom-
munications, and the like). The machine further provides a cache memory. A
cache is a high speed memory local to the central processing unit and containing
a time-varying subset of the contents of main memory.
A cache can greatly decrease the average memory access time for the
central processor memory operations, since a very high proportion of memory
reads can be satisfied out of the high speed cache. For a minority of memory
read attempts, it is necessary to halt the operation of the central processor in
order to bring in the requested data from main memory. In the machine described
herein, the cache is read directly by the central processor, and is written by
cache write circuitry in response to either a cache miss or a central processor
main memory write operation. The peripheral processors read and write main
memory through the memory controller, but do not read or write the cache, which
is reserved for the central processor operations.
Three problems, among others, arise in running such a cache, all of
which decrease the operating speed of the data processing machine.
First, although the peripheral processors do not write the cache, when
they write to a location in main memory, it is necessary to check the cache to
find out whether the contents of that main memory location have been brought in-
to the cache, and if so, it is necessary to invalidate the cache entry ~by set-
ting a valid/invalid bit to a state indicating "invalid"), since the entry no
longer corresponds exactly to the contents of main memory. This means that at
a particular time there may be contention between the operation of attempting
~7~s~i
to read the cache, and the operation of attempting to check the cache contents
after a peripheral processor main memory write operation ~tag check).
Second, since the cache cannot be written and read simultaneously,
there may at any particular time be contention between the central processor,
attempting to read the cache, and the cache write logic, attempting to write to
the cache in response to a previous cache miss (cache update). There may also
be contention if the cache write logic is attempting to write an invalid bit
after a previous tag check has demonstrated a tag match condition.
Finally, at any particular time there may be contention if the central
processor tries to read the cache while the memory controller is writing to the
cache to update it after a previous central processor write to main memory.
In prior art machines, the cache has been operated in such a way that
(1) overhead time must be spent in settling the contentions, particularly in the
first case; (2) on a cache update after a previous cache miss, it has been neces-
sary to keep the central processor stopped during a cache cycle dedicated to up-
dating the cache contents; and (3) it has been necessary to stop the central
processor during memory cycles dedicated to updating the cache contents after
a central processor write. All of these occurrences cause delays in memory
access and consequent degradation in the operation of the central processor.
The present invention avoids all these disadvantages.
A cache generally has an operating cycle of the same length as the
memory operation microinstruction cycle of the central processor. In the data
processing machine of the invention, the cache operating cycle is divided into
two subcycles dedicated to mutually exclusive operations. The first subcycle is
dedicated to receiving a central processor memory read request, with its address.
The second subcycle is dedicated to every other kind of cache operation. These
are in particular either (a) receiving an address from a peripheral processor
~7~5B~
for checking the cache contents after a peripheral processor
write to main memory, or (b) writing anything to the cache, inclu-
ding an invalid bit after a cache check match condition, or data
after either a cache miss or a central processor write to main
memory. By this means, contention is eliminated, so that over
head time need not be spent in resolving the contentions, and
write operations become "transparent" to the central processor
reading of the cache. From the viewpoint of the central proces-
sor, the cache is always available for read operations. The cen-
tral processor can continue uninterruptedly to read the cache on
successive central processor microinstruction cycles, regardless
of the fact that the cache contents are being "simultaneously"
checked, invalidated or updated after central processor writes.
After a cache miss, although the central processor must be stopped
to permit updating, it can resume operations a cycle earlier than
is possible without the divided cache cycle.
Further, the implementation of a memory management struc-
ture according to the invention is particularly economical of cir-
cuitry, reducing both cost and space requirements.
Briefly stated, according to the invention, there is
provided in a data processing machine including main memory means
for storing data, including instructions for directing operations
of the machine, and processor means for processing data, cache
memory means comprising: cache means including cache storing means
for storing a copy of a portion of the data stored in the main
memory means, cache control means for receiving read and write
requests from the processor means and for providing addresses
--3--
5i~31
corresponding to certain requests to a memory controller means,
and cache transfer means responsive to operation of the cache
control means for conducting data from the memory controller
means to the cache storing means and fGr conducting data from the
cache storing means to the processor means, the memory controller
means including controller control means responsive to the addres-
ses for providing outputs for controlling operation of the con-
troller means and the cache and main memory means, and controller
transfer means for conducting read data from the main memory means
to the cache storing means and for conducting write data directly
from the processor means to the main memory means, the controller
control means including timing means defining a cache memory
means operating cycle comprising a first subcycle and a second
subcycle, and the cache and controller control means responsive
to the timing means for accepting only processor read reque~ts
during first subcycles and for accepting and resolving conflicts
between all other cache and memory operation requests during sec-
ond subcycles.
As indicated in the above statement of invention, the
return path from processor to main memory is provided directly
from the processor to the memory controller means and does not
pass through the cache means. The cache means is thereby used
only for the transfer of data and instructions from main memory to
the processor and all other transfers are performed through the
memory controller means. The cache memory means of the present
invention is thereby directed to maximizing the rate of operation
of the processor by dedicating the cache means to the sole purpose
--4--
~ s
1175S81
and function of providing instructions and data to the processor.
As also indicated in the above statement of invention,
the memory controller means directs the cache means to operate on
a split cycle comprised of two subcycles. Moreover, the first
subcycle is dedicated to accepting only processor requests for
reads of data and instructions from the cache means to the pro-
cessor. All other main memory and cache related requests and
operations are accepted only during the second subcycle and the
order and priority in which they are performed is determined
through a conflict resolution process. The split cycle operation
of the cache of the present invention thereby operates to dedicate
the first subcycle solely and exclusively to accepting requests
for the transfer of data and instructions from the cache to the
processor; all other memory and cache operations are forced into
contention, that is, conflict, for main memory and cache access.
The cache memory means of the invention is thereby further direc-
ted to maximizing the rate of operation of the processor by ensur-
ing that the processor may receive data and instructions from the
cache every cache cycle, that is, by ensuring the continuous flow
of data and instructions to the processor.
As will be described in greater detail below, the cache
means is the central node through which all main memory and cache
operation requests are passed to determine the natures of the
requested operations. All data/instruction transfers in the sys-
tem, however, except reads of data and instructions to the pro-
cessor and including transfers from processor to main memory or
between peripheral devices and main memory, pass through only the
--5--
1~7~S~^l
memory controller means. Again, the cache memory means of the
present invention is directed to maximizing the rate of operation
of the processor by dedicating the cache means to the sole pur-
pose and function of providing instructions and data to the pro-
cessor.
The invention will now be described in greater detail with
reference to the accompanying drawings in which:
Figure 1 is a simplified diagrammatic view of a data pro-
cessing system having a data processing machine according to the
invention;
Figure 2 shows the data and address paths through the
data processing machine;
Figure 3 shows certain features of the central processor
of the data processing machine;
Figures 4 through 9 illustrate the formats of various
data and addresses pertinent to the invention;
Figure 10, appearing on the same drawing sheet as Figure
3, shows pertinent features of the control store;
Figure 11 shows the master clock;
--6--
117~8~
Figure 12 shows fundamental system timing signals generated by the
master clock of Figure 11;
Figure 13 shows a portion of the cache memory related to addressing
functions;
Figure 14 shows a portion of the cache related to data storage;
Figure 15 shows certain portions of the cache related to memory
control and other control functions;
Figure 16 shows portions of the circuitry r~ated to m~ory access
priority;
Figure 17 shows cache circuitry generating a control signal for
peripheral processor memory operations;
Figure 18 shows cache circuitry related to the use of certain con-
trol store signals by the cache;
Figure 19 shows the main memory;
Figure 20 shows the cache write logic, and
Figures 21, 22 and 23 are timing charts showing portions of the
operation of the data processing machine of the invention.
Referring now to the drawings, and particularly to Figure 1, the
entire system is seen in simplified form. The data processing machine 10 pro-
vides a central processor 12, a control store 14, and a master clock 20. There
is further provided a main memory 16, access to which is controlled by a memory
controller 18. Various peripheral devices (terminals, printers, disks, tapes,
telecommunications devices, and the like) are attached to data processing
machine 10 and with it comprise the system.
~ach peripheral device contains a processor, called a peripheral
processor. Several peripheral processors are connected to one of the bus
adapters 22, which in turn is connected to memory controller 18. There may be
-- 7 --
~7~S8~
several bus adapters. The purpose of bus adapter 22 is to buffer between the
64-bit data lines within the data processing machine and the 16-bit data lines
which connect the peripheral devices to machine 10. Memory controller 18 pro-
vides access to main memory 16 for the central processor and the peripheral
processors; it may also transmit instructions from central processor 12 to the
peripheral processors, in a manner not pertinent to the present invention.
Central processor 12 is connected to a high speed local memory or
cache 24, which contains a time-varying subset of the data stored in main memory.
Cache 24 is also connected to memory con~roller 18. The particular cache in
the preferred embodiment is direct-mapped, and contains 32K bytes. It employs
a write-through strategy; that is, the cache is updated whenever the central
processor write to main memory.
Cache 24, main memory 16, and memory controller 18 together comprise
the physical memory of the data processing machine.
The data and address paths through the system are shown more par-
ticularly in Figure 2. Central processor 12 has a 24-bit address bus 26, carry-
ing the address lines designated by the mnemonic "MA (for Memory Address) 0-23"
to cache 24. Central processor 12 has a 32-bit data-in bus 28, carrying the
data lines designated by the mnemonic "MM (for Main Memory) 0-31", and a 32-bit
data-out bus 30, carrying the data lines designated by the mnemonic "WD (for
Write Data) 0-31".
Cache 24 receives the address lines MA 0-23 on bus 26 from central
processor 12, and in addition is connected to bus 32, which carries address
lines designated by the mnemonic "BMA (for Bus Adapter Memory Address) 0-23"
from bus adapter 22. This address information is used to keep up to date the
information in the cache when corresponding information in main memory is changed
by one of the peripheral processors, as will be described in more detail in
-- 8 --
~1755~
what follows.
Cache 24 is connected to output address bus 34, carrying the address
lines designated by the mnemonic "CMA (for Cache Memory Address) 0-23' to memory
controller 18. Further, cache 24 is connected to bus 36, carrying the address
lines designated by the mnemonic "BMAR 3-20" (for Buffered Memory Register) to
main memory 16.
Cache 24 has one data-in bus and one data-out bus. The data-in
bus 38 carries the data lines from memory controller 18 designated by the
mnemonic "CAWD (for Cache Write Data) 0-63". Data bus 38 is used by memory
controller 18 to write data to the cache after a cache miss, or in response to
a central processor main memory write, as will be described in more detail in
what follows. Bus 38 is also used, in a manner not pertinent herein, to trans-
mit data to bus adapter 22. The data-out bus 40 carries the data lines from
cache 24 designated by the mnemonics MM 0-31, for input to central processor 12
on bus 28. Data bus 40 provides data to central processor 12 after a cache hit
in response to a central processor read request, as will be described in more
detail in what follows.
Main memory 16 receives the address lines BMAR 3-20 from cache 24,
as previously described, on bus 36, together with memory module select signals,
not shown in the Figure and not pertinent to the present invention. Main memory
16 has a 64-bit data-in bus 42 connected to memory controller 18, carrying the
data lines designated by the mnemonic "MMWD ~for Main Memory Write Data) 0-63".
All data written to main memory 16 is input on bus 42. Main memory 16 has a
64-bit data-out bus 44 connected to memory controller 18, carrying the data
lines designated by the mnemonic "MMRD (for Main Memory Read Data) 0-63". All
data read from main memory 16 is read out on bus 44.
Bus adapter 22 outputs address bits to cache 24 over bus 32, pre-
_ g _
11755~3~
viously described, in response to peripheral processor memory access requests,
in a manner not pertinent to the present invention. Bus adapter 22 has a 64-
bit data-out bus 46 connected to memory controller 18, carrying the data lines
designated by the mnemonics "BARD (for Bus Adapter Read Data) 0-63", and a 64-
bit data-in bus 48 connected through buffer 50 bo bus 38, carrying the data
lines designated by the mnemonic "BAWD (for Bus Adapter Write Data) 0-63". Note
that "Bus Adapter Read Data" refers to data read from the peripheral processor
to main memory 16, while "Bus Adapter Write Data" refers to data read from
main memory 16 and written to a peripheral processor.
In addition, bus adapter 22 outputs certain control signals to cache
24. These are MRBA (Bus Adapter Memory Request Signal), and BAC 0-2 (Bus
Adapter Control Signals). The BAC 0-2 signals are latched within the cache for
convenience of use; in their latched form they are designated BBAC 0-2.
The memory controller 18, as has been described, receives data over
bus 44 from main memory 16, over bus 46 from bus adapter 22, or over bus 30 from
central processor 12. Memory controller 18 receives address data on bus 34
from cache 24. Memory controller 18 outputs data on bus 38 to cache 24 and to
data latch 50 for output to bus adapter 22. Memory controller 18 further outputs
data to central processor 12 (via latch 54) on bus 52, carrying the data lines
designated by the mnemonic "DIRD (for Diagnostic or Read Data) 0-31". On the
occasion of a main memory read following a cache miss, as will be explained more
fully in what follows, a Miss Extended signal, derived in response to the cache
miss condition in a manner to be described in what follows, allows the data
from bus 52 to pass through latch 54 to bus 28 and thence to the central
processor.
Referring to Figure 3, only two elements within central processor 12
are pertinent to the present invention. These are memory data register 56, which
- 10 -
1~755~1
receives data over the lines carried by bus 28 ~MM 0-31), and memory address
register 58, which is loaded (in a manner not pertinent to the present invention)
with the address to be output over bus 26 ~MA 0-23) to the cache.
If the central processor is not stopped ~that is, when the signal
STCP Inverse is high: the derivation of this signal will be described in what
follows), the address signals from memory address register 58 are transferred
to cache 24 at time L0 (the timing signals including L0 will be described in
connection with Figure 12).
Referring now to Figures 4 - 9, various formats of data and addresses
are shown that are pertinent to the operation of the data processing machine.
Figure 4 illustrates a byte of data, defined as comprising 8 bits.
Figure 5 illustrates one word of data, defined as comprising four bytes, or
thirty-two bits. Figure 6 illustrates a doubleword, defined as comprising one
even word and one odd word, each of thirty-two bits. Data is stored in main
memory in doubleword units.
Referring now to Figure 7, the 24-bit physical address is shown as
it is seen by main memory; the address comprises a 12-bit page frame number
(expandable by two if the memory is enlarged), and an ll-bit offset, locating
the byte within the page.
Figure 8 shows the same 24-bit physical address as it is inter-
preted by the cache; the address comprises a 9-bit tag and a 12-bit index. The
low-order two bits are ignored, since they are used to select a byte within a
word, whereas the cache always transmits a word to the central processor, which
must then select the particular byte that is wanted. The third bit from the
right selects the even or odd word of a doubleword pair. Figure 9 shows the
format of data as stored in the cache. The even and odd words of a doubleword
pair are stored, together with the 9-bit tag for each. This entire 72-bit unit
- 11 -
1~75~
is addressed by the 12-bit index of the physical address.
The employment of an index and tag to address a direct-mapped cache
is well understood in the art of designing data processing machines. The
general aspects of managing cache memories are described, for example, in
Computer Engineering, by Bell, Mudge and McNamara (Digital Press, 1978).
Referring now to Figure 10, control store 14 contains control sig-
nals, which are accessed in groups of forty-eight signals output on forty-eight
parallel lines. The signal on each line may be either High (1) or Low (0), and
is applied directly to the hardware circuitry of the central processor 12 to
control the operation thereof.
Of the forty-eight signals on the lines, comprising a microinstruc-
tion, only certain ones are pertinent to the present invention. These are
signals 0-6 (called the "micro opcode"), which are decoded as a group to provide
one of a number of signals indicating the operation to be performed (such as
add, move, compare, shift) and signals 22 through 29, which are decoded as a
group to provide one of a number of signals indicating a memory operation (read
or write, with details of memory address register selection, memory data
register selection, and other matters not pertinent to the present invention).
These signals are indicated in Figure 2 as "memory control signals". Particular
ones of the control signals accessed by the central processor are connected
directly from the central processor to the cache and the memory controller, as
will be discussed in more detail in what follows. The accessing and decoding of
such groups of control signals (microinstructions) during operation of a data
processing machine is well known in the art, and will not be described herein.
Referring now to Figure 11, per~inent portions of the system master
clock 20 are shown. The master clock for the data processing machine is driven
by a 50 Mhz crystal, whose output is input to timing signal generation circuitry
- 12 -
~g7`~
60, which in a manner well known in the art generates appropriate timing
signals for the system. The basic timing signal (CLOCK) has a period of 40
nanoseconds and a 20 nanosecond pulse width. The signals TA, TO, Tl, T2; LA,
LO Ll, L2; CLOCK; and inverse CLOCK are represented in the timing chart of
Figure 12. These pulses are input to central processor 12.
Signals LA, LO, Ll, L2 are free-running, while TA, TO, Tl, T2 are
dependent on operating conditions in the central processor and elsewhere. Fur-
ther L and T pulses may be generated, under conditions to be described, but
are not shown in Figure 11 and are not pertinent to the present invention.
Two gating signals GTl and GT2, are generated in a manner to be des-
cribed more particularly in what follows. Signal GTl gates (enables or inhibits)
the central processor timing signals TA and TO; signal GT2 gates the timing
signals Tl and T2. The central processor cycle is defined as beginning with a
TA pulse. Thus the operation of the central processor can be stopped after TO
or after T2. Signal GT2 is normally a slave to signal GTl, but on the occurrence
of a "Miss" signal, in a manner to be described in what follows, GT2 is inhibit-
ed, so that pulses Tl and T2 will not occur, even though pulses TA and TO have
occurred.
The length of the microinstruction cycle of the central processor
varies according to the nature of the microinstruction. The central processor
cycle (of any length) is defined as beginning at TA. Most microinstructions,
including those which involve memory operations and are pertinent to the present
invention, require 160 nonoseconds for execution. For these microinstructions,
the pulses TA, TO, Tl and T2 comprise the cycle, as seen in Figure 12. Other
instructions may require longer than 160 nonoseconds for execution; for such in-
structions, further T pulses must be generated (T5 through T8, not shown). To
determine the number of T pulses to be generated, the control signals 0-6 (the
- 13 -
~ ~55~i
"micro opcode") of the current microinstruction controlling central processor
12 are input from central processor 12 to a decoder and counter 62 together with
the CLOCK signal from circuitry 60; according to the nature of the operation as
determined by the decoder, the counter is set, and at the appropriate time the
signal "COB" ~end of cycle) is generated to mark the end of the instruction
cycle. This signal resets circuitry 60 and causes the next cycle to begin with
a TA pulse.
The CLOCK signal is input directly to cache 24 and to memory control-
ler 18, where similar timing circuitry is provided to generate synchronous L
and T pulses. However, unless the gating signals GTl and GT2 are specifically
shown, the T pulses within the cache and memory controller do not stop when the
central processor stops.
The cache cycle is the same length as the central processor read or
write cycle, that is, 160 nanoseconds. However, it is defined as beginning
with the Ll pulse and comprising the pulses Ll, L2, LA, L0, which, as is seen
from Figure 12, means that the cache cycle is offset by 60 nanoseconds from the
central processor cycle. The memory controller cycle is offset by 40 nano-
seconds from the central processor cycle, and comprises the pulses TO, Tl, T2,
TA .
Purther, some timing pulses from the central processor are input
directly to cache 24 to cause events synchronized with particular central pro-
cessor events. Such cache events cannot occur when the central processor is
stopped, although the cache is not stopped.
Referring to Figures 13, 14, 15, 17, 18 and 20, cache 24 generally
comprises an addressing portion (Figure 13), a data storage and tag comparison
circuitry portion (Figure 14), and various control signal decoding circuitry
~Figures 15, 17, 18 and 20). The circuitry of Figure 16, and portions of the
- 14 -
~175~
circuitry of Figure 15, are physically located within the cache but are concep-
tually parts of the memory controller, since their functions are concerned
with the management of main memory.
Referring first to Figure 18, the central processor address (not
shown in this Figure) reaches cache 24 together with the control signals CM 22-
29 of the 48-signal group controlling current central processor operations.
As has been described, control signals 22-29 are memory access control signals
which control the nature of the memory operation to be performed at the address
specified by the central processor. For convenience of use in cache 24, cer-
tain of these signals are delayed by being latched or buffered, and the delayed
signals are referred to as "CCM", "BCM", "LCM" or "MCM" according to their
delays, as shown in the Figure.
Referring now to Figure 16, memory controller 18 provides main
memory-access priority determining circuitry 140. This circuitry is designed to
give priority of main memory access to any bus adapter request (on behalf of a
peripheral processor). Only when no bus adapter memory request is pending does
central processor 12 gain access to main memory, either to write or to read
after a cache miss. The input signal LC (Last Cycle) comes from the memory
controller timing circuitry of Figure 15, to be described, and is generated at
the end of a memory access operation. On the completion of any current memory
operation, if no bus adapter memory request is pending, by default BA goes low,
and the waiting central processor address is transmitted to main memory 16.
Thus after a cache miss there may be a delay of some cycles until main memory
is available to the central processor. During this time the central processor
remains stopped, as will be described.
This allocation of priority for main memory access between the cen-
tral processor and the bus adapter, conditioned on the presence or absence of
- 15 -
~ ~75581
bus adapter memory requests, must be clearly distinguished from the division
of the cache cycle between the central processor memory reads and other opera-
tions, to be described in more detail in what follows. The circuitry for the
division of the cache cycle is free-running and operates as described whether
or not any request from either the central processor or a bus adapter is pending.
Referring to Figure 17, a "BA Enable" signal is generated by a
flip flop in enabling circuit 142 at time TA in response to any bus adapter
memory request (MRBA) provided the memory control circuitry is ready (R/B). The
BA Enable signal is applied to the circuitry of Figure 13 to input the address
of the BA memory operation, for purposes of a cache check or invalidate pro-
cedure, to be described.
The timing for main memory 16 is largely generated by the circuitry
of Figure 15, the major part of which is functionally part of memory controller
18. Methods of timing and operating a main memory for a data processing machine
of the kind described herein are in general well understood in the art and
form no part of the present invention. Therefore, the generation of these
timing signals will not be described in detail; rather, those portions relevant
to the operation of the invention will be indicated.
Referring now to Figure 15, the control signals CCM 22-29 (from
Figure 18) are decoded in decoding circuitry 138 to determine whether the cen-
tral processor memory operation is a write or a read. If the operation is a
read, the control signals when decoded result in the generation of a "Read"
signal, indicating that the central processor memory operation is a read, to be
serviced in the cache. This signal is required within cache 24 to permit the
generation of a cache miss signal, as will be explained.
If the central processor memory operation is a write (to main mem-
ory), the control signals CCM 22-29 when decoded provide the write signals
117~
WRITE 8 (i.e. bits), WRITE 32, and WRITE 64, which specify the operations of
writing a byte, a word or a doubleword. (Unlike the peripheral processors, the
central processor does not write a half word; therefore the signal WRITE 16 is
not generated by the central processor control signals.) The BAC 0-2 signals
(memory access control signals) from bus adapter 22 are similarly decoded in
operation decoder 139 to derive read or write signals, input to circuitry 138.
The bus adapter write signals may be WRITE 8, WRITE 16, WRITE 32 or WRITE 64.
The MRBA (bus adapter memory request) signal is also input from the bus adapter
22.
The CP/BA input (from Figure 16) represents the priority allocation
for main memory access. (CP will be high when the central processor has
priority; BA will be high when a peripheral processor has priority,) The Clear
Miss signal is generated within cache 24 in a manner to be described, when the
cache miss has been satisfied by a main memory operation and the requested data
has been placed in the central processor memory data register 56 (Figure 3).
As is seen in the Figure, the "MOP" (memory operation) signal represents either
a bus adapter memory operation (BBACl, BBAC2 and BA priority) or a central
processor memory operation ~MCM 24 and 25, and CP priority).
Circuitry 138 generates appropriate memory control and timing sig-
nals from the described inputs. The generation of the control signals "WRITE
8", "WRITE 16", "WRITE 32", and "WRITE 64" has been described; "READ 64 B"
specifies the operation of reading a doubleword. The R/W (Read/Write: R high
for read, W high for write~ signal and Write Pulse are conventional inputs to
main memory 16. The Memory Timing Signals include CAS ~column address strobe),
CEN (column enable), and RAS (row address strobe), which are all conventional
and are input to main memory 16 to address it in a known manner.
The signals Cl, C2 and C3 are for internal use within the cache, and
- 17 -
keep track of the three instruction cycles (160 nanoseconds each) required for
a main memory operation. Their use will be explained in what follows. The
signal LC (last cycle) is 160 nanoseconds long and is generally synchronized
with the last cycle of the memory operation. The LC signal is input to reset
flip flop 141, which delays the CP priority signal (from Figure 16) to provide
a latched CP signal (LCP) whose use will be explained. Flip flop 137 is used
to delay the cache miss signal during a central processor Read operation, pro-
viding a "MISS EXT" (inverse) output whose use will be described.
The cache miss inverse signal is normally high, and maintains STCP
inverse (stop central processor), output from flip flop 135, normally high.
STCP inverse is input to the master clock (Figure 11); it is also input to cen-
tral processor memory address register 58 (Figure 3). So long as STCP inverse
remains high, the central processor is not stopped; the timing pulses TA, T0,
Tl, T2 are generated, and the central processor memory addresses are gated out
of memory address register 58. When a cache miss signal is generated, in a
manner to be described in connection with Figure 14, cache miss inverse goes
low, and at the next Ll timing pulse (L0 inverse is low) the output STCP inverse
goes low. This signal stops the generation of T pulses for the central proces-
sor, and also prevents the next memory address from being latched out to the
cache.
Referring now to Figure 13, the portion of the cache 24 particularly
relating to cache storage addressing and main memory addressing is shown. This
circuitry divides the cache cycle and dedicates alternate cache subcycles to
particular functions. The first cache subcycle is dedicated to processing a
central processor read address; the second cache subcycle is dedicated either to
processing a bus adapter read address for performing a cache check, or to writing
the cache. Writing the cache may involve either writing the invalid bit of a
- 18 -
55~P
particular cache entry after a cache check (performed in a previous cycle) has
determined that a tag match condition exists, or writing the cache data store
and tag to update the cache after a cache miss has been satisfied out of main
memory 16, or after a central processor main memory write.
The circuitry of Figure 13 receives addresses from two sources. One
address (MA 0-23) is received from central processor 12 for a memory operation
(read or write), and another address (BMA 0-23) is received from bus adapter
22 for a ca^he check or invalidate operation (resulting from a bus adapter main
memory write operation). The circuitry of Figure 13 determines which address
goes to the comparison circuitry of Figure 14 to be compared, and also which
address goes to main memory 16 for the memory operation. Generally, this cir-
cuitry includes multiplexers 102 and 104 to select the index and tag to be
applied to the cache storage and comparator of Figure 14; latches 110 and 108
to hold the input central processor address for application to main memory 16 in
case of a cache miss; and a multiplexer 112 to select the address to be sent
to main memory 16 for a memory operation.
Note that the circuitry of Figure 13 operates without reference to
whether the central processor memory operation is a read or a write. The "Read"
signal from Figure 15 is input to Figure 14, where the cache miss signal will
be generated only for a read operation. For a central processcr write operation,
all the operations up to the generation of the cache miss signal are performed,
but no miss signal is generated. Since, according to the invention, this sub-
cycle is dedicated to processing a central processor memory operation address,
no other operation could be performed during this subcycle, and therefore these
"wasted" operations cost no time.
Still referring to Figure 13, bus 26 carries address lines MA 0-23
from memory address register 58 of central processor 12 (Figure 3), which is
- 19 -
117S5~1
latched at L0 providing that the central processor is not stopped ~STCP inverse
is high). Bus 32 carries address lines BMA 0-23 from bus adapter 22. The
address from bus adapter 22 is stored in latch 100, which is gated (at time TA)
by the BA enable signal from Figure 17.
Of the incoming central processor address bus 26, lines 9-20 (which
carry the signals which comprise the index, see Figure 8) are input to the
Select Index Multiplexer 102, while lines 0-8 (the tag, see Figure 8) are input
to Select Tag Multiplexer 104. The incoming bus adapter address bus 32 is input
through buffer 106, enabled on a "BA Write" (BBAC 1) signal from bus adapter 22,
and is then similarly divided; lines 0-8 (the tag) are input to Select Tag
Multiplexer 104, while lines 9-20 are input to Select Index Multiplexer multi-
plexer 102.
The inputs to Multiplexer 102 are selected by the timing signal T12,
while the inputs to multiplexer 104 are selected by timing signal T12 inverse.
Thus the multiplexers 102 and 104 are switched at the same time but in opposite
senses; the central processor index is transmitted by multiplexer 102 when the
bus adapter tag is transmitted by multiplexer 104. Referring to the timing
chart of Figure 12, it is seen that T12 is high during Tl and T2; therefore T12
is an 80 nanosecond wide pulse.
Multiplexers 102 and 104 are thus switched twice during each cache
cycle (160 nanoseconds). During the first half of the cycle, the A inputs
(central processor index) to select index multiplexer 102 are transmitted to
cache address latch 114; during the second half of the cycle the B inputs are
transmitted. The B inputs may be either the bus adapter address from buffer 106,
for a cache check (on BA priority, during a peripheral processor write to main
memory); the same bus adapter address (held in buffer 106) for an invalidate
bit write (after a previous cache check has resulted in a tag match condition);
- 20 -
ll~SS8~
or a previously input central processor address (from latch 108). The previous-
ly input central processor address is either one for a read memory operation
which has caused a cache miss, or one for a central processor write memory
operation; in either case the address is now to be used as the address for a
cache update write operation.
During the first half of the cycle the B inputs to select tag multi-
plexer 104 are transmitted to select tag latch 116 for input to the tag compara-
tor (Figure 14); during thesecond half of the cycle the A inputs to multiplexer
104 are transmitted to latch 116. The purpose of this timing arrangement will
be explained in what follows.
Cache address latch 114 is latched by the "address clock" signal (Ll
LA); select tag latch 116 is latched by the "in tag clock" signal (Ll LA inverse).
For each main memory operation (including a cache update after a
miss), an address must be selected for application to main memory 16 for the
memory operation. For each central processor operation, whether a memory opera-
tion or some other kind of operation, the central processor address (MA 0-23)
is gated through latch 110 by timing signal T2 (provided central processor 12 is
not stopped, GT2 high), and is applied to main memory address multiplexer 112
and to latch 108. If the operation is not a memory operation, or is a memory
read and there is a cache hit, the contents of latch 108 are never used. If
there is a cache miss, then the signals CP (central processor memory access
cycle, from Figure 16), Tl, and Cl (from Figure 15; Cycle 1, the first cycle of
the memory operation to satisfy the miss) gate the address through latch 108 to
multiplexer 102, to index the location in cache data store 124 for the update
write after the completion of the memory cycle. The tag portion of the address
is output as TW0-8 for writing into the cache storage, as will be described.
Because the central processor is stopped in response to a cache miss
1:~755~1
after timing interval T0 of its cycle, it may already (during TA, T0) have sent
another address to cache for a memory read, before being stopped by the cache
miss signal ~as will be described). This address will not be lost, because
it will be saved in latch 110, which will not be gated until the next T2 timing
signal, after the cache miss signal is cleared. Therefore, during a main memory
operation to satisfy a cache miss, latch 110 holds the address for the next
memory operation, while latch 108 holds the address which caused the miss and
which has just gone to the main memory for the current operation. When the
memory operation has been completed and the data is to be written into the cache,
the index for writing the cache is obtained from cache address latch 108. The
tag is output as TW0-8 (tag write) to be written into cache tag store 120 at
the same time.
The alternate inputs to main memory address multiplexer 112 are
selected by the signal BA (high or low), from the priority circuitry of Figure
16. The selected address signals (BMAR 3-20, with module select signals not
pertinent to the invention) are output to address main memory 16 (Figure 19),
and to memory controller 18 (CMA 0-23). The memory controller employs the
address signals to maintain a bus transaction log and for other purposes, none
of which are pertinent to the present invention.
Referring next to Figure 14, the storage portion of the cache is
shown. This drawing has been simplified by not showing the actual division of
the cache into even and odd portions, which is not pertinent to the operation
of the invention. In effect, only one-half of the storage portion is shown.
To visualize the even/odd arrangement of the cache, Figure 14 up to the flip-flop
130 can be considered to represent either the even or the odd portion of the
cache; the remaining portion will then be represented by another similar struc-
ture, not shown, whose output is also input to the one bit flip-flop 13~ to
- 22 -
13~7~5~31
provide a single cache miss signal.
Data Store 124 is a random access memory (RAM) which stores the cache
entries, while Tag Store 120 stores the associated 9-bit tags, and Invalid Bit
Store 122 stores the associated Invalid Bits. Elements 124, 122 and 120 are all
addressed by the 12-bit index from cache address latch 114 (Figure 13), input
by the "address clock" timing signal (Ll LA) ~Figure 13). The tag portion of
the cache entry is read out to tag latch 134. The word portion of the cache
entry is simultaneously read out to data latch 126.
Tag latch 134 is controlled by the "tag latch enable" signal (timing
signals L0 + L2, the trailing edge of the pulse being active) to transmit the
stored tag to tag comparator 132. The address tag portion selected at multi-
plexer 104, represented as CWA 0-8, is input to tag comparator 132 from latch
116 (Figure 13) by the "in tag clock" (Ll LA inverse) for comparison. The miss/
hit output of the comparator is low if the tags are equal, or high if they are
unequal. This output is input to a one-bit flip-flop 130 which is sampled by
the "Miss clock" (LA inverse) for a central processor read memory operation only,
as controlled by the "Read" Signal from Figure 15. On a central processor write
memory operation or on a BA address subcycle, no cache miss or cache miss in-
verse signal is generated. The miss/hit bit from comparator 132 is OR'd with
the stored Invalid bit from store 122, before being input to flip-flop 130.
Thus, for a central processor read, either a no-tag-match condition or an invalid
bit results in a cache miss, represented by the cache miss signal (condition
signal).
The miss/hit signal is input to flip-flop 137 of Figure 15, as pre-
viously described, which generates a "Miss Extended" inverse signal (during a
read operation only).
The data from data store 124 is latched out of data latch 126 by the
- 23 -
1~7~58i
"data latch enable" signal (Ll L2) to buffer 128. If the tags are equal, and the
bit from store 122 indicates the entry is valid, then the data from buffer 128
goes directly on bus 40 to the memory data register 56 of central processor 12
(Figure 3); the Miss Extended inverse signal from flip-flop 137 enables latch
54 (Figure 2) and disables buffer 128.
The miss/hit bit from tag comparator 132 is also input to set flip-
flop 146. During a subsequent cache cycle, as will be described in more detail
in connection with Figure 22, the Invalid output is applied to the data-in port
of the cache invalid store 122, to be written at the address currently applied
to the store from cache address latch 108.
Since the data latch enable signal is high only during the first
cache operating cycle subcycle, no data will be latched out to central processor
12 during the second subcycle, for a cache check, invalidate write, or cache
data write operation.
Referring again to Figure 11, as has been described, the cache miss
signal stops the central processor by inverting GT2, which inhibits timing
pulses Tl and T2. The central processor is therefore stopped after timing pulse
T0. If no bus adapter is requesting main memory access, the priority circuit
of Figure 16 generates the signal CP/ (BA Inverse). The cache miss can be
immediately satisfied.
To satisfy the central processor read request on a cache miss, the
dule select bits (not shown) and the address signals BMAR 3-~ (from Figure
13) are sent to main memory 16 (Figure 19), together with timing and control
signals from Figure 15, to select the addressed doubleword. Three instruction
cycles are required to complete the main memory access. The doubleword is
routed through memory controller 18 on bus 44, and is then sent on bus 52 to CP
data latch 54 (Figure 2); the Miss Extended signal latches the data into memory
- 24 -
11755~
data register 56 ~Figure 13).
The cache miss signal is cleared ~Figure 14) at L0 when the memory
timing circuitry of Figure 15 has determined that the last cycle of the three
required main memory operation cycles has been reached, for a memory read opera-
tion pertaining to the central processor (LC, LCM 24, and LCP; LCM 24 is the
latched memory control signal CM 24 from Figure 18, which is always high for a
read operation). These inputs together are called the "Clear Miss" signal,
which is also input to the circuitry of Figure 15, where it clears the Read
signal.
In response to the cleared cache miss signal (miss inverse goes high),
the "STCP" (stop central processor) signal inverts at L0 (flip-flop 135, Figure
15). Referring again to Figure 11, when Miss inverse goes high, GT2 allows
pulses Tl, T2 to be output to the central processor, which restarts the processor
in mid cycle. GTl then allows pulses TA, T0 to be output. The central processor
then continues to operate until another cache miss occurs (or unless a write
main memory operation occurs, which is not pertinent to the present invention).
More in detail, and referring now to the timing chart of Figure 23,
the signal STCP inverse is normally high. It becomes low in either the case of
a central processor write to main memory, not described herein, or in response
to the Miss signal from flip-flop 130 (Figure 14), as shown in Figure 15. STCP
inverse goes low at the time Ll. As seen in Figure 11, STCP inverse is the in-
put to the Clear of GTl flip-flop 61; when STCP inverse goes low, GTl inverse
is forced low, inhibiting the next TA, T0 pulses to central processor 12, and
GTl is forced high.
In the absence of the cache miss signal (that is, in the case of a
central processor main memory write operation), the GTl signal is input to D of
the GT2 flip-flop 63; thereafter, at the next L0 pulse, GT2 inverse goes low,
- 25 -
117SS81
inhibiting the next Tl, T2 pulses to central processor 12. When STCP inverse
goes high again ~after the write operation is initiated) at pulse Ll, GTl
inverse goes high at pulse L2 (timing pulses TA, T0 are allowed), and GT2 in-
verse goes high at the next pulse L0 (timing pulses Tl, T2 are allowed). Thus
in the Write Main Memory case, the central processor 12 is stopped at TA and
takes up again at that pulse.
In the case of stopping the central processor because of a cache
miss, the cache miss signal is not generated until L0, halfway through the TA
pulse. Therefore a different stopping time (and timing of resuming operations)
must be provided in this case. For this purpose, the cache miss inverse signal
is AND'd with GTl for input to D of GT2 flip-flop 63, and the cache miss inverse
signal is also AND'd with the GT2 inverse output of flip-flop 63. Therefore
the gating signal GT2 is forced high when cache miss inverse goes low, inhibit-
ing the Tl, T2 pulses and stopping the central processor in mid-instruction
cycle. GTl inverse is subsequently forced low (at Ll) by STCP.
After the cache update has been completed, with the cache data store
being written (as will be described) during time TA of the second cache sub-
cycle within the last main memory cycle), the cache miss signal from flip-flop
130 is cleared (Figure 14). Cache miss inverse goes high at L0; STCP inverse
goes high at Ll (Figure 15). The transition of cache miss inverse forces GT2
low at L0, which allows timing pulses Tl, T2 to be output to central processor
12; thereafter, at L2, GTl inverse goes high and allows pulses TA, T0. The
central processor instruction cycle therefore resumes in midcycle, where it
left off.
The cache data store is updated after a cache miss, or during a cen-
tral processor main memory write operation, by a write cache operation.
Referring now to Figure 20, the cache write circuitry 150 controls
- 26 -
~L755~1
the writing of the cache contents after a cache miss, and also controls the
writing of the cache Invalid bit after a tag Match on a BA address comparison.
For writing the Invalid bit, the Invalid ~inverse) bit (from flip-flop 146,
Figure 14) is input to circuitry 150. For writing the cache data store, the
control signals LCM 24 and MCM 24, and the write control signals Write 8, Write
16, Write 32 or Write 64 (from Figure 15) are input.
Writing the cache data store occurs at different times for a main
memory write or read operation, as will appear in connection with Figure 23.
All writes occur at time TA, that is, during subcycle B of the cache operating
cycle. For a main memory write operation, the write pulses are output at time
TA of memory cycles Cl and C2 (Figure 15), while for a main memory read (cache
update) the write pulse is output at time TA of memory cycle 3 (LC, last cycle).
Invalidate bit writes also occur at time TA, during any cycle of the main memory
cycle. Since all writes occur during the second subcycle of the cache operat-
ing cycle, the cache write operations cannot interfere with the accepting of a
central processor read memory request during the first cache subcycle.
The Write Cache Pulses are input to tag store 120, invalid store 122,
and data store 124 (Figure 14) as appropriate.
The dedication of the cache subcycles to particular functions, as
described, and in particular the dedication of the first subcycle exclusively
to accepting a central processor memory read request, has the result that a
central processor address for a memory read operation is always accepted, once
in each cache cycle, for the purpose of comparing its tag with the cache contents.
If there is a cache hit, the requested data is returned to the central processor
within the TA period of the next central processor microinstruction cycle. The
central processor is thus able to proceed without pause.
If there is a cache miss, the central processor is stopped, and may
be obliged to wait several cycles until it obtains main memory access, which
occurs only when no bus adapter is contending for access. When the data is
obtained from main memory, it is provided immediately to the central processor,
during the second subcycle of the cache cycle, and when the central processor
is started again in response to the cache miss inverse going high, the central
processor starts in a phase of operation as though there had been a cache hit.
The cache data store is written during the second cache subcycle, after the
central processor has restarted.
The cache is checked for bus adapter tag matches only during a second
subcycle of the cache operating cycle. On a tag match condition, flip-flop 146
is set, and on the next second subcycle (after the central processor has had
its opportunity to enter a read memory request) the invalid bit at the matched
address is written by cache write logic 150 (Figure 20). Any subsequent attempt
by the central processor to read that location in cache will result in the
generation of a cache miss signal, and the cache will be updated as has been
described.
As a result of this dedication of cache operating subcycles, the
writing of the cache (either to write an invalid bit, to update a doubleword
in response to a cache miss, or to update the cache after a central processor
main memory write) is "transparent" to the read memory operations of the cen-
tral processor. The central processor never has to wait while such writing is
done. In particular, unlike the arrangement in many data processing machine
employing a cache memory, there is no "dedicated" cache cycle required for up-
dating the cache after a cache miss before the central processor can resume
operation. Moreover, the central processor can immediately (on its next micro-
instruction cycle) read a location which has just been updated after a cache
miss. When the central processor attempts to read a location which has just
1~755~3~
been the location of a main memory write operation, anomalies may occur, but
this situation is easily avoided by suitable precautions in microprogramming the
central processor.
Referring now to the timing diagrams of Figures 21, 22 and 23, the
operation of the invention will be described.
Referring first to Figure 21, the events of a central processor
read memory operation are shown.
The central processor read memory microinstruction begins at time
TA and lasts through T2. At the positive edge of LA inverse, the address is
made available to cache 24 from memory address register 58 (Figure 3). While
T12 is low, the A inputs to index multiplexer 102 (Figure 13) are selected,
transmitting the central processor index to cache address latch 114. The
"address clock" (Ll, LA) goes high at Ll and transmits the central processor
index from latch 114 to address the cache store (Figure 14). In response, data
is output from data store 124 and is latched out of data latch 126 at during Ll
L2 (80 nanoseconds). This data is latched into the central processor memory
data register 56 (Figure 3) at TA. In the case of a cache hit, the central pro-
cessor continues without pause with its next microinstruction cycle.
When T12 goes high, T12 inverse goes low, and the A inputs (central
processor tag) to select tag multiplexer 104 are selected and transmitted to
select tag latch 116. The "in tag clock" (Ll inverse, LA inverse) latches the
tag out to comparator 132 (Figure 14). The stored tag is output from tag store
120 at the same time as the stored data, in response to the input index from
latch 114; the negative-going edge of the "tag latch enable" (L0, L2) transmits
the stored tag to comparator 132. The miss-hit output of comparator 132 is
input to flip-flop 13Q, which it samples at LA inverse ("miss clock"). In the
case of a cache miss, the cache miss signal input to flip-flop 135 (Figure 15)
- 29 -
117~5~31
causes STCP to invert at L0 inverse.
As is seen in Figure 21, the cache miss signal is generated only
after the cache data has already been transferred to the memory data register
of central processor 12. If there is no miss, the central processor continues
with that data. If there is a miss, the central processor will be stopped after
T0 (as will be described in connection with Figure 23); the data will be re-
placed by the main memory read operation before the central processor resumes
operation.
Referring now to Figure 22, the cache check and invalidate operations
are illustrated. These operations are initiated only on a bus adapter (peri-
pheral processor) write to main memory operation. For such an operation, the
bus adapter sends the MRBA signal to the circuitry of Figures lG and 17, which
generate the BA priority signal and the BA enable signal. The BA enable signal
goes high at TA. A main memory operation is initiated by the circuitry of
Figure 15, beginning with cycle 1 (Cl) at T0. The memory access control signal
BAC 1 is latched as BBACl when the memory operation begins. When Tl, T2 is high,
the B inputs (BA index) to multiplexer 102 are selected and output to cache
address latch 114. The "address clock" (Ll, LA) outputs the BA index to the
cache store (Figure 14). No data is transmitted to the central processor.
The B inputs (BA tag) to multiplexer 104 are selected when Tl, T2
inverse goes high; the BA tag is transmitted to select tag latch 116. The "in
tag clock" (Ll inverse, LA inverse) latches the tag out to comparator 132. The
stored tag is latched out of tag latch 134 by "tag latch enable" ~L0, L2) to
comparator 134. The miss/hit bit is input to the invalidate flip-flop 146
(Figure 14), which is sampled by the "invalidate clock" at L2. In the case of
a tag match condition, the output INV inverse (normally high) goes low.
The INV inverse signal is input to the cache write circuitry of Figure
- 30 _
1~ 7SS~l
20, where it causes a write cache pulse to be output at TA. The INV output of
flip-flop 146 is the data input to invalid bit store 122 (Figure 14) when the
write cache pulse is input. The address at which the INV signal is written
is the same address at which the tag match condition was found, since the
address is maintained in buffer 106 throughout the BA main memory write opera-
tion (no furthcr BA address can be input until the memory operation is completed,
which may be after several cache operating cycles). The invalidate write
operation may in fact be repeated during each cache cycle throughout the main
memory operation; this causes no problem. Note that during the entire BA main
memory operation, including the invalidate write operations, the central pro-
cessor continues to have an opportunity in each cache cycle to read the cache.
If one of the central processor read operations results in a cache miss, the
central processor must be stopped until after the completion of the BA main
memory operation; if no other BA memory operation is pending, the central
processor will then be given memory priority by the circuitry of Figure 16, and
the main memory read and cache update can proceed.
Referring now to Figure 23, the events of a cache miss and update
are shown. The cache miss inverse signal goes low at L0 (Figure 14); the STCP
inverse signal goes low at Ll (Figure 15). The central processor 12 is stopped
after T0. The main memory operation is initiated with cycle 1 (Cl at T0). The
main memory operation comprises three cycles; the memory is written during
cycles 1 and 2 and read during cycle 3. The cache write pulse for updating the
cache store after a miss is generated during the last cycle (C3) since the main
memory must be read before the cache store can be written. Cache miss inverse
goes high again at L0 during the last main memory cycle; STCP inverse goes high
at Ll. The central processor is restarted at pulse Tl.
For a central processor memory write, the cache write pulses are
- 31 -
~7~i5~31
output at TA during cycles 1 and 2; the central processor is restarted after the
memory operation has begun. Central processor 12 can therefore read the cache
during each subcycle A while the write cache operation continues during sub-
cycle B.
- 32 -
