Optimization of packet processing by delaying a processor from entering an idle state

• US 9,396,010 B2
• Filed: 02/28/2014
• Issued: 07/19/2016
• Est. Priority Date: 09/07/2011
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Vincent, Pradeep, Becker, David D.
• Primary Examiner(s): LAMONT, BENJAMIN S
• Application Number:
  US14/194,077
• Publication Number:
  US 20140181818A1
• Time in Patent Office: 872 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 9/38 Concurrent instruction execution, e.g. pipeline or look ahead
• CPC Class Codes: G06F 9/45533 Hypervisors; Virtual machine monitors
• CPC Class Codes: G06F 9/5094 where the allocation takes into account power or heat criteria power management in computers in general G06F1/3203; thermal management in computers in general G06F1/206
• CPC Class Codes: H04L 49/20 Support for services
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

Some embodiments facilitate high performance packet-processing by enabling one or more processors that perform packet-processing to determine whether to enter an idle state or similar state. As network packets usually arrive or are transmitted in batches, the processors of some embodiments determine that more packets may be coming down a multi-stage pipeline upon receiving a first packet for processing. As a result, the processors may stay awake for a duration of time in anticipation of an incoming packet. Some embodiments keep track of the last packet that entered the first stage of the pipeline and compare that with a packet that the processor just processed in a pipeline stage to determine whether there may be more packets coming that need processing. In some embodiments, a processor may also look at a queue length of a queue associated with an upstream stage to determine whether more packets may be coming.

Claims

1. A non-transitory computer-readable storage medium storing computer-executable instructions that, when executed by a processor, cause the processor to perform operations, comprising:

receiving a network packet for processing at a first pipeline stage in a plurality of pipeline stages, the plurality of pipeline stages being respectively associated with a corresponding queue of a plurality of queues of network packets to be processed by the processor, the plurality of pipeline stages being distinct from the plurality of queues;

processing the network packet by a current pipeline stage;

upon completion of processing the network packet by the current pipeline stage, determining a queue length of a particular queue associated with an upstream pipeline stage for identifying an amount of processing time for the first pipeline stage in the plurality of pipeline stages, the upstream pipeline stage configured to process the network packet after the first pipeline stage; and

delaying the processor from entering the idle state for a duration of time based at least in part on determining that the queue length of the particular queue exceeds a threshold value.

2. The non-transitory computer-readable storage medium of claim 1, wherein the particular queue is associated with the upstream pipeline stage prior to the first pipeline stage.

3. The non-transitory computer-readable storage medium of claim 1, wherein the queue length is a first queue length, and the method further comprises determining a second queue length of another queue associated with another upstream pipeline stage when the determined first queue length is less than one.

4. The non-transitory computer-readable storage medium of claim 1, further comprising:

causing the processor to enter the idle state for at least the amount of processing time associated with the first pipeline stage;

determining that the queue length exceeds a second threshold value while the processor is in the idle state; and

processing one or more packets of the queue of network packets at the current pipeline stage.

5. The non-transitory computer-readable storage medium of claim 1, wherein the threshold value is zero.

6. A method, comprising:

receiving a network packet for processing at a first pipeline stage in a plurality of pipeline stages, the plurality of pipeline stages being respectively associated with a corresponding queue of a plurality of queues of network packets to be processed by the processor, the plurality of pipeline stages being distinct from the plurality of queues;

processing the network packet by a current pipeline stage;

upon completion of processing the network packet by the current pipeline stage, determining a queue length of a particular queue associated with an upstream pipeline stage for identifying an amount of processing time for the first pipeline stage in the plurality of pipeline stages, the upstream pipeline stage configured to process the network packet after the first pipeline stage; and

delaying the processor from entering the idle state for a duration of time based at least in part on determining that the queue length of the particular queue exceeds a threshold value.

7. The method of claim 6, wherein the particular queue is associated with the upstream pipeline stage prior to the first pipeline stage.

8. The method of claim 6, wherein the queue length is a first queue length, and the method further comprises determining a second queue length of another queue associated with another upstream pipeline stage when the determined first queue length is less than one.

9. The method of claim 6, further comprising:

causing the processor to enter the idle state for at least the amount of processing time associated with the first pipeline stage;

determining that the queue length exceeds a second threshold value while the processor is in the idle state; and

processing one or more packets of the queue of network packets at the current pipeline stage.

10. The method of claim 6, wherein the threshold value is zero.

11. The method of claim 6, wherein delaying the processor from entering the idle state for the duration of time is further based at least in part on identifying an amount of processing time elapsed between processing of the network packet by the first pipeline stage and processing of the network packet by the current pipeline stage, wherein the duration of time that the processor is delayed from entering the idle state corresponds to the amount of processing time elapsed.

12. The method of claim 6, wherein delaying the processor from entering the idle state for the duration of time is further based at least in part on:

determining a processing duration comprising of the time between processing the network packet by the first pipeline stage and receipt by the current pipeline stage;

determining a processing start time by subtracting the processing duration from a current time; and

comparing the processing start time and a last receipt time, the last receipt time indicating a time at which a last packet was received by the first pipeline stage, wherein the processor is delayed from entering the idle state when the comparison indicates that the processing start time is later than the last receipt time.

13. The method of claim 6, wherein the plurality of pipeline stages perform processing in parallel.

14. The method of claim 6, wherein delaying the processor from entering the idle state for the duration of time is further based at least in part on determining a longest processing time for an individual pipeline stage of the plurality of pipeline stages, and wherein the duration of time that the processor is delayed from entering the idle state corresponds to the longest processing time.

15. The method of claim 6, wherein delaying the processor from entering the idle state for the duration of time is further based at least in part on:

determining a number of packets processed by the current pipeline stage;

delaying the processor from entering an idle state when the queue length exceeds the number of packets processed the current pipeline stage; and

causing the processor to enter an idle state when the number of packets processed by the current pipeline stage exceeds the queue length.

16. A system, comprising:

a processor; and

a memory device including instructions that, when executed by the processor, cause the processor to;

receive a network packet for processing at a first pipeline stage in a plurality of pipeline stages, the plurality of pipeline stages being respectively associated with a corresponding queue of a plurality of queues of network packets to be processed by the processor, the plurality of pipeline stages being distinct from the plurality of queues;

process the network packet by a current pipeline stage;

upon completion of processing the network packet by the current pipeline stage, determine a queue length of a particular queue associated with an upstream pipeline stage for identifying an amount of processing time for the first pipeline stage in the plurality of pipeline stages, the upstream pipeline stage configured to process the network packet after the first pipeline stage; and

delay the processor from entering the idle state for a duration of time based at least in part on determining that the queue length of the particular queue exceeds a threshold value.

17. The system of claim 16, wherein the particular queue is associated with the upstream pipeline stage prior to the first pipeline stage.

18. The system of claim 16, wherein the queue length is a first queue length, and the processor is further caused to determine a second queue length of another queue associated with another upstream pipeline stage when the determined first queue length is less than one.

19. The system of claim 16, wherein the processor is further caused to:

enter the idle state for at least the amount of processing time associated with the first pipeline stage;

determine that the queue length exceeds a second threshold value while the processor is in the idle state; and

process one or more packets of the queue of network packets at the current pipeline stage.

20. The system of claim 16, wherein the threshold value is zero.