Method for updating value in distributed shared virtual memory among interconnected computer nodes having page table with minimal processor involvement

• US 5,522,045 A
• Filed: 08/04/1994
• Issued: 05/28/1996
• Est. Priority Date: 03/27/1992
• Status: Expired due to Term

• Current Assignee: Panasonic Corporation Of North America (Panasonic Holdings Corporation)
• Original Assignee: Panasonic Technologies, Inc. (Panasonic Holdings Corporation)
• Inventors: Sandberg, Jonathan
• Primary Examiner(s): AN, MENG AI T
• Application Number:
  US08/286,799
• Time in Patent Office: 663 Days
• Field of Search: 395/800, 395/725, 395/775, 395/700, 395/425, 395/275, 395/200, 395/325, 395/200.08, 395/200.01, 395/412, 395/413, 395/200.02, 395/200.06, 395/200.10 , 395/200.16, 395/824, 395/878
• US Class Current: 709/215
• CPC Class Codes: G06F 12/1072 Decentralised address translation, e.g. in distributed shared memory systems
• CPC Class Codes: G06F 12/1081 for peripheral access to main memory, e.g. direct memory access [DMA]
• CPC Class Codes: H04L 49/103 using a shared central buffer; using a shared memory
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags
• CPC Class Codes: H04L 49/3018 Input queuing
• CPC Class Codes: H04L 49/3027 Output queuing
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

The invention relates to general purpose interprocessor communication implemented through a distributed shared memory network connecting a plurality of processors, computers, multiprocessors, and electronic and optical devices. The invention teaches a method and means for shared memory based data transfer between a multiplicity of asynchronously operating devices (processors, computers, multiprocessors, etc.) each using possibly distinct memory address translation architectures. The invention further teaches shared virtual memory network communication and administration based on a unique network memory address translation architecture. This architecture is compatible with and augments the address translation and cache block replacement mechanisms of existing devices. More particularly, the invention teaches an adapter for insertion into an operating device, or node, whereby all address translation, memory mapping and packet generation can be implemented. The invention teaches that all network activities can be completed with only write and control operations. An interconnecting switch part and bus arrangement facilitates communication among the network adapters.

Claims

1. A method for a first node, said first node having at least one first processor, first user process, first operating system having a memory cycle, and first shared memory location at a first address, said first node being interconnected to a plurality of second nodes, each said second node having at least one second processor, second operating system, and second shared memory location at a virtual address and at least one page table, in response to said first user process assigning an update value to said at least one first shared memory location, to provide an update value to said at least one second shared memory location, comprising the steps of:

(a) updating, with said update value, said first shared memory location;

.

(b) accessing said page table and, with said first address, obtaining said virtual address;

(c) generating a write packet containing said virtual address and said update value;

(d) atomically generating a command packet comprising at least one command based upon said update value;

(e) sending said write packet to each of said second nodes;

(f) sending said command packet to each of said second nodes;

(g) receiving said command packet at each of said second nodes; and

(h) executing said command at each of said second nodes;

wherein steps (a) through (f) occur independent of operation of said first operating system and steps (a) through (d) occur atomically within said memory cycle; and

whereby said receiving and said executing occur atomically independent of the operation of said second operating system.

2. A method for a first node to update a first memory location, each said first node having at least one first processor, first operating system and said first memory location with first virtual memory location address, said first node connected in a network to a plurality of second nodes, each said second node having at least one second processor, second operating system and second memory location having a second virtual memory location address, wherein said first memory location and said plurality of second memory locations contain shared memory values, each said first node having at least one page table containing virtual addresses and physical addresses of said first memory locations at said first node and of said second memory locations at said plurality of second nodes, comprising the steps of:

(a) receiving at said first node a packet from said network containing an update value and said first virtual memory location address;

(b) accessing said at least one page table to translate said first virtual memory location address to a physical memory address corresponding to said first memory location; and

(c) updating, with said physical memory address, said first memory location with said update value;

whereby said receiving and said updating occur atomically independent of the operation of said first operating system.

