Apparatus and method for packet coalescing within interconnection network routers

• US 20060047849A1
• Filed: 06/30/2004
• Published: 03/02/2006
• Est. Priority Date: 06/30/2004
• Status: Abandoned Application

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Mukherjee, Shubhendu S.
• Application Number:
  US10/881,845
• Publication Number:
  US 20060047849A1
• Time in Patent Office: Days
• US Class Current: 709/238
• CPC Class Codes: G06F 15/17375 One dimensional, e.g. linear array, ring

Abstract

A method and apparatus for packet coalescing within interconnection network routers. In one embodiment, the method includes the scan of at least one input buffer to identify at least two network packets that include coherence protocol messages and are directed to the same destination, but from different sources. In one embodiment, coherence protocol messages within the network packets are combined into a coalesced network packet. Once combined, the coalesced network packet is transmitted to the same or matching destination. In one embodiment, combining multiple network packets (each containing a single logical coherence message) into a larger, coalesced network packet amortizes the fixed overhead of sending a network packet including a single coherence message, as compared to the larger, coalesced network packet, to improve bandwidth usage. Other embodiments are described and claimed.

Claims

1. A method comprising:

scanning at least one input buffer to identify at least two network packets having a different source and a matching destination, each network packet including a single coherence protocol message;

combining the coherence protocol messages within the identified network packets into a coalesced network packet; and

transmitting the coalesced network packet to the matching destination.

2. The method of claim 1, wherein the network packets occur in a burst from a producer to a consumer according to a stable producer-consumer sharing pattern.

3. The method of claim 1, wherein the identified network packets are destined to the same processor.

4. The method of claim 1, wherein combining comprises:

setting a pointer to each of the identified network packets;

updating a table of pointers with the coalesced network packet pointing to the at least two identified network packets; and

storing the coherence protocol messages within the coalesced network packet according to the table of pointers prior to forwarding of the coalesced network packet to an output port.

5. The method of claim 1, further comprising:

dropping the identified network packets.

6. The method of claim 1, wherein scanning further comprises:

searching a central buffer to detect network packets from different sources headed to a same destination; and

identifying detected network packets containing a single coherence protocol message.

7. The method of claim 1, wherein combining further comprises:

storing the identified network packets within a merge buffer;

forming the coalesced network packet from the coherence protocol messages within the identified network packets prior to assignment of the coalesced network packet to an output port; and

dropping the identified network packets.

8. The method of claim 1, wherein scanning further comprises:

storing detected network packets including a single coherence protocol message within a merge buffer; and

scanning the merge buffer to identify the at least two network packets having the same destination.

9. The method of claim 1, wherein the combining of the coherence protocol messages within the identified network packets into the coalesced network packet is performed during a merge pipeline stage.

10. The method of claim 1, wherein a coherence protocol message within a network packet comprises one of a cache miss request and a cache miss response.

11. A method comprising:

storing detected network packets including a coherence protocol message within a merge buffer;

scanning the merge buffer to identify at least two network packets having a different source and a matching destination; and

forming a coalesced network packet from coherence protocol messages within the identified network packets.

12. The method of claim 11, wherein the coalesced network packet is formed prior to assignment of the coalesced network packet to an output port.

13. The method of claim 11, wherein forming the coalesced network packet comprises:

setting a pointer to each of the identified network packets;

updating a table of pointers with the coalesced network packet pointing to the at least two identified network packets; and

storing the coherence protocol messages within the coalesced network packet according to the table of pointers prior to forwarding of the coalesced network packet to an output port.

14. The method of claim 11, further comprising:

dropping the identified network packets.

15. The method of claim 11, wherein storing further comprises:

searching a central buffer to detect network packets containing a single coherence protocol message.

16. An apparatus, comprising:

at least one input buffer including a plurality of read ports; and

a controller to scan the at least one input buffer via a read port to identify at least two network packets having a different source and a matching destination, each network packet including a coherence protocol message, and to combine coherence protocol messages within the identified network packets into a coalesced network packet.

17. The apparatus of claim 16, wherein the at least one input buffer comprises:

a central buffer, the controller to search the central buffer via a read port to detect network packets from different sources headed to a same destination and to identify detected network packets containing a coherence protocol message.

18. The apparatus of claim 17, further comprising:

a merge buffer, the controller to store detected network packets including a coherence protocol message within the merge buffer and to scan the merge buffer to identify the at least two network packets having the different source and the matching destination.

19. The apparatus of claim 17, wherein the controller is to form the coalesced network packet prior to assignment of the coalesced network packet to an output port

20. The apparatus of claim 17, wherein the apparatus comprises an interconnection router of a chip multi-processor.

21. The apparatus of claim 17, further comprising:

a crossbar coupled to the at least one input buffer, the crossbar to forward the coalesced network packet to an output port.

22. The apparatus of claim 21, further comprising:

input port arbitration logic to nominate at least one network packet within the input buffer for output port arbitration; and

output port arbitration logic to accept packet nominations from the input port arbitration logic and to select a network packet for dispatch.

23. The apparatus of claim 16, wherein the controller is to combine the coherence protocol messages within the identified network packets into the coalesced network packet during a merge pipeline stage.

24. The apparatus of claim 21, further comprising:

four 2D torus input ports and four 2D torus output ports.

25. The apparatus of claim 16, wherein the apparatus further comprises:

a processor core coupled to the controller.

26. A system comprising:

a network including a plurality of processor nodes, each processor node including an interconnection router comprising;

at least one input buffer including a plurality of read ports, and

a controller to scan the at least one input buffer via a read port to identify at least two network packets having a different source and a matching destination, each identified network packet including a coherence protocol message and to combine coherence protocol messages within the identified network packets into a coalesced network packet.

27. The system of claim 26, wherein the system is a cache-coherent shared-memory multi-processor system.

28. The system of claim 26, wherein the network is a two-dimensional mesh network.

29. The system of claim 26, wherein the at least one input buffer comprises:

a central buffer, the controller to search the central buffer to detect network packets from different sources headed to a same destination and to identify detected network packets containing a coherence protocol message.

30. The system of claim 26, further comprising:

a merge buffer, the controller to store detected network packets including a coherence protocol message within the merge buffer and to scan the merge buffer to identify the at least two network packets having the same destination.