一种基于片上网络的大规模全连接伊辛模型退火处理电路

摘要

本发明公开了一种基于片上网络的大规模全连接伊辛模型退火处理电路，涉及伊辛模型技术领域，针对现有技术中的模型电路处理规模小、扩展性低、收敛速度慢、并行处理能力低等问题提出本方案。包括：全局控制器、控制总线、自旋处理阵列及合并路由器阵列；所述全局控制器对所有自旋处理单元进行并行控制；所有自旋处理单元共享退火温度和随机数，并通过所述合并路由器阵列进行通讯传递和计算。优点在于，具有高收敛速度、高并行度、高拓展性以及低设计复杂度、低硬件资源成本，能够实现对全连接伊辛模型的高速、高并行退火处理。

权利要求

1.一种基于片上网络的大规模全连接伊辛模型退火处理电路，其特征在于，包括：全局控制器、控制总线、自旋处理阵列及合并路由器阵列；所述全局控制器对所有自旋处理单元进行并行控制；所有自旋处理单元共享退火温度和随机数，并通过所述合并路由器阵列进行通讯传递和计算；

所述全局控制器包括I/O模块、控制逻辑模块、温度调度模块和随机数发生模块；所述I/O模块，负责在用户和处理电路之间交换信息；所述控制逻辑模块负责产生相应的控制信号；所述温度调度模块和随机数发生模块分别负责产生退火温度和随机数；所述控制总线将控制信号、退火温度和随机数发送给所有的自旋处理单元；

所述自旋处理阵列包括多个自旋处理单元，每个自旋处理单元再包含256个自旋，每次处理更新一个自旋；

自旋处理单元包括一个控制单元、一个状态更新单元和一个生产单元；

所述控制单元包括控制逻辑和计数器；所述控制逻辑用于接收全局控制器的指令、相应地产生本自旋处理单元内所有计算元件之间的控制信号；所述计数器用于记录256个自旋中状态为‑1的自旋数量；

所述状态更新单元由一个部分和数寄存器、一个 寄存器、一个 寄存器、一个绝对值器、三个加法器、一个比较器、一个乘法器和一个翻转器组成；所述绝对值器和加法器用于接收和累加相关系数 ，并将累加结果存于 寄存器中；所述部分和数寄存器用于寄存基本部分和数量，以及 寄存器用于寄存累加得到的 ；所述比较器用于比较 和，决定是否更新本自旋处理单元所处理的单个自旋，若符合更新条件则选择 进一步更新自旋状态，否则状态保持不变；

其中， ，判

断是否满足更新条件，根据系统反馈及 进行线程动态调整，并且在最后阶段进行回温操作；N为自旋总数、V为总并行更新自旋数、K为线程数、M为单个线程并行更新自旋数，均为整数；为外磁系数；是序号j的自旋值，且j取值1至16；

所述生产单元由七级流水线组成，包括一个访问控制器、16个J存储器、一个h存储器、

16个σ存储器、16个比较器、多个加法器、多个多路复用器和多个非门，用于产生 的基本部分和 和 中的相关系数 ，并发送到其它自旋处理单元；所述访问控制器用于专门控制存储或读出相关系数 和外磁系数 ；所述第一级流水线之前，一次从16个J存储器中读出16个相关系数 ，启动16个比较器判断这些系数是否与所有被选择进行更新的自旋相关，若相关，则将其传送到第一级流水线；所述第二级流水线，由上一级传来的16个相关系数 和存储在σ存储器中的16个自旋 产生 的16个基本部分和 ，即当 时，直接传给下一级，当 时，激活非门对 进行按位取反，然后将结果传递到下一级；所述第三级流水线，通过具有 16 个输入的加法器树对基本部分和进行累加；所述第四级流水线，将外磁系数 添加到上一阶段的结果中；所述第五级流水线，将控制单元中计数器记录的的数量与前一阶段的结果相加；所述第六级流水线，若累加的部分和与当前自旋处理单元中处理的自旋相关，则直接送入下一级流水线，否则，则等待其它240个部分和，并合并到下一级流水线；所述第七级流水线，将计算 的基本部分和 或 中的相关系数，打包成部分和或系数包，并转发给其它的自旋处理单元。

2.根据权利要求1所述一种基于片上网络的大规模全连接伊辛模型退火处理电路，其特征在于，所述合并路由器包括一个合并模块和一个路由模块，分别负责合并以及转发信息包。

说明书

一种基于片上网络的大规模全连接伊辛模型退火处理电路

技术领域

