Multi-threaded constraint satisfaction solver

• US 10,509,654 B2
• Filed: 08/09/2017
• Issued: 12/17/2019
• Est. Priority Date: 08/09/2017
• Status: Active Grant

• Current Assignee: Red Hat, Inc. (International Business Machines Corporation)
• Original Assignee: Red Hat, Inc. (International Business Machines Corporation)
• Inventors: De Smet, Geoffrey
• Primary Examiner(s): Dinh, Paul
• Application Number:
  US15/672,364
• Publication Number:
  US 20190050225A1
• Time in Patent Office: 860 Days
• Field of Search: 716103, 716132
• CPC Class Codes: G06F 15/80 comprising an array of processing units with common control, e.g. single instruction multiple data processors G06F15/82 takes precedence ; for correlation function computation G06F17/15
• CPC Class Codes: G06F 9/3009 Thread control instructions
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

An object-oriented method for multi-threading in a constraint satisfaction solver is provided. A master thread establishes a first solution state of a constraint problem. The master thread establishes a plurality of solver threads, each solver thread having an initial solution state that is identical to a first solution state of the master thread, and a plurality of cloned planning entity objects that are clones of a plurality of planning entity objects. The master thread communicates a first plurality of temporary incremental state changes to the plurality of solver threads that alters the initial solution state of each solver thread to a different solution state. The master thread receives, from each respective solver thread of the plurality of solver threads, a first score associated with the different solution state of the respective solver thread.

Claims

1. A method for multi-threading, comprising:

establishing, by a master thread executing on a computing device comprising a processor device, an initial solution state of a constraint problem, the initial solution state based at least in part on a collective state of a plurality of planning entity objects used to model the constraint problem;

establishing, by the master thread executing on the computing device, a plurality of solver threads, each solver thread having an initial solution state that is identical to the initial solution state of the master thread and having a plurality of cloned planning entity objects that are clones of the plurality of planning entity objects;

communicating, by the master thread executing on the computing device, a first plurality of temporary state changes to the plurality of solver threads that alters the initial solution state of each solver thread to a different solution state;

receiving, from each respective solver thread of the plurality of solver threads, a first score associated with the different solution state of the respective solver thread;

identifying, by the master thread executing on the computing device, a particular score received from a particular solver thread of the plurality of solver threads as a best score; and

implementing a permanent state change to the initial solution state of the master thread to generate a new solution state that matches a solution state associated with the particular score.

2. The method of claim 1 further comprising:

sending, by the master thread to each solver thread, the permanent state change that, when implemented by the solver thread, identifies a new solution state for each solver thread that matches the solution state associated with the particular score, wherein the new solution state of each solver thread is identical to one another.

3. The method of claim 2 further comprising:

communicating, by the master thread, a second plurality of temporary state changes to the plurality of solver threads that alters the new solution state of each solver thread to a different solution state, each solver thread receiving a different temporary state change; and

receiving, from each respective solver thread of the plurality of solver threads, a second score associated with the different solution state of the respective solver thread.

4. The method of claim 1 wherein communicating the first plurality of temporary state changes to the plurality of solver threads comprises:

generating a temporary move object that comprises;

a memory pointer to at least one planning entity object of the master thread; and

a change in a state of the at least one planning entity object; and

communicating the temporary move object to a first solver thread of the plurality of solver threads.

5. The method of claim 4 wherein communicating the first plurality of temporary state changes to the plurality of solver threads comprises:

generating a plurality of temporary move objects, each temporary move object comprising;

a memory pointer to at least one planning entity object of the master thread;

a change in a state of the at least one planning entity object;

wherein each temporary move object differs from other temporary move objects; and

communicating a different temporary move object to each of the plurality of solver threads.

6. The method of claim 4 further comprising:

accessing, by the first solver thread, the temporary move object;

determining, by the first solver thread, a corresponding cloned planning entity object that corresponds to the at least one planning entity object of the master thread; and

implementing the change in the state on the corresponding cloned planning entity object.

7. The method of claim 6 wherein determining the corresponding cloned planning entity object comprises:

accessing the at least one planning entity object of the master thread to determine a unique identifier (ID) of the at least one planning entity object; and

accessing a registry that correlates the unique ID of the at least one planning entity object of the master thread to the corresponding cloned planning entity object of the first solver thread.

8. The method of claim 6 wherein determining the corresponding cloned planning entity object comprises:

accessing, by the first solver thread, the at least one planning entity object of the master thread;

comparing, by the first solver thread, the at least one planning entity object of the master thread to the plurality of cloned planning entity objects of the solver thread; and

determining that the corresponding cloned planning entity object corresponds to the at least one planning entity object of the master thread based on the comparing step.

9. The method of claim 1 further comprising:

