19346

VLIW – ПРОЦЕССОРЫ. НЕТРАДИЦИОННЫЕ АРХИТЕКТУРЫ

Лекция

Информатика, кибернетика и программирование

АК ЛЕКЦИЯ № 23 VLIW – ПРОЦЕССОРЫ. Нетрадиционные архитектуры Вычислительные системы с командными словами сверхбольшой длины VLIW Архитектура с командными словами сверхбольшой длины или со сверхдлинными командами VLIW Very Long Instruction Word известна с начала 80х из ряда универ...

Русский

2013-07-11

354 KB

73 чел.

АК ЛЕКЦИЯ № 23 VLIW – ПРОЦЕССОРЫ. Нетрадиционные архитектуры

Вычислительные системы с командными словами сверхбольшой длины (VLIW)

Архитектура с командными словами сверхбольшой длины или со сверхдлинными командами (VLIW, Very Long Instruction Word) известна с начала 80-х из ряда университетских проектов, но только сейчас, с развитием технологии производства микросхем она нашла свое достойное воплощение. VLIW - это набор команд, организованных наподобие горизонтальной микрокоманды в микропрограммном устройстве управления.

Идея VLIW базируется на том, что задача эффективного планирования параллельного выполнения нескольких команд возлагается на «разумный» компилятор. Такой компилятор вначале исследует исходную программу с целью обнаружить все команды, которые могут быть выполнены одновременно, причем так, чтобы это не приводило к возникновению конфликтов. В процессе анализа компилятор может даже частично имитировать выполнение рассматриваемой программы. Наследующем этапе компилятор пытается объединить такие команды в пакеты, каждый из которых рассматривается так одна сверхдлинная команда. Объединение нескольких простых команд в одну сверхдлинную производится по следующим правилам:

- количество простых команд, объединяемых в одну команду сверхбольшой длины, равно числу имеющихся в процессоре функциональных (исполнительных) блоков (ФБ);

- в сверхдлинную команду входят только такие простые команды, которые исполняются разными ФБ, то есть обеспечивается одновременное исполнение всех составляющих сверхдлинной команды.

Длина сверхдлинной команды обычно составляет от 256 до 1024 бит. Такая метакоманда содержит несколько полей (по числу образующих ее простых команд), каждое из которых описывает операцию для конкретного функционального блока. Такая метакоманда содержит несколько полей (по числу образующих ее простых команд), каждое из которых описывает операцию для конкретного функционального блока.

Каждое поле сверхдлинной команды отображается на свой функциональный блок, что позволяет получить максимальную отдачу от аппаратуры блока исполнения команд.

VLIW-архитектуру можно рассматривать как статическую суперскалярную архитектуру. Имеется в виду, что распараллеливание кода производится на этапе компиляции, а не динамически во время исполнения. То, что в выполняемой сверхдлинной команде исключена возможность конфликтов, позволяет предельно упростить аппаратуру VLIW-процессора и, как следствие, добиться более высокого быстродействия.

В качестве простых команд, образующих сверхдлинную, обычно используются команды RISC-типа, поэтому архитектуру VLIW иногда называют nocтRISC-apхитектурой. Максимальное число полей в сверхдлинной команде равно числу вычислительных устройств и обычно колеблется в диапазоне от 3 до 20. Все вычислительные устройства имеют доступ к данным, хранящимся в едином многопортовом регистровом файле. Отсутствие сложных аппаратных механизмов, характерных для суперскалярных процессоров (предсказание переходов, внеочередное исполнение и т. д.), дает значительный выигрыш в быстродействии и возможность более эффективно использовать площадь кристалла. Подавляющее большинство цифровых сигнальных процессоров и мультимедийных процессоров с производительностью более 1 млрд операций/с базируется на VLIW-архитектуре. Серьезная проблема VLIW - усложнение регистрового файла и связей этого файла с вычислительными устройствами.

Вычислительные системы с явным параллелизмом команд (ЕРIC)

Дальнейшим развитием идеи VLIW стала новая архитектура IA-64 — совместная разработка фирм Intel и Hewlett-Packard (IA - это аббревиатура от Intel Architecture). В IA-64 реализован новый подход, известный как вычисления с явным параллелизмом команд (EPIC, Explicitly Parallel Instruction Computing) и являющийся усовершенствованным вариантом технологии VLIW. Первым представителем данной стратегии стал микропроцессор Itanium компании Intel.

В архитектуре IA-64 предполагается наличие в процессоре 128 64-разрядных регистров общего назначения (РОН) и 128 80-разрядных регистров с плавающей запятой. Кроме того, процессор IA-64 содержит 64 однобитовых регистра предикатов.

Предикация - это способ обработки условных ветвлений. Суть в том, что еще компилятор указывает, что обе ветви выполняются на процессоре параллельно, ведь EPIC-процессоры должны иметь много функциональных блоков.

Если в исходной программе встречается условное ветвление (по статистике — через каждые шесть команд), то команды из разных ветвей помечаются разными регистрами предиката (команды имеют для этого соответствующие поля), далее они выполняются совместно, но их результаты не записываются, пока значения регистров предиката (РП) не определены. Когда, наконец, вычисляется условие ветвления, РП, соответствующий «правильной» ветви, устанавливается в 1, а другой - в 0. Перед записью результатов процессор проверяет поле предиката и записывает результаты только тех команд, поле предиката которых указывает на РП с единичным значением.

