Многоуровневое устройство для коммутации процессоров в многопроцессорной вычислительной системе Советский патент 1982 года по МПК G06F15/163 

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

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

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

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

для коммутации процессоров. В этой системе для установления связей между процессорами используется децентрализованный волновой алгоритм поиска пути к свободным процессорам 2J.

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

10 происходит распространение волновой помощи установления связи по всей многоуровневой структуре систе№Л, что препятствует одновременному распространению других процессовi.у установле15ния межпроцессорных связей. Кроме того, модуль коммутации, реализующий волновой алгоритм установления связи, име.ет сложную структуру, что снижает надежность всей системы.

20

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

Поставленная цель достигается тем, что в многоуровневое устройство для

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

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

следующего более высокого уровня, первые вход и выход последнего в группе модуля коммутации одного уровня соединены с четвертыми соответственно выходом и входом модуля коммута- 0 ции следующего более высокого уровня, модули коммутации группы одного уровня и соответствующий модуль коммутации следующего более высокого уровня соединены между собой/через общую Ыину, акаждый модуль коммутации, содержит блок управления, соединенный двусторонней связью с регистром идентификации адреса, первый выход блока управления соединен с первыми входами первого и второго регистров фиксации пути, первые выходы которых соединены соответственно с первым и вторым входами блока управления, в каждый. Кюдуль коммутации введены два входных приоритетных коммутатора, два выходных приоритетных коммутатора, два регистра индикаторов, два буферных регистра, причем второй выход блока управления соединен с первыми входами входных и выходных приоритетных ком- О мутаторов, третий выход блока управления соединен с вторыми входами входных ксФлмутаторов, первые выходы которых Соединены с третьим входом блока управления, соединенного двусторонни-35 ми связями 1C регистрами индикаторов, первые выходы выходных коммутаторов соединены с четвертым входом блока управления, первый выход которого соединен с первыми входами буферных 40 регистров, вторые входы которых соединены с вторыми выходами соответствующих регистров фиксации пути, пятый вход модуля коммутации соединен с третьим входом первого буферного 45 регистра, выход которого соединен с

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

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

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