receiving, by a first solver thread, a first temporary state change of the first plurality of temporary state changes;

implementing, by the first solver thread, the first temporary state change to alter the initial solution state of the first solver thread to a different solution state;

scoring, by the first solver thread, the different solution state; and

undoing the first temporary state change to revert the different solution state back to a solution state immediately prior to implementing the first temporary state change.

10. The method of claim 1 wherein communicating the first plurality of temporary state changes to the plurality of solver threads comprises:

generating a temporary move object that comprises;

a first memory pointer to at least one planning entity object of the master thread;

a change in a state of at least one mutable planning entity object; and

a second memory pointer to an immutable fact object of the master thread;

communicating the temporary move object to a first solver thread of the plurality of solver threads.

11. The method of claim 10 comprising:

accessing, by the first solver thread, the temporary move object;

determining, by the first solver thread, a corresponding cloned planning entity object that corresponds to the at least one mutable planning entity object of the master thread; and

implementing the change in the state on the corresponding cloned planning entity object using the second memory pointer to the immutable fact object of the master thread.

12. The method of claim 1, wherein the master thread executes on a first host machine, and at least one solver thread executes on a second host machine.

13. The method of claim 1, wherein the master thread executes on a first host machine, and each solver thread executes on a different host machine.

14. The method of claim 1 further comprising:

receiving, by a first solver thread, a temporary state change of the first plurality of temporary state changes;

accessing a working score associated with a current solution state of the first solver thread;

determining a subset of cloned planning entity objects of the plurality of cloned planning entity objects that are altered by the temporary state change; and

determining a first score associated with the temporary state change based on the working score and a score delta associated with an implementation of the temporary state change on the subset of cloned planning entity objects.

15. A computing device comprising:

a memory; and

at least one processor device coupled to the memory to;

establish, via a master thread, an initial solution state of a constraint problem, the initial solution state based at least in part on a collective state of a plurality of planning entity objects used to model the constraint problem;

establish, by the master thread, a plurality of solver threads, each solver thread having an initial solution state that is identical to the initial solution state of the master thread, and having a plurality of cloned planning entity objects that are clones of the plurality of planning entity objects;

communicate, by the master thread, a first plurality of temporary state changes to the plurality of solver threads that alters the initial solution state of each solver thread to a different solution state;

receive, from each respective solver thread of the plurality of solver threads, a first score associated with the different solution state of the respective solver thread;

identify, by the master thread, a particular score received from a particular solver thread of the plurality of solver threads as a best score; and

implement a permanent state change to the initial solution state of the master thread to generate a new solution state that matches a solution state associated with the particular score.

16. The computing device of claim 15 wherein the at least one processor device is further to:

send, via the master thread to each solver thread, the permanent state change that, when implemented by the solver thread, identifies a new solution state for each solver thread that matches the solution state associated with the particular score, wherein the new solution state of each solver thread is identical to one another.

17. The computing device of claim 15 wherein to communicate the first plurality of temporary state changes to the plurality of solver threads, the at least one processor device is further to:

generate a temporary move object that comprises;

a memory pointer to at least one planning entity object of the master thread; and

a change in a state of the at least one planning entity object; and

communicate the temporary move object to a first solver thread of the plurality of solver threads.

18. A computer program product stored on a non-transitory computer-readable storage medium and including instructions to cause a processor device to:

establish, via a master thread, an initial solution state of a constraint problem, the initial solution state based at least in part on a collective state of a plurality of planning entity objects used to model the constraint problem;

establish, by the master thread, a plurality of solver threads, each solver thread having an initial solution state that is identical to the initial solution state of the master thread and having a plurality of cloned planning entity objects that are clones of the plurality of planning entity objects;

communicate, by the master thread, a first plurality of temporary state changes to the plurality of solver threads that alters the initial solution state of each solver thread to a different solution state;

receive, from each respective solver thread of the plurality of solver threads, a first score associated with the different solution state of the respective solver thread;

identify, by the master thread, a particular score received from a particular solver thread of the plurality of solver threads as a best score; and

implement a permanent state change to the initial solution state of the master thread to generate a new solution state that matches a solution state associated with the particular score.

19. The computer program product of claim 18 wherein the instructions further cause the processor device to:

send, via the master thread to each solver thread, the permanent state change that, when implemented by the solver thread, identifies a new solution state for each solver thread that matches the solution state associated with the particular score, wherein the new solution state of each solver thread is identical to one another.

20. The computer program product of claim 18 wherein to communicate the first plurality of temporary state changes to the plurality of solver threads, the instructions further cause the processor device to:

generate a temporary move object that comprises;

a memory pointer to at least one planning entity object of the master thread; and

a change in a state of the at least one planning entity object; and

communicate the temporary move object to a first solver thread of the plurality of solver threads.