Предикаты формируются как результат сравнения значений, хранящихся в двух регистрах. Результат сравнения («Истина» или «Ложь») заносится в один из РП, но одновременно с этим во второй РП записывается инверсное значение полученного результата. Такой механизм позволяет процессору более эффективно выполнять конструкции типа I F - T H E N-E L S E .

Логика выдачи команд на исполнение сложнее, чем в традиционных процессорах типа VLIW, но намного проще, чем у суперскалярных процессоров с неупорядоченной выдачей. По мнению специалистов Intel и HP, концепция EPIC, сохраняя все достоинства архитектурной организации VLIW, свободна от большинства ее недостатков. Особенностями архитектуры EPIC являются:

- большое количество регистров;

- масштабируемость архитектуры до большого количества функциональных блоков. Это свойство представители компаний Intel и HP называют наследственно масштабируемой системой команд (Inherently Scaleable Instruction Set);

- явный параллелизм в машинном коде. Поиск зависимостей между командами осуществляет не процессор, а компилятор;

- предикация — команды из разных ветвей условного предложения снабжаются полями предикатов (полями условий) и запускаются параллельно;

- предварительная загрузка — данные из медленной основной памяти загружаются заранее.

Общий итог обзора технологии VLIW можно сформулировать следующим образом.

Преимущества. Использование компилятора позволяет устранить зависимости между командами до того, как они будут реально выполняться, в отличие от суперскалярных процессоров, где такие зависимости приходится обнаруживать и устранять "на лету". Отсутствие зависимостей между командами в коде, сформированном компилятором, ведет к упрощению аппаратных средств процессора и за счет этого к существенному подъему его быстродействия. Наличие множества функциональных блоков дает возможность выполнять несколько команд параллельно.

Недостатки. Требуется новое поколение компиляторов, способных проанализировать программу, найти в ней независимые команды, связать такие команды в строки длиной от 256 до 1024 бит, обеспечить их параллельное выполнение. Компилятор должен учитывать конкретные детали аппаратных средств. При определенных ситуациях программа оказывается недостаточно гибкой.

Основные сферы применения. VLIW-процессоры пока еще распространены относительно мало. Основными сферами применения технологии VLIW-являются цифровые сигнальные процессоры и вычислительные системы, ориентированные на архитектуру IA-64. Наиболее известной была VLIW-система фирмы Multiflow Computer, Inc. (Уже не существующей.) В России VLIW-концепция была реализована в суперкомпьютере Эльбрус 3-1 и получила дальнейшее развитие в его последователе - Эльбрус-2000 (Е2к). К VLIW можно причислить семейство сигнальных процессоров TMS320C6x фирмы Texas Instruments. С 1986 года ведутся исследования VLIW-архитектуры в IBM. В начале 2000 года фирма Transmeta заявила процессор Crusoe, представляющий собой программно-аппаратный комплекс. В нем команды микропроцессоров серии х86 транслируются в слова VLIW длиной 64 или 128 бит. Оттранслированные команды хранятся в кэш-памяти, а трансляция при многократном их использовании производится только один раз. Ядро процессора исполняет элементы кода в строгой последовательности.

Потоковые и редукционные вычислительные системы

В традиционных ВМ команды в основном выполняются в естественной последовательности, то есть в том порядке, в котором они хранятся в памяти. То же самое можно сказать и о традиционных многопроцессорных системах, где одновременно могут выполняться несколько командных последовательностей, но также в порядке размещения каждой из них в памяти. Это обеспечивается наличием в каждом процессоре счетчика команд. Выполнение команд в каждом процессоре — поочередное и потому достаточно медленное. Для получения выигрыша программист или компилятор должны определить независимые команды, которые могут быть поданы на отдельные процессоры, причем так, чтобы коммуникационные издержки были не слишком велики.

Традиционные (фон-неймановские) вычислительные системы, управляемые с помощью программного счетчика, иногда называют вычислительными системами, управляемыми последовательностью команд (control flow computer). Данный термин особенно часто применяется, когда нужно выделить этот тип ВС из альтернативных типов, где последовательность выполнения команд определяется не центральным устройством управления со счетчиком команд, а каким-либо иным способом. Если программа, состоящая из команд, хранится в памяти, возможны следующие альтернативные механизмы ее исполнения:

- команда выполняется, после того как выполнена предшествующая ей команда последовательности;

- команда выполняется, когда становятся доступными ее операнды;

- команда выполняется, когда другим командам требуется результат ее выполнения.

Первый метод соответствует традиционному механизму с управлением последовательностью команд; второй механизм известен как управляемый данными (data driven) или потоковый (dataflow); третий метод называют механизмом управления по запросу (demand driven).

Вычислительные системы с управлением вычислениями от потока данных

Идеология вычислений, управляемых потоком данных (потоковой обработки), была разработана в 60-х гадах Карпом и Миллером. В начале 70-х годов Деннис, а позже и другие начали разрабатывать компьютерные архитектуры, основанные на вычислительной модели с потоком данных.

