System for memory mapped hardware first in first out

1 . A system of memory-mapped hardware FIFOs and monotonic state variables, the system comprising: any number of memory-mapped hardware FIFOs defined as sets of readable and writable memory-mapped hardware registers, wherein different FIFOs in the system are independent, wherein each FIFO has its own maximum number of entries and element size; a memory interface to hardware logic that implements a queue with FIFO semantics, wherein a memory store operation on an address of a memory-mapped register performs an enqueue operation, and a memory load operation performs a dequeue operation; a memory interface to hardware logic that implements polling of the memory-mapped hardware FIFOs for readability and writability, wherein a memory load operation on a memory address of a memory-mapped register returns an indication of a set of FIFOs that are readable when at least one element is enqueued, and another memory load operation returns an indication of a set of FIFOs that are writable when a FIFO is not full; and any number of memory-mapped monotonic state variables defined as sets of readable and writable memory-mapped hardware registers, wherein different monotonic state variables are defined in pairs such that a value of one variable in the pair is bounded by another in the pair, and wherein values of the monotonic state variables are reset to zero without losing their monotonic property.

2 . The system of claim 1 , further comprising memory-mapped writable registers for performing FIFO enqueue operations, wherein the system performs steps of: utilizing a memory-mapped register assigned a memory address in an address space of the system, wherein different processors and execution elements perform memory store operations to enqueue data to the FIFO, wherein each memory store operation is atomic, wherein a register size equals an object size being enqueued, and wherein the object size corresponds to any word size supported by the system, including bytes, half words, words, double words, and quad words; and utilizing the hardware logic to implement the FIFO, wherein the logic is abstracted from a user such that the user interacts with the FIFO solely through memory operations.

3 . The system of claim 1 , further comprising memory-mapped readable registers for performing FIFO dequeue operations, wherein the system performs steps of: utilizing a memory-mapped register assigned a memory address in an address space of the system, wherein different processors and execution elements perform memory load operations to dequeue from the FIFO, wherein each memory load is an atomic operation, wherein a register size equals an object size being dequeued, wherein the object size corresponds to any word size supported by the system, and wherein if a load operation is performed when the FIFO is not empty, a first element is dequeued and returned as a result of the memory load operation, and if a load operation is performed when the FIFO is empty, a special null value is returned indicating that the FIFO is empty; and utilizing hardware logic to implement the FIFO, wherein the logic is abstracted from a user such that the user interacts with the FIFO solely through memory operations.

4 . The system of claim 1 , further comprising memory-mapped readable registers for reading FIFO status information, wherein the system performs steps of: utilizing a memory-mapped register assigned a memory address in an address space of the system, wherein different processors and execution elements perform memory load operations on the address of the register to read status information about the FIFO, wherein the status information includes an indication of whether the FIFO is full, an indication of whether the FIFO is empty, a number of elements enqueued on the FIFO, a number of available elements that can be enqueued on the FIFO, and a maximum number of elements of the FIFO.

5 . The system of claim 1 , further comprising memory-mapped FIFO control and configuration registers, wherein the system performs steps of: utilizing a memory-mapped register assigned a memory address in an address space of the system, wherein different processors and execution elements perform memory store operations on the address of the register to write control and configuration information about the FIFO, wherein control logic in a FIFO implementation processes written data and applies it as control data or configuration on FIFO operations, wherein the control and configuration information includes a maximum number of entries in the FIFO, a size of a FIFO entry, or commands to reset the FIFO.

6 . The system of claim 4 , wherein the system performs steps of allowing the FIFO status register to be read to perform credit-based flow control, wherein the register is read to determine how many objects are enqueued on the FIFO before it is full, and to determine how many elements are dequeued from the FIFO, wherein a program may use the information as credits and read the status register only when it needs to replenish credits.

