Memory apparatus for a message processing system and method of providing same

Memory apparatus for a message processing system and method of providing the same is described. In one example, a message processing system (200) includes a set of n processing elements (202) for processing messages, where n is an integer greater than zero. A set of m memories (204) is provided for storing the messages, where m is an integer greater than zero. Multiplexing logic (206) is provided for coupling each of the processing elements to each of the memories. Control logic (208) is provided for driving the multiplexing logic to provide access to each of the memories among the processing elements in accordance with a gated module-n schedule.

FIELD OF THE INVENTION

One or more aspects of the present invention relate generally to memory systems and, more particularly, to a memory apparatus for a message processing system and a method of providing the same.

BACKGROUND OF THE INVENTION

Programmable logic devices (PLDs) exist as a well-known type of integrated circuit (IC) that may be programmed by a user to perform specified logic functions. There are different types of programmable logic devices, such as programmable logic arrays (PLAs) and complex programmable logic devices (CPLDs). One type of programmable logic device, known as a field programmable gate array (FPGA), is very popular because of a superior combination of capacity, flexibility, time-to-market, and cost.

An FPGA typically includes an array of configurable logic blocks (CLBs) surrounded by a ring of programmable input/output blocks (IOBs). The CLBs and IOBs are interconnected by a programmable interconnect structure. The CLBs, IOBs, and interconnect structure are typically programmed by loading a stream of configuration data (known as a bitstream) into internal configuration memory cells that define how the CLBs, IOBs, and interconnect structure are configured. An FPGA may also include various dedicated logic circuits, such as memories, microprocessors, digital clock managers (DCMs), and input/output (I/O) transceivers.

Typically, network devices, such as routers, employ dedicated, special purpose components for processing packets that propagate through the network. Conventionally, network devices employ network processors or application specific integrated circuits (ASICs) to provide the desirable packet processing/network processing functions. Notably, ASICs employed for network processing functions typically include a static memory architecture that provides a fixed amount of memory resources with a fixed interconnection scheme. Dedicated network processors typically communicate with off-chip memories using a bus structure having a fixed width. Accordingly, there exists a need in the art for more flexible memory architectures and organizations for use in message processing systems.

SUMMARY OF THE INVENTION

Memory apparatus for a message processing system and method of providing the same is described. In one embodiment, a message processing system includes a set of n processing elements for processing messages, where n is an integer greater than zero. A set of m memories is provided for storing the messages, where m is an integer greater than zero. Multiplexing logic is provided for coupling each of the processing elements to each of the memories. Control logic is provided for driving the multiplexing logic to provide access to each of the memories among the processing elements in accordance with a gated module-n schedule. In one embodiment, the each of the memories comprises a memory circuit embedded within a programmable logic device, such as an FPGA (e.g., block RAMs). The multiplexing logic and the control logic may be configured using programmable logic blocks and programmable interconnect of the FPGA.

DETAILED DESCRIPTION OF THE DRAWINGS

Memory apparatus for a message processing system and method of providing the same is described. One or more aspects of the invention are also related to message processing (MP) systems. As used herein, the term “message” encompasses packets, cells, frames, data units, and like type blocks of information known in the art that is passed over a communication channel. A “message processing” system is a system or subsystem for processing messages (e.g., a packet processing system or a network processing system).

In addition, one or more aspects of the invention are described with respect to providing a memory system using an FPGA. Those skilled in the art will appreciate, however, that the present invention may be used to provide memory systems for other types of programmable logic devices, such as complex programmable logic devices (CPLDs).

In particular,FIG. 1is a block diagram depicting an exemplary embodiment of an FPGA102coupled to a program memory120. The FPGA102illustratively comprises programmable logic circuits or “blocks”, illustratively shown as CLBs104, IOBs106, and programmable interconnect108(also referred to as “programmable logic”), as well as configuration memory116for determining the functionality of the FPGA102. The FPGA102may also include an embedded processor block114, as well as various dedicated internal logic circuits, illustratively shown as blocks of random access memory (“BRAM110”), configuration logic118, digital clock management (DCM) blocks112, and input/output (I/O) transceiver circuitry122. Those skilled in the art will appreciate that the FPGA102may include other types of logic blocks and circuits in addition to those described herein.

