ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 25.12.2021
Просмотров: 2462
Скачиваний: 7
626 Глава 15. Потоковые и редукционные вычислительные системы
деляется отдельная область в специальной памяти кадров (frame memory), причем
раздача памяти под каждый кадр происходит уже на этапе выполнения программы.
Б схеме с явной адресацией токенов любое вычисление полностью описывает-
ся
указателем команды
,(IP, Instruction Pointer) и
указателем кадра
(FP, Frame
Pointer). Этот кортеж <FP, IP> входит в тег токена, а сам токен выглядит следую-
щим образом: Значение • FP.IP.
Команды, реализующие потоковый граф, хранятся в памяти команд и имеют
формат: Код операции • Индекс в памяти кадров • Адресат.
Здесь « Индекс в памяти кадров» определяет положение ячейки с нужным то-
кеном внутри кадра, то есть какое число нужно добавить к FP, чтобы получить
адрес интересующего токена. Поле -«Адресат» указывает на местоположение ко-
манды, которой должен быть передан результат обработки данного токена. Адрес
в этом поле также задан в виде смещения — числа, которое следует прибавить к
текущему значению IP, чтобы получить исполнительный адрес команды назначе-
ния в памяти команд. Если потребителей токена несколько, в поле «Адресат» за-
носится несколько значений смещения. Простой пример кодирования потокового
графа и токенов на его дугах показан на рис. 15.13.
Каждому слову в памяти кадров придан
бит наличия,
единичное значение ко-
торого удостоверяет, что в ячейке находится токен, ждущий согласования, то есть
что одно из искомых значений операндов уже имеется. Как и в архитектуре с окра-
деляется отдельная область в специальной памяти кадров (frame memory), причем
раздача памяти под каждый кадр происходит уже на этапе выполнения программы.
Б схеме с явной адресацией токенов любое вычисление полностью описывает-
ся
указателем команды
,(IP, Instruction Pointer) и
указателем кадра
(FP, Frame
Pointer). Этот кортеж <FP, IP> входит в тег токена, а сам токен выглядит следую-
щим образом: Значение • FP.IP.
Команды, реализующие потоковый граф, хранятся в памяти команд и имеют
формат: Код операции • Индекс в памяти кадров • Адресат.
Здесь «Индекс в памяти кадров» определяет положение ячейки с нужным то-
кеном внутри кадра, то есть какое число нужно добавить к FP, чтобы получить
адрес интересующего токена. Поле -«Адресат» указывает на местоположение ко-
манды, которой должен быть передан результат обработки данного токена. Адрес
в этом поле также задан в виде смещения — числа, которое следует прибавить к
текущему значению IP, чтобы получить исполнительный адрес команды назначе-
ния в памяти команд. Если потребителей токена несколько, в поле «Адресат» за-
носится несколько значений смещения. Простой пример кодирования потокового
графа и токенов на его дугах показан на рис. 15.13.
Каждому слову в памяти кадров придан
бит наличия,
единичное значение ко-
торого удостоверяет, что в ячейке находится токен, ждущий согласования, то есть
что одно из искомых значений операндов уже имеется. Как и в архитектуре с окра-
Вычислительные системы с управлением вычислениями от потока данных 6 2 7
шенными токенами, определено, что вершины могут иметь максимум две входные
дуга. Когда на входную дугу вершины поступает токен <vl, <FP, IP», в ячейке па-
мяти кадров с адресом FP + (IP.I) проверяется бит наличия (здесь IP.I означает со-
держимое поля I в команде, хранящейся по адресу, указанному в IP). Если бит
наличия сброшен (ни один из пары токенов еще не поступал), поле значения при-
шедшего токена (vl) заносится в анализируемую ячейку памяти кадров, а бит на-
личия в этой ячейке устанавливается в единицу, фиксируя факт, что первый токен
из пары уже доступен:
(FP + (IP.I).значение := vl
(FP + (IP.I).наличие :=1
Этот случай отражен на рис. 15.13,
а,
когда на вершину SUB по левой входной
дуге поступил токен
<35,
<FP, IP».
Если токен <v2,<FP, IP>> приходит на узел, для которого уже хранится значение
vl, команда, представляющая данную вершину, может быть активирована и вы-
полнена с операндами vl и v2. В этот момент значение vl извлекается из памяти
кадров, бит наличия сбрасывается, и на функциональный блок, предназначенный
для выполнения операции, передается пакет команды <vl, v2, FP, IP, IP.OP, IP.0>, со-
держащий операнды (vl и v2), код операции (IP.OP) и адресат ее результата (IP.D).
Входящие в этот пакет значения FP и IP нужны, чтобы вместе с IP.D вычислить
исполнительный адрес адресата. После выполнения операции функциональный
Рис. 15.14. Структура процессорного элемента типовой потоковой системы
с явной адресацией токенов
6 2 8 Глава 15. Потоковые и редукционные вычислительные системы
блок пересылает результат в блок формирования токенов. Рисунок 15.13, б демонст-
рирует ситуацию, когда токен уже пришел и на второй вход вершины SUB. Операция
становится активируемой, и после ее выполнения результат передается на вершины
ADD и MUL, которые ожидают входных токенов в ячейках FP+3 и FP+4 соответственно.
Типовая архитектура системы с явной адресацией токенов показана на рис. 15.14.
Отметим, что функция согласования токенов стала достаточно короткой операцией,
что позволяет внедрить ее в виде нескольких ступеней процессорного конвейера.
Макропотоковые вычислительные системы
Рассмотренный ранее механизм обработки с управлением от потока данных функ-
ционирует на уровне команд и его относят к
потоковой обработке низкого уровня
(fine-grain dataflow). Данному подходу сопутствуют большие издержки при пере-
сылке операндов. Для уменьшения коммуникационных издержек необходимо при-
менять потоковую обработку на процедурном уровне, так называемую
укрупнен-
ную потоковую
или
макропотоковую
обработку (multithreading). Буквальный
перевод английского термина означает потоковую обработку множества нитей.
Макропотоковая модель совмещает локальность программы, характерную для
фон-неймановской модели, с толерантностью к задержкам на переключение за-
дач, свойственной потоковой архитектуре. Это достигается за счет того, что вер-
шина графа представляет собой не одну команду, а последовательность из
нескольких команд, называемых
нитью
(thread). По этой причине макропотоко-
вую организацию часто именуют
крупнозернистой потоковой обработкой
(coarse-
grained dataflow). Макропотоковая обработка сводится к потоковому выполнению
нитей, в то время как внутри отдельной нити характер выполнения фон-нейма-
новский. Порядок обработки нитей меняется динамически в процессе вычисле-
ний, а последовательность команд в пределах нити определена при компиляции
статически. Структура макропотоковой ВС представлена на рис. 15.15.
Существенное отличие макропотоковой системы от обычной потоковой ВС
состоит в организации внутреннего управляющего конвейера, где последователь-
ность выполнения команд задается счетчиком команд, как в фон-неймановских
машинах. Иными словами, этот конвейер идентичен обычному конвейеру команд.
Вернемся к иллюстрации возможных вычислительных моделей (см. рис.15.1).
В макропотоковой архитектуре (см. рис. 15.1,
в)
каждый узел графа представляет
команду, а каждая закрашенная область — одну из нитей. Если команда приоста-
навливается, останавливается и соответствующая нить, в то время как выполне-
ние других нитей может продолжаться.
Существуют две формы макропотоковой обработки:
без блокирования
и
с бло-
кированием,
В модели без блокирования выполнение нити не может быть начато,
пока не получены все необходимые данные. Будучи запущенной, нить выполняется
до конца без приостановки. В варианте с блокированием запуск нити может быть
произведен до получения всех операндов. Когда требуется отсутствующий опе-
ранд, нить приостанавливается (блокируется), а возобновление выполнения от-
кладывается на некоторое время. Процессор запоминает всю необходимую инфор-
мацию о состоянии и загружает на выполнение другую готовую нить. Модель
с блокированием обеспечивает более мягкий подход к формированию нитей (час-
то это выражается в возможности использования более длинных нитей) за счет
дополнительной аппаратуры для хранения блокированных нитей.
Вычислительные системы с управлением вычислениями от потока данных 6 2 9
Рис. 15.15. Структура процессорного элемента типовой макропотоковой системы
Возможна также и потоковая обработка переменного уровня, когда узлы соот-
ветствуют как простым операциям, так и сложным последовательным процеду-
рам. Последний случай иногда называют
комбинированной обработкой с потока-
ми данных и потоками управления
(combined dataflow/control flow).
Гиперпотоковая обработка
В основе
гиперпотоковой технологии
(hyperthreading), разработанной фирмой Intel
и впервые реализованной в микропроцессоре Pentium 4, лежит то, что современ-
ные процессоры в большинстве своем являются суперскалярными и многоконвей-
ерными, то есть выполнение команд в них идет параллельно, по этапам и на не-
скольких конвейерах сразу. Гиперпотоковая обработка призвана раскрыть этот
потенциал таким образом, чтобы функциональные блоки процессора были бы мак-
симально загружены. Поставленная цель достигается за счет сочетания соответ-
ствующих аппаратных и программных средств.
Выполняемая программа разбивается на два параллельных потока (threads).
Задача компилятора (на стадии подготовки программы) и операционной системы
(на этапе выполнения программы) заключается в формировании таких последо-
вательностей независимых команд, которые процессор мог бы обрабатывать па-
раллельно, по возможности заполняя функциональные блоки, не занятые одним
из потоков, подходящими командами из другого, независимого потока.
Операционная система, поддерживающая гиперпотоковую технологию, воспри-
нимает физический суперскалярный процессор как два логических процессора
и организует поступление на эти два процессора двух независимых потоков команд.
Процессор с поддержкой технологии hyperthreading эмулирует работу двух
одинаковых логических процессоров, принимая команды, направленные для каж-
6 3 0 Глава 15. Потоковые и редукционные вычислительные системы
дого из них. Это не означает, что в процессоре имеются два вычислительных ядра —
оба логических процессора конкурируют за ресурсы единственного вычислитель-
ного ядра,' Следствием конкуренции является более эффективная загрузка всех
ресурсов процессора,
В процессе вычислений физический процессор рассматривает оба потока ко-
манд и по очереди запускает на выполнение команды то из одного, то из другого,
или сразу их двух, если есть свободные вычислительные ресурсы. Ни один из по-
токов не считается приоритетным. При остановке одного из потоков (в ожидании
какого-либо события или в результате зацикливания) процессор полностью пере-
ключается на второй поток. Возможность чередования команд из разных потоков
составляет принципиальное отличие между гиперпотоковой и макропотоковой
обработкой.
Наличие только одного вычислительного ядра не позволяет достичь удвоен-
ной производительности, однако за счет большей отдачи от всех внутренних ре-
сурсов общая скорость вычислений существенно возрастает. Это особенно ощу-
щается, когда потоки содержат команды разных типов, тогда замедление обработки
в одном из них компенсируется большим объемом работ, выполненных в другом
потоке.
Следует учитывать, что эффективность технологии hyperthreading зависит от
работы операционной системы, поскольку разделение команд на потоки осуще-
ствляет именно она.
Для иллюстрации рассмотрим некоторые особенности реализации гиперпото-
ковой технологии в процессоре Pentium 4 Хеоп. Процессор способен параллельно
обрабатывать два потока в двух логических процессорах. Чтобы выглядеть для
операционной системы и пользователя как два логических процессора, физический
процессор должен поддерживать информацию одновременно для двух отдельных
и независимых потоков, распределяя между ними свои ресурсы. В зависимости от
вида ресурса применяются три подхода: дублирование, разделение и совместное
использование.
Дублированные ресурсы.
Для поддержания двух полностью независимых кон-
текстов на каждом из логических процессоров некоторые ресурсы процессора
необходимо дублировать. Прежде всего, это относится к счетчику команд (IP,
Instruction Pointer), позволяющему каждому из логических процессоров отслежи-
вать адрес очередной команды потока. Для параллельного выполнения несколь-
ких процессов необходимо столько IP, сколько потоков команд необходимо отсле-
живать одновременно. Иными словами, у каждого логического процессора должен
быть свой счетчик команд. В процессоре Хеоп максимальное количество потоков
команд равно двум и поэтому требуется два счетчика команд. Кроме того, в про-
цессоре имеются две таблицы распределения регистров (RAT, Register Allocation
Table), каждая из которых обеспечивает отображение восьми регистров общего
назначения (РОН) и восьми регистров с плавающей запятой (РПЗ), относящихся
к одному логическому процессору, на совместно используемый регистровый файл
из 128 РОН и 128 РПЗ. Таким образом, RAT — это дублированный ресурс, управ-
ляющий совместно используемым ресурсом (регистровым файлом).
Разделенные ресурсы- В
качестве одного из видов разделенных ресурсов в Хеоп
выступают очереди (буферная память, организованная по принципу FIFO), рас-