Language selection

Search

Patent 1323449 Summary

Third-party information liability

Some of the information on this Web page has been provided by external sources. The Government of Canada is not responsible for the accuracy, reliability or currency of the information supplied by external sources. Users wishing to rely upon this information should consult directly with the source of the information. Content provided by external sources is not subject to official languages, privacy and accessibility requirements.

Claims and Abstract availability

Any discrepancies in the text and image of the Claims and Abstract are due to differing posting times. Text of the Claims and Abstract are posted:

  • At the time the application is open to public inspection;
  • At the time of issue of the patent (grant).
(12) Patent: (11) CA 1323449
(21) Application Number: 1323449
(54) English Title: METHOD AND APPARATUS FOR SHARING MEMORY IN A MULTIPROCESSOR SYSTEM
(54) French Title: METHODE ET DISPOSITIF POUR METTRE UNE MEMOIRE EN COMMUN DANS UN SYSTEME MULTIPROCESSEUR
Status: Expired and beyond the Period of Reversal
Bibliographic Data
(51) International Patent Classification (IPC):
  • G06F 13/18 (2006.01)
  • G06F 12/02 (2006.01)
(72) Inventors :
  • SCHIFFLEGER, ALAN J. (United States of America)
(73) Owners :
  • CRAY RESEARCH, INC.
(71) Applicants :
  • CRAY RESEARCH, INC. (United States of America)
(74) Agent: GOWLING WLG (CANADA) LLP
(74) Associate agent:
(45) Issued: 1993-10-19
(22) Filed Date: 1989-09-21
Availability of licence: N/A
Dedicated to the Public: N/A
(25) Language of filing: English

Patent Cooperation Treaty (PCT): No

(30) Application Priority Data:
Application No. Country/Territory Date
307,882 (United States of America) 1989-02-07

Abstracts

English Abstract


ABSTRACT OF THE DISCLOSURE
A system for sharing a memory between multiple
processors divides the memory into a plurality of sections,
subsections and banks and provides a CPU to memory path
between each CPU and each section of memory. Each CPU may
generate references to the memory from any one of four
ports, which are multiplexed to the memory paths and onto
the sections of memory. The system provides that each CPU
has an associated register in each subsection of memory and
that each CPU can make no more than one reference to a
subsection at a time. Reference conflict resolution means
are provided at the CPU level to arbitrate conflicts between
ports in the CPUs attempting to reference the same section
or subsection in the memory. Reference conflict resolution
means are provided at the subsection level of the memory to
arbitrate conflicts between different CPUs attempting to
reference the same banks of memory.


Claims

Note: Claims are shown in the official language in which they were submitted.


WHAT IS CLAIMED:
1. A system for sharing memory between a plurality of
processors, each processor having a plurality of ports for
generating memory references, the system comprising:
a shared memory comprising a plurality of sections,
each section connected to each processor by a memory path,
each section including a plurality of subsections, each
subsection including a plurality of banks, each bank including
a plurality of individually addressable memory locations;
section conflict means in each processor for
resolving conflicts between said memory references generated
by said plurality of ports of said each processor, so that
only one of said plurality of ports of said each processor
connects via the memory path for said each processor to one of
said plurality of sections at a time;
subsection conflict means in each processor for
resolving conflicts between said memory references generated
by said plurality of ports of said each processor, so that
only one of the memory references accesses one of said
plurality of subsections at a time; and
bank conflict means in each subsection for resolving
conflicts between said memory references generated by said
plurality of processors allowed access to one of said
plurality of subsections, so that only one of the memory
references generated by aid plurality of processors accesses
one of said plurality of banks in said one of said plurality
of subsections at a time.
2. The system of claim 1, wherein the section conflict
means in each processor comprises:
means for receiving the memory references generated
by the plurality of ports of said each processor as received
memory references;
means for determining if the received memory
references are attempting to access a particular section;
means for allowing only one of the ports of said
each processor to connect via the memory path for said each
processor to the particular section at a time if more than one
24

of the received memory references is attempting to access the
particular section; and
means for generating a conflict signal to a selected
port of said each processor whose particular memory reference
is attempting access to the particular section when the
selected port is not allowed to connect to the particular
section, because the selected port has an access priority
which is lower than the access priorities of the other ports
of said each processor attempting to access the particular
section, thereby causing the selected port to hold and
resubmit the particular memory reference and to stop
generating additional memory references until the selected
port is allowed to connect to the particular section.
3. The system of claim 1, wherein the subsection
conflict means in each processor comprises:
subsection busy means for monitoring each subsection
and for generating a subsection busy signal therefor
indicative of whether a memory reference from one of said
ports of said each processor is accessing said each
subsection; and
subsection conflict resolution means associated with
each port of said each processor for receiving a memory
reference as a received memory reference attempting to access
a requested subsection and the subsection busy signal for the
requested subsection, for allowing only one memory reference
from said each processor to access the requested subsection at
a time, and for generating a conflict signal to a selected
port of said each processor whose particular memory reference
is not allowed to access the requested subsection because the
subsection busy signal for the requested subsection indicates
a previous memory reference from one of the ports of said each
processor is currently accessing said requested subsection,
thereby causing the selected port to hold and resubmit the
particular memory reference, and further, causing the selected
port to stop generating additional memory references until the
held memory reference is allowed to access the requested
subsection.

