Всеволод Сергеевич Бурцев Параллелизм вычислительных процессов и развитие архитектуры суперэвм м, 1997

Токен запроса выдается в АП. Аппаратная часть работы самой команды НСО заканчивается записью токена запроса операндов в АП и входом в подпрограмму сложного оператора. В случае одного параметра и одного результата работа НСО значительно упрощается, так как нет необходимости в формировании токена запроса.

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

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

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

Одновходовая команда ПИ в качестве контекста так же, как и команда НСО, использует поля П и Т, а поле И определяет номер слова в блоке ОЗУ микропроцессора (величину индекса Nсл и признак ключа П). Признак ключа П, устанавливаемый в одном из разрядов поля индекса, определяет содержание данных ВП или Кл и соответствующее изменение кода операции в выходном токене, которую выполняет одновходовая команда ПИ. Ее действие практически сводится к изменению кода операции в формируемом токене. Код операции НСО заменяется на код операции "индексация с записью" (ИЗ), если в поле данных передается величина параметра (ВП), и на код операции "индексация со считыванием" (ИС), если в поле данных передается ключ, определяющий адрес и контекст передачи результата (Кл).

Двухвходовая команда ПИ из АП получает пакет, состоящий из контекста НСО ([ПТ]), индекса (И=Nсл&П) и параметра, содержащего либо величину параметра (ВП), либо ключ для передачи результата (Кл).

Команды ПИ в качестве адреса назначения имеют адрес команды НСО. Для формирования токена операнда, который должен найти в АП токен запроса, команда ПИ должна в поле ключа поставить ПТ текущего контекста. В этом случае поле ПТ и К сформированного токена будет определять имя (Р) сложного оператора в выполняемой программе. В поле данных формируемого токена операнда необходимо поставить параметр либо ВП, либо Кл. В токене операнде должен содержаться признак сохранения парного токена.

Операции ИЗ и ИС работают как обычные двухвходовые команды на любом свободном процессоре:

1. Физический адрес поля данных токена запроса индексируется: И=Nсл. Результат индексации устанавливается в поле [ИПТ] токена результата.

2. 
   Адресом назначения K₁ является вход в подпрограмму.
   
3. 
   В поле данных токена результата устанавливается величина параметра (ВП) в случае выполнения команды ИЗ или код ключа Кл в случае выполнения команды ИС, в поле кода операции устанавливается код команды продолжения сложного оператора ПСО.
   
4. 
   Сформированный токен через К₂' передается на выделенный микропроцессор для выполнения команды ПСО, которая осуществляет передачу управления по адресу K₁ на подпрограмму, выполняющую запись параметра или запись со считыванием результата и передачу управления на продолжение СО, адрес которого содержится в первом слове блока ОЗУ.
   

Рис.2. Работа со сложным оператором с одним входом и выходом.

Проследим последовательность работы сложного оператора в простейшем случае при одном параметре по входу и одном результате (НС01) (Рис.2).

127

B.C. Бурцев, Л.Г.Тарасенко. Использование микропроцессоров традиционной архитектуры в

системе потока данных

Имя программы (Р) в любом контексте определяется полями П и Т контекста выполняемой программы и кодом адреса назначения оператора НС01, который в каждом месте входа в СО разный. Необходимо по возможности исполнить столько НС01, сколько входов в сложный оператор может быть осуществлено за определенный период решения задачи. Поле И контекста может использоваться для определения адреса назначения выдачи результата И=К=В.

Команда НС01 выполняет следующие функции:

1. 
   Проверяет наличие свободного блока памяти на выполняемом микропроцессоре, и, если его нет, формирует пакет для выполнения этой команды на другом процессоре. Поиск процессора осуществляется через коммутатор К₁.
   
2. 
   Осуществляет вход в подпрограмму сложного оператора, которая выполняет запись единственного параметра из поля Д и ввод ключа, по которому может быть поставлен результат (поля П и Т текущего контекста и И=К=В или второй адрес назначения команды).
   
3. 
   Переходит к выполнению самой программы сложного оператора, которая может прерываться выполнением простых операторов.
   
4. 
   По окончании работы подпрограммы сложного оператора формируется токен результата, и если следующий оператор двухвходовой, он передается в АП.
   

Токен запроса состоит из полей П и Т, текущего контекста и адреса команды назначения, в данном случае адреса А команды НСО (имя сложного оператора Р). В поле данных (Д) устанавливается физический номер процессора и блока ОЗУ (ФА), в котором СО выполняется. Сформированый токен запроса посылается в АП, т.к. команды назначения будут двухвходовыми (ИЗ и ИС). Остальные этапы работы НСО полностью совпадают с работой HCOl.

Подпрограмма СО может прерываться простыми операторами и может остановиться в ожидании остальных входных параметров. В этом случае процессор освобождается для выполнения других простых или сложных операторов. Все параметры, кроме первого, вводятся в подпрограмму СО через простые команды ПИ, ИЗ и ИС.

По приходу параметров, команды ПИ формируют токены для команд ИЗ и ИС, которые состоят из имени Р (поле П, Т и К|) и самого параметра в поле Д. Величина индекса берется из поля И контекста (И=Nсл&П), определяющего имя СО. Токен с операцией ИЗ формируется в том случае, если в поле Д

Рис.3. Работа со сложными операторами со многими входами и выходами

