Арбитр мультипроцессорной системы
Изобретение относится к вычислительной технике и может быть использовано для распределения общих ресурсов: секций памяти и шин с временным разделением между процессорами в мультипроцессорных системах. Целью изобретения является увеличение производительности мультипроцессорной системы при поступлении запросов общих ресурсов . С этой целью в арбитр мультипроцессорной системы, содержащий блок памяти состояния и микропрограммный автомат, введены счетчик, коммутатор адресов, регистр, три блока стековой памяти и две группы блоков стековой памяти. 13 ил. (Л С
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК (5D 4 С 06 F 13/00
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
К АВТОРСКОМЪ СВИДЕТЕЛЬСТВУ
ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР
flO ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3781940/24-24 (22) 14. 08. 84 (46) 30. 08. 86. Бюл. И 32 (71) Рязанский радиотехнический институт (72) В.П.Корячко и Н.А.Смоляров (53) 681.325(088.8) (56) Патент США У 4237534, кл. С 06 F 9/46, G 06 F 11/00, 1980.
Lang Т.1 Va?его М. "М-users В-servers arbiter for multiple-busses
multiprocessors", Hiегоprocessing and
microprogramming, 1982, v. 1О, р. 11-.18. (54) АРБИТР МУЛЬТИПРОЦЕССОРНОЙ СИС.ТЕМЫ
„„SU„„1 254494 А 1 (57) Изобретение относится к вычислительной технике и может быть использовано для распределения общих ресурсов: секций памяти и шин с временным разделением между процессорами в мультипроцессорных системах. Целью изобретения является увеличение производительности мультипроцессорной системы при поступлении запросов общих ресурсов. С этой целью в арбитр мультипроцессорной системы, содержащий блок памяти состояния и микропрограммный автомат, введены счетчик, коммутатор адресов, регистр, три блока стековой памяти и две группы блоков стековой памяти. 13 ил.
1 12544
Изобретение относится к вычислительной технике и может быть использовано для распределения общих ресурсов: секций памяти и шин с временным разделением между процессорами в муль- типроцессорных системах.
Цель изобретения — увеличение производительности мультипроцессорной системы при поступлении запросов общих ресурсов. 10
На фиг. 1 показана структурная схема арбитра; на фиг. 2 — граф микропрограммы функционирования арбитра; на фиг. 3 — функциональная схема микропрограммного автомата; на фиг. 4 функциональная схема дешифратора признаков; на фиг, 5 — функциональная схема коммутатора адресов; на фиг.6 вариант ностроения первого блока стековой памяти; на фиг.7 — вариант по- 20 строения второго блока стековой памяти", на фиг. 8 — вариант построения третьего блока стековой памяти; на фиг. 9 — вариант построения блоков стековой памяти первой группы; на 2 фиг. 10 — вариант построения блоков стековой памяти второй группы; на фиг. 11 — вариант построения блока памяти состояния; на фиг. 12 — вариант построения счетчика; на фиг.13 —, вариант построения регистра.
Арбитр содержит (фиг.1) микропрограммный автомат 1 (блок управления), первый и второй блоки 2 и 3 стековой памяти, блок 4 памяти состояния, третий блок 5 стековой памяти, счетчик 6, коммутатор 7 адресов, регистр 8, блоки 9Π— 10 стековой памяти первой и второй группы, разделенные íà группы 9„ — 9 я < и 10 — 10 . Выходы автомата 1 соединены с входами блоков 2 и 3 стековой памяти, блока.4 памяти состояния, блока 5 стековой памяти, коммутатора 7, регистра 8 и блоков 9 и 10 стековой памяти первой и второй групп. Входы автомата 1 сое- динены с выходами блоков 2 и 3, блока 4 памяти состояния, блока 5 и блоков 9 и 10 стековой памяти первой и второй групп. Выходы коммутатора 7 подключены к входам блока 4 памяти, блоков 9 стековой памяти первой группы, регистра 8, выходам блока 5 памя" ти, блоков 9 стековой памяти первой группы, входам блоков 10 стековой памяти второй группы и счетчика 6. Вхо- S5 ды коммутатора 7 соединены с выходамн блока 4 памяти, блока 2, входом и выходом блока 5, выходами счетчика 6
94 3 и блока 3, один из выходов которого подключен к входам блоков 9 стековой памяти первой группы. Выход регистра 8 соединен с выходом арбитра, входы которого подключены к входам блоков 2 и 3 памяти.
Блок 1 (микропрограммный автомат) представляет собой управляющий автомат Мура, предназначенный для реализации микропрограммы работы арбитра (фиг. 2). Автомат 1 (фиг. 3) содержит дешифратор 11 признаков, элементы И 12-39, элементы ИЛИ 40-47, генератор 48 синхронизирующих импульсов, триггеры 49 — 52. Дешифратор 11 признаков (фиг. 4) содержит элементы И 53 — 64 н элементы ИЛИ 65-68.
Коммутатор 7 адресов (фиг. 5) содержит элементы И 69-72, элементы ИЛИ 7374, элементы И 75< -83 „. Блок 2 (фиг.6) содержит стековую память 84, блок 85 анализа приоритетов, регистр 86 и элементы ИЛИ 87-88. Блок 3 (фиг ° 7) содержит стековую память 89, блок 90 анализа приоритетов, регистр 91 и элемент ИЛИ 92. Блок 5 (фиг. 8) содержит стековую память 93, регистр 94 и элемент ИЛИ 95. Каждый иэ блоков 9 (фиг. 9) содержит стековую память 96, регистр 97 и элемент ИЛИ 98. Каждый из блоков 10 (фиг. 10) содержит стековую память 99, регистр 100 и элемент ИЛИ 101. Блок 4 памяти состояния (фиг. 11) содержит память 102 с произвольной выборкой, регистр 103 и элемент ИЛИ 104. Счетчик 6 (фиг.12) содержит суммирующий счетчик 105, дифференцирующую цепочку 106 и дйод 107. Регистр 8 (фиг. 13} содержит регистр 108, элемент ИЛИ 109 и элементы И 110< — 110„.
Блок 2 используется для записи и хранения информации об освобождении общих ресурсов. Информация С, об освобождении общих ресурсов i-м процессором представляет собой адреса освободившихся j-x секций памяти Ас„ сп и m-й шины А, которые использовались процессором. Блок 3 предназначен для записи и хранения запросов общих ресурсов. Запрос 3; процессора i представляет собой адреса запрашиваемой секции памяти А и запрашивающего процессора Ая.. Блок 4 памяти состояния (блок памяти с произвольной выборкой) предназначен для хранения состояния арбитра. Под состоянием арбитра понимается совокупность адресов шин, назначенных арбит1254494 ром секциям памяти. Адрес j-й ячейки. блока 4 памяти представляет собой адрес соответствующей секции памяти
Асп Информация, записанная в j -ую ячейку блока 4, представляет собой адрес шины, назначенной арбитром соответствующей секции памяти. Например, если во вторую ячейку блока 4 записан адрес нулевой шины (шины tO с адресом, равным "нулю"), в третью ячейку — адрес второй шины, в седьмую ячейку — адрес первой шины, то это означает, что второй секции памяти (секции с адресом, равным двум ) арбитром назначена нулевая шина, третьей секции памяти - вторая шина и седьмой секции памяти — первая шина, а вся совокупность адресов нулевой, первой и второй шин представляет сос- уО тояние арбитра.
Блок 5 используется для хранения адресов свободных шин (не назначенных секциям памяти). Счетчик 6 пред- 2 назначен для выдачи очередного адреса занятой шины в случае прихода запроса, когда нет свободной шины, а запрашиваемая секция памяти свободна.
Коммутатор 7 предназначен для связи элементов арбитра. Регистр 8 используется для записи и выдачи информации, разрешающей запрашивающему процессору использование требуемых общих ресурсов. Данная информация представляет собой адреса запрашиваемой секции памяти A ä, запрашивающего процессд, сора А . и шины А,„, назначенной
I ГН этой секции памяти.
Блоки 9 стековой памяти используются для организации очередей запро40 сов процессора к требуемым шинам. Так в блок 9 записываются запросы процессоров, поставленные арбитром в очередь к нулевой шине и т.д., в (W+3)-й . блок 9 — запросы, поставленные в оче-4 редь к (W-1)-й шине. Блоки 10 стековой памяти с номерами с 0+4 по W+Z+3 (10Π— 10z, ) предназначены для хранения признаков о наличии запросов к секциям памяти, к которым уже имеются обращения процессоров. Признак о наличги запроса к требуемой секции памяти представляет собой адрес этой секции. Например, если запрос приходит к нулевой секции памяти, к ко- Ы торой уже имеется обращение какогото процессора, то в блок 10О записывается адрес этой секции. Таким образом, в блок 10 записываются признаки наличия запросов нулевой секции памяти и т.д., в блок 10 признаки для (Z — 1)-й секции памяти.
Арбитр может работать при условии: только одна шина должна быть назначена группе процессоров, требующих доступа к одной и гой же секции памяти; только одна шина должна быть назначена каждому процессору. Порядок обслуживания запросов общих ресурсов—
"первый пришел — первый обслужен".
Арбитр работает следующим образом.
В начальном состоянии он ожидает поступления информации об освобождении общих ресурсов в блок 2 или запроса общих ресурсов в блок 3 (фиг.1).
При этом автомат 1 находится в состоянии а, и нс выдает никаких управляющих сигналов (фиг. 2). Если в арбитр поступил запрос общих ресурсов, то сигнал Х с выхода блока 3 (указателя ст ка 3) подается в автомат 1, который переходит в состояние а, вырабатывая сигнал считывания Y т.е. запроса из блока 3. После выполнения арбитром этой микрокоманды, автомат 1 переходит в состояние а, формируя сигнал считывания Y информации иэ блока 4 памяти состояния. На другой вход этого блока с выхода блока 3 через коммутатор 7 (при наличии íà его входе сигнала Y ) подается адрес запрашиваемой секции памяти. Если в результате считывания на вход автомата 1 поступает сигнал Х с выхода блока 4, означающий, что к запрашиваемой секции памяти уже есть обращение одного или нескольких процессом.. ров, то автомат 1 переходит в состояние а . При этом им выдаются следующие сигналы: Y — запись запроса в один из блоков 9 — 9 ; Y — запись признака о налички запроса
B O5HH кз 6JIOKOB 10 10,, У считывание информации из блока 2.
При выполнении микрооперации У запрос 3 подается непосредственно с выхода блока 3 на входы блоков 9О
9щ к записывается в тот из них, адрес которого поступает с выхода блока 4 через коммутатор 7 (при наличии на его входе сигнала Y ) на вхо3 ды этих блоков стеконой па взяти. При выполнении микрооперации У4 адрес запрашиваемой секции памяти, к которой уже имеется обращение, подается с выхода блока 3 через коммутатор 7 (при
5 12544 наличии на его входе сигнала У ) на входы блоков 10 — 10, и записывается в соответствующий блок.
При реализации микрооперации Y„ соответствующий управляющий сигнал поступает на вход блока 2. Если с выходов блоков 4 и 5 (указателя стека 5) соответственно. не поступают сигналы Х и Х4 на вход автомата 1, т.е. запрашйваемая секция памяти свободна и все шины заняты, то автомат 1 осуществляет переход в состояние а формируя следующие сигналы: Y> — запись запроса в один из блоков 9; Yzзались в блок 4 адреса шины, назначенной запрашиваемой секции памяти;
У вЂ” считывание информации иэ блока 2.
При выполнении микрооперации Уэ за.прос 3; подается с выхода блока 3 на входы блоков 9 и записывается в тот из них, адрес которого поступает с выхода счетчика 6 через коммутатор 7 (при наличии на его входах сигналов
У ) на другие входы этих блоков.
При реализации микрооперации У> адрес шины, назначенной арбитром запрашиваемой секции памяти, подается с выхода счетчика 6 через коммутатор 7 на вход блока 4 и записывается в ту его ячейку, адрес которой поступает с соответствующего выхода блока 3 через коммутатор 7 на вход бло" ка 4. При этом на входы коммутатора 7 подаются сигналы У, Y . После выполнения микрокоманды У, У», У> содержи35 мое счетчика 6 увеличивается на "еди-, ницу". При отсутствии сигнала Х с выхода блока 4 и поступлении сигнала Х с выхода блока 5 на вход автомата 1, т.е. когда запрашиваемая секция памяти свободна и имеется свободная шина, автомат 1 переходит в состояние аб, вырабатывая сигнал Y< .
При выполнении микрокоманды У
45 происходит считывание адреса свободной шины из блока 5 и запись в регистр 8 считываемого адреса, поступающего с выхода блока 5 на вход регистра 8, и запроса 3;, поступающего с выхода блока 3 через коммутатор 7 (при наличии на его входе сигнала Y4 ) на вход регистра 8. После выполнения арбитром микрокоманды У автомат 1 переходит. в состояние а, выдавая следующий набор сигналов: Yg — передача ин55 формации с регистра 8, разрешающей занятие требуемых общих ресурсов запрашивающему процессору; У>
94 Ь запись в блок 4 памяти состояния адреса шины, назначенной запрашиваемой секции памяти; У " считывание информации из блока 2.
При выполнении микрооперации Y управляющий сигнал У посупает на вход регистра 8, разрешая передачу иэ него информации: А „ °, А и. и А„ на коммутатор общих ресурсов
+ III с процессорами. И результате i-й процессор погучает доступ к 1-й секции памяти через m-ную шину. При выполнении микрооперации,У адрес шины Aö, назначенной арбитром запрашиваемой J é секции памяти, подается с выхода блока 5 через коммутатор 7 на вход. блока 4 и записывается в ту его ячейку, адрес которой поступает с выхода блока 3 (А „ ) через комму-. сп1 татор 7 на вход блока 4. При этом на входы коммутатора 7 подаются сигналы Y,,Y,,Y . Если в результате
Выполнения иикрокоманды У У Уэ или Y Y Y или Y Y Y соот ветственно с выходов блоков 2 и 3 не поступают сигналы Х > и Х на вход автомата 1 (что означает отсутствие информации об освобождении общих ресурсов и запросов процессоров), то арбитр заканчивает выполнение микропрограммы и переходит в начальное состояние (автомат t — в состояние а ).
Если с выхода блока 2 сигнал Х не выдается, а с выхода блока 3 сигнал Х поступает на вход автомата 1, то автомат 1 переходит в состояние а, формируя сигнал считывания Y иэ блока 3. В случае же поступления сигнала Х с выхода блока 2 на вход автомата 1, он переходит в состояние а, выдавая управляющий сигнал Y .
При выполнении микрокоманды У происходит считывание информации иэ одного из блоков 9, адрес которого определяет освободившуюся шину и поступает с второго выхода блока 2 через коммутатор 7 на входы блоков 9; запись в регистр 8 считываемой информации, подаваемой на вход регистра 8, и адреса освободившейся секции памяти, поступающего с выхода блока 2 через коммутатор 7 на вход регистра 8. Одновременно с этим осуществляется считывание информации иэ одного из блоков 10, адрес которого представляет собой адрес освободившейся секции памяти и.подается с выхода
7 1254 блока 2 через коммутатор 7 на входы этих блоков. l
При выполнении микрокоманды У>
1. на вход коммутатора 7 подается сиги нал У . Если в результате реализации з этой микрокоманды на вход автомата 1 сигнал К о наличии запроса к освободившейся шине не поступит с первого выхода одного из блоков 9, то автомат 1 переходит в состояние а, формируя следующие сигналы: Ущ — запись адреса освободившейся шины в блок 5;
Y — запись "нуля" в блок 4, 7 ри выполнении микрооперации У« осуществляется запись адреса освободившейся шины, поступающего непосредственно с выхода блока 2 на вход блока 5.
При выполнении микрооперации Ут происходит запись "нуля" в ту ячейку блока 4, адрес которой поступает с выхода блока 2 через коммутатор 7 (при наличии на его входе сигнала У, )на вход блока 4. Если после выполнения микрокоманды Ую, У на вход автомата 1 поступает сигнал Х, с выхода блока 2, то автомат 1 переходит в состояние а, вырабатывая сигнал считывания информации У из блока 2.
Если же сигнал Х, =О, то арбитром выполняются все действия, аналогичные тем, что и в случае, когда арбитр завершил выполнение одной иэ микрокоманд У, У4, У, или У, Yz, У или У, У, У и на входе автомата отсутствует сигнал Х>, Если после выполнения микрокоманды Y на вход автомата 1 с выхода одного иэ блоков 9 и выхода одного из блоков 10 соответственно поступят 4 2 сигналы Х6 и Хт о наличии запросов к.освободившейся шине и секции памяти, то автомат 1 переходит в состояние а„, выдавая сигнал У1 для передачи информации А „., Ая., Аы из ре45. гистра 8 на вход коммутатора общих ресурсов с процессорами. Нри поступлении на вход автомата 2 сигналов Х 1 и Х =О, то он переходит в состоя-. ние а, формируя сигналы: Y>. - передача йнформации из регистра 8 о разрешении занятия требуемых общих ресурсов запрашивающим процессором; У запись "нуля" в блок 4.
При выполнении микрооперации У происходит запись "нуля" в ту ячейку блока 4, адрес которой поступает с выхода блока 2 через коммутатор 7
494 8 (при наличии на его входах сигналов Y, Y ) на вход блока 4.
После выполнения микрокоманды У или У, У арбитр выполняет все те же действия, что и после реализации микрокоманды Ую, Yz. Если автомат находится в состоянии а< и поступил сигнал Х,, соответствующий освобождению общих ресурсов с выхода блока 2, то автомат 1 переходит в состояние а, выдавая сигнал считывания информации У из блока 2. Далее работа арбитра циклически повторяется.
Формула изобретения
Арбитр мультипроцессорной системы, содержащий блок памяти состояния и микропрограммный автомат, о т л и ч а ю шийся тем, что, с целью увеличения производительности при поступлении запросов общих ресурсов, он содержит счетчик, коммутатор адpecos, регистр, три блока стековой памяти и две группы блоков стековой памяти, при этом информационные входы коммутатора адресов с первого по седьмой соединены соответственно с информационным выходом блока памя" ти состояния, первым и вторым информационными выходами первого блока стековой памяти, первым и вторым ин" формационными выходами второго блока стековой памяти, первым информационным выходом третьего блока стековой памяти и выходом счетчика, входы микропрограммного автомата с первого по седьмой подключены соответственно к выходу указателя первого блока стековой памяти, выходу признака второго блока стековой памяти, выходу признака блока памяти состояния, выходу при= знака третьего блока стексвой памяти, выходу признака первого блока стековой памяти, выходам признака блоков стековой памяти первой группы и выходам признака блоков стековой памяти второй группы, выход микропрограммного автомата с первого по десятый соединены соответственно с синхровходом второго блока стековой памяти и управляющими входами коммутатора адресов с первого по девятый, адресные входы первого и второго блоков стековой памяти. подключены к адресному входу арбитра, синхровход первого блока стековой памяти соединен с пятым Выходом микропрограммного автомата, первый и второй информационные
9 1 входы, первый, второй и третий синхровходы и выход регистра подключены соответственно к второму информационному выходу третьего блока стековой памяти, информационным выходам блоков стековой памяти первой группы шестому, восьмому и девятому выходам микропрограммного автомата и выходу арбитра, информационные выходы коммутатора адресов с первого по пятый соединены соответственно с первшм и вторым адресными входами блока памяти состояния, входом счетчика, вторым информационным входом регистра и адресными входами блоков стековой памяти второй группы, кроме того второй информационный выход коммутатора адресов подключен к второму информационному выходу третьего блока стековой памяти и первым адресным входам блоков стековой памяти первой ( группы, вторые адресные входы вхоЭ
254494 10 ,ды разрешения обращения и синхровходы которых соединены соответственно с первым информа ионным выходом второго блока стековой памяти, третьим и девятым выходами микропрограммного автомата; синхровход и вход разрешения обращения. блока памяти состояния подключены соответственно к второму и седьмому выходам микропрограм1р много автомата, адресный вход, синхровход и вход разрешения обращения третьего блока стековой памятч соединены соответственно с вторым информационным выходом первого блока стековой памяти, шестым и десятым выходами микропрограммного автомата, а .входы разрешения обращения и синхровходы блоков стековой памяти второй группы подключены соответственно к четвертому и девятому выходом микропрограмного автомата, чарфюма7 t9v+3P и (и 4-> у у,р щр cmcw (иггЗ)-и слмл
1254494
1254494
1254494 сз ю
5 лгал
C3 4tu
С,Р леп
Сугазажюм сщсжа бжрк ланит а 7
- kg
Ч
4фр
С угазалаю стра
СФ х ф r
Om процеС С
4 Г Б лц ла1 а,gn -gwлад лФй лф-Гф.g лф мзда а7
Я
1254494 шт " .У, +%8
Фее.У хэ
Ace $$ силъ с7 с7
Agyp A c 44 сс щюйРс юочфве
4@v.tt
Составитель Г.Виталиев
Техред И.Попович Корректор И.Самборская
Редактор И. Касарда
Тираж 67) Подписное
ВНИИПИ Государственного комитета СССР по делам изобретений и открытий
333035, Иосква, Ж-35, Раушская наб., д. 4/5
Заказ 4722/53
Производственно-полиграфическое предприятие, г,ужгород, ул.Проектная, 4