Вычислительная модель потоковой обработки. В потоковой вычислительной модели для описания вычислений используется ориентированный граф, иногда называемый графом потоков данных (dataflow graph).

Этот граф состоит из узлов или вершин, отображающих операции, и ребер или дуг, показывающих потоки данных между теми вершинами графа, которые они соединяют.

Узловые операции выполняются, когда по дугам в узел поступила вся необходимая информация. Обычно узловая операция требует одного или двух операндов, а для условных операции необходимо наличие входного логического значения. По выполнении операции формируются один или два результата. Таким образом, у каждой вершины может быть от одной до трех входящих дуг и одна или две выходящих. После активации вершины и выполнения узловой операции (это иногда называют инициированием вершины) результаты передаются по ребрам к ожидающим вершинам. Процесс повторяется, пока не будут инициированы все вершины и получен окончательный результат. Одновременно может быть инициировано несколько узлов, при этом параллелизм в вычислительной модели выявляется автоматически.

На рис. 15.2 показан простой потоковый граф для вычисления выражения f=А/В+ В x С. Входами служат переменные А, В и С, изображенные вверху графа. Дуги между вершинами показывают тракты узловых операций. Направление вычислений — сверху вниз. Используются три вычислительные операции: сложение, умножение и деление. Заметим, что В требуется в двух узлах. Вершина «Копирование»- предназначена для формирования дополнительной копии переменной В.

Данные (операнды/результаты), перемещаемые вдоль дуг, содержатся в опознавательных информационных кадрах, маркерах специального формата — «токенах» (иначе «фишках»- или маркерах доступа). Рисунок 15.3 иллюстрирует движение токенов между узлами.

После поступления на граф входной информации маркер, содержащий значение А, направляется в вершину деления; токен с переменной В — в вершину копирования; токен с переменной С — в вершину умножения. Активирована может быть только вершина «Копирование», поскольку у нее лишь один вход и на нем уже присутствует токен. Когда токены из вершины «Копирование»' будут готовы, узлы умножения и деления также получат все необходимые маркеры доступа и могут быть инициированы. Последняя вершина ждет завершения операций умножения и деления, то есть когда на ее входе появятся все необходимые токены.

Практические вычисления требуют некоторых дополнительных возможностей, например при выполнении команд условного перехода. По этой причине в потоковых графах предусмотрены вершины-примитивы нескольких типов (рис. 15.4)

- вершина слияния — узел с двумя входами и одним выходом. Данные поступают только с какого-нибудь одного из двух входов. Входные данные без изменения подаются на выход. Комбинируя такие узлы, можно строить вершины слияния с m входами;

- вершина управления — существует в перечисленных ниже трех вариантах:

- TF-коммутатор — узел с двумя входами и одним выходом. Верхний вход — это дуга данных, а правый — дуга управления (логические данные). Если значение правого входа истинно (Т — True), то входные данные выводятся через левый выход, а при ложном значении на правом входе (F — False) данные следуют через правый выход;

D вентиль — узел с двумя входами и одним выходом. Верхний вход — дуга дан-ных, а правый — дуга управления. При истинном значении на входе управления данные выводятся через выходную дугу;

- арбитр — узел с двумя входами и двумя выходами. Все дуги являются дуга-ми данных. Первые поступившие от двух входов данные следуют через левую дугу, а прибывшие впоследствии — через правую выходную дугу. Активация вершины происходит в момент прихода данных с какого-либо одного входа.

Процесс обработки может выполняться аналогично конвейерному режиму: пос-ле обработки первого набора входных сигналов на вход графа может быть подан второй и т. д. Отличие состоит в том, что промежуточные результаты (токены) первого вычисления не обрабатываются совместно с промежуточными результатами второго и последующих вычислений. Результаты обычно требуются в последовательности использования входов.

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

Все известные потоковые вычислительные системы могут быть отнесены к двум основным типам: статическим и динамическим. В свою очередь, динамические потоковые ВС обычно реализуются по одной из двух схем: архитектуре с помеченными токенами и архитектуре с явно адресуемыми токенами.

Архитектура потоковых вычислительных систем

В потоковых ВС программа вычислений соответствует потоковому графу, который хранится в памяти системы в виде таблицы.

Принципиальная схема потоковой вычислительной системы (рис. 15.7) включает в себя блок управления (CS), где хранится потоковый граф, который используется для выборки обрабатываемых команд, а также функциональный блок (FS), выполняющий команду, переданную из CS, и возвращающий результат ее выполнения в CS.

Блоки CS и FS работают асинхронно и параллельно, обмениваясь многочисленными пакетами команд и результатами их выполнения. В пакете результата, поступающем из блока FS, содержится значение результата (val) и адрес команды, для которой пакет предназначен (des). На основании этого адреса блок CS проверяет возможность обработки команды. Команда может быть однооперандной или двухоперандной. В последнем случае необходимо подтверждение наличия обоих операндов (орг 1 и орг 2), и для этого устанавливается специальный признак. Блок управления загрузкой (LC) каждый раз при активировании определенной функции загружает из памяти программ код этой функции.

