Patent ID: 12222884

DETAILED DESCRIPTION OF THE INVENTION

The present invention will now be described more fully hereinafter with reference to the accompanying drawings, in which preferred embodiments of the invention are shown. This invention may, however, be embodied in many different forms and should not be construed as limited to the embodiments set forth herein. Rather, these embodiments are provided so that this disclosure will be thorough and complete, and will fully convey the scope of the invention to those skilled in the art. Those of ordinary skill in the art realize that the following descriptions of the embodiments of the present invention are illustrative and are not intended to be limiting in any way. Other embodiments of the present invention will readily suggest themselves to such skilled persons having the benefit of this disclosure. Like numbers refer to like elements throughout.

In this detailed description of the present invention, a person skilled in the art should note that directional terms, such as “above,” “below,” “upper,” “lower,” and other like terms are used for the convenience of the reader in reference to the drawings. Also, a person skilled in the art should notice this description may contain other terminology to convey position, orientation, and direction without departing from the principles of the present invention.

Furthermore, in this detailed description, a person skilled in the art should note that quantitative qualifying terms such as “generally,” “substantially,” “mostly,” and other terms are used, in general, to mean that the referred to object, characteristic, or quality constitutes a majority of the subject of the reference. The meaning of any of these terms is dependent upon the context within which it is used, and the meaning may be expressly modified.

Referring toFIGS.1-9, a memory-mapped FIFO architecture for use with a microprocessor and multiprocessor computer system, and associated methods, according to certain embodiments of the present invention are now described in detail. Throughout this disclosure, the present invention may be referred to as a memory-mapped FIFO system, a memory-mapped FIFO device, a memory-mapped FIFO, a FIFO system, a hardware FIFO, a FIFO device, a FIFO method, a FIFO, a device, a system, and a method. Those skilled in the art will appreciate that this terminology is only illustrative and does not affect the scope of the invention.

Certain embodiments of the invention, as shown and described by the various figures and accompanying text, may overcome the problems in the art described above by delivering the following advantages, as described in more detail herein below:

1) Consumes/generates/moves data efficiently at high data rates characteristic of network switches and converters (e.g., analog-to-digital, digital-to-analog)

2) Efficiently operates available buffers to mitigate latency penalties for memory access and avoids undesirable results of clogging of the queued data pipeline (e.g., dropped data, corrupted data streams)

Referring now toFIGS.1through9, the following features of the present invention may contribute to providing the advantages listed above:

A) Hardware FIFO(s)100that efficiently enqueues data on behalf of a processor core110.

B) Controllable FIFO(s)200capable of processing data while the processor core performs other activities.

C) Hardware FIFO bank(s)300comprising at least one of at least one hardware memory-mapped FIFO(s)100and at least one of controllable hardware memory-mapped FIFO(s)200.

D) Hardware FIFO(s)100backed by expandable buffer space in at least one of cache memory440, higher-level memory450, and additional buffer memory510.

E) Processor core(s)110operably coupled with at least one of hardware FIFOs (100) and FIFO banks(s)300and cache memory440via shared busses131and150and shared control signals114.

F) Processor core(s)110operably coupled with at least one of hardware FIFOs100and FIFO banks(s)300, cache memory440, and higher-level memory450through arbiters that mediate resource contention.

G) Automating data processing by a controllable FIFO based upon processor configuration. Illustration of Direct Memory Access (DMA) setup and operation as a specific example data processing comprising data movement using FIFO control structures (e.g.,FIG.8) and FIFO Controller250.

E) Solution space-specific configurations of a DMA-based microprocessor computer system, including split FIFOs (FIG.4), chained FIFOs, split FIFO streams, and merged FIFO streams

F) Auxiliary processor(s) for data-dependent pre- and post-processing, including addition of a modulus to the non-unit-stride output of a hardware FIFO(s) and/or a memory-mapped FIFO(s).

Memory-Mapped First-In First-Out (FIFO) Queue

Referring more specifically toFIG.1, the hardware FIFO100according to an embodiment of the present invention will now be discussed. The hardware FIFO100may comprise a head120, a tail140, and a FIFO buffer130. The hardware FIFO head120may be operably coupled with at least one of the data bus to fetch data154, a raw output port180, and a network output port190. Similarly, the hardware FIFO140tail may be operably coupled with at least one the data bus to write data152, a raw input port180, and a network input port190. An address decoder160for the head120detects if a memory operation affects the FIFO head120. An address decoder161for the tail140detects if the memory operation affects the FIFO tail140. The hardware FIFO may be configured to support enqueuing and dequeuing operations either synchronously or asynchronously. Said enqueuing operations from network190or raw inputs180are strobed by means of control signals192and182respectively, indicating valid data is available on the appropriate port. Similarly, said dequeuing operations to network or raw outputs are strobed by means of a control signal191and181, respectively, indicating valid data is available on the appropriate port.

