KR20060009000A - Threshold for unblocking processing nodes blocked due to the passage of data packets - Google Patents

Abstract

Threshold mechanisms are provided that allow producers and corresponding consumers running on the same resource (eg, CPU) to switch contexts between producers and consumers in a way that reduces the total number of context switches. This threshold mechanism is associated with a buffer where the producer stores the packet up to a given threshold before the consumer is allowed to drop the packet. This buffer has an upper limit associated with the number of packets that can be stored in the buffer. Flush flushes the buffer of the remaining packets when there are no more packets to be generated. In general, reducing the total number of context switches increases latency, but provides better performance.

Description

THRESHOLD ON UNBLOCKING A PROCESSING NODE THAT IS BLOCKED DUE TO DATA PACKET PASSING}

The present invention relates to a threshold for controlling the exchange of data packets between producers and consumers residing on the same CPU. More specifically, the present invention relates to software streaming based on graphs of processing nodes and for thresholds for unblocking processing nodes that are blocked due to the passage of data packets between two processing nodes residing on the same CPU. System and method.

Software streaming is based on graphs of processing nodes where communication is performed using individual data packets between processing nodes. This node actively passes packets from its input edge to its output edge, allowing data to flow through this graph. Each packet follows a specific loop through this graph, starting at the source node and ending at the sink node.

Two processing nodes running on the same resource (e.g. CPU) cannot run in parallel correctly. Instead, this resource switches between executions of two nodes. This is referred to as a context switch. Context switches are relatively expensive due to the fact that all registers must be stored, and even more expensive for CPUs that have caches (though they are no longer local due to switches).

When two communication processing nodes (producer, consumer) run on the same resource and the producer generates a packet, a context switch is required before the consumer can consume this packet. When a context switch is performed after each packet, two context switches (rear and forward) are required for each packet. To reduce this context switch, there are several options for tuning the system when constructing a streaming graph:

An option to increase the packet size and thus reduce the frequency of generating packets. This option has the disadvantage that both producers and consumers must be able to handle parameterized packet sizes. This increases the complexity of the node.

Let's say a producer creates a lot of packets before switching to a consumer.

Option to give this producer higher priority than consumer. This producer will continue until it can no longer proceed. The reason is that there are no longer empty packets available to fill and send to the consumer. At this point, the consumer can start. However, as soon as the consumer consumes one packet and releases it and this packet becomes available for reuse again, the producer is immediately active because there is an empty packet again and the producer has a higher priority than the consumer. Because it has a ranking. So giving producers higher priority does not solve the problem in most cases. Further, the priority is on the responsiveness of the control and is not used for this context switch problem.

Option to give equal priority to producers and consumers. These can generally be handled in a round robin fashion. This context switch may be limited depending on the time slice used by the operating system. However, giving the same priority to a task provides a negative impact on the worst case behavior (worst response). Thus, this option is in a trade-off relationship between the overhead of the context switch and the cost of the worst response.

Option to provide a threshold mechanism that prohibits consumers from starting to consume as soon as a packet is produced by the producer. And, additionally, when a consumer releases a packet and reuses it again, the producer provides an threshold mechanism that prevents the producer from consuming the packet immediately, that is, waiting for the amount of packets to reach its threshold. .

A common disadvantage of all the above mentioned options is the increased end-to-end latency, which is also true for the threshold mechanism.

The basic threshold mechanism is to unblock when a blocked consumer reaches a certain threshold (of available packets). A threshold of 5 (which informs the consumer only that a packet is present again when five packets are available) reduces the number of context switches by about the same factor (5).

This mechanism is used when the consumer is blocked, that is, when the consumer has previously tried to take a data packet but failed. This mechanism is not used if the consumer reaches a threshold of 5 without blocking at the data packet input. This threshold mechanism is independent of the processing node, i.e., the processing node does not know whether the threshold is used and what value the threshold has. The system integrator can configure this threshold during integration.

However, this threshold mechanism has several disadvantages, namely

Too high a threshold can lead to deadlock situations,

The disadvantage that if the data packet is not produced, the remaining data packets (below the threshold limit) may not be consumed because the consumer still does not know that some packets exist.

Have

In summary, the current state of the art regarding thresholds for limiting context switches is

As described above, with a general threshold,

-Passing of data packets,

Data packet synchronization,

-Calling the callback function when the data packet threshold is used

to be.

The threshold mechanism of the present invention is an effective means for reducing the number of context switches that are the result of the passage of data packets occurring at a given processor. Reducing the number of context switches leads to more efficient use of the processor. The threshold mechanism of the present invention is not visible at the processing node, i.e. no additional complexity in the node is required.

