Microsoft Corporation
Parallel search in program synthesis

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.