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

Все элементы одной строки объединяются в выходной канал. Таким образом, эта матрица может одновременно коммутировать n входных каналов с n выходными. Управление элементами коммутации или вентилями в каждой схеме управления коммутатора осуществляется триггерами управления Т_У (Рис.11).

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

64

В.С.Бурцев. Выбор новой системы организации выполнения высокопараллельных вычислитель-ных процессов, примеры возможных архитектурных решений построения суперЭВМ

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

Рис.10. Типовая схема коммутатора.

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

Если запроса по этому направлению нет, то через инвертор И открыт вентиль в₂ и происходит опрос второго и т.д. направлений. Если по данному выходному направлению запросов нет или все обработаны, вырабатывается сигнал, устанавливающий триггер Т_нк в нулевое положение. После каждого пускового импульса происходит работа коммутатора, заключающаяся в передаче входных токенов по скоммутированным каналам на регистры P_1-n модулей АП. После окончания передачи, начинается подготовка к новой работе элементов коммутационной матрицы. Если же не было "натыков" и за один такт работы коммутации все запросы были удовлетворены, следующий импульс пуска пройдет по всем вентилям в_з и выйдет в виде конца цикла, который укажет на то, что следующая строка токенов по всем направлениям может быть принята

на входные регистры коммутатора (в частности, входными регистрами коммутатора могут служить выходные регистры ИУ).

Рис.11. Коммутатор с последовательной обработкой.

Эта схема обладает тем недостатком, что пока вся строка не обработается, готовые токены должны ждать очереди, в то время как пути их коммутации могут быть свободными.

Рис.12. Коммутатор с асинхронной обработкой.

На Рис.12 приведена структурная схема УКМАП, позволяющая обрабатывать токены по мере освобождения канала по входу. Работа схемы по опросу

67

В.С.Бурцев. Выбор новой системы организации выполнения высокопараллельных вычислитель-ных процессов, примеры возможных архитектурных решений построения суперЭВМ

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

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

Ассоциативная память.

Ассоциативная память выполняет несколько команд в зависимости от кода операции. Основные из них - поиск парного токена по ключу и считывание его в случае прохождения или запись вновь пришедшего токена на свободное место, если поиск закончился отрицательно. Как правило, считывание происходит со стиранием информации, но в некоторых случаях выполнение операций требуют сохранения считываемого токена. Считанная информация объединяется с вновь пришедшим токеном и образуют пакет (Рис.8д), который поступает на входные регистры коммутатора КМР (РУ и РА). Ключом, как правило, является код, состоящий из разрядов номера команды, индекса, итераций и активации. В случае ситуации, когда близок к переполнению один из АП, происходит перераспределение записи вновь пришедшего токена в модуль с наименьшим заполнением.

Управление равномерным заполнением модулей памяти осуществляет центральное управление ассоциативной памяти УАП. Запись в другой модуль требует изменения алгоритма считывания, замедляет общий темп работы АП, однако останов работы всей машины происходит только в том случае, если переполняется вся память АП. Подробный алгоритм работы АП описан в [4].

Работа распределителя регулятора и буфера памяти.

Пакеты объединенных токенов, готовые для выполнения операций ИУ, из АП передаются на входные регистры коммутатора распределителя через распределитель регулятор. На распределитель регулятор приходят пакеты токенов из трех источников:

• 
  из ассоциативной памяти;
  

• 
  из буфера, в котором пакеты хранятся отдельно для выполнения на арифметическом процессоре (БА) и для выполнения на процессоре управления (БУ);
  

- из устройства управления (пакеты для выполнения одновходовых операций дублирования).

Выходными устройствами РР являются:

• 
  входные регистры КМР соответственно КМР_уу - РУ и КМР_ау - РА;
  

• 
  регистры записи в буферную память либо свою, либо буфера следующего канала;
  

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

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

Рис.13. Буфер распределитель.

69

Коммутатор распределитель построен на той же основе, что и КМАП (Рис.14). Отличие состоит в совершенно ином управлении триггерами Т_у.

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