4. The system of claim 1, wherein the bank conflict
means in each subsection of said shared memory comprises:
bank busy means for monitoring each bank in aid each
subsection and for generating a bank busy signal therefor
indicative of whether a memory reference generated by one of
said processors is accessing said each bank; and
bank conflict resolution means, one for said each
processor, for receiving a memory reference as a received
memory reference generated by one of said plurality of
processors attempting to access a requested bank, for
receiving the bank busy signal for the requested bank, for
allowing only one memory reference to access the requested
bank at a time, and for generating a bank conflict signal for
a selected processor when a particular memory reference
therefrom is not allowed to access the requested bank because
said requested bank is busy as indicated by said bank busy
signal for the requested bank.
5. The system of claim 1, wherein the bank conflict
means further comprises simultaneous bank conflict resolution
means for receiving said memory references generated by said
plurality of processors, for determining when more than one of
the memory references are simultaneously attempting to access
a particular bank, and for generating simultaneous access
conflict signals indicative of whether more than one of the
memory references is simultaneously attempting to access said
particular bank, said bank conflict resolution means for
receiving said simultaneous access conflict signals, for
allowing only one memory reference from one of said plurality
of processors to access the particular bank at a time, and for
generating simultaneous bank conflict signals for the other
processors attempting access when said memory references
therefrom are not allowed to access the particular bank
because said one of said plurality of processors which
generated said memory reference with allowed access has an
access priority greater than said other processors.
6. The system of claim 1, wherein the bank conflict
means further comprises release subsection means, one for said
26

each processor, for generating a release subsection signal to
said each processor based on the bank conflict signal for the
requested bank and the simultaneous bank conflict signals when
a memory reference from said each processor is allowed to
access said requested bank in the absence of any conflicts.
7. The system of claim 6, wherein said each subsection
further comprises:
subsection reference holding means, one for said
each processor, for receiving a memory reference from said
each processor, and for holding said memory reference if not
allowed access to said requested bank in said each subsection
until said each subsection is referenced again by said each
processor not allowed access to said requested bank; and
subsection read data holding means, one for said
each processor, for receiving read data from said requested
bank referenced by one of the processors, and for holding the
read data until the requested subsection is referenced again
by said one of the processors.
8. The system of claim 6, wherein said each subsection
further comprises:
subsection reference holding means, one for said
each processor, for receiving a memory reference from said
each processor, and for holding said memory reference if not
allowed access to said one of said plurality of banks in said
each subsection until said each subsection is referenced again
by said each processor not allowed access to said one of said
plurality of banks; and
subsection read data holding means, one for said
each processor, for receiving read data from said one of said
plurality of banks in one of said plurality of subsections
referenced by one of the processors, and for holding the read
data until said one of said plurality of subsections is
referenced again by said one of the processors.
9. The system of claim 8, further comprising:
asynchronous means, in at least one port of said
plurality of ports of said each processor, for permitting a
27

plurality of memory references from said at least one port to
access the shared memory in a non-sequential order; and
resynchronization means, in said at least one port
of said each processor, for returning results of said
plurality of memory references accessing said shared memory to
said at least one port in sequential order.
10. The system of claim 1, further comprising release
conflict resolution means in each processor for determining
when a particular memory reference generated by one of said
plurality of ports of said each processor has completed
accessing a requested bank in a requested subsection.
11. The system of claim 10, wherein the release conflict
resolution means in each processor comprises:
reference delay means coupled to each of said
plurality of ports in said each processor, for receiving
memory references from said each port and for delaying said
particular memory reference which as proceeded through the
section conflict means and the subsection conflict means of
said each processor until a time when a release subsection
signal for the particular memory reference would be received
from the requested subsection if no bank conflict occurs;
release subsection pending means for receiving the
release subsection signal, for holding the release subsection
signal until the particular memory reference has proceeded
through the reference delay means, and for generating a
release subsection pending signal while the release subsection
signal is held; and
subsection clearing means for clearing a
corresponding subsection busy signal in the subsection
conflict means indicative of whether another memory reference
is accessing said requested subsection when the release
subsection signal or the release subsection pending signal
match the particular memory reference, indicating that said
particular memory reference from the reference delay means is
allowed to access said requested bank of said requested
subsection.
28

12. The system of claim 11, wherein the release conflict
resolution means in each processor further comprises release
conflict checking means coupled to at least one read port of
said plurality of ports in said each processor, for receiving
a read memory reference attempting access to said requested
subsection from the reference delay means, for receiving
release subsection signals from the subsections, for receiving
release subsection pending signals generated while the release
subsection signals are held by the release subsection pending
means, for determining whether the read memory reference has
completed accessing said requested subsection by comparing
said read memory reference with said release subsection
signals and said release subsection pending signals, and for
generating a conflict signal when the read memory reference
has not completed accessing the requested subsection, the
conflict signal causing other all read memory references in
the reference delay means to be held and the read memory
reference to be resubmitted, and further, causing said at
least one read port to stop generating additional read memory
references until the other read memory references held in the
reference delay means are allowed to access the subsections to
which they are attempting access.
13. The system of claim 11, wherein the release conflict
resolution means in each processor further comprises release
section conflict resolution means for receiving conflict
signals from said release conflict checking means of said at
least one read port in each processor indicating whether read
memory references of said at least one read port in each
processor have completed access to the subsection to which
they are attempting access, for determining whether more than
one read memory reference is attempting to access said one of
said sections at a time, for allowing only one of the read
memory references with highest priority to access said one of
said sections at a time, and for generating a release section
conflict signal to a selected read port when a particular read
memory reference therefrom is not allowed to access said one
of said sections, the release section conflict signal causing
the selected read port to hold and resubmit the particular
29

