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

 

Союз Советских

Социалистических

Республик

ОПИСАНИЕ

ИЗОВРКтКНИЯ 74294З

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (б1) Дополнительное к авт. свид-ву (22) Заявлено 240378 т21) 2593797/18 — 24 (51)М. КЛ.

G 06 F 15/16 с присоединением заявки Йо (23) Приоритет

Государственный комитет

СССР по делам изобретений и открытий

Опубликовано 2506.80. Бюллетень М 23

Дата опубликования описания 2506.80 (53) УДК 681.14 (088. 8) (72) Автор изобретения

t0.Л. Усов (71) Заявитель (54) МУЛЬТИПРОЦЕССОРНАЯ СИСТЕМА

Изобретение относится к области вычислительной техники и предназначено для использования в управляющих комплексах. 5

Известна мультипроцессорная система, содержащая процессоры, устройство памяти и устройство сопряжения (1) .

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

ro обеспечения системы.

Наиболее близким, по существу технического решения является мультипроцессорная система, содержащая 20 процессоры, соединенные двухсторонними связями через устройство сопряжения с устройством памяти (2).

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

Цель изобретения — повышение производительности системы.

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

742943

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

Все подпрограммы хранятся н устройстве 20 памяти. В каждой подпрограмме имеется команда Сч — считынание номера очередной разрешенной для выполнения подпрограммы.

Рассмотрим функциональное назначение каждого из введенных устройстн.

Первая группа 1 регистров предназначена для запоминания номеров подпрограмм и осуществляет запоминание в двоичном коде номеров подпрограмм, готовых к выполнению, В первом регистре записываются номера подпрограмм первым процессором, но втором — вторым процессором и т.д.

Первый коммутатор 2 предназначен для коммутации регистров запоминания номеров подпрограмм и обеспечивает передачу содержимого одного иэ регистров 1 на дешифратор 3. дешифратор 3 преобраэует двоичный код н позиционный.

Блок 4 приоритетов ввода преднаэ— начен для обеспечения ввода номеров подпрограмм, готовых к выполнению, н порядке поступления заявок от процессорон на ввод.

Второй коммутатор 8 обеспечивает ввод номеров подпрограмм с дешифратора 3 н четвертую группу 12 регистров — регистрон запоминания номеров подпрограмм. Если номер подпрограммы вводит процессор, решающий )-ю задачу, то выходы дешифратора 3 j-му регистру 12.

Вторая группа 6 регистров производит распределение процессоров по задачам и обеспечинает привязку каждого процессора к решаемой задаче.

B эти регистры записываются относительные номера задач, которые долж— ны решаться каждым процессором.

Номер задачи не должен превышать количество регистров. Например,перный и нторой процессоры решают задачу М 1, третий, четвертый и пятый — задачу 9 2, шестой — Р 3 и тфде

Четвертая группа 12 регистрон осуществляет запоминание номеров подпрограмм н позиционном коде и предназначена для-запоминания н позиционном коде номеров подпрограмм, готовых к ныпрЛнению, В первом регистре записываются номера подпрограмм первой задачи, но втором— второй задачи и т.д.

При готовности выполнения i-ой подпрограммы j-ой задачи н i-й разряд регистра j записывается 1, Третий коммутатор 8 осуществляет коммутации регистров запоминания номеров подпрограмм и позиционном коде и обеспечивает передачу собО со@динан с первыми входами регистров четвертой группы, вторые входы которьи подключены к выходу второго коммутатора, первые выходы регистров четвертой группы подключены ко входу устройства памяти через устройство сопряжения, а вторые выходы — к пер5 вым входам третьего коммутатора,вторые входы которого подключены к выходам четвертого коммутатора, а вйхОдн — ко входам блока нормализации:чисел, выход которого соединен с п рвьэа входом сумматора, второй вход сумматора подключен к выходу пятого коммутатора, а выход к информационному входу блока постоянной памяти, выход которого соединен со входами процессоров, первый и второй входы пятого коммутатора подключены к пЕрвым выходам регистров третьей группы и выходам четвертого коммутатора соответственно, вторые ны- 20 ходи регистров третьЕй группы соединены со входами устройства памяти через устройство сопряжения, а информационные входы — с выходом устройства памяти, а перный и второй входы четвертого коммутатора подключены к выходу блока приоритетов вывода и перэым выходам регистров второй группы соответственно.

