本发明涉及组合优化领域，尤其涉及一种基于解耦式分层聚类的可扩展ising模型退火处理电路。
背景技术：
1、旅行商问题(travelling salesman problem，tsp)是在给定一系列城市和每对城市之间距离的条件下，求解访问每座城市一次并回到起始城市的最短路径的问题，在运筹学和理论计算机科学领域具有重大的研究意义。此外，许多现实世界的实际问题，如路由问题、物流配送问题、工程调度问题、金融投资问题等都可以映射到旅行商问题上。但作为组合优化中的一个典型的np难问题，随着旅行商问题规模的不断增大，传统计算机难以高效地求解旅行商问题的最优路径。
2、虽然ising模型为求解组合优化问题提供了统一的计算形式，但目前已有的ising退火处理器针对旅行商问题等带有约束的组合优化问题尚未具备高效的求解能力，具体可分为以下五个方面：
3、1)旅行商问题的复杂性高，映射到ising模型后的自旋数量和相应自旋间的耦合权重数据量庞大，导致硬件存储资源开销巨大；
4、2)所部署的全连接ising模型的网络连接密集程度高、复杂度高、可扩展性差，极大地限制了可处理的旅行商问题的规模；
5、3)旅行商问题的可行解之间存在较多、较高的能量势垒，当面对大规模的旅行商问题时，目前的ising退火处理器无法高效地探索解空间；
6、4)全连接ising模型的自旋间的数据依赖性限制，无法实现多自旋的同时更新，收敛速度较慢；
7、5)对于自旋更新判断过程中的概率激活函数的硬件实现，普遍存在面积开销大、近似精度或稳定性差的问题。
8、总的来说，对于一种能够解决大规模旅行商问题的存储资源开销小、高度可扩展、具有高效搜索机制、收敛速度快、概率激活函数硬件实现高效的ising模型退火处理器架构，目前仍没有比较好的解决方案。
技术实现思路
1、本发明目的在于提供一种基于解耦式分层聚类的可扩展ising模型退火处理电路，以解决上述现有技术存在的问题。
2、本发明中所述一种基于解耦式分层聚类的可扩展ising模型退火处理电路，包括：一个主控制器、s个集群退火处理模块、t个gty高速收发器、一个高速串行计算机扩展总线和若干个流水线寄存器；
3、所述主控制器用于产生各种控制信号，并且根据当前层的最优解计算下一层的外部场，然后将外部场加载到相应的集群退火处理模块中，并启动下一层的退火过程，直到所有层都被解决；
4、每个集群退火处理模块用于进行退火计算；包含四个集群退火处理单元、一个基于泰勒-查找表混合近似的阈值生成器和两个局部缓冲器；
5、所述t个gty高速收发器用于芯片间通信以支持大规模问题；
6、所述高速串行计算机扩展总线用于高效的数据加载、控制和结果读取；
7、所述若干个流水线寄存器放置在集群退火处理模块、集群退火处理单元与主控制器之间的总线上。
8、集群退火处理单元包含16个集群退火处理核心与一个局部控制器；集群退火处理核心包含两随机数产生器、自旋表、δh计算器、动态预测电路、更新控制电路与权重局部场存储器；
9、两随机数产生器用于生成两个不重复的随机整数i和j，以在自旋表中随机选中两行，其中0≤i<j≤15；
10、自旋表用于保存和更新自旋状态；
11、δh计算器和动态预测电路采用四自旋一步更新方法；
12、更新控制电路用于判断是否接收此步更新；
13、权重局部场存储器用于存储16×16m位权重系数w和16×2n位外部场h；
14、δh计算器采用8个加法器和若干个多路复用器计算同时更新四个自旋所带来的能量差δh，其中的自旋指数ki和kj用于选择相应的权重向量，而补偿值则通过两个随机数生成器生成的随机整数i和j来选择；动态预测电路在计算δh之前预测自旋表的下一个状态并相应地生成预测信号，如果预测成功，系统将继续进行下一次迭代；如果预测失败，则发出拒绝信号，并且下一个更新步骤将替换为纠正步骤，以将正确的状态加载到旋转表中。
15、动态预测电路具体步骤：
16、1)通过将阈值th与查找表中的预测阈值pth进行比较来生成预测信号；如果阈值th大于预测阈值pth，则预测信号设置为1；否则设置为0；
17、2)在同一时钟周期内，δh计算器计算δh，动态预测模块相应地生成更新信号；如果δh≤0或2kδh≤th，则更新信号设置为1；否则设置为0；
18、3)更新信号与预测信号进行异或运算得到的拒绝信号表示预测是否成功；如果拒绝信号被置为有效，则需要采取纠正步骤来纠正自旋状态。
19、基于泰勒-查找表混合近似的阈值生成器采用查找表的方式存储二阶导数较高的点。
20、对于斜率较小的点，直接采用泰勒近似以最小化面积开销；将概率激活函数判定翻转的条件pflip＝1进行变形可得2kδh≤th＝t(2k+4ln(2)-2kln(t)),t∈(0,216-1]，其中k是放缩系数，为正整数，th为激活阈值，t为温度，t为0到216-1的正整数；对数函数ln(t)采用近似泰勒级数进行拟合，其中，tn＝2n为泰勒级数展开点，biasn为对应的误差补偿值。
21、基于泰勒-查找表混合近似的阈值生成器采用10段泰勒展开来实现2kln(t)，并利用98×13b的查找表来存储前98个点的值；常数tn、2kln(tn)+2kbiasn存储在10×32b的查找表中，tn为17b，2kln(tn)+2kbiasn为15b；
22、输入t由16位线性移位寄存器生成；若t<98，则直接从98×13b的查找表读取ln(t)的结果；若t≥98，则ln(t)的结果是通过多次泰勒展开生成的，而tn、2kln(tn)+2kbiasn是根据t的值从10×32b的查找表中读取。
23、基于泰勒-查找表混合近似的阈值生成器具有四级流水线结构：
24、在流水线的第一级中，使用加法器和乘法器来生成(t-tn)和(t-tn)2；
25、在流水线的第二级中生(t-tn)3，而移位器用于计算和
26、
27、在流水线的第三级中，根据输入t对选择器的选择结果生成2kln(t)；
28、在流水线的第四级中，依据温度计算出阈值th。
29、本发明中所述一种基于解耦式分层聚类的可扩展ising模型退火处理电路，其优点在于，通过对同层次不同集群之间的解耦操作，消除了同层次相邻集群之间的约束关系，实现了不同集群之间的独立操作与并发更新，具有高度的可扩展性。所提出的增量聚类法减少了硬件设计复杂度，提高了硬件利用效率。采用交换更新的方式，搜索机制高效，且有效地减少了耦合权重系数与外部场大幅度减少了存储资源消耗。
30、提出的集群退火处理核心可进行独立地并发更新操作，一次可更新四个自旋收敛速度高，通过调整总线上群退火处理模块的数量，可以处理任何规模的旅行商问题。提出了动态预测电路，通过预测更新后的状态进行下一次迭代的运算，从而进一步提高收敛速度。
31、提出了基于泰勒-查找表混合近似的阈值生成器，通过混合近似的方式高效地实现了对数函数的近似，从而以低硬件成本、高稳定性、高精确度的方式实现了概率激活函数的计算。
1.一种基于解耦式分层聚类的可扩展ising模型退火处理电路，其特征在于，包括：一个主控制器、s个集群退火处理模块、t个gty高速收发器、一个高速串行计算机扩展总线和若干个流水线寄存器；
2.根据权利要求1所述一种基于解耦式分层聚类的可扩展ising模型退火处理电路，其特征在于，集群退火处理单元包含16个集群退火处理核心与一个局部控制器；集群退火处理核心包含两随机数产生器、自旋表、δh计算器、动态预测电路、更新控制电路与权重局部场存储器；
3.根据权利要求2所述一种基于解耦式分层聚类的可扩展ising模型退火处理电路，其特征在于，动态预测电路具体步骤：
4.根据权利要求3所述一种基于解耦式分层聚类的可扩展ising模型退火处理电路，其特征在于，基于泰勒-查找表混合近似的阈值生成器采用查找表的方式存储二阶导数较高的点。
5.根据权利要求4所述一种基于解耦式分层聚类的可扩展ising模型退火处理电路，其特征在于，对于斜率较小的点，直接采用泰勒近似以最小化面积开销；将概率激活函数判定翻转的条件pflip＝1进行变形可得2kδh≤th＝t(2k+4ln(2)-2kln(t)),t∈(0,216-1]，其中k是放缩系数，为正整数，th为激活阈值，t为温度，t为0到216-1的正整数；对数函数ln(t)采用近似泰勒级数进行拟合，其中，tn＝2n为泰勒级数展开点，biasn为对应的误差补偿值。
6.根据权利要求5所述一种基于解耦式分层聚类的可扩展ising模型退火处理电路，其特征在于，基于泰勒-查找表混合近似的阈值生成器采用10段泰勒展开来实现2kln(t)，并利用98×13b的查找表来存储前98个点的值；常数tn、2kln(tn)+2kbiasn存储在10×32b的查找表中，tn为17b，2kln(tn)+2kbiasn为15b；
7.根据权利要求6所述一种基于解耦式分层聚类的可扩展ising模型退火处理电路，其特征在于，基于泰勒-查找表混合近似的阈值生成器具有四级流水线结构：
