FPGA实现流水式排序算法

该算法采用双调排序算法，是一种可流水的递推算法，且算法的消耗时长可算，具体细节参考视频：

https://www.bilibili.com/video/BV1S3thzWEnh/?spm_id_from=333.1387.homepage.video_card.click&vd_source=69fb997b62efa60ae1add8b53b6a5923

module bitonic_sort(input						i_clk	,input						i_rst	,input		[16 * 16 - 1:0]	i_buff	,output		[16 * 16 - 1:0]	o_buff);localparam WIN = 16;wire	signed	[15:0]	w_data_buff	[0:15];genvar i;genvar j;generatefor(i = 0; i < 16; i = i + 1) beginassign w_data_buff[i] = i_buff[i * 16 + 15:i * 16];endendgenerate/*双调排序：Bitonic 首先将相邻两个元素作为一个数组:(0,1)(2,3)(4,5)(6,7)(8,9)(10,11)(12,13)(14,15)将其按照顺序、逆序交替排序，并两个相邻数组组成一个四元素的双调数组(0,1,2,3)(4,5,6,7)(8,9,10,11)(12,13,14,15)通过对每个四元素数组进行2、1间隔排序，使四元素数组按照顺序、逆序交替排序，并两个相邻数组组成一个8元素数组(0,1,2,3,4,5,6,7)(8,9,10,11,12,13,14,15)对每个8元素数组进行4、2、1间隔排序，使其按照顺序、逆序交替排序，最终组成16元素的回调数组(0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15)对回调数组按照8、4、2、1间隔排序，完成顺序或逆序排列*/reg	signed	[15:0]	r_bitonic_pipe0	[0:WIN - 1];//间隔1generatefor(i = 0; i < WIN / 4; i = i + 1) beginalways@(posedge i_clk or posedge i_rst) beginif(i_rst) beginr_bitonic_pipe0[i * 4] 	<= 'd0;r_bitonic_pipe0[i * 4 + 1]<= 'd0;endelse beginif(w_data_buff[i * 4] > w_data_buff[i * 4 + 1]) begin//升序r_bitonic_pipe0[i * 4] 		<= w_data_buff[i * 4 + 1];r_bitonic_pipe0[i * 4 + 1]	<= w_data_buff[i * 4];endelse beginr_bitonic_pipe0[i * 4] 		<= w_data_buff[i * 4];r_bitonic_pipe0[i * 4 + 1]	<= w_data_buff[i * 4 + 1];endendendalways@(posedge i_clk or posedge i_rst) beginif(i_rst) beginr_bitonic_pipe0[i * 4 + 2]<= 'd0;r_bitonic_pipe0[i * 4 + 3]<= 'd0;endelse beginif(w_data_buff[i * 4 + 2] < w_data_buff[i * 4 + 3]) begin//降序r_bitonic_pipe0[i * 4 + 2]<= w_data_buff[i * 4 + 3];r_bitonic_pipe0[i * 4 + 3]<= w_data_buff[i * 4 + 2];endelse beginr_bitonic_pipe0[i * 4 + 2]<= w_data_buff[i * 4 + 2];r_bitonic_pipe0[i * 4 + 3]<= w_data_buff[i * 4 + 3];endendendendendgeneratereg	signed	[15:0]	r_bitonic_pipe1	[0:WIN - 1];//间隔2generatefor(i = 0; i < WIN / 8; i = i + 1) beginfor(j = 0; j < WIN / 8; j = j + 1) beginalways@(posedge i_clk or posedge i_rst) beginif(i_rst) beginr_bitonic_pipe1[i * 8 + j] 	<= 'd0;r_bitonic_pipe1[i * 8 + j + 2]<= 'd0;endelse beginif(r_bitonic_pipe0[i * 8 + j] > r_bitonic_pipe0[i * 8 + j + 2]) begin//升序r_bitonic_pipe1[i * 8 + j]		<= r_bitonic_pipe0[i * 8 + j  + 2];r_bitonic_pipe1[i * 8 + j + 2]	<= r_bitonic_pipe0[i * 8 + j];endelse beginr_bitonic_pipe1[i * 8 + j]		<= r_bitonic_pipe0[i * 8 + j];r_bitonic_pipe1[i * 8 + j + 2]	<= r_bitonic_pipe0[i * 8 + j + 2];				endendendalways@(posedge i_clk or posedge i_rst) beginif(i_rst) beginr_bitonic_pipe1[i * 8 + j + 4]<= 'd0;r_bitonic_pipe1[i * 8 + j + 6]<= 'd0;endelse beginif(r_bitonic_pipe0[i * 8 + j + 4] < r_bitonic_pipe0[i * 8 + j + 6]) begin//降序r_bitonic_pipe1[i * 8 + j + 4]<= r_bitonic_pipe0[i * 8 + j + 6];r_bitonic_pipe1[i * 8 + j + 6]<= r_bitonic_pipe0[i * 8 + j + 4];endelse beginr_bitonic_pipe1[i * 8 + j + 4]<= r_bitonic_pipe0[i * 8 + j + 4];r_bitonic_pipe1[i * 8 + j + 6]<= r_bitonic_pipe0[i * 8 + j + 6];				endendendendendendgeneratereg	signed	[15:0]	r_bitonic_pipe2	[0:WIN - 1];generatefor(i = 0; i < WIN / 8; i = i + 1) beginfor(j = 0; j < WIN / 8; j = j + 1) beginalways@(posedge i_clk or posedge i_rst) beginif(i_rst) beginr_bitonic_pipe2[i * 8 + j * 2] 		<= 'd0;r_bitonic_pipe2[i * 8 + j * 2 + 1] 	<= 'd0;endelse beginif(r_bitonic_pipe1[i * 8 + j * 2] > r_bitonic_pipe1[i * 8 + j * 2 + 1]) begin//升序r_bitonic_pipe2[i * 8 + j * 2]		<= r_bitonic_pipe1[i * 8 + j * 2+ 1];r_bitonic_pipe2[i * 8 + j * 2 + 1]	<= r_bitonic_pipe1[i * 8 + j * 2];endelse beginr_bitonic_pipe2[i * 8 + j * 2]		<= r_bitonic_pipe1[i * 8 + j * 2];r_bitonic_pipe2[i * 8 + j * 2 + 1]	<= r_bitonic_pipe1[i * 8 + j * 2 + 1];endendendalways@(posedge i_clk or posedge i_rst) beginif(i_rst) beginr_bitonic_pipe2[i * 8 + j * 2 + 4]	<= 'd0;r_bitonic_pipe2[i * 8 + j * 2 + 5]	<= 'd0;endelse beginif(r_bitonic_pipe1[i * 8 + j * 2 + 4] < r_bitonic_pipe1[i * 8 + j * 2 + 5]) begin//降序r_bitonic_pipe2[i * 8 + j * 2 + 4]	<= r_bitonic_pipe1[i * 8 + j * 2 + 5];r_bitonic_pipe2[i * 8 + j * 2 + 5] 	<= r_bitonic_pipe1[i * 8 + j * 2 + 4];endelse beginr_bitonic_pipe2[i * 8 + j * 2 + 4]	<= r_bitonic_pipe1[i * 8 + j * 2 + 4];r_bitonic_pipe2[i * 8 + j * 2 + 5]	<= r_bitonic_pipe1[i * 8 + j * 2 + 5];endendendendendendgeneratereg	signed	[15:0]	r_bitonic_pipe3	[0:WIN - 1];//间隔4generatefor(i = 0; i < WIN / 4; i = i + 1) beginalways@(posedge i_clk or posedge i_rst) beginif(i_rst) beginr_bitonic_pipe3[i]	<= 'd0;r_bitonic_pipe3[i + 4]<= 'd0;endelse beginif(r_bitonic_pipe2[i] > r_bitonic_pipe2[i + 4]) begin//升序r_bitonic_pipe3[i]		<= r_bitonic_pipe2[i + 4];r_bitonic_pipe3[i + 4]	<= r_bitonic_pipe2[i];endelse beginr_bitonic_pipe3[i]		<= r_bitonic_pipe2[i];r_bitonic_pipe3[i + 4]	<= r_bitonic_pipe2[i + 4];endend	endalways@(posedge i_clk or posedge i_rst) beginif(i_rst) beginr_bitonic_pipe3[i + 8] <= 'd0;r_bitonic_pipe3[i + 12]<= 'd0;endelse beginif(r_bitonic_pipe2[i + 8] < r_bitonic_pipe2[i + 12]) begin//降序r_bitonic_pipe3[i + 8] <= r_bitonic_pipe2[i + 12];r_bitonic_pipe3[i + 12]<= r_bitonic_pipe2[i + 8];endelse beginr_bitonic_pipe3[i + 8] <= r_bitonic_pipe2[i + 8];r_bitonic_pipe3[i + 12]<= r_bitonic_pipe2[i + 12];endendendendendgeneratereg	signed	[15:0]	r_bitonic_pipe4	[0:WIN - 1];//间隔2generatefor(i = 0; i < WIN / 8; i = i + 1) beginfor(j = 0; j < WIN / 8; j = j + 1) beginalways@(posedge i_clk or posedge i_rst) beginif(i_rst) beginr_bitonic_pipe4[i * 4 + j] 		<= 'd0;r_bitonic_pipe4[i * 4 + j + 2]	<= 'd0;endelse beginif(r_bitonic_pipe3[i * 4 + j] > r_bitonic_pipe3[i * 4 + j + 2]) beginr_bitonic_pipe4[i * 4 + j] 		<= r_bitonic_pipe3[i * 4 + j + 2];r_bitonic_pipe4[i * 4 + j + 2]	<= r_bitonic_pipe3[i * 4 + j];endelse beginr_bitonic_pipe4[i * 4 + j] 		<= r_bitonic_pipe3[i * 4 + j];r_bitonic_pipe4[i * 4 + j + 2]	<= r_bitonic_pipe3[i * 4 + j + 2];endendendalways@(posedge i_clk or posedge i_rst) beginif(i_rst) beginr_bitonic_pipe4[i * 4 + j + 8]	<= 'd0;r_bitonic_pipe4[i * 4 + j + 10]	<= 'd0;endelse beginif(r_bitonic_pipe3[i * 4 + j + 8] < r_bitonic_pipe3[i * 4 + j + 10]) beginr_bitonic_pipe4[i * 4 + j + 8]	<= r_bitonic_pipe3[i * 4 + j + 10];r_bitonic_pipe4[i * 4 + j + 10]	<= r_bitonic_pipe3[i * 4 + j + 8];endelse beginr_bitonic_pipe4[i * 4 + j + 8] 	<= r_bitonic_pipe3[i * 4 + j + 8];r_bitonic_pipe4[i * 4 + j + 10]	<= r_bitonic_pipe3[i * 4 + j + 10];endendendend		endendgeneratereg	signed	[15:0]	r_bitonic_pipe5	[0:WIN - 1];//间隔1generatefor(i = 0; i < WIN / 4; i = i + 1) beginalways@(posedge i_clk or posedge i_rst) beginif(i_rst) beginr_bitonic_pipe5[i * 2]		<= 'd0;r_bitonic_pipe5[i * 2 + 1]	<= 'd0;endelse beginif(r_bitonic_pipe4[i * 2] > r_bitonic_pipe4[i * 2 + 1]) beginr_bitonic_pipe5[i * 2]		<= r_bitonic_pipe4[i * 2 + 1];r_bitonic_pipe5[i * 2 + 1]	<= r_bitonic_pipe4[i * 2];endelse beginr_bitonic_pipe5[i * 2]		<= r_bitonic_pipe4[i * 2];r_bitonic_pipe5[i * 2 + 1]	<= r_bitonic_pipe4[i * 2 + 1];endendendalways@(posedge i_clk or posedge i_rst) beginif(i_rst) beginr_bitonic_pipe5[i * 2 + 8]	<= 'd0;r_bitonic_pipe5[i * 2 + 9]	<= 'd0;endelse beginif(r_bitonic_pipe4[i * 2 + 8] < r_bitonic_pipe4[i * 2 + 9]) beginr_bitonic_pipe5[i * 2 + 8]	<= r_bitonic_pipe4[i * 2 + 9];r_bitonic_pipe5[i * 2 + 9]	<= r_bitonic_pipe4[i * 2 + 8];endelse beginr_bitonic_pipe5[i * 2 + 8]	<= r_bitonic_pipe4[i * 2 + 8];r_bitonic_pipe5[i * 2 + 9]	<= r_bitonic_pipe4[i * 2 + 9];endendendendendgeneratereg	signed	[15:0]	r_bitonic_pipe6	[0:WIN - 1];//间隔8generatefor(i = 0; i < WIN / 2; i = i + 1) beginalways@(posedge i_clk or posedge i_rst) beginif(i_rst) beginr_bitonic_pipe6[i]		<= 'd0;r_bitonic_pipe6[i + 8]	<= 'd0;endelse beginif(r_bitonic_pipe5[i] > r_bitonic_pipe5[i + 8]) beginr_bitonic_pipe6[i]		<= r_bitonic_pipe5[i + 8];r_bitonic_pipe6[i + 8]	<= r_bitonic_pipe5[i];endelse beginr_bitonic_pipe6[i]		<= r_bitonic_pipe5[i];r_bitonic_pipe6[i + 8]	<= r_bitonic_pipe5[i + 8];endendendendendgeneratereg	signed	[15:0]	r_bitonic_pipe7	[0:WIN - 1];//间隔4generatefor(i = 0; i < WIN / 8; i = i + 1) beginfor(j = 0; j < WIN / 4; j = j + 1) beginalways@(posedge i_clk or posedge i_rst) beginif(i_rst) beginr_bitonic_pipe7[i * 8 + j]		<= 'd0;r_bitonic_pipe7[i * 8 + j + 4]	<= 'd0;endelse beginif(r_bitonic_pipe6[i * 8 + j] > r_bitonic_pipe6[i * 8 + j + 4]) beginr_bitonic_pipe7[i * 8 + j]		<= r_bitonic_pipe6[i * 8 + j + 4];r_bitonic_pipe7[i * 8 + j + 4]	<= r_bitonic_pipe6[i * 8 + j];endelse beginr_bitonic_pipe7[i * 8 + j]		<= r_bitonic_pipe6[i * 8 + j]	;r_bitonic_pipe7[i * 8 + j + 4]	<= r_bitonic_pipe6[i * 8 + j + 4];endendendendendendgeneratereg	signed	[15:0]	r_bitonic_pipe8	[0:WIN - 1];//间隔2generatefor(i = 0; i < WIN / 4; i = i + 1) beginfor(j = 0; j < WIN / 8; j = j + 1) beginalways@(posedge i_clk or posedge i_rst) beginif(i_rst) beginr_bitonic_pipe8[i * 4 + j]		<= 'd0;r_bitonic_pipe8[i * 4 + j + 2]	<= 'd0;endelse beginif(r_bitonic_pipe7[i * 4 + j] > r_bitonic_pipe7[i * 4 + j + 2]) beginr_bitonic_pipe8[i * 4 + j]		<= r_bitonic_pipe7[i * 4 + j + 2];r_bitonic_pipe8[i * 4 + j + 2]	<= r_bitonic_pipe7[i * 4 + j];endelse beginr_bitonic_pipe8[i * 4 + j]		<= r_bitonic_pipe7[i * 4 + j]	;r_bitonic_pipe8[i * 4 + j + 2]	<= r_bitonic_pipe7[i * 4 + j + 2];endendendendendendgeneratereg	signed	[15:0]	r_bitonic_pipe9	[0:WIN - 1];//间隔1generatefor(i = 0; i < WIN / 2; i = i + 1) beginalways@(posedge i_clk or posedge i_rst) beginif(i_rst) beginr_bitonic_pipe9[i * 2]		<= 'd0;r_bitonic_pipe9[i * 2 + 1]	<= 'd0;endelse beginif(r_bitonic_pipe8[i * 2] > r_bitonic_pipe8[i * 2 + 1]) beginr_bitonic_pipe9[i * 2]		<= r_bitonic_pipe8[i * 2 + 1];r_bitonic_pipe9[i * 2 + 1]	<= r_bitonic_pipe8[i * 2];endelse beginr_bitonic_pipe9[i * 2]		<= r_bitonic_pipe8[i * 2]	;r_bitonic_pipe9[i * 2 + 1]	<= r_bitonic_pipe8[i * 2 + 1];endendendendendgenerate	generatefor(i = 0; i < 16; i = i + 1) beginassign	o_buff[i * 16 + 15:i * 16] = r_bitonic_pipe9[i];endendgenerateendmodule