CROSS REFERENCES

[0001] The present Application claims the benefit of U.S. Patent Application No.

13/252,276, entitled "Inter-Processor Communication Apparatus and Method," filed on October 4, 2011, the disclosure of which is expressly incorporated by reference in its entirety.

BACKGROUND

[0002] Computer devices utilizing multiple processors are well known in the art, and are in wide use. Typically, in these devices, each processor receives data to be processed, performs certain calculations and sends the processed data to be further processed by a different processor. The data to be processed by each of the processors is saved in buffers in memory, which is typically a shared resource. The sender selects a buffer in which to store a message, checks if the buffer is available, then begins to write, which requires more than one cycle. Thus, it is important to ensure mutual exclusivity, so that no buffer is allocated to two processors simultaneously. Thus, no two processors will write to the same buffer at the same time. Intercommunication between these processors is accomplished by sending messages from one to the other.

[0003] Sending a message from a first processor to a second processor is carried out by the operating system. The first processor notifies the operating system that a message addressed to a second processor is stored at a certain address in the memory. The operating system stops the receiving processor and provides the address to a buffer in which the message is stored to the second processor. The second processor reads the message stored at the received buffer, and processes the data stored in that buffer. The second processor then notifies the operating system that the data is ready for further processing, or is ready to be used.

[0004] A managing scheme can be implemented by the operating system to control and coordinate the operation of the processers to ensure mutual exclusivity. However, utilizing the operating system is expensive in terms of resources, as each time a message is delivered the operating system must intervene, causing a bottle neck and requiring large overhead. [0005] Accordingly, there is a long felt need for a device and method for improved inter- processor communication, and it would be very desirable if such a device and method operated without requiring intervention by the operating system

SUMMARY

[0006] The present invention relates to inter-processor communication apparatus and methods which are implemented largely or entirely in hardware and do not require intervention by the operating system.

[0007] According to a first exemplary embodiment, an inter-processor communication apparatus for communication between two processors having a shared memory includes: an arbitrated bus coupling the processors to one another and to the shared memory; a plurality of buffers in the shared memory, each of the buffers associated with one of the processors; and at least one pair of hardware queues coupled to each of the processors, the pair of hardware queues holding pointers to each of the buffers associated with that processor. One of the pair of queues may be associated with empty buffers of that processor while a second of the pair of queues may be associated with buffers containing messages for that processor.

[0008] According to certain examples, each processor may be provided with more than one pair of queues. Each pair of queues can be used, for example, to holding pointers to data of a different priority or type. For example, a first pair of the queues associated with one of the processors may hold data pointers for high priority data and a second pair of queues associated with the one of the processors may hold pointers for lower priority data.

[0009] According to certain examples, the first queue of the pair of queues for each processor may include a queue to which only that processor is able to write. The second queue of the pair of queues for each processor may include a queue which only that processor is able to read. [0010] According to certain examples, the bus may include a bus configured to guarantee mutually exclusive reading and writing for each of the queues associated with the processors. According to certain examples, at least one of the queues may be configured to return a null value in response to a pop operation when that queue is empty. In certain examples, at least one or more of the queues may include a First In First Out (FIFO) queue. [0011] According to a second exemplary embodiment, a method of providing inter- processor communication (IPC) between a first processor and a second processor, where the first and second processors are coupled to a shared memory having buffers each of which are associated with the first processor or the second processor is provided. The method may include: popping, by the first processor, a first pointer from a first hardware queue of the second processor, the first hardware queue associated with empty buffers of the second processor, and the first pointer associated with one of the empty buffers; placing a message to the second processor from the first processor in the empty buffer associated with the first pointer; and pushing, by the first processor, the first pointer to a second hardware queue of the second processor, the second hardware queue associated with buffers containing messages for the second processor.

[0012] According to certain examples, the method may further include attempting, by the first processor, to pop a second pointer from the first queue of the shared memory and receiving a null pointer, the null pointer indicating that the first queue is empty. In certain examples, the first processor may continue to periodically attempt to pop the second pointer from the first queue of the shared memory until a non-null pointer is received from the first queue.

