Cache coherence unit with integrated message passing and memory protection for a distributed, shared memory multiprocessor system

[0002] This application is related to co-pending application Ser. No. 09/003,771, filed Jan. 7, 1998, entitled, “Memory Protection Mechanism for a Distributed Shared Memory Multiprocessor With Integrated Message Passing Support,” by inventors Wolf-Dietrich Weber and Jaspal Kohli, to common assignee.

[0003] 1. Field of the Invention

[0004] The present invention relates generally to computer communication protocols, and more specifically to an integrated protocol that supports both shared memory cache coherence and protected shared nothing message passing.

[0005] 2. Description of Background Art

[0006] One class of multi-processor data computer system consists of a plurality of processor nodes communicating over a high-speed interconnection. Each processor node typically includes a processor and local Random Access Memory (RAM). A computational problem may be divided among processor nodes to use the particular resources available at different processor nodes or to reduce the real time needed to produce a result and thereby expedite the computation. Hence, a process running on one processor node may depend on computations being performed at other processor nodes in the computer system. The various processes communicate over the interconnection to exchange information and synchronize the processes.

[0007] There are two major multiprocessor programming paradigms that differ by how the processors communicate with one another. The shared memory paradigm allows all processors to access all memory in the entire machine. Processors communicate with each other by one processor writing a value to a given memory location and another processor reading that value from the same memory location. In contrast, in the shared nothing (or message-passing) paradigm, each processor can only access its own memory, and communicates with other processors by explicitly building messages and sending them to the other processor. Both programming paradigms have their relative merits and both are used. An advantage of the shared-memory paradigm is that it offers more efficient communication, whereas an advantage of the shared-nothing paradigm is that it offers greater protection of one process from all other processes.

[0008] Prior art systems usually allow only one or the other programming paradigm. If both are allowed, then they are usually supported over two different types of interconnects, usually a high-performance interconnect for shared memory and the associated cache coherence protocol, and a lower-performance interconnect for message-passing.

[0009] The objects of the present invention include the integration of a shared memory cache coherence protocol and a shared nothing message passing protocol onto the same high-performance interconnect and to raise protection boundaries between processors not sharing memory while allowing complete access to processors sharing memory.

[0010] The invention resides in a system and method for a message passing protocol to extend cache coherence management of scalable shared-memory multiprocessing computer systems. The scalable shared-memory multiprocessing computer system has a plurality of processors connected to an interconnection over which the processors communicate between themselves. The interconnection processors use a communication protocol which is adaptable for shared-memory computer systems, shared nothing computer systems, and hybrid computer systems in which some processors share memory while others do not, to send and receive messages on the interconnection. For hybrid computer systems it is important to raise protection boundaries between processors not sharing memory while allowing complete access to processors sharing memory. A processor node is able to tell whether an incoming message is from within the same coherence group (in which case it is completely unprotected) or is from outside the coherence group (in which case the shared-nothing protections apply). This allows processor nodes sharing memory and processor nodes sharing nothing to co-exist on the same interconnection. This is achieved by using node identification numbers (NIDs), coherence node numbers (CNNs), and a mapping between them. Each processing node in the system is given a NID. Nodes in a set which will share memory are each assigned a CNN and agree on a consistent mapping of CNNs to NIDs. With this mapping a processor node is able to tell whether an incoming message is from within the same coherence group (in which case it is completely unprotected) or is from outside the coherence group (in which case the shared-nothing protections apply). This allows processor nodes sharing memory and processor nodes sharing nothing to co-exist on a common interconnection.

[0011] These and other objects and advantages of the present invention will become apparent to those skilled in the art from the following detailed description of the invention and the accompanying drawings.

[0012] FIG. 1 is a functional block diagram of a computer system having multiple processor nodes according to the present invention;

[0013] FIG. 2 is a functional block diagram of an example of a processor node from FIG. 1 which includes a memory subsystem, an input/output subsystem, a Mesh Coherence Unit (MCU) and processors having respective caches; and

[0014] FIG. 3 is a block diagram of a Mesh Coherence Unit.

[0015] The present invention resides in a system and method for integrating a message passing protocol and the required protection boundaries into a scalable shared-memory multiprocessing computer system. A scalable shared-memory multiprocessing computer system has a plurality of processors connected to an interconnection over which the processors communicate with each other. The traditional mechanism by which a message is passed via an input/output channel and an interconnection. In contrast, the present invention uses the same communication channel, an interconnection, for both cache coherence and message passing, which significantly increases the rate at which messages may be exchanged. Each processor communicates with other interconnection processors by sending and receiving messages using a messaging protocol that is tightly integrated with the inter-processor node cache coherence protocol.

