Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2000-09-11
2004-11-02
Phan, Man (Department: 2665)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S392000, C370S400000, C370S414000
Reexamination Certificate
active
06813267
ABSTRACT:
BACKGROUND
1. Field of the Invention
The present invention relates to transferring data within a computing system. More specifically, the present invention relates to an apparatus and a method that facilitates both broadcast and point-to-point transmissions between components within a computing system.
2. Related Art
Modern computer systems are typically comprised of a number of devices, such as central processing units, memory units, input/output units, and caches. During computer system operation, address and data information must be rapidly transferred between these devices in order to achieve a high level of computer system performance. However, providing dedicated paths for communication between every pair of devices is impractical in sophisticated computer systems with a large number of devices because the number of paths increases quadratically with the number of devices.
A messaging system can be used to provide the necessary communications between devices. In a messaging system, packets are routed from a first device, possibly a central processing unit, through one or more switches to a second device, perhaps a memory. In response, the second device can return a packet to the first device.
In general, there can be two types of packets, point-to-point packets and broadcast packets. Point-to-point packets are used to transfer data between two devices. For example, a point-to-point packet may be used to send a memory request from a central processing unit to a memory unit to retrieve data. In contrast, a broadcast packet is used when all devices need to know the same piece of information, for instance, a message that a cache page has been invalidated.
Multiple point-to-point packets can be sent simultaneously. For instance, device
1
may be sending a packet to device
3
, while device
5
is sending a packet to device
2
. Since neither of these packets originate or terminate at a common device, the packets will not necessarily interfere with each other. A broadcast packet, however, must be the only packet being sent at a given time.
Interleaving point-to-point packets and broadcast packets can lead to a significant delay when a broadcast packet must be sent. This delay occurs because, before a broadcast packet is sent, the system must wait until all point-to-point packets are complete. In addition, favoring one type of packet over the other type can lead to starvation of the type of packet not being favored.
What is needed is an apparatus and a method for fairly arbitrating between point-to-point packets and broadcast packets in transmitting data between computer system components.
SUMMARY
One embodiment of the present invention provides a system that facilitates communications between a device within a computing system and one or more additional devices of the computing system. The system receives point-to-point packets and broadcast packets from the devices and inspects the headers of these packets to determine the type of a packet. The system also examines the state of the computing system to determine whether the state of the computer system is either broadcast preferred or point-to-point only. If the type of the packet is broadcast and the state of the computing system is broadcast preferred, the system sends the packet to all of the additional devices. If the type of the packet is broadcast and the state of the computing system is point-to-point only, the system delays sending the packet until the state of the computing system changes to broadcast preferred. If the type of the packet is point-to-point and the state of the computing system is broadcast preferred, the system delays sending the packet while broadcast packets are available to be sent. Finally, if the type of the packet is point-to-point and the state of the computing system is point-to-point only, the system sends the packet to the addressed device.
In one embodiment of the present invention, the receiving mechanism includes a plurality of input queues, each input queue being assigned to one of the plurality of additional devices of the computing system.
In one embodiment of the present invention, the system inspects the routing prefix of the packet to determine if the packet is a broadcast packet or a point-to-point packet. If the packet is a point-to-point packet, the system determines a destination for the packet.
In one embodiment of the present invention, the system uses an n-counter to count available packet slots and an m-counter to count broadcast preferred packet slots. The combination of the n-counter and the m-counter determine the state of the computing system. The system uses a broadcast arbiter to issue a broadcast grant to the input queue in response to a broadcast request. The system uses point-to-point arbiters to issue a point-to-point grant to one of the input queues in response to a point-to-point request. Output multiplexers route the packet from the input queue to the selected device, or in the case of a broadcast packet, to all of the devices.
In one embodiment of the present invention, the n-counter is configured to be reset to the number of available packet slots upon receiving an external command or when the n-counter decrements to zero.
In one embodiment of the present invention, the m-counter is configured to be reset to the number of broadcast preferred slots upon receiving an external command or when the n-counter decrements to zero.
In one embodiment of the present invention, upon decrementing to zero, the m-counter is configured to hold at zero waiting for a reset command.
In one embodiment of the present invention, the system sets the state of the computing system to broadcast preferred if both the n-counter and the m-counter are counting. The system sets the state of the computing system to point-to-point only if the n-counter is counting and the m-counter is zero.
In one embodiment of the present invention, the broadcast arbiter receives broadcast requests from the input queues and provides a broadcast grant signal to a requesting input queue based on the state of the computing system and the other grant signals.
In one embodiment of the present invention, the point-to-point arbiter receives point-to-point requests from the plurality of input queues and provides a point-to-point grant signal to the requesting input queue based on the state of the computing system and the other grant signals.
In one embodiment of the present invention, the output multiplexer routes the packet from the selected input queue to the device that is coupled with the output multiplexer.
REFERENCES:
patent: 4630260 (1986-12-01), Toy et al.
patent: 4734907 (1988-03-01), Turner
patent: 5001702 (1991-03-01), Teraslinna et al.
patent: 5195089 (1993-03-01), Sindhu et al.
patent: 5309433 (1994-05-01), Cidon et al.
patent: 5809027 (1998-09-01), Kim et al.
patent: 5956342 (1999-09-01), Manning et al.
patent: 6175566 (2001-01-01), Hahn et al.
patent: 6426957 (2002-07-01), Hauser et al.
patent: 6539025 (2003-03-01), Manning et al.
patent: 6567885 (2003-05-01), Marmash
Clayton William A.
Seltzer Wayne F.
Warner Lee A.
Grundler Edward J.
Park, Vaughn & Fleming LLP
Phan Man
Sun Microsystems Inc.
LandOfFree
Tunable broadcast/point-to-point packet arbitration does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Tunable broadcast/point-to-point packet arbitration, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Tunable broadcast/point-to-point packet arbitration will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3343025