As described above, because a hardware FIFO bank100is characterized by a single head120and tail140, such a FIFO100may be mapped to a single physical address of the processor core110or a virtual address of a process running on said processor core. One embodiment of the present invention may employ one address for the head120of the FIFO100and another address for the tail140. An alternative embodiment of the present invention may use a single address for both head120and tail140, but may recognize the logical distinction that a write to that address is enqueuing data at the tail140and a read is dequeuing data from the head120of the queue. Mapping a FIFO100into the address space of the processor core110, as opposed to a dedicated internal register, is an advantage of the present invention.

The FIFO buffer130provides storage for data enqueued at the FIFO tail that has not yet arrived at the FIFO head and may comprise any of several storage selected from the group consisting of a static random-access memory (SRAM), a flip-flop, a register file, and a latch. In one embodiment of the present invention, the depth of the FIFO buffer130is fixed.

When writing (enqueuing) on the memory-mapped FIFO100, the processor core110may simply write a value to the FIFO tail memory-mapped address. For example, and without limitation, this WRITE action may enqueue the value on the memory-mapped FIFO. When the memory-mapped FIFO is full, one embodiment of the present invention may be configured to treat the write as a cache miss and operate to stall the processor core110or the requesting process or thread. However, an alternative embodiment may be to operate to allow a write to fail.

A hardware FIFO100may be mapped to a memory location in the physical address space of the processor core110. Additionally, said hardware FIFO100may be mapped into the virtual address space of one or more processes executing on the processor core.

In one embodiment of the present invention, each hardware FIFO100may present either its head120or its tail140to the processor core110if its tail is written to or its head is read from, respectively, at least one of the Network190, Raw I/O180, other storage, and other FIFOs100. For example, and incoming Raw data input from an external analog-to-digital converter may asynchronously strobe data into the FIFO tail and this may be the only means of enqueuing data on the FIFO, whereas the processor may read (dequeue) data from the head of the processor using a typical LOAD operation. Alternatively, or in addition, the present invention may be configured such that both ends120,140of the FIFO100may be exposed to the processor core110for tasks such as inter-thread or inter-process communication.

How the processor core110may interact with a memory-mapped FIFO100will now be described in detail. In one embodiment, the present invention may include architecturally treating the FIFO similar to a cache memory as commonly understood to those skilled in the art. Such architectural mapping may advantageously support use of the existing cache control signals114to handle exceptions such as an empty or full FIFO. For example, and without limitation, when implementing a READ FIFO using an embodiment of the present invention, if the processor core110is to consume a value from a memory-mapped hardware FIFO100, it may simply read (fetch) a data structure from the memory exactly as it would from a cache memory. This action may have the effect of dequeuing the value at the head of the queue and returning it to the processor core110. If the FIFO is empty, the processor core110may observe a condition similar to a “cache miss” and may respond like it would to any cache miss—generally, by stalling the processor core110or the requesting process or thread executing on the processor core110until the data is available. The essential semantics of a cache miss is that the data is not yet ready, and that is the case for an empty FIFO as well. The key difference is the cause of unavailability. In the case of a traditional cache miss, the data must be retrieved from higher in the memory hierarchy. In the case of a FIFO, the processor core110is waiting for another value to be enqueued. In the specific case of SPv2, the processor core stalls on a cache miss. Because such blocking behavior may be undesirable, the present invention may include alternative cache miss handling features (as described in detail below).

Variants of this typical READ behavior may have valuable use cases that require enhancements to the processor core110beyond typical cache interfaces such as, for example, and without limitation, a non-dequeuing read operation (often referred to as a PEEK operation) that does not modify the state of the FIFO. Another interface enhancement, also for example, and without limitation, is a non-blocking read operation that signals invalid data returned due to an empty FIFO, but that allows processing to continue. Building upon this idea is the ability to suspend a thread that is blocked on a FIFO rather than stalling the processor core110completely.