[0013] According to certain examples, at least two pairs of queues may be associated with the second processor, each pair configured to hold pointers for a different priority of data. In certain examples, the first queue for the second processor may include a queue to which only the second processor is able to write, and the second queue for the second processor may include a queue which only the second processor is able to read. In certain examples, the first processor and the second processor may be communicatively coupled with an arbitrated bus configured to provide mutually exclusive reading and writing for each of the queues. In certain examples, at least one of the queues may include a FIFO queue.

[0014] According to a third exemplary embodiment, an apparatus may be provided for inter-processor communication between a first processor and a second processor, wherein the first and second processors are coupled to a shared memory having buffers each of which are associated with the first processor or the second processor. The apparatus may include:

means for popping, by the first processor, a first pointer from a first hardware queue of the second processor, the first hardware queue associated with empty buffers of the second processor, and the first pointer associated with one of the empty buffers; means for placing a message to the second processor from the first processor in the empty buffer associated with the first pointer; and means for pushing, by the first processor, the first pointer to a second hardware queue of the second processor, the second hardware queue associated with buffers containing messages for the second processor.

[0015] According to a fourth exemplary embodiment, a computer program product be provided for inter-processor communication (IPC) between a first processor and a second processor, wherein the first and second processors are coupled to a shared memory having buffers each of which are associated with the first processor or the second processor. The computer program product may include a computer readable storage device. The computer readable storage device may be configured to store computer readable program code that, when executed by at least the first processor, causes the first processor to: pop a first pointer from a first hardware queue of the second processor, the first hardware queue associated with empty buffers of the second processor, and the first pointer associated with one of the empty buffers; place a message to the second processor from the first processor in the empty buffer associated with the first pointer; and push the first pointer to a second hardware queue of the second processor, the second hardware queue associated with buffers containing messages for the second processor.

[0016] According to a fifth exemplary embodiment, a method is provided of providing inter-processor communication (IPC) between a first processor and a second processor, where the first and second processors are coupled to a shared memory having buffers each of which are associated with the first processor or the second processor. The method may include: the popping, by the first processor, a first pointer from a first hardware queue of the first processor, the first queue associated with messages for the first processor; processing, by the first processor, a message from the second processor stored at a buffer of the shared memory associated with the first pointer; and pushing, by the first processor, the first pointer to a second hardware queue of the first processor, the second hardware queue associated with empty buffers of the first processor.

[0017] According to certain examples, the method may include popping, by the first processor, a second pointer from the first queue in response to the pushing the first pointer to the second queue. In certain examples, an alert from at least one of the queues may be received at the first processor. The alert may include an interrupt to the first processor. In certain examples, the alert may include at least one of: an alert that the first queue is at least partially full or an alert that the second queue is at least partially empty. In certain examples, the first processor may check periodically for pending pointers associated with the first queue.

[0018] According to certain examples, at least two pairs of queues may be associated with the first processor, each pair configured to hold pointers for a different priority of data. In certain examples, the first queue for the first processor may include a queue which only the second processor is able to read, and the second queue for the first processor may include a queue to which only the second processor is able to write. In certain examples, the first processor and the second processor may be communicatively coupled with an arbitrated bus configured to provide mutually exclusive reading and writing for each of the queues. In certain examples, at least one of the queues may include a FIFO queue.

[0019] According to a sixth exemplary embodiment, an apparatus may be provided for inter-processor communication between a first processor and a second processor, wherein the first and second processors are coupled to a shared memory having buffers each of which are associated with the first processor or the second processor. The apparatus may include: means for popping, by the first processor, a first pointer from a first hardware queue of the first processor, the first queue associated with messages for the first processor; means for processing, by the first processor, a message from the second processor stored at a buffer of the shared memory associated with the first pointer; and means for pushing, by the first processor, the first pointer to a second hardware queue of the first processor, the second hardware queue associated with empty buffers of the first processor.