Для повышения степени параллелизма блоки CS и F5 строятся по модульному принципу, а графы потоковой программы распределяются между модулями с помощью мультиплексирования.

Статические потоковые вычислительные системы

Статическая потоковая архитектура, известная также под названием «единственный-токен-на-дугу» (single-token-рег-агс dataflow), была предложена Денисом в 1975 году [89]. В ней допускается присутствие на ребре графа не более чем одного токена. Это выражается в правиле активации узла [90]: вершина активируется, когда на всех ее входных дугах присутствует по токену и ни на одном из ее выходов токенов нет. Для указания вершине о том, что ее выходной токен уже востребован последующим узлом (узлами) графа, в ВС обычно прибегают к механизму подтверждения с аквитированием связи, как это показано на рис. 15.8. Здесь процессорами в ответ на инициирование узлов графа посылаются специальные контрольные токены.

Типовая статическая потоковая архитектура показана на рис. 15.9.

Память действий (узел потоковой машины, хранящий потоковый граф и циркулирующий на нем поток данных) состоит их двух блоков памяти: команд/данных и управляющей памяти. Вершина графа представлена в памяти команд/данных кадром, содержащим следующие поля:

- код операции;

- операнд 1;

……

- операндN;

- вершина/дуга 1;

- ...

- вершина/дуга К.

Каждому кадру в памяти команд/данных соответствует кадр в управляющей памяти, содержащий биты наличия для всех операндов и всех полей «вершина/дуга». Бит наличия операнда устанавливается в единицу, если этот операнд доступен, то есть если токен, содержащий данный операнд, уже поступил по входной дуге графа. Для поля «вершина/дуга» установленный бит наличия означает, что выходная дуга, ассоциированная с данным полем, не содержит токена. Вершина графа, описанная в памяти команд/данных, может быть активирована (операция может быть выполнена), если все биты наличия в соответствующем кадре памяти управления установлены в единицу. Когда данная ситуация распознается блоком обновления, он помещает пакет команды в очередь команд. Опираясь на очередь команд и содержимое памяти действий, блок выборки составляет пакет операции и направляет его в один из функциональных блоков. После выполнения требуемой операции функциональный блок создает пакет результата и передает его в блок обновления, который в соответствии с полученным результатом изменяет содержимое памяти действий.

Основное преимущество рассматриваемой модели потоковых вычислений заключается в упрощенном механизме обнаружения активированных узлов. К сожалению, статическая модель обладает множеством серьезных недостатков [55]. Во-первых, данный механизм не допускает параллельного выполнения независимых итераций цикла. Другой нежелательный эффект — колебания трафика токенов. Наконец, в современных языках программирования отсутствует поддержка описанного режима обработки данных. Несмотря на это, несколько образцов статических ВС все-таки были созданы или, по крайней мере, спроектированы.

Динамические потоковые вычислительные системы

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

Архитектура потоковых систем с помеченными токенами

В архитектуре с помеченными токенами (tagged-token architecture) память хранит один экземпляр потокового графа. Каждый токен содержит тег (фишку), состоящий из адреса команды, для которой предназначено заключенное в токене значение, и другой информации, определяющей вычислительный контекст, в котором данное значение используется, например номера итерации цикла. Этот контекст называют «цветом значения» а токен соответственно называют «окрашенным»-, в силу чего метод имеет еще одно название — метод окрашенных токенов. Каждая дуга потокового графа может рассматриваться как вместилище, способное содержать произвольное число токенов с различными тегами. Основное правило активирования вершины в динамических потоковых ВС имеет вид: вершина активируется, когда на всех ее входных дугах присутствуют токены с идентичными тегами.

Основное преимущество динамических потоковых систем — это более высокая производительность, достигаемая за счет допуска присутствия на дуге множества токенов. При этом, однако, основной проблемой становится эффективная реализация блока, который собирает токены с совпадающим цветом (токены с одинаковыми тегами). В плане производительности этой цели наилучшим образом отвечает ассоциативная память. К сожалению, такое решение является слишком дорогостоящим, поскольку число токенов, ожидающих совпадения тегов, как правило, достаточно велико. По этой причине в большинстве вычислительных систем вместо ассоциативных запоминающих устройств (ЗУ) используются обычные адресные ЗУ.

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

Архитектура потоковых систем с явно адресуемыми токенами

Значительным шагом в архитектуре потоковых ВС стало изобретение механизма явной адресации токенов (explicit token-store), имеющего и другое название — непосредственное согласование (direct matching). В основе этого механизма лежит то, что все токены в одной и той же итерации цикла и в одном и том же вхождении в реентерабельную процедуру имеют идентичный тег (цвет). При инициализации очередной итерации цикла или очередном обращении к процедуре формируется так называемый кадр токенов, содержащий токены, относящиеся к данной итерации или данному обращению, то есть с одинаковыми тегами, Использование конкретных ячеек внутри кадра задается на этапе компиляции. Каждому кадру выделяется отдельная область в специальной памяти кадров (frame memory), причем раздача памяти под каждый кадр происходит уже на этапе выполнения программы.

