SYSTEMS AND METHODS FOR MAPPING HARDWARE FIFO TO PROCESSOR ADDRESS SPACE

Abstract

An apparatus for a microprocessor computer system and method for configuring the same where said microprocessor computer system comprises a processor core and at least one hardware buffer FIFO with memory-mapped head and tail that handles data movement among the processor cores, networks, raw data input and outputs, and memory. The method for configuring said microprocessor computer system comprises utilizing a FIFO auxiliary processor to process said data traversing said hardware FIFO; utilizing said hardware FIFOs to efficiently pipe data through functional blocks; and utilizing a FIFO controller to perform DMA operations that include non-unit-stride access patterns and transfers among processor cores, networks, raw data input and outputs, memory, and other memory-mapped hardware FIFOs.

Claims

1. A method of configuring a microprocessor computer system, wherein said microprocessor computer system comprises: a plurality of external data streams, each associated with a distinct memory-mapped FIFO; and a processor core that processes multiple sequential iterations of a vector operation, each iteration requiring the processing of a datum from each of the data streams before proceeding to the next iteration; said method comprising, for each iteration of the vector operation, configuring said vector operation to access each memory-mapped FIFO in turn and to stall if any such access is invalid.

2. (canceled)

3. The method of claim 21, wherein the plurality of external data streams is a plurality of external input data streams; wherein each of said input data streams in enqueued in a distinct memory-mapped FIFO and said processor core must dequeue and process one datum from each memory-mapped FIFO for each iteration; wherein an invalid access of a memory-mapped FIFO comprises executing a read operation against an empty FIFO; and wherein iterating said vector operation results in processing the external input data streams.

4. (canceled)

5. The method of claim 1, wherein the plurality of external data streams is a plurality of external output data streams; wherein each of said output data streams is dequeued from a distinct memory-mapped FIFO and said processor core must enqueue one datum to each memory-mapped FIFO for each iteration; wherein an invalid access of a memory-mapped FIFO comprises executing a write operation against an full FIFO; and wherein iterating said vector operation results in generating the external output data streams.

6. (canceled)

7. The method of claim 1, wherein said external data streams are synchronously sampled data from a multiplicity of analog-to-digital converters.

8. The method of claim 1, wherein each said memory-mapped FIFO is accessed by said processor core as an address.

9. The method of claim 8, wherein the said processor core reads said memory-mapped FIFO by reading said address.

10. The method of claim 9, wherein said step of reading said address dequeues a value at the head of a queue.

11. The method of claim 8, wherein said processor core writes to said memory-mapped FIFO by writing said address.

12. The method of claim 11, wherein said step of writing said address enqueues a value at the head of a queue.

13. The method of claim 12, wherein said processor core will stall when writing to a full memory-mapped FIFO.

14. The method of claim 1, wherein when said plurality of external data streams are stored sequentially in said memory-mapped FIFO, said memory-mapped FIFO is addressed by specifying a vector stride of zero.

15. The method of claim 14, wherein said step of specifying a vector stride of zero reads a same address repeatedly to access all data in said memory-mapped FIFO.

16. The method of claim 1, wherein when said plurality of external data streams are to be stored sequentially in said memory-mapped FIFO, a write to the same memory-mapped FIFI address will fill said memory-mapped FIFO when a vector stride of zero is specified.

16. The method of claim 1, wherein said processor core will read and dequeue data at the head of a non-empty said memory-mapped FIFO and will block said read operation when said memory-mapped FIFO is empty.

17. The method of claim 1, wherein said processor core will read data at the head of a non-empty said memory-mapped FIFO and will block said read operation when said memory-mapped FIFO is empty.

18. The method of claim 1, wherein said processor core will read and dequeue data at the head of a non-empty said memory-mapped FIFO and will return an invalid value when said memory-mapped FIFO is empty.

19. The method of claim 1, wherein said processor core will read data at the head of a non-empty said memory-mapped FIFO and return an invalid value when said memory-mapped FIFO is empty.

20. The method of claim 18, wherein said processor core remains un-stalled when said invalid value is returned.