[0020] According to a seventh exemplary embodimenta computer program product be provided for inter-processor communication (IPC) between a first processor and a second processor, wherein the first and second processors are coupled to a shared memory having buffers each of which are associated with the first processor or the second processor. The computer program product may include a computer readable storage device. The computer readable storage device may be configured to store computer readable program code that, when executed by at least the first processor, causes the first processor to: pop a first pointer from a first hardware queue of the first processor, the first queue associated with messages for the first processor; process a message from the second processor stored at a buffer associated with the first pointer; and push the first pointer to a second hardware queue of the first processor, the second hardware queue associated with empty buffers of the first processor.

BRIEF DESCRIPTION OF THE DRAWINGS

[0021] A further understanding of the nature and advantages of the present invention may be realized by reference to the following drawings. In the appended figures, similar components or features may have the same reference label. Further, various components of the same type may be distinguished by following the reference label by a dash and a second label that distinguishes among the similar components. If only the first reference label is used in the specification, the description is applicable to any one of the similar components having the same first reference label irrespective of the second reference label.

[0022] Figure 1 is a block diagram illustration of a processing unit including inter- processor communication apparatus, constructed and operative in accordance with one embodiment;

[0023] Figure 2 is a flow chart illustration of one operation of the processing unit of Figure 1 , according to one embodiment; and

[0024] Figure 3 is a block diagram illustration of a processing unit including inter- processor communication apparatus, according to another embodiment.

DETAILED DESCRIPTION

[0025] The present disclosure relates to the design of a multi-processor inter-processor communication (IPC) infrastructure for supporting message interchange between multiple agents, residing on multiple different processors, on a particular chip or system. This apparatus may include a memory coupled to multiple processors, all typically coupled by a shared bus with an arbitration mechanism. All the processors may be mutually accessible by one another via the shared bus and the memory. Each processor may have defined buffer space, with associated addresses in the memory, for storing received data, and a mechanism for informing the processor when a message or data is waiting for processing. According to certain embodiments of the invention, each processor may include at least one first hardware queue, for holding pointers to empty buffers, and at least one second hardware queue, for holding pointers to buffers with received messages. These queues are coupled to the shared bus and are accessible by all the processors.

[0026] In the examples of the following description, the hardware queues are described in the context of First in First Out (FIFO) queues. However, it should be understood that other types of hardware queues (e.g., Last In First Out (LIFO) queues) may also be used.

[0027] In order to simplify the description of the invention, the term "empty buffer FIFO", as used in this application, shall refer to a FIFO, LIFO, or other special hardware memory for holding pointers to empty buffers. Similarly, the term "message FIFO" as used in this application, shall refer to a FIFO, LIFO, or other special hardware memory for holding pointers to buffers with received messages.

[0028] As described below, when a first processor wants to send a message or data to a second processor for processing, the first processor pops one pointer from the empty buffer FIFO of the second processor. The popped pointer is an address associated with the second processor pointing to a buffer in the data memory to which the first processor can write the data. The first processor then pushes the pointer into the message FIFO of the second processor, indicating that a message is waiting.

[0029] The second processor periodically pops the pointers from the message FIFO and reads and process the data stored in the buffers pointed to by these pointers. The second processor then pushes the pointers back to the empty buffer FIFO associated with the second processor.

[0030] In one particular embodiment, the entire process occurs without intervention by the operating system, thereby reducing processing time and reducing resources required for inter- processor communication. It will further be appreciated that, since a pointer is popped from the empty buffer FIFO in a single cycle of a shared bus, there is no possibility that two processors attempting to get a buffer address will get the same pointer, because mutual exclusivity is built into the system bus.

[0031] Thus, the following description provides examples, and is not limiting of the scope, applicability, or configuration set forth in the claims. Changes may be made in the function and arrangement of elements discussed without departing from the spirit and scope of the disclosure. Various embodiments may omit, substitute, or add various procedures or components as appropriate. For instance, the methods described may be performed in an order different from that described, and various steps may be added, omitted, or combined. Also, features described with respect to certain embodiments may be combined in other embodiments.

