Electrical computers and digital processing systems: multicomput – Multicomputer data transferring via shared memory
Reexamination Certificate
1999-01-25
2001-06-05
Decady, Albert (Department: 2133)
Electrical computers and digital processing systems: multicomput
Multicomputer data transferring via shared memory
C709S214000, C709S230000
Reexamination Certificate
active
06243742
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates generally to methods and apparatus for facilitating efficient communication in a computer network. More specifically, the present invention relates to improved techniques that permit nodes of a computer network to access the networks's distributed shared memory in an efficient manner.
Computer networks having distributed shared memory (DSM) are known in the art. For discussion purposes,
FIG. 1
illustrates a computer network
10
having a network infrastructure
12
(NI). Four network nodes
100
,
102
,
104
, and
106
are shown coupled to network infrastructure
12
. Through network infrastructure
12
, nodes
100
-
106
may communicate among one another to share programs, data, and the like. Of course, the number of nodes provided per network
10
may vary depending on needs, and may include any arbitrary number of nodes.
Within each network node, there exists a memory space, typically implemented in a memory module, whose memory blocks may be accessed by other network nodes. In general, each memory block in the network has an unique address that allows it to be uniquely addressed. The union of all memory blocks in the nodes of network
10
comprises the distributed shared memory (DSM). It should be noted, however, that although the memory blocks of the DSM may be accessed by any network node, a given memory block is typically associated with some home node in network
10
.
For the purposes the present invention, network infrastructure
12
may have any configuration and may be implemented by any protocol. Generally, network infrastructure
12
possesses the ability to correctly deliver a message from one node to another according to the destination address associated with that message. One exemplar network infrastructure is Sequent Numa-Q, available from Sequent Computer Systems, Inc. of Beaverton, Oreg.
Each of network nodes
100
-
106
may be as simple as a computer having a single processor that is coupled to its own memory via a memory cache. A network node may also be as complicated as a complete bus-based multi-processor system or even a multi-processor sub-network. In the latter case, a node may include multiple processors, each of which is coupled to its own memory module and memory cache, as well as to the distributed shared memory distributed among other nodes in the network. For ease of illustration, the invention will be described herein with reference to nodes having a single processor. It should be apparent to those skilled in the art given this disclosure, that the principles and techniques disclosed herein are readily extendible to nodes having multiple processors.
In the prior art, the network nodes typically communicate among themselves using a bus-based approach or a directory protocol. By way of example,
FIG. 2
is a schematic of a computer network, including exemplar nodes
100
a
and
100
b,
for implementing one version of the prior art bus-based protocol. In node
100
a
of
FIG. 2
, processor
200
a
is coupled to a memory module
204
a,
e.g., a dynamic random access memory module, via a memory cache
102
a,
which is typically implemented using some type of fast memory, e.g., static random access memory (SRAM). Memory module
204
a
may be divided into memory blocks, and memory cache
202
a
serves to expedite access to the memory blocks of memory module
204
a
by holding a copy of the requested memory block, either from its own node or another node in the network (such as node
100
b
), in its fast memory circuits. Through a network interface (included in each node but not shown to simplify illustration), node
100
a
may communicate with node
100
b
as well as other nodes in the network via a bus-based network infrastructure, e.g., bus
206
, to gain access to the distributed shared memory (DSM), which is distributed in the nodes of the network.
In a bus-based computer network, a memory request by a given node is typically broadcasted on the common bus to other nodes so that the request may be seen by all other nodes in the network. For example, if processor
200
a
of
FIG. 2
needs to access a memory block residing in another memory module of another network node, it typically broadcasts on the common bus its memory access request. All the nodes on a network would receive the same request, and the node whose memory address ranges match the memory address provided in the memory access request then responds.
This broadcast technique works adequately for relatively small computer networks. As computer networks grow larger and/or become more physically dispersed, the bus-based approach has several difficulties. For example, as the bus grows larger to accommodate more nodes, it is desirable to operate the bus at a higher speed since each node generally needs to access the bus for a period of time to execute its transactions. Operating a large bus at a high frequency is difficult because as busses become larger, they become electrically longer and electrical concerns, e.g., capacitance, may substantially limit their operating frequency. Consequently, the bus-based approach is generally unsuitable for large or physically dispersed computer networks.
Further, a bus-based protocol requires the provision of an arbiter circuit to enforce a natural ordering of transactions by the various nodes of the computer network. The arbiter needs to ensure that bus access requests from the various network nodes are properly ordered to avoid race conditions. The use of arbiter circuits and an arbitration scheme represent an additional layer of complexity, thereby adding to the expenses in the creation and maintenance of computer networks.
As can be appreciated by those skilled in the art, the extra messages that need to be sent in a bus-based system from the requesting node to all the nodes in a network represent an extra burden on the bus. Further, the requesting node must poll every node in the network and require each node to analyze the request to either ignore the request, or to respond. The extra work required of the other nodes in the network represents extra delay and additional processing that the network nodes must perform.
The directory protocol represents an attempt to implement a computer network in which natural broadcast is not necessary to service memory access requests, i.e., a transaction or a request from a node does not need to be broadcasted to all other nodes in the network.
FIG. 3
illustrates, for discussion purposes, a computer network node
100
suitable for implementing the directory protocol. In every node of the computer network employing the directory protocol, there may be provided a directory containing directory entries for the memory blocks of its memory module. With reference to
FIG. 3
, there is shown a directory
210
which may be implemented as a data structure in memory and contains directory entries, each of which correspond to a unique memory block of the memory module in node
100
. For example, there is shown in directory
210
a directory entry
212
, which corresponds to a memory block
208
in a memory module
204
. The union of all directory entries in a given node represents the directory for that node. There is also shown in
FIG. 3
an interface
206
, representing the circuit for connecting a node to its outside world, e.g., to the network infrastructure.
In the directory protocol, each node in the network, e.g., each of nodes
100
-
106
, must know whether it has an exclusive copy of a block of memory (a modifiable or M-copy), a shared, read-only copy (a S-copy), or it does not have a copy (an invalid or I-copy). When a node has an M-copy of the block, it is said to have an exclusive copy and can modify this copy to cause it to be potentially different from its counterpart in memory module
204
of the block's home node. When any node in the computer network possesses an M-copy of memory block
208
, all other nodes give up their copies, i.e., possessing only I-copies of that memory block.
Whereas only one node may have an M-copy of a memory
Hagersten Erik E.
Hill Mark Donald
Conley Rose & Tayon PC
De'cady Albert
Kivlin B. Noäl
Sun Microsystems Inc.
Ton David
LandOfFree
Hybrid memory access protocol in a distributed shared memory... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Hybrid memory access protocol in a distributed shared memory..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hybrid memory access protocol in a distributed shared memory... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2499849