21. The method of claim 19, wherein said processor core remains un-stalled when said invalid value is returned.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0033] FIG. 1 is a schematic block diagram of an exemplary microprocessor computer system employing a processor core and a memory-mapped hardware First In, First Out (FIFO) buffer architecture according to an embodiment of the present invention.

[0034] FIG. 2 a schematic block diagram of a memory-mapped hardware FIFO buffer further comprising a FIFO controller architecture according to an embodiment of the present invention.

[0035] FIG. 3 a schematic block diagram of an exemplary FIFO bank comprising at least one hardware FIFO according to an embodiment of the present invention.

[0036] FIG. 4 is a schematic block diagram of an exemplary microprocessor computer system employing a processor core, an exemplary FIFO bank, cache memory, and a higher-level memory according to an embodiment of the present invention.

[0037] FIG. 5 is a schematic block diagram of an exemplary FIFO bank, cache memory, and additional buffer memory according to an embodiment of the present invention.

[0038] FIG. 6 is a flowchart of a method of employing a hardware FIFO to process an incoming data packet according to an embodiment of the present invention.

[0039] FIG. 7 is a flowchart of a method of employing a hardware FIFO to process an outgoing data packet according to an embodiment of the present invention.

[0040] FIG. 8 an exemplary configuration register for a FIFO controller for controlling non-unit-stride Direct Memory Access data transfer and status reporting according to an embodiment of the present invention.

[0041] FIG. 9 is a schematic block diagram of an exemplary split FIFO comprising a FIFO bank and additional buffer memory connected by means of a bus according to an embodiment of the present invention.

DETAILED DESCRIPTION OF THE INVENTION

[0042] 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.

[0043] 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.

[0044] 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.

[0045] Referring to FIGS. 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.

[0046] 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:

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

[0048] 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)

[0049] Referring now to FIGS. 1 through 9, the following features of the present invention may contribute to providing the advantages listed above:

[0050] A) Hardware FIFO(s) 100 that efficiently enqueues data on behalf of a processor core 110.

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

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

[0053] D) Hardware FIFO(s) 100 backed by expandable buffer space in at least one of cache memory 440, higher-level memory 450, and additional buffer memory 510.

[0054] E) Processor core(s) 110 operably coupled with at least one of hardware FIFOs (100) and FIFO banks(s) 300 and cache memory 440 via shared busses 131 and 150 and shared control signals 114.

[0055] F) Processor core(s) 110 operably coupled with at least one of hardware FIFOs 100 and FIFO banks(s) 300, cache memory 440, and higher-level memory 450 through arbiters that mediate resource contention.

[0056] 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 Controller 250.

[0057] 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

[0058] 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).

[0059] Memory-Mapped First-In First-Out (FIFO) Queue

[0060] Referring more specifically to FIG. 1, the hardware FIFO 100 according to an embodiment of the present invention will now be discussed. The hardware FIFO 100 may comprise a head 120, a tail 140, and a FIFO buffer 130. The hardware FIFO head 120 may be operably coupled with at least one of the data bus to fetch data 154, a raw output port 180, and a network output port 190. Similarly, the hardware FIFO 140 tail may be operably coupled with at least one the data bus to write data 152, a raw input port 180, and a network input port 190. An address decoder 160 for the head 120 detects if a memory operation affects the FIFO head 120. An address decoder 161 for the tail 140 detects if the memory operation affects the FIFO tail 140. The hardware FIFO may be configured to support enqueuing and dequeuing operations either synchronously or asynchronously. Said enqueuing operations from network 190 or raw inputs 180 are strobed by means of control signals 192 and 182 respectively, 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 signal 191 and 181, respectively, indicating valid data is available on the appropriate port.

