Целью настоящей работы служит определение следующих стратегий распараллеливания локального элиминационного алгоритма для разреженных задач дискретной оптимизации на основе использования современных вычислительных архитектур. Независимые подзадачи, соответствующие разным блокам, и подзадачи, соответствующие независимым ветвям обобщенного элиминационного дерева, могут решаться параллельно при помощи таких вычислительных архитектур, как многоядерные процессоры, графические процессоры (GPU) и GRID. Для параллельной реализации ЛЭА предлагается использовать гибридную схему мастер-рабочий, которая допускает одновременное использование CPU и GPU, причем GPU, множество основных параллельных машин с общей памятью, выступают в качестве рабочих процессоров и выполняют решение подзадач ДО для блоков, а CPU используется в качестве мастера. 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.