Processing system, processing method, and processing program

Patent metadata

Field	Value
Publication number	US-2024184626-A1
Application number	US-202318520404-A
Country	US
Kind code	A1
Filing date	Nov 27, 2023
Priority date	Nov 29, 2022
Publication date	Jun 6, 2024
Grant date	—

Abstract

A processing system includes a parallel processing processor in which threads is constructed for each of blocks, and that optimizes a combination of binary variables under a one-hot constraint. A group variable is defined with a combination pattern satisfying the one-hot constraint as a solution candidate for each of groups of the binary variables. The parallel processing processor executes assigning the solution candidate of the group variable for each of the threads in each of the blocks, searching for an output value of the group variable in each of the blocks, and outputting the output value of all the group variables having been searched.

First claim

What is claimed is:

1 . A processing system comprising
a parallel processing processor in which a plurality of threads is constructed for each of a plurality of blocks, and that is configured to optimize a combination of binary variables under a one-hot constraint, wherein when a group variable is defined with a combination pattern satisfying the one-hot constraint as a solution candidate for each of groups of the binary variables, the parallel processing processor is configured to execute
assigning the solution candidate of the group variable for each of the threads in each of the blocks,
searching for an output value of the group variable on a basis of an energy evaluation value for the solution candidate of the group variable assigned for each of the threads in each of the blocks, and
outputting the output value of all the group variables having been searched.

2 . The processing system according to claim 1 , wherein
assigning the solution candidate includes assigning, for each of the threads, the solution candidate in which the combination pattern satisfying the one-hot constraint is expressed as an integer by a multi bit index for each of the groups of the binary variables in each of the blocks.

3 . The processing system according to claim 1 , wherein
assigning the solution candidate includes repeating processing of assigning the solution candidate of an identical group variable for each of the threads for all the group variables in each of the blocks.

4 . The processing system according to claim 1 , wherein
searching for the output value includes searching for the output value by update processing based on the energy evaluation value and a transition probability for the solution candidate of the group variable assigned to each of the threads in each of the blocks.

5 . The processing system according to claim 4 , wherein
searching for the output value includes updating the output value from the solution candidate for each of the threads in which a difference in the energy evaluation value from before the update processing and the transition probability corresponding to the difference are acquired in accordance with simulated annealing in each of the blocks.

6 . The processing system according to claim 4 , wherein
searching for the output value includes
updating the output value from the solution candidate for each of the threads in which the difference in the energy evaluation value from before the update processing and the transition probability corresponding to the difference are acquired in each of the blocks set as a replica of different temperatures, and
exchanging the output values for which an exchange condition based on the energy evaluation value is satisfied between the blocks of adjacent temperatures in accordance with a replica exchange method.

7 . The processing system according to claim 5 , wherein
searching for the output value includes acquiring the solution candidate in which the difference in the energy evaluation value is the largest in a negative direction as an update value for searching for the output value in each of the blocks.

8 . The processing system according to claim 7 , wherein
searching for the output value includes comparing, in each of the blocks, an integrated probability obtained by integrating the transition probability with a uniformly distributed random number probability for a limited number of the solution candidates from a high probability side of the transition probability among the solution candidates in which the difference in the energy evaluation value is positive, and continuing to search for the output value by using, as the update value, the solution candidate of the transition probability adopted as the uniformly distributed random number probability among the limited number of the solution candidates in a case where the integrated probability exceeds the uniformly distributed random number probability.

9 . The processing system according to claim 1 , further comprising
a host processing processor, wherein the host processing processor is configured to execute
inputting, to the parallel processing processor, the group variable in which the combination pattern satisfying the one-hot constraint for each of the groups of the binary variables is the solution candidate, and
outputting a solution in which the combination pattern of the binary variables is optimized to satisfy the one-hot constraint for each of the groups by mapping the output values of all the group variables output from the parallel processing processor.

10 . A processing method of optimizing a combination of binary variables under a one-hot constraint by a parallel processing processor in which a plurality of threads is constructed for each of a plurality of blocks, the processing method comprising:
when a group variable is defined with a combination pattern satisfying the one-hot constraint as a solution candidate for each of groups of the binary variables, assigning the solution candidate of the group variable for each of the threads in each of the blocks; searching for an output value of the group variable on the basis of an energy evaluation value for the solution candidate of the group variable assigned for each of the threads in each of the blocks; and outputting the output value of all the group variables having been searched.

11 . A non-transitory computer readable storage medium storing a processing program comprising a command that is stored in the storage medium to optimize a combination of binary variables under a one-hot constraint and is executed by a parallel processing processor in which a plurality of threads is constructed for each of a plurality of blocks,
wherein when a group variable is defined with a combination pattern satisfying the one-hot constraint as a solution candidate for each of groups of the binary variables, the command includes
assigning the solution candidate of the group variable for each of the threads in each of the blocks,
searching for an output value of the group variable on the basis of an energy evaluation value for the solution candidate of the group variable assigned for each of the threads in each of the blocks, and
outputting the output value of all the group variables having been searched.

Assignees

• Denso Corp

Inventors

• Miki Akira

Classifications

• G06F17/11

  for solving equations {, e.g. nonlinear equations, general mathematical optimization problems (optimization specially adapted for a specific administrative, business or logistic context G06Q10/04)} · CPC title

• G06F17/18 Primary

  for evaluating statistical data {, e.g. average values, frequency distributions, probability functions, regression analysis (forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04)} · CPC title

• G06F9/4881 Primary

  Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues · CPC title