На чертеже приведена блок-схема устройства. 30

Устройство содержит перную группу

1 регистров, первый коммутатор 2, дешнфратор 3, блок 4 приоритетов ввода, второй коммутатор 5, вторую группу 6 регистров, третью группу 7 реги- 35 стров, третий коммутатор 8, блок 9 норМализации чисел, сумматор 10,блок

11 Постоянной памяти четвертую группу 12 регистрон, четвертый коммутатор 13, блок 14 приоритетов вывода, пятЫй коммутатор 15, блок 16 синхронизации, процессоры 17 и 18, устройство

19 сопряжения, устройство 20 памяти, Каждой подпрограмме задачи н соответствии с некоторым алгоритмом, обеспечивающим некоторое оптимальное 45 решение задачи, присваивается порядковый номер. Решение подпрограмм задачи должно происходить н порядке возрастания их номеров. Но, так.как каждая задача может решаться раэлич- 50 ным числом процессоров, обеспечить одну и ту же последовательность решения подпрограмм беэ потерь производительности в общем случае нельзя.

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

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

742943 держимого одного иэ регистров 12 в блок 9 нормализации чисел в соответствии с номером решаемой задачи.

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

8 будет передано содержимое j-го регистра 12.

Блок 9 нормализации чисел служит для определения порядка числа, который равен минимальному номеру подпрограммы j--ой задачи, готовой к выполнению. Сумматор 10 предназначен для вычисления адреса, по которому в блоке 11 постоянной памяти хранится начальный адрес подпрограммы °

Блок 11 постоянной памяти пред I0 !

5 назначен для хранения начальных адресов подпрограмм решаемых задач. Начальные адреса подпрограмм для каждой задачи группируются в массивы.

Например, начальные адреса подпрограмм первой задачи хранятся в ячейках блока постоянной памяти с адресами 1-i второй задачи — 1 +1 †к Z и т.д.

Третья группа 7 регистров предназначена для хранения смещения начальных адресов задач и обеспечивает хранение смещения начальных адресов подпрограмм для каждой задачи. В эти регистры записываются смещения начальных адресов подпрограмм задач, которые должны решаться и записываться в регистры распределения процессоров по задачам6. При этом в первый регистр записывается смещение для первой задачи, во второй — для второй задачи и т,д.

Пятый коммутатор 15 предназначен для коммутации регистров смещения начальных адресов задач и обеспечивает передачу содержимого одного иэ регистров 7, определяемого номером решаемой задачи, в сумматор 10. Если же начальным адресом подпрограммы обращается i-й процессор, решающий j-ю. задачу, то через коммутатор 15 в сумматор 10 будет передано содержимое j-го регистра 7.

25

35

50

Блок 14 приоритетов вывода предназначен для обеспечения вывода начальных адресов подпрограмм в порядке обращения процессоров. 55

Четвертый коммутатор 13 вывода подпрограмм обеспечивает подключение к коммутаторам 8 и 15 соответствующих регистров 7 и 12. Если начальный адрес подпрограммы выводит процессор, решающий j-ю задачу, то коммутатор

13 вывода подключает к коммутаторам

8 и 15 соответственно j-e регистры

12 и 7.

Блок 16 синхронизации осуществляет синхронизацию приема информации 45 из устройства 20 памяти в регистры 1 запоминания номеров подпрограмм, в регистры 6 распределения процессоров по задачам, в регистры 7 смещения начальных адресов задач, работы блока 11 постоянной памяти работы блоков.