Двухвходовые команды ПИ используются тогда, когда необходимо ввести параметр из внешнего контекста по отношению к контексту НСО. В этом случае контекст СО и индекс И содержатся в поле данных первого операнда, а значение параметра в поле данных второго операнда. Сформированные токены операндов с операциями записи или считывания поступают в АП и по ключу Р объединяются с токеном запроса. Сформированные пакеты выполняются как простые операторы ИЗ и ИС. Эти операторы производят индексацию физического адреса содержащегося в поле токена запроса кодом индекса И и вместе со значением параметра посылаются через К₂' в тот процессор, на котором выполняется СО с именем Р. После того как подпрограмма СО получает результаты, она выдает их в соответствии с ключами Кл₁ и Кл₂, поставляемыми в качестве параметров посредством команды ИС.

Необходимо отметить, что введение сложных операторов возможно благодаря тому, что достаточно последовательно выдержан принцип обезличенного распределения всех видов ресурсов, таких как исполнительные устройства, коммутаторы К₁, К₂. Исключением являются только модули ассоциативной памяти. Этот принцип работы обеспечивается:

• 
  алгоритмом работы коммутатора К₁, выдающего готовую к исполнению пару токенов на свободный процессор;
  
• 
  исключением буферных регистров на входе исполнительных устройств скалярного процессора;
  
• 
  системой равномерного распределения загрузки входных регистров K₁ с использованием буферов памяти готовых пар;
  
• 
  алгоритмом ассинхронной работы коммутатора К₂;
  
• 
  алгоритмом работы микропроцессоров исполнительных устройств, позволяющим исключить буферные регистры на их входах.
  

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

Введение сложных операторов позволяет:

• 
  сократить требования к объему АП и количеству обращений к ней на определенных участках программ;
  
• 
  упростить использование подпрограмм;
  
• 
  увеличить производительность системы на последовательных вычислительных конструкциях с хорошо локализованными данными.
  

Новый механизм входа в подпрограмму "сложный оператор" не требует изменения контекста содержащей его программы, эта процедура заменена отысканием свободного места памяти микропроцессора, которое происходит аппаратно.

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

Пусть необходимо вычислить:

Y=X+X²+X³+X⁴+X⁵+X⁶;

Для исполнения вычислений выражения в исходной модели можно использовать программу, граф которой изображен на Рис. 4.

Фрагмент содержит 10 двухвходовых команд. Следовательно, при исполнении фрагмента потери динамического ресурса ассоциативной памяти составят 20 обращений. Максимальные потери статического ресурса ассоциативной памяти составят 3 слова.

Для исполнения фрагмента в модифицированной модели вычислений фрагмент может быть оформлен в виде сложного оператора с одним параметром и одним результатом. Для его запуска может быть использована команда НС01. Для исполнения фрагмента достаточно иметь 4 регистра, один из которых сумматор. Ни динамический, ни статический ресурс ассоциативной памяти использован не будет.

В следующем примере необходимо вычислить:

float х, у, z;

……………..

for (I:=0; i

{x:=yz+x; y:=xz+y; z:=xy+z;}

Пусть N-константа.

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

Тело цикла содержит 6 двухвходовых команд, исполняемых последовательно. Исключая потери на организацию цикла, статически развернем цикл. Фрагмент содержит 6N последовательно исполняемых двухвходовых команд. Следовательно, при исполнении фрагмента в исходной модели вычислений потери динамического ресурса ассоциативной памяти составят 12N обращений за считыванием и записью. Потери статического ресурса ассоциативной памяти в процессе исполнения фрагмента составят 5 слов.

Для исполнения фрагмента в новой модели вычислений он будет оформлен в виде сложного оператора с тремя параметрами и тремя результатами. Для запуска сложного оператора будет использована команда НСО. При исполнении потребуется 8 обращений к ассоциативной памяти за параметрами и результатами. Потери статического ресурса ассоциативной памяти составят 1 слово (для токена запроса параметров). Для исполнения фрагмента в микропроцессоре достаточно иметь 4 регистра, один из которых сумматор.

131

B.C. Бурцев, Л.Г.Тарасенко. Использование микропроцессоров традиционной архитектуры в

системе потока данных








Рис.4. Граф программы Рис.5. Граф программы

Итак, при использовании новой модели вычислений получим экономию динамического ресурса ассоциативной памяти, равную 12N-8 обращений, экономия статического ресурса составит по крайней мере 4 слова.

Приведенный на Рис.6 пример предполагает последовательный сбор параметров или элементов вектора в старой структуре. Этот пример интересен тем, что в новой структуре ввод параметров К₁ - К_n осуществляется по мере их готовности. Таким образом, новая структура имеет преимущество перед старой как по объему памяти, так и по времени выполнения этого фрагмента программы. Дело в том, что в случае задержки каких-либо параметров К; с малыми номерами, все параметры с более высокими номерами будут приняты в локальную память микропроцессора по мере их поступления и после прихода последнего без задержки будет сформирован вектор. Экономия по памяти составит в среднем n/2 - 1 ячейку АП. Этим методом можно воспользоваться для сокращения времени сбора вектора (см. Раздел 2).

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

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

132

B.C. Бурцев, Л.Г.Тарасенко. Использование микропроцессоров традиционной архитектуры в

системе потока данных

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

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

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

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

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

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

133

B.C. Бурцев, Л.Г.Тарасенко. Использование микропроцессоров традиционной архитектуры в

системе потока данных

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

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

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

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

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

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