Method and apparatus for scheduling rule matching in a processor
View Patent ↗In a network search processor, configured to handle search requests in a router, a scheduler for scheduling rule matching threads initiated by a plurality of initiating engines is designed to make efficient use of the resources in the network search processor while providing high speed performance. According to at least one example embodiment, the scheduler and a corresponding scheduling method comprise: determining a set of bundles of rule matching threads, each bundle being initiated by a separate initiating engine; distributing rule matching threads in each bundle into a number of subgroups of rule matching threads; assigning the subgroups of rule matching threads associated with each bundle of the set of bundles to multiple scheduling queues; and sending rule matching threads, assigned to each scheduling queue, to rule matching engines according to an order based on priorities associated with the respective bundles of rule matching threads.
1. A method of scheduling rule matching threads initiated by a plurality of initiating engines in a network search processor, for processing by multiple matching engines of the network search processor, the method comprising:
determining, by a scheduler, a set of bundles of rule matching threads, each bundle being initiated by a separate initiating engine;
distributing rule matching threads in each bundle of the set of bundles into a number of subgroups of rule matching threads;
assigning the subgroups of rule matching threads associated with each bundle of the set of bundles to multiple scheduling queues; and
sending rule matching threads, assigned to each scheduling queue, toward rule matching engines according to an order based on priorities associated with the respective bundles of rule matching threads.
2. A method according to claim 1 further comprising receiving, at the scheduler, data corresponding to one or more bundles of rule matching threads from one or more initiating engines of the plurality of initiating engines.
3. A method according to claim 2 , wherein upon receiving data corresponding to a first bundle from a given initiating engine, no other data corresponding to at least one other bundle is received from the given initiating engine until sending all rule matching threads in the first bundle to rule matching engines.
4. A method according to claim 1 further comprising sending a notification to an initiating engine associated with a given bundle upon sending at least one rule matching thread associated with the given bundle.
5. A method according to claim 1 , wherein the set of bundles determined being the bundles of the rule matching threads available at the scheduler at the time the set of bundles is determined.
6. A method according to claim 1 , wherein sending the rule matching threads toward the rule matching engines includes sending a request, for a respective data chunk, to a memory component of the network search processor, the respective data chunk being retrieved and forwarded to the rule matching engine.
7. A method according to claim 1 , wherein the set of bundles is a first set of bundles and the method further comprising determining a second set of bundles upon sending all the rule matching threads in the first set of bundles toward the rule matching engines.
8. A method according to claim 1 , wherein within a subgroup, the order is further based on priorities assigned to rule matching threads of a respective bundle.
9. A method according to claim 1 , wherein sending a rule matching thread toward a rule matching engine includes sending the rule matching thread only if a respective expected processing delay does not exceed a pre-defined threshold.
10. A method according to claim 9 , wherein the expected processing delay includes a processing time, at the rule matching engine, of the rule matching thread and an expected traveling and queuing time of the rule matching thread, the processing time is dependent on a size of a data chunk associated with the respective rule matching thread, the travel and queuing time being dependent on a cumulative size of data chunks associated with rule matching threads sent to the rule matching engines.
11. A network search processor comprising:
a plurality of initiating engines configured to initiate bundles of rule matching threads;
multiple rule matching engines configured to process the rule matching threads;
a scheduling engine configured to:
determine a set of bundles of rule matching threads, each bundle being initiated by a separate initiating engine;
distribute rule matching threads in each bundle of the set of bundles into a number subgroups of rule matching threads;
assign the subgroups of rule matching threads associated with each bundle to multiple scheduling queues; and
send rule matching threads, assigned to each scheduling queue, toward rule matching engines according to an order based on priorities associated with the respective bundles of rule matching threads.
12. A network search processor according to claim 11 , wherein the scheduling engine is configured to further receive data corresponding to one or more bundles of rule matching threads from one or more initiating engines of the plurality of initiating engines.
13. A network search processor according to claim 12 , wherein upon receiving data corresponding to a first bundle from a given initiating engine, no other data corresponding to at least one other bundle is received from the given initiating engine until sending all rule matching threads in the first bundle to rule matching engines.
14. A network search processor according to claim 11 , wherein the scheduling engine is configured to send a notification to an initiating engine associated with a given bundle upon sending at least one rule matching thread associated with the given bundle.
15. A network search processor according to claim 11 , wherein the set of bundles determined being the bundles of the rule matching threads available at the scheduling engine at the time the set of bundles is determined.
16. A network search processor according to claim 11 , wherein in sending a rule matching thread toward a rule matching engine, the scheduling engine is configured to send a request for a respective data chunk to a memory component of the network search processor, the respective data chunk being retrieved and forwarded to the rule matching engine.
17. A network search processor according to claim 11 , wherein the set of bundles is a first set of bundles and the scheduling engine is configured to further determine a second set of bundles upon sending all the rule matching threads in the first set of bundles toward the rule matching engines.
18. A network search processor according to claim 11 , wherein within a subgroup, the order is further based on priorities assigned to rule matching threads of a respective bundle.
19. A network search processor according to claim 11 , wherein in sending a rule matching thread toward a rule matching engine the scheduling engine is configured to send the rule matching thread only if a respective expected processing delay does not exceed a pre-defined threshold.
20. A network search processor according to claim 19 , wherein the expected processing delay is a sum of a processing time of the rule matching thread and an expected traveling and queuing time of the rule matching thread, the processing time is dependent on a size of a data chunk associated with the respective rule matching thread, the travel and queuing time being dependent on a cumulative size of data chunks associated with rule matching threads sent to the rule matching engines.