4 приоритета ввода и вывода 14.

В целом работа системы происходит следующим образом.

Перед началом работы в регистры

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

При выполнении команды Сч j-м процессором, решающим j-ю задачу, в блоке 16 синхронизации от этого процессора поступает сигнал ввода информации, а на 1-A регистр 1 запоминания номера подпрограммы сама информация, представляющая собой номер 8 очередной разрешенной для выполнения подпрограммы.

По сигналу ввода в блок 4 приоритетов ввода из блока 16 синхронизации ставится заявка от обратившегося процессора.

Если окажется, что заявка от i-го процессора в блоке приоритетов ввода

4 единственная, то информация иэ

i-ro регистра 1 запоминания номеров подпрограмм через коммутатор регистров 2 запоминания номеров подпрограмм поступит на дешифратор 3, где преобразуется в позиционный код и запишется в 6-й разряд j-го регистра 12 запоминания, номера подпрограммы в позиционном коде. После этого заявка в блоке 4 приоритетов ввода от i-го процессора через блок

16 синхронизации стирается.

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

При завершении решения подпрограммы j-ой задачи 1-м процессором от него в блок 16 синхронизации поступит сигнал вывода информации (начального адреса подпрограммы) °

По этому сигналу блок 16 синхронизации ставит заявку в блок 14 приоритетов вывода. Если эта заявка единственная, то коммутатор 13 вы-. вода подпрограмм разрешит передачу: содержимого j-ro регистра 12 запоминания подпрограмм в позиционном коде в блок 9 нормализации чиселу содержимого j-го регистра 7 смещения начальных адресов задач в сумматор 10.

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

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

1. Мультипроцессорные системы и параллельные вычисления. Под ред.

Ф.Г. Энслоу, с. 34, рис. 1,11,1976, 2. Авторское свидетельство СССР

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

В блоке 9 нормализации чисел находится порядок нормализации числа, который равен минимальному номеру подпрограммы, готовой к исполнению, Порядок числа из блока 9 поступаЕт на сумматор 10 и суммируется со смещением, поступившим из j-го регистра 7 смещения начальных адресов задач, На выходе сумматора образуется адрес, по которому из блока 11 постоянной памяти в обратившийся процессор считывается начальный адрес поДпрограммы.

Если же окажется, что в блоке

14 приоритетов вывода имеются еще на обслуживании заявки от других процессоров, то заявка ат i-ro процеСсора станет в очередь и будет обслужена после выполнения ранее поступивших заявок.

Для обеспечения воэможности запоминания состояния устройства распределения ресурсов при прерываниях регистры 1 запоминания номеров подпрбграммы, регистры 6 распределения прОцессоров по задачам, регистры 12 эайоминания номеров подпрограмм н позиционном коде, регистры 7 смещения начальных адресов задач через устройство 19 сопряжения соединены с устройством 20 памяти.

Предлагаемое устройство позволяет производить одновременное решениЕ от одной до N независимых задач íà N процессорах. При этом процессоры жестко не привязаны к решаемым задачам. В процессе решения задач количество процессоров, отВодимых для решения той или иной задачи может изменяться, что важно, найример, при появлении отказов в процессорах, при поступлении на решеиие задачи, имеющей более высокий приоритет и т.д.

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

20

35

50

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

Мультипроцессорная система, содержащая процессоры, соединенные двухсторонними связями через устройство сопряжения с устройством памяти, отличающаяся тем, что, с 60 целью повышения производительности

742943

Составитель Т. Арешеев

Техред И.Асталош Корректор В. Синицкая

Редактор П. Макаревич

3619/15

Заказ! !!

t ! ! ! !

l ! !

I !

1

t

Тираж 751 Подписное

ЦНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Филиал ППП Патент, г. ужгород, ул. Проектная,4

1

1 !

1

1, 1

l ! !

l !

I !

l