[0001] 本发明涉及伊辛模型技术领域，尤其涉及一种基于片上网络的大规模全连接伊辛模型退火处理电路。

背景技术

[0002] 组合优化问题是在一组有限的离散对象中，找出最优对象的一类问题，如旅行商问题、最大割问题、图形着色问题、航班调度问题等，属于典型的非确定性多项式难题。伊辛模型通过一群相互连接的自旋来描述物质相变的随机过程，大多数组合优化问题能够映射到伊辛模型中，即通过求解伊辛模型就能求解组合优化问题的最优解。退火算法源于固体物质退火原理，是一种通用的优化算法，能够有效求解伊辛模型。由于组合优化问题的解空间随着变量数而爆炸式增长且冯‑诺伊曼体系结构的处理器具有固有的串行工作机制，因此冯‑诺伊曼体系结构的处理器难以快速解决组合优化问题。量子退火处理器利用超导通量量子比特求解组合优化问题，具有卓越的精度和极快的求解速度。然而，量子退火处理器要求一个极低的工作环境，且消耗了高昂的成本。这些缺点限制了其在实际中的使用。随着半导体制造技术的发展，基于CMOS工艺的退火处理器被开发出来以克服上述问题。这类处理器采用SRAM单元存储自旋状态，利用逻辑电路实现自旋之间的相互作用，使用随机数产生器跳出局部极小值。与通用CPU和量子退火处理器相比，这类处理器在执行速度、成本和功耗方面有了很大的改善且在室温下就能工作。然而，当前大多数CMOS退火处理器仅仅支持自旋的稀疏互联，如格图、国王图和六方图等,这极大地限制了它们能解决的组合优化问题的种类。虽然目前已经开发出的几个支持全连接自旋的CMOS退火处理器能够求解很多组合优化问题，如旅行商问题和最大割问题等，但这些处理器消耗了大量的资源且仅仅实现了少量的全连接自旋，并且在每一迭代步中最多只能选择一个自旋进行状态更新。它们仅仅能够求解小规模的组合优化问题，且扩展性低、收敛速度慢、并行处理能力低。总的来说，对于一种拥有高拓展性、高收敛速度和高并行度，支持大规模全连接自旋且并行更新状态的退火处理架构，目前仍没有较好的设计方案。

发明内容

[0003] 本发明目的在于提供一种基于片上网络的大规模全连接伊辛模型退火处理电路，以解决上述现有技术存在的问题。

[0004] 本发明中所述一种基于片上网络的大规模全连接伊辛模型退火处理电路，包括：全局控制器、控制总线、自旋处理阵列及合并路由器阵列；所述全局控制器对所有自旋处理单元进行并行控制；所有自旋处理单元共享退火温度和随机数，并通过所述合并路由器阵列进行通讯传递和计算。

[0005] 所述全局控制器包括I/O模块、控制逻辑模块、温度调度模块和随机数发生模块；所述I/O模块，负责在用户和处理电路之间交换信息；所述控制逻辑模块负责产生相应的控制信号；所述温度调度模块和随机数发生模块分别负责产生退火温度和随机数；所述控制总线将控制信号、退火温度和随机数发送给所有的自旋处理单元。

[0006] 所述自旋处理阵列包括多个自旋处理单元，每个自旋处理单元再包含256个自旋，每次处理更新一个自旋。

[0007] 自旋处理单元包括一个控制单元、一个状态更新单元和一个生产单元；

[0008] 所述控制单元包括控制逻辑和计数器；所述控制逻辑用于接收全局控制器的指令、相应地产生本自旋处理单元内所有计算元件之间的控制信号；所述计数器用于记录256个自旋中状态为‑1的自旋数量；

[0009] 所述状态更新单元由一个部分和数寄存器、一个 寄存器、一个 寄存器、一个绝对值器、三个加法器、一个比较器、一个乘法器和一个翻转器组成；所述绝对值器和加法器用于接收和累加相关系数 ，并将累加结果存于 寄存器中；所述部分和数寄存器和寄存器用于寄存基本部分和数量和累加得到的 ；所述比较器用于比较 和 ，决定是否更新本自旋处理单元所处理的单个自旋，若符合更新条件则选择 进一步更新自旋状态，否则状态保持不变；

