Устройство для распределения заданий процессорам Советский патент 1990 года по МПК G06F9/50 

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

Цель изобретения состоит в повышении достоверности функционирования.

На чертеже изображена функциональная схема устройства.

Устройство содержит группу 1 регистров, первую 2, третью 3, вторую 4 и четвертую 5 группы элементов И, первую 6, вторую 7 и третью 8 группы элементов ИЛИ, пятую группу 9 элементов И, четвертую группу. ТО элементов ИЛИ, седьмую группу 11 элементов И, первую 12, третью 13 и вторую 14 группы триггеров, восьмую, девятую, одиннадцатую, шестую и десятую группы 15-19 элементов И, пятую 20 и шестую 21 группы элементов ИЛИ, первый 22 и второй 23 элементы НЕ, первый 24 и второй 25 элементы ИЛ И-НЕ, с первого 26 по четвертый 29 элементы ИЛИ, генератор ЗО импульсов, счетчик 31, элемент И-НЕ 32, второй 33 и первый 34 элементы задержки.

В исходном статическом состоянии обнулены триггеры групп 12-14, в счетчик 31 занесено число Е-С-1,где Е - емкбсть счетчика: m - разрядность кодов, которыми выражаются веса задач, причем при нечетном m число С округляется до ближайшего большего целого числа. Регистры группы 1 являются регистрами сдвига на два разряда в сторону старших разря- , дов при поступлении каждого импульса на тактовый вход. Информация с их выходов переписывается снова в регистры, а съем информации производится с прямых и инверсных выходов двух старших (последнего и предпоследнего) разрядов. Единичный потенциал подается на вход элемента НЕ 22 для задания режима минимального времени реализации пакета

дач, нулевой потенциал -для задания режима минимального среднего времени ожидания задачи в пакете; это соответствует режимам распределения задач по процессорам вычислительной системы по критерию минимума (максимума) веса задач в пакете. Если на вход элемента НЕ 22 подан потенциал 1, то при подаче сигнала на установочные входы регистры группы 1 сбрасываются а О, при подаче потенциала О сбрасываются в 1 (во всех разрядах).

Работа устройства начинается после задания режима и занесения весов задач в регистры группы 1; тогда знаки (1 или О), записанные в двух последних разрядах регистров группы 1, с прямых и инверсных выходов этих разрядов выступают через открытые элементы И групп 2 (3) и 4 (5)и элементы ИЛИ групп 6и 7 на соответ- 1 ствующие входы элементов ИЛИ групп 8 и

I 9 и ИЛИ-НЕ 24.

На выходах элементов ИЛИ групп 6 и 7 могут быть различные комбинации нулей и единиц. Вначале рассмотрим случай, когда на выходе какого-то одного элемента ИЛИ I 6, например ИЛИ 6i, - единичный потенци- I ал. Тогда на выходах элементов ИЛИ-НЕ 24 I и ИЛИ ГРУППЫ 8 - потенциал О, кроме элемента ИЛИ 8i, единичный потенциал с выхода которого поступает на второй вход элемента И 9i и первый вход элемента t1 11,, поскольку на первом входе элемента И 9| -- потенциал О, то на выходах всех элементов И группы 9 - потенциал О, на выходе элемента ИЛИ-НЕ-потенциал 1, который через элемент ИЛИ 10; проходит на второй вход элемента И 11|. Тем самым только на выходе элемента И 111 появляется единичный потенциал. Рассуждая аналогично, по- лучаем, что если единичный сигнал появля- |ется только на выходе одного элемента ИЛИ труппы 7, например ИЛИ 7i, а на выходах остальных элементов ИЛИ групп 6 и 7 - :нули, то единичный сигнал появляется только на выходе одного элемента И 11j.

Функциональный узел, состоящий из элементов ИЛИ группы 21, И группы 19 и

