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

ОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СоветскихСоциалистических .Республик 198 3714(22) Заявлено 12,01. 76 (21) 2314210/18-24 1 М Кп 3 с присоединением заявки М 6106 Г 15/16 Государственный комитет СССР по делам изобретений и открытий(54) МНОГОУРОВНЕВОЕ УСТРОЙСТВО ДЛЯ КОММУТАЦИИ ПРОЦЕССОРОВВ МНОГОПРОЦЕССОРНОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЕ Изобретение относится к вычислительной технике и может применятьсяпри построении высокопроизводительных и вычислительных систем,Известна вычислительная система,содержащая процессоры и блоки коммутации, которые образуют кольцо. Процессоры могут осуществлять межпроцессорный обмен, передавая данные покольцу блоков коммутации, которые,прОграммно управляются процессорами .1 3Недостатком этой системы являетсяпоследовательный принцип передачи информации по кольцу, образованномублоками коммутации, что ограничиваетэффективность вычислительной системыи не позволяет в значительных пределах увеличивать производительностьсистем эа счет подключения дополнительных ресурсов, так как при этомеще более ухудшается коэффициент использования оборудования.Наиболее близким техническим решением к изобретению является многоуровневое устройство для коммутациипроцессоров в многопроцессорной вычислительной системе, содержащее процессоры и модули коммутации, которыеобразуют многоуровневое устройство для коммутации процессоров. В этойсистеме для установления связей между процессорами используется децентрализованный волновой алгоритм поиска пути к свободным процессорам 2),Однако устройство имеет недостаточную эффективность, так как при установлении связи с одним свободнымпроцессором по волновому алгоритмупроисходит распространение волновойпомощи установления связи по всей многоуровневой структуре системы, чтопрепятствует одновременному распространению других процессов., установления межпроцессорных связей. Кроме того, модуль коммутации, реализующийволновой алгоритм установления связи, имеет сложную структуру, что снижает надежность всей системы.Целью изобретения является повышение надежности и коэффициента использования оборудования.Поставленная цель достигается тем,что в многоуровневое устройство длякоммутации, процессоров в многопроцессорной вычислительной системе, содержащее на каждом уровне группы модулей коммутации, причем первые выход и вход предыдущего модуля комму- ЗО тации группы одного уровня соединенысоответственно с вторыми входом и выходом последующего модуля коммутации той же группы того же уровня, второй вход первого в группе модуля коммутации одного уровня соединен с третьим выходом модуля коммутации 5 .,следующего более высокого уровня, первые вход и выход последнего в группе модуля коммутации одного уровня соединены с четвертыми соответственно выходом и входом модуля коммута ции следующего более высокого уровня, модули коммутации группы одного уровня и соответствующий модуль коммутации следующего более высокого уровня соединены между собой,через общую Мину, акаждый модуль коммутации, содержит блок управления, соединенный двусторонней связью с регистром иден-) тификации адреса, первый выход блока управления соединен с первыми входами первого и второго регистров фиксации пути, первые выходы которых соединены соответственно с первым и вторым входамй блока управления, в каждый Модуль коммутации введены два входных приоритетных коммутатора, два выходных приоритетных коммутатора, два регистра индикаторов, два буферных регистра, причем второй выход блока управления соединен с первыми входами входных и выходных приоритетных ком мутаторов, третий выход блока управления соединен с вторыми входами входных коммутаторов, первые выходы которых соединены с третьим входом блока управления, соединенного двусторонними связямис регистрами индикаторов, первые выходы выходных коммутаторов соединены с четвертым входом блока управления, первый выход которого соединен с первыми входами буферных 40 регистров, вторые входы которых соединены с вторыми выходами соответствукщих регистров Фиксации пути, пя,тый вход модуля коммутации соединен с третьим входом первого буферного 45 регистра, выход которого соединен с ,вторым входом второго регистра Фиксации пути, пятым входом блока управ-. ления и третьим входом второго буферного регистра, выход .которого соединен с четвертым входом первого буферного регистра, вторым входом первого регистра фиксации пути и шестым вхо,дом блока управления, второй буферный регистр соединен двусторонней связью ,с общей шиной, третий вход и вторай выход первого входного приоритетного коммутатора соединены соответственно с четвертым входом и третьим выходом модуля коммутации, третий вход и второй выход второго входного приоритетного коммутатора соединены соответственно с вторым входом и первым выходом модуля коммутации, вторые вход и выход первого выходного приоРитетного коммутатора соединены со ответственно с третьим входом и четвертым выходом модуля коммутации, вторые вход и выход второго выходного приоритетного коммутатора соединены соответственно с первым входом и вторым выходом модуля коммутации.На Фиг.1 изображена блок-,схемамногоуровневого устройства для коммутации, на фиг.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 коммутации имеется целеуказание, т.е, информация, показывающая, можно ли найти искомый типсвободного процессора, если прокладйвать путь через данный модуль коммутации.Два регистра 11 и 12 индикаторов используются для того, чтобы для каждого из двух возможных направлений поиска свободных процессоров (при поступлении команды поиска с нижней шины в первый буферный регистр 13 и с верхней шины - во второй буферный регистр 14 соответственно) иметь информацию о наличии свободных процессоров в соответствующем направлении, Содержимое первого регистра 11 инди- О каторов анализируется при поступлении в первый буферный регистр 13 запроса на установление соединения со свободным процессором. Если верхний индикатор равен единице, то это означает, 15 что если прокладывать путь через данный модуль 2 с информационной шины более низкого уровня на информационную шину более высокого уровня, то можно установить соединение со свободным 2 О процессором. Если же прокладывается путь с шины более высокого уровня на шину более низкого уровня, анализируется второй регистр 12 индикаторов. В буферные регистры блока 2 записывается как командная, так и числовая нформация. Характер информации определяется схемами управления блока 2, Каждая порция информации начинается с команды, по коду операции которой схемы управления блока 2 определяются, будет ли следовать за командой числовая информация или нет. Команда, поступающая с информационной шины во все модули 2 коммутации, подключенные к ней, обрабатывается в их блоках 3 управления. Одновременно с этим входные приоритетные коммутаторы 7 и 8 этих модулей обрабатывают служебную информацию, поступающую по линиям связи данного уровня (того же уровня, 4 О что и уровень информационных шин). В результате обработки этой информации входными приоритетными коммутаторами 7 и 8 определяется тот из модулей коммутаций, который выполняет 45 данную команду (например, команду поиска свободного процессора). Точно также и в случае необходимости выдачи команды на информационную шину сразу несколькими модулями 2, выход О ные приоритетные коммутаторы 9 и 10 этих модулей коммутации обрабатывают служебную информацию на линиях связи и определяют самый приоритетный модуль 2, который в данном случае и 55 выходит на информационную шину.Регистр 4 идентификации адреса используется дпя хранения адреса данного модуля коммутации. Адреса определяют порядковые номерам модулей 2, подключенных к одной информационной шине. В модулях коммутации, подключенных к информационным шинам различных уровней, используются независимые системы адресов.65 Адрес модуля коммутации используется при фиксации пути между двумя модулями 2, подключенными к одной информационной шине, При этом модули коммутации, через которые устанавливается соединение, обмениваются адресами. В дальнейшем при передаче информации по проложенному пути адреса,сопровождающие порцию информациисравниваются с адресом, хранящимся врегистре 4 идентификации адреса. Два регистра 5 и б Фиксации используются для хранения адресов модулей 2, с которыми устанавливается соединение при прокладке пути, Благодаря занесению адресов в регистры 5и б осуществляется Фиксация пути припоиске свободного процессора.После установления соединения сосвободным процессором, последний выдает сообщение о том, что соединениеустановлено, которое по проложенному пути передается процессору - инициатору установления соединения. Получив сообщение об установлении соединения, процессор-инициатор может начать обмен информацией по проложенному пути. Каждая порция передаваемойпо пути информации сопровождается накаждом уровне адресом того модулякоммутации, через который проложенпуть на шину другого уровня.После окончания совместной работыпуть между процессорами, если последующего обмена информацией не предполагается, может быть разрушен. Еслипредполагается, что в дальнейшем возможен повторный обмен информацией, то пеоед разрушением соединения производится опрос пути, соединяющегопроцессоры, с целью определения адресов коммутаторов, через которые этотпуть был проложен, Разрушение пути производится для того, чтобы неиспользуемые в течение некоторого времени соединения не уменьшали бы пропускную способность многоуровневой системы связи многопроцессорной вычислительной ма ины. Рассматриваемая система связи процессоров имеет древовидную структуру, и между двумя процессорами путь может быть проложентолько единственным образом. ПоэтомУпри последующих обращениях к конкретному процессору достаточно знать последовательность адресов коммутаторов,чтобы восстановить прежний путь.Процедура прокладки пути через коммутаторы при формировании соединений между процессорами позволяет организовать эффективную и высоконадежную защиту памяти. При установлении соединения с любым свободным процессором, расположенным в том числе и в другой группе, процессор-инициатор соединения может получить непосредственный доступ к памяти свободно 9 В 3714формула изобретения го процессора, Опросив путь, по кото рому осуществляется между процессора 1 ми обмен информацией, каждый из них . может определить относительный адрес другого процессора и запомнить его. Хранение относительных адресов поэво ляет отличить истинных владельцев ин формации, размещенной в блоке опера тинной памяти данного процессора, от случайно обратившихся к этому процессору. Для этого необходимо при повтор 10 ных обращениях к конкретному процессору, соединение с которым было временно разрушено, вслед за командой , "Восстановить путь" посылать команду фОпрос пути". Вновь набранная при оп росе пути последовательность адресов коммутаторов, через которые был проложен путь,. сравнивается с записанным ранее относительным адресом того процессора, который первоначально сформировал соединение с данным процессором. Только н случае совпадения хранящегося и вновь прошедшего относительных адресов, запрашивающему процессору разрешается непосредственная работа с данными, размещенными в блоке оперативной памяти данного процессора. Поскольку между двумя процессорами в данной многоуровневой структуре многопроцессорной вычислительной машины существует только единственный путь, то абсолютно исключается возможность обращения к памяти постороннего процессора. Таким образом, в данной многопро 35цессорной вычислительной машине засчет децентрализации процессов поис.ков процессоров и прокладки пути кним и совместного их выполнения достигается уменьшение времени формирования соединения между процессорами. В данной многопроцессорной вычислительной машине формирование соединений н ходе выполнения вычислительного процесса может происходить одновременно и совершенно независимовнутри отдельных групп процессоров,между различными группами, на различных уровнях многоуровненой структурысистемы связи, благодаря чему в приН Оципе может быть достигнута высокаяпроизводительность,Процедура формования соединений между процессорамипозволяет обеспечить высокую надежность многопроцессорной нычислителной системы,бОМногоуровневое устроистно длякоммутации процессоров н многопроцессорной вычислительной системе, содер; жащее на каждом уровне группы модулей коммутации, причем первые выход и 65 вход, предыдущего модуля коммутациитруппы одного уровня соединены соответственно с вторыми входом и выходом последующего модуля коммутациитой же группы того же уровня, второйвход первого в группе модуля коммутации одного уровня соединен с третьим выходом модуля коммутации следующего более высокого уровня, первыевход и выход последнего в группе модуля коммутации одного уровня соединены с четвертыми соответственно выходом и входом модуля коммутации следующего более высокого уровня, модуликоммутации группы одного уровня и соответствующий модуль коммутации:ледующего более высокого уровня соедииены между собой через общую шину, акаждый модуль коммутации содержитблок управления, соединенный двусторонней связью с регистром идентификации адреса, первый выход блока управления соединен с первыми входами первого и второго регистров фиксации пути, первые выходы которых соединенысоответственно с первым и вторым входами блока управления, о т л и ч а -ю щ е е с я тем, что, с целью повышения надежности и коэффициента использования оборудования, в каждыймодуль коммутации введены два входныхприоритетных коммутатора, два выходных приоритетных коммутатора, дварегистра индикаторов, дна буферныхрегистра, причем второй выход блокауправления соединен с первыми входамивходных и выходных приоритетных коммутаторов, третий выход блока управления соединен с вторыми входами вход,ных коммутаторов, первые выходы которых соединены с третьим входом блокауправления, соединенного двусторонними связями с регистрами индикаторов,первые выходы выходных коммутаторовсоединены с четвертым входом блокауправления, первый выход .которогосоединен с первыми входами буферныхрегистров, вторые входы которых соединены с вторыми выходами соответствующих регистров фиксации пути, пятый вход модуля коммутации соединенс третьим входом первого буферногорегистра, выход которого соединен свторым входом второго регистра фиксации пути, пятым входом блока управления и третьим входом второго буферного регистра, выход которого соединен с четвертым входом первого буФерного регистра, вторым входом первогорегистра фиксации пути и шестым входом блока управления, второй буферныйрегистр соединен двусторонней связьюс общей шиной, третий вход и второйвыход первого входного приоритетногокоммутатора соединены соотнетственнос четвертым входом и третьим выходоммодуля коммутации, третий вход ивторой выход второго входного приори,тетного коммутатора соединен соответ,ственно с вторым входом и первым выходом модуля коммутации, вторые входи выход первого выходного приоритетного коммутатора соединены соответственно с третьим входом и четвертым 5выходом модуля коммутации, вторыевход и выход второго выходного приоритетного коммутатора соединены соответственно с первым входом и вторым выходом модуля коммутации. 10 Источники информации,принятые во внимание при экспертизе 1. Евреинов Э.В.; Косарев Ь.Г. Од"нородные универсальные вычислительныасистемы высокой производительности.Новосибирск, "Наука", 1966, с.116 и117 .2. Авторское свидетельство СССРпо заявке Ю 2052304/18-24,кл. 6 06 Г 15/16, 1974 (прототип).983714 Составитель Т.АрешевРедактор А.аникина Техред Л.Пекарь Корректор И. Ватрушкина к Ужгород, ул. Проектная, 4 лиал ППП тент 927/59 Тираж 731 ВНИИПИ Государственного по делам изобретений и 113035, Иосква, Ж, Р мит кры ска дписноеСССРб., д.4/5