read memory reference therefrom and other read memory
references subsequent thereto in the reference delay means,
and further, causing the selected read port to stop generating
additional read memory references until the held particular
read memory reference therefrom is allowed to access said one
of said sections.
14. The system of claim 13, wherein the release conflict
resolution means in each processor further comprises read
subsection means in said each processor for receiving read
memory references generated by said at least one read port of
said plurality of ports which have proceeded through the
release conflict resolution means and for sending to one of
said sections a set of signals indicative of one of the
subsections therein to be accessed by one of the memory
references which has proceeded through said release conflict
resolution means, thereby causing data to be transferred to
the memory path between said one of said sections and said
each processor.
15. The system of claim 14, wherein the release conflict
resolution means in each processor further comprises write
reference mask means coupled to at least one write port of
said plurality of ports in said each processor for receiving
write memory references attempting access to said subsections
from the reference delay means, and for generating and holding
a write reference signal for each subsection to which access
is attempted by said write memory references until a
particular release subsection signal or a particular release
subsection pending signal has been received indicative of
whether one of said write memory references is allowed to
access one of said subsections, wherein the subsection
clearing means clears the corresponding subsection busy signal
in the subsection conflict means when the release subsection
signal or the release subsection pending signal is compared to
the write reference signals held in said write reference mask
means and indicates that said one of said write memory
references is allowed to access a particular requested bank in
said one of said subsections.

16. A method of memory access for sharing a memory
between a plurality of processors, each processor having a
plurality of ports for generating memory references, said
memory comprising a plurality of sections, each section
connected to each processor by a memory path, each section
including a plurality of subsections, each subsection
including a plurality of banks, each bank including a
plurality of individually addressable memory locations, said
method comprising the steps of:
generating a plurality of memory references by said
plurality of ports of said each processor attempting to access
individually addressable memory locations of said banks within
said subsections;
resolving subsection conflicts between said
plurality of memory references generated by said plurality of
ports of said each processor so that only one of the memory
references from said each processor is allowed to proceed to
attempt access to one of said plurality of subsections at a
time;
resolving section conflicts between said plurality
of memory references generated by said plurality of ports of
said each processor and which are allowed to proceed to
attempt access to said one of said plurality of subsections so
that only one of the plurality of ports of said each processor
connects via the memory path for said each processor to one of
said plurality of sections at a time; and
resolving bank conflicts between particular memory
references generated by said plurality of processor and which
are allowed to access to said one of said plurality of
subsections in said one of said plurality of sections so that
only one of said particular memory references accesses a
particular bank in said one of said plurality of subsections
at a time.
17. A method according to claim 16, wherein the step of
resolving subsection conflicts comprises the steps of.
receiving memory references generated by said
plurality of ports of said each processor;
31

tracking each subsection of said memory and
generating subsection busy signals indicative of whether said
each subsection is busy;
detecting if said memory references generated by
said plurality of ports of said each processor are directed to
subsections which are currently busy as indicated by said
subsection busy signals;
allowing one of said memory references generated by
one of said plurality of ports of said each processor to
access said one of said plurality of subsections if said one
of said plurality of subsections in not busy as indicated by
said subsection busy signals; and
resubmitting said memory references if they are
directed to subsections which are currently busy.
18. A method according to claim 17, wherein the step of
resolving section conflicts comprises the steps of:
receiving memory references generated by said
plurality of ports of said each processor and which are
allowed to proceed to attempt access to said one of said
plurality of subsections;
detecting whether two or more of said memory
references generated by said plurality of ports of said each
processor and allowed to proceed to attempt access to said one
of said plurality of subsections are attempting to
simultaneously access said one of said plurality of sections;
allowing only one of said two or more memory
references to access said one of said plurality of sections,
said one of said two or more memory references being the one
generated by one of said plurality of ports of said each
processor which has an access priority greater than the other
ports; and
resubmitting the memory references not allowed
access to said one of said plurality of sections.
19. A method according to claim 16, wherein the step of
resolving bank conflicts comprises the steps of:
receiving said particular memory reference;
32

tracking said plurality of banks of said one of said
plurality of subsections and generating bank busy signals
indicative of whether said banks of said one of said plurality
of subsections are busy;
detecting if said particular memory references are
attempting to access banks which are currently busy as
indicated by said bank busy signals;
holding said particular memory references attempting
access to banks which are currently busy and resubmitting said
particular memory references: and
allowing said particular memory references to access
said banks if said banks are not busy as indicated by said
bank busy signals.
20. A method according to claim 19, wherein said
resolving bank conflicts step further comprises the steps of:
detecting whether two or more of said particular
memory references are attempting to simultaneously access said
particular bank;
allowing only one of said two or more particular
memory references to access said particular bank, said one of
said two or more memory references being the one generated by
one of said plurality of processors which has an access
priority greater than the other processors; and
resubmitting the memory references not allowed
access to said particular bank.
21. A method according to claim 20, wherein said
resolving bank conflicts step further comprises the steps of:
generating subsection release signals for said particular
memory references allowed access to said one of said plurality
of subsections in said one of said plurality of sections
indicating that said memory references are allowed to access
said individual addressable memory locations of said banks.
22. A method according to claim 16, further comprising
the step of:
determining when a previous one of said particular
memory references has completed accessing said particular bank
33

so that said one of said particular memory references may
access said particular bank.
23. A method according to claim 22, wherein said
determining step comprises the steps of:
delaying said one of said particular memory
references until a time when a subsection release signal would
be received from said one of said plurality of subsections if
no bank conflict occurs and access to said individually
addressable memory locations is allowed and producing in
response thereto a delayed particular memory reference;
receiving said subsection release signal and said
delayed particular memory reference;
holding said subsection release signal as a pending
subsection release signal while aid one of said particular
memory references is being delayed;
comparing said delayed particular memory reference
with said subsection release signal and said pending
subsection release signal; and
clearing a subsection busy signal in response to a
match between said subsection release signal or said pending
subsection release signal and said delayed particular memory
reference indicating that said one of said particular memory
references is allowed access to said particular bank.
24. A method according to claim 23, wherein said
determining step further comprises the steps of:
receiving said delayed particular memory reference
from at least one read port of said plurality of ports as a
read memory reference;
comparing said read memory reference with said
subsection release signal and said pending subsection release
signal;
generating conflict signal if there is no match
between said subsection release signal or said pending
subsection release signal and said read memory reference; and
holding all other read memory references being
delayed in response to said conflict signal and shutting down
said at least one read port from generating any additional
34

