Параллельные вычисления. Баканов В.М. - 16 стр.

                                    - 16 -


  Параметрами модели являются число процессоров и их скорость, стои-
мость взаимодействия и период синхронизации. Вычисление в BSP состоит
из последовательности сверхшагов. На каждом отдельном сверхшаге процес-
сор выполняет вычисления, которые обращаются к локальной памяти и
отправляет сообщения другим процессорам. Сообщения являются запросами
на получение копии (операция чтения) или на обновление (запись) удален-
ных данных. В конце сверхшага процессоры выполняют барьерную
синхронизацию и только затем обрабатывают запросы, полученные в течение
данного сверхшага; далее процессоры переходят к выполнению следующего
сверхшага.
  Первоначально предложенная в качестве интересной абстрактной модели,
BSP позднее стала моделью программирования. Напр., в Оксфордском уни-
верситете (http://www.osc.ox.ac.uk) реализована библиотека взаимодействия и
набор протоколирующих инструментов, основанные на модели BSP. Эта
библиотека содержит около 20 функций, в которых поддерживается постули-
руемый BSP-стиль обмена сообщениями и удаленный доступ к памяти. Под-
модель E-BSP является расширением BSP, учитывающая несбалансирован-
ность схем взаимодействия.
  Более современной является модель LogP (David Culler, 1996), т.к. она
учитывает характеристики машин с распределенной памятью и содержит
больше деталей, связанных со свойствами выполнения в коммуникационных
сетях, нежели модель BSP. Процессы в LogP рассматриваются как асинхрон-
ные, а не синхронные. Компонентами модели являются процессоры, локаль-
ная память и соединительная сеть; свое название модель получила от про-
писных букв своих параметров:

  • L - верхняя граница задержки (Latency) при передаче от одного процессо-
    ра к другому сообщения, состоящего из одного слова.
  • о - накладные расходы (overhead), которые несет процессор при передаче
    сообщения (в течение этого промежутка времени процессор не может вы-
    полнять иные операции).
  • g - минимальный временной интервал (gap) между последовательными
    отправками или получениями сообщений в процессоре.
  • Р - число пар ‘процессор-память’.

  Единицей измерения времени является длительность основного цикла про-
цессоров. Предполагается, что длина сообщений невелика, а сеть имеет ко-
нечную пропускную способность.
  Модель LogP описывает свойства выполнения в коммуникационной сети,
но абстрагируется от ее структуры. Таким образом она позволяет моделиро-
вать взаимодействие в алгоритме, но не дает возможности промоделировать
время локальных вычислений. Такое ограничение модели было принято по-