Ring based distributed communication bus for a multiprocessor network

• US 5,551,048 A
• Filed: 06/03/1994
• Issued: 08/27/1996
• Est. Priority Date: 06/03/1994
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Steely, Simon C. Jr.
• Primary Examiner(s): Geckil, Mehmet B.
• Assistant Examiner(s): STACHLER, ROBERT
• Application Number:
  US08/253,474
• Time in Patent Office: 816 Days
• Field of Search: 395/200, 395/425, 395/200.03, 395/200.18, 395/200.21, 395/403, 395/468, 395/800
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0813 with a network or matrix configuration
• CPC Class Codes: G06F 12/0815 Cache consistency protocols

Abstract

A method for providing communication between a plurality of nodes coupled in a ring arrangement, wherein a plurality of the nodes comprise processors each having a cache memory for storing a subset of shared data. Each of the nodes on the ring deposits data into a data slot during a given time period. The data deposited by each node may comprise an address field and a node field. To ensure data coherency between the caches, each processor on the ring includes a queue for saving a plurality of received data representative of the latest bus data transmitted on the bus. As each processor receives new data, the new data is compared against the plurality of saved data in the queue to determine if the address field of the new data matches the address field of any of the saved data of the queue. In the event that the new data matches one of the plurality of saved data, it is determined whether the new data represents updated data from the memory device. If the new data represents updated data it is shifted into the queue. If it does not represent updated data, it is discarded.

Claims

1. A method for providing communication between a plurality of nodes coupled in a ring formation, said method comprising the steps of:

receiving, at an input of each node, data from one of the neighboring nodes on said ring during a predetermined time period;

depositing data at an output of each node during said predetermined time period, wherein said data deposited by each node is either said data received at said input of said node during said predetermined time period or data provided by the respective node; and

wherein said plurality nodes further comprises a plurality processors, each processor including a memory for storing a subset of shared data shared between at least two of said plurality of nodes,

wherein said method further comprises the step of maintaining data coherency between each of said memories in each of said plurality of processors and said memory node, said step of maintaining coherency further comprising the steps of;

determining, at each processor, whether data received during said time period is updated data of interest to said receiving processor by;

determining a first nodal distance between a processor that transmitted said new data and said receiving processor; and

determining a second nodal distance between said receiving processor and a node indicated in a node field associated with version data stored at said processor;

storing said received data at said receiving processor if the relationship between said first nodal distance and said second nodal distance indicate that said data is updated data of interest to said processor.

2. The method of claim 1, wherein said step of determining whether said data is updated data of interest to said processor further comprises the steps of:

at each node, storing a plurality of said data received at said respective input during said predetermined time period in a queue, said queue comprising an address field for storing and address said received data.

3. The method of claim 2, wherein said step of determining whether said data is of interest to said one of said processors further comprises the steps of:

as each processor receives data, comparing said received data against said plurality of saved data in said queue to determine if the address field of said received data matches the address field of any of said plurality saved data in said queue;

in the event that said new data matches one of said plurality of saved data, determining whether said new data represents updated data from said memory device; and

responsive to a determination that said data is updated data of interest to said receiving processor, shifting said new data into said queue.

4. The method of claim 3, wherein said received data represents updated data if:

said first nodal distance is less than said second nodal distance.

5. The method according to claim 4, wherein said predetermined time period comprises a fixed time slot, and wherein said method of determining whether said data is updated data further comprises the steps of:

determining a cycle difference, wherein said cycle difference is the difference in the number of fixed time slots between the transmission of said received data and the transmission of said stored version of said data having said matching address;

determining a nodal difference, wherein said nodal difference is the difference between said first nodal distance and said second nodal distance;

where said data is determined to be updated data if said nodal difference is less than said cycle difference; and

wherein said data is determined to not to be updated if said nodal difference is greater than said cycle difference.

6. The method of claim 5, further comprising the step of:

providing a decision mechanism to allow each of said processors to consistently either shift said new data into said queue or preclude said new data from being stored in said queue, said decision mechanism operating in response to said nodal difference being equal to said cycle difference.

7. An apparatus comprising:

a bus arranged in a ring and having a protocol dividing transfer of data on said bus into a plurality of fixed time slots; and

a plurality of nodes, coupled for point to point communication on said ring, each of said nodes being assigned a unique node number and communicating with said bus by transmitting data during one of said plurality of fixed time slots, wherein a portion of said of plurality of nodes comprises a plurality of processors, and wherein each of said processors further comprise a first memory, for storing a subset of shared data, said subset of shared data shared between at least two of said plurality of nodes;

means, at each node for receiving data from other nodes on said ring, wherein said received data comprises a node field and an address field;

means for maintaining coherency between said memories of said nodes including means, responsive to a match between said address field of said received data and an address of a version of said data stored at said receiving node, for determining a first distance and a second distance, wherein said first distance is the distance between the node indicated in the node field of the retrieved data and the node receiving the data, and the second distance is the distance between the mode receiving the data and a node associated with the stored version of the data at said received node.

8. The apparatus of claim 7, wherein one of said plurality of nodes is a memory, and wherein said shared data is further shared between said memory and one of said first memories of said processors.

9. The apparatus of claim 7, wherein each of said plurality of processors further comprises:

queue means for storing said received data; and

means for comparing the address field of said data received during each time slot against each of the address fields of said received data stored in said queue.

10. The apparatus of claim 7, wherein said means for comparing further comprises:

means, responsive to said first distance being less than said second distance, for shifting said retrieved bus data into said queue.

11. The apparatus of claim 10, further comprising:

means, responsive to said first distance being greater than said second distance, for determining a cycle difference, wherein the cycle difference is the number of fixed time slots between the time slot in which data is received by the retrieving node, and time slot in which data is received by the node having the matching address in the queue;

means for determining a node difference, wherein said node difference is the difference between said first distance and said second distance;

means, responsive to said node difference being less than said cycle difference, for shifting said retrieved into said queue; and

means, responsive to said node difference being greater than said cycle difference, for precluding storage of said retrieved data in said queue.

12. The apparatus of claim 11, further comprising:

means, responsive to said node difference being equal to said cycle difference and responsive to a fixed decision mechanism, for shifting said retrieved data into said queue, wherein said fixed decision mechanism is performed by each of said processors on said bus.