[0010] 所述生产单元由七级流水线组成，包括一个访问控制器、16个J存储器、一个h存储器、16个σ存储器、16个比较器、多个加法器、多个多路复用器和多个非门，用于产生 的基本部分和 和 中的系数 ，并发送到其它自旋处理单元；所述访问控制器用于专门控制存储或读出相互作用系数 和外磁系数 ；所述第一级流水线之前，一次从16个J存储器中读出16个系数 ，启动16个比较器判断这些系数是否与所有被选择进行更新的自旋相关，若相关，则将其传送到第一级流水线；所述第二级流水线，由上一级传来的16个系数 和存储在σ存储器中的16个自旋 产生 的16个基本部分和 ，即当 时，直接传给下一级，当 时，激活非门对 进行按位取反，然后将结果传递到下一级；所述第三级流水线，通过具有 16 个输入的加法器树对基本部分和进行累加；所述第四级流水线，将外磁系数 添加到上一阶段的结果中；所述第五级流水线，将控制单元中计数器记录的 的数量与前一阶段的结果相加；所述第六级流水线，若累加的部分和与当前自旋处理单元中处理的自旋相关，则直接送入下一级流水线，否则，则等待其它240个部分和，并合并到下一级流水线；所述第七级流水线，将计算 的基本部分和 或 中的系数 ，打包成部分和或系数包，并转发给其它的自旋处理单元。

[0011] 所述合并路由器包括一个合并模块和一个路由模块，分别负责合并以及转发信息包。

[0012] 本发明中所述一种基于片上网络的大规模全连接伊辛模型退火处理电路，其优点在于：

[0013] （1）具有高收敛速度、高并行度，能够实现对全连接伊辛模型的高速、高并行退火处理。从算法设计层面到硬件实现层面都支持多自旋并发更新：算法上，动态多线程并行更新退火算法能够动态地调整线程数K和单个线程并行更新自旋数M，在有限的硬件资源下，加速收敛，并且通过回温策略保证精度；硬件上，通过片上网络架构实现并行更新，实现算法功能。

[0014] （2）具有高拓展性，每个自旋处理单元能够处理256个自旋，仅需增加自旋处理单元的数量，就能够处理更大规模的组合优化问题。

[0015] （3）设计复杂度低、硬件资源成本低，对电路中的结构采用专门设计：全局控制器中，采用乘法器计算温度倒数避免了高成本除法器的使用，同时所有自旋处理单元共享温度和随机数，极大地降低了硬件成本与功耗。自旋处理阵列中，采用分布式存储、近内存计算结构，简化了自旋处理单元的结构，降低了通信流量负载，减轻了计算复杂度，提高了计算效率。同时自旋处理单元使用了全流水线结构，结合了独特的乘法累加操作，采用一个附有计数器的加法器替代十六个加法器，大大降了了硬件开销。合并路由器采用合并、偏转方案和全流水线设计，能够将多个部分和数据包合并为一个，减少通信流量负载和每次迭代消耗的计算时间，且简化了设计复杂性。

附图说明

[0016] 图1是本发明中所述大规模全连接伊辛模型退火处理电路的整体架构示意图。

[0017] 图2是本发明中所述全局控制器的工作状态示意图。

[0018] 图3是本发明中所述全局控制器的结构示意图。

[0019] 图4为本发明中所述自旋处理单元的结构示意图。

[0020] 图5为本发明中所述合并路由器的示意图。

具体实施方式

[0021] 如图1所示，本发明中所述一种基于片上网络的大规模全连接伊辛模型退火处理电路，包括一个全局控制器、控制总线、自旋处理阵列、合并路由器阵列。

[0022] 动态多线程并行更新退火算法，采用 ，，判断是否满足更新条件，根据系
统反馈及 进行线程动态调整，并且在最后阶段进行回温操作。其中N为自旋总数、V为总并行更新自旋数；K为线程数、M为单个线程并行更新自旋数，均为整数。

[0023] 所述全局控制器由四个模块组成，包括I/O模块、控制逻辑模块、温度调度模块和随机数发生模块。所述I/O模块，负责在用户和处理电路之间交换信息。所述控制逻辑模块负责产生相应的控制信号。所述温度调度模块和随机数发生模块分别负责产生退火温度和随机数。所述控制总线将控制信号、退火温度和随机数发送给所有的自旋处理单元。

[0024] 如图2所示，所述全局控制器共包含五种工作状态，即空闲状态、S1静态参数配置状态、S2动态参数配置状态、S3迭代状态、S4结果返回状态。在空闲状态下，即所有组件都处于待命状态，当接收到用户的启动信号时，将空闲状态切换到静态参数配置状态。在静止参数配置状态下，可以将初始退火温度值、温度衰减因子、温度阈值、连续迭代阈值、初始自旋状态和随机种子写入寄存器，然后切换到动态参数配置状态。在动态参数配置状态下，根据来自自旋处理阵列的反馈信号确定下一次迭代的线程数和基本退火温度值，并发送给所有的自旋处理单元，然后切换到迭代状态。在迭代状态下，所有的自旋处理单元被激活以计算自旋状态，若温度低于温度阈值，即计算任务完成，切换到结果返回状态，否则再次切换到动态参数配置状态。在结果返回状态下，将自旋的最终状态作为初始问题的解返回给用户。