7 . The system of claim 1 , wherein the FIFOs are employed as object allocators, wherein a memory object is referenced by a pointer address, wherein each FIFO holds objects that are pointer addresses, wherein a special null address indicates a null or no object, wherein the FIFO contains a maximum number of entries corresponding to a maximum number of allocatable objects, wherein at initialization, each pointer to an allocatable object is enqueued on the FIFO, wherein a program allocates an object by dequeuing from the FIFO, wherein if a non-null pointer is returned from the dequeue operation, it is the pointer of an allocated object, wherein if null is returned by the dequeue operation, the FIFO was empty and no object was allocated, and wherein a thread frees an object by enqueuing its pointer on the FIFO, wherein the enqueue operation will always succeed since the FIFO is never full unless all objects have been freed.

8 . The system of claim 1 , further comprising memory-mapped writable registers for polling FIFOs for writability, wherein the system performs steps of: utilizing a memory-mapped register assigned a memory address in an address space of the system, wherein different processors and execution elements perform memory load operations to poll a set of FIFOs for writability, wherein the register comprises a bitmap representing the FIFOs, wherein an index of a bit maps to one memory-mapped hardware FIFO, wherein the register indicates a set of writable, not full FIFOs, wherein a program polls the set of FIFOs by performing a load on the polling register, and wherein the system provides different sets of polling registers corresponding to arbitrary sets of memory-mapped FIFOs; and utilizing hardware logic and circuitry that logically map a status of the FIFO of whether a FIFO is writable or full to a bit in the memory address, wherein when the bit is set, there is at least one available entry to be enqueued on the FIFO.

9 . The system of claim 1 , further comprising memory-mapped readable registers for polling FIFOs for readability, wherein the system performs steps of: utilizing a memory-mapped register assigned a memory address in an address space of the system, wherein different processors and execution elements perform memory load operations to poll a set of FIFOs for readability, wherein the register comprises a bitmap representing the FIFOs, wherein an index of a bit maps to one memory-mapped hardware FIFO, wherein the register indicates a set of readable, not empty FIFOs, wherein a program polls the set of FIFOs by performing a load on a polling register, and wherein the system provides different sets of polling registers corresponding to arbitrary sets of memory-mapped FIFOs; and utilizing hardware logic and circuitry that logically map a status of the FIFO of whether a FIFO is readable or empty to a bit in the memory address, wherein when the bit is set, there is at least one element enqueued on the FIFO and the FIFO is readable.

10 . The system of claim 1 , further comprising a mailbox comprising a pair of a pollable FIFO and a writable FIFO, wherein the mailbox is implemented by a partition or thread of execution, wherein the partition executes a poll of the writable FIFO to identify when the FIFO is writable and then sends a message by writing to the FIFO, and wherein the partition executes a poll of the readable FIFO to identify when the FIFO is readable and then reads to dequeue and receive the message.

11 . The system of claim 1 , further comprising a scratchpad memory system comprising shared memory used for message passing between partitions, wherein at initialization of the system all scratchpad memory is placed in an allocator FIFO, wherein a thread that must send data to another thread allocates a scratchpad from the allocator FIFO, fills data content, and passes the message to another thread, wherein the data is passed as a pointer to a memory object.

12 . The system of claim 11 , wherein the mailbox holds points objects, wherein the pointer is enqueued and dequeued on the FIFO, wherein a partition sending a message to a mailbox allocates a scratchpad object from the allocator FIFO, writes data to the allocated scratchpad memory, and enqueues the scratchpad pointer on the mailbox FIFO, wherein a partition receiving a message from the mailbox polls the mailbox FIFO for readability, dequeues the scratchpad pointer from the mailbox, reads the data from the scratchpad memory, and either returns the scratchpad to the allocator FIFO or forwards the scratchpad to another partition.

