Verdvana

空持千百偈 不如吃茶去

硬件算法之流水线结构

18 Jul 2019 » Verilog HDL, FPGA, Hardware Algorithm

1 流水线结构原理

        硬件的流水线结构(pipelining)和我们身边生产工厂里的流水线作业类似,是一种通过连续进行大量运算来实现高速化处理的手段。

        在下图的非流水线结构中,运算1和运算2在硬件电路上依次执行。

1

        而在下图的流水线结构中,硬件电路被拆分成n个均等的阶段(stage)后,下一个运算无需等前一个运算完全结束即可开始。流水线的阶段也称为流水线的“级”。图中,n=5个阶段也可称为5级流水线结构。相对于非流水线结构中完成全部运算所需要的时间L,流水线结构在运算1完成之后,按阶段划分的每L/n个单位时间就可以完成一个运算。也就是说单位时间内,用来表示运算量的吞吐量(throughput)指标最大可以提升n倍。上图非流水线结构完成两个运算的时间内,下图流水线结构可以完成6个运算。

2

        运算5开始的时候,从运算1到运算5总共5级流水线在同时工作,不同阶段可以连续、并行的执行,这就是流水线结构高速化处理的基本原理。


2 使用流水线提升性能

        其实在流水线的实际应用中,n级流水线并不一定能得到n倍的速度提升。下面假设单位运算时间为L,总运算量为N,流水线分为n个阶段,然后通过建模对流水线的速度提升率进行分析说明。

        之前所说的的非流水线结构完成N个运算所需要的时间T(N)=LN。而对于流水线结构,完成N个运算所需的时间Tpipe(N)按照以下方法求解。

        首先,完成运算1所需时间为L。而下一个运算会在运算1完成后的L/n时间后完成。因此除了运算1,之后的N-1个运算每隔L/n个单位时间依次完成,总运算时间如下:

Tpipe(N)=L+(N-1)L/n=(n+N-1)L/n

        使用流水线结构的速度提升率Spipe(N)为T(N)除以Tpipe(N),可按照下面式子展开:

Spipe(N)=T(N) / Tpipe(N) = nN/(n+N-1) = n / (1 + (n-1)/N)

        当n«N时,Spipe(N)≈n,因此流水线结构和非流水线结构相比所得到的速度提升和阶段数量成正比,大约为n倍。这里的速度提升指的是吞吐量指标,完成单个运算所需要的延迟时间不会缩短。 也就是说,所谓性能提升n倍是指完成全部N个运算的时间缩短了,而每个运算从开始到结束的时间没有变化。

        当总运算量N没有远远大于流水线级数N时,性能提升的空间就比较有限了。例如,n=6级流水线上处理的运算量N=5时,Spipe(5)=6/(1+1)=3,运算时间只缩减到原来的三分之一。一个n级流水线所能达到的最大速度提升率为n,我们可以用下面的效率公式来衡量实际的速度提升率达到了最大提升率的百分之多少:

Epipe(n,N) = Spipe(N) / n = 1 / 1+(n-1)/N = N/(N+n-1)

        按刚才的例子计算得到Epipe(6,5)=5/(5+6-1)=0.5,因此所得速度提升为最大提升率的50%,这主要硬件是以低并行度处理的时间较长导致的。在运算5开始之前,硬件一直没有达到最大的并行度n=5。因此,流水线开始时有一个各阶段逐一启动的载入过程(prologue),而在流水线结束时有一个各阶段逐一停止的清空过程(epilogue)。载入过程和清空过程虽然无法省略,但当运算总数N足够大时其所占的时间比例足够小,就可以得到和n非常接近的速度提升率。反之,当运算总数较小时载入过程和清空过程的影响相对较大,速度提升率就较低。

        此外还有其他几个在实际硬件中影响流水线性能的因素存在,因此需要在设计时格外注意。下图为一个流水线的硬件结构实例。

        下图为非流水线结构硬件,整个运算采用的单一的组合逻辑电路实现。前级寄存器的值在时钟的上升沿更新,经过寄存器内部传输延迟后,输出到组合逻辑电路的输入。输入的数据接着在组合逻辑电路内部传播,经过关键路径(critical path)所需的延迟时间后运算结果到达后级寄存器。运算的结果数据在保持一定时间(触发器所需的建立时间)稳定之后,在下一个时钟到来时被写入寄存器,这样该电路的处理过程就完成了。从上面的过程我们可以得出时钟信号的输入时间间隔,也就是时钟周期(cycle time)必须大于(传输延迟) (组合逻辑电路的关键电路延迟)+(建立时间),这个极限值也就是电路时钟频率的最大值。

3

        将电路流水线化,可以提高时钟频率、增大吞吐量。下图是一个n=4级流水线的电路结构示意图。通过将电路拆分为多个阶段并在阶段之间插入流水线寄存器,单个时钟周期内数据需要传输的距离就被缩短到各个阶段内较小的组合逻辑电路中。然而,就算是完全军等地将原本的关键路径切分成n个阶段,时钟周期也不能缩短为原来的1/n。这是由于电路中还加入了流水线寄存器的延迟、建立时间,此外还要考虑各个寄存器的输入时钟信号间的偏移等因素。而且一般来说,将电路均等地拆分成n个阶段也是比较困难的。像下图所示,通常存在某个阶段的关键路径要比其它阶段的关键路径长,此时就算n=4,阶段的最大延迟也比1/4要长,因此时钟频率无法提升4倍。