read memory references until any held read memory references
are allowed access to a particular subsection to which they
are attempting access.
25. A method according to claim 24, further comprising
the step of:
controlling transfer of data from the memory to said
each processor when memory references generated by said each
processor are allowed access to a particular bank.
26. A method according to claim 23, wherein said
determining step further comprises the steps of:
receiving said delayed particular memory reference
from at least one write port of said plurality of ports as a
write memory reference:
comparing said subsection release signal and pending
subsection release signal to said write memory reference; and
clearing a subsection busy signal when said release
subsection signal or the release subsection pending signal
matches said write memory reference indicating that said write
memory reference is allowed to access said particular bank in
said one of said plurality of subsections.
27. A method according to claim 16, further comprising
the steps of:
allowing a plurality of read memory references from
at least one read port of said plurality of ports of said each
processor to access the memory in a non-sequential order: and
maintaining a sequential order for returning results
of said plurality of read memory references accessing the
memory to said at least one read port.

Description

Note: Descriptions are shown in the official language in which they were submitted.


1 323449
I
METHOD AND APPARATUS FOR SHARING MEMORY
IN A MULTIPROCESSOR SYSTEN
Technical Field of the Invention
The present invention pertains generally to the
field of multiprocessor computer systems and more
particularly to method and apparatus for sharing a memory
system between multiple processors.
Backaround of the Invention
In many cases the data processing speed of a
computer system can be greatly enhanced by providing one or
more additional processors to form a multiprocessor system
in which a common or central RAM memory is shared. However,
the sharing of resources, particularly the memory, results
in conflicts between the processors' various memory
reference requests, such that if ~he memory and the memory
access control logic is not properly designed much of the
potential increase in e~ficiency and economy of the system
~0 càn be lost to access delays.
Minimizing conflicts and delays in accessing a
shared memory is typically accomplished in two different ~ut
cooperative ways. One way is~to segment the shared memory
into many independently addressable banks such that each
reference to a bank ties up a relatively small percentage of
the memory, leaving the rest of the memory accessible~ Thls
approach, however, entails an increase in the complexlty and
- ': ~ : . ~ '
- . ~ . : : ,: , ,

1 3234~9
thus size and cost of the memory, and can also impose
limitations on the speed at which each reference may be
accomplished.
The other approach to minimizing memory reference
delays involves the interface between each processor and the
available memory access paths, and the treatment of
conflicting requests to memory either be~ween individual
ports in a processor or between different processors. As
may be readily appreciated, this approach must be
cooperative with the former approach 2S the design of the
interface must correspond to the number of independent
access paths between the memory and the processors.
Ideally, the memory interface should provide for
maximum utilization of the available memory access paths and
that each processor has substantially equal accessibility to
the memory at most times, particularly where there is no
master-salve relationship between the processors. In
additionj it is desireable that memory conflict be resolved
in as few systems clock periods as possible so that
~0 reference start up time and data buffering reguirements are
held to a minimum. The attainment of these goals is,
however, restrained by the cost and particularly the
quantity of logic which may be employed. In particular, in
the case of high-speed vector processing machines there are
~5 tight restrictions on the space which may be allotted to
' .
- . ` . ' ' ' ' ~ -,
'' ` '
,.. ::. . . :

. 1 323~49
interface circuits due to the necessity to bring all
processoxs into close proximity to the memory in order that
propagation delays be minimized. In addi~ion, it is
desireable that wiring requirements be held down.
~s is well appreciated by those skilled in the
art, attaining an efficien~, economical and workable memory
interface becomes increasingly difficult as the number or
processors is increased. Those designs which may be quite
efficient in a dual or 4 processor system may be totally
unsuitable for systems with more processors because of the
increases in logic wbich are needed to adapt such schemes to
a largsr number of processors, and the additional demands
made on the memory by the additional processors. Moreover,
increasing the number of processors typically increases the
nominal distance between a given processor and the memory,
increasing signal propagation delay and placing further
restraints on the number of logic levels which may be
employed.
Accordingly, it is readily seen that the system
used to share memory in a multiprocessor system is crucial
to its effiaiency~ Moreover, it is readily seen that there
are not only a large number of constraints on the design of
such systems but in addition that these constraints often
work against one another to represent a difficul-t~design
~5 challenge.
:
.

- 1 323449
-- 4 --
Summary of the Invention
The present invention provides a memory access
system for sharing a memory be~ween multiple processors.
The invention calls for a plurality of processors each
including two or more ports for generating memory references
to a shared memory. The shared memory has a plurality of
~ections each including a plurality of subsections, with
each subsection including a plurality of banks.
Individually addressable memory locations are located in the
banks. A memory path is provided from each processor in
each section of memory. The invention provides first means
for each processor for ar~itrating conflicts between ports
and a processor attempting to access the same section to
memory, and for connecting a port to the path. The first
means also prevents more than one port in a given processor
from accessing the same subsection of said memory at the
same time. Second means is provided for each said
subsection to memory for arbitrating conflicts between
processors attempting to access the same bank within a said
subsection at the same time and for providing a path to a
bank within a subsection from`a memory path so that only one
re~erence per processor can occur in a subsection at a time.
The invention further provides reference output means for
connecting a bank to a said path so that the contents of a
me-ory location can be returnod to a sa_d proc~esFor.
. . ., , . .. ... ~, . . . . . .. . .

1 3234~q
According to another aspect of the invention, at
particular one of said ports of a particular processor can
issue a plurality of memory references each to a different
subsection of,memory. Said second means for each said
subsection of memory permits said plurality of references to
access said memory locations in a sequence which is out of
the order in which said plurality of references is generated
by said pàrticular port. Said reference output means
includes resynchronization means for preventing memory
refe~ences from said particular port from being returned to
said particular processor out of the order generated by said
pa~ticular port. Said resynchroni~ation means further
includes register means for holding the con~ents of a said
memory location read out of a said subsection until said
resynchronization means permits the contents of said memory
location to be returned to said particular processor.
According to yet another,aspect of the invention,
a method of memory access provides for the sharing of memory
between a plurality of processors each including two or more
~0 ports for generating memory references, wherein said shared
memory includes a plurality of sections each including a
pluralit~ of subsections. Each said subsaction includes a
plurality of banks, with each bank including indlvidually
addressable memory locations. The method provides a memory
path between each said processor and each said sectlon of
.
I
` ;`
.

1 323/~9
-- 6 --
memory, and a regis~er within each said section for each
said processor.so that each said processor has a
corresponding register.in each said subsection-of memory.
The method-~-urther comprises. sending a reference from a
S particular port in a particular processor to a part-icular
subsection of~memory to.~the register in said particular
subsection corresponding to said particular.processor, and
for preventing any further references sent to particular
sùbsecti~n from saiA-particular processor until said
particular reference has been completed.
` According to yet another aspect of the method
according to the present invention, there is generated a
plurality of references from said particular por~ to
different subsections of memory, and said plurality of
xeferences are accomplished in said subsections of memory
without regarding to the order in which they were generated
~rom said particular port so that the memory locations ~eing
re~erenced can be read out asynchronously with respect to
said order. The method further includes a step of
reordering said plurality of references once they have beèn
read out of said memory locations and returning the contents
of said memory locations to said particular processor in the
same order the references were generated.
::
:
: . ,