As is well known in the art, the IOBs106, the CLBs104, and the programmable interconnect108may be configured to perform a variety of functions. Notably, the CLBs104are programmably connectable to each other, and to the IOBs106, via the programmable interconnect108. Each of the CLBs104may include one or more “slices” and programmable interconnect circuitry (not shown). Each CLB slice in turn includes various circuits, such as flip-flops, function generators (e.g., a look-up tables (LUTs)), logic gates, memory, and like type well-known circuits. The IOBs106are configured to provide input to, and receive output from, the CLBs104.

Configuration information for the CLBs104, the IOBs106, and the programmable interconnect108is stored in the configuration memory116. The configuration memory116may include static random access memory (SRAM) cells. The configuration logic118provides an interface to, and controls configuration of, the configuration memory116. A configuration bitstream produced from the program memory120may be coupled to the configuration logic118through a configuration port119. The configuration process of FPGA102is also well known in the art.

The I/O transceiver circuitry122may be configured for communication over any of a variety of media, such as wired, wireless, and photonic, whether analog or digital. The I/O transceiver circuitry122may comprise gigabit or multi-gigabit transceivers (MGTs). The DCM blocks112provide well-known clock management circuits for managing clock signals within the FPGA102, such as delay lock loop (DLL) circuits and multiply/divide/de-skew clock circuits.

The processor block114comprises a microprocessor core, as well as associated control logic. Notably, such a microprocessor core may include embedded hardware or embedded firmware or a combination thereof for a “hard” or “soft” microprocessor. A soft microprocessor may be implemented using the programmable logic of the FPGA102(e.g., CLBs104, IOBs106). For example, a MICROBLAZE soft microprocessor, available from Xilinx of San Jose, Calif., may be employed. A hard microprocessor may be implemented using an IBM POWER PC, Intel PENTIUM, AMD ATHLON, or like type processor core known in the art.

The processor block114is coupled to the programmable logic of the FPGA102in a well known manner. For purposes of clarity by example, the FPGA102is illustrated with 12 CLBs, 16 IOBs, 4 BRAMs, 4 DCMs, and one processor block. Those skilled in the art will appreciate that actual FPGAs may include one or more of such components in any number of different ratios. For example, the FPGA102may be selected from the VIRTEX-II PRO family of products, commercially available from Xilinx, Inc. of San Jose, Calif.

FIG. 2is a block diagram depicting an exemplary embodiment of a message processing system200in accordance with the invention. In embodiment, at least a portion of the system200may be implemented using an FPGA. The system200comprises processing elements (PEs)2020through202N-1(collectively referred to as processing elements202), memories2040through204M-1(collectively referred to as memories204), multiplexers (MUXs)2060through206M-1, and control circuits (CONs)2080through208M-1, where N and M are integers greater than zero. The multiplexers2060through206M-1collectively comprise multiplexer logic206. The control circuits2080through208M-1collectively comprise control logic208. The processing element2020comprises an ingress manager for receiving messages to be stored and processed by the system200, and the processing element202N-1comprises an egress manager for providing messages that have been stored and processed by the system200.

In the present embodiment, the processing elements202are arranged in a pure pipeline configuration. That is, an output terminal of the PE2020is coupled to an input terminal of the PE2021, an output terminal of the PE2021is coupled to an input terminal of the next PE, and so on until the output terminal of the PE202N-1is coupled to an input terminal of the PE202N-1. An input terminal of the ingress manager2020is configured to receive input messages, and an output terminal of the egress manager202N-1is configured to provide output messages.

A memory interface of each of the processing elements202is coupled to an input port of each of the multiplexers2060through206M-1. Output ports of the multiplexers2060through206M-1are respectively coupled to interfaces of the memories2040through204M-1. The memory interface of each of the processing elements202, as well as the input and output ports of the multiplexers2060through206M-1, may have a width, k, where k is determined by the interface to the memories204. For example, for if the memories204comprise BRAM, the memory interface comprises signals related to enable, address, write, and data to collectively provide a 20-bit wide interface.