[0061] As described above, because a hardware FIFO bank 100 is characterized by a single head 120 and tail 140, such a FIFO 100 may be mapped to a single physical address of the processor core 110 or a virtual address of a process running on said processor core. One embodiment of the present invention may employ one address for the head 120 of the FIFO 100 and another address for the tail 140. An alternative embodiment of the present invention may use a single address for both head 120 and tail 140, but may recognize the logical distinction that a write to that address is enqueuing data at the tail 140 and a read is dequeuing data from the head 120 of the queue. Mapping a FIFO 100 into the address space of the processor core 110, as opposed to a dedicated internal register, is an advantage of the present invention.

[0062] The FIFO buffer 130 provides 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 buffer 130 is fixed.

[0063] When writing (enqueuing) on the memory-mapped FIFO 100, the processor core 110 may 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 core 110 or the requesting process or thread. However, an alternative embodiment may be to operate to allow a write to fail.

[0064] A hardware FIFO 100 may be mapped to a memory location in the physical address space of the processor core 110. Additionally, said hardware FIFO 100 may be mapped into the virtual address space of one or more processes executing on the processor core.

[0065] In one embodiment of the present invention, each hardware FIFO 100 may present either its head 120 or its tail 140 to the processor core 110 if its tail is written to or its head is read from, respectively, at least one of the Network 190, Raw I/O 180, other storage, and other FIFOs 100. 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 ends 120, 140 of the FIFO 100 may be exposed to the processor core 110 for tasks such as inter-thread or inter-process communication.

[0066] How the processor core 110 may interact with a memory-mapped FIFO 100 will 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 signals 114 to 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 core 110 is to consume a value from a memory-mapped hardware FIFO 100, 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 core 110. If the FIFO is empty, the processor core 110 may observe a condition similar to a “cache miss” and may respond like it would to any cache miss—generally, by stalling the processor core 110 or the requesting process or thread executing on the processor core 110 until 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 core 110 is 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).

[0067] Variants of this typical READ behavior may have valuable use cases that require enhancements to the processor core 110 beyond 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 core 110 completely.

[0068] Referring more specifically to FIG. 2, the controlled hardware FIFO 200 according to an embodiment of the present invention will now be discussed. The controlled hardware FIFO 200 may comprise most elements of a head 120, a tail 140, and a FIFO buffer 130, FIFO controller 250, and configuration and status registers 210 read from and written to by the FIFO controller 250 by means of bus 211, and control signals 251 and 252 to control reading from the head and writing to the tail, respectively. The hardware FIFO head 120 may be operably coupled with at least one of the data bus to fetch data 154, a raw output port 180, and a network output port 190. Similarly, the hardware FIFO 140 tail may be operably coupled with at least one the data bus to write data 152, a raw input port 180, and a network input port 190. An address decoding is performed by the FIFO controller 250. The hardware FIFO may be configured to support enqueuing and dequeuing operations either synchronously or asynchronously under control of the FIFO controller 250 through control signals 252 and 251, respectively. Said enqueuing operations from network 190 or raw inputs 180 are strobed by means of control signals 192 and 182 respectively, 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 signal 191 and 181, respectively, indicating valid data is available on the appropriate port. The FIFO controller 250 is operably coupled with the configuration and status registers 210 by means of bus 211. Said registers 210 may be used to at least one of configure a state machine and microcontroller within the FIFO controller 250, provide scratch storage space to support FIFO controller 250 execution, hold FIFO controller 250 software, and indicate status back to the processor core 110. Configuration and status registers 210 may also be memory mapped into the processor address space to facilitate writing of configuration data and reading of status information by the processor core 110.

[0069] Referring more specifically to FIG. 3, the FIFO bank 300 according to an embodiment of the present invention will now be discussed. The FIFO bank 300 comprises at least one controlled hardware FIFO 200, address and data busses and control signals previously described for the controlled hardware FIFO, and a local bus 330. Said local bus 330 permits data movement among controlled hardware FIFOs without affecting the operation of the processor core 110, other FIFO banks, or other components sharing the address 131 and data 150 busses and control signals used by the FIFO bank 300.

