Многоуровневое устройство для коммутации процессоров в многопроцессорной вычислительной системе

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советских

Социалистических .

Республик

gij983? l 4 (61) Дополнительное к авт. свид-ву - (22) Заявлено12.01.76 (2 ) 2314210/18-24

iraq) + Кп 3 с присоединением заявки №G i 06 F 15/16

Государственный комитет

СССР но делам изобретений и открытий (23) Приоритет—

tS3) УДК681. 325 (088.8) Опубликовано 2 1282, Бюллетень ¹ 47

Дата опубликования описания 2 31282!

С.В.Горбачев, В.Б.Смирнов, В.А.Торгашев и Л.И.Бердников I (72) Авторы изобретения (71) Заявитель

У (54) МНОГОУРОВНЕВОЕ УСТРОЙСТВО ДЛЯ КОММУТАЦИИ ПРОЦЕССОРОВ

В мнОГОпРОцессОРИОЙ ВычислительнОЙ системе

Изобретение относится к вычислительной технике и может применяться при построении высокопроизводительных и вычислительных систем.

Известна вычислительная система, содержащая процессоры и блоки коммутации, которые образуют кольцо. Процессоры могут осуществлять межпроцессорный обмен, передавая данные по кольцу блоков коммутации, которые ,прОграммно управляются процессорами (.1 7°.

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

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

Целью изобретения является повышение надежности и коэффициента использования оборудования.

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

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

Модуль коммутации введены два входных приоритетных коммутатора, два выходных приоритетных коммутатора, два регистра индикаторов, два буферных регистра, причем второй выход блока управления соединен с первыми входами входных и выходных приоритетных ком- О мутаторов, третий выход блока управления соединен с вторыми входами входных коммутаторов, первые выходы которых соединены с третьим входом блока управления, соединенного двусторонни-35 ми связями с регистрами индикаторов, первые выходы выходных коммутаторов соединены с четвертым входом блока управления, первый выход которого соединен с первыми входами буферных 4р регистров, вторые входы которых соединены с вторыми выходами соответствукщих регистров Фиксации пути, пя,тый вход модуля коммутации соединен с третьим входом первого буферного 45 регистра, выход которого соединен с

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

На фиг.I изображена блок-,схема многоуровневого устройства для коммутации, на фиг.2 — входной приоритетный коммутатор на фиг.3 — выходной приоритетный коммутатор) на фиг.4 схема блока управления.

Блок-схема многоуровневого устройства для коммутации (Фиг.1) содержит процессор 1, модуль 2 коммутации, блок 3 управления, регистр 4 идентификации адреса, два регистра 5 и 6 фиксации пути, два входных приоритетных коммутатора 7 и 8 два выходных приоритетных коммутатора 9 и 10, два регистра 11 и .12 индикаторов, два буферных регистра 13 и 14.

Входной приоритетный .коммутатор 7 (8) включает триггер 15 приема, первый элемент И 16, второй элемент И 17, первый коммутатор 18.

Выходной приоритетный коммутатор

9 (10) содержит триггер 19 выдачи, третий элемент И 20, четвертый элемент И 21, второй коммутатор 22 и переключатель 23.

Блок 3 управления включает модификатор 24 адреса, блок 25 постоянной памяти, регистр 26 микрокоманды, схему 27 дешифрации и синхронизации, четыре коммутатора 28-31. устройство работает следующим образом. каждый процессор, входящий в состав машины, может находиться в свободном или активном (занятом) состоянии.

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

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

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

983714

Два регистра 11 и 12 индикаторов используются для того, чтобы для каждого из двух возможных направлений поиска свободных процессоров (при поступлении команды поиска с нижней шины в первый буферный регистр 13 и с верхней шины — во второй буферный регистр 14 соответственно) иметь информацию о наличии свободных процессоров в соответствующем направлении.

Содержимое первого регистра 11 инди- 1О каторов анализируется при поступлении в первый буферный регистр 13 запроса на установление соединения со свободным процессором. Если верхний индикатор равен единице, то это означает, 15 что если прокладывать путь через данный модуль 2 с информационной шины более низкого уровня на информационную шину более высокого уровня, то можно установить соединение со свободным gp процессором. Если же прокладывается путь с шины более высокого уровня на шину более низкого уровня, анализируется второй регистр 12 индикаторов.

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

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

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

В результате обработки этой информации входными приоритетными коммутаторами 7 и 8 определяется тот из модулей коммутаций, который выполняет 45 данную команду (например, команду поиска свободного процессора). Точно также и в случае необходимости выдачи команды на информационную шину сразу несколькими модулями 2, выход- 5Q ные приоритетные коммутаторы 9 и 10 этих модулей коммутации обрабатывают служебную информацию на линиях связи и определяют самый приоритетный модуль 2, который в данном случае и 55 выходит на информационную шину.

Регистр 4 идентификации адреса используется дпя хранения адреса данного модуля коммутации. Адреса определяют порядковые номерам модулей 2, подключенных к одной информационной шине. В модулях коммутации, подклю.ченных к информационным шинам различных уровней, используются независимые системы адресов.

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

Два регистра 5 и б фиксации используются для хранения адресов модулей 2, с которыми устанавливается соединение при прокладке пути. Благодаря занесению адресов в регистры 5 и б осуществляется фиксация пути при поиске свободного процессора.

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

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

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

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

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

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

Таким образом, в данной многопро 35 цессорной вычислительной машине за счет децентрализации процессов поисков процессоров и прокладки пути к ним и совместного их выполнения достигается уменьшение времени форми- 4Q рования соединения между процессорами. В данной многопроцессорной вычислительной машине формирование соединений н ходе выполнения вычислительного процесса может происходить одно- 45 временно и совершенно независимо внутри отдельных групп процессоров, между различными группами, на различных уровнях многоуровненой структуры системы связи, благодаря чему в прин" 5щ ципе может быть достигнута в||сокая производительность.Процедура формования соединений между процессорами позволяет обеспечить высокую надежность многопроцессорной вычислитель ной системы. бО . Многоуровневое устройство для коммутации процессоров н многопроцессорной вычислительной системе, содер: жащее на каждом уровне группы модулей коммутации, причем первые выход и ф5 вход, предыдущего модуля коммутации труппы одного уровня соединены соответственно с вторыми входом и выходом последующего модуля коммутации той же группы того же уровня, второй вход первого в группе модуля коммутациии одно го уровня соединен с третьим выходом модуля коммутации следующего более высокого уровня, первые вход и выход последнего s группе модуля коммутации одного уровня соединены с четвертыми соответственно выходом и входом модуля коммутации следующего более высокого уровня, модули коммутации группы одного уровня и соответствующий модуль коммутации

:ледующего более высокого уровня соеди

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

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

Источники информации, принятые во внимание при экспертизе

1. Евреинов Э.В.; Косарев Ь.Г. Îä нородные универсальные вычислительныа системы высокой производительности.

Новосибирск, "Наука", 1966, с.116 и

117.

2. Авторское свидетельство СССР по заявке 9 2052304/18-24, кл. G 06 F 15/16, 1974 (прототип) .

983714

Составитель Т.Арешев

Редактор A.éèèêèíà Техред Л.Пекарь

Корректор И. Ватрушкина

Филиал ППП "Патент", r.Óæãoðoä, ул.Проектная, 4

Заказ 9927/59 Тираж 731 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, (осква, Y(-35, Раушская наб., д.4/5