В схеме с явной адресацией токенов любое вычисление полностью описывается указателем команды,(IP, Instruction Pointer) и указателем кадра (FP, Frame Pointer). Этот кортеж <FP, IP> входит в тег токена, а сам токен выглядит следующим образом: Значение • FP.IP.

Команды, реализующие потоковый граф, хранятся в памяти команд и имеют формат: Код операции • Индекс в памяти кадров • Адресат.

Здесь «Индекс в памяти кадров» определяет положение ячейки с нужным токеном внутри кадра, то есть какое число нужно добавить к FP, чтобы получить адрес интересующего токена. Поле –«Адресат» указывает на местоположение команды, которой должен быть передан результат обработки данного токена. Адрес в этом поле также задан в виде смещения числа, которое следует прибавить к текущему значению IP, чтобы получить исполнительный адрес команды назначения в памяти команд. Если потребителей токена несколько, в поле «Адресат» заносится несколько значений смещения.

Типовая архитектура системы с явной адресацией токенов показана на рис. 15.14. Отметим, что функция согласования токенов стала достаточно короткой операцией, что позволяет внедрить ее в виде нескольких ступеней процессорного конвейера.

Рис. 15.14. Структура процессорного элемента типовой потоковой системы с явной адресацией токенов

Макропотоковые вычислительные системы

Рассмотренный ранее механизм обработки с управлением от потока данных функционирует на уровне команд и его относят к потоковой обработке низкого уровня (fine-grain dataflow). Данному подходу сопутствуют большие издержки при пересылке операндов. Для уменьшения коммуникационных издержек необходимо применять потоковую обработку на процедурном уровне, так называемую укрупненную потоковую или макропотоковую обработку (multithreading). Буквальный перевод английского термина означает потоковую обработку множества нитей.

Макропотоковая модель совмещает локальность программы, характерную для фон-неймановской модели, с толерантностью к задержкам на переключение задач, свойственной потоковой архитектуре. Это достигается за счет того, что вершина графа представляет собой не одну команду, а последовательность из нескольких команд, называемых нитью (thread). По этой причине макропотоковую организацию часто именуют крупнозернистой потоковой обработкой (coarsegrained dataflow). Макропотоковая обработка сводится к потоковому выполнению нитей, в то время как внутри отдельной нити характер выполнения фон-неймановский. Порядок обработки нитей меняется динамически в процессе вычислений, а последовательность команд в пределах нити определена при компиляции статически. Структура макропотоковой ВС представлена на рис. 15.15.

Существенное отличие макропотоковой системы от обычной потоковой ВС состоит в организации внутреннего управляющего конвейера, где последовательность выполнения команд задается счетчиком команд, как в фон-неймановских машинах. Иными словами, этот конвейер идентичен обычному конвейеру команд.

Существуют две формы макропотоковой обработки: без блокирования и с блокированием, В модели без блокирования выполнение нити не может быть начато, пока не получены все необходимые данные. Будучи запущенной, нить выполняется до конца без приостановки. В варианте с блокированием запуск нити может быть произведен до получения всех операндов. Когда требуется отсутствующий операнд, нить приостанавливается (блокируется), а возобновление выполнения откладывается на некоторое время. Процессор запоминает всю необходимую информацию о состоянии и загружает на выполнение другую готовую нить. Модель с блокированием обеспечивает более мягкий подход к формированию нитей (часто это выражается в возможности использования более длинных нитей) за счет дополнительной аппаратуры для хранения блокированных нитей.

Рис. 15.15. Структура процессорного элемента типовой макропотоковой системы

Возможна также и потоковая обработка переменного уровня, когда узлы соответствуют как простым операциям, так и сложным последовательным процедурам. Последний случай иногда называют комбинированной обработкой с потоками данных и потоками управления (combined dataflow/control flow).

Гиперпотоковая обработка

В основе гиперпотоковой технологии (hyperthreading), разработанной фирмой Intel и впервые реализованной в микропроцессоре Pentium 4, лежит то, что современные процессоры в большинстве своем являются суперскалярными и многоконвейерными, то есть выполнение команд в них идет параллельно, по этапам и на нескольких конвейерах сразу. Гиперпотоковая обработка призвана раскрыть этот потенциал таким образом, чтобы функциональные блоки процессора были бы максимально загружены. Поставленная цель достигается за счет сочетания соответствующих аппаратных и программных средств.

Выполняемая программа разбивается на два параллельных потока (threads). Задача компилятора (на стадии подготовки программы) и операционной системы (на этапе выполнения программы) заключается в формировании таких последовательностей независимых команд, которые процессор мог бы обрабатывать параллельно, по возможности заполняя функциональные блоки, не занятые одним из потоков, подходящими командами из другого, независимого потока.

Операционная система, поддерживающая гиперпотоковую технологию, воспринимает физический суперскалярный процессор как два логических процессора и организует поступление на эти два процессора двух независимых потоков команд. Процессор с поддержкой технологии hyperthreading эмулирует работу двух одинаковых логических процессоров, принимая команды, направленные для каждого из них. Это не означает, что в процессоре имеются два вычислительных ядра — оба логических процессора конкурируют за ресурсы единственного вычислительного ядра,' Следствием конкуренции является более эффективная загрузка всех ресурсов процессора.