Referring more specifically toFIG.2, the controlled hardware FIFO200according to an embodiment of the present invention will now be discussed. The controlled hardware FIFO200may comprise most elements of a head120, a tail140, and a FIFO buffer130, FIFO controller250, and configuration and status registers210read from and written to by the FIFO controller250by means of bus211, and control signals251and252to control reading from the head and writing to the tail, respectively. The hardware FIFO head120may be operably coupled with at least one of the data bus to fetch data154, a raw output port180, and a network output port190. Similarly, the hardware FIFO140tail may be operably coupled with at least one the data bus to write data152, a raw input port180, and a network input port190. An address decoding is performed by the FIFO controller250. The hardware FIFO may be configured to support enqueuing and dequeuing operations either synchronously or asynchronously under control of the FIFO controller250through control signals252and251, respectively. Said enqueuing operations from network190or raw inputs180are strobed by means of control signals192and182respectively, indicating valid data is available on the appropriate port. Similarly, said dequeuing operations to network or raw outputs are strobed by means of a control signal191and181, respectively, indicating valid data is available on the appropriate port. The FIFO controller250is operably coupled with the configuration and status registers210by means of bus211. Said registers210may be used to at least one of configure a state machine and microcontroller within the FIFO controller250, provide scratch storage space to support FIFO controller250execution, hold FIFO controller250software, and indicate status back to the processor core110. Configuration and status registers210may also be memory mapped into the processor address space to facilitate writing of configuration data and reading of status information by the processor core110.

Referring more specifically toFIG.3, the FIFO bank300according to an embodiment of the present invention will now be discussed. The FIFO bank300comprises at least one controlled hardware FIFO200, address and data busses and control signals previously described for the controlled hardware FIFO, and a local bus330. Said local bus330permits data movement among controlled hardware FIFOs without affecting the operation of the processor core110, other FIFO banks, or other components sharing the address131and data150busses and control signals used by the FIFO bank300.

Referring more specifically toFIG.4, the microprocessor computer system400employing a memory-mapped FIFO architecture according to an embodiment of the present invention will now be discussed. The system400may comprise a processor core110configured in data communication with a cache memory440and a higher-level memory450, which typically represents memory higher in the memory hierarchy, by means of memory interface453. Inserted into at least one data communication path between the processor core110and the cache memory440and/or the higher-level memory450may be one or more hardware FIFO banks300and a FIFO arbiter420. Each of the FIFO bank300comprises one or more hardware FIFOs, each of which may handle incoming or outgoing data of various types, such as, for example, and without limitation, raw input/output (I/O)180, network data190, and/or other forms of inter-thread communication and inter-processor communication. The microprocessor computer system400may include one or more FIFO banks300. Access to shared resources may require arbitration to mediate concurrent demands for said shared resources. Two such resources indicated, without limitation, are shared busses and signals to and from the processor core110and busses and signals to and from higher-level memory450. A FIFO arbiter420may arbitrate communications to and from the processor core110. The memory arbiter470may arbitrate communications to the memory450using a memory access controller460that detects contention for access to higher-level memory450. The FIFO arbiter420may split the data buses450from the processor core110into separate address busses to the FIFO banks(s)150and the cache memory442. Similarly, the FIFO arbiter420may split the address bus,411from the processor core110into separate address busses to the FIFO banks(s)131and the cache memory441. Similarly, control signals may be combined and arbitrated by the FIFO controller420; these include cache control signals414,114, and444. If address busses, data busses, and control signals are suitable compatible and controlled to avoid contention, the corresponding logic of the FIFO controller420may simply wire the corresponding signals together. The memory arbiter470similarly arbitrates among the FIFO banks(s)300and cache memory440for access to memory450by means of memory interface453under control of the memory access controller460. An additional embodiment of the present invention augments existing cache controls414with additional signals to enable additional FIFO operations.FIG.4depicts without limitation a FIFO bank300positioned in between the processor core110and its cache440; those skilled in the art will appreciate that there are many alternative configurations for physically locating a FIFO bank300and the cache440, including incorporation of a FIFO bank300into the cache440.

In an embodiment of the present invention that does not require a FIFO arbiter420, the processor core110may use the same busses411and450and control signals414to interact with the FIFO bank(s)300as it does for the cache memory440.

Referring more specifically toFIG.5, and referring concurrently toFIG.2andFIG.4, a split FIFO expansion of FIFO buffer capacity is discussed. One embodiment of the present invention, a FIFO bank300and at least one of an additional buffer memory510that may expand the FIFO buffer130capacity of the controlled hardware FIFOs200within the FIFO bank300. In this embodiment, the additional buffer memory may expand the depth of the FIFO buffer130of at least one of the controlled hardware FIFO200within the FIFO bank300. In yet another embodiment of the present invention, cache memory440or higher-level memory450may be used to expand the capacity of at least one of a controlled hardware FIFO. In both these embodiments, since components such as the processor core110, network I/O190, Raw I/O180and other FIFOs only interact with data on a controlled hardware FIFO through operations on its head and tail, the FIFO controller250of a controlled hardware FIFO200may expand and contract the capacity of its buffer without modifying its head or tail.