[0070] Referring more specifically to FIG. 4, the microprocessor computer system 400 employing a memory-mapped FIFO architecture according to an embodiment of the present invention will now be discussed. The system 400 may comprise a processor core 110 configured in data communication with a cache memory 440 and a higher-level memory 450, which typically represents memory higher in the memory hierarchy, by means of memory interface 453. Inserted into at least one data communication path between the processor core 110 and the cache memory 440 and/or the higher-level memory 450 may be one or more hardware FIFO banks 300 and a FIFO arbiter 420. Each of the FIFO bank 300 comprises 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 data 190, and/or other forms of inter-thread communication and inter-processor communication. The microprocessor computer system 400 may include one or more FIFO banks 300. 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 core 110 and busses and signals to and from higher-level memory 450. A FIFO arbiter 420 may arbitrate communications to and from the processor core 110. The memory arbiter 470 may arbitrate communications to the memory 450 using a memory access controller 460 that detects contention for access to higher-level memory 450. The FIFO arbiter 420 may split the data buses 450 from the processor core 110 into separate address busses to the FIFO banks(s) 150 and the cache memory 442. Similarly, the FIFO arbiter 420 may split the address bus, 411 from the processor core 110 into separate address busses to the FIFO banks(s) 131 and the cache memory 441. Similarly, control signals may be combined and arbitrated by the FIFO controller 420; these include cache control signals 414, 114, and 444. If address busses, data busses, and control signals are suitable compatible and controlled to avoid contention, the corresponding logic of the FIFO controller 420 may simply wire the corresponding signals together. The memory arbiter 470 similarly arbitrates among the FIFO banks(s) 300 and cache memory 440 for access to memory 450 by means of memory interface 453 under control of the memory access controller 460. An additional embodiment of the present invention augments existing cache controls 414 with additional signals to enable additional FIFO operations. FIG. 4 depicts without limitation a FIFO bank 300 positioned in between the processor core 110 and its cache 440; those skilled in the art will appreciate that there are many alternative configurations for physically locating a FIFO bank 300 and the cache 440, including incorporation of a FIFO bank 300 into the cache 440.

[0071] In an embodiment of the present invention that does not require a FIFO arbiter 420, the processor core 110 may use the same busses 411 and 450 and control signals 414 to interact with the FIFO bank(s) 300 as it does for the cache memory 440.

[0072] Referring more specifically to FIG. 5, and referring concurrently to FIG. 2 and FIG. 4, a split FIFO expansion of FIFO buffer capacity is discussed. One embodiment of the present invention, a FIFO bank 300 and at least one of an additional buffer memory 510 that may expand the FIFO buffer 130 capacity of the controlled hardware FIFOs 200 within the FIFO bank 300. In this embodiment, the additional buffer memory may expand the depth of the FIFO buffer 130 of at least one of the controlled hardware FIFO 200 within the FIFO bank 300. In yet another embodiment of the present invention, cache memory 440 or higher-level memory 450 may 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 core 110, network I/O 190, Raw I/O 180 and other FIFOs only interact with data on a controlled hardware FIFO through operations on its head and tail, the FIFO controller 250 of a controlled hardware FIFO 200 may expand and contract the capacity of its buffer without modifying its head or tail.

[0073] In one embodiment of the present invention comprising a controlled hardware FIFO and at least one of additional buffer storage 510, cache memory 440 and higher-level memory 450, data may be transferred from the FIFO buffer 130 to 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.

[0074] Referring now to FIG. 9, an embodiment of a split FIFO is discussed. A split FIFO comprises a plurality 930(A) of FIFO heads 120 and tails 140, connected to their FIFO buffers 930(B) by means of a bus 910 arbitrated by a bus arbiter 920. The FIFO head 120 and tail 140 (i.e. “externals” because they are externally accessible) are fed from and feed, respectively, FIFO backing queues 930(B) while relegating additional associated FIFO backing values (i.e., “internals”) to additional buffer memory 510, or cache 440, or higher-level memory 450. In such cases where the FIFO's buffer 930(A) and 930(B) are split, a data access bus 910 may be used to manage data traffic across the split. For example, and without limitation, access to the bus 910 may be arbitrated by a bus arbiter 920 to accommodate multiple FIFOs. Also for example, and without limitation, the FIFO bus interface may itself be a FIFO with the bus 910 synchronous to the processor core 110.