1 3234~9
Brief Description of the Drawinq
. Figure 1 is a simplified block diàgram of the
connection of the CPUs to the memory according to the
present invention;
- 5 Figure 2 is a simplified block diagram showing
connection of one CPU to each of the sub-sections of a
section of memory;
Figure 3 is a simplified block diagram showing the
connection of one CPU to one of the sub-sections in greater
detail;
~igure 4 is a simplifisd block diagram of the
basic structure of each of the sub-sections of memory;
Figure 5 is a simplified block diagram of a sub-
section conflict resolution circuit as provided for each CPU
in the system;
Figure 6 is a simplified block diagram of a bank
conflict resolution circuit as found in each sub-section of
memory; and
Figure 7 is a simplified block diagram of the
~0 release conflict circuit provided for each CPU.
,
Detailed Description of the Invention
The present invention relates to a system for
interfacing a plurality of CPUs to a central or shared
memory. In particular, the invention:is tallored for a
,

1 323~4q
multiprocessor system in which each processor is capable
of generating memory references from several independent
ports each of which may operate substantially
independently of the CPU to carry out data and
instruction transfers. An example of a CPU of the type
of which the present invention is adapted to interface
to a memory is shown in U.S. Patent No. 4,661,900 to
Chen et al., entitled "FLEXIBTT~' CHAINING IN A VECTOR
PROCESSOR". As shown in Figure 1, the present invention
is specifically designed for a multiprocessor system 10
having eight CPU's. It shall be understood, however,
that the principles of tha invention can be applied to
multiprocassor systems having a greater or lesser number
o~ cPus.
Memory 12 of system 10 is organized into four
sections. Each of the CPUs is connected to each of
these sections through a memory path 14. Each path 14
consists of the following:
72 Bits Write Data
20 Bits Address (32 million word memory option)
8 Bits Go Sub-section
1 Bit Write Reference
1 Bit Abort Reference (Address Range Error)
72 Bits Read Data
3 Bits Sub-section Read Select
Each addre~s is configured as follows:
Chip
Address ~ /su2b22s3e4ction\~ k ~ aAdd
- . . . .
, - :
, ` ' : . : ` ~ ' `
,` , ~ ` ,
. :

1 323449
The 72 bits of Write Data of path 14 comprise the
data to be written from a CPU to the memory. The eight Go
Sub-Section-signals indicate whiGh-of the eight Sub-Sections
within each memory section the reference is to. ~s
indicated above, the section ~o which a reference is
directed is controlled by the first two bits of the address.
These two bits determine which of the paths 14 the reference
will use to access the proper section of memory. As will be
qescribed below, internal to each CPU represented in Figure
l are a plurality of reference generating ports, any one of
which can be connected to any one of the four paths 14
between each CPU and the respective sections of memory 12.
The Write Reference signal on path 14 indicates whether the
reference is a write or a read reference. The Abort
Reference signal is also provided, and provides that a
reference may be aborted if an address range error is
detected by range checking circuits in the CPU's memory
reference generation circuits (not shown). The seventy-two
bits of read data are provided on each path 14 carry data
rom the memory to the CPU. Finally, three bits of Sub-
section Read Select Data is also provided. Further
information on the organization of memory 12 will be
provided below.
The system 10 as generally outlined above thereby
provides that one read or write reference can bo made every
'. ,.
. - '' '` ": ~ ' ' ' :
': ' ' ' ' ' ' ''

1 323~4q
-- 10 --
clock period on each path 14. Therefore, the system memory
is capable of 32 references per clock period. Figure 2
shows `that each se~t:ion of memory is organized into eight
sub-sections (0-7):-20. Each CPU is-connècted to each one of
the sub-sections 20 via one of paths 14-, each of which is
connected in parallel to each of the-sub~sections.
Figure 3 shows in more detail how each path 14 is
connected to each of the sub-sections 20, using the example
of the connection of CPU 0 to sub-section-0 of one of the
memory sections. Input logic 30 includes a first latch 32
to receive the 72 bits of Write Data from connection 14. A
latch 34 receives the Section Address from connection 14. A
latch 36 receives as input the Write Reference signal and
the Abort Reference signal.
Each of latches 32, 34, and 36 are clocked by the
Go Sub-Section 0 signal. As mentioned above, this Go Sub-
Section 0 signal is one bit of the 8 Go Sub-Section bits
càrried on connection 14 and indicates which sub-section
~ithin a section of memory the reference carried on a path
~0 `14 is directed to. When latches 32 and 34 are clocked ~he
Write Data and Section Address are passed through to the
bank select circuits 50 to be described below. In addition,
the Write Reference signal from latch 36 is passed to the
reference control circuits 40, which control the generation
of the signals necessary to actually reference the memory at
. .
` ~ `` `, ;
:
.
':' : '