[0032] Figure 1 is a block diagram of a processing unit 10 constructed and operative in accordance with one or more embodiments. For ease of description, processing unit 10 is illustrated as having two processors. However, alternatively, any suitable number of processors can be incorporated in the unit. Processing unit 10 includes a first processor 12a and a second processor 12b. Processors 12a and 12b are both coupled to a memory device 14 via a bus 16. Memory device 14 includes a plurality of buffers 15a, 15b each identified by a unique address. According to one embodiment, buffers 15a are associated with first processor 12a and buffers 15b are associated with second processor 12b. In this way, the data stored in buffers 15a is directed for processing by processor 12a, and the data stored in buffers 15b is directed for processing by processor 12b. All the buffers in memory device 14 are accessible by first and second processors 12a, 12b via bus 16, which includes an arbitration mechanism. It will be appreciated that memory device 14 can be a separate memory device, as illustrated, or, alternatively, buffers from memory can be incorporated inside each processor 12a, 12b, as long as they are accessible by all the other processors. [0033] First processor 12a is further coupled for writing to an empty buffer FIFO 20a configured for holding pointers to certain buffers 15 a, associated with processor 12a, and which are currently empty, i.e. have no pending messages stored therein. In addition, first processor 12a is coupled for reading to a message FIFO 22a configured for holding pointers to other buffers 15a which include messages pending to be processed by first processor 12a. [0034] Similarly, second processor 12b is coupled for writing to an empty buffer FIFO 20b configured for holding pointers to those buffers 15b associated with processor 12b, which are currently empty, i.e. have no pending messages stored therein. In addition, second processor 12b is coupled for reading to a message FIFO 22b configured for holding pointers to those buffers 15b which include messages pending to be processed by second processor 12b. [0035] As can be seen, first processor 12a is coupled for reading from the empty buffer

FIFO 20b of second processor 12b and is coupled for writing to message FIFO 22b of second processor 12b via bus 16. Similarly, second processor 12b is coupled for reading to the empty buffer FIFO 20a and is coupled for writing to the message FIFO 22a of processor 12a, via bus 16. Bus 16 enables communication between the first processor 12a and FIFOs 20b and 22b of second processor 12b, and the communication between second processor 12b and FIFOs 20a and 22a of first processor 12a. When the processing unit includes more than two processors, it will be appreciated that each processor is coupled to at least one FIFO to which only it can write but from which all the other processors can read, and to at least one FIFO from which only it can read and to which all the other processors can write. In addition, bus 16 is coupled to memory device 14, thus, allowing communication between first and second processor 12a and 12b and memory device 14 via the bus 16. It is a particular feature that bus 16 guarantees mutually exclusive reading and writing. This means that if two processors try to read from or write to any FIFO at the same time, the bus will impose an order between the two competing processors. In this way, each time only one processor reads or writes from or to a shared FIFO. It will be appreciated that communication between the different components of processor 10 may be implemented in another fashion from a bus, for example, by

implementing a message switching mechanism.

[0036] Figure 2 is a flow chart illustrating one method of operation of processing unit 10 of Figure 1, according to one embodiment. When data is to be sent from the second processor to the first processor, the second processor pops one pointer from the empty buffer FIFO of the first processor (block 42). The second processor stores the data for the first processor in the buffer corresponding to the popped pointer (block 44). The data may be in the form of a message containing the data and/or a processing instruction, etc. Upon completion of data writing, the second processor pushes the popped pointer into the message FIFO of the first processor (block 46) to notify it that a message is waiting for it in the location pointed to by the pointer. When the empty buffer FIFO is empty, meaning no buffer space associated with that particular processor is empty or available, the pop operation returns a null pointer. In this case, processor one may choose to continue attempting the pop operation until it gets a non null pointer (i.e., until a buffer has become available) or to do something else and perform the message sending at another time. This mechanism enables the message sending operation to be non blocking. That is, the sender is not stopped if the message send operation can not be performed, as occurs in conventional systems. [0037] According to one embodiment, the first processor periodically checks its message FIFO. Whenever its message FIFO contains a pointer, the first processor pops the pointer out (block 48). The first processor reads and processes the message stored in the memory buffer corresponding to the popped pointer (block 50). The first processor then pushes the pointer back into its empty buffer FIFO (block 52) making this buffer available, once again, for storing a message for the first processor.

