Generic Queue



Overview

All the queues used in our design are variations of a single generic queue. This allows for reusability of code, which reduces design time and decreases code size. Following is a diagram showing the inputs and outputs to this generic queue.



This generic queue is a queue with all the basic queue functionality (enQueue, deQueue, size return, etc.), but has generic constants so that is can be used in a variety of applications. These constants are defined by the programmer and include the queue size, the widths of the input and output data bus, the number of bits one can add or remove, and when the "queue almost full" alarm goes on and off.

Inside the Queue

The functionality of the queue is very basic, and is summarized in the following diagram.



Every queue has a tail and a head. In our case, the head is always the first bit of the queue and the tail is represented by a vector which indicates the bit position of end of the queue. The tail is basically the bit size of the stored information in the queue.

When the enQueue signal is asserted, the data bus is added to the end of the queue and the tail is incremented by the number of bits added. If there is not enough room in the queue to place the required number of bits, nothing is added to the queue and the data is dropped. When the deQueue signal is asserted, the specified number of bits are placed from the front of the queue onto the data bus. This means that when the deQueue signal is asserted, the data will be available on the next clock cycle. After the data is on the data bus, all the data in the queue is shifted right by the number of bits to remove. The space generated at the end of the queue by the shift is filled in with zeroes. It is also possible to enqueue and dequeue at the same time. In such a case, first the data to be removed is placed on the output bus. Then, all the data is shifted (zeroes at end), and then the new data is added to the queue. Since the input and output busses are usually the same width, the tail usually remains the same when this occurs.

The generation of the alarm is a very important part of the queue, since it lets the transmitting device know when the queue is almost full. This is used to stop transmission and therefore reduce (to nothing) the loss of data due to a full queue. There are separate numbers for when the alarm should turn on, and when it should turn off. This is because a programmer usually wants a sort of buffer zone before the transmitting device should start again. Not doing so could result in the alarm alternating between on and off almost every clock cycle. This makes the transmitter very inefficient. When the specified minimum number of bytes is available (alarmOnWhen), the alarm is turned on. This halts transmission. Data is then removed as needed until a specified number of bytes becomes available in the queue (alarmOffWhen). The alarm is then turned off and transmission resumes.

For a more detailed look at how the queue works, refer to the state machine diagram below.