信息处理系统、计算机实现的方法和计算机可读存储介质与流程

计算;推算;计数设备的制造及其应用技术1.本文讨论的实施方式涉及信息处理系统、信息处理方法和存储信息处理程序的非暂态计算机可读存储介质。背景技术：2.存在以下信息处理设备：该信息处理设备通过用伊辛模型代替组合优化问题来计算冯诺依曼计算机不擅长的多变量组合优化问题，伊辛模型是表示磁材料中的自旋(spin)行为的模型。在实际中解决由伊辛模型替代的问题的方法包括诸如模拟退火(sa)和模拟量子退火(sqa)的各种搜索算法。通过包含多个状态变量的能量函数将组合优化问题公式化。能量函数有时被称为目标函数或评估函数等。信息处理设备使用搜索算法来搜索使能量函数值最小化的伊辛模型的基态。基态对应于组合优化问题的最优解。3.此处，存在以下情况：根据在由能量函数表示的问题中处理的状态变量的数量(其是问题的规模)，将问题划分成多个子问题并进行求解。4.例如，已经提出了一种优化问题计算系统，该优化问题计算系统将组合优化问题划分成多个子问题并且使伊辛机单独求解多个子问题中的每一个。所提出的优化问题计算系统从伊辛机接收多个子问题的每个解，并且基于多个子问题的每个解计算整个组合优化问题的解。5.此外，还提出了一种方法，在该方法中将与组合优化问题有关的解空间划分成多个单元，多个单元中的每一个是解空间的子集，并且在每个单元中启动的处理线程部分地并行执行。6.相关技术的示例包括如下：日本公开特许公报第2020-4387号；以及美国专利申请公布第2016/0335568号。技术实现要素：7.技术问题8.当问题被划分成多个子问题并进行求解时，将多个子问题和与每个子问题对应的状态变量组分配给节点。每个节点通过固定不属于被分配给自身节点的状态变量组的状态变量的值并且更新属于被分配给自身节点的状态变量组的状态变量来搜索解。在每个节点中，由于根据通过通信与其他节点的解共享来更新不属于被分配给自身节点的状态变量组的状态变量，因此更新频率低。因此，如果不再允许仅通过被分配给自身节点的状态变量组中的更新来执行状态转变，则应该等待不属于所述状态变量组的其值固定的状态变量的值的更新，并且求解速度降低。9.在一个方面，本实施方式旨在提供促进求解性能的提高的信息处理系统、信息处理方法和程序。10.问题的解决方案11.根据实施方式的一个方面，提供了一种信息处理系统，其被配置成搜索由包含多个状态变量的能量函数表示的问题的解。在示例中，信息处理系统包括：多个节点，通过划分问题而产生的多个子问题被分别分配给多个节点，多个节点中的每一个被配置成：通过更新属于与被分配给自身节点的一个子问题对应地分配的状态变量组的状态变量之一的值来搜索解之一，状态变量组为包括多个状态变量中的部分状态变量的组；保存通过搜索找到的多个解；将由自身节点保存的多个解之中的至少一个解发送至其他节点；接收由其他节点发送的其他解；以及基于从其他节点接收的其他解，根据自身节点的解更新规则来更新由自身节点保存的多个解中的至少一部分，其中，第一状态变量组的一部分与第二状态变量组的至少一部分交叠，第一状态变量组是从多个状态变量之中分配给多个节点之中的第一节点的组，第二状态变量组是从多个状态变量之中分配给多个节点之中的第二节点的组。12.发明的有益效果13.一方面，可以促进求解性能的改进。附图说明14.图1是说明根据第一实施方式的信息处理系统的图；15.图2是示出根据第二实施方式的信息处理系统的示例的图；16.图3是示出节点的硬件示例的图；17.图4是示出信息处理系统的功能示例的图；18.图5是示出子问题中的固定位的示例的图；19.图6是示出划分模式的示例的图；20.图7是示出被分配给每个节点的权重因子的示例的图；21.图8是示出保存在解缓冲器中的信息的示例的图；22.图9是示出搜索的整体控制的示例的流程图；23.图10是示出搜索之后的解更新的第一示例的流程图；24.图11是示出向另一节点发送解的示例的流程图；25.图12是示出从另一节点接收解的示例的流程图；26.图13是示出在搜索时变量固定的示例的流程图；27.图14是示出搜索之后的解更新的第二示例的流程图；28.图15是示出划分模式的分配的另一示例(部分1)的图；29.图16是示出划分模式的分配的另一示例(部分2)的图；30.图17a和图17b是示出求解速度降低的示例的图；31.图18是示出求解性能提高的示例的图；32.图19是示出节点的另一硬件示例的图；以及33.图20是示出使用多种搜索方法的信息处理系统的示例的图。具体实施方式34.在下文中，将参照附图描述本实施方式。35.[第一实施方式][0036]将描述第一实施方式。[0037]图1是说明根据第一实施方式的信息处理系统的图。[0038]信息处理系统1计算由伊辛模型的能量函数表示的问题的解，并且输出计算出的解。由伊辛模型的能量函数表示的问题包括组合优化问题。[0039]能量函数包含与伊辛模型中包含的多个自旋对应的多个状态变量。状态变量是取值1或0的二进制变量。例如，伊辛模型中的自旋的值“‑1”对应于状态变量的值“0”。伊辛模型中的自旋的值“+1”对应于状态变量的值“1”。为此，状态变量也可以被称为取值0或1的位。解由多个状态变量表示。由多个状态变量的整体表示的解也可以被称为“完整解”。组合优化问题被转换成计算使能量函数值最小化的解的问题。使能量函数值最小化的解与伊辛模型的基态相关，并且对应于组合优化问题的最优解。[0040]信息处理系统1包括多个节点。信息处理系统1将由能量函数表示的问题按位划分成多个子问题，并且利用多个节点分布式处理多个子问题。信息处理系统1可以在具有连接至内部总线的多个节点的一个壳体中实现，或者可以通过连接至诸如局域网(lan)、广域网(wan)或因特网的网络的多个节点来实现。[0041]在图1的示例中，信息处理系统1包括节点10、20、30……。节点10、20、30……中的每一个被分配有待解决的问题，该问题是通过划分整个问题而获得的子问题。此处，整个问题的伊辛模型的能量由例如公式(1)中的能量函数e(x)定义。[0042][0043]状态向量x具有多个状态变量作为元素并且表示伊辛模型的状态。在使能量函数值最大化的问题的情况下，仅使能量函数的符号相反。[0044]公式(1)右侧的第一项是通过将两个状态变量的值与权重因子的乘积进行合并而获得的，而对于可以从伊辛模型中包含的n个状态变量中选择的两个状态变量的所有组合，没有遗漏和重复。第i个状态变量由xi表示。第j个状态变量由xj表示。指示第i个状态变量与第j个状态变量之间的权重的权重因子由wij表示。例如，权重因子指示两个状态变量之间的耦合强度。注意，wii＝0成立。此外，wij＝wji成立。[0045]公式(1)右侧的第二项是针对所有状态变量计算每个偏差(bias)与状态变量值的乘积之和。第i个状态变量的偏差由bi表示。常数由c表示。[0046]使公式(1)中的能量函数的值最小化的状态变量值的组合是问题的最优解。此处，能量函数的值简称为能量。[0047]同时，处理例如i＝1至k(k《n)的状态变量(其是n(n是等于或大于二的整数)个状态变量的一部分)的子问题的伊辛模型的能量由以下公式(2)中的能量函数e'(x)定义。[0048][0049]在公式(2)中，b'i和c'可以分别表示为公式(3)和公式(4)。[0050][0051][0052]在搜索处理i＝1至k(k《n)的状态变量的子问题的解时，i＝k+1至n的状态变量的值是固定的。公式(3)右侧第二项表示具有固定值的状态变量对偏差的贡献量，并且公式(4)右边第二项和第三项表示具有固定值的状态变量对常数的贡献量。[0053]例如，节点针对状态变量x1至xk中的每一个计算由于状态变量x1至xk之中的一个状态变量的值的变化而导致的能量函数e'(x)的值的变化量，并且以优先考虑e'(x)变小的变化的方式随机接受所述变化量。由于状态变量x1至xk之中的xi的变化而导致的能量变化量δe'i可以表示为以下公式(5)。[0054][0055]在公式(5)中，当状态变量xi从1变为0时，δxi变为-1，并且当状态变量xi从0变为1时，δxi变为+1。通过相对于某个状态的能量对根据状态转变的能量变化量δe'i进行合并，可以计算出从所述某个状态转变的另一状态的能量。[0056]例如，在sa方法和副本交换方法中，使用梅特罗波利斯(metropolis)方法或吉布斯(gibbs)方法来确定通过更新某个状态变量而引起的某个伊辛模型从某个状态到下一状态的转变概率。例如，根据能量变化量与噪声值之间的比较，节点也随机地允许能量函数e'(x)的值变大的变化。噪声值是基于温度值或随机数计算出来的。温度值越大，噪声值的大小越大。噪声值的大小越大，越容易允许能量增加量大的状态转变。[0057]注意，在上面的示例中，已经指出处理i＝1至k的状态变量的子问题。然而，对于处理索引i的其他部分中的状态变量的其他子问题，也类似地计算能量和能量变化量。根据子问题而被分配给每个节点的状态变量组是多个状态变量的整体x的子集，并且可以具有索引i的连续部分或不连续部分。例如，关于在索引i方面彼此毗邻的第一部分和第二部分，节点可以计算出与第一部分和第二部分不毗邻的状态变量组对应的子问题的解。[0058]例如，信息处理系统1可以连接至控制设备(未示出)。控制设备基于由用户输入的关于组合优化问题的信息，来利用伊辛模型的能量函数公式化组合优化问题。控制设备将由能量函数表示的问题划分成多个子问题，并且将多个子问题分配给节点10和20。控制设备可以包括在信息处理系统1中。此外，控制设备的功能可以在节点10、20、30……中的任何一个中提供。[0059]节点10包括存储单元11、处理单元12和搜索单元13。节点20包括存储单元21、处理单元22和搜索单元23。虽然未示出，但是类似于节点10和20，节点30……也包括存储单元、处理单元和搜索单元。在下文中，将主要描述节点10和20的处理单元12和22以及搜索单元13和23作为示例，但是节点30……的处理单元和搜索单元也对被分配给自身节点的子问题执行类似的处理。全部节点10、20、30……覆盖了待解决的问题的全部状态变量。[0060]存储单元11和21可以是易失性存储设备例如动态随机存取存储器(dram)，或者可以是非易失性存储设备例如硬盘驱动器(hdd)或闪存。存储单元11和21中的每一个保存由节点10和20获取的解，该解是完整解。保存解的存储单元11和21的存储区域被称为解缓冲区。[0061]处理单元12和22可以包括中央处理单元(cpu)、数字信号处理器(dsp)、专用集成电路(asic)、现场可编程门阵列(fpga)等。处理单元12可以是执行程序的处理器。“处理器”可以包括多个处理器的集合(多处理器)。[0062]搜索单元13和23搜索被分配给自身节点的子问题的解。例如，搜索单元13和23由专用硬件实现。例如，使用集成电路例如fpga实现的搜索电路可以用作搜索单元13或23。然而，包括搜索单元13和23的节点10、20、30……的搜索单元中的至少一个可以通过处理器执行预定程序来实现。例如，在包括搜索单元13和23的节点10、20、30……的搜索单元中使用的搜索方法包括sa、遗传算法(ga)、sqa、禁忌搜索等。搜索方法不限于这些方法，而是也可以采用其他搜索方法。此外，在包括搜索单元13和23的节点10、20、30……的搜索单元中使用的搜索方法可以相同，或者可以在某个搜索单元与另一搜索单元之间不同。[0063]此处，对于通过某个节点的搜索而找到的解，将考虑分配有子问题的解的已分配区域部分。解的已分配区域部分是解中与子问题对应的状态变量组的值的集合。例如，节点10被分配有第一子问题。状态变量组x0对应于第一子问题。这意味着与第一子问题对应的解的已分配区域部分是属于状态变量组x0的状态变量xm至xp的值的集合。此外，节点20被分配有第二子问题。状态变量组x1对应于第二子问题。与第二子问题对应的解的已分配区域部分是属于状态变量组x1的状态变量xn到xq的值的集合。此处，m、n、p和q的大小关系为m《n《p《q。这意味着状态变量组x0和x1在索引i＝n至p的部分xa中交叠。[0064]注意，虽然未示出，但是搜索单元13包括保存状态变量组x0、与状态变量组x0对应的状态变量之间的权重因子等的存储单元例如静态随机存取存储器(sram)。类似地，搜索单元23还包括保存状态变量组x1、与状态变量组x1对应的状态变量之间的权重因子等的存储单元。存储在搜索单元13和23中的每一个的存储单元中的信息用于通过搜索单元13和23中的每一个进行的对子问题的解搜索。[0065]通过搜索单元13和23中的每一个进行的对解的搜索例如在预定时间段内重复执行，并且输出通过每次搜索获得的解。如稍后将描述的，在下一次解搜索即将开始之前，通过保存在解缓冲器中的全部解中的一个解初始化搜索单元13和23中的每一个中的解信息。解信息包括关于所有状态变量之中除由自身节点负责的状态变量组之外的其值要被固定的状态变量组的信息，并且例如是上面公式(2)中的能量函数e'(x)中的b'、c'等。通过初始化解信息，重置了b'和c'。[0066]存储单元11存储用于由处理单元12进行的处理的信息。存储单元11存储权重因子。存储在存储单元11中的权重因子仅需要是与状态变量组x0对应的部分。例如，存储在存储单元11中的权重因子的数量仅需要为n×n个权重因子之中的n×(p-m+1)个。权重因子用于计算解的能量并且初始化解信息。[0067]此外，存储单元11存储基于由公式(1)表示的整个问题的能量函数e(x)而选择的解。存储单元11中保存有多个解。保存在存储单元11中的解的数量为在节点10中预设的预定数量。此外，存储单元11将与解对应的公式(1)的能量与解相关联地保存。[0068]以这种方式，节点10、20、30……分别被分配有通过划分待解决的组合优化问题而产生的多个子问题。节点10、20、30……中的每一个通过更新多个状态变量之中属于与被分配给自身节点的子问题对应的状态变量组的状态变量的值来搜索组合优化问题的解。节点10、20、30……中的每一个保存多个解，这多个解包括反映了通过搜索找到的解的组合优化问题的第一解。第一解可以是通过搜索找到的解，或者可以是通过将保存在存储单元11中的解中的状态变量组x0的值的集合替换为通过搜索找到的解的相同部分而获得的。例如，节点10从反映在节点10处通过搜索找到的解的第一解和保存在存储单元11中的多个解之中优先选择预定数量的能量低的解，并且将所选择的预定数量的解保存在存储单元11中。[0069]节点10将由节点10保存的多个解之中的至少一个解发送至多个节点之中的节点20。例如，节点10从保存在存储单元11中的多个解之中优先选择能量低的至少一个解，并且将所选择的解发送至节点20。节点10可以将解发送至除节点20之外的其他节点。[0070]节点20基于从节点10接收到的解来更新由节点20保存的多个解的至少一部分。例如，节点20从自节点10接收到的解和保存在存储单元21中的多个解之中优先选择预定数量的能量低的解，并且将选择的预定数量的解保存在存储单元21中。[0071]此外，被分配给节点10的状态变量组x0的一部分与被分配给节点20的状态变量组xl的至少一部分交叠。交叠部分是上述部分xa。注意，整个状态变量组x1可以与状态变量组x0的部分xa相关。[0072]以这种方式，在节点10处通过搜索找到的良好解与节点20共享。类似地，通过从节点20向节点10发送解，在节点20处获得的良好解也可以由节点10和20共享。可以异步或同步执行从节点10向节点20发送解和从节点20向节点10发送解。[0073]通过以上处理，节点10、20、30……中的每一个基于通过自身节点的搜索找到的解来更新由自身节点保存的解并且基于由另一节点保存的解来更新由自身节点保存的解。节点10、20、30……中的每一个可以基于已经以上述方式更新的由自身节点保存的解来初始化自身节点中的解信息，并且搜索下一解。[0074]例如，在搜索单元13获得某个解之后，在即将进行下一次搜索之前，处理单元12基于保存在存储单元11中的多个解来确定在下一次搜索中除状态变量组x0之外的状态变量的值，并且改变公式(2)中的b'和c'。处理单元22也与处理单元12类似地执行确定除状态变量组x1之外的状态变量的值的处理。[0075]此处，可以想到各种方法，作为用于供处理单元12基于保存在存储单元11中的解来确定除状态变量组x0之外的状态变量的值的方法。[0076]在一个示例中，处理单元12从保存在存储单元11中的多个解之中选择通过公式(1)计算出的能量最小的解，并且根据所选择的解采用除状态变量组x0之外的每个状态变量的值。[0077]替选地，处理单元12可以从保存在存储单元11中的多个解之中随机选择一个解，并且根据所选择的解采用除状态变量组x0之外的每个状态变量的值。此时，当在存储单元11中保存三个或更多个解时，处理单元12可以从k个(例如，大约两个或三个)最小能量解中随机选择一个解。替选地，处理单元12可以将保存在存储单元11中的多个解中的每一个解的除状态变量组x0之外的相应状态变量的值进行比较，以选择其值与其他解的值匹配的状态变量的数量最大的解，并且根据所述解采用相应状态变量的值。[0078]以这种方式，处理单元12基于保存在存储单元11中的解来确定除状态变量组x0之外的每个状态变量的值，并且初始化要设置在搜索单元13中的解信息。然后，搜索单元13开始搜索针对状态变量组x0的下一解，例如，其中以所选择的解中包含的每个状态变量的值作为初始状态。[0079]类似于处理单元12，处理单元22也基于保存在存储单元21中的解来确定除状态变量组xl之外的每个状态变量的值，并且初始化要设置在搜索单元23中的解信息，以使搜索单元23开始搜索下一解。[0080]节点10、20、30……重复执行上述处理，并且当经过预定时间时，将保存在存储单元11和21中的解单独输出至控制设备。控制设备将从节点10、20、30……获取的解转换成组合优化问题的解的格式，并且通过例如在显示设备上显示解或经由网络将解发送至用户使用的终端设备来向用户提供解。例如，控制设备可以向用户提供从节点10、20、30……之一获取的能量最小的解，或者向用户提供从节点10、20、30……获取的多个解。[0081]如上面所描述的，在信息处理系统1中，多个节点中的每个节点搜索其中仅更新根据被分配给自身节点的子问题而分配的状态变量组的解，该状态变量组是包括多个状态变量中的部分状态变量的状态变量组。多个节点中的每一个保存通过搜索找到的多个解。多个节点中的每一个节点将由自身节点保存的多个解之中的至少一个解发送至另一节点，并且接收由另一节点发送的解。多个节点中的每一个节点基于从另一节点接收的解例如根据自身节点的解更新规则来更新由自身节点保存的多个解的至少一部分，该解更新规则优先保留能量低的解。从多个状态变量之中被分配给第一节点的第一状态变量组的一部分和从多个状态变量之中被分配给第二节点的第二状态变量组的至少一部分交叠。[0082]以这种方式，通过与其他节点共享在某个节点处检测到的良好解，可以通过多个节点联合改善解。此时，也可以设想生成子问题，使得被分配给各个节点的状态变量组不交叠。[0083]然而，在每个节点中，由于根据通过通信与其他节点的解共享来更新不属于被分配给自身节点的状态变量组的状态变量，因此更新频率低。因此，如果不再允许仅通过被分配给自身节点的状态变量组的更新来执行状态转变，则应该等待不属于该状态变量组的其值固定的状态变量的值的更新，并且求解速度降低。[0084]因此，通过扩大在至少一个节点中未固定的状态变量组的已分配范围，可以降低对其值固定的状态变量的依赖性，并且可以促进求解性能的提高。例如，可以缩短达到低能量的解的时间。[0085][第二实施方式][0086]接下来，将描述第二实施方式。[0087]图2是示出根据第二实施方式的信息处理系统的示例的图。[0088]信息处理系统2包括控制设备50和节点100、200、300、400……。控制设备50和节点100、200……连接至网络60。网络60可以是lan、wan、因特网等。[0089]控制设备50从用户接受组合优化问题的问题数据的输入。基于问题数据，控制设备50对由伊辛模型的能量函数表示的问题执行转换。该问题作为使伊辛模型的能量函数最小化的问题给出。能量函数可以包括表示期望被最小化的成本的成本项和表示约束的惩罚项。整个问题的能量函数由公式(1)进行公式化。公式(1)是以二次无约束二元优化(qubo)格式公式化的能量函数。在公式(1)中，wij、bi和c是在公式化时计算的。[0090]控制设备50将由伊辛模型的能量函数表示的问题划分成多个子问题，并且将多个子问题分配给节点100、200……。在信息处理系统2在预定时间内搜索了解之后，控制设备50获取由节点100、200……保存的解，并且将获取的解转换成组合优化问题的解的格式，以向用户提供解。例如，控制设备50可以由信息处理设备例如服务器计算机来实现。[0091]节点100、200……各自搜索被分配给自身节点的子问题的解。节点100、200……包括执行对解的搜索的加速器。加速器是计算使能量函数值最小化的解的硬件。然而，由节点100、200……中的至少一个提供的解搜索功能可以通过软件来实现。例如，节点100、200……可以通过信息处理设备例如计算机来实现。[0092]节点100、200……的相应加速器可以使用彼此不同的搜索方法(其是搜索算法)来搜索解，或者至少两个加速器可以使用相同的搜索方法来搜索解。例如，搜索方法包括sa、ga、sqa、禁忌搜索等。[0093]图3是示出节点的硬件示例的图。[0094]节点100包括cpu 101、随机存取存储器(ram)102、hdd 103、介质读取器104、加速器卡105、网络接口卡(nic)106和总线107。cpu 101是第一实施方式的处理单元12和22的示例。ram 102是第一实施方式的存储单元11和21的示例。加速器卡105实现了搜索通过划分组合优化问题而获得的子问题的解的搜索单元的功能，如稍后将描述的。加速器卡105是第一实施方式的搜索单元13和23的示例。[0095]cpu 101是执行程序命令的处理器。cpu 101将存储在hdd 103中的程序和数据的至少一部分加载到ram 102中并且执行该程序。注意，cpu 101可以包括多个处理器核。此外，节点100可以包括多个处理器。下面描述的过程可以使用多个处理器或处理器核并行执行。此外，多个处理器的集合有时被称为“多处理器”或简称为“处理器”。[0096]ram 102是暂时存储由cpu 101执行的程序和由cpu 101用于算术运算的数据的易失性半导体存储器。注意，节点100可以包括除ram之外的任何类型的存储器或者可以包括多个存储器。[0097]hdd 103是存储诸如操作系统(os)、中间件和应用软件的软件程序和数据的非易失性存储设备。注意，节点100可以包括另一种类型的存储设备，例如闪存或固态驱动器(ssd)，并且可以包括多个非易失性存储设备。[0098]介质读取器104是读取记录在记录介质61上的程序和数据的读取设备。例如，可以使用磁盘、光盘、磁光(mo)盘、半导体存储器等作为记录介质61。磁盘包括软盘(fd)和hdd。光盘包括致密盘(cd)和数字多功能光盘(dvd)。[0099]介质读取器104将例如从记录介质61读取的程序和数据复制到诸如ram 102或hdd 103的另一记录介质。读取的程序例如由cpu 101执行。注意，记录介质61可以是便携式记录介质并且有时用于分发程序和数据。此外，记录介质61和hdd 103有时可以被称为计算机可读记录介质。[0100]加速器卡105是搜索由伊辛模型的能量函数表示的问题的解的硬件加速器。加速器卡105包括fpga 111和ram 112。fpga 111实现加速器卡105中的搜索功能。此外，搜索功能可以通过其他类型的集成电路例如图形处理单元(gpu)或asic来实现。ram 112保存用于fpga 111中的搜索的数据以及通过fpga 111中的搜索找到的子问题的解。[0101]搜索伊辛格式的问题的解的硬件加速器例如加速器卡105有时被称为伊辛机、玻尔兹曼(boltzmann)机等。如稍后将描述的，节点100可以包括多个加速器卡。[0102]nic 106是连接至网络60并经由网络60与控制设备50和节点200、300和400进行通信的通信接口。nic 106例如通过线缆连接至通信设备，例如交换机或路由器。[0103]总线107是节点100的内部总线。cpu 101、ram 102、hdd 103、介质读取器104、加速器卡105和nic 106连接至总线107。例如，外围部件互连快速(pcie)总线用于总线107。[0104]注意，节点200、300和400也由与节点100的硬件类似的硬件实现。控制设备50也由与节点100的硬件类似的硬件实现。然而，控制设备50不必包括与加速器卡105相关的硬件。[0105]图4是示出信息处理系统的功能示例的图。[0106]控制设备50包括控制单元51。控制单元51例如通过控制设备50的cpu执行存储在控制设备50的ram中的程序来实现。[0107]控制单元51接受组合优化问题的问题数据的输入，以将问题数据转换至伊辛格式，将转换至伊辛格式的问题划分成多个子问题，并且将多个子问题分配给节点100、200……。然而，控制单元51可以接受来自外部的关于多个子问题的信息的输入以将多个子问题分配给节点100、200……。[0108]此外，控制单元51从节点100、200……获取解，并且基于获取的解向用户提供组合优化问题的解。[0109]此处，下面将通过例示节点100和200来描述相应节点的功能，但是节点300、400……中的每一个均具有与节点100和200的功能类似的功能。[0110]节点100和200分别具有数据存储单元120和220、解缓冲器130和230、搜索单元140和240、通信单元150和250以及搜索控制单元160和260。[0111]节点100和200的ram(例如，ram 102)的存储区域分别用于数据存储单元120和220以及解缓冲器130和230。搜索单元140和240分别通过节点100和200的加速器卡实现。通信单元150和250以及搜索控制单元160和260分别通过节点100和200的cpu执行存储在节点的ram中的程序来实现。[0112]在下文中，将主要描述节点100的功能，但对节点200、300、400……中具有相同名称的功能进行类似说明。[0113]数据存储单元120存储用于搜索控制单元160的处理的数据。例如，数据存储单元120存储与由节点100负责的状态变量组有关系的状态变量之间的权重因子。当属于由节点100负责的状态变量组的状态变量的数量为k时，由数据存储单元120保存的权重因子的数量被给定为k×n。[0114]解缓冲器130保存在节点100处获得的解。解缓冲器130保存整个问题的解，其是完整解。基于通过搜索单元140处的搜索找到的解和从另一节点接收的解，更新保存在解缓冲器130中的解。[0115]搜索单元140搜索被分配给节点100的子问题的解。[0116]搜索单元140使用诸如sa、ga、sqa和禁忌搜索的任何上述搜索方法来搜索子问题的解。此处，作为示例，将考虑使用sa或副本交换方法的情况。[0117]搜索单元140针对由自身节点负责的每个状态变量计算由于由自身节点负责的状态变量组中的一个状态变量的值的变化而引起的能量函数e'(x)的值的变化量，并且以优先考虑e'(x)变小的变化的方式随机接受所述变化量。然而，搜索单元140固定属于由除自身节点之外的节点负责的状态变量组的状态变量的值。能量函数e'(x)的值的变化量δe'i由上述公式(5)表示。[0118]此外，在sa方法和副本交换方法中，使用梅特罗波利斯方法或吉布斯方法来确定由于更新某个状态变量而引起的某个伊辛模型从某个状态到下一状态的转变概率。例如，搜索单元140还根据能量变化量与噪声值之间的比较，来随机地允许能量函数e'(x)的值变大的变化。噪声值是基于温度值或随机数计算出来的。温度值越大，噪声值的大小越大。噪声值的大小越大，越容易允许能量增加量大的状态转变。[0119]搜索单元140重复这样的过程，直到满足针对解的一次搜索的搜索结束条件，并且取当搜索结束条件满足时由自身节点负责的每个状态变量的值和状态变量的固定值的集合，作为此时的解。例如，根据是否已经经过了预定单位时间或者状态变量改变的尝试次数是否已经达到预定的单位次数等，来验证搜索结束条件。[0120]注意，虽然未示出，但是搜索单元140包括本地存储器，其保存由自身节点负责的每个状态变量的值以及与每个状态变量有关系的权重因子。安装在加速器卡105等上的sram的存储区域用于本地存储器。例如，ram 112可以是提供本地存储器的sram。[0121]通信单元150将保存在解缓冲器130中的解发送至另一节点并且从另一节点接收解。[0122]搜索控制单元160控制搜索单元140和通信单元150。搜索控制单元160可以异步操作搜索单元140和通信单元150。搜索控制单元160基于由搜索单元140获取的解来更新保存在解缓冲器130中的解。此外，搜索控制单元160指示通信单元150发送保存在解缓冲器130中的解。搜索控制单元160基于由通信单元150从另一节点接收的解来更新保存在解缓冲器130中的解。此外，搜索控制单元160基于保存在解缓冲器130中的解来初始化搜索单元140中的解信息。[0123]图5是示出子问题中的固定位的示例的图。[0124]图表70示出了状态变量x1、x2、x3、xk、xk+1和xn之间的相互关系的示例。例如，状态变量xk属于由节点100负责的状态变量组。在节点100中，包括在由除节点100之外的节点负责的状态变量组中的xk+1和包括在由除节点100之外的节点负责的状态变量组中的xn被视为固定位。在图表70的示例中，xk+1＝1和xn＝0成立。[0125]搜索控制单元160可以使用固定位的值和包括在由搜索单元140负责的状态变量组中的状态变量与固定位之间的权重因子，通过公式(3)来指定偏差b'i。例如，xk与xk+1之间的权重因子wk,k+1用于计算b'k，并且x3与xk+1之间的权重因子w3,k+1用于计算b'3。[0126]此处，如下根据划分模式指定被分配给每个节点的状态变量组。[0127]图6是示出划分模式的示例的图。[0128]作为示例，如下确定用于划分模式的划分方案。此处，n被假定为全部状态变量的划分数量。n是等于或大于二的整数。m被假定为通过将状态变量划分成n个而获得的每个已划分区域的区域数量。m是等于或大于2的整数。进一步对已划分区域内部进行划分的区域可以被称为子区域。例如，通过将全部状态变量划分成m*n个区域并且从已划分区域之中选择m个区域而获得的模式作为一个模式，并且准备好所有的组合。注意，每个区域的大小可以相等或者可以不相等。在一个示例中，可以想到控制设备50将通过以下过程获得的划分模式分配给每个节点。[0129](1)将全部状态变量划分成m*n个区域。[0130](2)列出从m*n个区域之中选择m个区域的所有划分模式。[0131](3)从所有划分模式之中选择(n+1)个或更多个划分模式，使得所有单独的状态变量被包括在任何一个划分模式中。[0132]注意，上述步骤(1)至(3)可以由控制设备50执行。[0133]划分示例80例示了在m＝2和n＝2的情况下针对全部状态变量的所有划分模式。例如，在将全部状态变量划分为两个之后，将已划分部分进一步划分成两个区域。按从状态变量的最小索引开始的顺序，将以这种方式划分的区域看作区域a、b、c和d。在两个划分和四个区域的示例(即m＝2和n＝2的情况)中，区域数量为4(＝2*2)。因此，划分模式的总数为6(＝4c2)。[0134]划分模式#1具有区域a和b。划分模式#2具有区域a和c。划分模式#3具有区域a和d。划分模式#4具有区域b和c。划分模式#5具有区域b和d。划分模式#6具有区域c和d。[0135]例如，将与划分模式#1对应的子问题分配给节点100。在这种情况下，将与划分模式#1对应的状态变量组和权重因子分配给节点100。此外，将分别对应于划分模式#2、划分模式#3……的子问题分别分配给节点200、300……。当使用所有六个划分模式时，要使用的节点的数量将为六个。[0136]此处，当通过反转包含在区域a中的状态变量和包含在区域b中的状态变量来实现向良好解的移动时，由于划分模式#1可以在不受固定状态变量的影响的情况下搜索解，因此以高概率实现转变。同时，在划分模式#2和划分模式#3中，不允许属于区域a的状态变量和属于区域b的状态变量同时转变，因为状态变量是固定的。为了实现转变，预期等待通过经由每个节点的通信单元共享良好解来更新固定部分中的状态变量的值，这花费长时间。[0137]类似地，当通过反转包含在区域a中的状态变量和包含在区域c中的状态变量来实现向良好解的移动时，仅在划分模式#2下可以高速进行转变，但在其他模式下转变花费长时间。通过在区域a和b的集合、区域a和c的集合以及区域a和d的集合的所有四种划分模式下在共享解的同时进行求解，实现包括区域a中的状态变量的任何两个状态变量的转变，而不受固定状态变量的影响。[0138]此外，通过使用划分示例80中所示的所有划分模式#1至#6在相应节点之中计算解同时共享解，实现所有区域中任意两个状态变量的转变，而不受固定状态变量的影响。[0139]图7是示出被分配给每个节点的权重因子的示例的图。[0140]例如，节点100被分配有属于区域a和b的每个状态变量。节点200被分配有属于区域a和c的每个状态变量。节点300被分配有属于区域a和d的每个状态变量。被分配给每个节点的状态变量的值被保存在节点的搜索单元的本地存储器中。[0141]此外，每个节点将根据由自身节点负责的划分模式的权重因子保存在本地存储器中。表81例示了整个权重矩阵w中与区域a、b、c和d中的每一个对应的部分。此处，权重因子的参考符号的下划线“_”之后的数值指示关于状态变量的以下索引范围。与区域a对应的索引范围由“0”指示。与区域b对应的索引范围由“1”指示。与区域c对应的索引范围由“2”指示。与区域d对应的索引范围由“3”指示。[0142]与区域a对应的权重因子组为一组权重因子w_00、w_10、w_20和w_30。与区域b对应的权重因子组为一组权重因子w_01、w_11、w_21和w_31。与区域c对应的权重因子组为一组权重因子w_02、w_12、w_22和w_32。与区域d对应的权重因子组为一组权重因子w_03、w_13、w_23和w_33。[0143]例如，节点100保存与区域a和b对应的一组权重因子w_00、w_10、w_20和w_30以及一组权重因子w_01、w_11、w_21和w_31。此外，节点200保存与区域a和c对应的一组权重因子w_00、w_10、w_20和w_30以及一组权重因子w_02、w_12、w_22和w_32。节点300保存与区域a和d对应的一组权重因子w_00、w_10、w_20和w_30以及一组权重因子w_03、w_13、w_23和w_33。类似地，负责划分模式#4至#6的其他节点也根据由自身节点负责的划分模式来保存权重因子组。[0144]图8是示出保存在解缓冲器中的信息的示例的图。[0145]从全部状态变量向节点100分配与区域a和b对应的状态变量组x0。同时，与区域c和d对应的状态变量组x1被视为其中值固定的固定部分。[0146]解缓冲器130保存解和能量。为方便说明，包含解和能量的记录的标识号用“#”指示。[0147]具有标识号“0”的记录具有解“x0_0和x1_0”以及能量“e0”。此处，通过向表示某个状态变量组的参考符号如x0附加下划线“_”和数字例如“_1”，来将该状态变量组中各个状态变量的值的集合区分为例如“x0_0”和“x0_1”。[0148]示出了以下示例：解缓冲器130存储除了标识号“0”之外具有标识号“1”、“2”和“3”的记录。[0149]规定解缓冲器130中存储的解和能量的组数。在第二实施方式的示例中，假设在每个节点的解缓冲器中存储四组解和能量。然而，存储在各个节点的每个解缓冲器中的解和能量的组数可以是除四之外的数量。[0150]当针对状态变量组x0获取通过搜索单元140处的搜索找到的解时，搜索控制单元160计算解候选的能量，其中找到的解被反映在保存在解缓冲器130中的解中。此时，数据存储单元120仅保存关于与被分配给节点100的状态变量组x0中的每个状态变量耦合的状态变量的权重因子组。因此，搜索控制单元160如下计算当保存在解缓冲器130中的解的与状态变量组x0相关的一部分改变为新值时的能量。注意，对于被分配给另一节点的另一状态变量组，可以以类似的方式计算能量。[0151]全部状态变量被假定为sn。对应于sn的能量被假定为en。[0152]此外，利用表示sn＝sa&so。sa表示由自身节点负责的状态变量组，并且在节点100的情况下与状态变量组x0相关。so表示由另一节点负责的状态变量组，并且与作为节点100的固定部分的状态变量组x1相关。与符号“&”意指将&左侧的状态变量组和&右侧的状态变量组组合。[0153]将考虑以下情况：当由自身节点负责的状态变量组从sa更新为sa'时计算能量e的更新后的能量e'。[0154]例如，节点100针对保存在解缓冲器130中的解获得更新之前状态变量组sa的每个状态变量的值以及能量e。此外，可以在自身节点处计算状态变量组sa'相对于状态变量组sa的能量变化δe(e'-e)。例如，节点100将根据由自身节点保存的权重因子和so计算的附加偏差δb添加到原始偏差b，并且然后可以根据权重因子、偏差(b+δb)以及自身节点的状态变量的变化(sa'-sa)计算能量变化δe(e'-e)。[0155]因此，更新后的能量e'被给出为e'＝e+δe，并且仅可以由自身节点计算。[0156]接下来，将描述信息处理系统2的处理过程。首先，控制设备50将子问题分配给节点100、200……中的每一个。然后，节点100、200……执行以下所示的过程。尽管将主要描述节点100作为示例，但是节点200……执行与节点100的过程类似的过程。[0157]图9是示出搜索的整体控制的示例的流程图。[0158](s1)搜索单元140执行对子问题的解的搜索。搜索单元140通过搜索获得解。搜索控制单元160获取在搜索单元140处获得的解。在搜索中，搜索单元140仅更新属于被分配给自身节点的状态变量组x0的状态变量的值。[0159](s2)搜索控制单元160执行搜索之后的解更新。将稍后描述搜索之后的解更新的处理的细节。[0160](s3)搜索控制单元160执行经由通信单元150向另一节点发送解。稍后将描述向另一节点发送解的处理的细节。[0161](s4)搜索控制单元160执行经由通信单元150从另一节点接收解。稍后将描述从另一节点接收解的处理的细节。[0162](s5)搜索控制单元160验证是否满足搜索的整体控制的结束条件。当不满足结束条件时，搜索控制单元160进行到处理中的步骤s6。当满足结束条件时，搜索控制单元160进行到处理中的步骤s7。例如，结束条件是从整体控制的处理开始已经经过了预定时间，或者上述步骤s1已经执行了预定次数等。[0163](s6)搜索控制单元160执行搜索时的变量固定的处理。搜索时的变量固定的处理包括解信息的初始化。稍后将描述搜索时的变量固定的处理的细节。然后，搜索控制单元160进行到处理中的步骤s1。[0164](s7)搜索控制单元160将保存在解缓冲器130中的解输出到控制设备50。然后，搜索控制单元160结束搜索的整体控制的处理。[0165]注意，步骤s3中向另一节点发送解和步骤s4中从另一节点接收解不必如上所述在步骤s2之后执行，并且可以与通过搜索单元140进行的搜索异步地在任何时间执行，例如以预定周期执行。例如，可以设想，使向另一节点发送解的周期与基于通过搜索单元140进行的搜索找到的解更新解缓冲器130中的解的周期相同，或者比该周期长。此外，当另一节点将解作为推送发送时，可以执行从另一节点接收解。以这种方式，在自身节点处的搜索、向另一节点发送解和从另一节点接收解可以作为独立的处理单独执行。另外，可以以任何顺序执行步骤s3中向另一节点发送解和步骤s4中从另一节点接收解。例如，可以以相反的顺序执行步骤s3和s4。此外，有时一个节点接连从多个其他节点接收解。[0166]图10是示出搜索之后的解更新的第一示例的流程图。[0167]搜索之后的解更新的处理与步骤s2相关。[0168](s10)搜索控制单元160从搜索单元140获取通过搜索找到的解的已分配区域部分sp。已分配区域部分sp是通过搜索找到的解中被分配给自身节点的状态变量组x0的值的集合。[0169](s11)搜索控制单元160执行解候选生成循环。在图10的过程中，假设i为循环被执行的次数。假设i的初始值为零。此外，假设k为存储在解缓冲器130中的解的数量。每当循环被执行一次，i增加。当i《k成立时，重复执行以下步骤s12至s14。[0170](s12)搜索控制单元160从解缓冲器130获取第i个解s(i)和能量e(i)。[0171](s13)搜索控制单元160针对解s(i)生成解候选s'(i)，其中作为属于由节点100负责的状态变量组x0的状态变量部分的可用位被替换为已分配区域部分sp。[0172](s14)搜索控制单元160计算解候选s'(i)的能量e'(i)。[0173](s15)每当循环被执行一次，搜索控制单元160增加i，并且当达到i＝k时，退出解候选生成循环以进行到处理中的步骤s16。[0174](s16)搜索控制单元160比较解缓冲器130中的原始解s(i)和生成的解候选s'(i)的总共2k个能量e(i)和e'(i)，并且选择k个能量最低的解。要选择的k个解可以包括解候选s'(i)。[0175](s17)搜索控制单元160用在步骤s16中选择的k个解替换解缓冲器130中的解。然后，搜索控制单元160结束搜索之后的解更新的处理。[0176]图11是示出向另一节点发送解的示例的流程图。[0177]向另一节点发送解的处理与步骤s3相关。[0178](s20)搜索控制单元160从解缓冲器130获取前k个解，前k个解是k个能量最低的解。在图11的过程中，k表示等于或大于1但小于保存在解缓冲器130中的解的数量的整数。例如，从大约1到3的值之中规定k的值。[0179](s21)搜索控制单元160经由通信单元150将所选择的k个解和能量发送至另一节点。解的发送目的地是除自身节点之外的所有节点。然后，搜索控制单元160结束向另一节点发送解的处理。[0180]图12是示出从另一节点接收解的示例的流程图。[0181]从另一节点接收解的处理与步骤s4相关。[0182](s30)通信单元150从另一节点接收解sr和能量er。搜索控制单元160获取在通信单元150处接收的解sr和能量er。[0183](s31)搜索控制单元160获取解缓冲器130中的最差解sw的能量ew，最差解sw是具有最大能量的解sw。[0184](s32)搜索控制单元160验证er≤ew是否成立。当er≤ew成立时，搜索控制单元160进行到处理中的步骤s33。当er＞ew成立时，搜索控制单元160丢弃从另一节点接收的解sr并且结束从另一节点接收解的处理。[0185](s33)搜索控制单元160用解sr替换解缓冲器130中的最差解sw。搜索控制单元160丢弃最差解sw。然后，搜索控制单元160结束从另一节点接收解的处理。[0186]注意，图12示出了从另一节点接收一个解的示例。然而，当从另一节点接收到多个解时，搜索控制单元160将解缓冲器130中的解和接收到的解之中预定数量的能量最小的解保存在解缓冲器130中。[0187]图13是示出搜索时的变量固定的示例的流程图。[0188]搜索时的变量固定的处理与步骤s6相关。[0189](s40)搜索控制单元160从解缓冲器130中的前k个解(其是k个能量最低的解)中随机选择一个解ss。在图13中的过程中，k表示等于或大于1但小于保存在解缓冲器130中的解的数量的整数。[0190](s41)搜索控制单元160计算偏差，使得被分配给另一节点的变量部分固定至所选择的解ss的值。偏差与公式(2)中的b'相关。[0191](s42)搜索控制单元160将选择的解ss和偏差b'输入到搜索单元140并且使搜索单元140执行搜索。例如，可以假设在步骤s42的阶段设置在搜索单元140中的解ss，作为由搜索单元140进行的搜索的初始状态。此外，搜索控制单元160可以将当由另一节点负责的变量部分固定至所选择的解ss时的能量输入到搜索单元140，并且使搜索单元140更新能量。然后，搜索控制单元160结束搜索时的变量固定的处理。[0192]以这种方式，通过评估解候选——其中通过搜索新找到的解被节点100、200……反映在每个节点的解缓冲器中的所有解中，使搜索结果更容易被快速反映在很多良好解中。[0193]注意，在上面的示例中，假设解候选是通过用通过每个节点处的搜索找到的解的自身节点的已分配区域部分替换自身节点的解缓冲器中的解的对应部分来生成的，并且用解候选替换解缓冲器中的解。同时，也可以想到用于更新解缓冲器中的解的其他方法。[0194]例如，节点100、200……可以各自使用由其搜索单元获得的解作为解候选来更新自身节点的解缓冲器中的解。例如，为了获得解候选的能量，搜索控制单元160可以将用于搜索时的变量固定的解和解的能量保存在数据存储单元120中。例如，搜索控制单元160将解候选的能量与保存在解缓冲器130中的解的能量进行比较，并且如果解候选的能量大于保存在解缓冲器130中的最差解的能量，则用解候选替换最差解。接下来，将描述解缓冲器中的解的这种更新的过程的示例。[0195]图14是示出搜索之后的解更新的第二示例的流程图。[0196]搜索之后的解更新的处理与步骤s2相关。执行图14中的过程，代替图10中的过程。[0197](s50)搜索控制单元160将用于搜索时的除自身节点变量之外的变量固定的解sf和解sf的能量ef保存在数据存储单元120中。自身节点变量是包括在由节点100负责的状态变量组中的状态变量。[0198](s51)搜索控制单元160从搜索单元140获取通过搜索找到的解的已分配区域部分sp。[0199](s52)搜索控制单元160针对用于变量固定的解sf生成解sf'，在解sf'中，可用位被替换为已分配区域部分sp。[0200](s53)搜索控制单元160计算解sf'的能量ef'。[0201](s54)搜索控制单元160比较能量ef和ef'，并且选择较小一者的解。[0202](s55)搜索控制单元160用在步骤s54中选择的解替换解缓冲器130中的最差解。然后，搜索控制单元160结束搜索之后的解更新的处理。[0203]注意，还可以想到，在状态变量的值更新时，搜索单元140基于公式(5)更新当前状态的能量。在那种情况下，搜索控制单元160可以在步骤s53中从搜索单元140获取能量ef'。此处提到的状态表示由用于表达整个问题的所有状态变量的值表示的伊辛模型的状态。[0204]以这种方式，通过与其他节点共享在某个节点处检测到的良好解，可以通过多个节点联合改善解。此时，还可以想到生成子问题，使得被分配给各个节点的状态变量组不交叠。[0205]然而，在每个节点中，由于不属于被分配给自身节点的状态变量组的状态变量是根据通过通信与其他节点共享的解来更新的，因此更新频率低。因此，如果不再允许仅通过被分配给自身节点的状态变量组的更新来执行状态转变，则应该等待不属于该状态变量组的其值固定的状态变量的值的更新，并且求解速度降低。[0206]因此，通过扩大在至少一个节点中未固定的状态变量组的已分配范围，降低了对其值固定的状态变量的依赖性，并且可以促进求解性能的提高。例如，可以缩短达到低能量的解的时间。[0207]注意，还可以想到用于将划分模式分配给每个节点的其他方法。[0208]图15是示出划分模式的分配的另一示例(部分1)的图。[0209]例如，可以使用划分示例80中的所有划分模式的一部分。作为示例，可以将区域a、b、c和d分别分配给节点100、200、300和400，可以将具有区域b和d的划分模式分配给节点500，并且可以将具有区域c和d的划分模式分配给节点600。[0210]在这种情况下，将与区域a对应的权重因子组分配给节点100。将与区域b对应的权重因子组分配给节点200。将与区域c对应的权重因子组分配给节点300。将与区域d对应的权重因子组分配给节点400。将与区域a和c对应的权重因子组分配给节点500。将与区域b和d对应的权重因子组分配给节点600。[0211]然而，图15中的分配示例是示例，并且可以使用所有划分模式的另一部分。此外，还可以想到如下划分模式的分配。[0212]图16是示出划分模式的分配的另一示例(部分2)的图。[0213]在划分示例90中，如下将全部状态变量划分至六个划分模式#1至#6。例如，区域a1、b1和c1是通过按从最小索引起的顺序将全部状态变量界定至三个区域而获得的。区域a2、b2、c2和d2是通过按从最小索引起的顺序将全部状态变量界定至四个区域而获得的。区域a3、b3、c3、d3和e3是通过按从最小索引起的顺序将全部状态变量界定至五个区域而获得的。[0214]划分模式#1具有区域a1。划分模式#2具有区域b1。划分模式#3具有区域c1。划分模式#4具有区域b2。划分模式#5具有区域a3和c3。划分模式#6具有区域c3和d3。区域b2与区域a1、b1和c3中的每一个的一部分交叠。整个区域a3与区域a1的一部分交叠。整个区域c3与区域b1的一部分交叠。区域c3与区域b2的一部分交叠。区域d3与区域b1和c1中的每一个的一部分交叠。[0215]例如，可以想到将在图16中的划分模式#1至#6分配给6个节点。此外，还可以想到确定划分模式，使得全部状态变量的相应部分之间的交叠的数量接近均匀。例如，可以指定划分示例90中的划分模式#6以具有区域d3和e3。替选地，可以指定划分示例90中的划分模式#5以具有区域a3和e3。[0216]另外，在划分示例90中，示出了使用以诸如三、四和五的三种类型的数量来界定区域的划分模式的示例。然而，例如，可以使用以诸如二和三的两种类型的数量来界定区域的划分模式，或者可以使用以四种或更多种类型的数量来界定区域的划分模式。[0217]例如，当安装的存储器的量在相应节点的加速器卡之间不同时，可以想到使用通过不同的划分数量划分的划分模式。在这种情况下，通过将与具有宽索引范围的区域对应的状态变量组分配给具有大量安装存储器的节点并且将与具有窄索引范围的区域对应的状态变量组分配给具有少量安装存储器的节点，可以有效地利用存储器资源。[0218]图17a和图17b是示出求解速度降低的示例的图。[0219]图17a示出了图表g1。图17b示出了图表g2。图表g1和图表g2表示根据全部状态变量是否被划分，最低能量对四色问题的求解中的时间变化的影响。图表g1描绘了全部状态变量没有被划分的情况。图表g2描绘了全部状态变量被划分至五个区域并且各个划分区域不交叠的情况。图表g1和图表g2的横轴表示以秒为单位的时间，并且纵轴表示解的能量。[0220]比较图表g1和图表g2，可以看出，在仅在被分配给每个节点的区域中通过搜索来检索良好解的情况下求解进行，但是当不再允许这样做时，求解速度降低。在由每个节点进行的解搜索中，自身节点的已分配区域外的状态变量被固定至初始解的值，但更新频率较低，因为已分配区域外的状态变量仅通过节点之间的通信来更新。因此，有时难以提高解的质量。作为结果，如果由于固定状态变量的值的影响而不再允许在已分配区域中通过搜索来检索良好解，则会出现求解速度大大降低的现象。[0221]在大规模问题中，难以用单个节点计算出解，并且因此，求解速度的降低成为用多个节点计算解的问题。因此，在信息处理系统2中，使被分配给某个节点的状态变量组的一部分和被分配给另一节点的状态变量组的至少一部分交叠。[0222]图18是示出求解性能的提高的示例的图。[0223]如图6中例示的，对于两个划分和四个区域，总共存在六种划分模式。研究了使用的划分模式的数量增加到三个的情况，这与使用的划分模式的数量是两个而没有交叠区域的情况——这是通常的两个划分的情况——形成对照。在通常的两个划分的情况下，第一划分模式具有区域c和d，并且第二划分模式具有区域a和b。此外，在使用的划分模式的数量为三个的情况下，第一划分模式具有区域c和d，第二划分模式具有区域a和b，并且第三划分模式具有区域a和c。[0224]图表g3具有对四色问题的解的模拟结果，并且示出了解缓冲器中的解的能量的时间变化。图表g3的横轴表示以秒为单位的时间，并且纵轴表示解的能量。序列g31表示使用两个划分模式的情况。序列g32表示使用三个划分模式的情况。[0225]如由序列g31和g32所指示，通过使用三种划分模式并且使由相应节点负责的状态变量组的部分交叠，与通常的两个划分的情况相比，在解的质量和求解速度两个方面均确认了提高。例如，10个种子的最佳解的平均能量从32.2提高到23.3，从而提高了解的质量。此外，与通常的两个划分的情况相比，达到最佳解的时间改善了大约23％。例如，缩短了达到最佳解的时间。以这种方式，根据信息处理系统2，可以提高求解性能。[0226]图19是示出节点的另一硬件示例的图。[0227]例如，除了图4例示的硬件之外，节点100还可以包括加速器卡105a。类似于加速器卡105，加速器卡105a是硬件加速器，其搜索由伊辛模型的能量函数表示的问题的解。[0228]加速器卡105a包括gpu 111a和ram 112a。gpu 111a实现了加速器卡105a中的搜索功能。搜索功能可以通过其他类型的集成电路例如fpga或asic来实现。ram 112a保存用于由gpu 111a进行的搜索的数据和通过gpu 111a的搜索找到的子问题的解。[0229]注意，加速器卡105a可以使用与加速器卡105的搜索方法相同的搜索方法，或者可以使用与加速器卡105的搜索方法不同的搜索方法。例如，加速器卡105可以使用sa，并且加速器卡105a可以使用禁忌搜索。此外，节点100可以包括三个或更多个加速器卡。[0230]通过向一个节点提供两个或更多个加速器卡，可以在该节点中实现两个或更多个搜索单元的功能。在这种情况下，一个节点可以负责两个或更多个子问题。[0231]图20是示出使用多种搜索方法的信息处理系统的示例的图。[0232]例如，节点100使用sqa。节点200使用禁忌搜索。节点300使用sa。节点400使用ga。以这种方式，节点100、200、300、400……可以使用彼此不同的搜索方法。替选地，至少两个节点可以使用相同的搜索方法，使得在节点100、200、300、400……之间，至少两个节点使用sa，并且其他节点使用sqa或禁忌搜索。节点100、200、300、400……可以全部均使用相同的搜索方法。[0233]如例示的，搜索方法可以以节点为单位而不同，或者使用多种搜索方法的多个加速器可以混合配备在一个节点中。加速器由fpga、gpu、asic等实现，如之前所描述的。如在第二实施方式中例示的，fpga、gpu、asic等之中的至少两类集成电路可以混合配备在一个节点中。[0234]在信息处理系统2中，多个节点中的每一个与另一节点共享在每个节点处获得的多个解中的最佳解，并且基于共享的解来确定状态变量组中的每个节点处要在下一搜索中固定的每个状态变量的值。假设在较好的解附近极有可能存在更好的解。因此，通过与另一节点共享在每个节点处检测到的良好解，并且基于共享的解来确定状态变量组中的要被固定的每个状态变量的值，可以将搜索空间缩小到较好的解附近，并且更有可能获得更好的解。[0235]然后，通过扩大在至少一个节点中未固定的状态变量组的已分配范围，降低了对其值固定的状态变量的依赖性，并且可以促进求解性能的提高。例如，可以缩短达到低能量的解的时间。此外，更有可能获得能量较低的解。[0236]另外，在信息处理系统2中，每个节点可以异步进行搜索，并且每个节点也可以使用不同的搜索方法来搜索解。因此，对于相对大规模的问题，可以容易地增加节点，并且可以实现具有极好扩展性的系统。[0237]上述信息处理系统2执行例如以下处理。还可以在信息处理系统1中执行以下处理。[0238]信息处理系统2搜索由包含多个状态变量的能量函数表示的问题的解。信息处理系统2包括多个节点，通过划分问题而产生的多个子问题被分别分配给多个节点。节点100、200……是多个节点的示例。多个节点的数量可以是两个或更多个。[0239]多个节点中的每一个通过更新属于与被分配给自身节点的子问题对应地分配的状态变量组的状态变量的值来搜索解，该状态变量组是包括多个状态变量中的部分状态变量的状态变量组。多个节点中的每一个保存通过搜索找到的多个解。保存在解缓冲器130中的解是多个解的示例。这同样适用于保存在节点200……中的每一个的解缓冲器中的解。[0240]多个节点中的每一个将由自身节点保存的多个解之中的至少一个解发送至另一节点。多个节点中的每一个基于从另一节点接收的解根据自身节点的优先保留能量低的解的解更新规则来更新由自身节点保存的多个解的至少一部分。[0241]然后，被分配给第一节点的第一状态变量组的一部分与被分配给第二节点的第二状态变量组的至少一部分交叠。[0242]与每个节点负责没有交叠的状态变量组的情况相比，这可以减少对其值固定的状态变量的依赖性并促进求解性能的提高。[0243]注意，基于从第一节点接收的解来更新由第二节点保存的多个解的至少一部分的处理对应于当第一节点向第二节点发送解时使第二节点更新由第二节点保存的多个解的至少一部分的处理。[0244]此外，如图15和图16中例示的，第一状态变量组的不与第二状态变量组交叠的部分可以与从多个状态变量之中被分配给多个节点之中的第三节点的第三状态变量组的至少一部分交叠。[0245]与每个节点负责没有交叠的状态变量组的情况相比，这可以减少对其值固定的状态变量的依赖性并促进求解性能的提高。例如，在图16的划分示例90中，划分模式#2(区域b1)是第一状态变量组的示例，划分模式#4(区域b2)是第二状态变量组的示例，并且划分模式#6(区域c3和d3)是第三状态变量组的示例。[0246]替选地，第一状态变量组的不与第二状态变量组交叠的部分的一部分可以与从多个状态变量之中被分配给多个节点之中的第三节点的第三状态变量组的至少一部分交叠。[0247]与每个节点负责没有交叠的状态变量组的情况相比，这可以减少对其值固定的状态变量的依赖性并促进求解性能的提高。例如，在图16的划分示例90中，划分模式#1(区域a1)是第一状态变量组的示例，划分模式#5(区域a3和c3)是第二状态变量组的示例，并且划分模式#4(区域b2)是第三状态变量组的示例。[0248]此外，如图6所例示的，与被分配给多个节点中的每一个的子问题对应的状态变量组的多个部分中的每一个部分可以与被分配给多个节点之中的任何另一节点的另一状态变量组的一部分交叠。[0249]这允许在不受固定状态变量的值的影响的情况下执行任何两个状态变量的转变(任何两个位的转变)。[0250]此外，属于第一状态变量组的状态变量的数量可以不同于属于第二状态变量组的状态变量的数量。[0251]这使得能够根据每个节点的算术资源将搜索负荷分配给相应节点。[0252]例如，信息处理系统2可以包括控制单元51。控制单元51可以向多个节点中的每一个分配包括根据可用于供多个节点中的每一个搜索解的存储器大小的数目个状态变量的状态变量组。[0253]这允许有效地利用每个节点的存储器资源。例如，当节点具有较大的存储器大小时，可以将更多数量的状态变量安置成由适用节点负责，并且当节点具有较小的存储器大小时，可以将较少数量的状态变量安置成由适用节点负责。[0254]此外，控制单元51可以将多个子问题分配给多个节点。例如，控制单元51可以执行将被分配给第一节点的第一状态变量组的一部分与被分配给第二节点的第二状态变量组的至少一部分交叠的处理。此外，当在特定时间段内重复执行由多个节点中的每个节点进行的对解的搜索以及在节点之间发送和接收解时，控制单元51可以从由多个节点中的每一个保存的多个解之中获取至少一个解，并且输出所获取的解。[0255]这使得可以适当地获取通过使用多个节点获得的最终解。如先前所描述的，控制单元51获取由多个节点中的每一个保存在解缓冲器中的至少一个解，并且输出所获取的解。例如，控制单元51可以优先输出能量小的解。控制单元51可以将获取的解转换成组合优化问题的解的格式，例如，以将转换后的解的内容显示在与控制设备50连接的显示器上，或者将转换后的解的内容发送给连接至网络60的计算机，例如客户端计算机。[0256]此外，虽然示出了在控制设备50中提供控制单元51的功能的示例，但是节点100、200……中的任何一个均可以具有控制单元51的功能。例如，节点100、200……中的任何一个的cpu可以通过执行存储在节点的ram中的程序来运用控制单元51的功能。[0257]注意，可以通过使处理单元12执行程序来实现根据第一实施方式的信息处理。此外，可以通过使cpu 101执行程序来实现根据第二实施方式的信息处理。该程序可以记录在计算机可读记录介质61中。[0258]例如，可以通过分发记录有程序的记录介质61来分发程序。替选地，程序可以存储在另一计算机中并通过网络分发。例如，计算机可以将记录在记录介质61中或从另一计算机接收的程序存储(安装)在诸如ram 102或hdd 103的存储设备中，从存储设备读取程序，并且执行程序。









图片声明：本站部分配图来自人工智能系统AI生成,觅知网授权图片,PxHere摄影无版权图库。本站只作为美观性配图使用,无任何非法侵犯第三方意图,一切解释权归图片著作权方,本站不承担任何责任。如有恶意碰瓷者,必当奉陪到底严惩不贷!




内容声明：本文中引用的各种信息及资料（包括但不限于文字、数据、图表及超链接等）均来源于该信息及资料的相关主体（包括但不限于公司、媒体、协会等机构）的官方网站或公开发表的信息。部分内容参考包括:(百度百科,百度知道,头条百科,中国民法典,刑法,牛津词典,新华词典,汉语词典,国家院校,科普平台)等数据,内容仅供参考使用,不准确地方联系删除处理！本站为非盈利性质站点,发布内容不收取任何费用也不接任何广告!




免责声明：我们致力于保护作者版权，注重分享，被刊用文章因无法核实真实出处，未能及时与作者取得联系，或有版权异议的，请联系管理员，我们会立即处理，本文部分文字与图片资源来自于网络，部分文章是来自自研大数据AI进行生成,内容摘自(百度百科,百度知道,头条百科,中国民法典,刑法,牛津词典,新华词典,汉语词典,国家院校,科普平台)等数据,内容仅供学习参考,不准确地方联系删除处理!的,若有来源标注错误或侵犯了您的合法权益，请立即通知我们，情况属实，我们会第一时间予以删除，并同时向您表示歉意,谢谢!