Booth Id:
SOFT029
Category:
Systems Software
Year:
2019
Finalist Names:
Vulakh, David (School: Paul Laurence Dunbar High School)
Abstract:
Combinatorial constraint satisfaction problems can be solved through the generalizable algorithm of recursive search with backtracking, which runs in nondeterministic polynomial time. In order to complete large cases more quickly, the computational resources of multiple cores and machines can be pooled. The goal of the project was to create a general distributed backtracking framework capable of solving any given constraint satisfaction problem by breaking it into independent subproblems and assigning these tasks to parallel worker programs located on several cores, locally and on other machines. Additional goals included production of log files, capability to restart from those files without loss of work, and visualization of search statistics. To accomplish this, a simple distribution program that solved a specific problem -- finding Costas Arrays of size M -- using the cores of one machine was created, and the desired features -- creation of log files, restart capability, visualizations, distribution of work using TCP connections, and generalization to more problems -- were incrementally added. The efficiency of the distribution process was evaluated by comparing the runtime of the resulting program to that of a single worker for the same problem and by finding the proportion of total computational resources used by processes other than workers. Both of these measures indicated that overhead processes, as a fraction of total resources used, declined as the size of the problem increased. This implies that overhead is, for the problem sizes tested, dominated by constant-time startup operations and will continue to decline asymptotically as problem size increases.
Awards Won:
Air Force Research Laboratory on behalf of the United States Air Force: First Award of $750 in each Intel ISEF Category
Raytheon Technologies Corporation: Each winning project will receive $3,000 in shares of UTC common stock.
Third Award of $1,000