Method and apparatus for weighted message passing

This application claims the benefit of priority to previously filed U.S. provisional patent application Ser. No. 60/989,666, filed Nov. 21, 2007, entitled METHOD AND APPARATUS FOR SCHEDULE-DRIVEN AUTO-REORDERING MESSAGE PASSING SCHEME IN DEEPLY EMBEDDED PARALLEL MULTIMEDIA SYSTEMS. That provisional application is hereby incorporated by reference in its entirety.

This present application is related to the following U.S. Patent Application, which is assigned to the assignee hereof and incorporated herein by reference in its entirety: U.S. patent application Ser. No. 12/271,814, entitled METHOD AND SYSTEM FOR MESSAGE MULTICASTING, and filed concurrently herewith.

1. Field of the Invention

The present invention relates generally to message passing, and more particularly to message passing in multimedia systems.

2. Description of Related Art

The need for greater processing power in multimedia systems along with power consumption constraints has led to a new era of parallel computing or multi-core designs. One feature of parallel computer architecture is its inter-process communication (IPC). Message passing is one of the methods used for IPC. A prior art message passing system consists of FIFOs wherein the message buffers are written by one microprocessor (a “producer”) and read by another microprocessor (a “consumer”) respectively. FIGS. 1A and 1B illustrate a prior art message passing system consisting of a simple FIFO (First-In-First-Out). A message queue may have a start pointer and an end pointer, and the queue length therebetween is the message queue length. A write pointer and a read pointer are maintained and used to indicate a portion for previously read data, a portion for unread data, and a portion available for new data. When a producer writes a message to the queue, the write pointer is incremented, and when a consumer reads a message from the queue, the read pointer is incremented. FIG. 1A illustrates an un-wrapped state of operation wherein the write pointer is less than the read pointer, and FIG. 1B illustrates a wrapped state of operation in which the previously read data and the data to be written share the same portion.

In the system shown in FIGS. 1A and 1B , a message can be consumed by one consumer, since once a message is consumed, the read pointer in the FIFO increments, and the message is removed from the FIFO. To have a message from a producer be read by multiple consumers, the message has to be written in multiple queues, which considerably increases memory footprint. In addition, multiple FIFOs have to be read.

Another problem of the prior art system shown in FIGS. 1A and 1B is its inefficiency in system latency. The FIFO treats all messages the same way according to the first in first out logic. Since sub-computations involved in different applications in a multimedia system may have variable latencies, different incoming messages may consume varying amounts of time to process, thus leading to unpredictable response time. However, real time responsiveness is important in multimedia applications.

Embodiments of the present invention are described herein with reference to the accompanying drawings, similar reference numbers being used to indicate functionally similar elements.

FIGS. 1A and 1B illustrate a prior art system for message passing.

FIG. 2A illustrates a system for message passing according to one embodiment of the present invention.

FIG. 2B illustrates a sorter in a system for message passing according to one embodiment of the present invention.

FIG. 3 is a flow chart of a method for message passing according to one embodiment of the present invention.

FIGS. 4A-4B illustrate message queues generated in a method for message passing according to one embodiment of the present invention.

The present invention provides a method and system for message passing which weights messages in a queue according to urgency of consumption. A timestamp indicating the urgency of consumption may be assigned to a message, and messages may be automatically re-ordered based on their timestamps, following a first-in-weighted-out (FIWO) logic. Such a schedule-driven auto-reordered message passing system may provide increased efficiency and lower latency, and is independent of the configuration of memory types. Advantages of the present invention will become apparent from the following detailed description.

A weight may be assigned to each message according to urgency of consumption. In one embodiment, the weight is a time stamp. One example of the time stamp is an early delay deadline (EDD) which may be included in the header of a message, e.g., by the producer of the message. The EDD may indicate when a message must be pulled out of the queue and consumed. For example, video and audio processing may have different real time bounds. In audio systems, a packet may represent a bigger scale in time. A loss or real-time miss of an audio packet may impact the user's experience more significantly than that of a video packet. Thus, packet throughput for audio is more time critical than that for video, and so audio messages may have a higher urgency of consumption, and may be assigned earlier EDDs.

FIG. 2A illustrates a system for message passing according to one embodiment of the present invention. A queue of messages may sit in a memory interface 201 , which may be a random access memory (RAM) or a double data rate (DDR) memory. A start pointer 204 and an end pointer 205 may indicate the start and end of the queue respectively. A read pointer 202 may indicate the location of the message in the latest read operation, and a write pointer 203 may indicate the location of the message in the latest write operation. A pointer may be, e.g., a register. A QLEN computation module 206 may be coupled to a start pointer 204 and an end pointer 205 , compute the queue length and forward it to the queue length module 207 . The queue length module 207 may temporally store the queue length, and forward it to a Read/write Queues status module 208 , which in turn is coupled to a queue status module 209 . The Read/write Queue status module 208 may store information related to the read pointer 202 and the write pointer 203 . The queue status module 209 may store the information about the queue, e.g., the queue length, the queue length of the data to be read and the available space for new data.

A message scheduler 210 may include scheduling logic implemented by hardware, firmware, or software and may be added to the message passing. It may interact with the pointers to get EDDs of the messages in the queue, and generate an order to access the messages according to their EDDs.