Рис.14. Коммутатор распределитель.

Основными управляющими элементами этой схемы являются триггера занятости входного канала по каждому направлению Т_зк и триггера запроса по входным направлениям Т_зап (Рис.14). Работа схемы начинается с импульса "пуск", который опрашивает занятость канала. Так, если триггер Т_зкn стоит в "0", импульс "пуск" проходит через вентиль В₄ и происходит опрос триггера занятости следующего канала Т_зкк. Если входной канал не занят - Т_зкк стоит в "единице", опрашивающий импульс проходит через В₃ и вентили В₁, последовательно опрашиваются все направления по наличию запроса на входе. Если запрос есть на каком-либо направлении, срабатывает вентиль B₁ этого направления, триггер, управляющий элементами матрицы, встает в "единицу" (Т_укк), тем самым соединяя свободное направление с соответствующим входным. Одновременно с этим вырабатывается импульс, устанавливающий в нулевое положение триггер запроса Т_запк и триггер занятости Т_зкк скоммутированных направлений. Этот же импульс приходит на опрос триггера занятости следующего выходного направления.

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

• 
  свободных направлений достаточно, чтобы удовлетворить все запросы;
  
• 
  свободных каналов недостаточно для удовлетворения запросов по входам.
  

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

После работы схемы УКМР, работает система коммутатции и пакеты входных сигналов передаются на указанные триггерами Ту свободные направления.

Пакеты, для которых не нашлось свободных каналов, сбрасываются в буфер либо остаются на регистре в соответствии с алгоритмом работы устройства PP_l-n.

Существенным недостатком работы этой схемы является слишком большое время ее работы - максимальное время работы равно n²τ_в, где τ_в - задержка в вентиле измеряется сотыми долями наносекунды. Время работы этой схемы управления можно существенно уменьшить (более чем на порядок), если разбить матрицу управляющих триггеров на подматрицы и организовать двухкаскадную работу схемы по времени. В этом случае, каждой подматрице может соответствовать свой триггер управления подматрицы. Управление этими триггерами можно организовать по той же, ранее описанной, схеме. В этом случае триггера занятости запросов должны соответствовать занятости группы выходных триггеров и триггера запросов - состоянию группы триггеров запросов (Рис.14).

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

Сравним времена работы двухкаскадной и однокаскадной схем. Так, если необходимо коммутировать 128 на 128 направлений, матрицу можно разбить на 64 подматрицы (8x8 подматриц, каждая по 256 элементов). Время первого подцикла в этом случае будет (8x8) τ_в, а время второго цикла будет (16x16) τ_в. Таким образом, общий цикл двухступенчатого управления не превзойдет 310 τ_в, в то время как максимальное время работы одноступенчатой схемы измеряется 16000 τ_в.

Двухступенчатая схема имеет и то преимущество перед одноступенчатой, что лучше адаптируется к интегральной технологии.

Взаимодействие с векторным исполнительным устройством и центральной вычислительной машиной.

Векторное исполнительное устройство работает только с векторами (строками) размером в i28 элементов (обработка больших векторов происходит построчно). Поэтому, обмен информацией между векторным исполнительным устройством и скалярным вычислителем происходит как в обычном для исполнительного устройства виде (пакеты и токены), так и векторами. Пакеты в векторное исполнительное устройство (ВИУ) подаются из устройства РР₁ в буфер пакетов ВИУ, а токены из ВИУ поступают на входные регистры КМАП. Векторная информация, выходящая с ВИУ, поступает через коммутатор векторных регистров КВР в буфер векторных регистров. В КВР вектор преобразуется в вектор обычных токенов и поступает на входные регистры КМАП. Несколько сложнее обстоит дело с формированием вектора для передачи его из скалярного вычислителя в векторное исполнительное устройство. Дело в том, что различные элементы вектора формируются в АП в различные неопределенные времена. Поэтому, чтобы сформировать вектор, в систему запускается специальная команда "фишка". Эта команда "фишка" состоит: из кода операции, кода команды, индекса итерации, кода поколения, поля количества элементов. Из этой команды "фишки" формируется токен "фишка", состоящий из вышеперечисленных команды "фишки" и поля кода номера регистра БВР. Когда происходит объединение токен "фишки" с данным, образуется пакет "фишка", состоящий из полей токена "фишки" и поля данного (Рис.8г).

