推排序 Verilog实现原理

引言

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

参考的博客

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

原理

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

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

首先,将整个堆排序分为两个阶段:

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

我们这里统一构建大根堆

大根堆的构建

直接上流程:

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

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

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

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

交换数据,进行排序

流程如下:

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

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

实现

自己实现的读写时序存在问题,改好bug后再贴出来

缺陷

我觉得最大的缺陷就是:排序的数比较固定,就是和其他Verilog实现的排序算法相似,都是存在这个问题,如果更改排序的数的个数,这个模块或多或少都要修改一部分

热门相关:斗神战帝   豪门闪婚:帝少的神秘冷妻   刺客之王   仗剑高歌   薄先生,情不由己