推排序 Verilog实现原理

引言

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

参考的博客

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

原理

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

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

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

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

我们这里统一构建大根堆

大根堆的构建

直接上流程：

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

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

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

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

交换数据，进行排序

流程如下：

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

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

实现

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

缺陷

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