4

        这些因素的影响在阶段数增多的时候更为显著。因此,通常对某个组合逻辑电路进行轻度的流水线化时容易得到和阶段数相当的时钟频率提升,而将其拆分为数十、数百个阶段时主频提升的效果就会逐步减弱,甚至因为时钟偏移等因素反而降低性能。不单是拆分流水线,为电路添加流水线阶段时也要注意类似问题。另外,还要注意插入流水线寄存器所增加的延迟或关键路径切分不均等,都可能导致流水线化后电路的整体延迟比原电路恶化的情况。


3 Verilog HDL举例

        用8位全加器作为实例,分别列举了非流水线方法、2级流水线方法和4级流水线方法。

3.1 非流水线方法

module Adder_8bits(
	input					clk,
	input					rst_n,
	
	input  [7:0]		din_1,
	input  [7:0]		din_2,
	input					cin,
	output reg [7:0]	dout,
	output reg			cout
);


	 
always@(posedge clk or negedge rst_n) begin
	if(!rst_n) begin
		cout <= 1'b0;
		dout <= 8'b0;
	end
	
	else
		{cout,dout} <= din_1 + din_2 + cin;
end
	 
	 
endmodule

3.2 2级流水线方法

module Adder_8bits_2step(
	input					clk,
	input					rst_n,
	
	input  [7:0]		din_1,
	input  [7:0]		din_2,
	input					cin,
	output reg [7:0]	dout,
	output reg			cout
);


reg cout_temp;
reg [3:0] dout_temp;

always @(posedge clk or negedge rst_n) begin
	if(!rst_n) begin
		cout_temp <= 1'b0;
		dout_temp <= 4'b0;
	end
	
	else
		{cout_temp,dout_temp} = din_1[3:0] + din_2[3:0] + cin;
end

always@(posedge clk or negedge rst_n) begin
	if(!rst_n) begin
		cout <= 1'b0;
		dout <= 8'b0;
	end
	
	else
		{cout,dout} = { {1'b0,din_1[7:4]} + {1'b0,din_2[7:4]} + cout_temp, dout_temp};
end
	 
endmodule

        注意:这里在always块内只能用阻塞赋值方式,否则会出现逻辑上的错误!

3.3 4级流水线方法

module Adder_8bits_4step(
	input					clk,
	input					rst_n,
	
	input  [7:0]		din_1,
	input  [7:0]		din_2,
	input					cin,
	output reg [7:0]	dout,
	output reg			cout
);


reg cout_t1, cout_t2, cout_t3;

reg [1:0] dout_t1;
reg [3:0] dout_t2;
reg [5:0] dout_t3;

always @(posedge clk or negedge rst_n) begin
	if(!rst_n) begin
		cout_t1 <= 1'b0;
		dout_t1 <= 2'b0;
	end
	
	else
		{cout_t1, dout_t1} = {1'b0, din_1[1:0]} + {1'b0, din_2[1:0]} + cin;
end

always @(posedge clk or negedge rst_n) begin
	if(!rst_n) begin
		cout_t2 <= 1'b0;
		dout_t2 <= 4'b0;
	end
	
	else
		{cout_t2, dout_t2} = { {1'b0, din_1[3:2]} + {1'b0, din_2[3:2]} + cout_t1, dout_t1};
end

always @(posedge clk or negedge rst_n) begin
	if(!rst_n) begin
		cout_t3 <= 1'b0;
		dout_t3 <= 6'b0;
	end
	
	else
		{cout_t3, dout_t3} = { {1'b0, din_1[5:4]} + {1'b0, din_2[5:4]} + cout_t2, dout_t2};
end

always @(posedge clk or negedge rst_n) begin
	if(!rst_n) begin
		cout <= 1'b0;
		dout <= 8'b0;
	end
	
	else
		{cout, dout} = { {1'b0, din_1[7:6]} + {1'b0, din_2[7:6]} + cout_t3, dout_t3};
end


endmodule

3.4 分析综合

        建立顶层文件将这三个文件例化,分析综合,综合之后的RTL图如图所示:

5

3.5 仿真

        使用Modelsim进行仿真:

6

        因为非流水线结构也是一个时钟周期就完成计算,所以三种速度是一样的,尴尬😅。


4 总结

        利用流水线的设计方法,可大大提高系统的工作速度。这种方法可广泛运用于各种设计,特别是大型的、对速度要求较高的系统设计。虽然采用流水线会增大资源的使用,但是它可降低寄存器间的传播延时,保证系统维持高的系统时钟速度。在实际应用中,考虑到资源的使用和速度的要求,可以根据实际情况来选择流水线的级数以满足设计需要。

        这是一种典型的以面积换速度的设计方法。这里的“面积”主要是指设计所占用的FPGA逻辑资源数目,即利用所消耗的触发器(FF)和查找表(LUT)来衡量。“速度”是指在芯片上稳定运行时所能达到的最高频率。面积和速度这两个指标始终贯穿着FPGA的设计,是设计质量评价的最终标准。


        告辞。