计算机可读记录介质、数据处理装置和数据处理方法与流程

1.本文中讨论的实施方式涉及存储数据处理程序的非暂态计算机可读存储介质、数据处理装置和数据处理方法。


背景技术：

2.数据处理装置可以用于求解组合优化问题。数据处理装置将组合优化问题转换为伊辛模型(ising model)的能量函数，伊辛模型是表示磁体的自旋行为的模型，并且在能量函数中包括的状态变量的值的组合中搜索使能量函数的值最小化的组合。使能量函数的值最小化的状态变量的值的组合对应于由一组状态变量的值表示的最优解或基态。注意，在下文中，能量函数的值可以被称为能量。
3.用于在可行时间获得针对组合优化问题的近似解的方法的示例包括基于马尔可夫链蒙特卡罗(mcmc)方法的模拟退火(sa)方法或副本交换方法。
4.为了有效地求解组合优化问题(搜索解)，考虑增加解搜索处理的并行性。例如，提出了一种数据处理装置，在用于确定其值被更新的状态变量的一次试验(一个蒙特卡罗步骤的处理)中，基于由多个状态变量的更新引起的能量变化量来并行确定是否允许每个状态变量的更新。
5.然而，即使当多个状态变量的能量变化量的计算和确定处理被并行地执行并且允许大量状态变量的更新时，基于用于根据mcmc方法使伊辛型能量函数最小化的原理，在每个试验中更新的状态变量的数量为一。因此，当问题规模增大时，存在不必要的计算增大并且算术运算量增大的可能性。
6.为了减少算术运算量的浪费，已经提出了一种方法，用于将组合优化问题划分成多个子问题，并且并行地对各个子问题执行上述试验(在下文中，称为部分并行试验)。
7.相关技术的示例包括日本公开特许公报第2020-46997号、日本公开特许公报第2021-33341号和日本公开特许公报第2021-131695号。


技术实现要素：

