Programming model for transparent parallelization of combinatorial optimization

• US 8,417,689 B1
• Filed: 11/21/2011
• Issued: 04/09/2013
• Est. Priority Date: 11/21/2011
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Waas, Florian, Soliman, Mohamed, Krikellas, Konstantinos
• Primary Examiner(s): THAI, HANH B
• Application Number:
  US13/301,722
• Time in Patent Office: 505 Days
• Field of Search: 707/713, 707/718, 707/770, 707/966, 718/100, 718/103, 718/106
• US Class Current: 707/713
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 9/54 Interprogram communication

Abstract

Each of a plurality of subtasks is configured to explore and assess alternative solutions for a combinatorial optimization problem by a reentrant finite state machine is represented. Each of a plurality of threads is configured to perform operations comprising a subtask until either completion or a blocked state is reached and, in the event a blocked state is reached, to move on to performing another subtask that is not currently in a blocked state.

Claims

1. A method, comprising:

representing each of a plurality of subtasks configured to explore optimization alternatives for a combinatorial optimization problem by a reentrant finite state machine;

representing a space of optimization alternatives for a combinatorial optimization problem by a recursive data structure, wherein the reentrant finite state machine includes a state to store a solution to the given subtask in the data structure;

using a processor to assign a first subtask of the plurality of subtasks to a first processing thread, and a second subtask of the plurality of subtasks to a second processing thread;

determining that processing a current state of a first state machine associated with the first subtask is in a blocked condition that cannot be completed until the second subtask has been completed; and

suspending the first state machine for future reentrance and making the first processing thread available to perform a third subtask not currently in the blocked condition.

2. The method of claim 1, wherein suspending the first subtask comprises storing a current state of the reentrant finite state machine associated with the first subtask.

3. The method of claim 1, further comprising representing a space of optimization alternatives for a combinatorial optimization problem by a recursive data structure, wherein a solved subtask is represented only once in the data structure.

4. The method of claim 1, further comprising representing a space of optimization alternatives for a combinatorial optimization problem by a recursive data structure, wherein the reentrant finite state machine includes a state to indicate that the solution to the given subtask has been identified.

5. The method of claim 1, wherein the reentrant finite state machine includes a state to generate one or more subdivided subtasks for a given subtask.

6. The method of claim 1, wherein the combinatorial optimization problem is received in a single-thread view.

7. The method of claim 1, wherein the combinatorial optimization problem is determining an efficient query execution plan for a database query.

8. The method of claim 7, wherein the query execution plan is represented as a query plan tree whose nodes correspond to query operators.

9. The method of claim 8, wherein a space of optimization alternatives is encoded in a recursive data structure that represents a set of sub-goals of the query execution plan, wherein each sub-goal corresponds to a node in the query plan tree.

10. The method of claim 9, wherein a space of optimization alternatives is encoded in a data structure that represents each sub-goal as a group comprising alternative primitives.

11. The method of claim 10, wherein the reentrant finite state machine includes a first state to iterate on child groups of primitives, and a subsequent second state to operate on the primitive itself.

12. A system, comprising:

a processor; and

a memory coupled with the processor, wherein the memory is configured to provide the processor with instructions which when executed cause the processor to;

represent each of a plurality of subtasks configured to explore optimization alternatives for a combinatorial optimization problem by a reentrant finite state machine;

represent a space of optimization alternatives for a combinatorial optimization problem by a recursive data structure, wherein a solved subtask is represented only once in the data structure;

assign a first subtask of the plurality of subtasks to a first processing thread, and a second subtask of the plurality of subtasks to a second processing thread;

determine that processing a current state of a first state machine associated with the first subtask is in a blocked condition that cannot be completed until the second subtask has been completed; and

suspend the first state machine for future reentrance and making the first processing thread available to perform a third subtask not currently in the blocked condition.

13. The system of claim 12, wherein the combinatorial optimization problem is determining an efficient query execution plan for a database query.

14. A computer program product, the computer program product being embodied in a tangible computer readable storage medium and comprising computer instructions for:

representing each of a plurality of subtasks configured to explore optimization alternatives for a combinatorial optimization problem by a reentrant finite state machine;

representing a space of optimization alternatives for a combinatorial optimization problem by a recursive data structure, wherein a solved subtask is represented only once in the data structure;

assigning a first subtask of the plurality of subtasks to a first processing thread, and a second subtask of the plurality of subtasks to a second processing thread;

determining that processing a current state of a first state machine associated with the first subtask is in a blocked condition that cannot be completed until the second subtask has been completed; and

suspending the first state machine for future reentrance and making the first processing thread available to perform a third subtask not currently in the blocked condition.

15. The computer program product of claim 14, wherein the combinatorial optimization problem is determining an efficient query execution plan for a database query.