推排序 Verilog实现原理

这篇具有很好参考价值的文章主要介绍了推排序 Verilog实现原理。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

引言

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

参考的博客

也就这一个博客有介绍
堆排序的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_addr1 <= addr1;
                                w_addr2 <= addr2;
                                k <= addr2;
                                state = BUILD_WRITE;
                            end
                            else begin
                                state = BUILD_READ;
                                i = i - 1;
                            end
                        end
                        else begin
                            if(data1 <= data2)begin
                                w_data1 <= data2;
                                w_data2 <= data1;
                                w_addr1 <= addr1;
                                w_addr2 <= addr2;
                                state = BUILD_WRITE;
                            end
                            else begin
                                state = BUILD_READ;
                                i = i - 1;
                            end
                        end
                        re <= 0;
                     end
                end
                BUILD_WRITE:begin
                    we = 1;
                    state <= UPKEEP_READ;
                    i = i - 1;
                end
                UPKEEP_READ:begin
                    //leaf node
                    if(k > ADDR_WIDTH / 2 ) state <= BUILD_READ;
                    else begin
                        state <= UPKEEP_COMPARED;
                        re = 1;
                    end
                    //disable write
                    we = 0;
                    addr1 <= k;
                    addr2 <= 2 * k;
                    if(k * 2 + 1 <= ADDR_WIDTH) addr3 <= k * 2 + 1;
                    else addr3 <= 1;
                end
                UPKEEP_COMPARED:begin
                     if(r_ok) begin
                        if(k * 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 <= UPKEEP_WRITE;
                            end
                            else if(data1 <= data2 && data3 < data2) begin
                                w_data1 <= data2;
                                w_data2 <= data1;
                                w_addr1 <= addr1;
                                w_addr2 <= addr2;
                                k <= addr2;
                                state <= UPKEEP_WRITE;
                            end
                            else state <= BUILD_READ;
                        end
                        else begin
                            if(data1 <= data2)begin
                                w_data1 <= data2;
                                w_data2 <= data1;
                                w_addr1 <= addr1;
                                w_addr2 <= addr2;
                                k <= ADDR_WIDTH;
                                state <= UPKEEP_WRITE;
                            end
                            else state <= BUILD_READ;
                            
                        end
                        re <= 0;
                     end
                end
                UPKEEP_WRITE:begin
                    we = 1;
                    state <= UPKEEP_READ;
                end
                SORT_READY:begin
                    we = 0;
                    //condition of ending sort
                    if(j) state <= SORT_CHANGE;
                    else state <= COMPLETED;
                    re <= 1;
                    addr1 <= 1;
                    addr2 <= j;
                    k <= 1;
                    
                end
                SORT_CHANGE:begin
                    if(r_ok)begin
                        w_data1 <= data2;
                        w_data2 <= data1;
                        w_addr1 <= addr1;
                        w_addr2 <= addr2;
                        state <= SORT_CWRITE;
                        re <= 0;
                    end
                end
                SORT_CWRITE: begin
                    we = 1;
                    state <= SORT_READ;
                    j = j - 1;
                end
                SORT_READ:begin
                    //disable write
                    we = 0;
                    if(k <= j / 2) begin
                        state <= SORT_COMPARED;
                        addr1 <= k;
                        addr2 <= 2 * k;
                        if(2 * k + 1 <= j) addr3 <= 2 * k + 1;
                        re <= 1;
                    end 
                    else begin
                        state <= SORT_READY;
                    end
                    
                end
                SORT_COMPARED:begin
                    // big-node
                    if(r_ok) begin
                        if(k * 2 + 1 <= j) begin
                            if(data1 <= data3 && data2 <= data3) begin
                                w_data1 <= data3;
                                w_data2 <= data1;
                                w_addr1 <= addr1;
                                w_addr2 <= addr3;
                                state <= SORT_WRITE;
                                lf <= 1;
                            end
                            else if(data1 <= data2 && data3 < data2) begin
                                w_data1 <= data2;
                                w_data2 <= data1;
                                w_addr1 <= addr1;
                                w_addr2 <= addr2;
                                state <= SORT_WRITE;
                                lf <= 0;
                            end
                            else state <= SORT_READY;
                        end
                        else begin
                            if(data1 <= data2)begin
                                w_data1 <= data2;
                                w_data2 <= data1;
                                w_addr1 <= addr1;
                                w_addr2 <= addr2;
                                state = SORT_WRITE;
                                lf <= 0;
                            end
                            else state <= SORT_READY;
                        end
                        re <= 0;
                    end
                end
                SORT_WRITE:begin
                    we = 1;
                    state <= SORT_READ;
                    if(lf) k = k * 2 + 1;
                    else k = k * 2;
                end
                COMPLETED:begin
                    state <= COMPLETED;
                end
                default:begin
                    state <= ERROR;
                end
            endcase
        end
    end
    
   
endmodule

寄存器数组部分代码

module ram 
#(
    parameter ADDR_WIDTH = 12,
    parameter DATA_WIDTH = 8
)
(
    input [ADDR_WIDTH-1:0] addr1,addr2,addr3,
    input [ADDR_WIDTH-1:0] w_addr1,w_addr2,
    input we,clk,re,
    input [DATA_WIDTH-1:0] w_data1,w_data2,
    output reg [DATA_WIDTH-1:0] r_data1,r_data2,r_data3,
    output reg w_ok,r_ok
    );
    
    reg [DATA_WIDTH-1:0] data[ADDR_WIDTH:1];
    
    initial begin
        $readmemh("data.mem",data);    //需要创建对应的文件,用于填充数据
    end
    always @(posedge clk) begin
        if (we ) begin
            data[w_addr1] <= w_data1;
            data[w_addr2] <= w_data2;
            w_ok <= 1;
        end
        else w_ok <= 0;
        if(re) begin
            r_data1 <= data[addr1];
            r_data2 <= data[addr2];
            r_data3 <= data[addr3];
            r_ok <= 1;
        end
        else r_ok <= 0;
    end