The message scheduler 210 may have a sorter 2101 that identifies, based on the EDDs, the next message which is to be executed. FIG. 2B illustrates a sorter in a message scheduler according to one embodiment of the present invention. The sorter may have a number of slots, each of which may be used for one message. EDDs (e.g., TD 1 , TD 3 , TD 2 and TD 4 ) of messages (e.g., V 1 , A 3 , V 2 and V 4 ) may be filled in the slots, wherein TD 1 is the EDD of the message V 1 , TD 3 is the EDD of the message A 3 , TD 2 is the EDD of the message V 2 , and TD 4 is the EDD of the message V 4 . The sorter 2101 may sort the EDDs, putting the least one first.

The message scheduler 210 may interact with the memory interface 201 on the other side to pull the actual messages according to the order in the sorter.

The sorter 2101 may have a pending bit in each slot, indicating whether the slot is available for the next EDD. When a message is pulled from the queue, its slot in the sorter may be set, indicating that it is empty and available. The pending bit of a slot may be at the beginning of the slot, as shown in FIG. 2B .

The message scheduler 210 may sort the EDDs either at receive time or at request time, and may use an absolute sorting mechanism. Alternatively, to reduce sorting hardware, the message scheduler 210 may only use a fraction of bits of the timestamp and generate the order based on a time interval. In one embodiment, the message scheduler 210 may use 8 bits for the timestamp and the last two bits may provide a granularity of 100 microseconds (μs). Accordingly, the message may tolerate a latency of 100 μs. If there is another message having an EDD of 50 μs, it may be processed earlier.

If a few messages are triggered ready at the same time, a persistency header may be used to get allowable targets. The persistency header is described in the co-pending U.S. patent application Ser. No. 12/271,814, entitled METHOD AND SYSTEM FOR MESSAGE MULTICASTING, which is incorporated herein by reference in its entirety.

FIG. 3 is a flow chart of a method for message passing according to one embodiment of the present invention. The method may be used in the system shown in FIG. 2A , and may manage passing of messages in a queue, each of which has been assigned an EDD. As described above, the EDD may be assigned according to the urgency of consumption of the messages, e.g., an audio message may be assigned an earlier EDD than a video message.

FIG. 4A illustrates one example of the message queue. The message queue may contain video messages V 1 , V 2 , V 4 and an audio message A 3 . The arrival times for the video messages are T 1 , T 2 , T 4 , and the EDD for the video messages are TD 1 , TD 2 , TD 4 . The audio message's arrival time is T 3 , and its EDD is TD 3 . The order of the messages is V 1 , V 2 , A 3 , and V 4 .

At 301 , the message scheduler 210 may obtain EDDs of the messages from pointers 204 and 205 , and put them in a sorter, e.g., 2101 .

At 302 , the message scheduler 210 may generate an order to pull the messages based on their EDDs. FIG. 4B illustrates a time sequence of messages in a queue according to one embodiment of the present invention. As shown, although the audio message A 3 arrives later than the video message V 2 , A 3 's EDD, TD 3 , is earlier than V 2 's EDD, TD 2 . To avoid having the messages come out of order as when FIFO is used, the message scheduler 210 may generate an order to pull the messages according to a FIWO (First-In-Weighted-Out) logic. In one embodiment, the sorter may sort the EDDs, putting the least one first. Since A 3 has an earlier EDD, the order to pull the messages may be changed to V 1 , A 3 , V 2 , and V 4 , moving A 3 ahead of V 2 , as shown in FIG. 2B .

At 303 , the message scheduler 210 may check the pending bit in each slot in the sorter, ignoring those which have been set. It should be understood that 303 may be performed before 302 .

At 304 , the message scheduler 210 may pull the actual message with the least EDD in the sorter from the memory interface 201 . Since V 1 has the least EDD, V 1 may be pulled from the queue.

At 305 , a pending bit may be set in the sorter for a message which has been consumed. Since V 1 has been consumed, the pending bit of its slot in the sorter may be set, as shown in FIG. 2B . The next message may get the first empty slot.

The process may return to 301 , and the EDD of the next message may be filled in the first empty slot in the sorter.

Thus, the message scheduler 210 , or its sorter, does not move messages around. Instead, it looks at EDDs and pending bits for every slot, and determines which message should be pulled next and then pull the message. The message pass scheme shown in FIG. 2 is not a queue in which messages get shifted down, but a buffer with valid data and invalid data, and messages may be pulled out according to the valid data.

One advantage of the system shown in FIG. 2A is that, in contrast to a FIFO, the messages in the queue are not removed or collapsed, and may be accessed by another consumer. As a result, it is not necessary to write a message in multiple queues solely for the purpose of being accessed by multiple consumers, and memory footprints may be significantly reduced.

Another advantage of the system shown in FIG. 2A is that it may reduce inefficiencies in system latency. Different applications, e.g., audio and video, may have different latencies. The prior art system shown in FIG. 1 follows a simple FIFO logic and might not pass an audio message, which has a higher urgency of consumption, early enough and may impact end results. The system shown in FIG. 2A passes messages according to their urgency of consumption and consequently may improve user experience significantly.

Another advantage of the system shown in FIG. 2A is that it may reduce memory traffic. In the system shown in FIG. 1 , when there are a number of messages sitting in a message queue, a consumer looking to consume the messages may have to continuously pull to see which is the next message it wants to consume. This causes a lot of memory traffic. Since the message scheduler 210 in FIG. 2A sorts access to the messages according to their urgency of consumption, consumers do not have to pull the queue. This may significantly reduce the memory traffic in the system.

Several features and aspects of the present invention have been illustrated and described in detail with reference to particular embodiments by way of example only, and not by way of limitation. Alternative implementations and various modifications to the disclosed embodiments are within the scope and contemplation of the present disclosure. Therefore, it is intended that the invention be considered as limited only by the scope of the appended claims.