Information processing system, information processing method, and computer-readable recording medium storing program

Patent metadata

Field	Value
Publication number	US-2022261669-A1
Application number	US-202117512730-A
Country	US
Kind code	A1
Filing date	Oct 28, 2021
Priority date	Feb 17, 2021
Publication date	Aug 18, 2022
Grant date	—

Abstract

A system configured to search for solutions to a problem represented by an energy function containing state variables, the system including: nodes to which each subproblem divided from the problem is separately assigned, each node being configured to: search for the solutions by updating one of the state variables belonging to a state variable group including a part of the state variables; hold the solutions found by the search; transmit one of the solutions to another node; receive another one of the solutions from the another node; and update, based on the another one of the solutions, the solutions held by the own node in accordance with a rule, wherein a part of a first state variable group assigned to a first node from among the state variables overlaps with at least a part of a second state variable group assigned to a second node from among the state variables.

First claim

What is claimed is:

1 . An information processing system configured to search for solutions to a problem represented by an energy function that contains a plurality of state variables, the information processing system comprising:
a plurality of nodes to which a plurality of subproblems generated by dividing the problem is separately assigned, each of the plurality of nodes being configured to: search for one of the solutions by updating a value of one of the state variables that belongs to a state variable group assigned in correspondence with one of the subproblems assigned to an own node, the state variable group being a group that includes partial state variables of the plurality of state variables; hold a plurality of the solutions found by the search; transmit at least one of the solutions among the plurality of the solutions held by the own node to another node; receive another one of the solutions transmitted by the another node; and update, based on the another one of the solutions received from the another node, at least a part of the plurality of the solutions held by the own node in accordance with a solution update rule of the own node, wherein a part of a first state variable group overlaps with at least a part of a second state variable group, the first state variable group being a group assigned to a first node among the plurality of nodes from among the plurality of state variables, the second state variable group being a group assigned to a second node among the plurality of nodes from among the plurality of state variables.

2 . The information processing system according to claim 1 , wherein
a portion of the first state variable group that does not overlap with the second state variable group overlaps with at least a part of a third state variable group assigned to a third node among the plurality of nodes from among the plurality of state variables.

3 . The information processing system according to claim 1 , wherein
a part of a portion of the first state variable group that does not overlap with the second state variable group overlaps with at least a part of a third state variable group assigned to a third node among the plurality of nodes from among the plurality of state variables.

4 . The information processing system according to claim 1 , wherein
each of a plurality of portions of the state variable group assigned to each of the plurality of nodes overlaps with a part of another state variable group assigned to any node that is the another node among the plurality of nodes.

5 . The information processing system according to claim 1 , wherein
a number of the state variables that belong to the first state variable group is different from a number of the state variables that belong to the second state variable group.

6 . The information processing system according to claim 1 , further comprising
a control circuit configured to assign the state variable group that includes a number of the state variables according to a memory size available for each of the plurality of nodes to search for the solutions, to each of the plurality of nodes.

7 . The information processing system according to claim 1 , further comprising
a control circuit configured to assign the plurality of subproblems to the plurality of nodes, and when the search for the solutions by each of the plurality of nodes and the transmission and the reception of the solutions between the nodes are repeatedly performed for a particular period of time, acquires at least one of the solutions among the plurality of the solutions held by each of the plurality of nodes to output the acquired one of the solutions.

8 . A computer-implemented method of searching for solutions to a problem represented by an energy function that contains a plurality of state variables, the method comprising:
by each of a plurality of nodes to which a plurality of subproblems generated by dividing the problem is separately assigned, searching for one of the solutions by updating a value of one of the state variables that belongs to a state variable group assigned in correspondence with one of the subproblems assigned to an own node, the state variable group being a group that includes partial state variables of the plurality of state variables; holding a plurality of the solutions found by the search; transmitting at least one of the solutions among the plurality of the solutions held by the own node to another node; receiving another one of the solutions transmitted by the another node; and updating, based on the another one of the solutions received from the another node, at least a part of the plurality of the solutions held by the own node in accordance with a solution update rule of the own node, wherein a part of a first state variable group overlaps with at least a part of a second state variable group, the first state variable group being a group assigned to a first node among the plurality of nodes from among the plurality of state variables, the second state variable group being a group assigned to a second node among the plurality of nodes from among the plurality of state variables.

9 . A non-transitory computer-readable storage medium storing a program of searching for solutions to a problem represented by an energy function that contains a plurality of state variables, the program comprising instructions which, when the program is executed by each of a plurality of nodes to which a plurality of subproblems generated by dividing the problem is separately assigned, cause each of the plurality of nodes to perform processing, the processing comprising:
searching for one of the solutions by updating a value of one of the state variables that belongs to a state variable group assigned in correspondence with one of the subproblems assigned to an own node, the state variable group being a group that includes partial state variables of the plurality of state variables; holding a plurality of the solutions found by the search; transmitting at least one of the solutions among the plurality of the solutions held by the own node to another node; receiving another one of the solutions transmitted by the another node; and updating, based on the another one of the solutions received from the another node, at least a part of the plurality of the solutions held by the own node in accordance with a solution update rule of the own node, wherein a part of a first state variable group overlaps with at least a part of a second state variable group, the first state variable group being a group assigned to a first node among the plurality of nodes from among the plurality of state variables, the second state variable group being a group assigned to a second node among the plurality of nodes from among the plurality of state variables.

Assignees

• Fujitsu Ltd

Inventors

• Matsubara Satoshi

Classifications

• G06N5/01 Primary

  Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound · CPC title

• G06N7/01

  Probabilistic graphical models, e.g. probabilistic networks · CPC title

• G06F13/1673

  using buffers · CPC title

• G06N10/00 Primary

  Quantum computing, i.e. information processing based on quantum-mechanical phenomena · CPC title

• G06N5/043 Primary

  Distributed expert systems; Blackboards · CPC title