endmodule

激励模块

module top_tb
#(
    parameter ADDR_WIDTH = 12,
    parameter DATA_WIDTH = 8
)();
    reg clk,rst;
    wire [ADDR_WIDTH:1] addr1,addr2,addr3;    //read addr
    wire [DATA_WIDTH-1:0] data1,data2,data3;   //data
    wire we;                                  //enable write
    wire [DATA_WIDTH-1:0] w_data1,w_data2;     //write data

    initial begin
        clk <= 0;
        rst <= 1;
        #10;
        clk <= 1;
        #10;
        rst <= 0;
        forever begin
            clk <= ~clk;
            #50;
        end
    end
    top tp(clk,rst,addr1,addr2,addr3,data1,data2,data3,we,w_data1,w_data2);
endmodule

缺陷

实现过程中,最大的缺陷是排序的数不能太多,以为I/O端口有限文章来源地址https://www.toymoban.com/news/detail-418561.html

到了这里,关于推排序 Verilog实现原理的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 扰码器原理详解及verilog实现

            扰码就是对原始的用户数据进行扰乱,得到随机化的用户数据。连续扰码两次就能得到原始数据,通常是发送电路在发送数据时先对数据进行随机扰乱,接收电路使用相同的扰乱算法就可以重新恢复出原始的数据。如图所示:         扰码器产生伪随机的比特序列,

    2024年02月09日
    浏览(34)
  • FPGA实现Verilog 2分频:从原理到代码实现

    FPGA实现Verilog 2分频:从原理到代码实现 在数字电路设计中,2分频是一种常见的电路实现方式,可以将输入信号的频率减半。在FPGA设计中,我们可以利用Verilog语言快速实现2分频电路。本文将从原理出发,结合代码介绍FPGA实现2分频电路的方法。 原理及实现 2分频电路通常采

    2024年02月02日
    浏览(50)
  • 【Verilog编程】线性反馈移位寄存器(LFSR)原理及Verilog代码实现

    移位寄存器 :指若干个寄存器排成一列,每个寄存器中存放1bit二进制数据(0或1),每个时钟周期向左或向右移动一个bit。下图所示为一个向右移动的移位寄存器。 反馈移位寄存器(Feedback Shift Register,FSR) :每个时钟脉冲,移位寄存器向右移动一位,则移位寄存器的左左侧就

    2024年02月15日
    浏览(55)
  • FPGA流水线除法器(Verilog)原理及实现

      除法器的计算过程如下图所示。 假设数值的位宽为N。 Step1:分别将被除数和除数扩展至原来2倍位宽(2N),被除数在其左边补N位0,除数在其右边补N位0; Step2:将被除数依次左移(每次左移1位),末位补数值(该数值为被除数高N位与除数高N位的商),高N位为被除数高

    2024年02月11日
    浏览(41)
  • CRC循环冗余校验 (Cyclic Redundancy Check) 原理/电路实现/Verilog实现

    目录 1 什么是CRC循环冗余校验? 2 CRC校验的原理 2.1 多项式表示 2.2 模二 多项式除法 2.3 传输端  2.4 接收端 3 CRC码的产生 3.1 产生CRC码步骤 3.2 Verilog实现 4 电路实现原理—线性反馈移位寄存器 4.1 循环移位寄存器结构 4.2 最大长度移位寄存器  4.3 多项式除法电路(线性反馈移位

    2024年02月04日
    浏览(40)
  • 【排序算法】推排序算法解析:从原理到实现

    目录 1. 引言 2. 推排序算法原理 3. 推排序的时间复杂度分析 4. 推排序的应用场景 5. 推排序的优缺点分析 5.1 优点: 5.2 缺点: 6. Java、JavaScript 和 Python 实现推排序算法 6.1 Java 实现: 6.2 JavaScript 实现: 6.3 Python 实现: 7. 总结         推排序(Heap Sort)是一种高效的排序算法,

    2024年03月23日
    浏览(53)
  • 【排序算法】深入理解快速排序算法:从原理到实现

    目录 1. 引言 2. 快速排序算法原理 3. 快速排序的时间复杂度分析 4. 快速排序的应用场景 5. 快速排序的优缺点分析 5.1 优点: 5.2 缺点: 6. Java、JavaScript 和 Python 实现快速排序算法 6.1 Java 实现: 6.2 JavaScript 实现: 6.3 Python 7. 总结        快速排序是一种经典的排序算法,它的

    2024年03月20日
    浏览(46)
  • 【JAVA】我们常常谈到的方法是指什么?

    个人主页:【😊个人主页】 系列专栏:【❤️初识JAVA】 在之前的文章中我们总是会介绍到类中的各式各样的方法,也许在应用中我们对它已经有了初步的了解,今天我们就来详细的介绍一下“方法” 在中文中方法常常指的是获得某种东西或达到某种目的而采取的手段与行

    2024年02月13日
    浏览(45)
  • Verilog实现Gating clock(时钟门控技术)的原理和实现。可以画门级电路图。

    参考文献: 参考1-常见的锁存器结构,点击 参考2-clock gating整理,点击 时钟门控技术 ,是一种非常简单和有效的功耗控制方法,它的基本原理是通过关闭芯片上暂时用不到的功能和它的时钟,从而实现节省电流消耗的目的。 参考文献:

    2024年02月12日
    浏览(39)
  • 冒泡排序:原理、实现与性能分析

    引言 在编程世界中,排序算法是不可或缺的一部分。冒泡排序作为最基本的排序算法之一,虽然其效率并不是最高的,但其实现简单、易于理解的特点使得它成为学习和理解排序算法的入门之选。本文将详细介绍冒泡排序的原理、实现方法以及性能分析,帮助读者更好地掌握

    2024年02月19日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包