1 323~4~ :
11 --
the chip leval, which can be carried out in a conventional
fashion. Reference control 40 is connected to control read
data latch 38 which receives Read Data coming out of the
memory. Latch 38 is connected to an 8-to-1 multiplexer 42
which selects between the read data latches for each of the
circuits 30 used in one of ~he sections. The Read Data
selected by multiplexer 42 is passed back along path 14. The
multiplexer selection in multiplexer 42 is controlled by the
three bits of sub-section Read Select Data carried on the
path 14. The operation of this aspect of the invention will
be described in more detail below.
Referring now to Figure 4, there is shown a
simplified block diagram o~ one sub-section 20 of memory 12.
Each of the sub-sections includes eight banks of memory
organized in a interleaved fashion. For instance, the sub-
section 0 illustrated in Figure 4 includes banks 0, 32, 64,
96, 128, 160, 192 and 224. The banks are similarly
interleaved among the other sub-sections such that sub-
section 0 of memory section 1 would include banks 1, 33, 65,
~0 97, 129, 161, ~93 and 225 and so on for each successive sub-
section of memory progressing from section 0 to section 3.
Accordingly, memory 12 includes a total of 256 banks of
memory.
Each of the banks 52 of memory contains a number
of individually addressable memory location.s each with its
, , .

~ 32344q
- 12 -
own unique address. Each bank may function independently of
the others and can be referenced individually and/or
simultaneously with another bank within the same sub-
section. However, although different banks may be assessed
or referenced simultaneously, the present invention
contemplates that no one bank may be referenced more than
once every five system clock cycles, due to the recovery
time of the memory. The memory is preferably constructed
with 64K x l ECL chips available from Fujistu Electronics of
Japan and its U.S. agents.
Figure 4 shows that each of circuits 30 (as
illustrated in Figure 3) for each of-CPUs 0-7 are connected
to each of the bank select multiplexers 54, whereby each CPU
may access any one of the eight banks 52 within the sub-
section. Bank select multiplexers 54 further provideconnections for the Read Data outputs of banks 52 to read
out registers 38 of circuit 30, one of which is provided for
each of the CPUs.
Thus, as outlined above, there is ~rovided a
~0 me~ory access system wherein a CPU may generate a reference
to any one of the four sections of memory and any one of the
sub-sections and banks within each one of these sections.
Since more than one CPU may request a reference to the same
bank within any one of the sub-sections, there is provided
bank conflict checklng circuits 60 in each sub-sectlon to
.
., , ~
, . . . . .
- . ' , ' ' " ' ' .. ' ` , , ~ . , ' , '

1 323449
- 13 -
detect and arbitrate these conflicts. Conflict checking
circuits 60 are shown generally in Figure 4 and in more
detail in ~igure 6. As-shown in Figure 4, conflict checking
circuit 6n is interfaced wi~h reference control-circuit 40,
the-multiplexers 54 and the read out register 30 wherein
references to the banks within each sub-section are
controlled.
Referring now to Figure 5 there is shown in
simplified block diagram a sub-sectio~ conflict circuit 80.
Each CPU includes one circuit 80 to control the references
generated by the reference generating circuits ~82) of the
CPU. Each memory reference generation circuit, or "port",
includes, for instance, an input gate 84 and register 86 for
receiving and holding a base address. -A gate 88 and
lS register 90 may be provided to receive and hold an address
increment. An add circuit 92 is provided to add the base
address 86 to the increment 90, submit it to the reference
address register and return it to gate 84 to be resubmitted
~o base address register 86. As shown in control circuit
~0 100, there is preferably provided a block length register
102 ~hich is initially loaded with the length of the
intended reference and which is decremented once after each
reference until the register zeros out indicating that the
reference has been completed. Reference address register 94
passes the first 5 bits 2-24 of the memory reference

1 323449
- 14 -
address to the corresponding one of ~ates 110, one of which
is provided for each of memory reference generating circuits
82. The outpu~ of gates 110 are connected to one of sub-
section conflict detection circuits.112,.each of which are
in turn connected to a section conflict detection circuit
114. .Sub-section confLict.detection circuits 112 and
section conflict circuit 114 permits circuit 80 to detect if
a reference generated.by the CPU is directed to a sub-
section within.memory.12 which is currently busy processing
a reference previously generated by the same or a different
port within.the CPU. If such is the case, circuits 112
generate a sub-section conflict signal to the corresponding
- one of conflict.resolution circuits 115. Similarly,
attempts by more than one port to access the same section of
memory at the same time are detected by section conflict
checking circuit 114, which provides an output to each of
conflict resolution circuits 116. As noted above, since
there is only one input circuit 30 for each CPU in each sub-
section of memory no more than one reference to that input
~0 circuit at any time can be permitted from a CPU. SimilarIy
since there is only one path from each CPU to each section
of memory only one reference per section of memory can be
permitted from each CPU. Accordingly, conflict resolution
circuits 116 provide that these conditions are met.
-
~: :
,

1 323~49
To this end, conflict resolution circui's 116 provide
that each reference generated from a port in the CPU is
first checked to see whether or not it is attempting to
access a busy sub-section, as tracked by sub-section busy
circuit 120. Sub-section busy circuit 120 receives an input
from each of conflict resolution circuits 116 so that it can
keep track of which of the sub-sections are busy. If a sub~
section is busy, the sub-section identifying bits of the
address 2-24 are resubmitted-to the gate 110 over
connections 124, and reconsidered in this fashion until
allowed to proceed. Likewise, references which have a
section conflict are also resubmitted. If a reference is
permitted to proceed, the address bits 2-24 are forwarded
through a two CP delay circuit (not shown) along to the
release conflicts 146-149 of Figure 7.
Section conflict checking circuit 114 chec~s for
and prioritizes attempts to access the same section of
memory simultaneously. If more than one reference has a
simultaneous reference conflict without a sub-section busy
con~lict, the conflict is resolved as follows. First, if
the references each have the same increment (i.e. whether
odd or even addressing increment) the first port to initia~e
the reference has priority. An odd address increment always
has highest priority over an even increment. However, in
the case of port D, where a reference is an I/O reference,
,
~: ' ' ' "
:' : . '

1 3234~9
- 16 -
the port always has lowest priority unless 32 consecutive
conflicts occur; in which case the port is switched to
highest.priority. Xowever, if port D is doing an
instruction fetch,.it is gi~en.~he.highest.pEiority in all
cases. Once a reference is allowed through the subsection
confl ct checkj-.it.is transmitted on path 14 to the bank
conflict check of.Figure 6.
The output of conflict circuits 116 are fed to
section select circuits 117, which select which port will
access a given memory path 14, as controlled by the section
conflict circuit 114 and the section to which the reference
is directed as determined by.the address.
Referring now to Figure 6, there is shown in block
diagram form one of the bank conflict checking circuits for
one of the sub-sections. Each of the bank conflict checking
circuits 60 includes an input register 62 for each of the
CPUs 0-7. Bach of the register 62 receives the 3 bits of
the address data t25-27) which specify the bank within the
sub-section to which the reference is addressed. Bank
~0 conflict checking subcircuits 64 are provided to determine
for each reference from a CPU whether or not the bank sought
to be referenced is currently busy. For this purpose there ~ :.
is provided a bank busy circuit 66 which keeps track of
which banks of the sub-section are currently busy making a
reference. The output of bank busy circuit 66 is connected
-

1 323449
to each of bank conflict circuits 64 whereby each of them
can determine whether or not a refexence held in a register
62 has a conflict. If a conflict is detected, it is
indicated to the corresponding conflict resolution circuit
70. Each of conflict resolution circuits 70 also receive an
input signal from the simultaneous bank conflict resolution
circuit 72, which iden~ifies simultaneous attempts by two or
moxe processors to access the same bank of memory on the
same clock period.
If a conflict is detected by either a bank busy
circuit 64 or simultaneous bank conflict checking circuit 72
the conflict resolution circuits 70 are called into play to
resolve the conflict. A conflict is resolved either by
holding a reference attempting to access a busy bank (banks
are held busy for five clock periods), as in the case of a
bank busy conflict, or by holding all but one of references
attempting to access the same bank simultaneously on the
sama clock period.
If a simultaneous bank conflict is detected by
~a circuit 72, conflict resolution circuits 70 determine which
refexence will proceed first.` The priority of references is
fixed for each sub-section according to which section and
subsection is being referenced. From the predetermined CPU
path, the memory control determines which CPU has the higher
priority. As set forth in the table below, the priority is
,:

