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

                                     - 83 -


                                                         Первым этапом рабо-
                                                      ты по распараллелива-
                                                      нию является выявление
                                                      зависимостей;    второй
                                                      шаг - распараллелива-
                                                      ние циклов с использо-
                                                      ванием      результатов
                                                      первого этапа. Примеры
                                                      автоматических (выпол-
                                                      няемых распараллели-
                                                      вающим компилятором)
                                                      эквивалентных преобра-
                                                      зований в применении к
                                                      циклам приведены ниже
 Рисунок 22 — Пространство итераций для фрагмента (7) в табл.6.
                                                         Если последователь-
                                                      ная программа содер-
жит два оператора S1 и S2, причем S1 находится перед S2, то говорят, что ме-
жду этими двумя операторами существует зависимость по данным, если они
считывают или записывают данные в общей области памяти таким образом,
что порядок их выполнения нельзя изменять без изменения конечного ре-
зультата вычислений. Имеются три основных типа зависимости по данным:

  • Потоковая  зависимость - оператор S2 потоково зависит от S1, если S2 счи-
    тывает из ячейки, в которую записывает S1 (такая зависимость называет-
    ся истинной).
  • Антизависимость - оператор S2 является антизависимым относительно S1,

    если S2 записывает в ячейку, из которой S1 считывает.
  • Зависимость по выходу - оператор S2 зависит по выходу от S1, если опе-

    ратор S2 записывает данные в ту же ячейку памяти, что и S1.

  Часто просто говорят ‘S2 зависит от S1’, если между ними существует за-
висимость по данным (тип зависимости не важен). Зависимости по данным
легко определяется в последовательном коде, содержащем ссылки только на
скаляры. Намного труднее определить зависимости в циклах и при ссылках
на массивы (что обычно встречается вместе), поскольку ссылки в массивы
имеют индексы, а в индексах часто используются параметры циклов, т.е. ин-
дексы массива имеют различные значения на разных итерациях цикла. Общая
проблема вычисления всех зависимостей по данным в программе неразре-
шима из-за синонимичности имен массивов, которая возникает при исполь-
зовании указателей или вызовов функций внутри индексных выражений. Да-