Select terminals of the multiplexers2060through206M-1are respectively coupled to output terminals of the control circuits2080through208M-1. Each of the processing elements202is coupled to a control port of each of the control circuits2080through208M-1. That is, each of the processing elements202includes M control interfaces respectively coupled to the M control circuits208. Stated differently, each of the control circuits2080through208M-1includes N control interfaces respectively coupled to the N processing elements202.

In one embodiment, the system200is implemented using a programmable logic device, such as an FPGA. Notably, the memories204may comprise random access memory (RAM) embedded within an FPGA, such as static random access memory (SRAM) or BRAM. The multiplexers2060through206M-1, the control circuits2080through208M-1, and the processing elements202may be configured within an FPGA using programmable logic blocks and interconnect, may comprise dedicated circuitry embedded within the FPGA, or may comprise a portion of both programmable logic and dedicated circuitry. Use of an FPGA to provide a memory architecture for a message processing system allows for a scalable, domain-specific memory organization that has a concise interface, that is reusable, that has minimal addressing overhead, that can be deployed in a variety of computation structures, and that enables a reduction in power consumption.

Notably, in an FPGA, the number of memories204that may be used in the system200depends upon the number of processing elements202and the available routing resources (e.g., wires) in the FPGA. Ideally, the number of memories204equals the number of processing elements in the system200(i.e., M=N), with dedicated routing between each of the processing elements202and each of the multiplexers2060through206M-1, as well as between each of the processing elements202and each of the control circuits2080through208M-1. However, in practice, the number of processing elements202can be large and themselves consume enough routing resources to deter implementation of a large number of memories204. In such a scenario, less memories204may be used than there are processing elements202(i.e., M<N), various routing resources may be shared rather than dedicated (e.g., a bus), or both.

In operation, the memory architecture of the system200is configured to match the nature of message processing applications, wherein messages arrive at the ingress manager2020from an external interface and are stored in the memories204, a series of processing functions are performed on the messages, and the processed messages are transferred to another (or the same) external interface. Each of the remaining processing elements2021through202N-2is configured to perform a particular function or operation on the stored messages. For example, the system200may be configured to process internet protocol (IP) packets and may include processing elements for checking the IP header, performing an IP lookup, decrementing a time-to-live (TTL) field in IP packets, and like-type IP processing operations.

The processing elements202access the memories204to read messages from the memories204, as well as write processed messages to the memories204. In particular, the processing elements202access the memories204using the multiplexer logic206, which is controlled via the control logic208. For each of the memories204, the control logic208implements a gated module-N schedule for memory accesses among the N processing elements202. That is, for a particular one of the memories204, memory access cycles from the ingress manager2020through the processing elements2021to202N-2to the egress manager202N-1and back to the ingress manager2020. Only one of the processing elements may access a given one of the memories204at a time. The memory access is gated in that a processing element in the pipeline cannot obtain memory access until the proceeding processing element signals that its memory access is complete or that it does not require a memory access. The gating of memory access accounts for non-uniform processing latencies of the processing elements202(e.g., the processing element2021may take longer to process a message than the processing element2022).

Since the ingress manager2020is granted memory access in accordance with the gated modulo-N schedule described above, the input messages are allocated over the M memories204based on a modulo-M schedule. For example, the first message is allocated to the memory2040, the next message is allocated to the memory2041, and so forth until the Mth message is again allocated to the memory2040. Likewise, since the egress manager202N-1is granted memory access in accordance with the gated modulo-N schedule, the messages are de-allocated from the M memories204in accordance with a modulo-M schedule. In one embodiment, the ingress manager2020and the egress manager202N-1are buffers with memory access functions (i.e., buffers that are capable of pushing/pulling messages to/from a given memory location).

FIG. 3is a chart300illustrating an exemplary embodiment of memory access schedule in accordance with the invention. In the present example, the system200includes three memories (MEMs)204(i.e., M=3) and five processing elements202including the ingress manager2020and the egress manager202N-1(i.e., N=5). The chart300includes a horizontal axis302representing access slots, a vertical axis304representing the memories204, and cells306. Each of the cells306corresponds to a particular memory and access slot and includes the particular one of the processing elements202that is granted memory access.

