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

                                  - 14 -


менной работе выдают нужный результат за один-единственный такт ра-
боты вычислителя.
  Такие ‘многопроцессорные’ машины теоретически можно построить для
каждого конкретного алгоритма и, казалось бы, ‘обойти’ последо-
вательный характер алгоритмов. Однако не все так просто - конкретных
алгоритмов бесконечно много, поэтому развитые выше абстрактные рассу-
ждения имеют не столь прямое отношение к практической значимости. Их
развитие убедило в самой возможности распараллеливания, явилось основой
концепции неограниченного параллелизма, дало возможность рассматривать
с общих позиций реализацию т.н. вычислительных сред - многопроцессор-
ных систем, динамически настраиваемых под конкретный алгоритм.

  1.2.2 Абстрактные модели параллельных вычислений

  Модель параллельных вычислений обеспечивает высокоуровневый подход
к определению характеристик и сравнению времени выполнения различных
программ, при этом абстрагируются от аппаратного обеспечения и деталей
выполнения. Первой важной моделью параллельных вычислений явилась
машина с параллельным случайным доступом (PRAM, Parallel Random Ac-
cess Machine), которая обеспечивает абстракцию машины с разделяемой па-
мятью (PRAM является расширением модели последовательной машины с
произвольным доступом RAM - Random Access Machine). Модель BSP (Bulk
Synchronous Parallel, массовая синхронная параллельная) объединяет абст-
ракции как разделенной, так и распределенной памяти. В LogP моделируются
машины с распределенной памятью и некоторым способом оценивается
стоимость сетей и взаимодействия. Модель работы и глубины NESL основа-
на на структуре программы и не связана с аппаратным обеспечением, на ко-
тором выполняется программа.
  PRAM (Fortune, Wyllie, 1978) является идеализированной моделью син-
хронной машины с разделяемой памятью. Постулируется, что все процессо-
ры выполняют команды синхронно; в случае выполнения одной и той же ко-
манды PRAM является абстрактной SIMD-машиной, однако процессоры мо-
гут выполнять и различные команды. Основными командами являются счи-
тывание из памяти, запись в память и обычные логические и арифметиче-
ские операции.
  Модель PRAM идеализирована в том смысле, что каждый процессор в лю-
бой момент времени может иметь доступ к любой ячейке памяти (идеоло-
гема ‘Операции записи, выполняемые одним процессором, видны всем ос-
тальным процессорам в том порядке, в каком они выполнялись, но операции
записи, выполняемые разными процессорами, могут быть видны в произ-
вольном порядке’). Например, каждый процессор в PRAM может считывать
данные из ячейки памяти или записывать данные в эту же ячейку. На ре-