In one embodiment of the present invention comprising a controlled hardware FIFO and at least one of additional buffer storage510, cache memory440and higher-level memory450, data may be transferred from the FIFO buffer130to said storage as a single block more efficiently than with many individual transfer operations. Similarly, blocks may be transferred from said storage into a hardware FIFO with greater efficiency than individual transfer operations.

Referring now toFIG.9, an embodiment of a split FIFO is discussed. A split FIFO comprises a plurality930(A) of FIFO heads120and tails140, connected to their FIFO buffers930(B) by means of a bus910arbitrated by a bus arbiter920. The FIFO head120and tail140(i.e. “externals” because they are externally accessible) are fed from and feed, respectively, FIFO backing queues930(B) while relegating additional associated FIFO backing values (i.e., “internals”) to additional buffer memory510, or cache440, or higher-level memory450. In such cases where the FIFO's buffer930(A) and930(B) are split, a data access bus910may be used to manage data traffic across the split. For example, and without limitation, access to the bus910may be arbitrated by a bus arbiter920to accommodate multiple FIFOs. Also for example, and without limitation, the FIFO bus interface may itself be a FIFO with the bus910synchronous to the processor core110.

Referring toFIG.6, and referring concurrently toFIG.2, a means of configuring FIFO controller to process incoming data is discussed. One embodiment of the present invention comprises a means of a processor core110configuring and interacting with a controlled hardware FIFO200to processes packets or streams of incoming data, a stream being a potentially indeterminate amount of data. A new set of data (packet or stream)610starts entering a controlled hardware FIFO200at its tail140. Such data is not processed until it reaches the head of the FIFO until previous data is dequeued620. Once the head of a new set of data is detected622, if the FIFO controller has not already been configured to process the new data, the FIFO controller250interrupts the processor core110(630). Eventually the processor core110, may dequeue any amount of header data640. Prior to handing off processing to the FIFO controller250, the processor core110may perform other actions to ensure proper handing650. For example and without limitation, the processor core may initialize a data structure in higher-level memory into which the processed data will be written. The processor core110may then configure the FIFO controller250by means of writing to its configuration registers210. Whether pre-configured, or just configured, the FIFO controller250is now configured to process the incoming data. The FIFO controller250processes each data word670. Such processing may continue indefinitely or until a termination condition is satisfied672. For example, and without limitation, if the data is packetized, such processing may continue until the end of the packet is detected. If the processor core110requested an interrupt674upon completion, the FIFO controller250will then interrupt the processor core110(680). The processor core110may then inspect the FIFO controller250status registers210(690) and complete the current operation695and prepare for the next data to arrive.

Continuing to refer toFIG.6, and referring concurrently toFIG.2andFIG.4, an example said process of incoming data may include data movement under the control of the FIFO controller250. Said controller may, without limitation, write data from its head to computable memory addresses to cache440, higher-level memory450and other FIFOs. Once the FIFO controller is configured, it may perform its function independently, effectively performing a Direct Memory Access (DMA) operation. As the addresses are computed for each data word670, the effect may be a non-unit-stride DMA. Exemplar patterns include, without limitation, a matrix cornerturn, a fast Fourier transform (FFT) butterfly, and a fanning out from one FIFO to many others.

Referring toFIG.7, and referring concurrently toFIG.2, a means of configuring FIFO controller to read and process data is discussed. One embodiment of the present invention, said processor core configures said FIFO controller710to retrieve and process data from at least one of cache memory, other memory, and other memory-mapped FIFO prior to initiating FIFO controller execution. Said processor core may write any required header data to said FIFO720prior initiating FIFO controller processing725. Thereafter, said FIFO controller executes according to said configuration the following steps until FIFO controller satisfies termination condition specified760in said configuration: computing address of next data item according to said configuration730and retrieving next data item from said address740and processing said next data item according to said configuration750. If said FIFO controller is configured to interrupt said processor core770at the completion of said processing, it interrupt said processor core780, which inspects said FIFO configuration and status registers and completes processing790.

Continuing to refer toFIG.7, and referring concurrently toFIG.2andFIG.4, an example said process of outgoing data may include data movement under the control of the FIFO controller250. Said controller may, without limitation, read data from computable memory addresses from cache440, higher-level memory450and other FIFOs and enqueue it at its tail. Once the FIFO controller is configured, it may perform its function independently, effectively performing a Direct Memory Access (DMA) operation. As the addresses are computed for each data word730, the effect may be a non-unit-stride DMA. Exemplar address patterns include, without limitation, a matrix cornerturn, a fast Fourier transform (FFT) butterfly, and a fanning in from many FIFOs to one FIFO.