8.技术问题
9.在部分并行试验中，取决于并行执行其试验的状态变量的数量(在下文中，可以称为并行试验位数)，存在不能实现足够的求解性能的可能性。例如，根据问题，在并行试验位数减少的情况下，存在被允许更新的状态变量的数量太小的情况，当能量被最小化时，难以选择适当的状态变量作为更新目标，并且适当的状态转变变得不太可能发生。
10.在一个方面，本实施方式的目的是提供可以改善求解组合优化问题的性能的程序、数据处理装置和数据处理方法。
11.问题的解决方案
12.根据实施方式的一方面，提供了一种存储数据处理程序的非暂态计算机可读记录介质，该数据处理程序用于使搜索由包括多个状态变量的能量函数表示的组合优化问题的
解的计算机执行以下处理，所述处理包括：通过执行以下操作执行搜索解的搜索处理：针对从多个状态变量中选择的多个第一状态变量，并行确定是否接受多个第一状态变量的每个值的改变，并且在改变多个选择的第一状态变量时执行改变其值的改变被确定为被接受的一个状态变量的值的处理；以及基于搜索处理的搜索状态或指示另一组合优化问题的搜索记录的搜索信息来指定多个选择的第一状态变量的数量，并且重复该搜索处理。
13.发明的有益效果
14.在一个方面，该实施方式可以改善求解组合优化问题的性能。
附图说明
15.图1是用于说明根据第一实施方式的数据处理装置的图；
16.图2是示出根据第二实施方式的数据处理装置的硬件示例的图；
17.图3是示出数据处理装置的功能示例的图；
18.图4是示出模块处理单元的示例的图；
19.图5是示出由模块处理单元进行的局部字段更新的功能示例的图；
20.图6是示出根据所确定的组配置处理副本的第一示例的图；
21.图7是示出根据所确定的组配置处理副本的第二示例的图；
22.图8是示出流水线处理的示例的图；
23.图9是示出读取加权系数的示例的图；
24.图10是示出数据处理装置的处理过程的示例的流程图；
25.图11是示出用于收集和记录搜索信息的过程的示例的流程图；
26.图12是示出用于确定并行试验位数p的处理过程的第一示例的流程图；
27.图13是示出用于确定并行试验位数p的处理过程的第二示例的流程图；
28.图14是示出用于确定并行试验位数p的处理过程的第三示例的流程图；以及
29.图15是示出四个组的并行处理过程的示例的流程图。
具体实施方式
30.在下文中，将参照附图描述用于执行实施方式的模式。
31.[第一实施方式]
[0032]
将描述第一实施方式。
[0033]
图1是用于说明根据第一实施方式的数据处理装置的图。
[0034]
数据处理装置10通过使用mcmc方法搜索组合优化问题的解，并且输出所搜索到的解。例如，数据处理装置10使用基于mcmc方法的sa方法、副本交换方法等来搜索解。数据处理装置10包括存储单元11和处理单元12。
[0035]
存储单元11可以是诸如随机存取存储器(ram)的易失性存储装置，或者可以是诸如闪存存储器的非易失性存储装置。存储单元11可以包括诸如寄存器的电子电路。处理单元12可以是诸如中央处理单元(cpu)、数字信号处理器(dsp)、专用集成电路(asic)、现场可编程门阵列(fpga)或图形处理单元(gpu)的电子电路。处理单元12可以是执行程序的处理器。“处理器”可以包括一组多个处理器(多处理器)。
[0036]
例如，组合优化问题由伊辛型能量函数公式化，并且被使能量函数的值最小化的
问题代替。能量函数可以称为目标函数、评估函数等。能量函数包括多个状态变量。状态变量是取值为0或1的二进制变量。状态变量可以被表达为位。组合优化问题的解由多个状态变量的值(在下文中，可以称为状态向量)来表示。使能量函数的值最小化的解表示伊辛模型的基态并且对应于组合优化问题的最优解。能量函数的值被表达为能量。
[0037]
伊辛型能量函数由公式(1)表示。
[0038]
[表达式1]
[0039][0040]
状态向量x具有多个状态变量作为元素，并且表示伊辛模型的状态。公式(1)是以二次无约束二进制优化(qubo)格式公式化的能量函数。注意，在使能量最大化的问题的情况下，使能量函数的符号反转就足够了。
[0041]
公式(1)右侧的第一项是针对可以从所有状态变量中选择的两个状态变量的所有组合，在不遗漏和重复的情况下对两个状态变量的值与加权系数的乘积进行积分。下标i和下标j是状态变量的索引。第i个状态变量由xi指示。第j个状态变量由xj指示。标记w
ij
指示第i个状态变量与第j个状态变量之间的权重，或者指示耦合强度的加权系数。满足w
ij
＝w
ji
和w
ii
＝0。
[0042]
公式(1)右侧的第二项是获得所有状态变量的相应偏差与状态变量的值的积的总和。第i个状态变量的偏差由bi指示。包括能量函数中包括的加权系数、偏差等的问题信息被存储在存储单元11中。
[0043]
当状态变量xi的值变为1-xi时，状态变量xi的增量可以表示为δxi＝(1-xi)-xi＝1-2xi。因此，关于能量函数e(x)，由于状态变量xi的变化引起的能量变化量δei由公式(2)表示。
[0044]
[表达式2]
[0045][0046]
标记hi被称为局部字段并且由公式(3)表示。局部字段可以被称为局部字段(lf)。
[0047]
[表达式3]
[0048][0049]
当状态变量xj改变时局部字段hi的改变量δh
i(j)
由公式(4)表示。
[0050]
[表达式4]
[0051][0052]
存储单元11保存与多个状态变量中的每一个相对应的局部字段hi。当状态变量xj的值改变时，处理单元12通过将改变量δh
i(j)
添加至hi来获得与位反转之后的状态相对应的hi。
[0053]
处理单元12使用metropolis(梅特罗波利斯)方法或gibbs(吉布斯)方法来确定是
否接受其中能量变化量变为δei的状态转变，例如搜索解中状态变量xi的值的变化。例如，在用于搜索从某一状态到能量低于该某一状态中的能量的另一状态的转变的相邻搜索中，处理单元12在概率上不仅接受转变到能量降低的状态，而且接受转变到能量增加的状态。例如，接受导致δe的状态变量的值的变化的概率a由公式(5)表示。
[0054]
[表达式5]
[0055][0056]
标记β指示指示温度的参数t(t》0)的倒数(β＝1/t)，并且被称为逆温度。min运算符指示取自变量的最小值。公式(5)的右上侧对应于metropolis方法。公式(5)的右下侧对应于gibbs方法。处理单元12将a与均匀随机数u(关于某个索引i，0《u《1成立)进行比较，并且当u《a成立时，接受状态变量xi的值的改变并且改变状态变量xi的值。当u《a不成立时，处理单元12不接受状态变量xi的值的改变并且不改变状态变量xi的值。根据公式(5)，δe的值越大，a变得越小。另外，当β越小，例如t越大，越容易允许δe大的状态转变。例如，在使用metropolis方法的情况下，处理单元12可以通过使用作为公式(5)的修改的公式(6)来进行转变确定。
[0057]
[表达式6]
[0058]
ln(u)
×
t≤-δe
ꢀꢀꢀꢀ
(6)
[0059]
例如，在对于均匀随机数u(0《u≤1)而言δe满足公式(6)的情况下，处理单元12接受状态变量的值的改变。在对于均匀随机数u而言δe不满足公式(6)的情况下，处理单元12不接受状态变量的值的改变。
[0060]
在根据第一实施方式的数据处理装置10中，处理单元12通过针对并行试验位数的部分并行试验来确定其值被改变的状态变量(在下文中，称为要更新的状态变量)。此外，处理单元12具有用于改变并行试验位数的功能。
[0061]
图1示出了由处理单元12执行的处理的一部分的流程。
[0062]
(s1)首先，处理单元12例如使用并行试验位数p1执行搜索处理。
[0063]
在将包括在能量函数中的状态变量的数量假设为n时，在步骤s1中的处理中，处理单元12针对从x1至xn中选择的p1个状态变量，并行确定是否接受变量的值的变化(包括δe计算处理)。此外，处理单元12改变要更新的状态变量的值，该要更新的状态变量是通过上述对p1个状态变量的确定来确定接受其值的改变的状态变量(在下文中，称为更新候选状态变量)中的一个。在存在多个更新候选状态变量的情况下，随机地或根据预定规则选择一个状态变量作为要更新的状态变量。
[0064]
注意，如果更新候选状态变量的数量经常为零，则不会发生状态转变，并且浪费了计算时间。因此，处理单元12可以在每个部分并行试验中恒定地改变p1个状态变量中的一个状态变量的值。以下将该方法称为无拒绝方法。
[0065]
在使用无拒绝方法的情况下，处理单元12足以为属于p1个状态变量的每个状态变量xi生成均匀随机数u[i]，并且足以选择使max(0,δei)+tlog(-log(u[i]))最小化的xi作为更新目标。注意，max运算符指示取自变量的最大值。例如，在更新候选状态变量的数量为零的情况下，处理单元12可以根据无拒绝方法选择要更新的一个状态变量。
[0066]
处理单元12在改变所选择的p1个状态变量时执行上述处理以搜索解。在图1的示例中，x1至xn中的每一个被划分为区域(在图1中表示为并行试验区域)a1至an，每个区域包括p1个状态变量。例如，从区域a1至区域an顺序地执行搜索。注意，每个区域可以包括相同的状态变量。此外，在已经执行搜索直到区域an之后，可以从区域a1再次执行搜索。
[0067]
(s2)例如，在上述搜索处理被执行预定时段的情况下，处理单元12基于指示步骤s1中的搜索处理的搜索状态的搜索信息，将要在部分并行试验中选择的状态变量的数量(并行试验位数)从p1改变为p2。
[0068]
指示搜索状态的搜索信息例如可以是通过预定时段的搜索处理获得的更新候选状态变量的数量的累积值，或者可以是其值已经实际改变的状态变量的数量的累积值。此外，搜索信息可以是由一组x1至xn表示的状态向量的移动量(由汉明距离表示)，无论在预定时段的搜索处理中是否更新能量的最小值(或更新次数)等。注意，处理单元12可以通过基于搜索信息指定适当的并行试验位数来执行搜索，该搜索信息是关于在过去执行的用于搜索另一组合优化问题的处理中的搜索中的并行试验位数的记录。
[0069]
在步骤s1的搜索处理时，上述搜索信息存储在存储单元11中。
[0070]
例如，在步骤s2的处理中，处理单元12根据通过预定时段的搜索处理获得的更新候选状态变量的数量的累积值来计算每个部分并行试验中的更新候选状态变量的数量的平均值。然后，例如，如果平均值小于第一阈值，则处理单元12将p1改变为大于p1的p2。在更新候选状态变量的数量小的情况下，当能量最小化时，难以选择适当的状态变量作为更新目标，并且存在求解性能恶化的可能性。因此，为了促进适当的状态转变并且改善求解性能，如上所述增加了并行试验位数。如果上述平均值大于第二阈值(》第一阈值)，则处理单元12将p1改变为小于p1的p2。这是因为，即使更新候选状态变量的数量太大，也选择要更新的一个状态变量，并且因此，不必要的计算增加，并且算术运算量增加。
[0071]
稍后将描述用于在使用其他搜索信息的情况下调整并行试验位数的方法的示例(参照图13和图14)。
[0072]
(s3)在改变并行试验位数之后，处理单元12使用并行试验位数p2执行搜索处理。步骤s3中的处理与上述步骤s1中的处理类似地执行。在图1的示例中，示出了包括关于x1至xn的p2个状态变量的区域b1至bm的数量为m(《n)的示例。例如，从区域b1至区域bm顺序地执行搜索。注意，每个区域可以包括相同的状态变量。此外，在已经执行搜索直到区域bm之后，可以从区域b1再次执行搜索。
[0073]
在步骤s3中的搜索处理被执行预定时段的情况下，处理单元12可以基于指示步骤s3中的搜索处理的搜索状态的搜索信息来执行步骤s2中的处理，进一步改变并行试验位数，并且重复搜索处理。
[0074]
注意，处理单元12可以使用分别指示多个状态变量的多个副本并行地执行针对多个副本的上述搜索处理。注意，将在第二实施方式中描述使用多个副本的搜索处理的示例。
[0075]
在步骤s1和s3中的处理中执行sa方法的情况下，例如每当部分并行试验重复预定次数时，处理单元12根据预定温度参数变化时间表减小作为指示温度的参数的t的值。然后，处理单元12输出例如在部分并行试验重复预定次数的情况下获得的状态向量作为组合优化问题的计算结果(例如，可以在未示出的显示装置上显示)。注意，每当状态变量的值改变时，处理单元12可以更新由公式(1)表示的能量函数(能量)的值，并且可以使存储单元11
保存直到该点最小能量情况下的能量和状态。在这种情况下，例如，处理单元12可以输出与在部分并行试验重复预定次数之后存储的最小能量相对应的状态作为计算结果。
[0076]
在处理单元12执行副本交换方法的情况下，处理单元12针对分别被设置t的不同值的多个副本中的每一个执行上述步骤s1至s3中的处理。注意，尽管稍后将描述特定示例，但是可以将相同的并行试验位数设置至每个副本，或者可以将不同的并行试验位数分别设置至多个副本。每当部分并行试验重复预定次数时，处理单元12交换副本。例如，处理单元12选择具有相邻t值的两个副本，并且基于副本之间的能量差或t值差以预定交换概率交换所选择的两个副本之间的t值或状态。例如，每当改变针对每个副本的状态变量的值时，处理单元12更新能量函数(能量)的值，并且将直到该点最小能量情况下的能量和状态存储在存储单元11中。然后，例如，处理单元12输出在上述部分并行试验在每个副本中重复预定次数之后存储的最小能量中的与所有副本中的最小能量相对应的状态作为计算结果。
[0077]
根据上述第一实施方式的数据处理装置10基于搜索信息改变部分并行试验的并行试验位数(用于并行确定是否接受值变化的状态变量的数量)。因此，可以根据反映问题的特性的搜索状态来设置并行试验位数，并且优化用于改变一个状态变量的值的算术运算量，并且可以改善大规模问题的求解性能。
[0078]
此外，除了算术运算量的优化之外，通过如上所述改变并行试验位数，在一个状态变量的值改变的情况下，可以调整在状态变量变成接下来接受值的改变的状态变量(作为更新候选)之前的时段。因此，可以避免当状态通过改变状态变量的值而从局部解中逃离时，状态变量的值再次改变并且状态再次被约束至局部解的情况。
[0079]
[第二实施方式]
[0080]
接下来，将描述第二实施方式。
[0081]
图2是根据第二实施方式的数据处理装置的硬件示例。
[0082]
数据处理装置20是使用mcmc方法搜索组合优化问题的解并且输出所搜索到的解的计算机。数据处理装置20包括cpu 21、ram 22、硬盘驱动器(hdd)23、gpu 24、输入接口25、介质读取器26、网络接口卡(nic)27和加速器卡28。
[0083]
cpu 21是执行程序命令的处理器。cpu 21将存储在hdd 23中的程序和数据中的至少一部分加载至ram 22中以执行程序。注意，cpu 21可以包括多个处理器核。此外，数据处理装置20可以包括多个处理器。可以通过使用多个处理器或处理器核并行执行以下描述的处理。此外，多个处理器的集可以被称为“多处理器”或简称为“处理器”。
[0084]
ram 22是暂时存储由cpu 21执行的程序和由cpu 21使用的用于算术操作的数据的易失性半导体存储器。注意，数据处理装置20可以包括与ram不同类型的存储器，或者可以包括多个存储器。
[0085]
hdd 23是存储诸如操作系统(os)、中间件或应用软件的软件和数据的非易失性存储装置。注意，数据处理装置20可以包括诸如闪存存储器或固态驱动器(ssd)的另一类型的存储装置，或者可以包括多个非易失性存储装置。
[0086]
gpu 24根据来自cpu 21的命令向连接至数据处理装置20的显示器101输出图像。可以使用任何类型的显示器例如阴极射线管(crt)显示器、液晶显示器(lcd)、等离子体显示器或有机电致发光(oel)显示器作为显示器101。
[0087]
输入接口25从连接至数据处理装置20的输入装置102获取输入信号，并且将输入
信号输出至cpu 21。可以使用定点装置(例如鼠标、触摸面板、触摸板或轨迹球)、键盘、遥控器、按钮开关等作为输入装置102。此外，可以将多种类型的输入装置连接至数据处理装置20。
[0088]
介质读取器26是读取记录在记录介质103上的程序和数据的读取装置。可以使用例如磁盘、光盘、磁光盘(mo)、半导体存储器等作为记录介质103。磁盘包括软磁盘(fd)和hdd。光盘包括致密盘(cd)和数字通用盘(dvd)。
[0089]
介质读取器26例如将从记录介质103读取的程序或数据复制到另一记录介质例如ram 22或hdd 23。通过例如cpu 21执行读取的程序。注意，记录介质103可以是便携式记录介质，并且可以用于程序和数据的分发。此外，可以将记录介质103和hdd 23称为计算机可读记录介质。
[0090]
nic 27是连接至网络104并且经由网络104与另一计算机通信的接口。例如，nic 27通过电缆连接至诸如交换机或路由器的通信装置。nic27可以是无线通信接口。
[0091]
加速器卡28是通过使用mcmc方法搜索由公式(1)的伊辛型能量函数表示的问题的解的硬件加速器。通过在固定温度下执行mcmc方法或者执行其中在多个温度之间交换伊辛模型的状态的副本交换方法，加速器卡28可以用作采样器以在该温度下根据玻尔兹曼分布对状态进行采样。加速器卡28执行诸如副本交换方法和sa方法的退火处理，用于逐渐降低t值以求解组合优化问题。
[0092]
sa方法是通过在每个t值处根据玻尔兹曼分布对状态进行采样并且将用于采样的t从高温降低到低温(例如，增加逆温度β)来高效地找到最优解的方法。通过例如即使在β大的情况下也在低温侧在一定程度上改变状态，即使当t值快速下降时，也存在发现良好的解的增加的可能性。例如，在使用sa方法的情况下，加速器卡28在以固定t值重复状态转变的试验一定次数之后重复降低t值的操作。
[0093]
副本交换方法是用于通过使用多个t值来独立地执行mcmc方法，并且对于在各个t值处获得的状态适当地交换t值(或状态)的方法。通过在低温下通过mcmc搜索状态空间的窄范围并且在高温下通过mcmc搜索状态空间的宽范围，可以高效地找到好的解。例如，在使用副本交换方法的情况下，加速器卡28重复以下操作：在多个t值中的每一个t值处并行地执行状态转变的试验，并且每当执行一定数量的试验时，对于在各个t值处获得的状态以预定的交换概率交换t值。
[0094]
加速器卡28包括fpga 28a。fpga 28a实现加速器卡28的搜索功能。该搜索功能可以由另一类型的电子电路例如gpu或asic实现。fpga 28a包括存储器28b。存储器28b保存诸如用于由fpga 28a进行的搜索的问题信息、由fpga28a搜索的解、指示搜索状态的搜索信息等的数据。fpga28a可以包括多个存储器，包括存储器28b。
[0095]
fpga 28a是根据第一实施方式的处理单元12的示例。存储器28b是根据第一实施方式的存储单元11的示例。注意，加速器卡28可以包括fpga28a外部的ram，并且存储在存储器28b中的数据可以根据fpga28a的处理临时保存在ram中。
[0096]
可以将搜索伊辛形式的问题的解的硬件加速器例如加速器卡28称为伊辛机器、玻尔兹曼机器等。
[0097]
加速器卡28通过使用多个副本并行地执行解搜索。副本指示能量函数中包括的多个状态变量。在下面的描述中，将状态变量表达为位。包括在能量函数中的每个位与整数索
引相关联并且根据该索引来标识。
[0098]
图3是示出数据处理装置的功能示例的图。
[0099]
数据处理装置20包括整体控制单元30、m(m是等于或大于2的整数)个模块(可以称为电路单元)31a1、31a2、
……
、和31am、搜索信息聚集单元32和选择器33。使用fpga28a和存储器28b的电子电路来实现整体控制单元30、模块31a1至31am、搜索信息聚集单元32和选择器33。
[0100]
整体控制单元30控制模块31a1至31am、搜索信息聚集单元32和选择器33。此外，整体控制单元30接收由搜索信息聚集单元32收集的搜索信息，并且确定并行试验位数p。然后，整体控制单元30基于所确定的p确定稍后要描述的模块31a1至31am的组配置，并且将指示所确定的组配置的组配置信息提供给选择器33。
[0101]
此外，整体控制单元30基于从选择器33提供的每个组的翻转位索引来更新由存储单元保存的每个副本的状态向量。翻转位索引是要更新的位的索引(在下文中，称为翻转位)。
[0102]
此外，整体控制单元30可以通过将与索引相对应的δe添加至由保存与每个副本的当前状态向量相对应的能量的能量保存单元所保存的能量来更新每个副本的能量。注意，在图3中，省略了保存与每个副本相对应的当前状态向量的存储单元和保存与每个副本的当前状态向量相对应的能量的能量保存单元。存储单元和能量保存单元可以通过例如fpga28a中的存储器28b的存储区域来实现，或者可以通过寄存器来实现。
[0103]
此外，整体控制单元30向模块31a1至31am提供控制信息、组配置信息和关于翻转位的信息(在下文中，称为翻转位信息)。翻转位信息包括例如翻转位索引和翻转位的反转方向(指示从0至1的反转或从1至0的反转的信息)。
[0104]
模块31a1至31am分别包括模块控制单元31b1、31b2、
……
、和31bm以及模块处理单元31c1、31c2、
……
、和31cm。
[0105]
模块控制单元31b1至31bm从整体控制单元30接收控制信息、组配置信息和翻转位信息，并且控制模块31a1至31am中的流水线控制、用于更新每个副本的局部字段的处理等。
[0106]
模块31a1至31am基于并行试验位数p被适当地组合，并且被分组为n(n为等于或大于2的整数)个组。针对每个单位处理时段，针对多个副本中的每n个副本，各自包括一个或多个模块的n个组使用并行试验位数p执行部分并行试验。此外，模块处理单元31c1至31cm将指示搜索状态的搜索信息发送至搜索信息聚集单元32。稍后将描述模块处理单元31c1至31cm的示例。
[0107]
搜索信息聚集单元32收集搜索信息并且将所收集的搜索信息发送至整体控制单元30。
[0108]
选择器33基于从整体控制单元30接收的组配置信息改变选择器配置。然后，在每个组中包括多个更新候选位的索引(在下文中，称为翻转候选位)的情况下，选择器33为每个组并行选择一个。然后，选择器33输出所选择的索引作为翻转位索引，并且将所选择的索引提供给整体控制单元30。
[0109]
在下文中，将描述模块数量m＝8的情况。然而，该数量不限于此。
[0110]
图4是示出模块处理单元的示例的图。注意，在图4中，省略了图3所示的整体控制单元30、模块控制单元31b1至31bm以及搜索信息聚集单元32的图示。
[0111]
在图4的示例中，数据处理装置20包括模块处理单元31c1至31c8。
[0112]
模块处理单元31c1包括存储器单元40a、h计算单元40b1至40bk、δe计算单元40c1至40ck、选择器40d以及搜索信息获取单元40e。其他模块处理单元31c2至31c8具有类似的配置。例如，模块处理单元31c2包括存储器单元41a、h计算单元41bl至41bk、δe计算单元41cl至41ck、选择器41d以及搜索信息获取单元41e。模块处理单元31c3包括存储器单元42a、h计算单元42b1至42bk、δe计算单元42c1至42ck、选择器42d以及搜索信息获取单元42e。模块处理单元31c4包括存储器单元43a、h计算单元43b1至43bk、δe计算单元43c1至43ck、选择器43d以及搜索信息获取单元43e。模块处理单元31c5包括存储器单元44a、h计算单元44b1至44bk、δe计算单元44c1至44ck、选择器44d以及搜索信息获取单元44e。模块处理单元31c8包括存储器单元47a、h计算单元47b1至47bk、δe计算单元47c1至47ck、选择器47d以及搜索信息获取单元47e。标记k是由模块处理单元31c1至31c8中的每一个处理的位数。
[0113]
例如，存储器单元40a至47a由fpga28a中的包括存储器28b的多个存储器实现。h计算单元40b1至47bk、δe计算单元40c1至47ck、选择器40d至47d以及搜索信息获取单元40e至47e由fpga 28a的电子电路实现。
[0114]
在图4中，通过向h计算单元40b1至47bk添加下标n作为“hn”计算单元来表示名称，使得容易找到与第n位的对应关系。同样地，在图4中，通过向δe计算单元44c1至44ck添加下标n作为“δen”计算单元来表示名称，使得容易找到与第n位的对应关系。
[0115]
例如，h计算单元40b1和δe计算单元40c1关于n个位中的第一位执行算术运算。此外，h计算单元40bk和δe计算单元40ck关于第i位执行算术运算。
[0116]
如上所述，模块31a1至31am基于并行试验位数p被适当地组合和分组，并且对每个组中的某个副本执行部分并行试验。
[0117]
在图4的示例中，示出了模块31a1被分类为组a，模块31a2被分类为组b，模块31a3和31a4被分类为组c，以及模块31a5至31a8被分类为组d的情况。在这种情况下，在组a和b中的每一个中执行使用并行试验位数p＝k的部分并行试验，在组c中执行使用并行试验位数p＝k*2的部分并行试验，以及在组d中执行使用并行试验位数p＝k*4的部分并行试验。
[0118]
数据处理装置20通过n个组的n种类型的处理(流水线)对多个副本并行地执行部分并行试验，以使得可以有效地使用fpga 28a的算术运算资源。例如，在图4的示例的情况下，数据处理装置20以与组a至d相对应的四个流水线并行地处理多个副本。在本示例中，假设副本的数量为16。16个副本被表示为副本r0、副本r1、
……
、和副本r15。
[0119]
在此，将描述存储在存储器单元40a至47a中的信息。存储器单元40a至47a中的每一个存储关于自身组的位与另一位的每一对的加权系数w＝{w
γ,δ
}。当状态向量的位的数量为n时，加权系数的总数量为n2。满足w
γ,δ
＝w
δ,γ
。满足w
γ,γ
＝0。由于每个副本的处理是针对相同问题的处理，因此如果副本的数量增加，则要存储的加权系数的总数量不改变。
[0120]
在图4的示例中，存储器单元40a存储加权系数w
1,1
至w
1,n
、
……
、和w
i,1
至w
i,n
。例如，加权系数w
1,1
至w
1,n
用于与n个位中的第一位相对应的算术运算。存储在存储器单元40a中的加权系数的总数量为i*n。注意，在由模块处理单元31c1至31c8中的每一个处理的位的数量为k的情况下，i＝k。
[0121]
存储器单元41a存储加权系数w
i+1,1
至w
i+1,n
、
……
、以及w
j,1
至w
j,n
。存储器单元42a
存储加权系数w
j+1,1
至w
j+1,n
、
……
、以及w
k,1
至w
k,n
。存储器单元43a存储加权系数w
k+1,1
至w
k+1,n
、
……
、以及w
l,1
至w
l,n
。存储器单元44a存储加权系数w
l+1,1
至w
l+1,n
、
……
、以及w
m,1
至w
m,n
。存储器单元47a存储加权系数w
o+1,1
至w
o+1,n
，n、
……
、以及w
n,1
至w
n,n
。
[0122]
例如，其值被改变的位的索引从模块控制单元31b1至31bm被提供给存储器单元40a至47a。然后，从存储器单元40a至47a中读取与索引相对应的加权系数，并且将加权系数提供给h计算单元40b1至47bk。
[0123]
在如图4中的组的数量为4的情况下，最多四个索引同时被提供给存储单元40a至47a。因此，最多四个加权系数同时被提供给h计算单元40b1至47bk中的每一个。四个加权系数对应于四个副本。
[0124]
下面，将主要将与第一位相对应的h计算单元40b1和δe计算单元40c1作为示例进行描述。其他h计算单元和δe计算单元具有类似的功能。
[0125]
h计算单元40b1使用从存储单元40a读取的加权系数，基于公式(3)和(4)计算针对并行处理的四个副本中的每一个的局部字段h1。例如，h计算单元40b1包括用于保存在先前时间针对副本计算的局部字段h1的寄存器，并且通过将副本的δh1添加至h1来更新存储在副本中的副本的h1。注意，从模块控制单元31b1向h计算单元40b1提供指示针对每个副本要反转的由索引指示的位的反转方向的信号。h1的初始值是根据问题根据b1用公式(3)预先计算的，并且被预先设置至h计算单元40b1的寄存器。
[0126]
δe计算单元40c1使用由h计算单元40b1保存的接下来要处理的一个副本的局部字段h1，基于公式(2)，计算作为根据副本的自身位的反转的能量变化量的δe1。δe计算单元40c1例如可以根据副本的自身位的当前值来确定自身位的反转方向。例如，当自身位的当前值为0时，从0至1的方向是反转方向，而当自身位的当前值为1时，从1至0的方向是反转方向。δe计算单元40c1将计算出的δe1提供给选择器40d。
[0127]
选择器40d对从δe计算单元40c1至40ck同时提供的每个δe进行公式(6)中的确定，并且确定是否能够反转该位。例如，选择器40d针对由δe计算单元33a1计算出的能量变化δe1，基于公式(6)确定是否允许索引＝1的位的反转。例如，选择器40d根据-δe1与根据t的热噪声之间的比较来确定针对副本是否可以反转该位。热噪声对应于公式(6)中的均匀随机数u的自然对数值与t的乘积。
[0128]
此外，选择器40d根据公式(6)基于随机数随机地选择翻转候选位中的一个，并且将对应于所选择的位的索引提供给选择器33。注意，在没有被确定为可反转的位的情况下，选择器40d不需要输出索引。然而，在使用上述无拒绝方法的情况下，恒定地输出一个位的索引。
[0129]
选择器41d至47d针对由自身模块处理的位与选择器40d类似地工作。
[0130]
搜索信息获取单元40e获取模块31a1中的搜索信息。搜索信息获取单元40e获取例如从选择器40d输出的索引的数量(对应于翻转候选位的数量)作为搜索信息。搜索信息获取单元40e可以获取诸如每个副本中的翻转位的数量或能量变化量的信息作为搜索信息。
[0131]
搜索信息获取单元41e至47e具有与搜索信息获取单元40e类似的功能。
[0132]
在如上所述的模块31a1被分类为组a，模块31a2被分类为组b，模块31a3和31a4被分类为组c，并且模块31a5至31a8被分类为组d的情况下，选择器33的功能如下。
[0133]
由于组a包括一个模块31a1，因此选择器33具有用于输出从模块31a1的模块处理
单元31c1输出的索引的功能(被示出为“1-1选择”)。由于组b包括一个模块31a2，因此选择器33具有用于输出从模块31a2的模块处理单元31c2输出的索引的功能。组c包括两个模块31a3和31a4。因此，选择器33具有用于选择和输出从模块31a3和31a4的模块处理单元31c3和31c4中的任何一个输出的索引的功能(被示出为“2-1选择”)。组d包括四个模块31a5至31a8。因此，选择器33具有用于选择和输出从模块31a5至31a8的模块处理单元31c5至31c8中的任何一个输出的索引的功能(被示出为“4-1选择”)。
[0134]
选择器33基于随机数随机地选择多个索引中的一个。此外，选择器33可以基于例如从选择器40d至47d提供的选择权重信息来优先选择任何一个索引。作为选择权重信息，例如，可以使用翻转候选位的数量。在这种情况下，优先选择从具有大的翻转候选位的数量的模块处理单元输出的索引。此外，在选择器40d至47d使用无拒绝方法的情况下，与由选择器40d至47d选择的位相对应的值max(0,δei)+tlog(-log(u[i]))可以用作选择权重信息。在这种情况下，优先选择从max(0,δei)+tlog(-log(u[i]))的值减小的模块处理单元输出的索引。
[0135]
这样的选择器33可以例如通过使用具有使能的四个8输入1输出门电路来实现。在实现“1-1选择”的门电路中，八个输入中的一个输入由(例如，包括在从整体控制单元30提供的组配置信息中的)使能信号使能。在实现“2-1选择”的门电路中，八个输入中的两个输入由使能信号使能。在实现“4-1选择”的门电路中，八个输入中的四个输入由使能信号使能。然后，执行上述选择处理。
[0136]
图5是示出由模块处理单元进行的局部字段更新的功能示例的图。在图5中，示出了模块31a1的模块处理单元31c1中的局部字段更新的功能示例。其他模块处理单元31c2至31cm的局部字段更新的功能类似于模块处理单元31c1的局部字段更新的功能。
[0137]
存储器单元40a包括对应于模块数量m＝8的8个存储器40p1、40p2、
……
、和40p8。存储器40p1存储加权系数w
1,1
至w
1,i
、w
2,1
至w
2,i
、
……
、和w
i,1
至w
i,i
。存储器40p2存储w
1,i+1
至w
1,j
、w
2,i+1
至w
2,j
、
……
、和w
i,i+1
至w
i,j
。存储器40p8存储w
1,k+1
至w
1,n
、w
2,k+1
至w
2,n
、
……
、和w
i,k+1
至w
i,n
。
[0138]
h计算单元40b1至40bk中的每一个基于公式(3)和(4)，使用最多四个加权系数来并行地更新与最多四个副本的自身位相对应的局部字段。例如，h计算单元40b1包括h保存单元r1、选择器s10至s13以及加法器c1至c4。其他h计算单元具有与h计算单元40b1类似的功能。例如，h计算单元40bk包括h保存单元ri、选择器si0至si3以及加法器c5至c8。在下文中，将描述h计算单元40b1。
[0139]
h保存单元r1保存与16个副本中的每一个相对应的自身位的局部字段。h保存单元r1可以包括触发器，并且可以包括四个ram，每个ram每次读取1个字。h计算单元40b1中的自身位是索引＝1的位。
[0140]
选择器s10选择从存储器40p1至40p8读取的八个加权系数中的四个，并且将四个所选择的加权系数中的每一个提供给加法器c1至c4中的任何一个。例如，选择器s10可以使用具有使能的四个8输入1输出门电路来实现。在这样的门电路中，基于组配置信息，利用从模块控制单元31b1提供的使能信号来使能八个输入中的一个，并且输出使能的输入的加权系数。
[0141]
选择器s11从h保存单元r1读取每个组中要进行更新处理的副本的局部字段，并且
将局部字段提供给加法器c1至c4。由选择器s11从h保存单元r1同时读取的局部字段的最大数量为4。
[0142]
加法器c1至c4通过将从选择器s10输出的加权系数添加至关于在从选择器s11提供的四个组中处理的副本的局部字段来更新局部字段，并且将局部字段提供给选择器s12。如上所述，加权系数的符号可以例如根据指示从模块控制单元31b1提供的位的反转方向的信号来确定。
[0143]
选择器s12将由加法器c1至c4更新的副本的局部字段存储在h保存单元r1中。
[0144]
选择器s13从h保存单元r1读取模块31a1所属的组a中的接下来要处理的副本的自身位的局部字段，并且将该局部字段提供给δe计算单元40c1。
[0145]
以这种方式，针对最多四个副本，h计算单元40b1可以通过选择器s10至s12和加法器c1至c4同时更新对应于索引＝1的局部字段。
[0146]
利用上述配置，数据处理装置20针对16个副本并行执行最多4个流水线。
[0147]
接下来，将描述根据由整体控制单元30确定的组配置的副本处理的示例。注意，在以下示例中，假设一个流水线的级的数量例如级的数量为四。
[0148]
第一阶段是δe计算。δe计算是在每个组中针对属于该组的每个位并行计算δe的处理。
[0149]
第二阶段是翻转确定。翻转确定是针对并行计算的每个位的δe选择要反转的一个位的处理。
[0150]
第三阶段是w读取。w读取是从存储器单元40a至47a读取加权系数的处理。
[0151]
第四阶段是h更新。h更新是基于所读取的加权系数来更新副本的局部字段的处理。与h更新级并行地执行副本中要反转的位的反转。因此，也可以说h更新阶段是位更新阶段。
[0152]
注意，流水线的级的数量不限于4。
[0153]
此外，在下文中，其中执行针对流水线的一个级的处理的时段被称为一步时段。
[0154]
图6是示出根据所确定的组配置处理副本的第一示例的图。在图6中，m0至m7表示模块31a1至31a8。在随后的附图中，模块31a1至31a8被表示为m0至m7。
[0155]
在图6的示例中，首先，组合模块31a1至31a8中的两个。例如，模块31a1至31a8的组的数量为4。在这种情况下，在副本r0至r15中的四个中，每步时段并行执行使用并行试验位数p＝k*2的部分并行试验。
[0156]
数据处理装置20在每一级中在偏移四个步时段或等于或大于四个步时段的时间处开始副本的处理，使得在一个组中处理的副本的h更新之后在下一个组中执行相同副本的处理。因此，由于通过使用反映先前位更新的局部字段在每个副本中执行δe计算，因此观察到mcmc方法的顺序处理的原理。
[0157]
在图6的示例中，在偏移四步时段的时间处，在一个组中处理的副本在下一个组中被处理。
[0158]
接下来，在图6的示例中，配置在特定时间处改变为其中模块31a1至31a8中的四个被组合的配置。例如，模块31a1至31a8的组的数量从4变为2。在这种情况下，在副本r0至r15中的两个中，每步时段并行地执行使用并行试验位数p＝k*4的部分并行试验。此外，由于并行处理的副本的数量为2，因此数据处理装置20例如在完成在一个组中处理的副本的h更新
之后并且在下一个组中处理相同的副本之前改变步时段。在图6的示例中，当组的数量为4时，上述的步时段是4个步时段。然而，当组的数量为2时，上述的步时段改变为8个步时段。
[0159]
图7是示出根据所确定的组配置处理副本的第二示例的图。
[0160]
在图7的示例中，模块31a1至31a8(m0至m7)被划分为分别属于一个模块、一个模块、两个模块和四个模块的四个组。在图7的示例中，用四个并行试验位数p中的一个来执行每个副本的部分并行试验。由于使用一个模块来处理副本r0至r7，因此并行试验位数p为k。由于使用两个模块来处理副本r8至r11，因此并行试验位数p为k*2。由于使用四个模块来处理副本r12至r15，因此并行试验位数p为k*4。
[0161]
由于并行试验位数p中的这样的差异，对所有n个位执行试验的时段对于每个副本是变化的。通过对使用最小数量的模块处理的副本(在本示例中的副本r0至r7)中的所有位执行一次试验，在所有副本中对所有n个位执行一次试验。
[0162]
在图7的示例中，在一步时段中使用一个模块来处理副本r0至r7。在所有n个位被划分并且由副本r0至r7中的八个模块处理的情况下，其中对所有位执行一次试验的步时段是4(流水线的级的数量)*8(模块的数量)＝32个步时段。
[0163]
在这种情况下，如图7所示，整体控制单元30控制每个副本的处理被分配至的模块和每个模块的组配置，使得每个副本在32个步时段中完成针对所有n个位的至少一次试验。
[0164]
图8是示出流水线处理的示例的图。
[0165]
在图8的示例中，数据处理装置20在每一级中偏移四个步时段的时间处开始处理副本，使得在一个组中处理的副本的h更新之后，在下一个组中处理相同的副本。例如，副本r0的处理在每一级中偏移四个步时段的时间处开始，使得在模块31a8(m7)的组中的副本r0的h更新之后，在模块31a4(m3)的组中执行副本r0的处理。
[0166]
因此，由于通过使用反映先前位更新的局部字段在每个副本中执行δe计算，因此观察到mcmc方法的顺序处理的原理。
[0167]
在此，局部字段的更新需要反映在副本的所有位中。因此，对四个副本的所有位同时执行加权系数的读取。如图5所示，数据处理装置20将保存与每个组对应的加权系数的存储器划分成例如存储器40p1至40p8。因此，对应于多个副本的访问不集中在相同的存储器上。例如，在图8中具有星形的步时段中，加权系数的读取如下。
[0168]
图9是示出读取加权系数的示例的图。
[0169]
模块31a1至31a8(m0至m7)的存储器单元40a至47a中的每一个被划分为八个存储器。八个存储器中的每一个保存分配至自身模块的k个位和分配至模块31a1至31a8中的任何一个的k个位之间的加权系数。
[0170]
例如，在模块31a1的存储单元40a中，w0(m0)、w0(m1)、w0(m2)、w0(m3)、w0(m4)、w0(m5)、w0(m6)和w0(m7)被划分成八个存储器(图5中的存储器40p1至40p8)并且被保存。例如，w0(m0)是分配至模块31a1的k个位之间的加权系数。w0(m7)是分配至模块31a1的k个位与分配至模块31a8的k个位之间的加权系数。
[0171]
例如，在模块31a8的存储单元47a中，w7(m0)、w7(m1)、w7(m2)、w7(m3)、w7(m4)、w7(m5)、w7(m6)和w7(m7)被划分成八个存储器并且被保存。例如，w7(m0)是分配至模块31a8的k个位与分配至模块31a1的k个位之间的加权系数。w7(m7)是分配至模块31a8的k个位之间的加权系数。
[0172]
在如图4所示的组配置的情况下(在图9中组a至d表示为ga至gd)，w0(m0)至w7(m0)是当分配至组a的位被反转时用于每个模块的h更新的加权系数。此外，w0(m1)至w7(m1)是当分配至组b的位被反转时用于每个模块的h更新的加权系数。此外，w0(m2)至w7(m2)和w0(m3)至w7(m3)是在当分配至组c的位被反转时用于每个模块的h更新的加权系数。此外，w0(m4)至w7(m4)、w0(m5)至w7(m5)、w0(m6)至w7(m6)以及w0(m7)至w7(m7)是当分配至组d的位被反转时用于每个模块的h更新的加权系数。
[0173]
在图8中具有星形的步时段中，当由属于组a的模块31a1(m0)处理的副本r4的位被反转时，从保存w0(m0)至w7(m0)的存储器中的每一个读取加权系数。此外，当由属于组b的模块31a2(m1)处理的副本r0的位被反转时，从保存w0(m1)至w7(m1)的存储器中的每一个读取加权系数。
[0174]
此外，当由属于组c的模块31a3(m2)和31a4(m3)处理的副本r8的位被反转时，从保存w0(m2)至w7(m2)或w0(m3)至w7(m3)的存储器中的每一个读取加权系数。在所反转的位是分配至模块31a4的位的情况下，如图9所示，从保存w0(m3)至w7(m3)的存储器中的每一个读取加权系数。
[0175]
此外，当由属于组d的模块31a5(m4)至31a8(m7)处理的副本r12的位被反转时，从保存关于模块31a5(m4)至31a8(m7)中的任何一个的加权系数的每个存储器中读取加权系数。例如，从保存w0(m4)至w7(m4)、w0(m5)至w7(m5)、w0(m6)至w7(m6)或w0(m7)至w7(m7)中的任何一个的每个存储器读取加权系数。在所反转的位是分配至模块31a7的位的情况下，如图9所示，从保存w0(m6)至w7(m6)的存储器中的每一个读取加权系数。
[0176]
以这种方式，由于关于四个副本的处理是对分配至不同模块的位的处理，如果存储器如图9中那样以模块为单位划分，则在四个副本中的位反转时的存储器访问不集中在相同的存储器(相同的读取端口)上。因此，可以抑制由于作为瓶颈的h更新时的存储器访问而导致的计算时间的增加。
[0177]
注意，数据处理装置20确定在h更新时加权系数的值是否为零，不执行从存储器读取其值为零的加权系数，并且可以仅读取其值不为零的加权系数。因此，可以减少从存储器读取加权系数的次数。注意，在这种情况下，读取所需的周期数可以根据其值为零的加权系数相对于所有加权系数的比率而变化。然而，当周期数比预定阈值长时，数据处理装置20足以执行控制以使流水线停顿。
[0178]
接下来，将描述数据处理装置20的处理过程。首先，将描述针对一个副本的处理过程。
[0179]
图10是示出数据处理装置的处理过程的示例的流程图。
[0180]
(s20)fpga 28a的整体控制单元30执行初始设置。例如，初始设置包括并行试验位数p的初始值的设置，用于收集搜索信息的变量的初始化等。在下面的示例中，itrnum、csum、fsum、dsum、emin和eminupdate被用作用于收集搜索信息的变量。
[0181]
变量itrnum是表示迭代次数的变量。变量csum是表示翻转候选位的数量的累积值的变量。变量fsum是表示翻转位数的累积值的变量。变量emin是表示最小能量的变量。变量dsum是表示由汉明距离表示的状态向量的移动量(移动距离)的累积值的变量。
[0182]
在步骤s20的处理中，对itrnum＝0、csum＝0、fsum＝0和eminupdate＝0执行初始化。例如，将emin初始化为可以由数据处理装置20处理的最大值。
[0183]
注意，在步骤s20的处理中，例如，整体控制单元30可以将在cpu21的控制下提供给fpga 28a的问题信息(包括在能量函数中的加权系数、偏置等)设置至模块31a1至31am。
[0184]
(s21)整体控制单元30确定是否是改变并行试验位数p的时间。例如，确定对于每个预定时段(预定迭代次数)改变并行试验位数p的时间到来。在确定是改变时间的情况下，整体控制单元30进行至步骤s22的处理，而在确定不是改变时间的情况下，整体控制单元30进行至步骤s23的处理。
[0185]
(s22)整体控制单元30执行用于确定并行试验位数p的处理。稍后将描述步骤s22中的处理的示例。
[0186]
(s23)整体控制单元30将控制信息、组配置信息和翻转位信息提供给模块31a1至31am，并且使模块31a1至31am执行部分并行试验循环。此外，整体控制单元30基于所确定的p确定将在后面描述的模块31a1至31am的组配置，并且将指示所确定的组配置的组配置信息提供给选择器33。
[0187]
(s24)由一个或多个模块31a1至31am的组合执行使用并行试验位数p的部分并行试验。在步骤s24的处理中，对副本的p个位并行执行de计算和翻转确定。
[0188]
(s25)选择器33选择翻转位。在步骤s25的处理中，选择器33通过选择作为翻转确定的结果而获得的翻转候选位的索引中的一个来选择翻转位。将所选择的翻转位的索引(翻转位索引)提供给整体控制单元30。
[0189]
(s26)整体控制单元30更新保存在存储单元中的各个副本的状态向量的与提供给选择器33的翻转位索引相对应的位。此外，整体控制单元30将翻转位信息提供给模块31a1至31am。模块31a1至31am基于翻转位信息执行h更新。
[0190]
(s27)搜索信息聚集单元32收集和记录搜索信息。稍后将描述步骤s27中的处理的示例。
[0191]
(s28)模块31a1至31am重复步骤s24至s27中的处理，同时基于整体控制单元30的控制，偏移执行部分并行试验的区域，直到完成副本中的所有位(n个位)的试验。当完成副本中的所有位(n个位)的试验时，整体控制单元30进行至步骤s29中的处理。
[0192]
(s29)整体控制单元30确定是否结束搜索。在满足预定搜索结束条件的情况下，整体控制单元30确定结束搜索。例如，在迭代次数达到预定次数的情况下，整体控制单元30确定结束搜索。在确定结束搜索的情况下，fpga28a结束处理。在确定不结束搜索的情况下，重复从步骤s21的处理。
[0193]
注意，在执行sa方法的情况下，每当重复预定次数的部分并行试验时，fpga28a根据预定温度参数变化时间表减小t的值。在执行副本交换方法的情况下，每当部分并行试验重复预定次数时，fpga28a为多个副本中的每一个设置不同的t值并且执行副本交换。例如，fpga28a选择具有相邻t值的两个副本，并且基于副本之间的能量差或t值差以预定交换概率交换t值或状态。
[0194]
当处理结束时，fpga 28a将与最终获得的每个副本相对应的状态向量作为解输出至cpu 21。fpga 28a可以将与每个副本对应的能量与位状态向量一起输出至cpu 21。fpga 28a可以将通过搜索获得的解中具有最低能量的解作为最终解输出至cpu 21。cpu 21可以控制gpu 24并且使显示器101显示解。
[0195]
接下来，将描述用于由搜索信息聚集单元32收集和记录搜索信息的过程的示例。
[0196]
图11是示出用于收集和记录搜索信息的过程的示例的流程图。注意，搜索信息聚集单元32仅收集用于确定并行试验位数p的处理的搜索信息就足够了。然而，在图11中，示出了其中收集多种类型的搜索信息的示例。
[0197]
(s40)搜索信息聚集单元32使itrnum向上计数(+1)。
[0198]
(s41)搜索信息聚集单元32获取搜索信息。在该示例中，搜索信息聚集单元32获取翻转候选位的数量c、翻转的存在或不存在f(在包括翻转的情况下f＝1，在没有翻转的情况下f＝0)、当前状态向量statecur和当前能量ecur作为搜索信息。可以从模块31a1至31am获取翻转候选位的数量c，并且可以根据选择器33是否输出翻转索引来获取翻转的存在或不存在f。在当前状态向量statecur和当前能量ecur存储在存储器28b中的情况下，搜索信息聚集单元32从存储器28b获取statecur和ecur。
[0199]
(s42)搜索信息聚集单元32确定是否ecur《emin。在确定ecur《emin的情况下，搜索信息聚集单元32执行步骤s43中的处理，而在确定不满足ecur《emin的情况下，搜索信息聚集单元32执行步骤s44中的处理。
[0200]
(s43)搜索信息聚集单元32用ecur更新emin，并且使eminupdate向上计数(+1)。
[0201]
(s44)搜索信息聚集单元32确定是否是移动量获取时间。例如，在从先前的移动量获取时间起将itrnum增加预定次数的情况下，搜索信息聚集单元32确定是移动量获取时间。在确定是移动量获取时间的情况下，搜索信息聚集单元32执行步骤s45中的处理，而在确定不是移动量获取时间的情况下，搜索信息聚集单元32执行步骤s47中的处理。
[0202]
(s45)搜索信息聚集单元32计算参考状态向量与当前状态向量statecur之间的移动量(汉明距离)d。
[0203]
(s46)搜索信息聚集单元32更新参考状态向量。例如，参考状态向量被更新为statecur。
[0204]
(s47)搜索信息聚集单元32收集搜索信息。例如，搜索信息聚集单元32将c添加至csum，将f添加至fsum，并且将d添加至dsum，以更新csum、fsum和dsum。
[0205]
因此，搜索信息聚集单元32结束用于收集和记录搜索信息的一次处理。
[0206]
上述搜索信息的收集和记录可以针对每个副本执行，或者可以针对所有副本共同执行。
[0207]
接下来，将描述用于由整体控制单元30确定并行试验位数p的处理过程的示例。
[0208]
图12是示出用于确定并行试验位数p的处理过程的第一示例的流程图。
[0209]
(s50)整体控制单元30计算翻转候选位的数量的平均值cave。整体控制单元30通过将从搜索信息聚集单元32提供的csum除以itrnum(迭代次数)来计算cave。
[0210]
(s51)整体控制单元30确定是否cave》cthu且p》pthl。cthu是cave的第一阈值。pthl是并行试验位数p的下限值(例如k(由一个模块处理的位的数量))。在确定cave》cthu且p》pthl的情况下，整体控制单元30执行步骤s53的处理，而在确定不满足cave》cthu或不满足p》pthl的情况下，整体控制单元30执行步骤s52中的处理。
[0211]
(s52)整体控制单元30确定是否cave《cthl且p《pthu。cthl是cave的第二阈值，并且cthl《cthu。pthu是并行试验位数p的上限值(例如k*m(模块的数量))。在确定cave《cthl且p《pthu的情况下，整体控制单元30执行步骤s54中的处理，而在确定不满足cave《cthl或不满足p《pthu的情况下，整体控制单元30执行步骤s55中的处理。
[0212]
(s53)整体控制单元30设置p＝p-pdec以减少并行试验位数p。pdec是k的整数倍值并且是预定的。
[0213]
在cave太大的情况下，不必要的计算增加，并且算术运算量增加。因此，为了抑制算术运算量，整体控制单元30减少并行试验位数p。
[0214]
(s54)整体控制单元30设置p＝p+pinc，以便增加并行试验位数p。pinc是k的整数倍值并且是预定的。pinc可以是与pdec相同的值。
[0215]
在cave太小的情况下，难以选择适当的翻转候选位以便使能量最小化，并且存在求解性能恶化的可能性。因此，为了促进适当的状态转变并且改善求解性能，如上所述地增加并行试验位数p。
[0216]
(s55)整体控制单元30将确定的并行试验位数p设置至模块31a1至31am。
[0217]
(s56)整体控制单元30初始化用于收集搜索信息的变量，并且结束用于确定并行试验位数p的处理。在步骤s56的处理中，对itrnum＝0、csum＝0、fsum＝0、dsum＝0和eminupdate＝0执行初始化。
[0218]
图13是示出用于确定并行试验位数p的处理过程的第二示例的流程图。
[0219]
(s60)整体控制单元30计算指示预定时段中的翻转位出现率的翻转率frate。整体控制单元30通过将从搜索信息聚集单元32提供的fsum除以itrnum(迭代次数)来计算frate。
[0220]
(s61)整体控制单元30确定是否frate》fthu且p》pthl。fthu是frate的第一阈值。在确定frate》fthu且p》pthl的情况下，整体控制单元30执行步骤s63中的处理，而在确定不满足frate》fthu或不满足p》pthl的情况下，整体控制单元30执行步骤s62中的处理。
[0221]
(s62)整体控制单元30确定是否frate《fthl且p《pthu。fthl是frate的第二阈值，并且fthl《fthu。在确定frate《fthl且p《pthu的情况下，整体控制单元30执行步骤s64中的处理，而在确定不满足frate《fthl或不满足p《pthu的情况下，整体控制单元30执行步骤s65中的处理。
[0222]
(s63)整体控制单元30设置p＝p-pdec以减少并行试验位数p。在frate太大的情况下，发生太多状态转变，并且计算的收敛性恶化。因此，存在求解性能恶化的可能性。因此，整体控制单元30减少并行试验位数p，以减少frate的大小。
[0223]
(s64)整体控制单元30设置p＝p+pinc以增加并行试验位数p。在frate太小的情况下，很少发生状态转变。因此，存在求解性能恶化的可能性。因此，为了促进状态转变并且改善求解性能，如上所述地增加并行试验位数p。
[0224]
由于步骤s65和s66中的处理与图12所示的步骤s55和s56中的处理相同，因此省略其描述。
[0225]
图14是示出用于确定并行试验位数p的处理过程的第三示例的流程图。
[0226]
(s70)整体控制单元30计算移动量d的平均值dave。整体控制单元30通过将从搜索信息聚集单元32提供的dsum除以itrnum(迭代次数)来计算dave。
[0227]
(s71)整体控制单元30确定是否dave》dthu、emin未被更新且p》pthl。dthu是dave的第一阈值。在确定dave》dthu、emin未被更新且p》pthl的情况下，整体控制单元30执行步骤s73中的处理。在确定不满足dave》dthu、或emin被更新、或不满足p》pthl的情况下，整体控制单元30执行步骤s72中的处理。
[0228]
注意，emin是否被更新可以根据eminupdate是否是等于或大于1的值来确定。
[0229]
(s72)整体控制单元30确定是否dave《dthl、emin未被更新且p《pthu。dthl是frate的第二阈值，并且dthl《dthu。在确定dave《dthl、emin未被更新且p《pthu的情况下，整体控制单元30执行步骤s74中的处理。在确定不满足dave《dthl、或emin被更新、或不满足p《pthu的情况下，整体控制单元30执行步骤s75中的处理。
[0230]
(s73)整体控制单元30设置p＝p-pdec以减少并行试验位数p。在即使dave是大的也未更新emin的情况下，发生许多不必要的计算，并且存在求解性能恶化的可能性。因此，整体控制单元30减少并行试验位数p，以防止不必要计算的发生。
[0231]
(s74)整体控制单元30设置p＝p+pinc以增加并行试验位数p。在dave太小并且emin未被更新的情况下，由于搜索范围太窄，存在求解性能恶化的可能性。因此，为了扩大搜索范围并且改善求解性能，如上所述地增加并行试验位数p。
[0232]
由于步骤s75和s76中的处理与图12所示的步骤s55和s56中的处理相同，因此省略其描述。
[0233]
如上所述的用于确定并行试验位数p的处理可以基于关于每个副本的搜索信息的集合来执行，或者可以基于关于所有副本的搜索信息的集合来执行。
[0234]
此外，如上所述的三种类型的确定处理可以彼此组合。例如，将通过三种类型的确定处理确定的并行试验位数p设置至模块31a1至31am。
[0235]
注意，基于所确定的并行试验位数p的值，整体控制单元30可以执行调整以使每个副本中的p为相同值(参照图6)或者使每个副本中的p为特定比率(参照图7)。因此，提高了流水线处理的效率。
[0236]
接下来，将使用执行四个组的并行处理的情况作为示例来更具体地描述由数据处理装置20进行的处理过程。
[0237]
图15是示出四个组的并行处理的过程的示例的流程图。图15包括图10所示的过程中的步骤s23至s28中的处理的针对多个副本的更具体的示例。省略了用于确定并行试验位数p的处理、用于收集和记录搜索信息的处理等的说明。
[0238]
(s80)整体控制单元30执行初始设置。例如，初始设置包括并行试验位数p的初始值的设置和用于收集上述搜索信息的变量的初始化。此外，在使用多个副本的情况下，设置副本的数量、组的数量(在图15中的示例中为4)以及组之间的副本间隔。流水线的级的数量或等于或大于级的数量的值被设置为副本间隔(在上述图8中的示例中为4)。
[0239]
此外，在步骤s80中的处理中，首先，设置模块31a1至31am中的每一个被分配至的组以及由每个组处理的副本。例如，在上述图7所示的示例中，模块31a1至31a4(m0至m3)被分配至一个组，并且副本r12被分配至该组。此外，模块31a5和31a6(m4和m5)被分配至一个组，并且副本r8被分配至该组。此外，模块31a7(m6)被分配至一个组，并且副本r4被分配至该组。模块31a8(m7)被分配至一个组，并且副本r0被分配至该组。
[0240]
整体控制单元30可以将具有较高温度(作为表示设置温度较大的参数的t值)的副本分配至包括较小数量的模块的组，使得副本具有较小的并行试验位数p的初始值。
[0241]
在下文中，四个组被表示为g0至g3。
[0242]
(s81)模块31a1至31am执行循环处理，直到对每个副本中的所有位执行一次试验。
[0243]
(s82)整体控制单元30针对副本循环的每一轮设置模块或组至副本的分配。
[0244]
在上述图7所示的示例中，一步时段对应于一轮副本循环。对于每一轮副本循环，分配至每个模块的副本改变。然后，对于每四轮副本循环，向其分配相同副本的模块改变。例如，在第一轮中，副本r12被分配至模块31a1至31a4(m0至m3)，并且副本r8被分配至模块31a5和31a6(m4和m5)。此外，在第一轮中，副本r4被分配至模块31a7(m6)，并且副本r0被分配至模块31a8(m7)。四轮之后，副本r12被分配至模块31a5至31a8(m4至m7)，并且副本r8被分配至模块31a1和31a2(m0和m1)。此外，四轮之后，副本r4被分配至模块31a3(m2)，并且副本r0被分配至模块31a4(m3)。
[0245]
(s83a、s83b、s83c、s83d)由组g0至g3并行执行分配至相应的组g0至g3的副本的de计算。在模块的数量m＝8的情况下，由图4所示的δe计算单元41c1至47ck执行de计算。
[0246]
(s84a、s84b、s84c、s84d)由组g0至g3并行执行分配至相应的组g0至g3的副本的翻转确定。在模块的数量m＝8的情况下，由图4所示的选择器40d至47d执行翻转确定。
[0247]
(s85a、s85b、s85c、s85d)组g0至g3并行确定在由每个组处理的副本中是否发生翻转。模块31a1至31am的模块控制单元31b1至31bm基于从整体控制单元30提供的翻转位信息执行上述确定。
[0248]
在确定在步骤s85a中的处理中发生翻转的情况下，执行步骤s86a中的处理。在确定在步骤s85b中的处理中发生翻转的情况下，执行步骤s86b中的处理。在确定在步骤s85c中的处理中发生翻转的情况下，执行步骤s86c中的处理。在确定在步骤s85d中的处理中发生翻转的情况下，执行步骤s86d中的处理。在确定在步骤s85a至s85d中的处理中不发生翻转的情况下，执行步骤s88的处理。
[0249]
(s86a、s86b、s86c、s86d)在组g0至g3中，模块31a1至31am中的每一个从存储器读取关于翻转位的所有加权系数。在翻转位出现在所有组g0至g3中的情况下，由相应的模块31a1至31am(参照图9)读取针对所有组的翻转位的加权系数。
[0250]
(s87a、s87b、s87c、s87d)组g0至g3中的每一个使用所读取的加权系数执行具有图5所示的功能的h更新。在翻转位发生在所有组g0至g3中的情况下，针对由组g0至g3处理的副本中的每一个，更新与所有组的位相对应的局部字段。
[0251]
(s88)重复步骤s82、s83a至s87a、s83b至s87b、s83c至s87c和s83d至s87d中的处理，直到在每个副本中执行针对整个位的一次试验。当在每个副本中执行针对整个位的一次试验时，在经历循环处理时执行步骤s89中的处理。
[0252]
(s89)整体控制单元30确定是否结束搜索。在满足预定搜索结束条件的情况下，整体控制单元30确定结束搜索。例如，在迭代次数达到预定次数的情况下，整体控制单元30确定结束搜索。在确定结束搜索的情况下，fpga28a结束处理。在确定不结束搜索的情况下，重复从步骤s81的处理。
[0253]
注意，图10至图15所示的处理的顺序是示例，并且可以适当地改变处理的顺序。例如，在步骤s42和s43中的处理之前，可以执行步骤s44和s45中的处理。
[0254]
根据上述第二实施方式的数据处理装置20，基于指示搜索状态的搜索信息来改变部分并行试验的并行试验位数p。因此，可以根据反映问题特征的搜索状态来设置并行试验位数p，并且优化了用于改变一个位的算术运算量，并且可以改善针对大规模问题的求解性能。
[0255]
此外，除了算术运算量的优化之外，通过如上所述地改变并行试验位数p，在某个
位被反转的情况下，可以调整在该位成为下一个更新候选之前的时段。因此，通过反转位，可以避免当状态从局部解中逃离时位被再次反转并且状态被局部解再次约束的情况。
[0256]
此外，在根据第二实施方式的数据处理装置20中，对于每个单位处理时段(一步时段)，针对多个副本中的n个副本，每个包括一个或多个模块的n个组并行地执行并行部分试验。在执行各个部分并行试验的组之间，执行控制，使得在一个组完成关于针对某个副本的并行试验位数p的更新处理(h更新或状态向量的更新)之前，其他组不开始针对副本的部分并行试验的处理。数据处理装置20偏移流水线的处理时间，使得其他组处理其他副本，直到针对副本的更新处理完成。因此，即使在并行试验位数p是可变的情况下，也可以在遵守mcmc方法的顺序处理的原理的同时有效地利用算术运算资源，并且可以改善针对较大问题的求解性能。
[0257]
注意，在第二实施方式中，作为示例，组的数量为4。然而，组的数量可以是除了四个之外的多个。此外，副本的数量可以是除了16之外的数量。此外，由每个模块处理的位的数量被设置为k。然而，针对每个模块，k可以是不同的值。
[0258]
此外，数据处理装置20对每个副本的处理可以由fpga 28a如在上述示例中那样执行，或者可以由诸如cpu 21或gpu 24的另一算术单元执行。诸如fpga28a或cpu 21的算术单元是数据处理装置20中的处理单元的示例。此外，保存多个副本的存储单元可以由如上所述的存储器28b或寄存器来实现，或者可以由ram 22来实现。此外，可以说加速器卡28是“数据处理装置”的示例。
[0259]
注意，根据第一实施方式的信息处理可以通过使处理单元12执行程序来实现。此外，根据第二实施方式的信息处理可以通过使cpu 21执行程序来实现。程序可以记录在计算机可读记录介质103中。
[0260]
例如，可以通过分发其中记录有程序的记录介质103来分发程序。可替选地，该程序可以存储在另一计算机中并且经由网络分发。例如，计算机可以将记录在记录介质103中或者从另一计算机接收的程序存储(安装)在诸如ram 22或hdd 23的存储装置中、从存储装置读取程序并且执行程序。
[0261]
虽然已经基于实施方式描述了根据实施方式的程序、数据处理装置和数据处理方法的一个方面，但是这些仅为示例，并且不限于上面的描述。

