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

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