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

                                           - 73 -


чам (точное решение невозможно получить за разумное время). Однако и в
этом случае получение решения, значимо (в несколько раз) повышающее
производительность, является ценным и должно быть использовано.
  Усложняет проблему необходимость учета конвейерности, присущей
практически каждому современному процессору, причем в разной степени
(разработчиками заявлено, что процессор IBM Power5 способен выполнять за
такт четыре операции с плавающей точкой, процессоры AMD Opteron и Intel
Xeon EM64T - две операции с плавающей точкой за такт (*).
  Конечно, в реальности распараллеливание на уровне отдельных операто-
ров полезно в лучшем случае для параллельных компьютеров с общей памя-
тью (SMP-систем, многоядерных процессоров); рациональнее в роли отдель-
ного оператора рассматривать группу операторов, могущую выполняться по-
следовательно без обмена данными с другими (возможно, параллельно вы-
полняющимися) подобными группами команд (гранула, зерно распараллели-
вания, см. подраздел 1.3). Однако выявить гранулы (зерна) параллелизма
(вручную или автоматически) очень непросто.
  Одним из эмпирических методов проектирования алгоритмов наименьшей
высоты (с минимальным числом ярусов) является процесс сдваивания. Для
задачи вычисления произведений n чисел a1, a 2 ... a n алгоритм последователь-
ного вычисления для n=8 представляется так (по работе [1]):

     исходные данные: a1 a 2 a3 a 4 a5 a 6 a 7 a8
     ярус 1: a1 × a 2
     ярус 2: ( a1 a 2 ) × a 3
     ярус 3: ( a1 a 2 a 3 )× a 4
     ярус 4: ( a1 a 2 a 3 a 4 ) × a 5
     ярус 5: ( a1 a 2 a 3 a 4 a 5 )× a6
     ярус 6: ( a1 a 2 a 3 a 4 a 5 a6 ) × a7
     ярус 7: ( a1 a 2 a 3 a 4 a 5 a6 a7 ) × a 8

  Высота этой схемы (число ярусов) равна 7, ширина (число операций на
каждом ярусе) равна 1. Алгоритм может быть реализован на многопроцес-
сорной вычислительной системе, но все кроме одного процессоры будут про-
стаивать.
  Использование другого алгоритма решения той же задачи (используется
свойство ассоциативности умножения) приводит к схеме:

     исходные данные: a1 a 2 a3 a 4 a5 a 6 a 7 a8

*
    Антонов А.С. Далеко ли до пика? //Журнал ‘Открытые системы’, № 06, 2006.