Referring toFIG.8, and concurrently withFIG.2andFIG.4, an exemplar FIFO “head of queue” and configuration register is shown. The following examples assume, without limitation, that the maximum width of the physical FIFO word is equal to the width of the processor core cache line (as illustrated, 512-bits, although this exemplary configuration is not limiting). As shown, adjacent 512-bit word may contain the next value802to be read from the FIFO and the control variables804to support DMA, respectively. The DMA may execute a simple state machine implemented as part of the FIFO controller250to move data into cache memory440or higher memory450without additional processor core110intervention aside from setting up the transfer. This set up operation may include processing frame headers (if any) and determining where the data should go. The data may be written in non-unit stride. In the illustrated example, the data word is fixed length for any given transfer and the length may be any value less than or equal to 512 (although powers of two are easiest to handle). Those skilled in the art will appreciate that this DMA register example is only illustrative and does not affect the scope of the invention that may include a plurality of registers for accomplishing a plurality of actions.

The potentially wide value word may require multiple accesses to process if it exceeds the width of the data bus112. To facilitate this processing, both dequeuing and non-dequeuing read operations may be employed: one that “consumes” the value (and thus results in the next value in line coming to the queue head) and one that only “peeks” at some portion of the value (up to and including the full value). Employing said combinations of operations, an exemplar the processor core110may “walk” down the 512-bit wide data word 64-bits at a time performing non-dequeuing reads until it reaches the last 64-bit word. It then performs a dequeuing read and consumes the data at the head of the queue, which will have the effect of moving the next data value, if available, to the head of the FIFO. Similarly for a write operation, an exemplar the processor core110with a 64-bit data bus first performs a non-enqueuing write that writes the first 64 bits of data into the FIFO tail. As a non-enqueuing write, the written data cannot move towards the head of the FIFO. Subsequently, the processor core110may “walk” down the 512-bit wide data word 64-bits at a time performing non-enqueuing writes until it reaches the last value to be written. It then performs an enqueuing write that will release the 512-bit word to move towards the head of the FIFO. That word will now be unaffected by subsequent write operations on the hardware FIFO.

Applying the memory-mapped FIFO architectural constructs defined above, various embodiments of microprocessor computing systems employing those constructs will now be discussed.

Implementing Vector and Matrix Instructions

As a matter of definition, a vector processor (or array processor) is a central processing unit (CPU) that implements an instruction set containing instructions that operate on one-dimensional arrays of data called vectors and multi-dimensional arrays of data called matrices. A “stride” of an array (also referred to as increment, pitch or step size) may be defined as the number of locations in memory between beginnings of successive array elements. The SPv2 is a vector processor that has many vector-oriented instructions, such as vector dot product. Because vectors may be unit-stride (e.g., 8 bytes for a single-precision complex values) or non-unit-stride, the vector instructions have a parameter defining the stride (in bytes) between adjacent values. However, if a vector operation is operating upon data stored sequentially in a memory-mapped FIFO that has a single head address, addressing to a FIFO-oriented architecture may be accomplished by simply specifying a vector of stride zero. The result will be that the same address may be read over and over again (thus draining the memory-mapped FIFO) but each access will retrieve a subsequent value from the vector. Similarly, vector writes may fill a memory-mapped FIFO.

Similarly, matrices may be processed using an array of FIFOs, each holding a row or column of a matrix. To perform a matrix-vector product such as beamforming over a stream of incoming data, the processor core110may store the weights in internal registers and accumulate a dot product of these weights and each row of the matrix by dequeuing a value from the head of each FIFO in turn and adding the product of that value with the corresponding weight to the accumulated sum. This extension to this concept of vector instruction processing is particularly valuable when processing data in lock step from several input sources, such as a bank of analog-to-digital (A/D) converters from a radio frequency phased array presenting data as raw input data180. Rather than relying on complex software synchronization and moving data blocks to memory before processing, a processor core110may be configured to read from a plurality of hardware FIFOs100in turn. Doing so may guarantee that all data that starts in synchronization remains in synchronization. If, perhaps due to network congestion, one input falls slightly behind, resulting in an empty FIFO, the processor core110may simply pause (block) until the data arrives and then may continue. If the addresses for the relevant memory-mapped FIFOs have a fixed stride, such a configuration may make it even easier to use existing fixed-stride vector instructions. Similar use cases may apply to WRITE FIFOs. Continuing the example above, if multiple beams are being formed by computing dot products on the input samples from the A/D converters, these synchronized beams may be sent out on WRITE FIFOs for subsequent processing either by the processor core110or by another servicing component. For operations that require a FIFO value to be used several times before moving to the next value, the processor core110may perform non-dequeuing reads until it is time to move to the next value at which point a dequeuing read is performed.