Поля I, Т, П и NK служат для нахождения в АП элемента массива. Выполнение этой команды на исполнительном устройстве сводится к выдаче токена через коммутатор выхода К_вых в БВР, прибавлении D к одному из полей I, T, П, проверке на окончание цикла и выдачи нового токена на КМАП. Во вновь сформированном токене поле одного данного пустое. После нахождения нового элемента вектора в АП, этот пакет с одним данным передается на свободное ИУ и цикл повторяется, пока все элементы вектора не будут сформированы. После того как сформирован вектор, из БВР он передается в векторное устройство, но на этом работа команды "фишки" не прекращается, т.к. массив, который мы хотим сформировать в ВИУ, может состоять из нескольких подвекторов по 128 элементов. Существование команды "фишки" заканчивается после того, как все подвектора данного вектора сформированы. По окончанию работы, команда "фишка" формирует пакет для ВИУ, который предписывает ему сформировать вектор в векторной оперативной памяти (ОЗУ).

72

В.С.Бурцев. Выбор новой системы организации выполнения высокопараллельных вычислитель-ных процессов, примеры возможных архитектурных решений построения суперЭВМ

Исполнением этой операции будет токен, который ВИУ передаст через КМАП скалярному вычислителю. Этот токен известит систему о том, что данный вектор готов к работе. Виртуальный адрес вектора будет указан в передаваемом токене в поле данных.

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

Таким образом, взаимодействие всей скалярной вычислительной системы с ВИУ концептуально ничем не отличается от взаимодействия с исполнительным устройством с той только разницей, что в полях данных токенов и пакетов стоят не сами их данные, а описание векторов, их виртуальный адрес в ОЗУ ВИУ (Рис.8г).

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

7. Возможные варианты упрощения и развития структурной схемы машины потока данных

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

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

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

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

73

В.С.Бурцев. Выбор новой системы организации выполнения высокопараллельных вычислитель-ных процессов, примеры возможных архитектурных решений построения суперЭВМ

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

Как уже говорилось, основным звеном, сдерживающим производительность машины потока данных, является ассоциативная память. Если реализовать модуль памяти на интегральных схемах БИКМОП структуры с разрешающей способностью технологического процесса 0,7 микрон, то можно говорить о темпе работы, период которого не превышает 10 нс [4].

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

С таким темпом может справиться работа 2-4 транспьютеров, в каждом из которых может обрабатываться по два пакета одновременно в конвейерном режиме. Четыре коммутатора КМАП в построчном режиме обеспечат необходимый темп работы для АП.

Таким образом, максимальная производительность Пnk = 10¹⁰ операций в секунду будет реализована только в том случае, если параллелизм задачи на объеме памяти в 3 млн. слов будет не меньше

NC = N_KaH ( N_AПC_AП + N_kmpC_kmp + N_ИУС_ИУ + N_КМАПС_КМАП )

Напомним, что NC - это общее количество операций, которое должно выполняться в системе при ее полной загрузке; N_KaH - число каналов системы; N_ап, N_ИУ, N_kmp, N_КМАП - число однотипных устройств в блоке каждого канала; С_АП, С_кмр, С_ИУ, С_КМАП - уровень конвейеризации каждого устройства.

Так, для обеспечения темпа продвижения информации по кольцу, на современной технологической базе необходимо иметь N_АП=1, N_kmp=2, N_иу=2, N_КМАП=4 и соответственно С_ап=2, С_кмр=2, С_иу=2, С_КМАП=1, что соответствует времени операции АП=20 нс, времени операции КМР=40 нс, времени операции на транспьютере 40 нс и времени операции КМАП=40 нс. Общая максимальная производительность системы каналов при полной загрузке будет 10¹⁰ оп/с. Полная загрузка системы будет на участках задачи, где параллелизм