US5551048A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Ring based distributed communication bus for a multiprocessor network
Assignee: Hewlett Packard Development Co LP
•
Filing: 1994-06-03
•
Granted: 1996-08-27
•
Expires: 2014-06-03
Abstract
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.
Inventors
- 👤 Simon C. Steely, Jr.
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-31 17:34
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/08; G06F12/0802; G06F12/0806; G06F12/0813; G06F12/0815
Claims Analysis
Total Claims: 14
Claim 1
Independent Claim
252 words
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.
Claim 2
Independent Claim
252 words
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.
Claim 3
Dependent Claim
61 words
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.
Claim 4
Dependent Claim
120 words
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.
Claim 5
Dependent Claim
24 words
The method of claim 3, wherein said received data represents updated data if: said first nodal distance is less than said second nodal distance.
Claim 6
Dependent Claim
133 words
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.
Claim 7
Dependent Claim
57 words
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.
Claim 8
Independent Claim
240 words
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.
Claim 9
Independent Claim
240 words
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.
Claim 10
Dependent Claim
35 words
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.
Claim 11
Dependent Claim
50 words
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.
Claim 12
Dependent Claim
33 words
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.
Claim 13
Dependent Claim
129 words
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.
Claim 14
Dependent Claim
49 words
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.
References Cited (Backward Citations)
US4466060A
Cited
US4894823A
Cited
US5341483A
Cited
US5088032A
Cited
US5197146A
Cited
US5043885A
Cited
US5191652A
Cited
US5386546A
Cited
US5265235A
Cited
US5249283A
Cited
US5386536A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-08-27 | 2000-02-26 | 2000-08-27 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-08-27 | 2004-02-26 | 2004-08-27 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-08-27 | 2008-02-26 | 2008-08-27 | $7700.00 | Window Closed / Lapsed |