О частичной синхронизации итерационных методов

Аннотация

Темпы развития многопроцессорной вычислительной техники способствуют исследованию параллельных алгоритмов, среди которых немаловажную роль играют метод Монте-Карло и асинхронные итерации. Выгодной особенностью таких алгоритмов является отсутствие необходимости наличия глобального времени в многопроцессорной системе (отсутствие синхронизации) и эффективность загрузки имеющихся вычислительных ресурсов (отсутствие простоя процессоров). В работе развивается и обобщается на нелинейный случай предложенный ранее авторами метод частичной синхронизации итераций при решении систем уравнений вида x = F (x), где x - неизвестный вектор-столбец длины n, а F - оператор из Rn в Rn. Рассматриваются такие операторы F, для которых не выполнено достаточное условие сходимости асинхронных итераций, но при этом сходятся простые итерации. В этом случае можно указать пример оператора и свойства вычислительной системы, при которых асинхронные итерации будут расходиться. При этом эффективным решением может стать частичная синхронизация. Предложен алгоритм, обеспечивающий сходимость асинхронных итераций и метода Монте-Карло для указанного класса операторов. Оценивается скорость сходимости метода. Результаты могут быть полезны при решении больших задач на многопроцессорных вычислительных комплексах. Библиогр. 4 назв.