Note that because FIFOs implemented as described herein are memory-mapped, the processor core110may treat them just like any other memory location using efficient primitives like LOAD and STORE operations. Thus, memory-mapped FIFOs advantageously may be operable with existing compilers, using keywords like “volatile” in the C programming language, and assemblers without need for modification. Expensive operations (such as invoking the operating system and interrupt handling) may not generally be required to interact with the memory-mapped FIFOs.

Moving Data Efficiently to/from Memory

Referring toFIG.4, and concurrentlyFIG.2, a means for performing DMA operations is described. A person of skill in the art will immediately recognize the need, in appropriate computation scenarios, to efficiently store FIFO values into cache memory440and higher level memory450. For example, and without limitation, one FIFO value storage approach may be to use a memory-move instruction (referred to as a vector copy) with a zero-stride input or output for writing to and reading from cache memory440, respectively. While such a storage approach may work, the memory-move instruction may involve dedicating the processor core110to the task. Alternatively, certain embodiments of the present invention may include a means to perform Direct Memory Access (DMA) to move data into and out of a memory-mapped FIFO. DMA may effectively “automate” the reading/writing of data from/to cache memory440or higher level memory450. A first step in implementing a DMA storage approach may include specifying by the processor core110writing to the FIFO controller250configuration registers210the address in cache memory440to use as a source or destination to hold the data going to or coming from the FIFO, respectively. For example, and without limitation, this address specification task may take the form either of the processor core110assigning an address for the next incoming/outgoing data, or of a hardware state machine computing the address. Another step in implementing the DMA storage approach may include enforcement of the buffer size limit to avoid buffer overflow. In these ways, the controlled hardware FIFO200may serve as a buffer between bursty processor demands and the desire for block-oriented memory transfer operation. In a modern computer architecture, these transfer operations may advantageously be used for high speed remote dynamic memory access (RDMA) across a network190.

Referring toFIG.4and concurrentlyFIG.2, in one embodiment of the present invention, a FIFO controller250may retrieve data from many locations spread throughout higher-level memory450and enqueue it at its tail140independently from the processor core in a sophisticated form of prefetch. A benefit of this approach is that potentially many page opening latency penalties may be masked, and but avoiding the cache, the cache is not forced to evict data. Similarly, a FIFO controller250may write to many locations in higher-level memory450.

Chaining FIFOs and FIFO-Like Stream Processors

Continuing to refer toFIG.4and concurrentlyFIG.2, as described above, a DMA implementation according to an embodiment of the present invention (seeFIG.1) may be directed to transfer of data between cache memory440and FIFO banks300, but the controllable hardware FIFOs200may be memory mapped just like any other address. Therefore, a variant of DMA may forward data from one FIFO into another. Such a mechanism may advantageously support efficient store and forward patterns, and may be especially advantageous for off-loading incoming sensor data to alternative processors or chips.

In certain embodiments of the present invention, elements being chained need not actually be FIFOs, but instead need only implement the FIFO interface. For example, and without limitation, non-FIFO functional blocks that may implement a FIFO interface (e.g., enqueue and dequeue) may include integer-to-floating point converters (and reverse), TCP/IP offload engines, encryptors/decryptors, encoders/decoders, and checksum generators/checkers. Without programming, said functional blocks may stream process their inputs (sources) into outputs streamed to their outputs (sinks). In addition to forming a means to readily insert potentially significant hardware accelerators into an architecture, this embodiment of the present invention may allow such processing to be strung together; as long as the functional blocks implement FIFO interfaces, such elements may be chained by “forwarding” the head of one FIFO into the tail of another. By repeating this process, a chain of arbitrary length may be constructed. Unlike known techniques for chaining FIFOs together, chaining of memory-mapped FIFOs may implement data manipulations and may be addressed using the same techniques as transfers to memory.

Splitting FIFO Streams

Referring toFIG.2, given the flexibility of FIFO data consumption, DMA, and processing described above, certain embodiments of the present invention may be configured to advantageously process a stream of data in more than one way; in essence, to split a FIFO stream (or frame) into two or more copies.

For example, and without limitation, splitting may be accomplished using a source FIFO head120and a plurality of consumers (FIFO tails140), wherein the FIFO head controller forwards the data word at the head to each of the plurality of tail FIFOs before the word is dequeued. Also for example, and without limitation, splitting may be accomplished within a processing step whereby the processor core110(seeFIG.1) may consume incoming data, but as it consumes that data for its own purposes, it also forwards the data to another FIFO. This FIFO may be hard-coded in the processor core's110hardware or firmware, or the FIFO may be selected arbitrarily by the host processor core110as described above for DMA transfers.

Merging FIFO Streams

