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