The present invention addresses the aforementioned disadvantages by providing a threshold for unblocking blocked processing nodes to reduce the overhead of context switches. In addition, the present invention can be extended by a mechanism that prevents deadlocks or data stuck in a buffer. Exemplary extensions may delay the notification to the consumer or delay further work in the low priority system to remove all thresholds when the system is in an 'idle' state. Or is the timeout for the threshold that determines the maximum time.

1 shows a low priority producer component 100 connected to a high priority consumer component 110 via a buffer component 120.

2A shows a buffer fill and context switch 200 for a low priority producer component production buffer for the high priority consumer component of FIG. 1 when no threshold is used.

2B shows a buffer fill and context switch 210 for a low priority producer component production buffer for the high priority consumer component of FIG. 1 when a threshold of 5 is used.

3 illustrates a state transition diagram for one embodiment of the present invention with a threshold of two associated with a buffer that can hold three packets.

The system and method of the present invention reduces the number of context switches that result from passing packets to higher priority streaming components in a system with a pre-emptive priority based scheduler. In general, reducing the number of context switches results in better performance but increases latency.

In a preferred embodiment, the buffer threshold is a mechanism that delays the signaling of blocked consumer components until the packet is available to the buffer, i.e., until the threshold amount of packets is present in the buffer. When the threshold of the buffer is set to x, the waiting, ie blocked component associated with this buffer is signaled only when x packets are available to the buffer.

1 shows a low priority producer component 100 coupled to a high priority consumer component 110 via a buffer component 120, all of which are on the same processor. FIG. 2A shows the filling of the buffer component 120 of FIG. 1 when a data packet is passed, that is, consumed immediately after being produced. That is, when producer component 100 places a packet in buffer 120, component 100 may be immediately preempted by consumer component 110 (assuming consumer component 110 is ready to execute). . When the consumer component 110 is ready and waits for new input again, the producer component 100 is restarted. As shown in FIG. 2A, the number of context switches 200 as a result of this communication depends on the frequency of passing packets. 2B shows the same situation except that the buffer has an associated threshold of five. The number of context switches 210 is reduced by a factor equal to approximately five. This reduction occurs because the consumer component 110 first consumes all five available packets in bursts and then waits for new input when the producer component 100 restarts. The producer component 100 may produce five packets before being preempted by the consumer component 110. The irregularities in both Figures 2A and 2B are due to several reasons, such as when the entire packet is signaled as available in the buffer, for example when the consumer component 110 is signaled that there are no empty packets. Triggered when the consumer component 110 is not ready to run.

Packets in the buffer are not available to the consumer component unless the threshold associated with this buffer has been reached. For example, due to the end of the file for producer input, it is also possible that this packet placed within the buffer component 120 by the producer component 100 is not available to the consumer component 110. In this case, extra care must be taken to ensure that packets remaining in the buffer 120 are flushed (ie processed by the consumer).

This attention is required so that, for example, using a buffer threshold that is too high does not cause deadlock, for example, the number of packets produced is insufficient to reach the buffer threshold. The basic example is that if four packets are circulating through the system, setting the threshold to 5 will allow the system to lock up since the threshold is never reached. So the basic rule is to make the threshold equal or lower than the amount of packets produced. In more complex systems, where the availability of a packet depends on the availability of other packets, this simple rule may not be sufficient, and more complex rules are required that take into account multiple thresholds.

Moreover, the selection of the buffer threshold should minimize the increase in the chain delay caused by the use of this threshold. In almost all cases, it is desirable to have a low latency (for example, audio can only be delayed by 2 milliseconds before the end user starts to know this audio), so even a system that allows a threshold of 10 Even if 10 packets are cycled within, the low latency requirement may indicate a suboptimal lower threshold setting for the context switch overhead.

Initially, the buffer threshold is not active. When the component is blocked or the file is terminated, a special command packet is sent to flush the packets held by the buffer component through a cascade action. A possible state for a buffer that can hold three packets and has a threshold set to two is shown in FIG. 3. The following state transitions are possible:

Take step 310, where the packet is added to the buffer by the sender (310).

Take step 320: step 320, where the packet is successfully removed from the buffer by the receiver

Attempt but fail at step 330: Consumer attempts to get a packet from the buffer but fails because the buffer is empty (330). This activates the threshold mechanism.

Flushing in step 340: the flush command deactivating the threshold 340, so that the consumer can get the packet even though the threshold has not been reached.

Notifying the consumer at step 350: reaching a threshold and discovering that the consumer may begin obtaining packets from the buffer 350