В процессе вычислений физический процессор рассматривает оба потока команд и по очереди запускает на выполнение команды то из одного, то из другого, или сразу их двух, если есть свободные вычислительные ресурсы. Ни один из потоков не считается приоритетным. При остановке одного из потоков (в ожидании какого-либо события или в результате зацикливания) процессор полностью переключается на второй поток. Возможность чередования команд из разных потоков составляет принципиальное отличие между гиперпотоковой и макропотоковой обработкой.

Наличие только одного вычислительного ядра не позволяет достичь удвоенной производительности, однако за счет большей отдачи от всех внутренних ресурсов общая скорость вычислений существенно возрастает. Это особенно ощущается, когда потоки содержат команды разных типов, тогда замедление обработки в одном из них компенсируется большим объемом работ, выполненных в другом потоке.

Следует учитывать, что эффективность технологии hyperthreading зависит от работы операционной системы, поскольку разделение команд на потоки осуществляет именно она.

Для иллюстрации рассмотрим некоторые особенности реализации гиперпотоковой технологии в процессоре Pentium 4 Хеоп. Процессор способен параллельно обрабатывать два потока в двух логических процессорах. Чтобы выглядеть для операционной системы и пользователя как два логических процессора, физический процессор должен поддерживать информацию одновременно для двух отдельных и независимых потоков, распределяя между ними свои ресурсы. В зависимости от вида ресурса применяются три подхода: дублирование, разделение и совместное использование.

Дублированные ресурсы. Для поддержания двух полностью независимых контекстов на каждом из логических процессоров некоторые ресурсы процессора необходимо дублировать. Прежде всего, это относится к счетчику команд (IP, Instruction Pointer), позволяющему каждому из логических процессоров отслеживать адрес очередной команды потока. Для параллельного выполнения нескольких процессов необходимо столько IP, сколько потоков команд необходимо отслеживать одновременно. Иными словами, у каждого логического процессора должен быть свой счетчик команд. В процессоре Хеоп максимальное количество потоков команд равно двум и поэтому требуется два счетчика команд. Кроме того, в процессоре имеются две таблицы распределения регистров (RAT, Register Allocation Table), каждая из которых обеспечивает отображение восьми регистров общего назначения (РОН) и восьми регистров с плавающей запятой (РПЗ), относящихся к одному логическому процессору, на совместно используемый регистровый файл из 128 РОН и 128 РПЗ. Таким образом, RAT — это дублированный ресурс, управляющий совместно используемым ресурсом (регистровым файлом).

Разделенные ресурсы. В качестве одного из видов разделенных ресурсов в Хеоп выступают очереди (буферная память, организованная по принципу FIFO), расположенные между основными ступенями конвейера. Применяемое здесь разделение ресурсов можно условно назвать статическим: каждая буферная память (очедедь) разбивается пополам, и за каждым логическим процессором закрепляется своя половина очереди.

Применительно к другому виду очередей — очередям диспетчеризации команд (их в процессоре три) — можно говорить о динамическом разделении. Вместо того чтобы из предусмотренных в каждой очереди двенадцати входов фиксировано назначить входы 0-5 логическому процессору (ЛП) 0, а входы 6-11 — логическому процессору 1, каждому ЛП разрешается использовать любые входы очереди, лишь бы их общее число не превысило шести.

С позиций логического процессора и потока между статическим и динамическим разделением нет никакой разницы — в обоих случаях каждому ЛП выделяется своя половина ресурса. Различие становится существенным, если в качестве отправной точки взять физический процессор. Отсутствие привязки потоков к конкретным входам очереди позволяет не принимать во внимание, что имеются два потока, и расценивать обе половины как единую очередь. Очередь диспетчеризации команд просто просматривает каждую команду в общей очереди, оценивает зависимости между командами, проверяет доступность ресурсов, необходимых для выполнения команды, и планирует команду к исполнению. Таким образом, выдача команд на исполнение не зависит от того, какому потоку они принадлежат. Динамическое разделение очередей диспетчеризации команд предотвращает монополизацию очередей каким-либо одним из логических процессоров.

Завершая обсуждение разделяемых ресурсов, отметим, что если процессор Хеоп обрабатывает только один поток, то для обеспечения максимальной производительности этому потоку предоставляются все ресурсы процессора. В динамически разделяемых очередях снимаются ограничения на количество входов, доступных одному потоку, а в статических разделяемых очередях отменяется их разбиение на две половины.

Совместно используемые ресурсы. Этот вид ресурсов в гиперпотоковой технологии считается определяющим. Чем больше ресурсов могут совместно использовать логические процессоры, тем большую вычислительную мощность можно «снять№» с единицы площади кристалла процессора. Первую группу общих ресурсов образуют функциональные (исполнительные) блоки: целочисленные операционные устройства, блоки операций с плавающей запятой и блоки обращения (чтения/записи) к памяти. Эти ресурсы "не знают", из какого ЛП поступила команда. То же самое можно сказать и о регистровом файле —втором виде совместно используемых ресурсов.

