О распараллеливании локального элиминационного алгоритма

We introduce strategies for parallelizing a sequential local elimination algorithm for sparse discrete optimization problems. The local elimination procedure exploits the structure of the underlying problem graph using extended elimination tree. We propose to use hybrid Master-Worker scheme where worker processors (GPUs) solve concurrently subproblems corresponding to super-nodes of extended elimination tree that are generated by a single master process (CPU). Subproblem generation is embedded into an local elimination algorithm and takes previous subproblem solutions into account. The current state of parallel architectures and parallelization technics is discussed.