[0038] It will further be appreciated that this operation can be carried out in the opposite direction, in which the first processor sends data or a message to the second processor. In this case, the first processor pops one pointer from the empty buffer FIFO of the second processor and stores data in a data buffer, associated with the second processor, corresponding to the popped pointer. The first processor then pushes the pointer into the message FIFO of the second processor (not shown in the diagram). The second processor will pop the pointer from its message FIFO, process the data stored in the corresponding data buffer, and push the pointer back into its empty buffer FIFO. [0039] As mentioned hereinabove, according to one embodiment, each processor is programmed to check, periodically, its message FIFO for pending pointers. This can be implemented by means of a loop. This means, for example, automatically after processing data associated with one pointer, the pointer is pushed back to the empty buffer FIFO and the next pointer is popped from the message FIFO. Alternatively, after a pre-selected time period has passed, the message FIFO can be checked again. It will be appreciated that, when the message FIFO is empty, and the processor has processed all the pending messages and pushed the pointers back to the empty buffer FIFO, the processor can perform other, unrelated operations, while periodically checking its message FIFO.

[0040] Alternatively or in addition, the message FIFO may include alert mechanism hardware, alerting the processor of the status of pointers in its FIFO. This logic hardware checks the status of the FIFOs and outputs a signal according to the number of pointers therein. The mechanism can be set by the user so that one of the signals is connected to the interrupt of the processor, alerting it to the status of the FIFO. According to one embodiment, an alert may be generated each time a pointer is pushed into a message FIFO. Alternatively, an alert may be generated, for example, when the message FIFO contains a preset number of pointers. The alert system would then signal the processor to pop the pointers from the message FIFO and to process the data stored in the corresponding buffers. Alternatively, different alerts can be generated to indicate that the empty buffer FIFO is completely or partially empty, or that the message FIFO is partially or completely full. The alert signal can be set so that the receipt of a selected number of messages will be interpreted as "almost full" and be connected to the interrupt. Or the user may prefer to connect the "quarter full" number of messages to the interrupt, for more frequent review of incoming messages.

[0041] Figure 3 is a block diagram of a processing unit 60 having an IPC constructed and operative in accordance with another embodiment. Processing unit 60 operates in

substantially the same manner as processing unit 10 of Figure 1. Processing unit 60 includes a plurality of processors, here illustrated as four processors 61 to 64, and a memory device 70 coupled by a bus 66. Each one of processors 61-64 is coupled to two empty buffer FIFOs 61a-64a and two message FIFOs 61b-64b, respectively. Memory device 70 includes a plurality of buffers 72, each associated physically or virtually with one of processors 61-64. At least two pairs of FIFOs are provided associated with each processor to permit one pair to act as the empty buffer and message FIFOs for high priority messages and the second pair to act as the empty and message FIFOs for low priority messages. It will be appreciated that further pairs of FIFOs can be coupled to each processor as required, for different types, classes, priorities, etc.

[0042] Each FIFO is configured to hold a preset number of pointers, preferably

corresponding to the number of buffers associated with each processor. For example, the FIFO may be adapted to hold 128 pointers corresponding to 128 buffers 72 in the memory device 70. Accordingly, the memory device 70 may include 128 buffers for each of the four processors 61-64, i.e. 512 buffers. Associating each buffer with one of processors 61-64 is preferably carried out during initialization of the processing unit 60, for example, when the processing unit is turned on.

[0043] It will be appreciated that the size of each pointer may vary in accordance with the size of memory device 70. For example, when the size of memory device 70 is 4Giga bytes, each pointer must be 32 bits. It will be further appreciated that memory device 70 may be formed as an integral part of processing unit 60, or alternatively, may be any external memory device, as known in the art. In the latter case, processing unit 60 includes appropriate coupling means for coupling to the memory device, as known in the art. [0044] Bus 68 in processing unit 60 may be configured to control the communication between processors 61-64, so as to allow each processor to pop and push a pointer to or from another processor. For example, if both processor 61 and processor 63 must send data to be processed by processor 64, both processors 61 and 63 must pop a pointer from empty buffer FIFO 64a and push it into FIFO 64b. In this case, the arbitration mechanism in bus 68 controls the order of the communication, so as to ensure mutual exclusivity.

