Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1998-08-06
2002-04-23
Marcelo, Melvin (Department: 2663)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S412000
Reexamination Certificate
active
06377582
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field of the Invention
The present invention relates to the use of virtual slots in a ring topology and to a dynamic wait method of determining whether a node in the ring should retain or give up ownership of a virtual slot.
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. Control of access to the ring is nontrival.
There is a need for an improved system and method for transmitting messages on the ring and for determining which nodes may transmit the messages at a given time.
SUMMARY OF THE INVENTION
In some embodiments, a ring based multiprocessor system includes nodes in a ring, at least some of the nodes including network interface circuitry to transmit messages beginning at a first flit of multi-flit virtual slots.
In some embodiments, a ring based multiprocessor system includes nodes in a ring at least some of the nodes including network interface circuitry to transmit messages in virtual slots between nodes. The interface circuitry includes control circuitry to determine whether to retain or release ownership of the virtual slots based on values in an insig buffer and an ownership history table.
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 Michael 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.
Aldous Alan K.
Marcelo Melvin
LandOfFree
Decentralized ring arbitration for multiprocessor computer... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Decentralized ring arbitration for multiprocessor computer..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Decentralized ring arbitration for multiprocessor computer... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2906676