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

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

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. В данном случае переименование не требует действительной операции копирования, а может быть выполнено с помощью заменяющего имени или соответствующего распределения регистров. Однако в других случаях переименование может потребовать копирования.

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

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

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