本发明涉及碰撞检测，尤其涉及一种基于忆阻器阵列的碰撞检测加速器及其使用方法。
背景技术：
1、碰撞检测是机器人路径规划中最耗时间的一个步骤，占用了超过90％的总时间。完整的路径规划一共分为三部分，首先，一个完整的立体空间通过传感器被编码为路径图。编码之后的路径图包括环境中的障碍物，以及所有机器人可能的运动轨迹。第二步，在碰撞检测中，每一条运动轨迹需要和环境中的所有障碍物一一比对，得到这条轨迹的碰撞结果。最后，基于所有轨迹的碰撞结果，应用图搜索算法等，可以搜索到从起始点到终止点的最优路径，即机器人路径规划的最优解。
2、然而，机器人本身存在的高自由度，环境中的动态障碍物，以及现实环境中机器人大量可能的运动轨迹，使得路径规划中的碰撞比对成为一个耗时长，能耗高的任务。传统的基于中央处理器(central processing unit,cpu)的计算方式需要3秒或以上的时间才能完成碰撞检测任务。而由于环境中存在动态障碍物，应用于实际的加速器需要满足小于1毫秒的时间限制，才能保证在实时环境中路径规划的准确率。为了进一步满足碰撞检测需要的低延时和低能耗，人们已经设计了一系列的加速器来满足机器人实时避障的需求。
3、高性能图形处理器(graphics processing unit,gpu)应用于路径规划可以有效加速碰撞检测的过程。然而，目前基于gpu的加速器仍然需要几百毫秒的时间来完成碰撞比对，并且需要占用大量的功耗，不满足现实的应用场景。基于专用集成电路(application-specific integrated circuits,asic)的加速器在碰撞检测任务中具备广泛的应用前景。例如，基于现场可编程门阵列(field programmable gate array,fpga)的硬件加速器可以实现快速的碰撞检测，然而片上面积的限制使得此类加速器只能被应用于小规模的环境中。基于静态随机存取存储器(static random access memory,sram)的加速器通过八叉树的编码方式，和迭代循环的算法能够支持基于大规模环境的路径规划。然而，从cpu到计算单元的大量数据搬运能耗开销较大，计算效率也无法满足实时动态环境的要求。
4、研究人员已经设计了应用于路径规划应用中碰撞检测的一系列asic硬件加速器，相比于初始的cpu实现方法取得了计算速度和能效上的很大进步。但目前的一些加速器尚不够完善，并且存在一些可继续优化的空间：
5、(1)现有基于软件的加速器需要消耗大量的能耗和时延，编译高自由度的机器人避障环境需要消耗大量时间。
6、(2)基于硬件的asic加速器受限于片上面积，无法同时将所有数据同时部署，很难处理大规模的环境避障。
7、(3)基于硬件的asic加速器需要占用大量开销从存储单元将数据搬运到计算单元，极大降低了整体的工作效率。
8、因此，需要一种新型的硬件加速器，能够同时支持快速(<1毫秒)和大规模的碰撞检测，以应用于环境路径规划。通过引入忆阻器的存内计算技术，可以大大减少内存间数据搬运的功耗，具备应用于动态环境中实时低功耗碰撞检测的前景。
9、存内计算通过在存储器内部进行实时数据处理和分析，减少数据传输时间和带宽消耗。而阻变式随机存取存储器(resistive random-access memory,rram)，即忆阻器，是一种新型的存储器件，以其极好的互补金属氧化物半导体(complementary metal-oxide-semiconductor,cmos)工艺兼容性、小尺寸、低功耗、非易失性、大容量等特点而被广泛研究，成为有望用于下一代高密度的片上存储级内存以及存内计算的具有潜力的技术。基于忆阻器的存内计算模型在神经网络加速，机器学习，图像识别等领域具备广泛的应用前景。
10、已有文献应用动态随机存取存储器(dynamic randomaccess memory,dram)作为存储单元，使用大规模dram阵列存储环境信息实现碰撞检测的存内计算。通过八叉树的环境编码和每个子阵列中添加的三条额外位线，实现了dram阵列的存内计算比对。
11、然而，现有的基于dram实现存算功能需要消耗较大的额外面积和功耗，且由于其易失性，不断刷新的功耗较大，因此整个加速器工作需要占用大量能耗和面积开销。
12、因此，本领域的技术人员致力于开发一种基于非易失性忆阻器阵列的存内计算碰撞检测加速器及其使用方法，以克服现有技术存在的问题。
技术实现思路
1、有鉴于现有技术的上述缺陷，本发明所要解决的技术问题是：现有加速器未能满足小于1毫秒的时间限制；现有加速器在数据搬运的过程中消耗了大量能耗；以及现有加速器难以支持大规模的环境避障比对的问题。
2、为实现上述目的，本发明提供了一种基于非易失性忆阻器阵列的存内计算碰撞检测加速器，包括第一存储器阵列、第二存储器阵列、第三存储器阵列、中央处理器、时序控制电路、信号“0”产生器，所述第一存储器阵列为传统的静态随机存取存储器阵列，被配置为存储动态环境编码；所述第二存储器阵列为大规模基于忆阻器的三态内容寻址存储器阵列，被配置为存储所有机器人轨迹编码，并逐步接收来自所述第一存储器阵列的行数据；所述第三存储器阵列为基于静态随机存取存储器的内容寻址存储器阵列，被配置为存储来自所述第二存储器阵列的搜索结果；所述环境编码和轨迹编码基于三态内容寻址存储器的扩展八叉树进行编码和建立逻辑映射表格；所述中央处理器被配置为控制所述第一存储器阵列和时序控制电路，并接收来自所述第三存储器阵列的匹配结果；所述信号“0”产生器与所述第三存储器阵列的搜索数据缓存连接；所述时序控制电路被配置为检测所述第三存储器阵列是否被数据充满，如果没有，则将所述第二存储器阵列的搜索结果发送到所述第三存储器阵列，如果被数据充满，所述中央处理器控制所述信号“0”产生器产生全零向量发送到所述第三存储器阵列的搜索数据缓存，搜索得到碰撞比对结果。
3、进一步地，所述中央处理器进一步被配置为利用路径搜索算法，返回机器人从起始点到终止点的最佳路径。
4、进一步地，所述环境编码具体过程为：将整个三维环境切分为8n-1个相同大小的子立方体，n代表八叉树编码的层数，至少为2，使用2比特数据对最后一层的八叉树进行编码，根据每个最后一层子空间内物体占据状态的不同，赋予其对应的编码，当最后一层子空间内物体占据状态为完全占据时，编码为“11”，当最后一层子空间内物体占据状态为部分占据时，编码为“10”，当最后一层子空间内物体占据状态为完全空闲时，编码为“00”；所述轨迹编码具体过程为：在碰撞检测开始前，环境中的传感器感应整个三维环境中的障碍物，并分析所有机器人可能的运行轨迹，并依此建立完整的路径图，对于机器人的每条运行轨迹，使用整个三维环境作为八叉树编码的基空间，将机器人的每条运行轨迹扫过的体积视为障碍物，其他体积为空闲空间，当最后一层子空间被运行轨迹扫过的体积完全占据时，编码为“11”，当最后一层子空间被运行轨迹扫过的体积部分占据时，编码为“10”，当最后一层子空间被运行轨迹扫过的体积完全空闲时，编码为“00”。
5、进一步地，所述第一存储器阵列中存储的动态环境编码被配置为将编码“1”转换为电源高电平，将编码“0”转换为低电平。
6、进一步地，所述第二存储器阵列中存储的所有机器人轨迹编码被配置为将编码“1”转换为低阻态，将编码“0”转换为高阻态。
7、进一步地，所述第二存储器阵列中的基本单元为两个晶体管-两个忆阻器的结构。
8、进一步地，所述第二存储器阵列的匹配线通过灵敏放大器与所述第三存储器阵列连接。
9、进一步地，所述第一存储器阵列通过灵敏放大器与所述第二存储器阵列的搜索数据缓存连接，所述第二存储器阵列的搜索数据缓存与所述第二存储器阵列的搜索信号线连接。
10、进一步地，所述第三存储器阵列为多个第三存储器阵列，所述多个第三存储器整列与所述第二存储器阵列并行连接。
11、本发明还提供了一种如上所述的基于忆阻器阵列的碰撞检测加速器的使用方法，包括以下步骤：
12、步骤1、将第一存储器阵列的行数据表示为enj，其中j为第一存储器的行数，每一行代表一个子空间，j初始化为1；
13、步骤2、将第一存储器阵列的第j行数据读取并发送到第二存储器阵列中的搜索数据缓存；
14、步骤3、在第二存储器阵列中执行搜索操作，第二存储器阵列的搜索数据缓存中的环境编码与相应子空间的轨迹编码之间进行碰撞检测，如果发生了碰撞，相应的匹配线电压将被拉低，只有当所有子空间都没有碰撞时，匹配线电压才能保持高电平；将碰撞结果返回到第二存储器阵列的匹配结果缓存中，记为crij，其中i代表第二存储器阵列打开的行数为第i行，即执行碰撞检测的轨迹当前为第i个，i的最大值决定了一次同时比对搜索的轨迹数量；
15、步骤4、将第二存储器阵列中的匹配结果存储到第三存储器阵列的列向量中；时序控制电路检测第三存储器阵列是否被数据充满，如果没有，则j递增1，返回步骤2；
16、步骤5、执行第三存储器阵列搜索以输出最终的碰撞检测结果cri，第三存储器阵列中的每一行表示一条轨迹与所有子空间的环境之间的碰撞结果，如果在第三存储器阵列搜索过程中，第三存储器阵列中的某个匹配线被拉低，表明这条轨迹与环境存在碰撞情况。
17、本发明的有益效果在于：
18、1、通过设计独特的比对表格，匹配三态内容寻址存储器的存内搜索逻辑和碰撞比对逻辑，实现一个环境同时和多个机器人运行轨迹进行比对。后续通过进一步的流水线设计和二次搜索操作，进一步减少了整体运算的时延。与此同时，三态内容寻址存储器所独有的“x”位编码逻辑，能够支持碰撞检测过程中分辨率不足导致进一步细分的要求，基于忆阻器的三态内容寻址存储器结构具备快速碰撞检测的能力。
19、2、基于忆阻器的存内搜索结构可以在实现存储的同时，完成碰撞检测的比对。为了避免多次刷新写入导致的忆阻器耐久度问题，我们使用大规模的忆阻器阵列来存储较为固定的路径图，即大规模的机器人运行轨迹，而使用静态随机存取存储器阵列存储实时变化的动态环境，利用忆阻器阵列本身的高密度，低能耗和快速读取速度进行能耗和时延的碰撞检测加速器设计。
20、3、八叉树的编码方式加上大规模忆阻器阵列的应用，使得片上部署大规模环境的轨迹信息成为可能。由于环境中存在动态障碍物，静态随机存取存储器其高速的读写速度能够支持环境变化的速率。由于在整个碰撞检测任务中，机器人大量的运行轨迹需要占据大量的存储空间，高密度的忆阻器存储和灵活的八叉树编码能够大大降低面积开销。
21、以下将结合附图对本发明的构思、具体结构及产生的技术效果作进一步说明，以充分地了解本发明的目的、特征和效果。
1.一种基于忆阻器阵列的碰撞检测加速器，其特征在于，包括第一存储器阵列、第二存储器阵列、第三存储器阵列、中央处理器、时序控制电路、信号“0”产生器，所述第一存储器阵列为传统的静态随机存取存储器阵列，被配置为存储动态环境编码；所述第二存储器阵列为大规模基于忆阻器的三态内容寻址存储器阵列，被配置为存储所有机器人轨迹编码，并逐步接收来自所述第一存储器阵列的行数据；所述第三存储器阵列为基于静态随机存取存储器的内容寻址存储器阵列，被配置为存储来自所述第二存储器阵列的搜索结果；所述环境编码和轨迹编码基于三态内容寻址存储器的扩展八叉树进行编码和建立逻辑映射表格；所述中央处理器被配置为控制所述第一存储器阵列和时序控制电路，并接收来自所述第三存储器阵列的匹配结果；所述信号“0”产生器与所述第三存储器阵列的搜索数据缓存连接；所述时序控制电路被配置为检测所述第三存储器阵列是否被数据充满，如果没有，则将所述第二存储器阵列的搜索结果发送到所述第三存储器阵列，如果被数据充满，所述中央处理器控制所述信号“0”产生器产生全零向量发送到所述第三存储器阵列的搜索数据缓存，搜索得到碰撞比对结果。
2.如权利要求1所述的基于忆阻器阵列的碰撞检测加速器，其特征在于，所述中央处理器进一步被配置为利用路径搜索算法，返回机器人从起始点到终止点的最佳路径。
3.如权利要求1所述的基于忆阻器阵列的碰撞检测加速器，其特征在于，所述环境编码具体过程为：将整个三维环境切分为8n-1个相同大小的子立方体，n代表八叉树编码的层数，至少为2，使用2比特数据对最后一层的八叉树进行编码，根据每个最后一层子空间内物体占据状态的不同，赋予其对应的编码，当最后一层子空间内物体占据状态为完全占据时，编码为“11”，当最后一层子空间内物体占据状态为部分占据时，编码为“10”，当最后一层子空间内物体占据状态为完全空闲时，编码为“00”；所述轨迹编码具体过程为：在碰撞检测开始前，环境中的传感器感应整个三维环境中的障碍物，并分析所有机器人可能的运行轨迹，并依此建立完整的路径图，对于机器人的每条运行轨迹，使用整个三维环境作为八叉树编码的基空间，将机器人的每条运行轨迹扫过的体积视为障碍物，其他体积为空闲空间，当最后一层子空间被运行轨迹扫过的体积完全占据时，编码为“11”，当最后一层子空间被运行轨迹扫过的体积部分占据时，编码为“10”，当最后一层子空间被运行轨迹扫过的体积完全空闲时，编码为“00”。
4.如权利要求3所述的基于忆阻器阵列的碰撞检测加速器，其特征在于，所述第一存储器阵列中存储的动态环境编码被配置为将编码“1”转换为电源高电平，将编码“0”转换为低电平。
5.如权利要求4所述的基于忆阻器阵列的碰撞检测加速器，其特征在于，所述第二存储器阵列中存储的所有机器人轨迹编码被配置为将编码“1”转换为低阻态，将编码“0”转换为高阻态。
6.如权利要求5所述的基于忆阻器阵列的碰撞检测加速器，其特征在于，所述第二存储器阵列中的基本单元为两个晶体管-两个忆阻器的结构。
7.如权利要求6所述的基于忆阻器阵列的碰撞检测加速器，其特征在于，所述第二存储器阵列的匹配线通过灵敏放大器与所述第三存储器阵列连接。
8.如权利要求1所述的基于忆阻器阵列的碰撞检测加速器，其特征在于，所述第一存储器阵列通过灵敏放大器与所述第二存储器阵列的搜索数据缓存连接，所述第二存储器阵列的搜索数据缓存与所述第二存储器阵列的搜索信号线连接。
9.如权利要求1所述的基于忆阻器阵列的碰撞检测加速器，其特征在于，所述第三存储器阵列为多个第三存储器阵列，所述多个第三存储器整列与所述第二存储器阵列并行连接。
10.一种如权利要求1所述的基于忆阻器阵列的碰撞检测加速器的使用方法，其特征在于，包括以下步骤：