И 27, работает таким образом, что потенциал 1 появляется только в том случае, когда число единиц на выходах элементов И группы 11 равно или больше двух, в противном случае (все нули или одна единица на выходах элементов И группы 11) на выходе элемента ИЛИ 27 - нулевой сигнал При наличии потенциала 1 только на выходе элемента И 111 на выходе элемента ИЛИ 27- 0, на выходе элемента НЕ 23 - 1, поэтому . Элементы И 15i открыты, и триггер 12| пере- (5расывается в единичное состояние. Единичный импульс с его выхода через элемент

о

ИЛИ 20| поступает на выход устройства как сигнал на выбор задания с номером один, а также, поступив на установочный вход регистра 1|, сбрасывает его в заданное (режимом 5 работы устройства) состояние (О или 1 во всех разрядах). Через элемент ИЛИ 29 единичный потенциа л с выхода триггера 12i проходит на второ й вход элемента И-НЕ 32, на первый вход которого поступает 1 с 10 инверсного выхода переполнения счетчика 31, Появляющийся на выходе элемента И- КЕ 32 нулевой потенциал закрывает все элементы И групп 2-5 на время, когда после подачи сигнала на вход запуска генератор 15 30 осуществляет выдачу импульсов, счет которых ведет счетчик 31, а информация в регистрах группы 1 при поступлении каждого импульса на тактовый вход смещается на два разряда вправо и одновременно пере- М записывается. Когда счетчик 31 переполняется, сигнал с прямого выхода переполнения останавливает генератор 30, устанавливает счетчик 31 в исходное состояние, а также через элемент задержки сбра- 25 сывает в О триггеры 12. Начинается новый цикл устройства по выбору очередной задачи путем сравнения содержимого очередных разрядов весов задач, записанных в регистр группы 1 и поступающих с соответ- 30 ствующих выходов последнего и предпоследнего разрядов, кроме содержимого заблокированного (в данном случае - регистра 10 регистра группы 1. Конечно, при ОДНОЙ 1 в самом начале работы устройства J5 перезапись информации в регистры группы i путем запуска генератора 30 можно было и не дзлать, но удобно это делать потому, что такой вариант появления сигналов на выходах элементов И группы 11 может про- 40 изойти в процессе работы устройства, и тогда такой режим перезаписи с блокировкой на это время элементов И 2-5 необходим. Для унификации работы устройства и сделала перезапись информации в начале 5 работы устройства при одной единице на выходах элементов И группы 11.

Если с выходов регистров группы 1 поступают одни нули, го на выходах всех эле- ментов И группы 11 - нули, на выходах 0 элементов ИЛИ группы 20 - нули, и после подачи сигнала на вход запуска генератор 30 начинает выдачу импульсов, первый из которых, поступив на тактовые входы реги- строе группы 1, сдвигсет записанные в них 5 коды на два разряда вправо (а два старших разряда перезаписываются в два первых разряда). Пусть теперь на выходах нескольких элементов ИЛИ группы 6, например ИЛИ б| и 6,-потенциал 1, на выходе эл°- 7| - потенциал 1, на выхода х

остальных элементов ИЛИ группы 7 - О. Тогда на выходе элемента ИЛИ-НЕ 24 - О, на выходах элементов ИЛИ 8i и 8j , на выходе элемента И 9i - 1, на выходах остальных элементов И группы 9 - О, на выходе элемента ИЛИ-НЕ 25 - О, на выходе элемента И 111,- 1, на выходах остальных элементов И группы 11 - О. Далее аналогично рассмотренному на выходе элемента ИЛИ 20i появится импульс как сигнал на выбор задачи с номером один. Аналогично устройство работает и в случае, когда 1 присутствует на выходах элементов ИЛИ группы 7, но только на выходе какого-то одного элемента ИЛИ группы 6 присутствует 1,

Теперь рассмотрим случай, когда одинаковые коды снимаются с двух или более регистров группы 1. Пусть, например, 1 присутствует на выходах элементов ИЛИ 6j и 6i, а с выходов элементов ИЛИ 1 и 1 также поступает потенциал 1. Тогда на выходе элемента ИЛИ-НЕ 24 - О, на выходах элементов ИЛИ 8i и 8j - 1, на обоих входах и выходах элементов И , на выходах элементов И 11i и 11j - 1, на выходах остальных элементов И группы 11 - О. Аналогично и при О на обоих выходах элементов ИЛИ 7| и 7j только на выходах элементов И 111 и 11j - 1. С выходов элементов И Hi.и 11/ единичные сигналы поступают на входы элементов И 15i, 15j и 16i, 16j и на функциональный узел из групп элементов И 19, ИЛИ 21 и ИЛИ 27, на выходе которого появляется 1, открывающая элементы И 16i и 16j, поэтому триггеры 13i и 13j перебрасываются в единичное состояние. Появляющийся на выходе элемента ИЛИ 28 единичный потенциал открывает элементы И группы 17, и тогда единичные сигналы с инверсных выходов остальных триггеров группы 13 проходят на единичные входы одноименных триггеров группы 14 и перебрасывают их в единичное состояние; нулевые потенциалы с их инверсных выхо-, дов закрывают соответствующие элементы И групп 2-5 и блокируют выдачу информации из регистров группы 1 до конца данного цикла работы устройства по выбору очередной задачи. Сигналом с выхода элемента 33 задержки триггеры группы 13 возвращаются в нулевое состояние. Далее при выдаче генератором 30 следующего импульса и обусловленного этим сдвига записанной в регистрах группы 1 информации на два разряда вправо производится сравнение кодов выдаваемой регистрами группы 1 информации, но уже информация заблокированных регистров группы 1 в сравнении не участвует.

По мере работы устройства наступит момент, когда будет найден максимальный код, и импульс будет выдан с выхода соответствующего элемента ИЛИ группы 20. Однако возможен и случай, когда в двух или более регистрах группы 1 записаны максимальные веса, например в регистрах 1i и 1j. Тогда к моменту переполнения счетчика 31 лишь триггеры 14i и 14 останутся в состоя0 НИИ О, и потому лишь с их инверсных выходов единичные импульсы через элементы И 181И 18j и элементы ИЛИ 20i и 20j пройдут на соответствующие выходы устройства, когда сигнал переполнения с выхода счетчи5 ка 31 поступит на вторые входы элементов И группы 18. Порядок выполнения задач не имеет значения - можно вначале выполнить первую, а можно и вторую.

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

5 осуществлении зависимого процесса сравнения кодов, записанных в регистрах группы 1, путем блокировки тех из них, в которых оказываются записанные меньшие (большие) коды, а также путем устранения неверных

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

Формула изобретения Устройство для распределения заданий

5 процессорам, содержащее группу регистров, шесть групп элементов И, пять групп элементов ИЛИ, два элемента ИЛИ-НЕ, первый элемент задержки, первую группу триггеров, счетчик и генератор импульсов,

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

5 элементов И первой и третьей, второй и четвертой групп подключены соответственно к входам соответствующих элементов ИЛИ первой и второй групп, выходы элементов ИЛИ первой группы соединены с

0 первыми входами одноименных элементов ИЛИ третьей группы и соответствующими входами первого элемента ИЛИ-НЕ, выход которого подключен к вторым входам элементов ИЛИ третьей группы, выходы эле5 ментов ИЛИ второй группы соединены с первыми входами одноименных элементов И пятой группы, к вторым входам которых подключены выходы соответствующих элементов ИЛИ третьей группы, выходы элементов И пятой группы соединены с

первыми входами одноименных элементов ИЛИ четвертой группы и входами второго элемента ИЛИ-НЕ, выход которого подключен к вторым входам элементов ИЛ И четвертой группы, инверсные выходы триггеров первой группы соединены с первыми входами одноименных элементов ИЛИ пятой группы, выход первого элемента задержки соединен с инверсными входами триггеров первой группы, вход первого элемента задержки соединен с первыми входами элементов И шестой группы, отличающееся тем, что, с целью повышения достоверности функционирования, в него дополнительно введены шестая группа элементов ИЛИ, вторая и третья группы триггеров, второй элемент задержки, с седьмой по одиннадцатую группы элементов И, элемент |И-НЕ, четыре элемента ИЛИ и два элемента |НЕ, выход первого из которых соединен с I вторыми входами элементов И первой и вто- |рой групп, а вход соединен с вторыми входами элементов И третьей и четвертой групп и является входом задания режима |работы устройства, пусковым входом уст- ройства является вход запуска генератора |импульсов, выход которого подключен к так- товым входам регистров группы и входу счи- тывания счетчика, инверсный в ыход переполнения которого соединен с первым уходом элемента И-НЕ, выход которого под- kлючeн к третьим входам элементов И с Первой по четвертую группы, прямой выход Переполнения счетчика соединен с входом Останова генератора импульсов, установочным входом счетчика и через первый эле- Мент задержки с нулевыми входами tpиггepoв второй группы, инверсные выхо- Йы которых подключены к четвертым вхо- Дам одноименнных элементов И с первой по четвертую группы и к вторым входам одноименных элементов И шестой группы, выход каждого регистра группы соединен с его ||1нформационным входом, первые и вторые Входы элементов И седьмой группы подключены к выходам одноименных элементов

ИЛИ соответственно третьей и четвертой групп, третьи входы элементов И седьмой группы объединены и соединены с выходом первого элемента ИЛИ, входы которого под- 5 ключены к выходам элементов ИЛИ первой и второй групп, выходы элементов И седьмой группы подключены к первым входам одноименных элементов И восьмой, девя- той и десятой групп, вторые входы элемен- 10 тов И десятой группы соединены с выходами одноименных элементов ИЛИ Шестой группы, пеевь1й вход 1-го элемента И десятой группы (1-1, п, где п - число задач в пакете) соединен с входами j-x элементов 15 ИЛИ шестой группы (,n,), выходы элементов И десятой группы подключены к входам второго элемента ИЛИ, выход которого соединен с входом второго элемента НЕ и вторыми входами элементов И девятой 20 группы, выход второго элемента НЕ подключен к вторым входам элементов И вось- . мой группы, выходы которых соединены с единичными входами одноименных триггеров первой группы, выходы элементов ИЛИ 25 пятой группы подключены к установочным входам одноименных регистров группы и являются выходами устройства, выходы элементов И девятой группы подключены к единичным входам одноименных триггеров 30 третьей группы, прямые выходы которых соединены с входами третьего элемента ИЛИ, выход которого подключен к первым входам элементов И одиннадцатой группы и через второй элемент задержки к нулевым входам 5 триггеров третьей группы, инверсные выходы которых соединены с вторыми входами одноименных элементов И одиннадцатой группы, выходы которых подключены к единичным входам одноименных триггеров 0 второй группы, выходы элементов И шестой группы соединены с вторыми входами одноименных элементов ИЛИ пятой группы, инверсные выходы триггеров первойг группы соединены с входами четвертого элемента 5 ИЛИ, выход которого соединен с вторым входом элемента И-НЕ,

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