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

                                        - 76 -

       Результаты разработок использованы при создании системы V-Ray (разработка
     НИВЦ МГУ, http://parallel.ru/v-ray).

  В общем случае анализ имеющего m дуг графа алгоритма с целью выявле-
ния параллелизма (напр., выявление ярусов) требует порядка т 2 переборов,
при этом сам алгоритм выполняется (на однопроцессорном компьютере) за
пропорциональное m время. Т.о. время исследования структуры алгоритма с
целью выявления параллелизма значительно превышает время его выполне-
ния! Как показано в работе (∗), решение наиболее практически ценных вари-
антов задачи оптимального размещения операций по процессорам МВС тре-
бует числа переборов порядка m! для только одного набора входных данных
(т.е. по трудоемкости относится к NP-полным задачам и точное решение не-
возможно получить за разумное время).
   В большинстве (из огромного множества наработанных) последовательных
алгоритмов присутствует внутренний параллелизм (возможность представле-
ния алгоритма в параллельной форме при сохранении его вычислительных
свойств – численной устойчивости и др.), который может быть выявлен ме-
тодом построения и анализа графа алгоритма. В сложных случаях применя-
ются эквивалентные преобразования исходных алгоритмов. Графы алгорит-
мов для некоторых задач приведены в [1,3]. Для часто применяемых алго-
ритмов (напр., операции с матрицами) операции распараллеливания прове-
дены и соответствующие программы собраны в                     проблемно-
ориентированные библиотеки (пакеты).
   Практического использование выявленных возможностей распараллелива-
ния требует отображения графа алгоритма на конкретную многопроцессор-
ную вычислительную систему, для чего необходимо иметь описание МВС -
количественные параметры процессоров и коммуникационной среды (на
первом этапе анализа часто принимается одинаковое время выполнения лю-
бых вычислительных операций и мгновенный обмен данными между процес-
сорами, при учете времени обмена данными проводится анализ коммуника-
ционной трудоемкости параллельного алгоритма). Именно на этом этапе
можно определить:

    • Время выполнения параллельного алгоритма.
    • Ускорение (отношение времени решения задач на скалярной ЭВМ к вре-
      мени выполнения параллельного алгоритма).
    • Эффективность (величина, определяющая усредненную долю времени
      выполнения алгоритма, в течение которой процессоры на самом деле ис-
      пользуются для решения задачи).

∗
    Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. –М.: Мир,
     1982, -416 c.