Мультипроцессорная система Советский патент 1980 года по МПК G06F15/167 

1

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

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

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

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

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

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

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

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

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

25 и второй групп подключены ко входам устройства памяти через устройство сопряжения, а информационные входы к выходу устройства памяти, выход первого коммутатора -подключен ко

30 входу дешифратора, выход которого соединен с первыми входами регистров четвертой группы, вторые входы которых подключены к выходу второго коммутатора, первые выходы регистро чеТ|Вертой группы подключены ко вход устройства памяти через устройство сопряжения, а вторые выходы - к пер вым входам третьего коммутатора,вто рьое входы которого подключены к выходрм четвертого коммутатора, а ) - ко входам блока нормализация чисел, выход которого соединен с первым входом сумматора, второй вхо сукплатора подключен к выходу пятрго кокосу т атора, а выход к инфор мационному входу блока постоянной п мяти, выход которого соединен со процессоров, первый и второ вхо|9з1 пятого коммутатора подключены к первым выходам регистров третьей группы и выходам четвертого коммута Topii соответственно, вторые ВЫХОДЕ регистров третьей группы соеди ненм со входами устройства памяти черфз устройство сопряжения, а инфор мадцонные входы - с выходом устройства памяти, а первый и второй входы четвертого коммутатора подключены к выходу блока приоритетов вывода и первым выходам регистров второй гру пы ctooTBeTCTBeHHo. На чертеже приведена блок-схема устройства. Устройство содержит первую группу Iрегистров, первый коммутатор 2, дешифратор 3, блок 4 приоритетов вво да, второй коммутатор 5, вторую груп пу б регистров, третью группу 7 реги стров, третий коммутатор 8, блок 9 нормализации чисел, сумматор 10,бло IIп|остоянной памяти четвертую группу 12 регистров, четвертый коммутатор 13, блок 14 приоритетов вывода, пятцй коммутатор 15, блок 16 синхрон заци:и, процессоры 17 и 18, устройств 19 сопряжения, устройство 20 памяти Каждой подпрограмме задачи в соответствии с некоторым алгоритмом, обеспечивающим некоторое оптимальное решение задачи, присваивается порядковый номер. Решение подпрограмм задачи должно происходить в порядке возрастания их номеров. Но, так.как каждая задача может решаться различным числом процессоров, обеспечить одну и ту же последовательность решение подпрограмм без потерь произво дительности в общем случае нельзя. Динамическое перераспределение подПрограмм в управляющих системах приводит к большим потерям производительности вследствие высокой частот решения задач. поэтому в процессе решения задачи опре еляются номера подпрограмм, готорых для решения, и при освобожденир процессора на него должна пере дава1гься подпро5ра 1ма, имеющая среди roToiabix к выполнению наименьший номер. Определение подпрограммы, готовой для решения, осуществляется следующим образом. Все подпрограммы хранятся в устройстве 20 памяти. В каждой подпрограмме имеется команда Сч - считывание номера очередной разрешенной для выполнения подпрограммы, Рассмотрим функциональное назначение каждого из введенных устройств. Первая группа 1 регистров предназначена для запоминания номеров подпрограмм и осуществляет запоминание в двоичном коде номеров подпрограмм, готовых к выполнению. В первом регистре записываются номера подпрограмм первым процессором, во втором - вторьом процессором и т,д. Первый коммутатор 2 предназначен для коммутации регистров запоминания номеров подпрограмм и обеспечивает передачу содержимого одного из регистров 1 на дешифратор 3. Дешифратор 3 преобразует двоичный код в позиционный, -Блок 4 приоритетов ввода предназначен для обеспечения ввода номеров подпрограмм, готовых к выполнению, в порядке поступления заявок от процессоров на ввод, Второй коммутатор 5 обеспечивает ввод номеров подпрограмм с дешифратора 3 в четвертую группу 12 регистров - регистров запоминания номеров подпрограмм. Если номер подпрограммы вводит процессор, решающий j-ю задачу, то выходы дешифратора 3 подключаются к j-му регистру 12, Вторая группа б регистров производит распределение процессоров по задачам и обеспечивает привязку каждого процессора к решаемой задаче. В эти регистры записываются относительные номера задач, которые должны решаться каждым процессором, Номер задачи не должен превышать количество регистров. Например,первый и второй процессоры решают задачу № 1, третий, четвертый и пятый - задачу W 2, шестой - 3 и т,д. Четвертая группа 12 регистров осуществляет запоминание номеров подпрограмм в позиционном коде и предназначена для-запоминания в позиционном коде номеров подпрограмм, готовых к выполнению. В первом регистре записываются номера подпрограмм первой задачи, во втором - второй задачи и т.д. При готовности выполнения i-ой подпрограммы j-ой задачи в i-й разряд регистра j записывается 1, Третий коммутатор 8 осуществляет коммутации регистров запоминания номеров подпрограмм в позиционном коде и обеспечивает передачу содержимого одного из регистров 12 в блок 9 нормализации чисел в соответствии с номером решаемой задачи Если за начальным адресом подпрограммы обращается процессор, решающий j-ю задачу, то через коммутатор 8 будет передано содержимое j-ro ре гистра 12. Блок 9 нормализации чисел служит для определения порядка числа, кото рый равен минимальному номеру подпрограммы j-ой задачи, готовой к выполнению. Сумматор 10 предназначен для вычисления адреса, по которому в блоке 11 постоянной памяти хранится начальный адрес подпрограм мы. Блок 11 постоянной памяти предназначен для хранения начальных адр сов подпрограмм решаемых задач. Начальные адреса подпрограмм для каждой задачи группируются в массивы. Например, начальные адреса подпрограмм первой задачи хранятся в ячейках блока постоянной памяти с адресами 1-1,, второй задачи - i/+l-io Птi И Т. д. Третья группа 7 регистров предназначена для хранения смещения начальных сщресов задач и обеспечивает хранение смещения начальных адресов подпрограь«ч для каждой задачи. В эти регистры записываются смещения начальных адресов подпрограмм задач, которые должны решаться и записываться в регистры распределения процессоров по задачам6, При этом в первый регистр записывается смещение для первой задачи, во второй - для второй задачи и т.д. Пятый коммутатор 15 предназначен для коммутации регистров смещения начальных адресов задач и обеспечивает передачу содержимого одного из регистров 7, определяемого номером решаемой задачи, в сумматор 10. Если же начальным адресом подпрогр 1ммы обращается i-й процессор, решающий j-ю. задачу, то через ко 1мутатор 15 в сумматор 10 будет передано содержимое j-ro регистра 7. Блок 14 приоритетов вывода предназначен для обеспечения вывода начальных адресов подпрограмм в поряд ке обращения процессоров. Четвертый коммутатор 13 вывода п программ обеспечивает подключение к коммутаторам 8 и 15 соответствующих регистров 7 и 12. Если начальный адрес подпрограммы выводит процессо решающий j-ю задачу, то коммутатор 13 вывода подключает к коммутаторам 8 и 15 соответственно j-e регистры 12 и 7. Блок 16 синхронизации осуществля ет синхронизацию приема информации из устройства 20 памяти в регистры 1 запоминания номеров подпрограмм, в регистры б распределения процессоров по задачам, в регистры 7 смещения начальных адресов задач, работы блока 11 постоянной памяти работы блоков. 4 приоритета ввода и вывода 14. В целом работа системы происходит следующим образом. Перед началом работы в регистры 6 распределения процессоров по задачам записываются относительные номера задач, которые должны решать каждый процессор, а в регистры 7 смещения начальных адресов задач соответствующие этим задачам смещения. При выполнении команды Сч j-м процессором, решающим j-ю задачу, в блоке 16 синхронизации от этого процессора поступает сигнал ввода информации, а на i-й регистр 1 запоминания номера подпрограмма сама информация, представляющая собой номер 6 очередной разрешенной для выполнения подпрограммы. По сигналу ввода в блок 4 приоритетов ввода из блока 16 синхронизации ставится заявка от обратившегося процессора. Если окажется, что заявка от i-ro процессора в блоке приоритетов ввода 4 единственная, то информация из i-ro регистра 1 запоминания номеров подпрограмм через коммутатор регистров 2 запоминания номеров подпрограмм поступит на дешифратор 3, где преобразуется в позиционный код и запишется в 6-й разряд j-ro регистра 12 запоминания.номера подпрограммы в позиционном коде. После этого заявка в блоке 4 приоритетов ввода от i-ro процессора через блок 16 синхронизации стирается. Если же окажется, что в блоке 4 приоритетов ввода имеются еще не обслуженные заявки от других процессоров, то заявка от 1-го процессора станет в очередь и будет обслужена после выполнения ранее поступивших заявок. При завершении раиения подпрограммы j-ой задачи i-м процессором от него в блок 16 синхронизации поступит сигнал вывода информации (начального адреса подпрограммы). По этому сигналу блок 16 синхронизации ставит заявку в блок 14 приоритетов вывода. Если эта заявка единственная, то коммутатор 13 вывода подпрограмм разрешит передачу: содержимого регистра 12 запоминания подпрограмм в позиционном коде в блок 9 нормализации чисел;содержимого j-ro регистра 7 смещения начальных адресов згшач в сумматор 10.

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

Порядок числа из блока 9 поступает на сумматор 10 и суммируется со смещением, поступившим из j-ro регистра 7 смещения начальных адресов задач.

На выходе сумматора образуется адрес, по которому из блока 11 постоянной памяти в обратившийся процефсор считывается начальный адрес поДпрогрс1ммы,

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

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

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

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

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

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

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

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

1.Мультипроцессорные системы и Параллельные вычисления. Под ред. Ф.Г. Энслоу, с. 34, рис. 1.11,1976.

2.Авторское свидетельство СССР 301705, кл. G 06 F 15/16, 1969 (прототип).