Parallel Processing for Solution Space Partitions

摘要

Systems, devices, methods, and computer-readable media are disclosed for utilizing group theoretic techniques to enable data exchange between a supervisory central processing unit (CPU) and a group of graphical processing units (GPUs). The CPU may be configured to utilize a tabu search metaheuristic to explore a solution space to determine an optimal solution to an optimization problem. More specifically, the CPU may determine a fragmentation of a solution space that yields multiple partitions of the solution space and may assign each partition to a respective GPU configured to calculate a computational result. The CPU may then determine a new fragmentation of the solution space based on the computational results received from the GPUs that yields new partitions of the solution space and may assign each new partition to a respective GPU configured to again generate a computational result based on its assigned new partition. The CPU may continue to determine new fragmentations based on the computational results of the GPUs until stopping criteria are satisfied and a timely, high-quality solution to the optimization problem is determined.

主权项

1. A method, comprising:
determining a set of variables associated with an optimization problem; determining a function associated with the optimization problem, wherein the function is to be optimized based at least in part on the set of variables; determining an initial solution to the optimization problem, wherein determining the initial solution comprises determining an initial set of values of the set of variables and determining an initial value of the function based at least in part on the initial set of values; determining a neighborhood of solutions associated with the initial solution; selecting a first solution in the neighborhood of solutions as a current solution of the optimization problem; determining one or more additional solutions to the optimization problem based at least in part on the current solution, wherein the at least first solution is determined by a first graphical processing unit (GPU) and at least a second solution is determined by a second GPU different from the first GPU, and wherein the determining further comprises allocating to the first solution for determination by the first GPU and the allocating the second solution for determination by the second GPU; including the one or more additional solutions in a set of elite solutions; and determining that a second solution in the set of elite solutions is a final solution to the optimization problem, wherein determining that the second solution is a final solution comprises:
determining a final set of values of the set of variables, the final set of values being associated with the second solution;determining a final value of the function based at least in part on the final set of values; anddetermining that the final value of the function optimizes the function for each solution in the set of elite solutions.