A*算法的FPGA 實現

郭金貴

（西安工業大學機電工程學院，陜西 西安 710021）

1 A*算法FPGA 實現的整體系統設計

系統的整體結構框圖如圖1 所示。它主要包括系統的整體控制模塊，節點查找模塊，節點選擇模塊，路徑信息更新模塊，最優路徑選擇模塊，存儲接口模塊。

從圖1 中可以看到A*算法FPGA 實現的各個模塊的大致分布關系。主要有路徑參數等信息作為系統的輸入，系統的輸出主要包括SDRAM讀寫的路徑信息和最優路徑信息。

圖1 A*算法FPGA 設計總體結構框圖

從圖2 可以看出系統設計的整個流程。從輸入開始后，系統就進入了工作狀態，首先對內部寄存器進行了初始化，然后讀取第一個節點所有的集合，根據節點信息選取下一節點，節點選擇后進行信息更新，把當前的狀態信息進行存儲；然后判斷所有節點是否都已遍歷，如果是，存儲路徑，判斷循跡是否完成，循跡完成后根據選擇比較電路，得出最優路徑，否則繼續進行循跡直到查找到目標點為止，最后結束整個優化算法流程。

圖2 FPGA 整體控制流程圖

2 存儲模塊設計

SDRAM存儲模塊，它主要是用于讀寫節點的延遲信息、節點的花費信息、節點的位置信息以及最優結果信息。SDRAM設計邏輯框如圖3 所示。

圖3 SDRAM 設計邏輯框圖

PC 端通過串口將要發送的命令數據發送給FPGA，FPGA 內部串口接收模塊將接收到的命令和數據傳遞給命令解析模塊，命令解析模塊的主要作用是將命令和數據進行分離，將待寫入SDRAM的數據輸出到寫FIFO 里面，讀寫指令通過另一通道傳遞給SDRAM的頂層模塊，寫的時候從寫FIFO 里面把數據拿出來，寫入到SDRAM 里面，讀的時候將SDRAM 上一次寫入的數據讀出，存儲到讀FIFO 里面，全部讀出完之后，再將讀出的數據通過串口發送模塊發送到PC 端。如圖4 為SDRAM的讀寫狀態機。

圖4 SDRAM 讀寫狀態機

對SDRAM的控制器設計完成之后，進行具體代碼設計，然后對SDRAM進行仿真，使得數據和接口都符合SDRAM的實際時序。

3 系統整體控制模塊設計

系統整體控制模塊主要是完成整個系統的時序控制，控制其他各個模塊的工作關系，讓整個系統分模塊依次進行工作。控制模塊的邏輯交換圖如圖5 所示，表示control 模塊與各個分模塊的控制關系。

圖5 控制模塊邏輯交換圖

3.1 節點選擇模塊設計

節點選擇模塊主要是用于確定下一個節點，需要從當前節點的八領域內可選的位置中選擇一個估值最小的位置。其選擇主要取決于節點間路徑的延遲信息以及花費信息，再加上OPEN 列表中必經節點的信息，選擇出最優的節點。具體實現電路如圖6 所示。

圖6 節點選擇模塊設計

3.2 路徑信息更新模塊設計

選擇好節點位置后，反饋到控制模塊，控制模塊控制路徑信息更新模塊進行更新。更新的信息主要從起始節點到目前節點所走過的節點的位置信息，走過路徑總的延遲信息，總的花費信息。具體實現電路如圖7 所示。

圖7 路徑信息更新模塊電路設計

3.3 最優路徑選擇模塊設計

A*算法FPGA 實現的最優路徑選擇模塊從根本上講是在遍歷完所有可行節點后，在所有路徑中選擇路徑長度花費最小（mincost）的作為最優路徑。當找到最優路徑后就能夠知道，估價值最小的路徑和理論最優的路徑是否一致，就可以驗證出算法的正確性。為了驗證，程序從所有過程的路徑中尋找。電路實現除了讀取地址接口外，本質上來說是循環比較電路，如圖8 所示。

圖8 最優路徑選擇模塊設計

4 結論

本文基于FPGA 平臺，對A*算法進行了移植，通過從A*算法的整體功能出發，將A*算法劃分成六個不同功能的部分和模塊，并對各個模塊進行了具體的電路設計與實現，并編寫測試文件，在modelsim 上進行了仿真驗證。實現了A*算法的FPGA 實現，提高了A*算法的尋跡速度。