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

                                                     - 31 -



    t
  S≤ s =
                      ts                 =
                                                  1
                                                        .                         (4)
     tp    f × t s + (1 − f )× t s / n          ⎛1− f ⎞
                                             f +⎜     ⎟
                                                ⎝ n ⎠

                                                                     1
  Анализ выражения (4) показывает (т.к. lim S ( f , n ) =              ), что только при
                                                              n →∞   f
малой доли последовательной операций (f<<1) возможно достичь значитель-
ного (естественно, не более чем в n раз) ускорения вычислений (рис.5). В
случае f=0,5 ни при каком (даже бесконечно большом) количестве процессо-
                                                   ров невозможно достичь
                                                   S>2! Заметим, что эти
                                                   ограничения носят фун-
                                                   даментальный     харак-
                                                   тер (их нельзя обойти
                                                   для заданного алгорит-
                                                   ма), однако практиче-
                                                   ская оценка доли f по-
                                                   следовательных опера-
                                                   ций априори обычно не-
                                                   возможна.
                                                     Таким образом каче-
                                                   ственные характеристи-
      Рисунок 4 — Схема к выводу закона Амдаля     ки самого алгоритма на-
                                                   кладывают ограничения
на возможное ускорение при распараллеливании. Например, характерные для
инженерных расчетов алгоритмы счета по последовательным формулам рас-
параллеливаются плохо (часть f значима), в то же время сводимые к задачам
линейного программирования (ЛП – операции с матрицами – умножение, об-
ращение, нахождение собственных значений, решение СЛАУ – систем ли-
нейных алгебраических уравнений и т.п.) алгоритмы распараллеливаются
удовлетворительно.
  Априорно оценить долю последовательных операций f непросто (само по-
нятие ‘последовательных’ и ‘параллельных’ операций трудноформализируе-
мо и допускает неоднозначные толкования). Однако можно попробовать
формально использовать формулу Амдаля для решения обратной задачи –
определения f по экспериментальным данным производительности; это дает
возможность количественно судить о достигнутой эффективности распа-
раллеливания.