Современные высокопроизводительные компьютеры


Обнаружение и устранение зависимостей компилятором и разворачивание циклов - часть 5


Эти зависимости приведут к ожиданию операторами S3 и S4 завершения оператора S1.

  • Имеется антизависимость от S1 к S2.

  • Имеется зависимость по выходу от S1 к S4.

    Следующая версия цикла устраняет эти ложные (или псевдо-) зависимости.

    for (i=1;i<=100;i=i+1) {

    /* Y переименовывается в T для устранения

    зависимости по выходу */

    T[i] = X[i] / c;

    /* X переименовывается в X1 для устранения

    антизависимости */

    X1[i] = X[i] + c;

    Z[i] = T[i] + c;

    Y[i] = c - T[i];

    }

    После цикла переменная X оказалась переименованной в X1. В коде программы, следующем за циклом, компилятор просто может заменить имя X на имя X1. В данном случае переименование не требует действительной операции копирования, а может быть выполнено с помощью заменяющего имени или соответствующего распределения регистров. Однако в других случаях переименование может потребовать копирования.

    Анализ зависимостей является важнейшей технологией для улучшения использования параллелизма. На уровне команд она дает информацию, необходимую для изменения в процессе планирования порядка обращений к памяти, а также для определения полезности разворачивания цикла. Для обнаружения параллелизма уровня цикла анализ зависимостей является базовым инструментом. Эффективная компиляция программ для векторных машин, а также для мультипроцессоров существенно зависит от этого анализа. Кроме того, при планировании потока команд полезно определить, являются ли потенциально зависимыми обращения к памяти. Главный недостаток анализа зависимостей заключается в том, что он применим при ограниченном наборе обстоятельств, а именно к обращениям внутри одного гнезда циклов и использует аффинные функции индексов. Таким образом, имеется огромное многообразие ситуаций, при которых анализ зависимостей не может сообщить нам то, что мы хотели бы знать, а именно:

    • когда обращения к объектам выполняются с помощью указателей, а не индексов массива,

    • когда индексация массива осуществляется косвенно через другой массив, что имеет место при работе с разреженными массивами,




      Начало  Назад  Вперед



      Книжный магазин