Queue and its implementation

Queue and its implementation

queue

Queue is FIFO, in a word, it is first in first out. For example, the order of entering the queue is 1, 2, 3, 4, then the order of leaving the queue is also 1, 2, 3, 4

Implementation of the queue

Software-GO language implementation

In addition to using linked lists and arrays to implement linked lists, GO language has a new built-in data structure called slicing, which can implement listsome functions similar to dynamic languages (slicing and append). It is very easy to use this data structure to implement queues.

Structure

type fifo struct {
    data []int
    length int
}

Dequeue method

f.data[1:]It is similar to the slicing operation in python, which means that the first value is cut off and the rest is retained

func (f *fifo) Pop() (int, error) {
    if len(f.data) == 0 {
        return 0, errors.New("empty fifo")
    } else {
        temp := f.data[0]
        f.data = f.data[1:]
        f.length--
        return temp, nil
    }
}

Enqueue method

The append method is the slice processing method that comes with the go language. The first parameter is the slice to be manipulated, the subsequent parameters are the variables to be inserted after the slice, and the return value is the new slice after the insertion is completed.

func (f *fifo) Push(din int) {
    f.data = append(f.data, din)
    f.length++
}

Constructor

func New_fifo() *fifo {
    return &fifo{[]int{}, 0}
}

Hardware-Verilog implementation

Fifo is often used to implement buffers because it does not change the data sequence. It is commonly used to implement fifo using dual-port ram + control logic.

Port definition

module fifo_control #(
    parameter WIDTH = 8,
    parameter DEPTH_LOG = 8
)(
    input clk,//Clock
    input rst_n,//Asynchronous reset active low

    input fifo_write_req,
    input [WIDTH-1:0]fifo_write_data,
    output reg fifo_full,

    input fifo_read_req,
    output reg fifo_empty,

    output reg ram_write_req,
    output reg [DEPTH_LOG-1:0]ram_write_addr,
    output reg [WIDTH-1:0]ram_write_data,

    output reg [DEPTH_LOG-1:0]ram_read_addr
);

Wire net definition

reg [DEPTH_LOG-1:0]write_point,read_point;
wire almost_full = (write_point == read_point-1'b1)? 1'b1:1'b0;
wire almost_empty = (write_point == read_point + 1'b1)? 1'b1:1'b0;

Write pointer control

always @(posedge clk or negedge rst_n) begin
    if(~rst_n) begin
        write_point <='b0;
        ram_write_req <='b0;
    end else if((!fifo_full || fifo_read_req) && fifo_write_req) begin
        write_point <= write_point + 1'b1;
        ram_write_req <= 1'b1;
    end else begin
        ram_write_req <='b0;
    end
end

(!fifo_full || fifo_read_req) && fifo_write_reqTo write execution conditions:

  • fifo is dissatisfied and write request
  • Read and write requests at the same time (overflow is not possible)

fifo full signal generation

always @ (posedge clk or negedge rst_n) begin
    if(~rst_n) begin
        fifo_full <='b0;
    end else if(fifo_read_req && fifo_write_req) begin
        fifo_full <= fifo_full;
    end else if(fifo_read_req) begin
        fifo_full <='b0;
    end else if(almost_full && fifo_write_req) begin
        fifo_full <='b1;
    end
end
  • fifo_read_req && fifo_write_reqWhen reading and writing at the same time, the full signal state will not change
  • almost_full && fifo_write_reqWhen the write request is valid and there is only one space left, the full signal is set
  • fifo_read_reqAs long as you have read it once, it can't be full

Write address and data generation

always @ (posedge clk or negedge rst_n) begin
    if(~rst_n) begin
        ram_write_data <='b0;
        ram_write_addr <='b0;
    end else begin
        ram_write_data <= fifo_write_data;
        ram_write_addr <= write_point;
    end
end

Read pointer/address control

always @ (posedge clk or negedge rst_n) begin
    if(~rst_n) begin
        read_point <='b0;
        ram_read_addr <='b0;
    end else if(!fifo_empty && fifo_read_req) begin
        read_point <= read_point + 1'b1;
        ram_read_addr <= read_point;
    end
end
  • !fifo_empty && fifo_read_reqWhen fifo is not empty, read fifo

fifo null signal generation

always @ (posedge clk or negedge rst_n) begin
    if(~rst_n) begin
        fifo_empty <= 1'b1;
    end else if(fifo_read_req && fifo_write_req) begin
        fifo_empty <= fifo_empty;
    end else if(fifo_write_req) begin
        fifo_empty <= 1'b0;
    end else if(almost_empty && fifo_read_req) begin
        fifo_empty <= 1'b1;
    end
end
Reference: https://cloud.tencent.com/developer/article/1110712 Queue and its implementation The realization of the queue queue-Cloud + Community-Tencent Cloud