Method and apparatus for optimizing selection of available contexts for packet processing in multi-stream packet processing

• US 7,649,901 B2
• Filed: 06/13/2001
• Issued: 01/19/2010
• Est. Priority Date: 02/08/2000
• Status: Expired due to Term

• Current Assignee: ARM Finance Overseas Limited (SoftBank Group Corp.)
• Original Assignee: MIPS Technologies Incorporated (Wave Computing, Inc.)
• Inventors: Musoll, Enrique, Nemirovsky, Mario
• Primary Examiner(s): Pham, Chi H.
• Assistant Examiner(s): MEW, KEVIN D
• Application Number:
  US09/881,628
• Publication Number:
  US 20020083173A1
• Time in Patent Office: 3,142 Days
• Field of Search: 370/412, 370/414, 370/416, 370/395.41, 370/395.4, 370/395.42, 370/395.43, 370/36, 370/413, 709/231, 709/238
• US Class Current: 370/412
• CPC Class Codes: G06F 9/546 Message passing systems or structures, e.g. queues
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames
• CPC Class Codes: H04L 47/621 Individual queue per connection or flow, e.g. per VC
• CPC Class Codes: H04L 47/6215 Individual queue per QOS, rate or priority
• CPC Class Codes: H04L 49/201 Multicast operation; Broadcast operation
• CPC Class Codes: H04L 49/205 Quality of Service based
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 49/901 using storage descriptor, e.g. read or write pointers
• CPC Class Codes: H04L 49/9073 Early interruption upon arrival of a fraction of a packet
• CPC Class Codes: H04L 69/12 Protocol engines
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A context-selection mechanism is provided for selecting a best context from a pool of contexts for processing a data packet. The context selection mechanism comprises, an interface for communicating with a multi-streaming processor; circuitry for computing input data into a result value according to logic rule and for selecting a context based on the computed value and a loading mechanism for preloading the packet information into the selected context for subsequent processing. The computation of the input data functions to enable identification and selection of a best context for processing a data packet according to the logic rule at the instant time such that a multitude of subsequent context selections over a period of time acts to balance load pressure on functional units housed within the multi-streaming processor and required for packet processing. In preferred aspects, programmable singular or multiple predictive rules of logic are utilized in the selection process.

Claims

1. A context-selection mechanism within a microprocessor for selecting a context from a pool of contexts for processing a data packet having a header, comprising:

an interface for receiving the data packet and communicating with a multi-streaming processor, said multi-streaming processor comprising a core that includes the pool of contexts;

circuitry for computing input data into a value according to one or more logic rules and for selecting a context from the pool of contexts based at least in part on the value; and

a loading mechanism for preloading data corresponding to the received data packet into the selected context for subsequent processing, the preloaded data including information from the data packet header;

wherein computation of the input data functions to enable identification and selection of a context for packet processing according to the logic rule at the instant time such that a multitude of context selections made over a period of time facilitate balancing of load pressure on functional units housed within the multi-streaming processor core and required for packet processing.

2. The context-selection mechanism of claim 1 integrated to a data packet router operating in a data-packet-network.

3. The context-selection mechanism of claim 2 wherein the data-packet-network is the Internet network.

4. The context-selection mechanism of claim 1 wherein the pool of contexts is divided into separate clusters in the core, each cluster containing some of the functional units used in packet processing.

5. The context-selection mechanism of claim 1 wherein the input data into the computation circuitry includes availability information of individual ones of the pool of contexts at the time of computation.

6. The context-selection mechanism of claim 5 wherein the input data into the computation circuitry further includes real time information of any processing streams stalled in un-available ones of the pool of contexts and the reason for the stall.

7. The context-selection mechanism of claim 5 wherein the input data into the computation circuitry further includes statistical data about previous processing time periods required to process similar data packets.

8. The context-selection mechanism of claim 5 herein the input data into the computation circuitry further includes statistical data about the distribution of instruction types associated with individual ones of previously processed and similar data packets.

9. The context-selection mechanism of claim 1 wherein the input data is sourced from the multi-streaming processor.

10. The context-selection mechanism of claim 1 wherein the input data is sourced from a third party.

11. The context-selection mechanism of claim 4 wherein the clusters are numbered and the functional units are distributed symmetrically therein.

12. The context-selection mechanism of claim 4 wherein the clusters are numbered and the functional units are distributed asymmetrically therein.

40. The context selection mechanism of claim 1, wherein the data corresponding to the received data packet includes:

an address indicating the start of a memory region in which the received data packet is stored; and

at least a portion of a header of the received data packet.

41. The context selection mechanism of claim 40, wherein the loading mechanism is configured to:

convey a first indication to the multi-streaming processor at the start of preloading data corresponding to the received data packet; and

convey a second indication to the multi-streaming processor at the completion of preloading data corresponding to the received packet.

13. A system for load balancing pressure on functional units within a multi-streaming processor core during the processing of multiple data packets comprising:

