引言 推排序常常應用在操作系統的任務調度中，嘗試使用硬體對堆排序進行實現，在實現的過程中不使用function和tasks語法，即真·硬體實現 參考的博客 也就這一個博客有介紹 堆排序的Verilog實現 原理 ~~堆排序還需要複習一遍嗎?~~ 我肯定是要的 菜鳥-堆排序 圖解排序演算法(三)之堆排序 ...
引言
推排序常常應用在操作系統的任務調度中，嘗試使用硬體對堆排序進行實現，在實現的過程中不使用function和tasks語法，即真·硬體實現
參考的博客
也就這一個博客有介紹
堆排序的Verilog實現
原理
堆排序還需要複習一遍嗎? 我肯定是要的
菜鳥-堆排序
圖解排序演算法(三)之堆排序
可以看到，推排序很複雜，所以我們需要祭出我們的FSM(有限狀態機)
首先，將整個堆排序分為兩個階段：
- 構建大根堆或小根堆
- 從最後一個節點開始，和根節點交換，並維護大根堆
我們這裡統一構建大根堆
大根堆的構建
直接上流程：
-
從第一個非葉子節點開始，讀取左右孩子的值；
-
比較大小，確定是否需要交換，以及交換的數據；
-
寫入或不寫入，如果這個節點是根節點，那麼構建結束。
還是很簡單的，就是需要在讀寫時註意控制，以及節點編號的判斷與更改
交換數據，進行排序
流程如下：
- 從最後一個節點開始；
- 交換根節點和這個節點的值；
- 維護大根堆
3.1 從根節點開始，讀取左右孩子的值；
3.2 比較大小，確定是否需要交換，以及交換的數據；
3.3 寫入或不寫入，如果這個節點是葉子節點，那麼維護結束。 - 如果這個節點已經是根節點，排序結束。
我們可以發現在這個第三步和之前構建的步驟是相似的，雖然我很想優化掉它，但是能力不太夠
實現
自己實現的讀寫時序存在問題，改好bug後再貼出來
缺陷
我覺得最大的缺陷就是：排序的數比較固定，就是和其他Verilog實現的排序演算法相似，都是存在這個問題，如果更改排序的數的個數，這個模塊或多或少都要修改一部分
