 ПОЗНАВАТЕЛЬНОЕ Сила воли ведет к действию, а позитивные действия формируют позитивное отношение Как определить диапазон голоса - ваш вокал Игровые автоматы с быстрым выводом Как самому избавиться от обидчивости Противоречивые взгляды на качества, присущие мужчинам Вкуснейший "Салат из свеклы с чесноком" Натюрморт и его изобразительные возможности Применение, как принимать мумие? Мумие для волос, лица, при переломах, при кровотечении и т.д. Как научиться брать на себя ответственность Зачем нужны границы в отношениях с детьми? Световозвращающие элементы на детской одежде Как победить свой возраст? Восемь уникальных способов, которые помогут достичь долголетия Классификация ожирения по ИМТ (ВОЗ) Глава 3. Завет мужчины с женщиной
Оси и плоскости тела человека - Тело человека состоит из определенных топографических частей и участков, в которых расположены органы, мышцы, сосуды, нервы и т.д.
| Понятие о векторизации программ
Рассмотрим второй уровень параллелизма – параллелизм на уровне циклов. Данный уровень соответствует векторной обработкеданных, т.е. обработке данных, представленных в виде векторов. Под вектором обычно понимают некоторый упорядоченный набор данных, размещенных в памяти регулярным образом. Примерами векторов в программах могут служить строки, столбцы, диагонали, массивы целиком, в то же время, например, поддиагональная часть двумерной матрицы вектором не является. Некоторый фрагмент программы может быть обработан в векторном режиме, если для его выполнения могут быть использованы векторные команды. Поиск таких фрагментов в программе и их замена на векторные команды называется векторизацией программы. Векторные команды – такие команды, которые выполняются над всеми элементами вектора одновременно. В противоположность векторным командам, команды, работающие с обычными данными (не векторами) называются скалярными. Типичным векторизуемым фрагментом программы может служить цикл с независимыми итерациями, например for( i = 0; i < N; ++i) A[i] = B[i] + C[i]; Выполнение данного цикла на скалярном процессоре будет выглядеть следующим образом. На каждой итерации цикла будут производиться следующие действия: · выборка из памяти операнда B[i]; · выборка из памяти операнда C[i]; · сложение B[i]и C[i]; · запись в память по адресу A+i результата сложения. Число итераций в этом случае будет равно N. Теперь допустим, что указанная программа будет выполнена на процессоре, поддерживающим команды, оперирующие с векторами-массивами данных длиной L. Итерации цикла из нашего примера примут следующий вид: · выборка из памяти векторного операнда, содержащего элементы с B[i]поB[i+L]; · выборка из памяти векторного операнда, содержащего элементы с C[i]поC[i+L]; · сложение векторных операндов; · запись в память по адресам с A+i по A+i+L результата сложения. Всего понадобится не более чем Задача векторизации программ возлагается на компилятор, транслирующий программу для исполнения на векторном процессоре. Следует заметить, что далеко не каждый цикл может быть векторизован. Основными препятствиями для векторизации могут являться следующие условия: 1. Зависимость итераций по данным. Примером может служить следующий фрагмент: for( i = 1; i < Imax; ++i) A[i] = B[i] + A[i-1]; В данном цикле в каждой итерации в качестве операнда используется значение, вычисленное в предыдущей итерации. Зависимости по данным могут иметь место быть и между разными операторами тела цикла. 2. Отсутствие регулярно расположенных векторов. В следующем примере индекс массива для второго операнда вычисляется на каждой итерации цикла: for( i = 0; i < Imax; ++i) { j = calc_index(i); A[i] = B[j] + A[i]; }
Кроме этого, векторизация невозможна: · когда обращения к объектам выполняются с помощью указателей, а не индексов массива; · когда индексация массива осуществляется косвенно через другой массив, что имеет место при работе с разреженными массивами. 3. Вызов неизвестных подпрограмм и функций:
for( i = 0; i < Imax; ++i) func(i);
Следует заметить, что в некоторых случаях зависимости по данным в процессе анализа кода могут быть найдены и устранены. При этом проверка зависимостей может оказаться очень сложной, но в принципе возможной во время компиляции. В общем же случае задача определения действительного наличия зависимостей является NP-полной. Однако на практике многие частые случаи могут быть точно проанализированы при вполне умеренных затратах. Кроме определения наличия зависимостей, компилятор старается также классифицировать тип зависимости. Это позволяет компилятору распознать зависимости по именам и устранить их путем переименования и копирования. Рассмотрим основные типы зависимостей и способы их устранения. 1. Истинные зависимости по данным между итерациями цикла. Например, возьмем следующий цикл:
for( i = 1; i <= Imax; i++ ) { A[i+1] = A[i] + C[i]; /* оператор S1 */ B[i+1] = B[i] + A[i+1]; /* оператор S2 */ }
Если предположить, что A, B и C являются неперекрывающимися массивами, то между операторами этого цикла можно обнаружить две истинных зависимости: 1. Операторы S1 и S2 используют значение, которое было вычислено на более ранней итерации, поскольку итерации i вычисляют A[i+1] и B[i+1], которые считываются в итерации i+1. 2. Оператор S2 использует значение A[i+1], которое вычисляется оператором S1 в той же самой итерации. Выявленные две зависимости отличаются друг от друга и имеют различный эффект. Рассмотрим зависимость оператора S1 от его более ранней итерации. Ее наличие означает, что между различными итерациями цикла существует зависимость по данным. Кроме того, поскольку оператор S1 зависит от самого себя, то последовательные итерации оператора S1 должны выполняться упорядоченно. Нетрудно видеть, что подобная зависимость по данным между итерациями делает векторизацию цикла невозможной. Вторая зависимость (оператора S2 от оператора S1) не передается от итерации к итерации. Поэтому при наличии подобного типа зависимостей можно сделать цикл векторизуемым при условии, что каждая пара операторов в итерации выполняется в определенном порядке. Покажем эту возможность на примере следующего цикла.
for( i = 1; i <= Imax; ++i ) { A[i] = A[i] + В[i]; /* оператор S1 */ B[i+1] = С[i] + D[i]; /* оператор S2 */ } В этом примере оператор S1 использует значение, которое присваивается оператором S2 в предыдущей итерации. Таким образом, здесь имеется зависимость между итерациями операторов S1 и S2. Несмотря на имеющиеся зависимости, этот цикл можно сделать векторизуемым, т.к. здесь ни один из операторов S1 и S2 не зависит сам от себя. Поэтому указанный цикл можно представить в следующем виде: A[1] = A[1] + В[1]; for( i = 1; i <= Imax-1; ++i) { B[i+1] = С[i] + D[i]; A[i+1] = A[i+1] + В[i+1]; } B[Imax+1]=С[Imax]+D[Imax]; 2. Истинные зависимости с расстоянием.Часто зависимости между итерациями цикла появляются в форме рекуррентного отношения, при этом некоторые рекуррентные отношения могут быть источником значительной степени параллелизма. Например, рассмотрим цикл:
for ( i = k+1; i <= Imax; ++i) Y[i] = Y[i-k] + Y[i]; На итерации j цикл обращается к элементу j-k. Говорят, что цикл имеет зависимость с расстоянием k. Чем больше расстояние, тем больше степень потенциального параллелизма, которую можно получить при помощи разворачивания цикла. Например, если мы разворачиваем цикл, имеющий зависимость с расстоянием 1, последовательные операторы зависят друг от друга. Если мы разворачиваем цикл, который имеет зависимость с расстоянием k, то имеется последовательность из k команд, которые не имеют зависимостей и могут быть векторизованы. Хотя многие циклы с зависимостями между итерациями имеют расстояние зависимостей 1, случаи с большими расстояниями в действительности возникают достаточно часто. Большее расстояние между зависимостями может обеспечивать большую степень векторизации. Далее рассмотрим два типа так называемых ложных (или псевдо-) зависимостей. 3. Зависимости по выходу. В этом случае цикл содержит несколько последовательных операторов, изменяющих один и тот же элемент массива. Параллельное выполнение этих операторов может привести к конфликту вида «запись после записи». Примером зависимости по выходу может являться следующий цикл:
for( i = 1; i <= Imax; ++i ) { A[i] = B[i] + d; /* оператор S1 */ … A[i] = C[i] / k; /* оператор S2 */ }
В данном примере имеется зависимость по выходу от S1 к S2. Для устранения зависимостей по выходу используется прием переименования переменных. Приведенный цикл изменяется следующим образом:
for( i = 1; i <= Imax; ++i ) { D[i] = B[i] + d; /* A переименовывается в D */ … A[i]=C[i]/k; /* зависимость по выходу устранена*/ }
4. Антизависимость проявляется, когда значение элемента массива, используемое в качестве операнда одним из операторов цикла, изменяется в последующих операторах, что делает невозможным параллельное исполнение этих операторов. Устранение антизависимости также осуществляется с помощью переименования переменных. К качестве комплексного примера приведем следующий цикл, имеющий несколько типов зависимостей. Найдем все истинные зависимости, зависимости по выходу и антизависимости и устраним зависимости по выходу и антизависимости с помощью переименования.
for( i = 1; i <= Imax; ++i ) { Y[i] = X[i] / c; /* оператор S1 */ X[i] = X[i] + c; /* оператор S2 */ Z[i] = Y[i] + c; /* оператор S3 */ Y[i] = c - Y[i]; /* оператор S4 */ }
В этих четырех операторах имеются следующие зависимости: 1. Имеются истинные зависимости от S1 к S3 и от S1 к S4 из-за Y[i]. Эти зависимости приведут к ожиданию операторами S3 и S4 завершения оператора S1. Тем не менее, отсутствуют истинные зависимости между различными итерациями цикла, что делает возможным его векторизацию. 2. Имеется антизависимость от S1 к S2из-за X[i]. Значение X[i] изменяется в S2, но при этом используется в качестве операнда в S1. 3. Имеется зависимость по выходу от S1 к S4, т.к. Y[i]изменяется в обоих этих операторах. Следующая версия цикла устраняет выявленные зависимости.
for (i = 1; i <= Imax; ++i ) { /* 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. В данном случае переименование не требует операции копирования, а может быть выполнено с помощью заменяющего имени или соответствующего распределения регистров. Однако в других случаях переименование может потребовать копирования. Анализ зависимостей является важнейшей технологией для повышения степени параллелизма и для обнаружения параллелизма уровня цикла является базовым инструментом. От этого анализа существенно зависит эффективность компиляции программ для векторных машин и мультипроцессоров.
|
итерация цикла.