[0025] 如图3所示，所述全局控制器中，通过监视器对来自用户的数据包进行识别，并将相关的静态参数存储在配置寄存器文件中，将其它参数传送到路由器。经一次迭代后，来自不同线程的翻转信号值被不同的计数器相加，累加结果保存在记录寄存器堆中，并且采用比较器阵列获取最大翻转的自旋数以选择相应线程。若连续多次迭代累加的结果为0，则通过左移操作增加线程数。线性反馈移位寄存器用于随机数的产生，决定自旋是否翻转。所述全局控制器中，提前计算温度倒数并发送给所有的自旋处理器，以乘法器取代除法器。所述全局控制器中，当退火温度过低，并且系统陷入局部最小值时，提高退火温度。

[0026] 所述自旋处理阵列用于并行更新自旋的状态。所述自旋处理阵列包括多个自旋处理单元，每个自旋处理单元再包含256个自旋，每次处理更新一个自旋。如图4所示，自旋处理单元包括一个控制单元、一个状态更新单元和一个生产单元。所述控制单元包括控制逻辑和计数器。所述控制逻辑用于接收全局控制器的指令、相应地产生本自旋处理单元内所有计算元件之间的控制信号。所述计数器用于记录256个自旋中状态为‑1的自旋数量。所述状态更新单元由一个部分和数寄存器、一个 寄存器、一个 寄存器、一个绝对值器、三个加法器、一个比较器、一个乘法器和一个翻转器组成。所述绝对值器和加法器用于接收和累加相关系数 ，并将累加结果存于 寄存器中。所述部分和数寄存器和 寄存器用于寄存基本部分和数量和累加得到的 。所述比较器用于比较 和 ，决定是否更新本自旋处理单元所处理的单个自旋，若符合更新条件则选择 进一步更新自旋状态，否则状态保持不变。

[0027] 所述生产单元由七级流水线组成，包括一个访问控制器、16个J存储器、一个h存储器、16个σ存储器、16个比较器、多个加法器、多个多路复用器和多个非门，用于产生 的基本部分和 和 中的系数 ，并发送到其它自旋处理单元。所述访问控制器用于专门控制存储或读出相互作用系数 和外磁系数 。所述第一级流水线之前，一次从16个J存储器中读出16个系数 ，启动16个比较器判断这些系数是否与所有被选择进行更新的自旋相关，若相关，则将其传送到第一级流水线。所述第二级流水线，由上一级传来的16个系数 和存储在σ存储器中的16个自旋 产生 的16个基本部分和 ，即当 时，直接传给下一级，当 时，激活非门对 进行按位取反，然后将结果传递到下一级。所述第三级流水线，通过具有 16 个输入的加法器树对基本部分和进行累加。所述第四级流水线，将外磁系数 添加到上一阶段的结果中。所述第五级流水线，将控制单元中计数器记录的 的数量与前一阶段的结果相加。所述第六级流水线，若累加的部分和与当前自旋处理单元中处理的自旋相关，则直接送入下一级流水线，否则，则等待其它240个部分和，并合并到下一级流水线。所述第七级流水线，将计算 的基本部分和 或 中的系数 ，打包成部分和或系数包，并转发给其它的自旋处理单元。

[0028] 如图5所示，所述合并路由器阵列提供通信链路，以支持不同的自旋处理单元之间的数据包交换，并且能够将多个部分和数据包合并成一个。所述合并路由器主要包含合并阶段和路由阶段，由东、南、西、北四个输入端口及相应的四个输出端口、六个比较器、六个选择器、三个加法器、四个寄存器组、一个弹出器、一个交叉开关、一个仲裁器组成。所述合并阶段，六个比较器会先比较经输入端接收的数据包的类型和目的地，若符合合并条件则将这些数据包通过加法器合并成一个数据包。所述路由阶段，通过弹出器、交叉开关和仲裁器经输出端口将数据包发送给当前自旋处理单元或其它路由器。

[0029] 对于本领域的技术人员来说，可根据以上描述的技术方案以及构思，做出其它各种相应的改变以及形变，而所有的这些改变以及形变都应该属于本发明权利要求的保护范围之内。