a context-selection mechanism having a communication interface;

circuitry for computing input data into a value according to one or more logic rules and a mechanism for preloading data corresponding to a data packet received from the communication interface into available ones of a pool of contexts within the core, the preloaded data including at least a portion of a data packet header of the data packet;

a multi-streaming processor core responsible for processing the data packets, the processor core hosting the functional units and the context pool; and

a set of instructions comprising the one or more logic rules governing context selection, wherein packet processing pressure upon the functional units within the processor core is balanced by selecting individual contexts for processing packet information based at least in part on the value.

14. The system of claim 13 integrated to a data packet router operating in a data-packet-network.

15. The system of claim 14 wherein the data-packet-network is the Internet network.

16. The system of claim 13 wherein the pool of contexts is divided into separate clusters in the processor core, each cluster containing some of the functional units used in packet processing.

17. The system of claim 13 wherein the input data into the computation circuitry includes availability information of individual ones of the pool of contexts at the time of computation.

18. The system of claim 13 wherein the input data into the computation circuitry further includes real time information of any processing streams stalled in un-available ones of the pool of contexts and the reason for the stall.

19. The system of claim 13 wherein the input data into the computation circuitry further includes statistical data about previous processing time periods required to process similar data packets.

20. The system of claim 13 wherein the input data into the computation circuitry further includes statistical data about the distribution of instruction types associated with individual ones of previously processed and similar data packets.

21. The system of claim 13 wherein the input data is sourced from the multi-streaming processor and provided in a software table.

22. The system of claim 13 wherein the input data is sourced from a third party.

23. The system of claim 16 wherein the clusters are numbered and the functional units are distributed symmetrically therein.

24. The system of claim 16 wherein the clusters are numbered and the functional units are distributed asymmetrically therein.

25. The system of claim 13 wherein the set of instructions comprising the logic rule is programmable.

42. The system of claim 13, wherein the data corresponding to the received data packet includes:

an address indicating the start of a memory region in which the received data packet is stored; and

at least a portion of a header of the received data packet.

43. The system of claim 42, wherein the mechanism for preloading data is configured to:

convey a first indication to the multi-streaming processor at the start of preloading data corresponding to the received data packet; and

convey a second indication to the multi-streaming processor at the completion of preloading data corresponding to the received packet.

26. A method for load balancing pressure on functional units contained within a multi-streaming processor core during processing of multiple data packets comprising steps of:

(a) arranging the functional units into two or more separate clusters on the core of the processor, each of said clusters containing an equal number of contexts that may write to functional units which are hosted by a corresponding cluster, wherein said functional units and contexts are included in the processor core;

(b) receiving a data packet for processing, the data packet having a header;

(c) receiving as input for computation, data about the instant availability status of individual contexts within each cluster;

(d) receiving as input for computation, data about stream status of streams occupying any contexts within each cluster; and

(e) computing the data received as input to produce a value, the value identifying and initiating selection of a context for processing packet information and balancing packet processing load of the functional units within each cluster;

(f) preloading data corresponding to the received data packet into the selected context for subsequent processing, the preloaded data including information from the data packet header; and

(g) repeating steps (b) through (f) for each of the multiple data packets for processing.

27. The method of claim 26 practiced in conjunction with a data packet router operating in a data-packet-network.

28. The method of claim 27 wherein the data-packet-network is the Internet network.

29. The method of claim 26 wherein in step (a) the functional units are provided within each cluster in a symmetrical fashion.

30. The method of claim 26 wherein in step (a) the functional units are provided within each cluster in an asymmetrical fashion.

31. The method of claim 26 wherein in step (b) the packet is received at a data port of a data router and requires automatic activation.

32. The method of claim 26 wherein in step (b) the packet is held by the processor and requires a context for processing.

33. The method of claim 26 wherein in step (c) availability status comprises an indication of which one of two components owns each context.

34. The method of claim 33 wherein in step (c) one of the components is the processor and other component is a packet management unit.

35. The method of claim 26 wherein in step (d) the data about stream status includes whether or not streams are stalled within any of the contexts and the reason for each instance of a stalled stream.

36. The method of claim 26 wherein in step (d) the data about stream status includes time parameters of how long each stream will take to process data packets associated with their contexts.

37. The method of claim 26 wherein in step (d) the data about stream status includes distribution parameters of instruction types that each stream has executed to process its data packet.

38. The method of claim 26 wherein in steps (c) through (d) are practice according to the rule of logic.

39. The method of claim 26 wherein the rule of logic is programmable.

44. The method of claim 26, wherein the data corresponding to the received data packet includes:

an address indicating the start of a memory region in which the received data packet is stored; and

at least a portion of a header of the received data packet.

45. The method of claim 44, further comprising:

conveying a first indication to the multi-streaming processor at the start of preloading data corresponding to the received data packet; and

conveying a second indication to the multi-streaming processor at the completion of preloading data corresponding to the received packet.