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

                                   - 18 -


выходу элемента называется глубиной (depth) этого элемента (глубина схемы
равна наибольшей из глубин составляющих ее элементов).
  Теорема Брента утверждает (доказательство в вышецитируемой работе),
что при моделировании работы схемы глубиной d и размером п с ограничен-
ными входными степенями элементов с использованием CREW-алгоритма на
р процессорах достаточно (т.е. не выше) времени O(n/p+d). Выражение O(f)
говорит, что скорость роста сложности алгоритма ограничена функцией f.
  На рис.1 приведен результат моделирования схемы размером (общее коли-
чество процессоров) n=15 при глубине схемы (максимальное число элемен-
тов на каждом из уровней глубины) d=5 с числом процессоров p=2 (одновре-
менно моделируемые элементы объединены в группы прямоугольными об-
ластями, причем для каждой группы указан шаг, на котором моделируются ее
элементы; моделирование происходит последовательно сверху вниз в поряд-
ке возрастания глубины, на каждой глубине по p штук за раз). Согласно тео-
ремы Брента моделирования такой схемы на CREW-машине займет не более
ceil(15/2+1)=9 шагов.
  Там же показано, что выводы Брента верны и для моделирования схем на
EREW-машине (при условии, что выходные степени всех элементов также
ограничены сверху).

  1.2.3 Способы параллельной обработки данных,
        погрешность вычислений

   Возможны следующие режимы выполнения независимых частей про-
граммы:

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