As shown, during access slot0, PE0is granted access to MEM0. During access slot1, PE0is granted access to MEM1and PE1is granted access to MEM0. During access slot2, PE0is granted access to MEM2, PE1is grated access to MEM1, and PE2is granted access to MEM0. During access slot3, PE0no longer has access to any of the three memories. In access slot3, PE1is granted access to MEM2, PE2is grated access to MEM1, and PE3is granted access to MEM0. PE0does not obtain memory access again until access slot5, at which slot PE0is again granted memory access to MEM0. This schedule is repeated for additional access slots. Note that the access slots may provide memory access to a given PE for an arbitrary number of clock cycles. That is, access slots may have non-uniform durations in terms of clock cycles.

Returning toFIG. 2, as the control logic208implements the gated modulo-N access schedule, each of the processing elements202may choose memory access or skip memory access by communicating such to the control logic208. In addition, the control logic208may provide status information to, or receive status information from, each of the processing elements202. The connection between every one of the processing elements202and every one of the control circuits2080through208M-1allows for the communication of control information (e.g., a choose/skip signal), status information, and the like. Each connection between a processing element and a control circuit may be configured to communicate a plurality of signals.

In particular,FIG. 4is a block diagram depicting an exemplary embodiment of the control circuit2080in accordance with the invention. It is to be understood that the other control circuits2081through208M-1are identical to the embodiment shown inFIG. 4. The control circuit2080comprises a select port402, a status port404, a choose/skip port406, a done port407, and gating logic408. The select port402is configured to provide a selection signal to the multiplexer2060for selecting a respective one of the processing elements202for memory access. The status port404is configured to provide various status data to, or received various status data from, each of the processing elements202. The choose/skip port406is configured to receive a control signal from each of the processing elements202configured to either choose or skip memory access. The done port407is configured to receive a done signal from each of the processing elements202indicating that a respective processing element has completed with its memory access. The gating logic408is configured to drive the multiplexer2060to select the currently scheduled processing element if such processing element has asserted its choose/skip signal. If the scheduled processing element has not asserted its choose/skip signal, the gating logic408drives the multiplexer2060to select none of the processing elements202for memory access.

View400depicts an exemplary embodiment of the gating logic408. In the present embodiment, the gating logic408comprises a multiplexer410, a 1-bit comparator/word generator412, a modulo counter414, and a bitwise AND gate416. Input ports of the multiplexer410are coupled to the choose/skip port406and are configured to receive choose/skip signals from each of the processing elements202. That is, the multiplexer410includes N input ports, each of the N input ports configured to receive a choose/skip signal from a respective one of the processing elements2020through202N-1. An output port of the multiplexer410is coupled to an input port of the 1-bit comparator/word generator412.

An output port of the 1-bit comparator/word generator412is coupled to an input port of the bitwise AND gate416. Output ports of the modulo counter414are respectively coupled to a selection port of the multiplexer410and another input port of the bitwise AND gate416. Input ports of the modulo counter414are coupled to the done port407and are configured to receive done signals from each of the processing elements202. That is, the modulo counter414includes N input ports, each of the N input ports configured to receive a done signal from a respective one of the processing elements2020through202N-1. An output port of the bitwise AND gate416is coupled to the select port402.

In operation, the modulo counter414maintains a binary count that is used to drive the multiplexer2060to select a processing element for memory access. The modulo counter414cycles from causing the first of the processing elements202(i.e., the ingress manager) to be selected, to causing the last of the processing elements202(i.e., the egress manager) to be selected and then back to the first of the processing elements202. The output of the modulo counter414is gated by the bitwise AND gate416.

Notably, if the currently scheduled processing element asserts its choose/skip signal, then the 1-bit comparator/word generator412will detect an asserted output from the multiplexer410(as selected by the output of the modulo counter414) and will generate a word comprising N ones. The word produced by the 1-bit comparator/word generator412and the word produced by the modulo counter414are processed using a bitwise AND operation in the bitwise AND gate416. Since the word generated by the 1-bit comparator/word generator412contains all ones, the count from the modulo counter414will pass through the bitwise AND gate416to drive the select terminal of the multiplexer2060.

