Circuit for allocating memory cycles to two processors that share memory

A circuit for allocating main memory cycles between two data processors has means for making the allocation by either of two procedures. In one procedure, control of memory is transferred only after a request for memory access has been made. In a second procedure, transfer of memory control to a requesting processor is automatically accompanied by a request to return control. The control memory of a processor selects the process by two bits called Code Idle and Code Release. Code Idle accompanies instructions that usually mean that the releasing processor will not need memory for several memory cycle times, and an explicit request for transfer is made when memory is actually needed. Code Release accompanies instructions that do not require memory access at the time but are typically followed by a memory request within a processor cycle time or a few processor cycle times. Memory control is returned without the delay that is associated with an explicit request.

FIELD OF THE INVENTION 
This invention relates to a data processing system in which two processors 
share a main memory. More specifically, the invention relates to a circuit 
that allocates memory cycles to each processor. 
INTRODUCTION 
Circuits are well known that allocate memory cycles to two different 
processors, but it will be helpful to review the features and the 
terminology that particularly apply to this invention. Some of these 
features can be illustrated in a single processor system. In a single 
processor system, a data bus interconnects registers of the memory with 
registers in the processor, and an address bus connects a memory address 
handling circuit in the memory to receive an address from a register in 
the processor. There is also a control bus that the processor uses to send 
a select signal to the memory to start a memory cycle. The memory may use 
this bus to signal status to the processor, for example that the memory is 
busy or that there is valid data on the data bus. 
The processor also operates with a control memory (or with equivalent 
sequential logic circuits) that is accessed for a control word (also 
called a microcode word) that contains a bit pattern that sets the gates 
of the processor to a particular state. A sequence of these control words 
steps the processor gates through a sequence of states for a particular 
operation such as fetching a data word from the main memory. When the 
processor decodes an instruction, it uses the Operation code of the 
instruction as an address to access the control memory at the appropriate 
location for the first control word in a control program routine for the 
instruction. At the end of the control program routine for one 
instruction, the processor branches to a location in the control memory 
for a control program routine to fetch the next instruction from main 
memory. The control word as it has been described so far is also combined 
with status bits to permit branches in the control program. 
The cycle time of the main memory is ordinarily longer than the cycle time 
of the control memory and it may be an integral number of the control 
memory cycle times, for example, twice as long in the system that will be 
described to illustrate this invention. In this example, some processor 
instructions are executed in three or a small number of cycles, and some 
require a few times as many cycles. Thus, in a sequence of memory 
accesses, the memory operates in synchronism with the processor, beginning 
a next memory cycle at a corresponding point in the clock cycle of the 
processor when the processor raises the memory select signal. When two 
processors share memory, each processor alternates between memory 
accessing instructions and arithmetic and logic unit instructions, and the 
memory operations of each processor can more or less fit into the times 
for the arithmetic and logic operations of the other processor. 
THE PRIOR ART 
In a multi-processor system, the memory address bus and the memory data bus 
have gates that connect these busses to a particular one of the 
processors, and an allocation circuit is provided for permitting only one 
of the processors to be connected to the memory busses for a memory cycle 
time. Ordinarily, a memory allocation circuit has a latch that is set to 
enable the gates in the bus of one processor and is reset to enable the 
gates of the other processor. The latch is switched whenever control of 
memory is to be switched between the processors. 
As an introductory example of a memory allocation circuit, the two 
processors may be assigned alternate cycles of the memory. If the 
processors are carefully synchronized, the processors can access memory 
with no delay in switching the control of memory from one processor to the 
other. A general object of this invention is to provide a new and improved 
memory allocation circuit that works well with two processors that are not 
precisely synchronized. This object is important in a system of two 
processors that have separate clocks that are only approximately at the 
same frequency. It is also important for a system of two processors that 
are mounted on separate boards and are interconnected by relatively long 
cables that introduce delays in propagating the clock signals and thereby 
cause significant skews in clocks. It is also generally important in 
multiprocessor systems because when the circuits are made faster, it is 
more difficult to maintain two processors in synchronism. 
In one technique for reducing the switch-over time, the processor that has 
requested access to memory is signalled slightly before the end of the 
last memory cycle by the other processor so that the requesting processor 
can raise its select signal as soon as possible (Mercy U.S. Pat. No. 
3,715,729). 
SUMMARY OF THE INVENTION 
It will be convenient to call the two processors "A" and "B" when referring 
to both of them in some combined operation. In these examples, either 
processor A or processor B may be identified as having access to memory or 
as not having access to memory. In a more generalized description, the two 
processors will be called the "requesting processor" and the "controlling 
processor" or the "releasing processor". This circuit operates to switch 
memory control from one processor to the other only after a request for 
memory access has been made by the requesting processor and the release 
has been granted by the controlling processor. Preferably, but optionally, 
the controlling processor does not release memory until it has decoded an 
instruction for a non-memory operation. The circuit performs the transfer 
of memory control by either of two procedures. In one procedure, a 
processor signals a request for the memory access when it decodes an 
instruction that requires memory access or when it branches to instruction 
fetch in its control program. In the second procedure, the request is made 
automatically as part of the release signal procedure. The two procedures 
are defined by the control program of the releasing processor. The control 
program routines are coded with two bits that will be called "Code Idle" 
and "Code Release". The logic function Code Idle+Code Release=0 defines a 
conventional memory request that would otherwise be coded by a single bit 
in the control memory. Code Idle signifies that a subsequent memory access 
is not required for some indefinite (but probably long) number of memory 
cycles. Code Release signifies that a subsequent memory access will 
probably be required within a memory cycle or so. Some examples will help 
to explain the significance of this circuit and operation. 
An example of Code Idle is in an instruction to multiply the contents of 
two registers. This operation does not require memory access because 
registers of the processor have already been loaded with operands from 
main memory. In addition, the multiply operation is performed as a 
sequence of additions and shifts, and it typically takes a relatively 
large number of processor cycles. The time for this operation is typically 
long enough that the other processor may operate to access memory, process 
the operands, and then access memory again. In this situation, it is an 
advantage to have the other processor retain control of memory even while 
it is not actually making access to memory. 
An example of Code Release is in the control program routine to fetch an 
instruction. The instruction being fetched may be the multiply instruction 
of the preceding example so that the current memory access will be the 
last access by the processor for several cycles, but there is a 
significant likelihood that it will be another access to memory to fetch 
operands. During the instruction fetch in this example, the processor that 
controls memory sends a signal Code Release to the other processor (if the 
other processor has signalled a request for memory access) and the 
releasing processor then immediately signals a request for memory access. 
If the other processor takes only one memory cycle, control of memory is 
returned as soon as possible. Means is also provided to cancel this 
automatic request if the next instruction is in fact one that has the Code 
Idle bit. Other examples will be presented later. 
In the circuit that will be described, each processor has a latch that will 
be called a control latch that is set to give control of memory to the 
associated processor or reset to give control of memory to the other 
processor. Thus, these two latches provide the conventional control 
function that is provided by a single latch in the description of the 
prior art. Each processor also has a latch called a request latch that is 
set by the other processor to signal that the other processor requires 
access to memory. This latch in the releasing processor is reset when the 
requesting processor gets access to memory. Each processor also has a 
latch that will be called a Release Latch that is set to switch control of 
memory to the other processor for an indefinite number of memory cycles in 
response to the control memory bit Code Idle and the set state of the 
request latch. Each processor also includes gating the timing means that 
responds to Code Release to set the control latch of the other processor 
and then to set the request latch so that memory control can be returned 
on the next cycle. 
The apparatus that will be described in detail has other features and 
advantages that will illustrate more general aspects of the invention.

