Синхронные и асинхронные вычисления

  • 7 мин

На следующем рисунке показана модель массовых параллельных синхронных вычислений BSP.

The bulk synchronous parallel (BSP) model.

Рис. 8. Массовая синхронная параллельная модель

Независимо от используемой модели программирования, разработчик может задать распределенное вычисление как синхронное или асинхронное. Это различие относится к наличию или отсутствию (глобального) координационного механизма, который синхронизирует операции задач. Распределенная программа является синхронной, только если задачи компонентов работают в режиме заданного порядка. То есть для некоторой константы $(c \geq 1)$ если какая-либо задача прошла $(c + 1)$ шагов, то все остальные задачи должны пройти как минимум $c$ шагов1. В дальнейшем, если какая-либо задача пройдет $(c + 2)$ шагов, то все остальные задачи должны пройти по меньшей мере $(c + 1)$ шагов. Очевидно, что это ограничение требует создания координационного механизма, с помощью которого можно синхронизировать действия задач и обеспечить соблюдение времени их выполнения. Такие механизмы обычно оказывают значительное влияние на производительность. Как правило, в синхронных программах распределенные задачи должны ожидать завершения определенных вычислений или поступления определенных данных в предварительно определенных точках3. Программа, которая не является синхронной, называется асинхронной. В асинхронных программах нет требования к ожиданию поступления определенных данных в предварительно определенных точках. Вычислительная асинхронность в меньшей степени влияет на производительность, но предполагает необходимость оценки корректности или допустимости программы

Программы MapReduce и Pregel, например, используют синхронные вычисления, а программы GraphLab — асинхронные. Pregel применяет модель массовых параллельных синхронных вычислений BSP2, которая является синхронной моделью, обычно используемой для эффективной реализации распределенных программ. BSP объединяет три атрибута: компоненты, маршрутизатор и метод синхронизации. Компонент BSP состоит из процессора и данных, хранящихся в локальной памяти, но модель не исключает других возможностей, например хранения данных в удаленной памяти. BSP нейтрально относится к количеству процессоров, будь то два или миллион. Программы BSP можно написать для $v$ виртуальных распределенных процессоров для выполнения на $p$ физических распределенных процессорах, где $(v > p)$.

Модель BSP основана на модели программирования, отправляющей и получающей сообщения через маршрутизатор, который, в принципе, может передавать только сообщения "точка — точка" между парами компонентов. (Модель не предоставляет средств вещания, хотя разработчики могут реализовать их с помощью нескольких точечных коммуникаций.) Чтобы достичь синхронности, BSP разбивает все вычисления на последовательность шагов, называемых супер-шагами. На каждом супершаге $S$ каждому компоненту назначается задача для выполнения (локальных) вычислений. Компоненты на $S$ могут отправлять сообщения в компоненты $(c + 1)$ на супершаге $(S + 1)$, и им разрешено неявно получать сообщения от компонентов на супершаге $(S-1)$. На каждом супершаге задачи работают одновременно и не обмениваются данными друг с другом. Между супершагами задачи выполняются в режиме заданного порядка: задача на шаге $(S + 1)$ не может начинаться до завершения всех задач на супершаге $S$. Для соблюдения этого условия BSP применяет глобальную барьерную синхронизацию, как показано на рис. 8. Поскольку BSP не предоставляет одновременный доступ к одной ячейке памяти, этой модели не требуется какой-либо другой механизм синхронизации, кроме барьеров.

Еще одна основная проблема в распределенной системе заключается в выделении данных таким образом, чтобы вычисления не замедлялись неравномерными задержками доступа к памяти или неравномерной нагрузкой между отдельными задачами. BSP способствует равномерным задержкам доступа, используя локальные данные: данные передаются между супершагами до запуска реальных вычислений, и модель, таким образом, отделяет вычисления от обмена данными. Такое разделение означает, что ни одна конкретная топология сети не выходит за рамки требования обеспечить высокую пропускную способность. Допускаются топологии бабочки, гиперкуба и оптических координат.

Объемы данных между задачами в пределах супершага могут варьироваться, а загрузка задач в основном зависит от распределенной программы и обязанностей, которые она возлагает на входящие в нее задачи. Соответственно, время, необходимое для завершения супершага, определяется его самой медленной задачей. (Супершаговая задача не может зафиксироваться до завершения его самой медленной задачи.) Это ограничение представляет серьезную проблему для модели BSP, так как она может создать дисбаланс нагрузки, который обычно снижает производительность. Причиной неравномерного распределения нагрузки также могут быть разнородные кластеры, особенно в облаке. Обратите внимание, что, хотя модель BSP предлагает несколько проектных решений, она не делает их использование обязательным. Модель BSP позволяет применять множество решений по выбору (например, барьерная синхронизация может быть реализована с более высокой степенью детализации или полностью отключена, если она не требуется для данного приложения).

Ссылки

  1. A. S. Tanenbaum and M. V. Steen (October 12, 2006). Distributed Systems: Principles and Paradigms Prentice Hall, Second Edition
  2. L. G. Valiant (1990). A Bridging Model for Parallel Computation In Communications of the ACM
  3. D. P. Bertsekas and J. N. Tsitsiklis (January 1, 1997). Parallel and Distributed Computation: Numerical Methods Athena Scientific, First Edition