[0016] FIG. 1 is a functional block diagram of a computer system 100 according to the invention, including multiple processor nodes 102a-tand a processor node interconnection 104 which provides point-to-point communication between the connected nodes. Each of the processor nodes 102a-tmay be configured as a stand-alone computer system or be configured in combination with other processor nodes to form a computer system in which the processor nodes share memory. The term “site” is used to designate a group of processor nodes sharing a physical address space in memory. Selected processor nodes 102a-d,102f-i,102l-o,and 102q-tare respectively configured as sites 106a,106b,106cand 106d.Other processor nodes 102e,102j,102k,and 102pare also connected via interconnection 104, but do not share memory. Processor nodes in different sites communicate via message passing. For example, processor nodes in site 106acan communicate with processor nodes in other sites, e.g., processor node 102nin site 106c,by sending messages via interconnection 104. Each site typically runs a single copy of an operating system, similar to what could be run on a Symmetric Multiprocessor (SMP).

[0017] Cache coherence with integrated message passing and memory protection between processor nodes 102a-tare achieved with the invention as applied to the exemplary system 100. The processor nodes in a site, e.g., processor nodes 102a-din site 106a,share a physical address memory space. In addition, each of the processor nodes may have multiple processors, each having a cache memory (FIG. 2). Thus, cache coherence must be maintained between caches of processors not only within a node, but also in different processor nodes. For example, caches in node 102amust be coherent with caches in nodes 102b-d.

[0018] The invention includes a memory protection mechanism which permits access to a shared physical memory address space for processor nodes inside a site and denies access for processor nodes outside a site. For example, processor node 102emay pass messages to processor node 102a.However, because processor node 102eis not within site 106a,processor node 102emay not perform memory access operations on the physical address space of site 106a.

[0019] The memory protection mechanism relies on node identifiers (NIDs) and coherence node numbers (CNNs) and a mapping between them. Each processor node in the system is given a NID that is unique system-wide. In addition, each processor node within a site is assigned a CNN that is unique within the site. Processor nodes in a site each keep a table that holds the mapping between CNNs and NIDs for all other processor nodes within that site. In system 100, site 106dhas node 102twith NID=151, CNN=1, node 102swith NID=152, CNN=2, node 102rwith NID=153, CNN=3, and node 102qwith NID=154, CNN=4. Messages communicated between processor nodes always include the NID that identifies the source processor node. The receiving node uses its mapping table to determine whether the incoming message is from a processing node within the same site or not. If the source node site differs from the destination node site, memory access protections apply.

[0020] FIG. 2 is a functional block diagram of a processor node 102. Processor node 102 is exemplary of FIG. 1 processor nodes 102a-tand includes processors 202a-deach having a respective cache 204a-d,a memory subsystem 206, an input/output subsystem 208, and a mesh coherence unit (MCU) 210. Each of the functional units 202a-d,206, 208, and 210 are connected to bus 212 for transmitting control, address, and data signals between the units. The mesh coherence unit 210 is connected to interconnection 104. The mesh coherence unit 210 coordinates inter-processor node cache coherence, inter-processor node message passing, and inter-processor node memory protection.

[0021] The processors 202a-d,memory subsystem 206, input/output subsystem 208, mesh coherence unit 210 and bus 212 represent one possible processor node implementation; for example, a different number of processors could be used.

[0022] FIG. 3 is a block diagram of mesh coherence unit 210, which maintains inter-processor node cache coherency, supports message passing between processor nodes 102a-t,and protects against unauthorized memory accesses.

[0023] Mesh coherence unit 210 includes an output control element 310, an input control element 312, a cache coherence control element 314, and an interconnection interface 316. Output control element 310 includes a CNN map register 332, and input control element 312 includes a memory access control element 334. Output control element 310 receives control signals via line 322 and data signals via line 324 from bus 212, and transmits output messages to interconnection interface 316 for transmission to a designated processor node 102a-t.Similarly, input control element 312 receives messages from interconnection interface 316 and transmits control signals via line 326 and data signals via line 328 to bus 212 for delivery to a designated processor, e.g., 102a.

[0024] Cache coherence control element 314 maintains state information for cached memory locations. Referring again to FIG. 2, each processor node within a site 102 has memory subsystem 206 that is local to the processors within that node. Cache coherence control element 314 (FIG. 3) coordinates coherency for memory locations that are local relative to mesh coherence unit 210.

[0025] CNN map register 332 and memory access control element 334 use node identification numbers (NIDs), coherence node numbers (CNNs), and a mapping between them to provide memory protection between processor nodes. Each node 102 in system 100 is given a NID. Once a set of nodes is committed to share memory, they are each assigned a CNN, and all adopt a consistent mapping of CNNs to NIDs. With this mapping a processor node is able to tell whether an incoming message is from within the same coherence group (in which case it is completely unprotected) or is from outside the coherence group (in which case the shared-nothing protections apply). This allows processor nodes sharing memory and processor nodes sharing nothing to co-exist on the same interconnection.

[0026] The exemplary embodiments described herein are for purposes of illustration and are not intended to be limiting. Therefore, those skilled in the art will recognize that other embodiments could be practiced without departing from the scope and spirit of the claims set forth below.