THE APATUS OF THE DRAWING 
Introduction--FIG. 1 
FIG. 1 shows two processors A and B that share a main memory. A gate 
circuit selectively connects the memory data bus, address bus and control 
bus to the corresponding busses of the processors. A memory allocation 
circuit receives a memory request signal from the processors and controls 
the gates to give memory access to a selected one of the processors. (In 
the more detailed description later, the allocation circuit will be 
described from the viewpoint of a separate set of components associated 
with each processor.) The allocation circuit also sends a select signal on 
the control bus to the memory to start a memory cycle. These components 
and interconnections are conventional in the broad way in which they have 
been described and they illustrate a wide variety of applications for the 
circuit of this invention. FIG. 1 also shows the signals Code Release and 
Code Idle which originate in the control memory of a processor. It also 
shows timing signals that are formed by each processor and are used by 
components of the allocation circuit. 
An Overview--FIG. 2 
FIG. 2 is a simplified view of the memory allocation circuit that shows the 
general flow of information in the circuit and the interconnections with 
other components. Line fragments are shown to indicate the relation of 
FIG. 2 to the more detailed circuit of FIG. 3. Ordinarily, the allocation 
circuit will be constructed as separate identical circuits for processors 
A and B, and the circuit for A is shown in the upper part of FIG. 2, and 
the circuit for B is shown in the lower part. Letter subscripts "a" and 
"b" designate components for a particular processor A or B. 
Each processor separately produces signals Code Release and Code Idle. Code 
Release has an up level (arbitrarily) and a 1 logic level when the current 
instruction that is being executed does not require memory access but is 
likely to be followed by an instruction that does require memory access. 
Code Idle has a 1 logic level when the current instruction does not 
involve memory access and is not likely to be followed within about a 
memory cycle time by an instruction that does require memory access. The 
function Code Idle+Code Release=0 is a request for memory access. The bits 
Code Idle and Code Release are part of the microcode and values of these 
bits are assigned on the basis of the statistical frequency that a 
particular microcode sequence that does not require memory is followed by 
a microcode sequence that does require memory. Stated from a different 
viewpoint, if all of the microcode routines were coded to transfer memory 
control by Code Idle, the operation would be slowed because a releasing 
processor executing certain instructions would be required to wait while 
its memory request signal was processed by the other processor and memory 
control was returned. Conversely, if all transfer were handled by the Code 
Release procedure, the operation would be slowed by unnecessary transfer 
of control of memory. 
Each processor has a latch 4a, 4b that is set to give control of memory to 
the associated processor when the latch is set. The function of these 
latches is conventional in the simplified form of the circuit in FIG. 2. 
Latch 4a is set by a signal Release Memory to A on line 1b, and latch 4b 
is set by a corresponding signal from processor A. 
The signal Release Memory on line 1a or 1b falls to a 0 logic level to 
signal that the corresponding processor requests memory access, and this 
signal is transmitted through gates 7a or 7b and 8a or 8b to set a latch 
4a or 4b. The set state of latch 4a or 4b signals that the other 
processor, B or A respectively, has requested a transfer of control of 
memory. 
A latch 3a or 3b is set to release memory to the other processor in 
response to the coincidence of the set state of the associated request 
latch and the signal Code Idle from the associated control memory. A gate 
11a or 11b performs the input logic for the latch and a gate 10a or 10b 
couples the latch output to the line 1a or 1b. 
Gate 10a or 10b cooperates with an AND gate 9a or 9b to produce a signal 
Release Memory on line 1a or 1b on the coincidence of a request for 
transfer and the bit Code Release. This signal is not latched and it 
appears on line 1a or 1b as a pulse, as will be explained in more detail. 
The logic functions that have just been introduced are shown as legends on 
the signal lines in the more detailed diagram of FIG. 3. 
The Circuit of FIG. 3 
FIG. 3 is a more detailed drawing of the memory allocation circuit for 
processor A. The input lines, the output lines and the latches will be 
familiar from the introductory description of FIG. 2. The other components 
will be introduced as they appear in descriptions of the operation of the 
circuit. 
Each processor has a conventional clock that operates through cycles of 
four clock times that are called C1, C2, C3 and C4. For some operations 
that will be described, each clock time is further divided into half. 
These four times make up a processor cycle or equivalently a control 
memory cycle and in the specific system that is being described two 
control memory cycles take as long as one main memory cycle. (As 
previously explained, the operations of the processor to access memory 
take two processor cycles.) 
Note that latch 5a is a D type latch that is set or reset according to the 
binary value of a signal at a data input D at a time when a signal is up 
at a clock input C. Gates 11a and 12a similarly control the latch 3a to be 
set or reset at a clock time C4. The actual times and time relationships 
that have been presented only to make the operation examples easy to 
understand, and the invention will be useful in systems with various 
timing arrangements. 
Operation With Code Idle--FIG. 4 
FIG. 4 shows a series of timing waveforms that illustrate the use of the 
Code Idle bit. At the beginning of the example, the control latch 4a is 
set to give control of memory to A. Conventional circuits that are not 
shown in the drawing respond to the set state of latch 4a and to the A 
clock, and at the midpoint of C2 time processor A raises its select signal 
to begin a memory cycle. This memory cycle runs through two processor 
cycle times and ends at the midpoint of the second next C2 time. At the 
beginning of the example, processor B does not need memory (Code 
Idle(B)=1) and line 1b is up and the request latch 5a remains reset. 
Similarly, processor A requires memory and its line 1a is down. Processor 
B encounters a need for memory access and drops line 1b to set latch 5a at 
the next C2 time. Since the clocks of A and B are not synchronized, the 
fall of line 1b can occur at any time with respect to the clock of A, and 
the timing of FIG. 4 is arbitrary. Also, FIG. 4 illustrates the example in 
which A releases the next memory cycle, but in the general case A may 
continue to take several memory cycles before releasing memory. 
In the interval between the start of the memory cycle for A and the second 
C4 time, A has decoded an instruction that has caused Code Idle(A) to 
rise. An AND gate 11a detects the coincidence of Code Idle(A), C4 time, 
and the request at the output of latch 5a, and gate 11a sets latch 3a 
which raises the signal Release Memory to B on line 1a. The signal on line 
1a also resets latches 4a and 5a. Resetting latch 4a takes control of 
memory away from A and resetting latch 5a signifies that B has not made a 
request for memory control since control was transferred to B as the 
result of a previous request. 
While processor B waits for memory control after dropping the signal on 
line 1b, it stops its clock at a position to restart with the rise of the 
C2 timing pulse. In the interval that starts with the rise of Release to B 
on line 1a and ends with the midpoint of C2 time when the memory cycle for 
A ends, conventional circuits in B are able to detect the set state of 
latch 4b and to restart the B clock and raise the Memory Select signal on 
the memory control bus. The switch over is not instanteous because the 
output of latch 4a or 4b is propagated through two latch stages (not 
shown, but conventional) to avoid a problem of latch metastability that 
may occur when communicating components are not otherwise synchronized. B 
then accesses memory for one or several memory cycles until a request has 
been made by A and B no longer needs memory. 
Operation of Code Release--FIG. 5 
The example of FIG. 5a begins in the same way that has been described for 
the example of FIG. 4. However, in this example, the release to B is 
enabled by the bit Code Release (A), and the signal on line 1a is a pulse 
having the timing of a C4 pulse of the A processor clock. In response to 
the rise of this pulse, latch 4b sets and latches 4a and 5b are reset as 
in the previous example. However, on the fall of the pulse, latch 5b is 
again set. Thus is a request for access by A is registered before A 
actually decodes an instruction that may or may not require memory access. 
FIG. 5 shows the example in which B raises release on line 1b during the 
first memory cycle and A makes access to memory or for next cycle. 
Alternatively, B may keep control of memory by not raising release and/or 
A may decode an instruction that causes Code Idle to rise on line 1a and 
causes latch 5b to reset. 
As a modification of the example of FIG. 5, suppose that Code Release rises 
in processor A at a time when Release Memory to A is still up on line 1b. 
In this situation Request latch 5a is still reset and gate 10a is closed 
so that the release pulse does not appear on line 1a as in the example of 
FIG. 5. If B requires a memory access while Code Release is up in A, latch 
5a sets at C2 time and gate 10a is opened to transmit a release pulse to B 
at the next C4 time, as in the example of FIG. 5. 
Several common operations involve two processor cycles in which one memory 
access is made and then two subsequent processor cycles or non-memory 
operations and then a next instruction fetch. If processor A is in such a 
sequence and processor B has already requested access to memory, B may 
make a single access to memory during the third and fourth processor 
cycles of A in the optimum example, as in FIG. 5. If B requests memory 
during the third processor cycle of A, B can make a single access to 
memory during the fourth processor cycle in A and in a next processor 
cycle in which A must wait for memory access as in the modification of 
FIG. 5 described in the preceding paragraph. Thus in the second of these 
examples, the invention reduces the time that memory is unused when both 
processors are accessing memory in a non-optimum situation. 
OTHER EMBODIMENTS 
The circuit can be adapted easily to modified operations. As one example, 
each processor may have conventional means for operating as a data 
channel. A beginning channel operation is a further example of microcode 
instruction sequences that do not require memory for several cycle times. 
Conversely, while data is transferred between main memory and an I/O 
device, one processor makes intensive use of memory. Preferably, each 
circuit includes a latch that is set by microcode that identifies a data 
transfer for an I/O operation. When the latch is set, the lines 1a and 1b 
are switched to give the next memory cycle to the processor that is 
performing the channel operation, even if this processor has not release 
memory. In some systems, only one processor has attached devices and the 
other processor does not execute channel instructions. In this situation, 
only one processor is programmed to execute instructions that access 
control program routines that cause this switch in memory control. If both 
processors have attached devices, this modified circuit causes control of 
memory to pass back and forth so that the two processors advantageously 
take alternate memory cycles. 
Other modifications of the circuit will be apparent within the spirit of 
the invention and the intended scope of the claims.