Арбитр мультипроцессорной системы Советский патент 1986 года по МПК G06F13/00 

ч1254494

Изобретение относится к вычислительной технике и может быть использовано для распределения общих ресурсов: секций памяти и шин с временным разделением между профессорами в муль-5 типроцессорных системах.

Цель изобретения - увеличение производительности мультипроцессорной системы при поступлении запросов общих ресурсов.10

На фиг. 1 показана структурная схема арбитра; на фиг, 2 - граф микропрограммы функционирования арбитра; на фиг. 3 - функциональная схема микропрограммного автомата; на фиг. 4 - |5 функциональная схема дешифратора признаков; на фиг. 5 - функциональная схема коммутатора адресов; на фиг.6 - вариант построения первого блока сте- ковой памяти; на фиг.7 - вариант по- 20 строения второго блока стековой памяти; на фиг. 8 - вариант- построения третьего блока стековой памяти; на фиг. 9 - вариант построения блоков стековой памяти первой группы; на 25 фиг. 10 - вариант построения блоков- стековой памяти второй группы; на фиг. 11 - вариант построения блока г амяттл состояния; на фиг. 12 - вариант построения счетчика; на фиг.13 -, Q вариант построения регистра. .

Арбитр содержит (фиг.1) микропрограммный автомат 1 (блок управления), пе)вый и второй блоки 2 и 3 с тековой памяти, блок 4 памяти состояния, тре2

и блока 3, один из выходов которого подключен к входам блоков 9 стековой памяти первой группы. Выход регистра 8 соединен с выходом арбитра, вхо ды которого подключены к входам бло ков 2 и 3 памяти.

