A*算法的FPGA 實(shí)現(xiàn)

郭金貴

（西安工業(yè)大學(xué)機(jī)電工程學(xué)院，陜西 西安 710021）

1 A*算法FPGA 實(shí)現(xiàn)的整體系統(tǒng)設(shè)計(jì)

系統(tǒng)的整體結(jié)構(gòu)框圖如圖1 所示。它主要包括系統(tǒng)的整體控制模塊，節(jié)點(diǎn)查找模塊，節(jié)點(diǎn)選擇模塊，路徑信息更新模塊，最優(yōu)路徑選擇模塊，存儲(chǔ)接口模塊。

從圖1 中可以看到A*算法FPGA 實(shí)現(xiàn)的各個(gè)模塊的大致分布關(guān)系。主要有路徑參數(shù)等信息作為系統(tǒng)的輸入，系統(tǒng)的輸出主要包括SDRAM讀寫的路徑信息和最優(yōu)路徑信息。

圖1 A*算法FPGA 設(shè)計(jì)總體結(jié)構(gòu)框圖

從圖2 可以看出系統(tǒng)設(shè)計(jì)的整個(gè)流程。從輸入開始后，系統(tǒng)就進(jìn)入了工作狀態(tài)，首先對(duì)內(nèi)部寄存器進(jìn)行了初始化，然后讀取第一個(gè)節(jié)點(diǎn)所有的集合，根據(jù)節(jié)點(diǎn)信息選取下一節(jié)點(diǎn)，節(jié)點(diǎn)選擇后進(jìn)行信息更新，把當(dāng)前的狀態(tài)信息進(jìn)行存儲(chǔ)；然后判斷所有節(jié)點(diǎn)是否都已遍歷，如果是，存儲(chǔ)路徑，判斷循跡是否完成，循跡完成后根據(jù)選擇比較電路，得出最優(yōu)路徑，否則繼續(xù)進(jìn)行循跡直到查找到目標(biāo)點(diǎn)為止，最后結(jié)束整個(gè)優(yōu)化算法流程。

圖2 FPGA 整體控制流程圖

2 存儲(chǔ)模塊設(shè)計(jì)

SDRAM存儲(chǔ)模塊，它主要是用于讀寫節(jié)點(diǎn)的延遲信息、節(jié)點(diǎn)的花費(fèi)信息、節(jié)點(diǎn)的位置信息以及最優(yōu)結(jié)果信息。SDRAM設(shè)計(jì)邏輯框如圖3 所示。

圖3 SDRAM 設(shè)計(jì)邏輯框圖

PC 端通過串口將要發(fā)送的命令數(shù)據(jù)發(fā)送給FPGA，F(xiàn)PGA 內(nèi)部串口接收模塊將接收到的命令和數(shù)據(jù)傳遞給命令解析模塊，命令解析模塊的主要作用是將命令和數(shù)據(jù)進(jìn)行分離，將待寫入SDRAM的數(shù)據(jù)輸出到寫FIFO 里面，讀寫指令通過另一通道傳遞給SDRAM的頂層模塊，寫的時(shí)候從寫FIFO 里面把數(shù)據(jù)拿出來，寫入到SDRAM 里面，讀的時(shí)候?qū)DRAM 上一次寫入的數(shù)據(jù)讀出，存儲(chǔ)到讀FIFO 里面，全部讀出完之后，再將讀出的數(shù)據(jù)通過串口發(fā)送模塊發(fā)送到PC 端。如圖4 為SDRAM的讀寫狀態(tài)機(jī)。

圖4 SDRAM 讀寫狀態(tài)機(jī)

對(duì)SDRAM的控制器設(shè)計(jì)完成之后，進(jìn)行具體代碼設(shè)計(jì)，然后對(duì)SDRAM進(jìn)行仿真，使得數(shù)據(jù)和接口都符合SDRAM的實(shí)際時(shí)序。

3 系統(tǒng)整體控制模塊設(shè)計(jì)

系統(tǒng)整體控制模塊主要是完成整個(gè)系統(tǒng)的時(shí)序控制，控制其他各個(gè)模塊的工作關(guān)系，讓整個(gè)系統(tǒng)分模塊依次進(jìn)行工作?？刂颇K的邏輯交換圖如圖5 所示，表示control 模塊與各個(gè)分模塊的控制關(guān)系。

圖5 控制模塊邏輯交換圖

3.1 節(jié)點(diǎn)選擇模塊設(shè)計(jì)

節(jié)點(diǎn)選擇模塊主要是用于確定下一個(gè)節(jié)點(diǎn)，需要從當(dāng)前節(jié)點(diǎn)的八領(lǐng)域內(nèi)可選的位置中選擇一個(gè)估值最小的位置。其選擇主要取決于節(jié)點(diǎn)間路徑的延遲信息以及花費(fèi)信息，再加上OPEN 列表中必經(jīng)節(jié)點(diǎn)的信息，選擇出最優(yōu)的節(jié)點(diǎn)。具體實(shí)現(xiàn)電路如圖6 所示。

圖6 節(jié)點(diǎn)選擇模塊設(shè)計(jì)

3.2 路徑信息更新模塊設(shè)計(jì)

選擇好節(jié)點(diǎn)位置后，反饋到控制模塊，控制模塊控制路徑信息更新模塊進(jìn)行更新。更新的信息主要從起始節(jié)點(diǎn)到目前節(jié)點(diǎn)所走過的節(jié)點(diǎn)的位置信息，走過路徑總的延遲信息，總的花費(fèi)信息。具體實(shí)現(xiàn)電路如圖7 所示。

圖7 路徑信息更新模塊電路設(shè)計(jì)

3.3 最優(yōu)路徑選擇模塊設(shè)計(jì)

A*算法FPGA 實(shí)現(xiàn)的最優(yōu)路徑選擇模塊從根本上講是在遍歷完所有可行節(jié)點(diǎn)后，在所有路徑中選擇路徑長度花費(fèi)最?。╩incost）的作為最優(yōu)路徑。當(dāng)找到最優(yōu)路徑后就能夠知道，估價(jià)值最小的路徑和理論最優(yōu)的路徑是否一致，就可以驗(yàn)證出算法的正確性。為了驗(yàn)證，程序從所有過程的路徑中尋找。電路實(shí)現(xiàn)除了讀取地址接口外，本質(zhì)上來說是循環(huán)比較電路，如圖8 所示。

圖8 最優(yōu)路徑選擇模塊設(shè)計(jì)

4 結(jié)論

本文基于FPGA 平臺(tái)，對(duì)A*算法進(jìn)行了移植，通過從A*算法的整體功能出發(fā)，將A*算法劃分成六個(gè)不同功能的部分和模塊，并對(duì)各個(gè)模塊進(jìn)行了具體的電路設(shè)計(jì)與實(shí)現(xiàn)，并編寫測試文件，在modelsim 上進(jìn)行了仿真驗(yàn)證。實(shí)現(xiàn)了A*算法的FPGA 實(shí)現(xiàn)，提高了A*算法的尋跡速度。