. ~ 323~9
- 18 -
such that a CPU with a CPU A reference has the highest
priority while a CPU with a letter CPU H would have the
lowest priority. The table shows the CPUs letter
reference.
CPU TO MEMORY PRIORITY TABLE
_ ..
Section O 1 2 3
_ __ _
O 2 O 2 O 2 O 2
Subsection 1 3 1 3 1 3 1 3
5 6 5 6 s4 6 4 6
_ . .
Q A H D E C F B G
O _
1 B G A H D E C F
. ___ _ _
C 2 C F B G A H D E
P _ _
U 3 D E C F B G A H
_ _ __ _ _
4 H A E D F C G B
P _ _ _ _
~ 5 G B H A E D F C
T __ _ _ _
H 6 F C G B H A E D
_ ._ _ _.
l 7 E D F C G B H A
351 _ _ _ _ _ _ -
For example, if CPU 3 went to Section 1, Subsection 5,
its CPU letter reference would be CPU C when competing for
~0 any of the banks in Subsection 5. This means any reference
from CPU A or CPU B for the same bank as CPU C wanted would
cause CPU C to wait. As will be recognized by those skilled
.'.~-:
,
- . .,
: : . ` ` ~ ' ' : :

~ 323449
- 19 -
in the art, the priority sy-stem-outlined above can be
achieved with a single priority circuit design by merely
changing the wiring of the CPU memory paths to subsection
circuits. `-^ - - - -
If a reference is held, conflict resolution circuit 70
resubmits the reference to the originating input register 62
via signal path 74 so that the reference can be reconsidered
on succeeding clock cycles. If no conflict is detected, a
Sub-Section Release signal (SS Release) is generated by the
conflict resolution circuit 70 coxresponding to the
originating register 62 to indicate that the reference being
attempted can proceed. This Sub-Section Release signal is
fed to the reference control circuit 4Q (Fig. 4) to
accomplish a memory reference in the banks. Conflict
resolution circuits 70 generate an output signal fed to
selec~ control-signal circuits 71, which generate the
signals necessary to control multiplexers 54. Accordingly,
it may be seen that no more than one reference can be issued
to any bank within a sub-section at a time. Preferably it
~0 is desirable to physically locate the circuit of Figure 6
close to or in the subsection it handles.
Referring now to Figure 7, there is shown one of the
release conflict circuits 140 of CPU's 0-7. A release
conflict circuit 140 is provided for each CPU. Release
conflict circuit 140 includes four lnput registers 146-14g

1 323~49
- 20 -
each of which receive at their respective inputs memory
address bits 2-24 as generated from circuit 80 of Figure 6.
These address bits are delayed two clock periods from when
they are generated from circuit 116 to when they are applled
to circuits 146-149. This delay corresponds to the minimum
amount o~ me req~red--for--a referenc~--w~ich is all-owed by
- the sub-section-conflict circuit to clear the bank conflict
circuit in Figure 6 if no conflict occurs. This 2 CP delay
plus circuits 116, 146 and 170 matches the 5 CP bank busy
reference cycle time.
--- Release confli~t-ci~reuits 160--163 are provided and are
connected to the respective outputs of-circuits 146-150.
Circuits 160-163 ~ook for a subsection release signal to
match-a reference--indicat-ed-in-circuits 146-150. Circuits
160-163 can look-to release pending-reference regis-ter 152
or to sub-section release signals arriving on signal path
165.
The release pending reference logic 152, holds a copy
of all subsection release signals, that were received on
path 165, which did not match a referance in cixcuits 146-
150. Thesa sub-section release signals are held until a
reference in 146-150 does match at which time corresponding
pending releasa is cleared.
Circuits 160-162 are connected to conflict resolution
~5 circuits 170-172, respectively. If a reference arrives at a
,,
: ,
' '. ' ' ' , ` '~ ` `