技术特征：
1.一种存储数据处理程序的非暂态计算机可读记录介质，所述数据处理程序用于使搜索由包括多个状态变量的能量函数表示的组合优化问题的解的计算机执行以下处理，所述处理包括：通过执行以下操作执行搜索解的搜索处理：针对从所述多个状态变量中选择的多个第一状态变量，并行确定是否接受所述多个第一状态变量的每个值的改变，并且在改变多个选择的第一状态变量时执行改变其值的改变被确定为被接受的一个状态变量的值的处理；以及基于所述搜索处理的搜索状态或指示另一组合优化问题的搜索记录的搜索信息来指定所述多个选择的第一状态变量的数量，并且重复所述搜索处理。2.根据权利要求1所述的非暂态计算机可读记录介质，其中，所述搜索信息包括所述多个第一状态变量中的其值的改变被确定为被接受的第二状态变量的数量在第一时段中的第一累积值。3.根据权利要求2所述的非暂态计算机可读记录介质，所述处理还包括：基于所述第一累积值计算所述第二状态变量的数量在所述第一时段中的第一平均值；在所述第一平均值大于第一阈值的情况下，减少所述多个第一状态变量的数量；以及在所述第一平均值小于第二阈值的情况下，增加所述多个第一状态变量的数量，所述第二阈值小于所述第一阈值。4.根据权利要求1至3中任一项所述的非暂态计算机可读记录介质，其中，所述搜索信息包括所述多个第一状态变量中的其值变化的第三状态变量的数量在第二时段中的第二累积值。5.根据权利要求4所述的非暂态计算机可读记录介质，所述处理还包括：基于所述第二累积值计算所述第三状态变量在所述第二时段中的出现率；在所述出现率大于第三阈值的情况下，减少所述多个第一状态变量的数量；以及在所述出现率小于第四阈值的情况下，增加所述多个第一状态变量的数量，所述第四阈值小于所述第三阈值。6.根据权利要求1至5中任一项所述的非暂态计算机可读记录介质，其中，所述搜索信息包括由根据所述多个状态变量的状态向量在第三时段中的汉明距离表示的移动量。7.根据权利要求6所述的非暂态计算机可读记录介质，所述处理还包括：基于所述移动量计算所述移动量在所述第三时段中的第二平均值；在所述第二平均值大于第五阈值并且所述能量函数的最小值在所述第三时段中的搜索处理中未被更新的情况下，减少所述多个第一状态变量的数量；以及在所述第二平均值小于第六阈值并且所述最小值未被更新的情况下，增加所述多个第一状态变量的数量，所述第六阈值小于所述第五阈值。8.一种数据处理装置，所述数据处理装置搜索由包括多个状态变量的能量函数表示的组合优化问题的解，所述数据处理装置包括：处理单元，所述处理单元被配置成：针对从所述多个状态变量中选择的多个第一状态变量，并行确定是否接受所述多个第一状态变量的每个值的改变，通过在改变多个选择的第一状态变量时执行改变其值的改变被确定为被接受的一个状态变量的值的处理来执行搜索解的搜索处理，基于所述搜索处理的搜索状态或指示另一组合优化问题的搜索记录的
搜索信息，指定所述多个选择的第一状态变量的数量，并且重复所述搜索处理；以及存储单元，所述存储单元被配置成存储所述搜索信息。9.根据权利要求8所述的数据处理装置，其中，所述处理单元包括被分组的m个(m是等于或大于2的整数)模块和n个(n是等于或大于2的整数)组中的选择器，所述n个组中的每一组包括一个或多个模块，对于每个单位处理时段，针对分别指示所述多个状态变量的多个副本中的每n个副本，所述n个组并行地做出关于所述多个第一状态变量的确定，所述选择器根据对于所述n个组中的每一组的并行确定来选择其值的改变被确定为被接受的一个状态变量，以及所述处理单元执行控制，使得在改变所述第一副本中的由所述选择器选择的状态变量的值的更新处理在所述n个组中的第一组中结束之前，所述n个组中的除所述第一组之外的组不开始处理第一副本，所述第一副本是所述多个副本中的一个副本。10.一种搜索由包括多个状态变量的能量函数表示的组合优化问题的解的数据处理方法，所述数据处理方法包括：通过执行以下操作执行搜索解的搜索处理：针对从所述多个状态变量中选择的多个第一状态变量，并行确定是否接受所述多个第一状态变量的每个值的改变，并且在改变多个选择的第一状态变量时执行改变其值的改变被确定为被接受的一个状态变量的值的处理；以及基于所述搜索处理的搜索状态或指示另一组合优化问题的搜索记录的搜索信息来指定所述多个选择的第一状态变量的数量，并且重复所述搜索处理。

技术总结
本申请公开了计算机可读记录介质、数据处理装置和数据处理方法。计算机可读记录介质存储有数据处理程序，该数据处理程序用于使搜索由指示状态变量的能量函数表示的组合优化问题的解的计算机执行以下处理，所述处理包括：通过执行以下操作执行搜索解的搜索处理：针对从状态变量中选择的多个第一状态变量，并行确定是否接受多个第一状态变量的每个值的改变，并且在改变多个选择的第一状态变量时执行改变其值的改变被确定为被接受的一个状态变量的值的处理；以及基于搜索处理的搜索状态或指示另一组合优化问题的搜索记录的搜索信息来指定多个选择的第一状态变量的数量，并且重复该搜索处理。该搜索处理。该搜索处理。


技术研发人员：渡部康弘 田村泰孝
受保护的技术使用者：富士通株式会社
技术研发日：2022.11.24
技术公布日：2023/8/28