Параллелизм и конвейеризация в ступенях КС.
Параллелизм и конвейеризация, основные направления повышения производительности КС при ограничении на возможности подъема тактовой частоты и практически касаются и операционных блоков и устройств управления.
Параллелизм — это возможность одновременного выполнения более одной операции над данными или адресами. Возможность параллельного выполнения этих операций определяется правилом Рассела.
Объекты A и B (команды, операторы, программы) являются независимыми и могут выполняться параллельно, если выполняется следующее условие: [(In(B) ^ Out(A)) ˇ (In(A) ^ Out(B)) ˇ (Out(A) ^ Out(B))] = Ø, (2.1)
где In(A) — набор входных, а Out(A) — набор выходных переменных объекта A. Если условие не выполняется, то между A и B существует зависимость, и они не могут выполняться параллельно. Если условие нарушается в первом терме, то такая зависимость называется прямой. Если условие нарушено во втором терме, то такая зависимость называется обратной. Наконец, если условие не выполняется в третьем терме, то такая зависимость называется конкуренционной.
К основным формам параллелизма относят: естественный или векторный параллелизм; параллелизм независимых ветвей; параллелизм смежных операций или скалярный параллелизм.
Мелкозернистый (скалярный) параллелизм
При исполнении программы регулярно встречаются ситуации, когда исходные данные для i-й операции существовали всегда или вырабатываются заранее, например, при выполнении (i - к)-й операции. Тогда при соответствующем построении вычислительной системы можно совместить во времени выполнение i-й операции с выполнением (i - 1)-й, (i - 2)-й, ... операций (смещение менее к). В таком понимании скалярный параллелизм похож на параллелизм независимых ветвей, однако они отличаются длиной ветвей и требуют разных ядер процессора.
Скалярный параллелизм обычно работает автоматически под управлениием диспетчера процессора. Как правило, поддерживается и параллельная проверка условия Рассела. При его нарушении отменяется выполнение не распараллеливаемой команды, для сохранения предыдущего результата вводят виртуальные регистры, отображающие основные и хранящие результаты выполнения программ.
Крупнозернистый параллелизм.
Векторный параллелизм (естественный параллелизм). Вектор — одномерный массив, который образуется из многомерного массива, если один из индексов не фиксирован и пробегает все значения в диапазоне его изменения (координаты в фазовых пространствах и т.п.). Блок MMX и специализированные векторные процессоры примеры реализации векторных архитектур.
Параллелизм независимых ветвей. Если в задаче выделены независимые участки программ — ветви, они могут выполняться на различных процессорах.
Параллелизм вариантов.Это путь ускорения одной и той же модели при разных входных параметрах.
Параллелизм вариантов отличается от идеологии крупнозернистого параллелизма. Отличие состоит в том, что в случае крупнозернистого параллелизма вычисления проводятся внутри одной задачи и требования к скорости обмена между частями задачи достаточно высокие. В параллелизме вариантов распараллеливаются целые задачи, обмен между которыми в принципе отсутствует.
Закон Амдала. Одной из главных характеристик параллельных систем является ускорение R решения задач в параллельных системах. Оно определяется выражением: R = T1 /Tn ,
где T1 − время решения задачи на однопроцессорной системе, а Tn − время решения той же задачи на n − процессорной системе.
Пусть W = Wск + Wпр, где W − общее число операций в задаче, Wпр − число операций, которые можно выполнять параллельно, а Wcк − число скалярных (нераспараллеливаемых) операций. Обозначим также через t время выполнения одной операции. Это довольно грубое ограничение. Тогда получаем известный закон Амдала
Здесь a = Wск /W − удельный вес скалярных операций, n - число процессоров.
Сетевой закон Амдала. Основной вариант закона Амдала не отражает потерь времени на межпроцессорный обмен сообщениями. Эти потери могут не только снизить ускорение вычислений, но и замедлить вычисления по сравнению с однопроцессорным вариантом. Поэтому необходима некоторая модернизация выражения.
Введем переменные - Wc − количество передач данных, tc − время одной передачи данных и получим сетевой закон Амдала:
Конвейеризация
Конвейеризация (или конвейерная обработка) в общем случае основана на разделении подлежащей исполнению функции на более мелкие части, называемые ступенями, и выделении для каждой из них отдельного блока аппаратуры. Так обработку любой машинной команды можно разделить на несколько этапов (несколько ступеней), организовав передачу данных от одного этапа к следующему. При этом конвейерную обработку можно использовать для совмещения этапов выполнения разных команд. Производительность при этом возрастает благодаря тому, что одновременно на различных ступенях конвейера выполняются несколько команд. Конвейерная обработка такого рода широко применяется во всех современных быстродействующих процессорах.
Конвейеризация увеличивает пропускную способность процессора (количество команд, завершающихся в единицу времени), но она не сокращает время выполнения отдельной команды. В действительности, она даже несколько увеличивает время выполнения каждой команды из-за накладных расходов, связанных с добавлением конвейерных регистров. Однако общее увеличение пропускной способности означает, что программа будет выполняться быстрее по сравнению с простой неконвейерной схемой.
Конвейерные регистры к длительности такта добавляют время установки и задержку распространения сигналов.
Диаграмма работы простейшего конвейера при 8-ми элементном векторе данных.
| Номер такта/ данные | ||||||||||||
| Д( i) | IF | ID | EX | MEM | WB | |||||||
| Д(i+1) | IF | ID | EX | MEM | WB | |||||||
| Д(i+2) | IF | ID | EX | MEM | WB | |||||||
| Д(i+3) | IF | ID | EX | MEM | WB | |||||||
| Д(i+4) | IF | ID | EX | MEM | WB | |||||||
| Д(i+5) | IF | ID | EX | MEM | WB | |||||||
| Д(i+6) | IF | ID | EX | MEM | WB | |||||||
| Д(i+7) | IF | ID | EX | MEM | WB |
Конвейеризация эффективна только тогда, когда загрузка конвейера
близка к полной, а скорость подачи новых команд и операндов соответствует максимальной производительности конвейера. Если произойдет задержка, то параллельно будет выполняться меньше операций и суммарная производительность снизится. Такие задержки могут возникать в результате возникновения конфликтных ситуаций.
В качестве примера рассмотрим неконвейерную машину с пятью этапами выполнения операций, которые имеют длительность 2 нс каждая.
Пусть накладные расходы на организацию конвейерной обработки составляют 0,1 нс. Тогда среднее время выполнения команды в неконвейерной машине при 25 элементном входном векторе будет равно 2*5*25= 250 нс. Если же используется конвейерная организация, длительность такта будет равна длительности этапа обработки плюс накладные расходы, т.е. 2,1 нс. Это время соответствует среднему времени выхода глубоко конвейеризированных данных с конвейера. Таким образом, ускорение, полученное в результате конвейеризации, будет равно: Среднее время выполнения команды в конвейерном режиме 2,1*5+24*2.1=60,9 нс. Ускорение составило величину 4,1 раза. При глубоко конвейеризированных данных получим выигрыш в производительности 4,76 раза. В отличии от распаралеливания рост аппаратуры здесь существенно меньший, так как все ступени узко специализируются.
Задержки в работе конвейера, его аннулирование могут возникать в результате возникновения конфликтных ситуаций. Конфликты снижают реальную производительность конвейера, которая могла бы быть достигнута в идеальном случае. Отметим три типа конфликтов:
1. Структурные конфликты, которые возникают из-за конфликтов по ресурсам, когда аппаратные средства не могут поддерживать все возможные комбинации команд в режиме одновременного выполнения с совмещением.
2. Конфликты по данным, возникающие в случае, когда выполнение одной команды зависит от результата выполнения предыдущей команды.
3. Конфликты по управлению, которые возникают при конвейеризации команд переходов и других команд, которые изменяют значение счетчика команд.
Конфликты в конвейере приводят к необходимости приостановки
выполнения команд (pipeline stall). Обычно в простейших конвейерах, если приостанавливается какая-либо команда, то все следующие за ней команды также приостанавливаются. Команды, предшествующие приостановленной, могут продолжать выполняться, но во время приостановки не выбирается ни одна новая команда.
Пусть конвейерное устройство состоит из l ступеней, срабатывающих за один такт. Тогда, например, для сложения двух векторов из n элементов потребуется ( l + n- 1) тактов. Если при этом используются также векторные команды, то потребуется (возможно, несколько) σ дополнительных тактов для их инициализации. Эта величина учитывает также возможные пропуски тактов выдачи результатов на выходе конвейера, вследствие необходимости выполнения вспомогательных операций, связанных с организацией конвейера. С использованием введенных обозначений запишем соотношение для оценки производительности конвейера:
где τ – время такта работы компьютера. На рис. 7.1 приведен график зависимости производительности от n.
Рис. 7.1. Зависимость производительности конвейерного устройства от длины входного набора данных
Обычно КС строятся с использованием одновременно всех типов устройств: скалярных, векторных и конвейерных. В частности, первый векторно-конвейерный компьютер Cray-1 (пиковая производительность 160 Mflops) имел 12 конвейерных функциональных устройств, причем все функциональные устройства могли работать одновременно и независимо друг от друга. И любой современный компьютер сочетает конвейеризацию и параллелизм в своих основных блоках.