Referring toFIG.2, certain embodiments of the present invention may be configured to advantageously process merging of two or more data streams into a single FIFO stream (or frame). That is, the inverse of splitting FIFO streams is merging FIFO streams. Two forms of merging are of particular interest in the context of memory-mapped FIFOs, and each has advantageous practical applications. The first is data-word-by-data-word consumption from a plurality of FIFOs. This consumption may be synchronous or asynchronous (Note: “synchronous” consumption need not be with respect to a “global” clock because FIFOs are often asynchronous devices; therefore, synchronization may be defined herein as respective to a local clock). After a word from each FIFO has been consumed, the outputs may be processed in any manner desirable. A generalization of this concept may be that such consumption need not be one-for-one. For example, and without limitation, to compute a scalar-vector product, a single word (representing a single-precision floating point number) may be consumed from one FIFO and then used to scale each value consumed from another FIFO. As such, data values may be consumed arbitrarily according to the logic of the consuming processor. One embodiment of the present invention may configure a merging FIFO to dequeue one value from each of a plurality of FIFO heads and process or enqueue them onto the merging FIFO's tail.

Another form of merging is at the “Frame” level. In this case, the processor may alternate in arbitrary order among a plurality of incoming FIFOs and may forward a plurality of data words from that FIFO before selecting the next FIFO. An example of frame-level merging is forwarding from multiple incoming network queues into a single TCP/IP offload engine. The data packets may be transferred in their entirety as a block/frame without insertion of other values.

FIFO Status

Referring now toFIG.8, and continuing to refer toFIG.2, in certain embodiments of the present invention, several elements of status that may be of practical value for the processor core110to read or write currently may not be accessible under the scheme described above. Simple status bits such as FIFO_EMPTY, FIFO_FULL, FIFO_ALMOST_EMPTY, and FIFO_ALMOST_FULL (see also820atFIG.8) may be used to inform potential readers and writers of a hardware FIFO of the current state of said FIFO. Each of these, as well as other FIFO status indicators known in the art, may be used by the processor core110to handle exceptional conditions or to avoid stalling when the FIFO is empty or full. Additionally, as described above, certain embodiments of the present invention may associate data stored at a fixed address with the configuration804of said hardware FIFO100, such that the addresses, stride (modulus), and length may define the parameters for DMA operations. Mapping this status and configuration data210into a readable and writable location may advantageously allow the processor core110to access these data. Given that the FIFO200may be mapped into the address space of the processor core110, a natural, although not the only, implementation may be to use an adjacent memory address to access and manipulate said configuration and status data. Alternatively, dedicated registers defined for that purpose in the internal architecture of the processor core are anticipated, although such a solution may require extensive changes to the processor core and potentially to the instruction set.

Accommodating Differing Datum Sizes

Referring again toFIG.1, a person of skill in the art will immediately recognize that data packets, and particularly those from raw I/O sources180, may not match a word size or cache line size of one or more processor cores available within a computing system. For example, and without limitation, when manipulating data streaming from A/D converters, it is possible that 12-bit values may be of interest. The controllable hardware FIFO200may need to be able to accommodate differing datum sizes to offload data manipulation functions from the processor core110. Employing the invention described herein, the FIFO configuration word may be a practical location to place this configuration information.

For example, and without limitation, one implementation may include a plurality of data elements concatenated on a single cache line. As data is read, according to the word size of the fetch instruction, the data may be shifted and masked as necessary to align the data by either the processor core110or the FIFO controller250. Another embodiment may define a composite record (up to the size of the cache line) that may contain a plurality of sub-records. This processor core110may read the record and may deconstruct the sub-records in software or, alternatively, may parallel-load the sub-records into as many registers as appropriate. The semantics enforced may dictate that the record is not available until the entire set of bytes comprising the record is available. Such an implementation may require that the sender and receivers agree on the datum length apriori. One implementation option may be that data is framed and that the frame header indicates the datum length for the data within it. Similar mechanisms may be used on both enqueuing and dequeuing.

Cache Line “Pinning”

Referring toFIG.4and concurrently toFIG.2, a means to implement a hardware FIFO100as part of a cache is discussed. An embodiment of the present invention wherein memory-mapped FIFOs100are managed within the cache memory440that maximizes reuse of an existing cache controller is now described in more detail. For example, and without limitation, in a typical memory cache configuration known in the art, data from a small set of memory locations (typically addressed by their location in higher-level memory450but placed according to the cache architecture) may be replicated in the cache memory440. That data may be brought in and evicted as needed, and several schemes exist for choosing how physical addresses are mapped to cache locations and which cache lines are evicted. In this embodiment of the present invention, the addresses of the FIFOs100may be mapped into, and managed by the cache. However, because hardware FIFOs100represent physical structures and not just data, they may not be “evicted” from the cache memory440. Effectively, memory-mapped FIFOs act as if they are pinned in the cache memory440permanently. For example, and without limitation, cache pinning may be implemented as a 5-way set associative cache where one “way” may be dedicated to the FIFO banks330. In practice, as indicated inFIG.4, such FIFO banks300may sit alongside of the cache memory440rather than inside it.

