Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1998-08-06
2003-06-03
Marcelo, Melvin (Department: 2733)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S412000
Reexamination Certificate
active
06574219
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field of the Invention
The present invention relates to multiprocessor computer systems on a decentralized ring that performs passive message ordering.
2. Background Art
Multiprocessor computer systems have included buses that allow communication between processors, and between a chipset and the processors (each of which are referred to as nodes). To avoid contention on the bus, a central arbiter, which may be in the chipset, determines which node on the bus may transmit a message on the bus. A message on the bus is broadcast to each node on the bus and each node receives the message essentially at the same time. Therefore, there is no confusion as to the order in which the messages are transmitted.
Ring topologies have been developed in which each node is connected to an adjacent node on a ring. In a point-to-point ring, each node is separated from adjacent nodes on the ring by links (conductors). An advantage of rings are that the drivers of conductors on the ring are loaded only with the receiver circuitry of the particular node, not all nodes on the system. Accordingly, the signals may change state significantly faster.
Each node may transmit messages to each other node, but the messages are passed sequentially from node to node, rather than from a central point to all nodes simultaneously. Accordingly, none of the links can be observed by all the nodes. Ordinarily, a node will not know that another node has transmitted a message until it is received. If more than one node concurrently transmits messages, they will be received in different orders by different nodes. For messages such as snoop requests, this will lead to incorrect results.
Accordingly, there is a need for a system to order messages such that each node orders messages consistently.
SUMMARY
In some embodiments, a computer system includes nodes connected through conductors to form a ring. Messages are transmitted on the ring and at least some of the nodes each include control circuitry to receive the messages in a node reception order that is different for each node and order the messages in a global order that is the same for each node having the control circuitry.
REFERENCES:
patent: 4933933 (1990-06-01), Dally et al.
patent: 5025365 (1991-06-01), Mathur et al.
patent: 5604450 (1997-02-01), Borkar et al.
patent: 5623628 (1997-04-01), Brayton et al.
patent: 5715428 (1998-02-01), Wang et al.
patent: 5751986 (1998-05-01), Fetterman et al.
patent: 5881303 (1999-03-01), Hagersten et al.
patent: 5960179 (1999-09-01), Hagersten
patent: 6112283 (2000-08-01), Neiger et al.
Barroso, Luiz A. and Michel Dubois, “Cache Coherence on a Slotted Ring”, Proceedings of the 1991 International Conference on Parallel Processing, Aug. 1991, pp. I-230 to I-237.
Hopper, Andrew and Roger M. Needham, “The Cambridge Fast Ring Networking System”, IEEE Transactions on Computers, vol. 37, No. 10, Oct. 1988, pp. 1214-1223.
Neiger, Gil and Sam Toueg, “Simulating Synchronized Clocks and Common Knowledge in Distributed Systems”, Journal of the Association for Computing Machinery, vol. 40, No. 3, Apr. 1993, pp. 334-367.
Pierce, John R. “How Far Can Data Loops Go”, IEEE Transactions on Communications, vol. Com-20, No. 3, Jun. 1972, pp. 527-530.
Cheng Kai
Neiger Gilbert A.
Wade Nicholas D.
LandOfFree
Passive message ordering on a decentralized ring does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Passive message ordering on a decentralized ring, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Passive message ordering on a decentralized ring will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3160802