After the transition to get but fails, the context switch is prevented because the consumer is not scheduled until it knows there are two packets in the buffer. This state transition diagram can be extended in a simple way to include larger buffers and higher thresholds.

Although embodiments of the invention described herein are preferably implemented in software, all or some of the embodiments described above may be implemented using separate hardware elements and / or logic circuits.

In this regard, the present invention has been described with respect to specific exemplary embodiments. However, the present invention is not limited to the above-described embodiments and modifications thereof, and one of ordinary skill in the art will be able to make various changes and modifications without departing from the spirit and scope of the appended claims. I can understand.

As described above, the present invention can be used for controlling the exchange of data packets between producers and consumers residing on the same CPU.

Claims (14)

An apparatus for controlling a switch of context between an execution context of a producer of a packet and an execution context of a consumer of this packet, A buffer for internal storage of the packet by the producer and removal of the packet by the consumer, A count for incrementing and decrementing in response to storage of the packet in the buffer and removal of the packet from the buffer, respectively; A threshold imposed on the count, the threshold having a preset value and an on and off state; A limit value for the count, the limit value having a preset value, As the first means, (a) delaying the producer from the switch in the context to the consumer's execution context if the threshold is on and the count is less than the predetermined value of the threshold, wherein the first means Set the threshold to off before the context is switched, (b) delay the producer's delay from the switch in the context to the consumer's execution context when the threshold is on and a buffer flush is required to cause the consumer to process the remaining packets in the buffer. Stop, where the first means sets the threshold off before the context is switched, With the first means, Second means for setting the threshold to on and directing a context switch to the producer if the count is zero And a device for controlling a context switch. The apparatus of claim 1, wherein the preset value of the threshold value is greater than a preset value of the threshold value. The apparatus of claim 1, wherein the first and second means are implemented in software. The apparatus of claim 1, wherein the first and second means are implemented with control logic. The apparatus of claim 1, wherein the first and second means are a priority based scheduler and the producer has a higher priority than the consumer. 6. The apparatus of claim 5, wherein the preset value of the threshold value is greater than the preset value of the threshold value. 6. The apparatus of claim 5, wherein the priority based scheduler is implemented in software. 6. The apparatus of claim 5, wherein the priority based scheduler is implemented with control logic. An apparatus for controlling the generation of a packet by a producer and for controlling the consumption of the packet by a consumer, the apparatus comprising: A buffer storage for storing packets therein, the buffer having a threshold and a threshold imposed on the number of packets stored in the buffer, the threshold and the threshold having respective preset values, Thresholds are buffer stores, which have on and off states, Control logic Including; When the threshold is off, the control logic causes the producer to generate a packet and store it in the buffer store and direct the context switch to the consumer, When the threshold is on, the control logic causes the producer to generate a packet and store the packet in the buffer store and to the consumer until the number of packets stored in the buffer store is equal to the threshold. Delay the context switch, and then the control logic sets the threshold off and directs the context switch to the consumer's context, When the threshold is on and a buffer flush is required, the control logic sets the threshold to off and causes the scheduler to switch to the consumer's execution context to process the remaining packets in the buffer. , When the buffer is empty, the control logic sets the threshold on and directs a context switch to the producer, Device for controlling the generation and consumption of packets. 10. The apparatus of claim 9, wherein the predetermined value of the threshold value is greater than a predetermined value of the threshold value. A method of controlling a context switch between a context of a packet producer and a context of a consumer of a packet, Providing a threshold and a limit for the number of generated packets, the threshold and limit having respective preset values, the threshold being on and off ( providing a threshold and a threshold having an off state; When the context is the context of the producer and the threshold is off, the producer performs a step of generating a packet while directing the switch of the context to the context of the consumer, When the context is the context of the producer and the threshold is on, the producer, (a) generating a threshold number of packets while not directing the switch of the context to the context of the consumer; (b) when the threshold number of packets has been generated, setting the threshold off Performing the step, When the context is the context of the consumer, the consumer, (c) consuming a packet generated by the producer; (d) when there are no more packets to be consumed, A substep of setting the threshold on; Substep of switching the context to the producer's context Steps to perform A method for controlling a switch of context, comprising. 12. The method of claim 11, wherein the preset value of the threshold value is greater than the preset value of the threshold value. 12. The method of claim 11, further comprising providing a buffer for storing packets generated by the producer, Wherein each of the generating steps further comprises storing the generated packet in the provided buffer. The method of claim 13, wherein the preset value of the threshold value is greater than the preset value of the threshold value.

Images