Блок 1 (микропрограммный автомат представляет собой управляющий авто мат Мура, пред||азначенный для реали зации микропрограммы работы арбитра (фиг. 2). Автомат 1 (фиг. 3) содержит дешифратор 11 признаков, элемен ты И 12-39, элементы ИЛИ 40-47, ген ратор 48 синхронизирующих импульсов триггеры 49 - 52. Дешифратор 11 при знаков (фиг. 4) содержит элементы И 53- 64 и элементы ИЛИ 65-68. Ком1-1утатор 7 адресов (фиг. 5) содер жит элементы И 69-72, элементы ИЛИ 7 74, элементы И 75,-83. Блок 2 (фиг. содержит стековую память 84, блок 8 анализа приоритетов, регистр 86 и элементы ИЛИ 87-88. Блок 3 (фиг.7) содержит стековую память 89, блок 9 анализа приоритетов, регистр 91 и элемент ИЛИ 92. Блок 5 (фиг. 8) сод жит стековую память 93, регистр 94 и элемент ИЛИ 95. Каждый из блоков (фиг. 9) содержит стековую память 9 регистр 97 и элемент ИЛИ 98. Каждый из блоков 10 (фиг. 10) содержит сте вую память 99, регистр 100 и элемент ИЛИ 101. Блок 4 памяти состоян (фиг. 11) содержит память 102 с про извольной выборкой, регистр 103 и

тий блок 5 стековой памяти, счетчик 6, элемент ИЛИ 104. Счетчик 6 (фиг.12)

коммутатор ки 9. - 10 и второй группы

7 адресов, регистр 8, бло- 2, стековой памяти первой

разделенные на группы

9 -

W-4

И

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. Входы коммутатора 7 соединены с выходами блока 4 памяти, блока 2, входом и выходом блока 5, выходами счетчика 6

2

и блока 3, один из выходов которого подключен к входам блоков 9 стековой памяти первой группы. Выход регистра 8 соединен с выходом арбитра, входы которого подключены к входам блоков 2 и 3 памяти.

Блок 1 (микропрограммный автомат) представляет собой управляющий автомат Мура, пред||азначенный для реализации микропрограммы работы арбитра (фиг. 2). Автомат 1 (фиг. 3) содержит дешифратор 11 признаков, элементы И 12-39, элементы ИЛИ 40-47, генератор 48 синхронизирующих импульсов, триггеры 49 - 52. Дешифратор 11 признаков (фиг. 4) содержит элементы И 53- 64 и элементы ИЛИ 65-68. Ком1-1утатор 7 адресов (фиг. 5) содержит элементы И 69-72, элементы ИЛИ 73- 74, элементы И 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,- 11 OR.

Блок 2 используется для записи и хранения информации об освобождении общих ресурсов. Информация С; об освобождении общих ресурсов i-м процессором представляет собой адреса освободившихся J-X секций памяти и т-й шины A|j, которые использовались процессором. Блок 3 предназначен для записи и хранения запросов общих ресурсов. Запрос 3; процессора 1 представляет собой адреса запрашиваемой секции памяти А,; и запрашивающего процессора . Блок 4 памяти состояния (блок памяти с произ- вольной выборкой) предназначен для хранения состояния арбитра. Под состоянием арбитра понимается совокупность адресов шин, назначенных арбитром секциям памяти. Адрес j-й ячейки блока 4 памяти представляет собой адрес соответствующей секции памяти

АСП

Информация, записанная в j-ую 5 ячейку блока 4, представляет собой адрес шины, назначенной арбитром соответствующей секции памяти. Например, если во вторую ячейку блока 4 записан адрес нулевой шины (шины ю с адресом, равным нулю), в третью ячейку - адрес второй шины, в седьмую ячейку - адрес первой шины, то это означает, что второй секции памяти (секции с адресом, равным двум) 13 арбитром назначена нулевая шина, третьей секции памяти - вторая шина и седьмой-секции памяти - первая шина, а вся совокупность адресов нулевой.

разом, в блок lOg записываются признаки наличия запросов нулевой сек- ции памяти и т.д., в блок 10, - признаки для (Z - 1)-й секции памяти Арбитр может работать при условии: только одна шина должна быть назначе на группе процессоров, требующих доступа к одной и гой же секции памя ти; только одна шина должна быть назначена каждому процессору. Порядок обслуживания запросов общих ресурсов первый пришел - первый обслужен.

Арбитр работает следующим образом

В начальном состоянии он ожидает поступления информации об освобождении общих ресурсов в блок 2 или запроса общих ресурсов в блок 3 (фиг.1) При этом автомат 1 находится в состоянии а. и НС выдает никаких управпервой и второй шин представляет сое-2о ляющих сигналов (фиг. 2). Если в артояние арбитра.

Блок 5 используется для хранения адресов свободных шин (не назначенных секциям памяти). Счетчик 6 пред- 25 назначен для выдачи очередного адреса занятой гаины в случае прихода запроса, когда нет свободной шины, а запрашиваемая секция памяти свободна. Коммутатор 7 предназначен для связи элементов арбитра. Регистр 8 используется для записи и выдачи информации, разрешающей запрашивающему процессору использование требуемых общих ресурсов. Данная информация представляет собой адреса запрашиваемой секции

30

35

памяти А

CPJ

запрашивающего процеси шины Л,

назначенной

40

сора п- t lunnoi этой секции памяти.

Блоки 9 стековой памяти используются для организации очередей запросов процессора к требуемым шинам. Так в блок 9о записываются запросы процессоров, поставленные арбитром в очередь к нулевой шине и т.д., в (и+3)-й блок 9 - запросы, поставленные в оче- редь к (и-1)-й шине. Блоки 10 стековой памяти с номерами с W+4 по W+Z+3 (Юр - lOj., ) предназначены для хранения признаков о наличии запросов к секциям памяти, к которым уже имеются обращения процессоров. Признак о наличги запроса к требуемой секции памяти представляет сабой адрес этой секции. Например, если запрос приодит к нулевой секции памяти, к ко- 55 торой уже имеется обращение какого- то процессора, то в блок Юо записывается адрес этой секции. Таким об50

разом, в блок lOg записываются признаки наличия запросов нулевой сек- ции памяти и т.д., в блок 10, - признаки для (Z - 1)-й секции памяти. Арбитр может работать при условии: только одна шина должна быть назначена группе процессоров, требующих доступа к одной и гой же секции памяти; только одна шина должна быть назначена каждому процессору. Порядок обслуживания запросов общих ресурсов - первый пришел - первый обслужен.

Арбитр работает следующим образом.

В начальном состоянии он ожидает поступления информации об освобождении общих ресурсов в блок 2 или запроса общих ресурсов в блок 3 (фиг.1) При этом автомат 1 находится в состоянии а. и НС выдает никаких управ25

30

5

0

5

битр поступил запрос общих ресурсов, то сигнал Xj с выхода блока 3 (указателя 3) подается в автомат 1, который переходит в состояние а, вырабатывая сигнал считывания Y , т.е. запроса из блока 3. После выполнения арбитром этой микрокоманды, автомат 1 переходит в состояние а, формируя сигнал считывания Y информации из блока 4 памяти состояния. На другой вход этого блока с выхода блока 3 через коммутатор 7 (при наличии на его входе сигнала Y,j ) подается адрес запрашиваемой секции памяти. Если в результате считывания на вход автомата 1 поступает сигнал Х с выхода блока 4, означаюоций, что к запраши Баемой секции памяти уже есть обращение одного или нескольких процессоров, то автомат 1 переходит в состояние а. При этом им выдаются следующие сигналы: Y, - запись запроса в один из блоков 9р - 9vv., ; Y - пись признака о наличии запроса

за

в один из блоков

10„ 10

Г-1

YC 9

считывание информации из блока 2.

При выполнении микрооперации Y запрос 3 подается непосредственно с выхода блока 3 на входы блоков 9о

w-

и записывается в тот из них,

адрес которого поступает с выхода блока 4 через коммутатор 7 (при наличии на его входе сигнала Y) на входы этих блоков стекоьой памяти. При выполнении микрооперации Y адрес запрашиваемой секции памяти, к которой уже имеется обращение, подается с выхода блока 3 через коммутатор 7 (при

наличии на его входы блоков

5

входе

сигнала Y. ) на

12

Юс 10

н -1

и записывается в соответствующий блок.

При реализации микрооперации Yg соответствующий управляющий сигнал поступает на вход блока 2. Если с выходов блоков 4 и 5 (указателя стека 5) соответственно не поступают сигналы X. и Х на вход автомата 1, т.е. запрашиваемая секция памяти свободна и все шины заняты, то автомат 1 осуществляет переход в состояние а,, формируя следукяцие сигналы: Y - запись запроса в один из блоков 9; Y - запись в блок 4 адреса шины, назначенной запрашиваемой секции памяти; считывание информации из блока 2

YS При выполнении микрооперации Yg за- .прос 3 подается с вьпсода блока 3 на входы блоков 9 и записывается в тот из них, адрес которого поступает с выхода счетчика 6 через коммутатор 7 (при наличии на его входах сигналов э 1) на другие входы этих блоков.

При реализации микрооперации Yy адрес шины, назначенной арбитром запрашиваемой секции памяти, подается с выхода счетчика 6 через коммутатор 7 на вход блока 4 и записывается в ту его ячейку, адрес которой поступает с соответствующего выхода блока 3 через коммутатор 7 на вход бло- . При этом на входы коммутатора 7

подаются сигналы Y, Y нения микрокоманды Y , Y , Yj мое счетчика 6 увеличивается на

После выпол- содержи- еди-

40

ницу . При отсутствии сигнала Х, с выхода блока 4 и поступлении сигнала Х4 с выхода блока 5 на вход автомата t, т.е. когда запрашиваемая секция памяти свободна и имеется свободная шина, автомат 1 переходит в состояние а, вырабатывая сигнал Y.

При выполнении микрокоманды Y происходит считьшание адреса свободной шины, из блока 5 и запись в регистр 8 считываемого адреса, поступающего с выхода блока 5 на вход регистра 8, и запроса 3;, поступающег хода блока 3 через коммутатор 7

45

с вы- (при 50

наличии на его входе сигнала

Y«)

на

При выполнении микрокоманды Y происходит считывание информации из одного из блоков 9, адрес которого определяет освободившуюся шину и поступает с второго выхода блока 2 через коммутатор 7 на входы блоков 9; запись в регистр 8 считываемой информации, подаваемой йа вход регистра 8, и адреса освободившейся секции памяти, поступакнцего с выхода блока 2

вход регистра 8. После выполнения арбитром микрокоманды Yj автомат 1 пере- через коммутатор 7 на вход регист- ходит в состояние а, выдавая следую- ра 8. Одновременно с этим осуществля- щий набор Yj - передача ин- ется считывание информации из одного формации с регистра 8, разрешагацей из блоков 10, адрес которого пред- занятие требуемых общих ресурсов запрашивающему процессору;

V

ставляет собой адрес освободившейся секции памяти и подается с выхода

запись в блок 4 памяти состояния адреса шины, назначенной запращиваемой секции памяти; Yj - считывание информации из блока 2.

При выполнении микрооперации Y- управляющий сигнал Yg посупает на - вход регистра 8, разрешая передачу

0

0

;

0

из него информации: А(. Af,; и Ац на коммутатор общих ресурсов с процессорами. В результате i-й процессор погучает доступ к j-й секции памяти через т-ную шину. При выполнении микро операции Y адрес шины Ац, назначенной арбитром запра- J шиваемой j-й секции памяти, подается с выхода блока 5 через коммутатор 7 на вход, блока 4 и записывается в ту его ячейку, адрес которой поступает с выхода блока 3 () через коммутатор 7 на вход блока 4. При этом на входы коммутатора 7 подаются сигналы Yg,Y, Yj. Если в результате выполнения микрокоманды Y, Yj. , Yj , или Y, Yj, Yj, или Y,, Y, Y соответственно с выходов блоков 2 и 3 не поступают сигналы X j и Xg на вход автомата 1 (что означает отсутствие информации об освобождении общих ресурсов и запросов процессоров), то арбитр заканчивает выполнение микропрограммы и переходит в начальное состояние (автомат 1 - в состояние а) .

Если с выхода блока 2 сигнал Xj. не выдается, а с выхода блока 3 сигнал Xj поступает на вход автомата 1, то автомат 1 переходит в состояние а,, формируя сигнал считывания Y, из бло3.

5

0

ка J. В случае же поступления сигнала Хс с выхода блока 2 на )зход автомата 1, он переходит в состояние а вьщавая управлякяций сигнал Y, .

При выполнении микрокоманды Y происходит считывание информации из одного из блоков 9, адрес которого определяет освободившуюся шину и поступает с второго выхода блока 2 через коммутатор 7 на входы блоков 9; запись в регистр 8 считываемой информации, подаваемой йа вход регистра 8, и адреса освободившейся секции памяти, поступакнцего с выхода блока 2

через коммутатор 7 на вход регист- ра 8. Одновременно с этим осуществля- ется считывание информации из одного из блоков 10, адрес которого пред-

через коммутатор 7 на вход регист- ра 8. Одновременно с этим осуществля ется считывание информации из одного из блоков 10, адрес которого пред-

ставляет собой адрес освободившейся секции памяти и подается с выхода

блока 2 через коммутатор 7 на входы этих блоков.

При выполнении микрокоманды Y ,н« вход коммутатора 7 подается сигнал Y,. Если в результате реализации этой микрокоманды на вход автомата 1 сигнал Х о наличии запроса к освободившейся шине не поступит с первого выхода одного из блоков 9, то автомат 1 переходит в состояние а,д , формируя следующие сигналы: ,„ - запись адреса освободившейся шины в блок 5; Y - запись нуля в блок 4.

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

При выполнении микрооперации Y происходит запись нуля в ту ячейку блока 4, адрес которой поступает с выхода блока 2 через коммутатор 7 (при наличии на его входе сигнала Yfp) на вход блока 4. Если после выполнения микрокоманды Y,o , Y на вход автомата 1 поступает сигнал X, с выхода блока 2, то автомат 1 переходит

в состояние а

в )

вырабатывая сигнал

считывания информации Yj из блока 2. Если же сигнал X,0, то арбитром выполняются все действия, аналогичные тем, что и в случае, когда арбитр завершил выполнение одной из микрокоманд Y, , Y4 , Yj , или Y, , Y, , ff

или Y

8

7

И на

входе автомата

1

отсутствует сигнал ХзЕсли после выполнения микрокоманды Y на вход автомата 1 с выхода одного иэ блоков 9 и одного из блоков 10 соответственно поступят сигналы Х- и Х о наличии запросов к освободившейся шине и секции памяти, то автомат 1 переходит в состояние а,, , выдавая сигнал Yj для передачи информации Agp. , Ад; , ре гистра 8 на вход коммутатора общих ресурсов с процессорами. При поступлнии на вход автомата 1 сигналов

.и X, 0, то он переходит в состояние а. , формируя сигналы:

YJ пере50

дача информации из регистра 8 о разрешении занятия требуемых общих ресурсов запрашивающим процессором; Yy запись нуля в блок 4.

55

При вьтолнении микрооперации Y7 происходит запись нуля в ту ячейку блока 4, адрес которой поступает с выхода блока 2 через коммутатор 7

544948

(при наличии на его входах сигналов Yg, Yy) на вход блока 4.

После выполнения микрокоманды Y

г

или Yg, Yj арбитр выполняет все те же 5 действия, что и -после реализации микрокоманды Y(o , Y7. Если автомат 1 находится в состоянии а, и поступил сигнал X,, соответствующий освобождению общих ресурсов с выхода бло- 10 ка 2, то автомат 1 переходит в состояние ag, выдавая сигнал считывания информации Yj из блока 2. Далее работа арбитра циклически повторяется.

-

)

15

20

25

30

35

50

55

Формула изобретения

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

входы, первый, второй и третий син- хровходы и выход регистра подключены соответственно к второму информационному выходу третьего блока стековой памяти, информационным выходам блоков стековой памяти первой группы, шестому, восьмому и девятому выходам микропрограммного автомата и выходу арбитра, информационные выходы коммутатора адресов с первого по пятый соединены соответственно с первЫм и вторым адресными входами блока памяти состояния, входом счетчика, вторым информационным входом регистра и адресными входами блоков стековой памяти второй группы, кроме того, второй информационный выход коммутатора адресов подключен к второму информационному выходу третьего блока стековой памяти и первым адресным входам блоков стековой памяти первой группы, вторые адресные входы, вхо12

етЛв/тма стоя Уу Уу стек

1254494

10

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

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

()-u {v()-e} сте i cfne/f

Of

Cfj

У маЗ

-. a , i( 47

s

2

3

,

т

- Ha7 ffffSfy

Us

56

Q4

57

« 5

66

i/s

56

as

,,

ff .r

V 7

67

Lf4t

S

5

-

6О

7

S

5/

62

6S

6

09

аю

О //

г

./

6,7

с -52

Фиг. 4

.d

С y arjcvne/7f с/тге а

CmeiroSaffi /геемлть

f7f /7/ fff J7i От л/уоцеес.

Фиг.б

У5

C/TfSA-ofaur

C,yfa3a/r &f7jf с/7ге зa ajre/за /T/K/oflcf/ffe/T ffc

х

Фиг. 7

Изобретение относится к вычислительной технике и может быть использовано для распределения общих ресурсов: секций памяти и шин с временным разделением между процессорами в мультипроцессорных системах. Целью изобретения является увеличение производительности мультипроцессорной системы при поступлении запросов общих ресурсов. С этой целью в арбитр мультипроцессорной системы, содержащий блок памяти состояния и микропрограммный автомат, введены счетчик, коммутатор адресов, регистр, три блока стековой памяти и две группы блоков стековой памяти. 13 ил. (Л С