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

                                   - 15 -


альных параллельных машинах такого, конечно, не бывает, поскольку моду-
ли памяти на физическом уровне упорядочивают доступ к одной и той же
ячейке памяти. Более того, время доступа к памяти на реальных машинах не-
одинаково из-за наличия кэшей и возможной иерархической организации
модулей памяти.
  Базовая модель PRAM поддерживает конкуррентные (в данном контексте -
параллельные) считывание и запись (CRCW, Concurrent Read, Concurrent
Write). Известны подмодели PRAM, учитывающие правила, позволяющие
избежать конфликтных ситуаций при одновременном обращении нескольких
процессоров к общей памяти:

  • Параллельное считывание при параллельной записи (CRCW, Concurrent
    Read, Concurrent Write) – данные каждой ячейки памяти в любой момент
    времени могут считываться и записываться параллельно любыми про-
    цессорами.
  • Параллельное считывание при исключительной записи (CREW, Concur-
    rent Read, Exclusive Write) - из каждой ячейки памяти в любой момент
    времени данные могут считываться параллельно любыми процессорами,
    но записываться только одним процессором.
  • Параллельное считывание при исключительной записи (ERCW, Exclusive
    Read, Concurrent Write) - из каждой ячейки памяти в любой момент вре-
    мени данные могут считываться только одним процессором, однако запи-
    сываться параллельно несколькими.
  • Исключительное считывание при исключительной же записи (EREW,
    Exclusive Read, Exclusive Write) - каждая ячейка памяти в любой момент
    времени доступна только одному процессору.

  Эти модели более ограничены (и, само собой, более реалистичны), однако
и их трудно реализовать на практике. Даже же при этом модель PRAM и ее
подмодели полезны для анализа и сравнения параллельных алгоритмов. Вер-
сией модели PRAM с обменом сообщениями является BPRAM.
  В модели массового синхронного параллелизма BSP (Valiant, 1990) син-
хронизация отделена от взаимодействия и учтены влияния иерархии памяти
и обмена сообщениями. Модель BSP включает три компонента:

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