3. A method for a first node to provide an update value to a plurality of second nodes, each said first node having at least one first processor, first operating system, said first memory location having a first virtual memory location address, said first node being connected in a network to a plurality of second nodes, each said second node having at least one second processor, second operating system and second memory location having a second virtual memory location address, wherein said first memory location and said plurality of second memory locations contain shared memory values, each said first node having at least one first page table containing virtual addresses and physical addresses of said first memory locations locations at said first node and of said second memory locations at said plurality of second nodes, comprising the steps of:

(a) receiving at said first node a first packet from said network containing an update value and said first virtual memory location address; and

(b) updating, with said first virtual memory location address, said first memory location;

(c) performing a look-up with said first page table by providing said first virtual memory location address to said first page table and obtaining at least one said second memory location address corresponding to said first virtual memory location address therefrom; and

(d) generating a second packet containing said second memory location address and said update value;

(e) sending said second packet to said plurality of second nodes;

whereby said generating occurs atomically independent of said first operating system.

4. The method of claim 3 wherein said second memory location address comprises a virtual address for said shared memory at said plurality of second nodes.

5. The method of claim 4 wherein each of said plurality of second nodes includes at least one second page table comprising virtual addresses and physical addresses for memory locations of said shared memory and further comprising at a second node the steps of:

(a) receiving said second packet comprising said virtual memory location address and said update value;

(b) obtaining a physical address corresponding to said virtual memory location address from said page table; and

(c) updating at said physical address, said second memory location;

whereby said steps (a) through (c) occur atomically independent of the operation of said second operating system.

6. A method for a first node to update a first memory location and to propagate a command based thereon to a network of nodes, each said first node having at least one first processor, first operating system and said first memory location with first virtual memory location address, said first node connected in a network to a plurality of second nodes, each said second node having at least one second processor, second operating system and second memory location having a second virtual memory location address, wherein said first memory location and said plurality of second memory locations contain shared memory values,

(a) receiving at said first node a first network packet containing said update value and a first virtual memory location address;

(b) updating, with first virtual memory location address, said first memory location;

(c) atomically generating a command packet comprising at least one command based upon said update value;

(d) sending said command packet to each said second node;

(e) receiving said command packet at each said second node; and

(f) executing said command at each said second node;

whereby said receiving, said updating, said generating and said sending occur atomically independent of operation of said first operating system and said receiving and executing occur atomically independent of the operation of said second operating system.

7. A method for updating shared virtual memory among shared memory locations having addresses, said shared memory locations being associated with a first node, said first node having a first operating system and at least one first page table, and said shared memory locations also being associated with at least one second node, said second node connected to said first node through a network, and said second node having at least one Second operating system and at least one second page table, comprising:

(a) memory mapping said shared memory locations into said page tables;

(b) multicasting a packet containing at least one shared memory update and a virtual address for at least one said shared memory location from said first node to said at least one second node;

(c) receiving said packet at said at least one second node;

(d) accessing said at least one second page table;

(e) finding, with said second page table, said shared memory location corresponding to said virtual address at said at least one second node and

(f) updating said shared memory location at said at least one second node with said shared memory update;

whereby steps (a) through (f) occur atomically independent of the operation of said first and said at least one second operating systems.

8. The method of claim 7 wherein said network includes at least one third node having at least one third operating system, at least one third shared memory location having a third shared memory address and at least one third page table further comprising the steps, in said at least one second node, of:

(a) assembling a second packet containing said update and said third shared memory address for transmission to said at least one third node; and

(b) sending said second packet to said third node;

whereby said assembling and said sending occur atomically independent of the operation of said at least one second operating system.

9. The method of claim 8 wherein said assembling comprises accessing said at least one second page table and obtaining a physical address corresponding to said third shared memory location at said at least one third node and further comprising the steps of:

(a) receiving said second packet at said at least one third node; and

(b) updating, with said physical address, said at least one third shared memory location;

whereby said receiving and said updating occur atomically independent of operation of said at least one third operating system.

10. The method of claim 8 wherein said third shared memory address comprises a virtual address and further comprising the steps of:

(a) receiving said second packet at said at least one third node;

(b) obtaining, with said page table, a physical address corresponding to said third shared memory address; and

(c) updating, with said physical address, said at least one third shared memory location;

whereby said receiving, said obtaining and said updating occur atomically independent of operation of said at least one third operating system.