Abstract:
Message synchronization in network processors includes passing data from a producer processor to an inter-processor ring structure, while setting a bit in a register and reading the register by a consumer processor, while clearing the register. Messages are passed by removing data from the ring with the amount of data removed from the ring corresponding to a number of bits set in the register.

Description:
BACKGROUND  
       [0001]     This invention relates to message synchronization between multiple processors.  
         [0002]     It is often necessary to synchronize messages passing between processors. Fast and successful synchronization of messages is vital for high performance systems such as network devices that include network processors. Network processors typically include multiple microengines, and often a core processor to manage the microengines. Often these microengines share work on a common task and are required to pass messages between the microengines.  
         [0003]     Some network processors include a type of register that is known as a self-destruct register. A read from the register returns the current register state (all bits that were set following the last read operation to the register or after a reset) and atomically clears the register. 
     
    
     DESCRIPTION OF DRAWINGS  
       [0004]      FIG. 1  is a block diagram of a network processor.  
         [0005]     FIGS.  2 -A to  2 -D hereinafter  FIG. 2  is a block diagram of a microengine used in the network processor of  FIG. 1 .  
         [0006]      FIG. 3  is a block diagram of showing message passing between microengines.  
         [0007]      FIGS. 4-7  are flow charts depicting aspect of message synchronization.  
     
    
     DETAILED DESCRIPTION  
       [0008]     Referring to  FIG. 1 , a communication system  10  includes a parallel, hardware-based multithreaded processor  12 . The hardware-based multithreaded processor  12  is coupled to a bus such as a PCI bus  14 , a memory system  16  and a second bus  18 . The system  10  is especially useful for tasks that can be broken into parallel subtasks or functions. Specifically hardware-based multithreaded processor  12  is useful for tasks that are bandwidth oriented rather than latency oriented. The hardware-based multithreaded processor  12  has multiple microengines  22  each with multiple hardware controlled threads that can be simultaneously active and independently work on a task.  
         [0009]     The hardware-based multithreaded processor  12  also includes a central controller  20  that assists in loading microcode control for other resources of the hardware-based multithreaded processor  12  and performs other general-purpose computer type functions such as handling protocols, exceptions, and extra support for packet processing where the microengines pass the packets off for more detailed processing such as in boundary conditions. In one embodiment, the processor  20  is a Strong Arm® (Arm is a trademark of ARM Limited, United Kingdom) based architecture. The general-purpose microprocessor  20  has an operating system. Through the operating system the processor  20  can call functions to operate on microengines  22   a - 22   f . The processor  20  can use any supported operating system preferably a real time operating system. For the core processor implemented as Strong Arm architecture, operating systems such as, MicrosoftNT Real-Time, VXWorks and μCUS, a freeware operating system available over the Internet, can be used.  
         [0010]     The hardware-based multithreaded processor  12  also includes a plurality of function microengines  22   a - 22   f . Functional microengines (microengines)  22   a - 22   f  each maintain a plurality of program counters in hardware and states associated with the program counters. Effectively, a corresponding plurality of sets of threads can be simultaneously active on each of the microengines  22   a - 22   f  while only one is actually operating at any one time.  
         [0011]     In one embodiment, there are six microengines  22   a - 22   f  as shown. Other embodiments have more than or less than six microengines. Each of the microengines  22   a - 22   f  has capabilities for processing multiple hardware threads. The six microengines  22   a - 22   f  operate with shared resources including memory system  16  and bus interfaces  24  and  28 . The memory system  16  includes a Synchronous Dynamic Random Access Memory (SDRAM) controller  26   a  and a Static Random Access Memory (SRAM) controller  26   b . SDRAM memory  16   a  and SDRAM controller  26   a  are typically used for processing large volumes of data, e.g., processing of network payloads from network packets. The SRAM controller  26   b  and SRAM memory  16   b  are used in a networking implementation for low latency, fast access tasks, e.g., accessing look-up tables, memory for the core processor  20 , and so forth.  
         [0012]     The six microengines  22   a - 22   f  access either the SDRAM  16   a  or SRAM  16   b  based on characteristics of the data. Thus, low latency, low bandwidth data is stored in and fetched from SRAM, whereas higher bandwidth data for which latency is not as important, is stored in and fetched from SDRAM. The microengines  22   a - 22   f  can execute memory reference instructions to either the SDRAM controller  26   a  or SRAM controller  16   b.    
         [0013]     One example of an application for the hardware-based multithreaded processor  12  is as a network processor. As a network processor, the hardware-based multithreaded processor  12  interfaces to network devices such as a media access controller device e.g., a 10/100 BaseT Octal MAC  13   a  or  a  Gigabit Ethernet device  13   b . As a network processor, the hardware-based multithreaded processor  12  can interface to any type of communication device or interface that receives or sends large amounts of data. Communication system  10  functioning in a networking application could receive a plurality of network packets from the devices  13   a ,  13   b  and process those packets in a parallel manner. With the hardware-based multithreaded processor  12 , each network packet can be independently processed.  
         [0014]     In the arrangement shown in  FIG. 1 , the network processor is part of a network router, but could also be used in a network interface device, switch, and other types of applications. Another example for use of processor  12  is a print engine for a postscript processor or as a processor for a storage subsystem, i.e., RAID disk storage. A further use is as a matching engine. In the securities industry for example, the advent of electronic trading requires the use of electronic matching engines to match orders between buyers and sellers. These and other parallel types of tasks can be accomplished on the system  10 .  
         [0015]     The processor  12  includes a bus interface  28  that couples the processor to the second bus  18 . Bus interface  28  in one embodiment couples the processor  12  to the so-called FBUS  18  (FIFO bus). The FBUS interface  28  is responsible for controlling and interfacing the processor  12  to the FBUS  18 . The FBUS  18  is a 64-bit wide FIFO bus, used to interface to Media Access Controller (MAC) devices.  
         [0016]     The processor  12  includes a second interface e.g., a PCI bus interface  24  that couples other system components that reside on the PCI  14  bus to the processor  12 . The PCI bus interface  24 , provides a high-speed data path  24   a  to memory  16 , e.g., the SDRAM memory  16   a . Through that path data can be moved quickly from the SDRAM  16   a  through the PCI bus  14 , via direct memory access (DMA) transfers. The hardware based multithreaded processor  12  supports image transfers. The hardware based multithreaded processor  12  can employ a plurality of DMA channels so if one target of a DMA transfer is busy, another one of the DMA channels can take over the PCI bus to deliver information to another target to maintain high processor  12  efficiency. Additionally, the PCI bus interface  24  supports target and master operations. Target operations are operations where slave devices on bus  14  access SDRAMs through reads and writes that are serviced as a slave to target operation. In master operations, the processor core  20  sends data directly to or receives data directly from the PCI interface  24 .  
         [0017]     Each of the functional units are coupled to one or more internal buses. As described below, the internal buses are dual, 32 bit buses (i.e., one bus for read and one for write). The hardware-based multithreaded processor  12  also is constructed such that the sum of the bandwidths of the internal buses in the processor  12  exceed the bandwidth of external buses coupled to the processor  12 . The processor  12  includes an internal core processor bus  32 , e.g., an ASB bus (Advanced System Bus) that couples the processor core  20  to the memory controller  26   a ,  26   c  and to an ASB translator  30  described below. The ASB bus is a subset of the so-called AMBA bus that is used with the Strong Arm processor core. The processor  12  also includes a private bus  34  that couples the microengine units to SRAM controller  26   b , ASB translator  30  and FBUS interface  28 . A memory bus  38  couples the memory controller  26   a ,  26   b  to the bus interfaces  24  and  28  and memory system  16  including flashrom  16   c  used for boot operations and so forth.  
         [0018]     Referring to  FIG. 2 , each of the microengines  22   a - 22   f  includes an arbiter that examines flags to determine the available threads to be operated upon. Any thread from any of the microengines  22   a - 22   f  can access the SDRAM controller  26   a , SDRAM controller  26   b  or FBUS interface  28 . The memory controllers  26   a  and  26   b  each include a plurality of queues to store outstanding memory reference requests. The queues either maintain order of memory references or arrange memory references to optimize memory bandwidth. For example, if a thread — 0 has no dependencies or relationship to a thread — 1, there is no reason that threads 1 and 0 cannot complete their memory references to the SRAM unit out of order. The microengines  22   a - 22   f  issue memory reference requests to the memory controllers  26   a  and  26   b . The microengines  22   a - 22   f  flood the memory subsystems  26   a  and  26   b  with enough memory reference operations such that the memory subsystems  26   a  and  26   b  become the bottleneck for processor  12  operation.  
         [0019]     Data functions are distributed amongst the microengines. The data buses, e.g., ASB bus  30 , SRAM bus  34  and SDRAM bus  38  coupling shared resources, e.g., memory controllers  26   a  and  26   b  are of sufficient bandwidth such that there are no internal bottlenecks. As an example, the SDRAM can run a 64 bit wide bus. The SRAM data bus could have separate read and write buses, e.g., could be a read bus of 32 bits wide running at 166 MHz and a write bus of 32 bits wide at 166 MHz.  
         [0020]     The core processor  20  also can access the shared resources. The core processor  20  has a direct communication to the SDRAM controller  26   a  to the bus interface  24  and to SRAM controller  26   b  via bus  32 . However, to access the microengines  22   a - 22   f  and transfer registers located at any of the microengines  22   a - 22   f , the core processor  20  access the microengines  22   a - 22   f  via the ASB Translator  30  over bus  34 . The ASB translator  30  can physically reside in the FBUS interface  28 , but logically is distinct. The ASB Translator  30  performs an address translation between FBUS microengine transfer register locations and core processor addresses (i.e., ASB bus) so that the core processor  20  can access registers belonging to the microengines  22   a - 22   c.    
         [0021]     Although microengines  22  can use the register set to exchange data as described below, a scratchpad memory  27  is also provided to permit microengines to write data out to the memory for other microengines to read. The scratchpad  27  is coupled to bus  34 .  
         [0022]     The processor core  20  includes a RISC core  50  implemented in a five stage pipeline performing a single cycle shift of one operand or two operands in a single cycle, provides multiplication support and 32 bit barrel shift support. This RISC core  50  is a standard Strong Arm® architecture but it is implemented with a five stage pipeline for performance reasons. The processor core  20  also includes a 16 kilobyte instruction cache  52 , an 8 kilobyte data cache  54  and a prefetch stream buffer  56 . The core processor  20  performs arithmetic operations in parallel with memory writes and instruction fetches. The core processor  20  interfaces with other functional units via the ARM defined ASB bus. The ASB bus is a 32-bit bi-directional bus  32 .  
         [0023]     Referring to  FIG. 3 , two microengines  22   a ,  22   b  of the microengines  22   a - 22   f  in the processor  12  hereinafter “network processor” are shown. One of the microengines  22   a  is a producer microengine whereas the other  22   b  is a consumer microengine. The producer microengine  22   a  processes packets and provides results of the processing that will be used by the consumer microengine  22   b . The producer microengine has a plurality of contexts (threads of executing instructions). Disposed between the producer microengine  22   a  and the consumer microengine  22   b  is an inter-processor ring structure  60 . The inter-processor ring structure  60  is a memory structure or ring that can be in SRAM, SDRAM, scratchpad or a microengine next neighbor register array.  
         [0024]     When the producer processor  22   a  has a message that it needs to be placed on the inter-processor ring  60 , it will place the data on the ring  60  and set a bit in a self-destruct register  62 . The bit location in the self-destruct register  62  is determined by using a counter on the producing microengine that will start at, e.g., bit  0  and cycle through all bit positions in the self-destruct register  62 , e.g., 32 bit positions, before continuing again with the first bit (i.e. bit  0 ). The counter that the producer uses to select the next bit to set in the self-destruct register is global to all threads on the producer microengine  22   a  that place data on the inter-processor ring. The self-destruct register  62  enables synchronization between the microengines  22   a - 22   b . The self-destruct register and inter-processor ring  60  allows up to a maximum of, e.g., 32 outstanding messages before the producing microengine temporarily stops sending data to the ring  60  to permit the consumer microengine to empty some of the ring&#39;s  60  contents.  
         [0025]     This storage capacity provided by the inter-processor ring  60  is more than adequate in most situations. For example in the case of next neighbor rings, the number of long words that the ring can hold is 128. If the number of long words in a message is 4 or more, then the next neighbor ring will fill up before the 32-bit self-destruct register window overflows. If the message is less than 4 longwords, then two self-destruct registers can be used for synchronization. A counter “global_cnt”  66  is used by the producer microengine to select the next bit to set in the self-destruct register  62 . Counter global_cnt  66  is an absolute register in the producer microengine. It could be located in memory (i.e. local memory, scratch, SRAM or DRAM). Counter global_cnt  66  is global to all threads on the producer microengine that place data on the inter-processor ring.  
         [0026]     The self-destruct register  62  is used for synchronizing data passed between microengines. During a write operation, a bit in the 32-bit register is ORed with the existing 32 bits. This operation is atomic so multiple producers can write to the register without causing race conditions. A read from the register returns the current register state (all bits that were set following the last read operation to the register or after a reset) and atomically clears the register.  
         [0027]     The consumer processor  22   b  checks the self-destruct register to determine the number of messages to read from the inter-processor ring. The consumer processor  22  uses a Find First bit Set (FFS) microinstruction with the self-destruct register to immediately determine if the ring needs processing. The FFS microinstruction locates the first bit set in a register. If a bit it set, it will return the bit position in an output register otherwise it will set the ‘Z’ flag in the network processor. It is not necessary to use the FFS instruction. Any instruction or combinations of instructions that can determine if a bit is set will work as well. Other arrangements are possible. If the self-destruct register returns a value of 0, then no message is in the inter-processor ring  60 . In order to minimize the need for polling of the self-destruct register  62 , signaling by the producer thread could be used. In this embodiment, producer microengine  22   a  will signal consumer microengine  22   b  when producer microengine  22   a  places data on the inter-processor ring. Consumer microengine  22   b  will check the inter-processor ring if it receives a signal that indicates that at least one message is waiting in the ring. Once the signal is received, consumer microengine  22   b  will check the self-destruct register to determine the number of messages waiting on the ring.  
         [0028]     Using the self-destruct register  62 , the thread can quickly determine the number of outstanding messages that need to be processed off of the inter-processor ring  60 . The self-destruct register synchronizes data that is passed between the producer and consumer microengines  22   a ,  22   b.    
         [0029]     The Table below is an example communication stream that could occur between a producer  22   a  (ME:1) and a consumer  22   b  (ME:2) processor. In the example, the producer  22   a  writes five messages to the inter-processor ring  60 . The consumer  22   b  independently reads the self-destruct register  62  twice to retrieve all five messages.  
                                                     TABLE 1                                   Self-Destruct                       Register           Time   ME:1   ME:2   Value after           (in steps)   (Producer)   (Consumer)   Operation   Comments                                0   CTX0 places data on       0 × 01   Bit 0 is set in self-destruct register           inter-processor ring           and writes 0 × 01 to the           self-destruct register.       1   CTX1 places data on       0 × 03   Bits 0 and 1 are set in self-destruct           inter-processor ring           register           and writes 0 × 02 to the           self-destruct register.       2   CTX2 places data on       0 × 07   Bits 0, 1 and 2 are set in self-           inter-processor ring           destruct register           and writes 0 × 04 to the           self-destruct register.       3       CTX0 the reads a   0 × 00   When ME:2 reads the self-destruct               value of 0 × 07 from       register, it is reset to 0. Since 3 bits               the self-destruct       were set, it will take 3 messages               register       from the inter-processor ring.       4   CTX3 places data on       0 × 08   Bit 4 is set in the self-destruct           inter-processor ring           register           and writes 0 × 08 to the           self-destruct register.       5   CTX4 places data on       0 × 18   Bits 4 and 5 are set in the self-           inter-processor ring           destruct register           and writes 0 × 18 to the           self-destruct register.       6       CTX1 the reads a   0 × 00   When ME:2 reads the self-destruct               value of 0 × 18 from       register, it is reset to 0. Since 2 bits               the self-destruct       were set, it will take 2 messages               register       from the inter-processor ring.                  
 
         [0030]     Referring to  FIG. 4 , a process  70  to place data from a producer microengine  22   a  onto the inter-processor ring  60  without using signaling is shown. During initialization  71 , global_cnt register  66  on the producer microengine, e.g., microengine  22   a  is set to point to bit  0  in the self-destruct register  62 . This initialization is performed typically once, such as when the processor is powered on, or reset.  
         [0031]     The process  70  populates  72  the ring with all bytes in the message from the producer microengine, sets  73  the bit in the self-destruct register corresponding to the bit in the global_cnt and checks  74  if global_cnt exceeds the maximum number of bits in the self-destruct register, e.g., 32. If the count is met, the process  70  resets  76  the global_cnt to bit  0  and exits  79 . Otherwise, the process  70  exits  79  and a new instance of the process  70  will place additional data on the inter-processor ring from subsequent producers and set the next available bit position.  
         [0032]     It is also possible to use a signal in conjunction with the self-destruct register to avoid excessive use of the bus when the producer microengine polls the self-destruct register to determine if any data is available to be read off the ring.  
         [0033]     Referring to  FIG. 5 , a process  80  to place data on inter-processor ring (in conjunction with signals) is shown. Process  80  has an initialization  81 , in which the global_cnt register  66  is set to point to bit  0 . Process  80  populates  82  the inter-processor ring  60  with all bytes in the message from the producer microengine, sets  84  the bit in the self-destruct register corresponding to the bit in the global_cnt, and signals  85  a thread in the processing microengine that a message is available to be read. The process checks  86  if global_cnt exceeds the maximum number of bits in the self-destruct register, e.g., 32. If the count is met, the process  80  resets  87  global_cnt to bit  0  and exits. Otherwise the process  80  exits  89  and a new instance of the process  80  will place additional data on the inter-processor ring from subsequent producers, and set the next available bit position.  
         [0034]     The consumer microengine, e.g., microengine  22   b  will either use the inter-microengine signal to poll the self-destruct register or periodically choose to poll the self-destruct register to determine if a message or multiple messages need to be read from the ring.  
         [0035]     Referring to  FIG. 6 , a process  90  to read data off the inter-processor ring without the use of signaling is shown. The process  90  reads  92  the self-destruct register and sets  94  a value in a local register. This register can be either global to all threads executing on the microengine or it can be local to the thread that performed the read operation. The reason that the contents from the self-destruct register are maintained in a local register is because the self-destruct register is reset to zero when the data is read. If the data were not kept locally, it would be lost. The process  90  checks  96  the value in the local register, and if the value in the local register equals zero then the process  90  exits  99 . Otherwise, the process  90  retrieves  97  a message off of the inter-processor ring, removes  98  one of the set bits from the local register and returns to check  96  the value in the local register. The process  90  continues to process available messages and exits  99  when the value in the local register equals zero.  
         [0036]     If the solution requires the use of the inter-microengine signals, then the consumer microengine will change to the following:  
         [0037]     Referring to  FIG. 7 , a process  100  to read data off the inter-processor ring in conjunction with signaling is shown. The process  100  wakeups  101  when the signal sent from the producer microengine  22   a  is received. The process  100  reads  102  the self-destruct register. The process  100  then determines  103  if any bits are set in the self-destruct register (i.e. using the FFS micro instruction). If no bits are set, it immediately exit  109  otherwise the process  100  sets  104  the value in a local register. The process retrieves a message off the ring  107 . It clears one bit from the local register  108 . The process could retrieve multiple messages simultaneously. It will clear the number of bits equal to the number of messages read off the ring. The process checks  106  the value in the local register and if the local register value equals zero then the process goes to  102  to check if any more messages were placed on the ring while the process read messages off the ring. Otherwise, the process  100  returns to  107  to continue processing messages.  
         [0038]     A number of embodiments of the invention have been described. Nevertheless, it will be understood that various modifications may be made without departing from the spirit and scope of the invention. Accordingly, other embodiments are within the scope of the following claims.