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*算法的寻迹速度。