[0075] Referring to FIG. 6, and referring concurrently to FIG. 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 core 110 configuring and interacting with a controlled hardware FIFO 200 to processes packets or streams of incoming data, a stream being a potentially indeterminate amount of data. A new set of data (packet or stream) 610 starts entering a controlled hardware FIFO 200 at its tail 140. Such data is not processed until it reaches the head of the FIFO until previous data is dequeued 620. Once the head of a new set of data is detected 622, if the FIFO controller has not already been configured to process the new data, the FIFO controller 250 interrupts the processor core 110 (630). Eventually the processor core 110, may dequeue any amount of header data 640. Prior to handing off processing to the FIFO controller 250, the processor core 110 may perform other actions to ensure proper handing 650. 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 core 110 may then configure the FIFO controller 250 by means of writing to its configuration registers 210. Whether pre-configured, or just configured, the FIFO controller 250 is now configured to process the incoming data. The FIFO controller 250 processes each data word 670. Such processing may continue indefinitely or until a termination condition is satisfied 672. 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 core 110 requested an interrupt 674 upon completion, the FIFO controller 250 will then interrupt the processor core 110 (680). The processor core 110 may then inspect the FIFO controller 250 status registers 210 (690) and complete the current operation 695 and prepare for the next data to arrive.

[0076] Continuing to refer to FIG. 6, and referring concurrently to FIG. 2 and FIG. 4, an example said process of incoming data may include data movement under the control of the FIFO controller 250. Said controller may, without limitation, write data from its head to computable memory addresses to cache 440, higher-level memory 450 and 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 word 670, 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.

[0077] Referring to FIG. 7, and referring concurrently to FIG. 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 controller 710 to 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 FIFO 720 prior initiating FIFO controller processing 725. Thereafter, said FIFO controller executes according to said configuration the following steps until FIFO controller satisfies termination condition specified 760 in said configuration: computing address of next data item according to said configuration 730 and retrieving next data item from said address 740 and processing said next data item according to said configuration 750. If said FIFO controller is configured to interrupt said processor core 770 at the completion of said processing, it interrupt said processor core 780, which inspects said FIFO configuration and status registers and completes processing 790.

[0078] Continuing to refer to FIG. 7, and referring concurrently to FIG. 2 and FIG. 4, an example said process of outgoing data may include data movement under the control of the FIFO controller 250. Said controller may, without limitation, read data from computable memory addresses from cache 440, higher-level memory 450 and 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 word 730, 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.

[0079] Referring to FIG. 8, and concurrently with FIG. 2 and FIG. 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 value 802 to be read from the FIFO and the control variables 804 to support DMA, respectively. The DMA may execute a simple state machine implemented as part of the FIFO controller 250 to move data into cache memory 440 or higher memory 450 without additional processor core 110 intervention 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.

[0080] The potentially wide value word may require multiple accesses to process if it exceeds the width of the data bus 112. 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 core 110 may “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 core 110 with 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 core 110 may “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.

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

[0082] Implementing Vector and Matrix Instructions

[0083] 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.

[0084] 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 core 110 may 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 data 180. Rather than relying on complex software synchronization and moving data blocks to memory before processing, a processor core 110 may be configured to read from a plurality of hardware FIFOs 100 in 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 core 110 may 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 core 110 or by another servicing component. For operations that require a FIFO value to be used several times before moving to the next value, the processor core 110 may perform non-dequeuing reads until it is time to move to the next value at which point a dequeuing read is performed.

[0085] Note that because FIFOs implemented as described herein are memory-mapped, the processor core 110 may 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.

[0086] Moving Data Efficiently to/from Memory

[0087] Referring to FIG. 4, and concurrently FIG. 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 memory 440 and higher level memory 450. 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 memory 440, respectively. While such a storage approach may work, the memory-move instruction may involve dedicating the processor core 110 to 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 memory 440 or higher level memory 450. A first step in implementing a DMA storage approach may include specifying by the processor core 110 writing to the FIFO controller 250 configuration registers 210 the address in cache memory 440 to 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 core 110 assigning 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 FIFO 200 may 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 network 190.