[0045] The detailed description set forth above in connection with the appended drawings describes exemplary embodiments and does not represent the only embodiments that may be implemented or that are within the scope of the claims. The term "exemplary" used throughout this description means "serving as an example, instance, or illustration," and not "preferred" or "advantageous over other embodiments." The detailed description includes specific details for the purpose of providing an understanding of the described techniques. These techniques, however, may be practiced without these specific details. In some instances, well-known structures and devices are shown in block diagram form in order to avoid obscuring the concepts of the described embodiments.

[0046] Information and signals may be represented using any of a variety of different technologies and techniques. For example, data, instructions, commands, information, signals, bits, symbols, and chips that may be referenced throughout the above description may be represented by voltages, currents, electromagnetic waves, magnetic fields or particles, optical fields or particles, or any combination thereof.

[0047] The various illustrative blocks and modules described in connection with the disclosure herein may be implemented or performed with a general-purpose processor, a digital signal processor (DSP), an application specific integrated circuit (ASIC), a field programmable gate array (FPGA) or other programmable logic device, discrete gate or transistor logic, discrete hardware components, or any combination thereof designed to perform the functions described herein. A general-purpose processor may be a

microprocessor, but in the alternative, the processor may be any conventional processor, controller, microcontroller, or state machine. A processor may also be implemented as a combination of computing devices, e.g., a combination of a DSP and a microprocessor, multiple microprocessors, one or more microprocessors in conjunction with a DSP core, or any other such configuration. [0048] The functions described herein may be implemented in hardware, software executed by a processor, firmware, or any combination thereof. If implemented in software executed by a processor, the functions may be stored on or transmitted over as one or more instructions or code on a computer-readable medium. Other examples and implementations are within the scope and spirit of the disclosure and appended claims. For example, due to the nature of software, functions described above can be implemented using software executed by a processor, hardware, firmware, hardwiring, or combinations of any of these. Features implementing functions may also be physically located at various positions, including being distributed such that portions of functions are implemented at different physical locations. Also, as used herein, including in the claims, "or" as used in a list of items prefaced by "at least one of indicates a disjunctive list such that, for example, a list of "at least one of A, B, or C" means A or B or C or AB or AC or BC or ABC (i.e., A and B and C).

[0049] Computer-readable media includes both computer storage media and

communication media including any medium that facilitates transfer of a computer program from one place to another. A storage medium may be any available medium that can be accessed by a general purpose or special purpose computer. By way of example, and not limitation, computer-readable media can comprise RAM, ROM, EEPROM, CD-ROM or other optical disk storage, magnetic disk storage or other magnetic storage devices, or any other medium that can be used to carry or store desired program code means in the form of instructions or data structures and that can be accessed by a general-purpose or special- purpose computer, or a general-purpose or special-purpose processor. Also, any connection is properly termed a computer-readable medium. For example, if the software is transmitted from a website, server, or other remote source using a coaxial cable, fiber optic cable, twisted pair, digital subscriber line (DSL), or wireless technologies such as infrared, radio, and microwave, then the coaxial cable, fiber optic cable, twisted pair, DSL, or wireless technologies such as infrared, radio, and microwave are included in the definition of medium. Disk and disc, as used herein, include compact disc (CD), laser disc, optical disc, digital versatile disc (DVD), floppy disk and blu-ray disc where disks usually reproduce data magnetically, while discs reproduce data optically with lasers. Combinations of the above are also included within the scope of computer-readable media. [0050] The previous description of the disclosure is provided to enable a person skilled in the art to make or use the disclosure. Various modifications to the disclosure will be readily apparent to those skilled in the art, and the generic principles defined herein may be applied to other variations without departing from the spirit or scope of the disclosure. Throughout this disclosure the term "example" or "exemplary" indicates an example or instance and does not imply or require any preference for the noted example. Thus, the disclosure is not to be limited to the examples and designs described herein but is to be accorded the widest scope consistent with the principles and novel features disclosed herein.

[0051] What is claimed is: