引言

推排序常常应用在操作系统的任务调度中，尝试使用硬件对堆排序进行实现，在实现的过程中不使用function和tasks语法，即真·硬件实现

参考的博客

也就这一个博客有介绍
堆排序的Verilog实现

原理

堆排序还需要复习一遍吗? 我肯定是要的
菜鸟-堆排序
图解排序算法(三)之堆排序

可以看到，推排序很复杂，所以我们需要祭出我们的FSM(有限状态机)

首先，将整个堆排序分为两个阶段：

1. 构建大根堆或小根堆
2. 从最后一个节点开始，和根节点交换，并维护大根堆

我们这里统一构建大根堆

大根堆的构建

直接上流程：

1. 从第一个非叶子节点开始，读取左右孩子的值；

2. 比较大小，确定是否需要交换，以及交换的数据；

3. 写入或不写入，如果这个节点是根节点，那么构建结束。

4. 如果写入了，需要对子树进行判断，也就是保证子树也是大根堆

还是很简单的，就是需要在读写时注意控制，以及节点编号的判断与更改

交换数据，进行排序

流程如下：

1. 从最后一个节点开始；
2. 交换根节点和这个节点的值；
3. 维护大根堆
   3.1 从根节点开始，读取左右孩子的值；
   3.2 比较大小，确定是否需要交换，以及交换的数据；
   3.3 写入或不写入，如果这个节点是叶子节点，那么维护结束。
4. 如果这个节点已经是根节点，排序结束。

我们可以发现在这个第三步和之前构建的步骤是相似的，虽然我很想优化掉它，但是能力不太够

实现

这个部分最容易出现的问题就是读写，然后自己也是调试了好几天才弄出来

顶层代码

module top
#(
    parameter ADDR_WIDTH = 12,
    parameter DATA_WIDTH = 8
)
(
    input clk,rst,
    output [ADDR_WIDTH:1] addr1,addr2,addr3,    //read addr
    output [ADDR_WIDTH-1:0] w_addr1,w_addr2,
    output [DATA_WIDTH-1:0] data1,data2,data3,   //data
    output we,re,w_ok,r_ok,                                  //enable write and read
    output [DATA_WIDTH-1:0] w_data1,w_data2     //write data
    
);

    heap_sort hp
    (.clk(clk),.rst(rst),.w_ok(w_ok),.r_ok(r_ok),.re(re),
                .data1(data1),.data2(data2),.data3(data3),
                .addr1(addr1),.addr2(addr2),.addr3(addr3),
                .we(we),.w_data1(w_data1),.w_data2(w_data2),
                .w_addr1(w_addr1),.w_addr2(w_addr2));
                
    ram ram01
    (.clk(clk),.we(we),.re(re),.w_ok(w_ok),.r_ok(r_ok),
                .addr1(addr1),.addr2(addr2),.addr3(addr3),
                .w_data1(w_data1),.w_data2(w_data2),
                .w_addr1(w_addr1),.w_addr2(w_addr2),
                .r_data1(data1),.r_data2(data2),.r_data3(data3));
endmodule

排序部分状态机算法

module heap_sort
#(
    parameter ADDR_WIDTH = 12,
    parameter DATA_WIDTH = 8,
    parameter FSM_STATE = 5
)
(
    input clk,rst,
    input [DATA_WIDTH-1:0] data1,data2,data3,       //data from ram
    input w_ok,r_ok,                                //finish read and write
    output reg [ADDR_WIDTH:1] addr1,addr2,addr3,    //read addr
    output reg [ADDR_WIDTH-1:0] w_addr1,w_addr2,
    output reg we,re,                                  //enable write and read
    output reg [DATA_WIDTH-1:0] w_data1,w_data2     //write data
    );

    parameter IDLE = 0;
    parameter BUILD_READ = 1;
    parameter BUILD_COMPARED = 2;
    parameter BUILD_WRITE = 3;
    parameter UPKEEP_READ = 4;
    parameter UPKEEP_COMPARED = 5;
    parameter UPKEEP_WRITE = 6;
    parameter SORT_READY = 7;
    parameter SORT_CHANGE = 8;
    parameter SORT_CWRITE = 9;
    parameter SORT_READ = 10;
    parameter SORT_COMPARED = 11;
    parameter SORT_WRITE = 12;
    parameter COMPLETED = 13;
    parameter ERROR = 14;

    reg [FSM_STATE-1:0] state;
    reg [ADDR_WIDTH-1:0] i,j,k;
    reg lf; 

    always @(posedge clk) begin
        if (rst) begin
            state <= 0;
            i <= 0;
            j <= 0;
            k <= 0;
            lf <= 0;
        end
        else begin
            case (state)
                IDLE:begin
                    state <= BUILD_READ;
                    i <= ADDR_WIDTH / 2;
                    j <= ADDR_WIDTH;
                    k <= ADDR_WIDTH;
                end
                BUILD_READ:begin
                    //disable write
                    we = 0;
                    //condition of ending build 
                    if(i)begin
                        state <= BUILD_COMPARED;
                        re = 1;
                        addr1 <= i;
                        addr2 <= 2 * i;
                        if(i * 2 + 1 <= ADDR_WIDTH) addr3 <= i * 2 + 1;
                        else addr3 <= 1;
                    end
                    else begin
                        state <= SORT_READY;
                        re <= 0;
                    end
                end
                BUILD_COMPARED:begin
                    // big-node
                    if(r_ok) begin
                        if(i * 2 + 1 <= ADDR_WIDTH) begin
                            if(data1 <= data3 && data2 <= data3) begin
                                w_data1 <= data3;
                                w_data2 <= data1;
                                w_addr1 <= addr1;
                                w_addr2 <= addr3;
                                k <= addr3;
                                state = BUILD_WRITE;
                            end
                            else if(data1 <= data2 && data3 < data2) begin
                                w_data1 <= data2;
                                w_data2 <= data1;
                                w_a