[0088] Referring to FIG. 4 and concurrently FIG. 2, in one embodiment of the present invention, a FIFO controller 250 may retrieve data from many locations spread throughout higher-level memory 450 and enqueue it at its tail 140 independently 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 controller 250 may write to many locations in higher-level memory 450.

[0089] Chaining FIFOs and FIFO-Like Stream Processors

[0090] Continuing to refer to FIG. 4 and concurrently FIG. 2, as described above, a DMA implementation according to an embodiment of the present invention (see FIG. 1) may be directed to transfer of data between cache memory 440 and FIFO banks 300, but the controllable hardware FIFOs 200 may 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.

[0091] 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.

[0092] Splitting FIFO Streams

[0093] Referring to FIG. 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.

[0094] For example, and without limitation, splitting may be accomplished using a source FIFO head 120 and a plurality of consumers (FIFO tails 140), 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 core 110 (see FIG. 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's 110 hardware or firmware, or the FIFO may be selected arbitrarily by the host processor core 110 as described above for DMA transfers.

[0095] Merging FIFO Streams

[0096] Referring to FIG. 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.

[0097] 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.

[0098] FIFO Status

[0099] Referring now to FIG. 8, and continuing to refer to FIG. 2, in certain embodiments of the present invention, several elements of status that may be of practical value for the processor core 110 to 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 also 820 at FIG. 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 core 110 to 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 configuration 804 of said hardware FIFO 100, such that the addresses, stride (modulus), and length may define the parameters for DMA operations. Mapping this status and configuration data 210 into a readable and writable location may advantageously allow the processor core 110 to access these data. Given that the FIFO 200 may be mapped into the address space of the processor core 110, 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.

[0100] Accommodating Differing Datum Sizes

[0101] Referring again to FIG. 1, a person of skill in the art will immediately recognize that data packets, and particularly those from raw I/O sources 180, 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 FIFO 200 may need to be able to accommodate differing datum sizes to offload data manipulation functions from the processor core 110. Employing the invention described herein, the FIFO configuration word may be a practical location to place this configuration information.

[0102] 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 core 110 or the FIFO controller 250. 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 core 110 may 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.

[0103] Cache Line “Pinning”

[0104] Referring to FIG. 4 and concurrently to FIG. 2, a means to implement a hardware FIFO 100 as part of a cache is discussed. An embodiment of the present invention wherein memory-mapped FIFOs 100 are managed within the cache memory 440 that 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 memory 450 but placed according to the cache architecture) may be replicated in the cache memory 440. 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 FIFOs 100 may be mapped into, and managed by the cache. However, because hardware FIFOs 100 represent physical structures and not just data, they may not be “evicted” from the cache memory 440. Effectively, memory-mapped FIFOs act as if they are pinned in the cache memory 440 permanently. 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 banks 330. In practice, as indicated in FIG. 4, such FIFO banks 300 may sit alongside of the cache memory 440 rather than inside it.

[0105] 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.

[0106] Referring again to FIG. 2, the concept of adding an FPGA or other programmable device to the FIFO controller 250 of 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 core 110, having a port through which the processor core 110 pushes the program, and having external signals that permit the FIFO controller 250 programs to be executable independently of the processor core 110.

[0107] 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.

[0108] 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.

[0109] Multiprocessor Systems

[0110] Referring to FIG. 4 and concurrently FIG. 6, a multiprocessor system employing hardware FIFOs is described. Multiprocessor systems, especially those comprising multiple processing cores 110 on a processor die, require high-speed communications. Such systems, may employ crossbar networks or other network topologies that present processor cores 110 with a plurality of incoming and outgoing network ports 190. Such architectures advantageously may employ memory-mapped controllable FIFOs 200 to 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 FIFOs 200. 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.

[0111] 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.

[0112] 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.

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