队列

队列即FIFO，一言以蔽之就是先进先出。比如入队列的顺序是1,2,3,4，那么出队列的顺序也是1,2,3,4

队列的实现

软件——GO语言实现

除了使用链表和数组实现链表以外，GO语言内置一种新的数据结构叫切片，可以实现类似于动态语言中的list的一些功能（切片和append），用这个数据结构实现队列非常容易

结构体

1
2
3
4
type fifo struct {
	data   []int
	length int
}

出队列方法

f.data[1:]就是类似于python中的切片操作，表示切掉第一个值，剩下的保留

1
2
3
4
5
6
7
8
9
10
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
	}
}

入队列方法

append方法是go语言自带的切片处理方法，第一个参数是要操作的切片，随后的参数都是要插入到切片之后的变量，返回值是完成插入后新的切片

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

构造函数

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

硬件——Verilog实现

fifo由于其不改变数据顺序常用于实现buffer，常用双口ram+控制逻辑的方法实现fifo

端口定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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
);

线网定义

1
2
3
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;

写指针控制

1
2
3
4
5
6
7
8
9
10
11
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_req为写执行条件：

  • fifo不满且写请求
  • 读写同时又请求（不可能溢出）

fifo满信号生成

1
2
3
4
5
6
7
8
9
10
11
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_req当读写同时进行时，满信号状态不会改变
  • almost_full && fifo_write_req当写请求有效且只剩一个空位时，满信号置位
  • fifo_read_req只要读过一次，不可能满

写地址与数据生成

1
2
3
4
5
6
7
8
9
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

读指针/地址控制

1
2
3
4
5
6
7
8
9
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_req当fifo非空时，读fifo

fifo空信号生成

1
2
3
4
5
6
7
8
9
10
11
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