Conversely, if the currently scheduled processing element de-asserts its choose/skip signal, then the 1-bit comparator/word generator412will detect a de-asserted output from the multiplexer410(as selected by the output of the modulo counter414) and will generate a word comprising N zeros. Since the word generated by the 1-bit comparator/word generator412contains all zeros, the count from the modulo counter414will not pass through the bitwise AND gate416to drive the select terminal of the multiplexer2060. In this manner, the control circuit2080is configured to provide memory access for the processing elements202in accordance with a gated modulo-N schedule.

Returning toFIG. 2, in one embodiment of the invention, based on the knowledge of individual latencies of each of the processing elements202, the memories204may be put into sleep mode (thus consuming less power) for a certain number of clock cycles and awakened a few clock cycles before access by the next processing element. For example, a status signal may be provided from each of the processing elements202to each of the control circuits2080through208M-1. Based on the status of a given processing element, a control circuit may cause its respective memory to enter a sleep mode for a period of time and then “wake-up” the memory before access is granted to the next processing element.

FIG. 5is a block diagram depicting another exemplary embodiment of a message processing system500in accordance with the invention. The system500comprises a plurality of pipelines502, and input queue/load balance circuit504, and an output queue/interface control circuit506. An input port of the input queue/load balance circuit504is configured to receive messages. Output ports of the input queue/load balance circuit504are respectively coupled to input ports of the pipelines502. Output ports of the pipelines502are respectively coupled to input ports of the output queue/interface control circuit506. An output port of the output queue/interface control circuit506is configured to provide processed messages. Each of the pipelines502may comprise the message processing system200shown inFIG. 2. For purposes of clarity, only the processing elements are shown in each of the pipelines502and range from PE1through PENfor each pipeline.

The input queue/load balance circuit504reads messages (e.g., packets from a network interface) and allocates the messages among the pipelines502for processing. The input queue/load balance circuit504balances the load across all of the pipelines502to ensure a more uniform latency across the pipelines502. The output queue/interface control circuit506retrieves messages from the individual pipelines502and writes the messages to an external interface. In another embodiment, the input queue/load balance circuit504may be omitted and messages may be directly coupled to the pipelines502from an external interface (e.g., network interface).

FIG. 6is a block diagram depicting yet another exemplary embodiment of a message processing system600in accordance with the invention. The system600comprises a plurality of pipelines6021through602X(collectively referred to as pipelines602), input queue/load balance circuit604, and an output queue/interface control circuit606. The pipelines6021through602Xrespectively include sub-pipelines6031through603X. Each of the sub-pipelines603generally includes k processing elements, where k is an integer greater than zero. In the present embodiment, the sub-pipeline6031includes three processing elements, the sub-pipeline6032includes four processing elements, and the sub-pipeline603Xincludes two processing elements.

Each of the pipelines602may comprise the message processing system200shown inFIG. 2, modified as described below. For purposes of clarity, only the processing elements are shown for each of the pipelines602. The input queue/load balance circuit604and the output queue/interface control circuit606are coupled to the pipelines602and operate in a similar manner as described above with respect toFIG. 5.

The system600implements a pipeline-of-pool configuration. Notably, for the pipeline6021(the present examples may be applied to the other pipelines602), a decision is made after the processing element PE1as to whether flow continues to processing element PE2(“primary flow”) or to processing element PE21of the sub-pipeline6031(“sub-flow”). In one embodiment, each of the memories204comprises a dual-port memory (e.g., a BRAM in an FPGA). The multiplexing logic206includes a first set of multiplexers coupled to the memories2040through204M-1using the first ports thereof, and another set of M multiplexers that are coupled to the memories2040through204M-1using the second ports thereof. The first set of multiplexers control access to the memories204among the processing elements of the primary flow (e.g., PE1, PE2, PE3, and PEM). The second set of multiplexers control access to the memories204among the processing elements of the sub-flow (e.g., PE21, PE22, and PE23). The control logic208provides a gated modulo-n schedule for memory access among the processing elements of the primary flow, and a gated modulo-k schedule for memory access among the processing elements of the sub-flow.

In another embodiment, the memories204only include one port. In such an embodiment, a second set of multiplexers is not required and the control logic is configured to provide a gated modulo-(n+k) schedule for memory access among the processing elements of the entire pipeline6021. However, this will result in a longer delay through the pipeline6021equal to the delay of all of the processing elements.