Сила гиперпотоковой технологии —общие ресурсы —одновременно является и ее слабостью. Проблема возникает, когда один поток монополизирует ключевой ресурс (такой, например, как блок операций с плавающей запятой), чем блокирует другой поток, вызывая его остановку. Задача предотвращения таких ситуаций возлагается на компилятор и операционную систему, которые должны образовать потоки, состоящие из команд с максимально различающимися требованиями к совместно используемым ресурсам. Так, один поток может содержать команды, нуждающиеся главным образом в блоке для операций с плавающей запятой, а другой — состоять преимущественно из команд целочисленной арифметики и обращения к памяти.

В заключение необходимо остановиться на третьем виде общих ресурсов — кэш-памяти. Процессор Хеоп предполагает работу с кэш-памятью трех уровней (LI, L2 и L3) и так называемой кэш-памятью трассировки. Оба логических процессора совместно используют одну и ту же кэш-память и хранящиеся в ней данные. Если поток, обрабатываемый логическим процессором 0, хочет прочитать некоторые данные, кэшированные логическим процессором 1, он может взять их из общего кэша. Из-за того, что в гиперпотоковом процессоре одну и ту же кэш-память используют сразу два логических процессора, вероятность конфликтов и, следовательно, вероятность снижения производительности возрастает.

Любой вид кэш-памяти одинаково трактует все обращения для чтения или записи, вне зависимости от того, какой из логических процессоров данное обращение производит. Это позволяет любому потоку монополизировать любой из кэшей, причем никакой защитой от монополизации, как это имеет место в случае очередей диспетчеризации команд, процессор не обладает. Иными словами, физический процессор не в состоянии заставить логические процессоры сотрудничать при их обращении к кэшам.

В целом, среди совместно используемых ресурсов в технологии hyperthreading кэш-память оказывается наиболее критичным местом, и конфликты за обладание этим ресурсом сказываются на общей производительности процессора наиболее ощутимо.

По оценке Intel, прирост скорости вычислений в некоторых случаях может достигать 25-35%. В приложениях, ориентированных на многозадачность, программы ускоряются на 15-20%. Возможны, однако, ситуации, когда прирост в быстродействии может быть незаметен и даже быть отрицательным. Таким образом, эффективность технологии находится в прямой зависимости от характера реализуемого программного приложения. Максимальная отдача достигается при работе серверных приложений за счет разнообразия процессорных операций.

В настоящий момент аппаратная поддержка технологии заложена в микропроцессоры Pentium 4, причем, по информации Intel, в процессоре Pentium 4 Хеоп это потребовало 5% дополнительной площади на кристалле. Программная поддержка технологии предусмотрена в операционных системах Windows 2000, Windows XP и Windows .NET Server (в предшествующих ОС Windows такая возможность отсутствует).

Вычислительные системы с управлением вычислениями по запросу

В системах с управлением от потока данных каждая команда, для которой имеются все необходимые операнды, немедленно выполняется. Однако для получения окончательного результата многие из этих вычислений оказываются ненужными. Отсюда прагматичным представляется иной подход, когда вычисления инициируются не по готовности данных, а на основе запроса на данные. Такая организация вычислительного процесса носит название управления вычислениями по запросу (demand-driven control). В ее основе, как и в потоковой модели (data-driven control), лежит представление вычислительного процесса в виде графа. В потоковой модели узлы вверху графа запускаются раньше, чем нижние. Это — нисходящая обработка. Механизм управления по запросу состоит в обработке вершин потокового графа снизу вверх путем разрешения запуска узла, лишь когда требуется его результат. Данный процесс получил название редукции графа, а ВС, оперирующая в режиме снизу вверх (см, рис. 15.1, г), называется редукционной вычислительной системой.

Математическую основу редукционных ВС составляют лямбда-исчисления [2,57,202], а для написания программ под такие системы нужны так называемые функциональные языки программирования (FP, Haskell и др.). На функциональном языке все программы представляются в виде выражений, а процесс выполнения программы заключается в определении значений последних (это называется оценкой выражения). Оценка выражения производится посредством повторения операции выбора и упрощения тех частей выражения, которые можно свести от сложного к простому (такая часть выражения называется редексом, причем сам редекс также является отдельным выражением). Операция упрощения называется редукцией. Процесс редукции завершается, когда преобразованное редукцией выражение больше не содержит редекса. Выражение, не содержащее редекса, называется нормальной формой.

В редукционной ВС вычисления производятся по запросу на результат операции. Предположим, что вычисляется выражение а = (b +1) х с – d/c. В случае потоковых моделей процесс начинается с самых внутренних операций, а именно с параллельного вычисления (b + 1) и d/c. Затем выполняется операция умножения (b + 1) х с и, наконец, самая внешняя операция — вычитание. Такой род вычислений часто называют энергичными вычислениями (eager evaluation).

При вычислениях, управляемых запросами, все начинается с запроса на результат а, который включает в себя запрос на вычисление выражений (b + 1) х с и d/c, а те, в свою очередь, формируют запрос на вычисление b + 1, то есть на операцию самого внутреннего уровня. Результат возвращается в порядке, обратном поступлению запросов. Отсюда название ленивые вычисления (lazy evaluation), поскольку операции выполняются только тогда, когда их результат требуется другой команде. Редукционные вычисления, естественно, согласуются с концепцией функционального программирования, упрощающей распараллеливание программ.

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

