Мультипроцессорная система

(21) 368 (22) 16. (46) 15. (2) Р.И В.И. Сиг (71) Орд 255/24-241.835.85, Бюл. В 18Белицкий, А.В. Плов и Б.П, Малиновна Ленина институВ.М. Глушкова325(088.8)гишвили И,В, и дрсистемы, М., "На лаги ский кибернеки им.3) 681 6) Пра ссорнь237.Сошро 81 (и кропро,1978,г РезЦп, МагсЬтотип). ВЕННЫЙ КОМИТЕТ СССРИЗОБРЕТЕНИЙ И ОТНРЫТИИ ОПИСАНИЕ ИЗОБ ТОРСКОМУ СВИДЕТЕЛ(54)(57) 1. МУЛЬТИПРОЦЕССОРНАЯ СИСТЕМА, содержащая процессоры, общеезапоминающее устройство, коммутаторобщих устройств ввода-вывода и блокприоритета, группа выходов разрешениякоторого подключена к входам разрешения каждого процессора, выходы запросов которых подключены к группевходов запросов блока приоритета,адресные выходы каждого процессораподключены к группе адресных входовобщего запоминающего устройства и кгруппе входов управления коммутатораобщих устройств ввода-вывода, группа входов стробирования которого подключена к выходам стробирования группы управляющих выходов каждого процессора, информационные входы-выходы каждого процессора подключены кгруппе информационных входов-выходовобщего запоминающего устройства ик группе информационных входов-выходов коммутатора общих устройствввода-вывода, выходы управления памятью группы управляющих входов-выходов каждого процессора подключены к группе входов управления общегозапоминающего устройства, группысинхровходов процессоров объединенымежду собой и являются входом синхронизации системы, причем каждый процессор содержит микропроцессор, блоксинхронизации, регистр, буферные регистры адреса, данных, управления иблок памяти, адресный вход которогосоединен с адресным выходом микропроцессора и информационным входом буферного регистра адреса, выход которого является адресным выходом процессора, входы записи буферного регистра управления, буферного регистра адреса и буферного регистра данных объединены между собой, перваягруппа информационных входов-выходов ф фбуферного регистра данных подключена . Ск информационным входам-выходам процессора и к группе информационныхвходов регистра, вторая группа информационных входов-выходов буферногорегистра данных соединена с группойинформационных входов блока памятии группой информационных входов-выходов микропроцессора, тактовый входкоторого соединен с выходом блокасинхронизации, группа управляющихвыходов микропроцессора соединена сгруппой информационных входов буферного регистра управления и группойвходов управления записью блока памя"ти, выходы разрядов буферного регистра управления подключены к группеуправляющих входов-выходов процессора,о т л и ч а ю щ а я с я тем, что,с целью повышения производительности,входы-выходы признака прерывания про-.цессоров объединены между собой, а156088 Составитель П. Чистобородовексеенко Техред З.Палий ректор М. Демч ктор е одп иал аказ 3148/47 ВНИИПИ по де 113035, МТираж 710 Государственного лам изобретений осква, Ж, Рауш Пкомитета СССРоткрытийская наб д. 4/5 атент", г. Ужгород, ул, Проектная, 4каждый процессор дополнительно содержит дешифратор, триггер, три элемента И, элемент ИЛИ, группу элементов И, мультиплексор и одноразрядный блок памяти, адресный вход которого соединен с выходом мультиплексора, первая группа информационных входов которого соединена с выходами элементов И группы и второй группой информационных входов-выходов буферного регистра данных, вторая группа информационных входов мультиплексора подключена к первой группе информационных входов-выходов буферного регистра данных, вход записи которого Соединен с первым инверсным входом первого элемента И, первым входом второго элемента И, с входом разрешения группы управляющих входов-выходов про.цессора и входом синхронизации триггера, прямой выход которого соединен с вторым входом второго элемента И, выход которого соединен с входом-выходом признака прерывания процессора, входом разрешения мультиплексора и входом чтения одноразрядного блока памяти, выход которого соединен с входом прерывания микропроцессора и входом записи регистра, инверсный выход триггера соединен с входом блокировки буферного регистра управления, группа информационных входов которого соединена с группой информационных входов дешифратора, первый. выход которого соединен с управляющим входом мультиплексора и входом разрешения выдачи одноразрядного блока памяти, второй выход дешифратора соединен с входом установки триггера, а третий выход - с первыми входами элементов И группы, вторые входы которых соединены с группой выходов регистра, прямой вход первого элемента И соединен с выходом элемента ИЛИ, первый и второй входы которого соединены с выходами записи и чтения группы управляющих выходов микропроцессора соответственно, второй инверсный вход .первого элемента И соединен с выходом третьего элемента И, входом разрешения блока памяти и стробирующим входом дешифратора, вход селектирования которого подключен к выходу младшего разряда группы адресных выходов микропроцессора, выходы старших разрядов группы адресных выходов микропроцес - сора подключены к входам третьего элемента И, вход признака режима блока синхронизации соединен с выходом старшего разряда буферного регистра управления, вход запуска блока синхронизации соединен с выходом первого элемента И и выходом запроса процессора, информационный вход триггера соединен с шиной нулевого потенциала процессора, входы первой и второйсинхросерий микропроцессора являются группой синхровходов процессора.2. Система по п.1, о т л и ч а ю - щ а я с я тем, что микропроцессорсодержит регистр признаков, буферный регистр адреса, регистр текущих данных, сумматор, два элемента И, блок элементов И, узел регистров, регистр входных данных, регистр выходных данных, регистр команд, регистр адреса, блок памяти микрокоманд и регистр микрокоманд, вход разрешения которого соединен с выходом первого элемента И, первый вход которого является входом первой синхросерии микропроцессора, а второй вход - тактовым входом микропроцессора, информационный вход регистра микрокоманд соединен с выходом блока памяти микрокоманц, вход которого соединен с выходом регистра адреса, вход старших разрядов которого соединен с выходом регистра команд, информационный вход которого соединен с информационными входами регистра текущих данных, узла регистров, регистра входных данных и первым входом блока элементов И, второй вход которого соединен с выходом сумматора и входом первого элемента И, выход которого соединен с входом признака нуля регистра признака, вход признака.переполнения которого соединен с выходом старшего разряда сумматора, выход переноса которого соединен с входом признака переноса регистра признака, выход которого соединен с входом признаков регистра адреса, вход адреса следующей микрокоманды которого соединен с выходом поля адреса регистра микрокоманд, первая группа выходов разрядов управления которого соединена с входами управления сумматора, регистра текущих данных, регистра признаков, буферного регистра адреса, узла регистров, регистра входных данных, регистравыходных данных, регистра команд и вторым входом блока элементов И,1156088 30 35 40 выход узлз регистров соедттттетт сихолом первого операнда т ущчатсттта,информационными входами регттстраттыходиых данных и Гуферттого регистра адрес а, выход которого являетс.яадресным выходом микропроцессора,вход второй сиихросерии которого соединен с синхровходами буферногорегистра артреса, узла регистров,регистра признаков, регистра команд Изобретение относится к вттчисттительной технике и может быть использовано при создании мультипроцессорных систем (МПС) из микропроцессоров,МПС предназначены для решения 5 задач, требующих такой скорости обработки информации или достоверности результата, которые не могут быть достигнуты в однопроцессорной системе. Основа функционирования МПС - одно временное выполнение различными процессорами системы независимых или слабо зависимых частей общей программы (параллельных ветвей). Если одновременно выполняемые ветви не полностью независимы, между реализующими ихпроцессорами должен производиться информационный обмен, причем тем болееинтенсивный, чем сильней связанымежду собой ветви программы, При одновременном выполнении большого числа даже слабо связанных ветвей время, затрачиваемое на такие обмены,составляет значительную часть времени решения задачи. 25 Цель изобретения - увеличение производительности мультипроцессорной системы при динамическом распределении ее ресурсов.На фиг. 1 представлена структурная схема предлагаемой системы; на фиг. 2 - блох приоритета:, на фиг.3- схема процессора; на фиг, 4 - схема общего запоминающего устройства;.на фиг, 5 - схема коммутатора общих устройств ввода-вывода; на фиг. 6 - схема микропроцессора; на фиг. 7-10 -1 блок-схемы алгоритмов функционирования системы. и регттстра текущих данных, вттхстд которого соединен с входом второго операнда сумматора, группа вт.тхоцов регистра выходных данных соединена с.группой входов регистра входных данных и является группой информационньтх входов-выходов микропроцессора,группа управляющих выходов которогосоединена с группой ныхс 1 дов признаков регистра микрокоманд,Система состоит из несколькихпроцессоров 1, общего запоминающегоустройства 2, коммутатора 3 общихустройств ввода-вывода, блока 4 приоритета, связанных между собой внешними магистралями адреса 5, данных 6,управления 7, а также шиной 8 признака прерывания,Блок приоритета содержит входнойрегистр 9, выходной регистр 10, ком-бинационную схему 11, которая содержит первую группу элементов И 12 ивторую группу элементов И 13, элементы И 14 и 15, одновибратор 16, тактирующий генератор 17, входы 18 запросов, выходы 19 разрешения.Каждый процессор содержит микропроцессор 20, магистраль 21 данных,магистраль 22 адреса, управляющиешины 23, 24 и 25, дешифратор 26, элемент И 27, блок 28 памяти, буферныйрегистр 29 адреса, блок 30 синхронизации, буферный регистр 31 управления,элемент ИЛИ 32, элемент И 33, вход34 разрешения, выход 35 запроса,элемент И 36, триггер 37, буферный. регистр 38 данных, мультиплексор 39,одноразрядный блок 40 памяти, вход41 прерывания микропроцессора, регистр 42, группу элементов И 43, тактовый вход 44 микропроцессора, входы45 и 46 первой и второй синхросериимикропроцессора, управляющие выхо- .ды 47, адресные входы 48 и информационные входы-выходы 49 процессора. Общее запоминающее устройство содержит накопитель 50, группу элементов И 51, элементы И 52 и 53, элемент ИЛИ 54, одновибратор 55.Коммутатор общих устройств вводавывода содержит дешифраторы 56 и 57,группы элементов И 58-63,Микропроцессор содержит сумматор64, регистр 65 выходных данных, буферный регистр бб адреса, узел регистров 67, регистр 68 входных данных, блок элементов И 69, регистр 70текущих данных, регистр 71 команд,регистр 72 адреса, регистр 73 признаков, элемент И 74, регистр 75 микрокоманд, блок 76 памяти микрокоманд,элемент И 77.В качестве микропроцессора можетбыть использован стандартный микропроцессор КР 580 ИК 80,Система работает следующим обра Ветвь 2.Захватить семафор ветви 1,Записать в А 56088 4ным блокам памяти всех процессоров 1.Единичный уровень появляется на выходе одноразрядного блока памятитолько в процессоре, реализующем 3-ю5 ветвь программы. Этот уровень вызыва.ет прерывание работы этого процессора, и последний переходит к выполнению программы информационного обмена, например, через устройство 2.10 Для того, чтобы проиллюстрироватьработу системы, предположим, чтопараллельная программа состоит издвух ветвей;Ветвь 1,Ь 1, Захватить семафор ветви 1,Считать А.зом,Каждый процессор 1 может обращаться к общему запоминающему устройству 2 и к коммутатору общих устройствввода-вывода 3 с помощью магистралей5, 6 и 7. При необходимости использовать эти магистрали процессор устанавливает высокий уровень на своем 23выходе запроса шин. Сигналы запросашины, поступающие от всех элементарных процессоров, анализируются блоком 4, который устанавливает сигналвысокого уровня на входе разрешения 30шины того из запросивших шину элементарных процессоров, чей приоритетмаксимален.Каждый из элементарных процессоров, получив сигнал РазРешения шины, Зиспользуя магистрали 5-7, выполняетобращение к устройству 2 или коммутатору 3 и снимает запрос шины сосвоего выхода,Каждый процессор, получая для реа 40пизации ветвь программы, записываетв один из своих внутренних узлов одноразрядный блок памяти - едичицу в ячейке, соответствующей номеру выполняемой ветви. Таким образом, в 45 каждый конкретный момент времени в одноразрядном блоке памяти процессора. записаны единицы в ячейках, соответствующих выполняемым им ветвям программы. При возникновении у -го 50 процессора необходимости обменяться информацией с процессором, выполняющим 1-ю ветвь программы, 1-й процессор запрашивает шины и, получив их, выставляет на внешней магистрали 6 И данных код номера 3-й ветви и подает на шину 8 признака прерывания сигнал, инициирующий обращение к одноразряд единицу.Послать прерывание ветви 1, Освободить семафор ветви 1. Конец ветви 2. Если АФО, записать А в В,Перейти на Ь 2. Освободить семафор ветви 1.Останов,Перейти на Ь 1,Ь 2. Конец ветви 1,Пусть начальное содержание ячейки А в общем запоминающем устройстве равно "О",Управляющие таблицы программы вобщем запоминающем устройстве будутиметь вцц: Ветвь 1, Ветвь 2.Программа Программа1. 2.Признак испол- Признак исполняемости равен О. няемости равен О.Предположим далее, что в системе имеются три процессора. Тогда функционирование системы осуществляется следующим образом.Процессор с максимальным приоритетом под управлением программы операционной системы, размещенной в его внутреннем запоминающем устройстве, захватывает семафор управляющих таблиц, обращается к управляющим таблицам. В них процессор отыскивает не- исполняемую ветвь (ветвь 1), отмечает ее признаком исполняемости, равным единице, загружает и программу ветви 1 и освобождает семафор, Затем второй процессор захватывает семафор, обращается к управляющим таблицам, в которых обнаруживает, что ветвь 1 наполняется, а ветвь 2 не исполняется, отмечает ветвь 2 признаком исполняемости, равным единице,5 11560886загружает программу ветви 2 и освобождает семафор, Третий процессортакже обращается к таблицам, но обнаружив, что все ветви исполняются,переходит в режим ожидания. 5Первый и второй процессоры послезагрузки программ переходят к их исполнению, Исполнение программы ветвиначинается обращением к операционнойсистеме соответствующего процессора 10)которая осуществляет запись единицыв ячейку одноразрядного блока памяти. Так, первый процессор записываетединицу в ячейку, соответствующуюветви 1, а второй процессор - в ячейку, соответствующую ветви 2. Одноразрядный блок памяти третьего процессора не содержит единиц.Затем первый и второй процессорыначинают выполнениесвоих программ. 20Если первым семафор ветви 1 захватывает процессор, выполняющий ветвь 1,то он обнаруживает, что ячейка А содержит нуль, и переходит к командеостанова, после чего семафор захваты-Иваетвторой процессор. Этот процессор записывает в А единицу, посыпаетпрерывание ветви 1 и завершает выполнение своей программы, Сообщение опрерывании поступает на входы всех Щпроцессоров, но на него реагируетлишь первый, так как только в его одноразрядном блоке памяти имеетсяединица в ячейке, соответствующей ветви 1, Первый процессор в момент пре рывания либо находится перед первойкомандой программы, либо в состоянииостанова, что обеспечивается защитойостальной программы семафором и особенностью выдачи прерывания. В томи в другомслучае управление передается операционной системе, котораялишь увеличивает содержимое счетчикакоманд на единицу, т.е, передает управление следующей команде программы.5В первом случае управление непосредственно передается на метку 1, а вовтором - на команду перехода на мет- ляется разрешающий сигнап,ку 1. Поэтому в любом случае первый процессор считает единичное значе- у ванне из ячейки А, записывает его в ячейку В и переходит на метку 2 конца своей программы.Если же второй процессор захватывает семафор ветви 1 прежде, чем первый процессор записывает единицу в свой одноразрядный блок памяти, то посланное им прерывание не воспринимают ни первый, ни третий процессоры,и после того, как он закончит выполнение своей программы, первый процессор записывает единицу в свой одноразрядный блок памяти, считываетсодержимое ячейки А, где уже находится единица, записывает его в ячейкуВ и завершает выполнение своей программы, Таким образом, при любом ходе вычислительного процесса результатом параллельной программы будетА=1, В=1, на что не требуется нициклического опроса ячейки, ни дополнительного блокирования шины,Процессор работает следующим образом,При всяком обращении микропроцессор 20 устанавливает на внутреннеймагистрали 22 адреса код адреса,на шинах 23 и 24 - сигнал, определяющий направление передачи информациипо магистрали 21 данных (в микропроцессор - чтение, из микропроцессора - запись), а на шине признакаЗУ.или УВВ - сигнал, интерпретирующий код, выставленный на магистралиадреса, в качестве ячейки ЗУ илиномера устройства ввода-вывода. Призаписи микропроцессор выдает информацию на внутреннюю магистраль данных, а при чтении принимает.При обращении к блоку 28 памятимикропроцессор выставляет на магистрали 22 адреса код, старшие разрядыкоторого, воздействуя на элементИ 27, вызывают появление на выходепоследнего сигнала, разрешающегоработу блока 28 и дешифратора 26.Сигнал на управляющей шине 25 ЗУ илиУВВ выбирает один из названных блоков, запрещая другой. Работа выбранного устройства инициируется появлением сигнала на шинах 23 или 24.1 Фтадшая часть адреса при этом определяет номер ячейки в ЗУ, к которойпроизводится обращение, или тот выход дешифратора 26, на котором появПри обращении к общему запоминающему устройству 2 или коммутатору Э общих устройств ввода-вывода (фиг. 1) микропроцессор 20 выставляет на и внутренней магистрали 22 адреса код, старшая часть которого не вызывает появления на выходе элемента И 27 сигнала "лог. 1". Поэтому появление сигналов записи ипи чтения на шинах ,23 или 24 вызывает появление сигна1156088 7ла уровня "лог.1" на выходе элемента И 33, Этот сигнал приостанавливает работу микропроцессора, воздействуя на него через блок 30 синхронизации, и поступает на выход 35 за5 проса шин, взаимодействуюший с блоком 4, Сигнал блока 4 по входу 34 разрешения шин подключает регистры 29, 31 и 38 к внешней магистрали системы, Регистры открыты до тех пор, 10 пока микропроцессор не закончит цикл обращения к общему запоминающему устройству или коммутатору общих УВВ. Время цикла обращения в этом случае задается сигналом "Готов" внешней 15 магистрали, который воздействует на вход 44 микропроцессора 20 через регистр 31 и блок 30 синхронизации, Момент окончания цикла определяется микропроцессором 20, который снимает 20 сигналы записи или чтения, вследствие чего блок.4 устанавливает на входе 34 уровень "лог.0", закрывая регист - ры 29, 31 и 38 и отключая внутренние магистрали процессора от внешних. 25При записи информации в одноразрядный блок 40 памяти микропроцессор выставляет на шине поизнака ЗУ или УВВ сигнал "лог, 0", на магистрали адреса - код, вызывающий появление 30 сигнала на втором выходе дешифратора 26. Этот сигнал переключает мультиплексор 39 таким образом, что информация с внутренней магистрали 21 данных поступает на адресные и информационные входы блока 40. Код, выставляемый микропроцессором 20 на магистрали 21 данных, определяет адрес ячейки в блоке 40 и записываемый в эту ячейку код. 40Для передачи прерывания на какой- либо процессор системы микропроцессор 20 устанавливает триггер 37 в состояние "1", выполняя цикл записи в УВВ. Триггер 37 своим нулевым выходом блокирует регистр 31. Палее описанным способом инициируется цикл, аналогичный записи в общее запоминающее устройство. Однако при получении с внешней магистрали сигнала разреше-д ния открываются регистры 29 и 38 (регистр 31 блокирован) и элемент И 36, который выставляет на внешней магистрали сигнал на шине 8 признака прерывания. Сигналы чтения и записи у на внешнюю магистраль через блокированный регистр 31 не поступают, Таким образом, на внешней магистрали 6 данных оказывается код номера прерываемой ветви, сопровождаемый сигналомва шине 8 признака прерывания.Этот сигнал воздействует на входычтения одноразрядных блоков 40 памяти всех процессоров. Код с внешнеймагистрали данных выбирает в блоке40 ячейку, к которой производитсяобращение, Если в данном процессореиз блока 40 прочитана единица, намикропроцессор 20 поступает запроспрерывания и в регистр 42 записывается с внешней магистрали 6 данных кол,вызвавший это прерывание. Реагируяна сигнал запроса прерывания, микропроцессор 20 принимает информацию изрегистра 42, производит операцию обращения, при которой на дешифраторе26 оказывается в состоянии "лог. 1"выход, управляющий группой 43. Анализируя эту информацию, микропроцессор выясняет, по какой из выполняемых им ветвей программы произошлопрерывание, и производит действия,предусмотренные программой реакциина прерывание,Алгоритм работы элементарного процессора с одноразрядным запоминающимустройством состоит из четырех фаз:выбора очередной ветви, завершенияочередной ветви, обработки прерывания от собственного одноразрядного блока памяти,передачипрерывания одноразрядному блоку памяти другого процессора.Первая фаза алгоритма.Загрузка программы очереднойветви в запоминающий блок процессора.2. Запоминание семиразрядногокода признака (имени) ветви на регистре процессора,3. Формирование единицы в восьмом разряде регистра.4, Захват семафора ветви,5. Выдача восьмиразрядного содери,имого регистра в одноразрядныйблок памяти,б. Освобождение семафора ветви,Замечание 1, Семиразрядные кодыприсваиваются именам ветвей притрансляции и хранятся в управляющихтаблицах ветвей, Таким образом может быть не более 128 различных имен ветвей.Вторая фаза алгоритма,1. Захват семафора ветви.2. Формирование нуля в восьмомразряде регистра,содержащемимя ветви,3. Выдача содержимого регистрав одноразрядный блок памяти.4. Освобождение семафора ветви.Третья фаза алгоритма.1, Анализ процессором причиньгпрерывания.2, Если причина прерывания связана с одноразрядным блоком памяти,сравнение переданного извне имениветви с именем исполняемой ветви длявыявления ситуации, когда завершениеветви и прерывание произошли одновременно.3. Если имена ветвей совпали,переход на подпрограмму обработкипрерывания, связанную с данной ветвью. 15Четвертая фаза алгоритма.1, Запоминание кода имени ветви,на регистре.2, Захват семафора ветви, которойпередается прерывание. Ю3. Выдача содержимого регистра водноразрядный блок памяти.Замечание 2, Каждый одноразрядныйблок памяти в мультипроцессорнойсистеме имеет два адреса - один для 5собственного процессора и один дляостальных,Общее запоминающее устройство работает следующим образом.Работа устройства инициируетсяпоявлением высоких уровней на шинахчтения или записи внешней магистрали7 управления при низком уровне нашине выбора ЗУ илй УВВ той же магистрали. При записи высокий уровеньпоявляется на выходе элемента И 52,инициируя операцию записи в накопителе (адрес ячейки задается кодомна магистрали 5, а заносимый код -магистралью 6), Через элемент ИЛИ 54инициируется одновибратор 55, устанавливающий на шийе "Готов" магистрали 7 низкий уровень на время обращения к накопителю,При чтении информации из устройства высокий уровень с выхода элемента И 53 инициирует операцию чтения из накопителя 50, одновременно открывая группу элементов И 51. Синхронизация через шину Готов" производится так же, как при записи.