1 323~`9
- 21 -
register 146-148 and does not match a corresponding SS
release signal, circuits 170-172 generate a release conflict
signal which is applied to circuit 80, which forces a
conflict in conflict circuits 112 (Fig. 5), which in turn
shuts down the corresponding port. This conflict also holds
all references in the 2 CP delay circuit (not shown) and in
the corr sponding one of 146-148 and resubmits the reference
in 170 through 180.
If a match occurs in more than one of circuits 160-162
for read references, then section conflict circuit 175
determines if those read references are to the same section.
If more than one cf those read references is to the same
section, then all but one port will generate a release
conflict at 170-1~2. The priority in A is highest if B and
D did not have section conflicts the previous CP. B is
highest if it had a section conflict the previous CP and D
has not had 2 CP of section conflicts. D lS highest if it
has had 2 CP's of section conflict.
Circuit 150, port C sub-section reference mask,
~0 contains 32 latches corresponding to each of the 32 sub-
sections. If a reference arrives at registex 149 and does
not match a corresponding SS release signal, the
corresponding latch in 150 is set. Circuit 163 compares the
SS release t165) and release pending (152) signals to the -
~5 reference in 149 and to the reference mask 150.
', , ` :

1 3234~
- 22 -
The four references in a port "pipeline" ~either A, B
or D) can receive SS releases non-sequentially but then will
be matched up with their corresponding release sequentially
as each reference passes through 146-148 thus maintaining a
seguential order for read references. Port C is write only
and therefore no sequential order of completion is
necessary. Therefore SS reference mask 150 is used instead
of a release conflict to merely keep track of which
references are pending. Release sub-section control
circuit 142 produces a release sub-section signal to each
one of the eight sub-sections within the four sections of
memory, for a total of 32 release sub-section signals. Nhen
a match between a re~erence and a release occurs in 160-163/
the circuit 142 generates the appropriate release SS. These
signals are applied to the sub-section checking circuit 120
(Fig. 5). These signals clear the subsection busy signal
which is set by the CPU when the CPU makes a reference to
the subsection, and signify that the reference has been
checked by the bank conflict circuit and was allowed to
proceed in the subsection. The CPU is thus permitted to
issue another reference to the cleared subsection. Circuit
142 also generates the SS read select signals for each
section for a read reference when the release SS is
generated.
-:

1 ~234~9
- 23 -
Although the invention has been described herein in its
preferred-form, those skilled in the art will readily
recognize that various modifications and changes may be made
thereto without departing -from the spirit and scope of the
claims appended hereto. :
. .
,
.
: ~ : .

Representative Drawing
A single figure which represents the drawing illustrating the invention.
Administrative Status

2024-08-01:As part of the Next Generation Patents (NGP) transition, the Canadian Patents Database (CPD) now contains a more detailed Event History, which replicates the Event Log of our new back-office solution.

Please note that "Inactive:" events refers to events no longer in use in our new back-office solution.

For a clearer understanding of the status of the application/patent presented on this page, the site Disclaimer , as well as the definitions for Patent , Event History , Maintenance Fee  and Payment History  should be consulted.

Event History

Description Date
Inactive: Adhoc Request Documented 1996-10-19
Time Limit for Reversal Expired 1996-04-21
Letter Sent 1995-10-19
Grant by Issuance 1993-10-19

Abandonment History

There is no abandonment history.

Owners on Record

Note: Records showing the ownership history in alphabetical order.

Current Owners on Record
CRAY RESEARCH, INC.
Past Owners on Record
ALAN J. SCHIFFLEGER
Past Owners that do not appear in the "Owners on Record" listing will appear in other documentation within the application.
Documents

To view selected files, please enter reCAPTCHA code :



To view images, click a link in the Document Description column. To download the documents, select one or more checkboxes in the first column and then click the "Download Selected in PDF format (Zip Archive)" or the "Download Selected as Single PDF" button.

List of published and non-published patent-specific documents on the CPD .

If you have any difficulty accessing content, you can call the Client Service Centre at 1-866-997-1936 or send them an e-mail at CIPO Client Service Centre.


Document
Description 
Date
(yyyy-mm-dd) 
Number of pages   Size of Image (KB) 
Claims 1994-03-08 12 584
Abstract 1994-03-08 1 28
Drawings 1994-03-08 6 183
Cover Page 1994-03-08 1 14
Descriptions 1994-03-08 23 793
Representative drawing 2002-04-30 1 12
Examiner Requisition 1992-11-24 1 52
Prosecution correspondence 1993-03-24 4 96
Prosecution correspondence 1993-04-08 5 131
Prosecution correspondence 1993-05-05 1 29
PCT Correspondence 1993-07-14 1 32
PCT Correspondence 1993-02-03 1 23