Известны два типа моделей редукционных систем: строчная и графовая, отличающиеся тем, что именно передается в функцию — скопированные значения данных или же только указатели, указывающие на места хранения данных.

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

На рис. 15.17 показан процесс вычислений с помощью строчной редукции.

Рис. 15.17. Процесс вычислений в модели со строчной редукцией: в — исходный граф; б, в — последовательно редуцированные графы; г— результат редукции

Если требуется значение a=(b + с) х (b - с) (рис. 15.17, я), то копируется граф программы, определяющий вычисление а (рис. 15.17,6). При этом запускается операция умножения. Поскольку это вычисление невозможно без предварительного расчета двух параметров, то запускаются вычисления «+» и «-», в результате чего образуется редуцированный граф (с ветвями «6» и «2»), показанный на рис, 15.17, в. Результат получается путем дальнейшей редукции (рис. 15.17, г),

В графовой редукционной модели выражение представлено как ориентированный граф. Граф сокращается по результатам оценки ветвей и подграфов. В зависимости от запросов возможно параллельное оценивание и редукция различных частей графа или подграфов. Запросившему узлу, который управляет всеми ссылками на граф, возвращается указатель на результат редукции. ≪Обход≫ графа и изменение ссылок продолжаются, пока не будет получено значение результата, копия которого возвращается запросившей команде.

Рисунок 15.18 иллюстрирует пример вычислений с помощью графовой редукции.

Рис. 15.18. Процесс вычислений в модели с графовой редукцией: а — исходный граф; б, в, г— последовательная редукция со сменой направления указателей; д — результат редукции

В этой модели, когда требуется найти значение а, определение вычисления а не копируется, а передается указатель определяющей программы. При достижении узла «а» направление переданного указателя меняется на противоположное, чтобы запомнить место, из которого будет выдаваться результат вычисления (рисунок 15.18, б). Далее путем повторения операции смены направления указателя (текущего указателя) на обратное получается граф, показанный на рис. 15.18, в. Теперь операции *+* и «-» можно выполнять, граф редуцируется сначала до изображенного на рис. 15.18, г, а затем — на рис. 15.18,д.


 

А также другие работы, которые могут Вас заинтересовать

6746. Порядок применения в Таможенном союзе количественных ограничений 29.69 KB
  Порядок применения в Таможенном союзе количественных ограничений. В соответствии с соглашением О единых мерах нетарифного регулирования в отношении третьих стран количественные ограничения экспорта (импорта) представляют собой меры по количественн...
6747. Лицензирование во внешнеторговой сфере Таможенного союза 28.91 KB
  Лицензирование во внешнеторговой сфере Таможенного союза. В рамках Таможенного союза применение мер регулирования, затрагивающих внешнюю торговлю товарами, включенными в единый перечень, а также применение тарифной квоты реализуются, как правило, пу...
6748. Порядок и условия применения тарифных квот в Таможенном союзе 26.25 KB
  Порядок и условия применения тарифных квот в Таможенном союзе. В соответствии с Соглашением об условиях и механизме применения тарифных квот от 12 декабря 2008 г. при осуществлении регулирования ввоза на единую таможенную территорию сельскохозяйстве...
6749. Другие виды нетарифного регулирования (наблюдение за экспортом/импортом, исключительное право на экспорт/импорт, особые виды запретов и ограничений во внешней торговле товарами) 27.69 KB
  Другие виды нетарифного регулирования (наблюдение за экспортом/импортом, исключительное право на экспорт/импорт, особые виды запретов и ограничений во внешней торговле товарами). Наряду с квотированием и лицензированием Соглашением о единых мерах не...
6750. Клеточные основы наследственности человека 29.41 KB
  Клеточные основы наследственности человека Клетка - основная единица биологической активности. Первое описание клеток было сделано в 1665 году англичанином Р.Гуком. В зависимости от структурных особенностей клетки делятся на прокариотическ...
6751. Жизненный (клеточный) цикл 26.07 KB
  Жизненный (клеточный) цикл Весь период существования клетки от её возникновения до деления или гибели называется жизненным, или клеточным циклом. Вновь появившаяся клетка первоначально растет и дифференцируется, затем она выполняет свои специфически...
6752. Деление клетки 24.88 KB
  Деление клетки. В настоящее время известно три типа деления эукариотических клеток: амитоз, митоз и мейоз. Амитоз - прямое деление. При этом клетка, а иногда – только её ядро, делится путём простой перетяжки. Равномерного распределения нас...
6753. Основы цитогенетики. Строение и типы метафазных хромосом человека 26.99 KB
  Основы цитогенетики. Строение и типы метафазных хромосом человека. Многие ученые в разных странах мира изучали хромосомы клеточного ядра. Однако только в 1955 году Тио и Леван установили, что в большинстве клеток у человека присутствует 46 хромосом....
6754. Понятие о кариотипе человека 27.61 KB
  Понятие о кариотипе человека. Число, размеры и форма хромосом являются специфическими признаками для каждого вида живых организмов. Так, в клетках рака-отшельника содержится по 254 хромосомы, а у комара - только 6. Соматические клетки человека ...