13 . The system of claim 1 , further comprising a credit-based scheme to permit multiple producers of a FIFO, wherein each FIFO has a maximum number of enqueued entries, wherein each producer of the FIFO is given a number of credits for enqueuing on the FIFO, wherein a sum of all credits given to all producers is less than or equal to the maximum number of enqueued entries minus a number of entries currently enqueued, wherein each producer maintains a variable for the number of credits it has, wherein when a producer wishes to enqueue on the FIFO it does so only if a number of its available credits is greater than zero, wherein when the producer enqueues, it subtracts one from its available credits, wherein a consumer that dequeues and processes an object increments a variable representing the number of credits to be returned to the producer by one, wherein the consumer returns the credits to the producer via a message sent from the consumer to the producer, and wherein once the credits are returned, the consumer resets the return variable to zero.

14 . The system of claim 1 , further comprising monotonic state variables, wherein the system comprises monotonic variables in memory that are written by a producer and read by a consumer, wherein a monotonic property ensures that a producer overwrites a last written value without loss of information, wherein a consumer reads the variable at any time to obtain correct and up-to-date information, wherein pairs of monotonic variables mutually bound each other such that data written to one monotonic variable is bounded by another variable, and wherein when a limit is reached, a producer refrains from writing new data to the monotonic variable until the consumer writes data to the paired monotonic variable to increase the producer's bound.

15 . The system of claim 14 , wherein the system performs steps of allowing a monotonic variable to be arbitrarily reset to baseline start values while maintaining the monotonic property, wherein a state machine that includes state variables within the monotonic variable implements a protocol between a first party and a second party to gracefully reset a monotonic variable, wherein the protocol is driven by a finite state machine.

16 . The system of claim 15 , further comprising a protocol to synchronize a pair of monotonic state variables, the system comprising: epochs of monotonic variables, wherein when an epoch starts, the monotonic variables are reset to an earlier state, wherein two bits in each monotonic state variable are used for signaling, one bit representing a generation number (0 or 1) and another bit indicating the state of the variable as closed (1) or opened (0), wherein the two bits together constitute an MSV state, wherein the MSV state bits are fields in the pair of monotonic variables, wherein the bits are set by a producer such that the monotonic property is maintained and are bounded by the paired monotonic variable, wherein the protocol for setting the MSV state is driven by a finite state machine, wherein two parties communicate as MSV master and MSV slave, wherein only the master initiates a new epoch, wherein a new epoch starts in a closed state, and the generation bits of both variables are equal, wherein in the closed state a remainder of each monotonic variable is set to a default baseline value, wherein the master initiates a new epoch by opening its variable and flipping the generation bit, wherein the slave observes the master's open state and matches its generation bit, wherein both sides then open for normal operations, and wherein epochs are closed when both sides set their closed bits to one, allowing a process to repeat.

17 . The system of claim 16 , wherein the monotonic state variables are implemented as memory-mapped hardware registers, wherein logic of the monotonic state variables is abstracted from a user, wherein when a monotonic state variable is written by a producer, a consumer receives an asynchronous notification, wherein the monotonic state variable is polled for readability, and wherein when the consumer reads the monotonic state variable, it is cleared as not readable with respect to polling.

18 . The system of claim 16 , wherein the system performs steps of using monotonic state variables to implement connection-based semantics, wherein a master opens a monotonic state variable providing connection information, wherein once both monotonic state variables are open, a connection is established, and wherein the connection is closed by closing the monotonic state variables.

19 . The system of claim 18 , wherein the system performs steps of using monotonic state variables to express dependencies for parallelism, wherein non-state information in the monotonic variables contains a bitmap of dependencies that are set by a producer of the monotonic state variable, wherein once a dependency bit is set it remains set until the monotonic state variables are reset, wherein dependency bitmaps adhere to the monotonic property, wherein at a start of packet processing, dependencies are cleared and the monotonic state variables are opened, wherein dependency bits are set as dependencies are resolved, and when a dependency bit is set, a consumer is notified and performs appropriate processing, wherein when packet processing is complete, the monotonic state variables are closed and dependencies are cleared, and wherein the monotonic state variables are reused for processing another packet.