Тема_8_2010 Планирование работы конвейера (Лекции (ещё одни))

Тема 8: Планирование загрузки конвейера. Методикаразворачивания циклов.Параллелизм на уровне выполнения команд, планирование загрузки конвейера и методикаразворачивания циклов ................................................................................................................. 1Устранение зависимостей по данным и механизмы динамического планирования ............ 11Параллелизм на уровне выполнения команд, планирование загрузкиконвейера и методика разворачивания цикловВ предыдущих лекциях мы рассмотрели средства конвейеризации, которыеобеспечивают совмещенный режим выполнения команд, когда команды являютсянезависимыми друг от друга.

Это потенциальное совмещение выполнения командназывается параллелизмом на уровне команд.Далее рассмотрим ряд методов развития идей конвейеризации, основанныхна увеличении степени параллелизма, используемой при выполнении команд.Начнем с рассмотрения методов, позволяющих снизить влияние конфликтов поданным и по управлению, а затем вернемся к теме расширения возможностейпроцессора по использованию параллелизма, заложенного в программах. Затемобсудим современные технологии компиляторов, используемые для увеличениястепени параллелизма уровня команд.Среднее количество тактов для выполнения команды в конвейере можноопределить как:CPI конвейера = CPI идеального конвейера +Приостановки из-за структурных конфликтов +Приостановки из-за конфликтов типа RAW +Приостановки из-за конфликтов типа WAR +Приостановки из-за конфликтов типа WAW +Приостановки из-за конфликтов по управлениюCPI идеального конвейера есть не что иное, как максимальная пропускнаяспособность, достижимая при реализации.Уменьшая каждое из слагаемых в правой части выражения, минимизируемобщий CPI конвейера и таким образом увеличиваем пропускную способностькоманд.

Это выражение позволяет также охарактеризовать различные методысокращения CPI, по тому компоненту общего CPI, который соответствующийметод уменьшает.Укажем некоторые методы, которые рассмотрим ниже, и их воздействие навеличину CPI.1МетодРазворачивание цикловБазовое планирование конвейераСнижаетПриостановки по управлениюПриостановки RAWДинамической планирование сцентрализованной схемой управленияДинамическое планирование спереименованием регистровДинамическое прогнозирование переходовВыдача нескольких команд в одном тактеАнализ зависимостей компиляторомПрограммная конвейеризация и планированиетрассВыполнение по предположениюДинамическое устранение неоднозначностипамятиПриостановки RAWПриостановки WAR и WAWПриостановки по управлениюИдеальный CPIИдеальный CPI и приостановки поданнымИдеальный CPI и приостановки поданнымВсе приостановки по данным иуправлениюПриостановки RAW, связанные спамятьюПрежде, чем рассмотреть эти методы, необходимо определить концепции, накоторых эти методы построены.Параллелизм уровня команд: зависимости и конфликты по даннымВсе рассматриваемые методы используют параллелизм, заложенный впоследовательности команд.

Как было указано выше этот тип параллелизманазывается параллелизмом уровня команд или ILP.Рассмотрим базовый блок - линейная последовательность команд, переходыизвне которой разрешены только на ее вход, а переходы внутри которой разрешенытолько на ее выход.

Степень параллелизма, доступная внутри базового блокадостаточно мала. Например, средняя частота переходов в целочисленныхпрограммах составляет около 16%. Это означает, что в среднем между двумяпереходами выполняются примерно пять команд. Поскольку эти пять командвозможно взаимозависимые, то степень перекрытия, которую можно использоватьвнутри базового блока, возможно, будет меньше чем пять.

Чтобы получитьсущественное улучшение производительности, необходимо использоватьпараллелизм уровня команд одновременно для нескольких базовых блоков.Самый простой и общий способ увеличения степени параллелизма,доступного на уровне команд, является использование параллелизма междуитерациями цикла. Этот тип параллелизма часто называется параллелизмомуровня итеративного цикла. Ниже приведен простой пример цикла,выполняющего сложение двух 1000-элементных векторов, который являетсяполностью параллельным:2for (i = 1; i <= 1000; i = i + 1)x[i] = x[i] + y[i];Каждая итерация цикла может перекрываться с любой другой итерацией,хотя внутри каждой итерации цикла практическая возможность перекрытиянебольшая.Имеется несколько методов для превращения такого параллелизма уровняцикла в параллелизм уровня команд.

Эти методы основаны главным образом наразворачивании цикла либо статически, используя компилятор, либо динамическис помощью аппаратуры. Ниже рассмотрим подробный пример разворачиванияцикла.Важным альтернативным методом использования параллелизма уровнякоманд является использование векторных команд. По существу векторнаякоманда оперирует с последовательностью элементов данных. Например,приведенная выше последовательность на типичной векторной машине можетбыть выполнена с помощью четырех команд:• двух команд загрузки векторов x и y из памяти,• одной команды сложения двух векторов и• одной команды записи вектора-результата.Конечно, эти команды могут быть конвейеризованными и иметьотносительно большие задержки выполнения, но эти задержки могутперекрываться. (Векторные команды и векторные машины будут рассмотрены вотдельной лекции)Разработка идей векторной обработки предшествовала появлениюбольшинства методов использования параллелизма.

Но на сегодня машины,использующие параллелизм уровня команд постепенно заменяют машины,базирующиеся на векторной обработке.ЗависимостиЧтобы точно определить, что понимается под параллелизмом уровня цикла ипараллелизмом уровня команд, а также для количественного определения степенидоступного параллелизма, необходимо определить, что такое параллельныекоманды и параллельные циклы.Начнем с объяснения того, что такое пара параллельных команд. Двекоманды являются параллельными, если они могут выполняться в конвейереодновременно без приостановок, предполагая, что конвейер имеет достаточноресурсов (структурные конфликты отсутствуют).Поэтому, если между двумя командами существует взаимозависимость, то они неявляются параллельными. Имеется три типа зависимостей:• зависимости по данным,• зависимости по именам и• зависимости по управлению.3Зависимости по управлению сохраняются путем реализации схемы обнаруженияконфликта по управлению, которая приводит к приостановке конвейера поуправлению.

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

Мы обсудим коротко зависимости по именам. Анализ параллелизмауровня цикла фокусируется на определении того, зависят ли по данным обращенияк данным в последующей итерации от значений данных, вырабатываемых в болееранней итерации.Рассмотрим следующий цикл:for (i=1; i<=100; i=i+1){ A[i+1] = A[i] + C[i]; /* S1 */B[i+1] = B[i] + A[i+1];} /*S2*/}Предположим, что A, B и C представляют собой отдельные, неперекрывающиесямассивы.

Какие зависимости по данным имеют место между операторами этогоцикла?Имеются две различных зависимости:1. S1 использует значение, вычисляемое оператором S1 на более раннейитерации, поскольку итерация i вычисляет A[i+1], которое считывается витерации i+1.

То же самое справедливо для оператора S2 для B[i] и B[i+1].2. S2 использует значение A[i+1], вычисляемое оператором S1 в той же самойитерации.Эти две зависимости отличаются друг от друга и имеют различный эффект.Чтобы увидеть, чем они отличаются, предположим, что в каждый момент временисуществует только одна из этих зависимостей.