Блок-схема многоуровневого устройства для коммутации (фиг.1) содержит процессор 1, модуль 2 коммутации, блок 3 управления, регистр 4 идентификации ада1еса, два регистра 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 коммутации имеется целеуказание, т.е. информация, показывающая, можно ли найти искомый тип свободного процессора, если прокладывать путь через данный модуль коммутации . Два регистра 11 и 12 индикаторов используются для того, чтобы для каж дого из двух возможных направлений поиска свободных процессоров (при по ступлении команды поиска с нижней шины в первый буферный регистр 13 и с верхней шины - во второй буферный регистр 14 соответственно) иметь информацию о наличии свободных процессоров в соответствующем направлении. Содержимое первого регистра 11 индикаторов анализируется при поступлени Б первый буферный регистр 13 запроса на установление соединения со свобод ным процессором. Если верхний индика тор равен единице, то это означает, что если прокладывать путь через данный модуль 2 с информационной 1иин более низкого уровня на информационную шину более высокого уровня, то можно установить соединение со свободным процессором. Если же прокладывается путь с. шины более высокого уровня на шину более низкого уровня, анализируется второй регистр 12 индикаторо В буферные регистры блока 2 записыва ется как командная, так и числовая . нформация. Характер информации определяется схемами управления блока 2, Каждая порция информации начинается с команды, по коду операции которой схемы управления блока 2 определяются, будет ли следовать за командой числовая информация или нет. Команда поступающая с информационной шины во все модули 2 коммутации, подключенные к ней, обрабатывается в их блоках 3 управления. Одновременно с эти входные приоритетные коммутаторы 7 и 8 этих модулей обрабатывают служебну информацию, поступающую по линиям связи данного уровня (того же уровня что и уровень информационных шин). В результате обработки этой информации входными приоритетными коммутаторами 7 и 8 определяется тот из модулей коммутаций, который выполняет данную команду (например, команду поиска свободного процессора). Точно также и в случае необходимости выдачи команды на информационную шину сразу несколькими модулями 2, выходные приоритетные коммутаторы 9 и 10 этих модулей коммутации обрабатывают служебную информацию на линиях связи и определяют самый приоритетный модуль 2, который в данном случае и выходит на информационную шину. Регистр 4 идентификации адреса используется для хранения адреса данного модуля коммутации. Адреса определяют порядковые номерам модулей 2, подключенных к одной информационной шине. В модулях коммутации, подключенных к информационным шинам различных уровней, используются независимые система адресов. . Адрес модуля коммутации используется при фиксации пути между двумя модулями 2, подключенными к одной информационной шине. При этом модули коммутации, через которые устанавливается соединение, обмениваются гшресами. В дальнейшем при передаче информации по проложенному пути адреса, сопровождающие порцию информации сравниваются с адресом, хранящимся в регистре 4 идентификации адреса. Два регистра 5 и б фиксации используются для хранения адресов модулей 2, с которыми устанавливается соединение при прокладке пути. Благо- . даря занесению адресов в регистры 5 и 6 осуществляет-ся фиксация пути при поиске свободного процессора. После установления соединения со свободным процессором, последний выдает сообщение о том, что соединение установлено, которое по проложенному пути передается процессору - инициатору установления соединения. Получив сообщение об установлении соединения, процессор-инициатор может начать обмен информацией по проложенному пути. Каждая порция передаваемой по пути информации сопровон ;дается на каждом уровне адресом того модуля коммутации, через который проложен путь на шину другого уровня. После окончания совместной работы путь между процессорами, если последующего обмена информацией не предполагается, может 6tJTb разрушен. Если предполагается, что в дальнейшем возможен повторный обмен информацией, то пеоед разрушением соединения производится опрос пути, соединяющего процессоры, с целью определения адресов коммутаторов, через которые этот путь был проложен. Разрушение пути производится для того, чтобы неиспользуемые в течение некоторого времени соединения не уменьшали бы пропускную способность многоуровневой системы связи многопроцессорной вычислительной ма1-1ины. Рассматриваемая система связи процессоров имеет древовидную структуру, и между двумя процессорами путь можот быть проложен только единственным образом. Поэтому при последующих обращениях к конкретному процессору достаточно знать последовательность адресов коммутаторов, чтобы восстановить прежний путь. Процедура прокладки пути через коммутаторы при формировании соединений между процессорами позволяет организовать эффективную и высоконадежную защиту памяти. При установлении соединения с любым свободным процессором, расположенным в том числе и в другой группе, процессор-инициатор соединения может получить непосредственный доступ к памяти свободного процессора. Опросив путь, по кото рому осуществляется между процессора ми обмен информацией, каждый из них может определить относительный адрес другого процессора и запомнить его. Хранение относительных адресов позво ляет отличить истинных владельцев ин формации, размещенной в блоке оперативной памяти данного процессора, от случайно обратившихся к этому процес сору. Для этого необходимо при повто ных обращениях к конкретному процессору, соединение с которым было вреNffiHHO разрушено вслед за командой Восстановить путь по,сылать команду Опрос пути. Вновь набранная при оп росе пути последовательность адресов коммутаторов, через которые был про :oжeн. путь,. сравнивается с записанны ранее относительным адресом того про цессора, который первоначально сформировал соединение с данным процессо ром. Только в случае совпадения хранящегося и вновь прошедшего относительных адресов, запраьшваютему процессору разрешается непосредственная работа с данными, размещенными в блоке оперативной памяти данного про цессора. Поскольку между двумя процессорами в данной многоуровневой структуре многопроцессорной вычислительной машины существует только единственный путь, то абсолютно исключается возможность обращения к памяти постороннего процессора. Таким образом, в данной многрпро цессорной вычислительной машине за счет децентрализации процессов поисков процессоров и прокладки пути к ним и совместного их выполнения достигается уменьшение времени формирования соединения между процессорами. В данной многопроцессорной вычис лительной машине формирование соединений в ходе выполнения вычислительного процесса может происходить одно временно и совершенно независимо внутри отдельных групп процессоров, между различными группами, на различ ных уровнях многоуровневой структуры системы связи, благодаря чему в приН ципе может быть достигнута высокая производительность.Процедура формования соединений между процессорами позволяет обеспечить высокую надежность многопроцессорной вычислител ной системы. Формула изобретения Многоуровневое устройство для коммутации процессоров в многопроцес сорной- вычислительной системе, содер жащее на каждом уровне группы модулей коммутации, причем первые выход вход предыдущего модуля коммутации группы одного уровня соединены соответственно с вторыми входом и выходом последующего модуля коммутации той же группы того же уровня, второй вход первого в группе модуля коммутации одного уровня соединен с третьим выходом модуля коммутации следующего более высокого уровня, первые вход и выход последнего в группе модуля коммутации одного уровня соединены с четвертыми соответственно выходом и входом модуля коммутации следующего более высокого уровня, модули коммутации группы одного уровня и соответствующий модуль коммутации следующего более высокого уровня соеди иены между собой через общую шину, а каждый модуль коммутации содержит блок управления, соединенный двусторонней связью с регистром идентификации адреса, первый выход блока управления соединен с первыми входами первого и второго регистров фиксации пути , первые выходы которых соединены соответственно с первым и вторым входами блока управления, отличающее с я тем что, с целью пошл-шения надежности и коэффициента использования оборудования, в каждый модуль коммутации введены два входных приоритетных коммутатора, два выходных приоритетных коммутатора, два регистра индикаторов, два буферных регистра, причем второй выход блока у правления соединен с первыми входами входных и выходных приоритетных коммутаторов, третий выход блока управ-ления соединен с вторыми входами вход,ных коммутаторов, первые выходы которых соединены с третьим входом блока управления, соединенного двусторонними связями с регистрами индикаторов, первые выходы выходных коммутаторов соединены с четвертым входом блока управления, первый выход которого соединен с первыми входами буферных регистров, вторые входы которых соединены с вторыми выходс1ми соответствующих регистров фиксации пути, пятый вход модуля коммутации соединен с третьим входом первого буферного регистра, выход которого соединен с вторим входом второго регистра фиксации пути, пятым входом блока управления и третьим входом второго буферного регистра, выход которого соединен с четвертым входом первого буферного регистра, вторым входом первого регистра фиксации пути и шестым входом блока управления, второй буферный регистр соединен двусторонней связью с общей шиной, третий вход и второй выход первого входного приоритетного коммутатора соединены соответственно с четвертым входом и третьим выходом модуля коммутации, третий вход и второй выход второго входного приори,тетного коммутатора соединен соответ.ственно с вторым входом и первым выходом модуля коммутации, вторые вход и выход первого выходного приоритетного коммутатора соединены соответственно с третьим входом и четвертым выходом модуля коммутации, вторые вход и выход второго выходного приоритетного коммутатора соединены соответственно с первым входом и вторым выходом модуля коммутации.

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

1.Евреинов Э.В. , Косарев to.Г. Оя нородные универсальные вычислительны

системы высокой производительности. Новосибирск, Наука, 1966, с.116 и 117.

2.Авторскоесвидетельство СССР по заявке 2052304/18-24,

кл. G 06 F 15/16, 1974 (прототип).

e.f