Message passing with parallel queue traversal

• US 8,170,041 B1
• Filed: 09/14/2005
• Issued: 05/01/2012
• Est. Priority Date: 09/14/2005
• Status: Active Grant

• Current Assignee: National Technology & Engineering Solutions Of Sandia LLC (Honeywell International Inc.)
• Original Assignee: Sandia Corporation (Martin Marietta Corporation)
• Inventors: Underwood, Keith D., Brightwell, Ronald B., Hemmert, K. Scott
• Primary Examiner(s): Pham, Chi
• Assistant Examiner(s): Riyami, Abdullah
• Application Number:
  US11/226,092
• Time in Patent Office: 2,421 Days
• Field of Search: 370/236, 370/392, 370/394, 370/250, 370/252, 370/350, 370/412, 370/413, 370/414, 370/415, 370/420, 370/421, 370/422, 370/423, 370/426, 370/428, 370/235, 370/232, 370/465, 370/474, 719/313, 719/321, 719/328, 719/312, 719/314, 719/315, 719/316, 709/100, 709/101, 709/103, 709/245, 709/313, 709/314, 709/315, 709/318, 395/200.38, 395/670, 395/672, 395/674, 395/375, 395/650, 395/800, 395/200.63, 395/200.64, 395/200.65, 395/200.66, 395/200.67, 375/200.63, 375/200.64, 375/200.65, 375/200.66, 375/200.67, 375/200.38, 375/670, 375/672, 375/674, 375/375, 375/650, 375/800
• US Class Current: 370/412
• CPC Class Codes: G06F 13/385 for adaptation of a particular data processing system to different peripheral devices

Abstract

In message passing implementations, associative matching structures are used to permit list entries to be searched in parallel fashion, thereby avoiding the delay of linear list traversal. List management capabilities are provided to support list entry turnover semantics and priority ordering semantics.

Claims

1. An apparatus for supporting message passing, comprising:

an input that receives from a requesting source a request associated with a message;

an information storage apparatus that stores a prioritized queue of entries;

an associative matching apparatus coupled to said input and said storage apparatus, said associative matching apparatus configured for searching said prioritized queue of entries in parallel to determine whether any of said entries matches predetermined information in the request, wherein said associative matching apparatus is configured to identify, in parallel with said searching, one of said entries whose priority in said prioritized queue is highest among a plurality of said entries determined to match said predetermined information, and wherein said associative matching apparatus is configured to provide a data path for routing, from said prioritized queue to the requesting source, at least a portion of an entry of said prioritized queue that matches said predetermined information.

2. The apparatus of claim 1, wherein said associative matching apparatus includes prioritization logic that identifies said one entry and selects at least a portion thereof for routing on said data path.

3. The apparatus of claim 2, wherein said associative matching apparatus includes identification logic that identifies a position of said one entry in the queue.

4. The apparatus of claim 3, including control logic coupled to said identification logic and said storage apparatus, said control logic removing said one entry from the queue in response to said identification logic.

5. The apparatus of claim 4, wherein said control logic also reconfigures the queue such that an empty position in the queue created by said removal of said one entry is relocated within the queue to become a lowest priority position of the queue which is available to receive a new entry into the queue.

6. The apparatus of claim 5, wherein said prioritization logic is coupled to said identification logic, and said identification logic produces signals that control said prioritization logic.

7. The apparatus of claim 3, wherein said prioritization logic is coupled to said identification logic, and said identification logic produces signals that control said prioritization logic.

8. The apparatus of claim 2, wherein said prioritization logic includes a multiplexer tree.

9. The apparatus of claim 8, wherein the queue consists of 2^N entries, and said multiplexer tree includes N levels of multiplexers.

10. The apparatus of claim 8, wherein said multiplexer tree includes a plurality of multiplexers having a respectively corresponding plurality of multiplexer control inputs, said associative matching apparatus including identification logic that identifies a position of said one entry in the queue, said identification logic coupled to said multiplexer control inputs.

11. The apparatus of claim 1, wherein said associative matching apparatus includes identification logic that identifies a position of said one entry in the queue.

12. The apparatus of claim 11, including control logic coupled to said identification logic and said storage apparatus, said control logic removing said one entry from the queue in response to said identification logic.

13. The apparatus of claim 12, wherein said control logic also reconfigures the queue such that an empty position in the queue created by said removal of said one entry is relocated within the queue to become a lowest priority position of the queue which is available to receive a new entry into the queue.

21. The apparatus of claim 1, provided as an MPI apparatus.

14. A network interface apparatus that supports message passing between a data network and a host data processing apparatus, comprising:

a network input that receives messages from the data network;

a host input that accepts from the host data processing apparatus receive requests respectively indicative of messages that the host data processing apparatus expects to receive from the data network;

an information storage apparatus coupled to said host input and said network input and configured to stores a first prioritized queue of entries that are respectively associated with receive requests received from the host data processing apparatus and a second prioritized queue of entries that are respectively associated with messages received from the data network; and

an associative matching apparatus coupled to said network input and said host input and said storage apparatus, said associative matching apparatus responsive to a message from the data network for searching said first prioritized queue of entries in parallel to determine whether any of said entries thereof matches predetermined information in the message, and said associative matching apparatus responsive to a receive request from the host for searching said second prioritized queue of entries in parallel to determine whether any of said entries thereof matches predetermined information in the receive request;

wherein, if a plurality of said entries of one of said first and second prioritized queues match the associated predetermined information, the associated parallel searching identifies one of said plurality of entries whose priority in said one prioritized queue is highest.

15. The apparatus of claim 14, provided as a network interface chip.

16. A method for supporting message passing, comprising:

receiving from a requesting source a request associated with a message;

maintaining a prioritized queue of entries;

searching said prioritized queue of entries in parallel with digital logic circuitry to determine whether any of said entries matches predetermined information in the request;

identifying, with the digital logic circuitry and in parallel with said searching, one of said entries whose priority in said prioritized queue is highest among a plurality of said entries determined to match said predetermined information; and

providing a data path through the digital logic circuitry for routing, from said prioritized queue to the requesting source, at least a portion of an entry of said prioritized queue that matches said predetermined information.

17. The method of claim 16, including selecting at least a portion of said one entry for routing on said data path.

18. The method of claim 17, including identifying a position of said one entry in the queue.

19. The method of claim 18, including removing said one entry from the queue in response to said identifying said position.

20. The method of claim 19, including reconfiguring the queue such that an empty position in the queue created by said removing is relocated within the queue to become a lowest priority position of the queue which is available to receive a new entry into the queue.