As described above, various embodiments of the present invention exemplify how a small state machine may convert a simple FIFO mechanism into a powerful tool to map data into memory and/or forward data across a distributed computing architecture. In addition, if an FPGA or small microprocessor or microcontroller is added to the FIFO control design, additional functions such as data-dependent processing and routing and format translation may be performed on the fly that may be valuable for various applications. For example, and without limitation, converting 16-bit integer data into IEEE single-precision floating point representation, and dropping or capping outlier data, multi-step parallel sorting algorithms may be implemented where FIFOs represent bins in a multi-step sort, and moving averages may be computed.

Referring again toFIG.2, the concept of adding an FPGA or other programmable device to the FIFO controller250of present invention may open the potential for either a static configuration or runtime modification of FIFO controller logic. Run time configuration may be accomplished by at least one mechanism for a processor core to load a program/configuration into the programmable device. In an embodiment of the present invention using an FPGA, such configuration data may include the configuration of the FPGA logic or said logic may be configured statically. Potential mechanisms include having the controller's program storage memory-mapped into the address space of the processor core110, having a port through which the processor core110pushes the program, and having external signals that permit the FIFO controller250programs to be executable independently of the processor core110.

Because of the ease of operating the FIFO interfaces using simple processor instructions (e.g., LOAD and STORE), much of the complexity commonly associated with messaging may be avoided, thus facilitating very low latency processing that may be advantageous to time-sensitive applications such as financial trading. For example, and without limitation, a processor core with a writable micro-store may be able to process entire messages with a single compound instruction. To continue the example of financial decisions, complex event processing may execute without interruption and without fetching instructions from memory.

While one advantageous use of the invention may be for handling high data rate computation and microprocessor computer systems, the FIFO abstraction and the mapping into simple processor instructions may allow low-power processors to more efficiently handle incoming and out-going data, which may be particularly appropriate and advantageous for internet-of-things (IoT) devices.

Multiprocessor Systems

Referring toFIG.4and concurrentlyFIG.6, a multiprocessor system employing hardware FIFOs is described. Multiprocessor systems, especially those comprising multiple processing cores110on a processor die, require high-speed communications. Such systems, may employ crossbar networks or other network topologies that present processor cores110with a plurality of incoming and outgoing network ports190. Such architectures advantageously may employ memory-mapped controllable FIFOs200to efficiently create, consume, and transmit high speed packet data (FIG.6), while minimizing load on the processor cores. Likewise, high-speed multi-processor system communications means such as Remote Direct Memory Access (RDMA) may advantageously employ memory mapped FIFOs. One embodiment of the present invention is a multicomputer system comprising a plurality of computational nodes connected to a communications network through memory-mapped controllable FIFOs200. A further embodiment of the present invention further comprises fixed functionality computational blocks that at least one of consumes data from at least one memory-mapped hardware FIFO and produces data that is enqueued on a memory-mapped hardware FIFO.

Some of the illustrative aspects of the present invention may be advantageous in solving the problems herein described and other problems not discussed which are discoverable by a skilled artisan.

While the above description contains much specificity, these should not be construed as limitations on the scope of any embodiment, but as exemplifications of the presented embodiments thereof. Many other ramifications and variations are possible within the teachings of the various embodiments. While the invention has been described with reference to exemplary embodiments, it will be understood by those skilled in the art that various changes may be made and equivalents may be substituted for elements thereof without departing from the scope of the invention. In addition, many modifications may be made to adapt a particular situation or material to the teachings of the invention without departing from the essential scope thereof. Therefore, it is intended that the invention not be limited to the particular embodiment disclosed as the best or only mode contemplated for carrying out this invention, but that the invention will include all embodiments falling within the scope of the appended claims. Also, in the drawings and the description, there have been disclosed exemplary embodiments of the invention and, although specific terms may have been employed, they are unless otherwise stated used in a generic and descriptive sense only and not for purposes of limitation, the scope of the invention therefore not being so limited. Moreover, the use of the terms first, second, etc. do not denote any order or importance, but rather the terms first, second, etc. are used to distinguish one element from another. Furthermore, the use of the terms a, an, etc. do not denote a limitation of quantity, but rather denote the presence of at least one of the referenced item.

Thus the scope of the invention should be determined by the appended claims and their legal equivalents, and not by the examples given.