Parallel Search in Program Synthesis
First Claim
1. A method for parallel scheduling in program synthesis, the method comprising operations performed using an electronic processor, the operations comprising:
- receiving a task to synthesize in a domain specific language (DSL);
synthesizing the task, wherein synthesizing of the task comprises;
generating a plurality of sub-goals based on the task, wherein the synthesized task comprises a solved subset of the plurality of the sub-goals;
determining an estimated completion time for each of the plurality of sub-goals, wherein each of the plurality of sub-goals is expressed using the DSL;
scheduling the plurality of the sub-goals based on the estimated completion time, wherein at least two of the plurality of the sub-goals are scheduled to be executed in parallel; and
solving the plurality of sub-goals based on the scheduling to synthesize the task in the DSL, wherein an elapsed real time to complete the synthesizing the task is reduced compared to scheduling the sub-goals in an order based on sub-goal generation.
1 Assignment
0 Petitions
Accused Products
Abstract
Systems, methods, and computer-executable instructions for parallel searching in program synthesis. A task to synthesize in a domain specific language (DSL) is received. The task is synthesized. Synthesizing the task includes generating sub-goals based on the task. The synthesized task includes a subset of the sub-goals. An estimated completion time for each of the sub-goals is expressed using the DSL is determined. The sub-goals are scheduled based on the estimated completion time. Some of the sub-goals are scheduled to be executed in parallel. The sub-goals are solved based on the scheduling to synthesize the task in the DSL. An elapsed real time to complete the synthesizing the task is reduced compared to scheduling the sub-goals in an order based on sub-goal generation.
21 Citations
20 Claims
-
1. A method for parallel scheduling in program synthesis, the method comprising operations performed using an electronic processor, the operations comprising:
-
receiving a task to synthesize in a domain specific language (DSL); synthesizing the task, wherein synthesizing of the task comprises; generating a plurality of sub-goals based on the task, wherein the synthesized task comprises a solved subset of the plurality of the sub-goals; determining an estimated completion time for each of the plurality of sub-goals, wherein each of the plurality of sub-goals is expressed using the DSL; scheduling the plurality of the sub-goals based on the estimated completion time, wherein at least two of the plurality of the sub-goals are scheduled to be executed in parallel; and solving the plurality of sub-goals based on the scheduling to synthesize the task in the DSL, wherein an elapsed real time to complete the synthesizing the task is reduced compared to scheduling the sub-goals in an order based on sub-goal generation. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
10. A system for parallel scheduling of sub-goals, the system comprising:
-
an electronic processor configured to receive a task to synthesize in a domain specific language (DSL); a parallelized synthesizer configured to synthesize the task, wherein to synthesize the task the parallelized synthesizer is configured to; generate a plurality of sub-goals based on the task, wherein the synthesized task comprises a subset of the plurality of the sub-goals; and determine an estimated completion time for each of the plurality of sub-goals, wherein each of the plurality of sub-goals is expressed using the DSL; and a scheduler configured to schedule the plurality of the sub-goals based on the estimated completion time, wherein some of the plurality of the sub-goals are scheduled to be executed in parallel on computing resources, and wherein an elapsed real time to complete the task synthesis is reduced compared to the sub-goals executed in an order based on sub-goal generation. - View Dependent Claims (11, 12, 13, 14, 15)
-
-
16. A computer-readable storage medium storing computer-executable instructions for parallel scheduling of sub-goals, the stored instructions comprising:
-
instructions to receive a task to synthesize in a domain specific language (DSL); instructions to synthesize the task, wherein the instructions to synthesize the task comprise; instructions to generate a plurality of sub-goals based on the task, wherein the synthesized task comprises a subset of the plurality of the sub-goals; and instructions to determine an estimated completion time for each of the plurality of sub-goals, wherein each of the plurality of sub-goals is expressed using the DSL; and instructions to schedule the plurality of the sub-goals based on the estimated completion time, wherein some of the plurality of the sub-goals are scheduled to be executed in parallel on computing resources, and wherein an elapsed real time to complete the task synthesis is reduced compared to the sub-goals executed in an order based on sub-goal generation. - View Dependent Claims (17, 18, 19, 20)
-
Specification