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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (51)5 G 06 F 9/46

ГОСУДАРСТВЕННЫИ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4684071/24-24 (22) 25.04.89 (46) 23,12.90. Бюл, ¹ 47 (72) Г.С.Колесник и М.Г.Колесник (53) 681.325(088.8) (56). Авторское свидетельство СССР

¹966697,,кл,,6 06 F9/46,,1981.

Авторское свидетельство СССР № 1183967, кл. G 06 F 9/46, 1984. (54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ

ЗАДАНИЙ ПРОЦЕССОРАМ (57) Изобретение относится к вычислительной технике и может быть использовано при организации вычислительного процесса по обработке задач.. в многопроцессорных

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

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

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

Устройство содержит группу 1 регистров, первую 2, третью 3, вторую 4 и четвертую 5 группы элементов И, первую 6, вторую

7 и третью 8 группы элементов ИЛИ, пятую группу 9 элементов И, четвертую группу 10 элементов ИЛИ, седьмую группу 11 элементов И, первую 12, третью 13 и вторую 14 группы триггеров, восьмую, девятую, одиннадцатую, шестую и десятую группы 15-19 элементов И, пятую 20 и шестую 21 группы элементов ИЛИ, первый 22 и второй 23 элементы НЕ, первый 24 и второй 25 элементы

ИЛИ-НЕ, с первого 26 по четвертый 29 эле, Ж,, 1615721 А1 (многомашинных) вычислительных системах. Цель изобретения состоит в повышении достоверности функционирования.

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

34 элементы задержки.

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

"О" сбрасываются в "1" (во всех разрядах).

Работа устройства начинается после задания режима и занесения весов задач в регистры группы 1; тогда знаки ("1" или

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

: 9 и ИЛИ-НЕ 24.

На выходах элементов ИЛИ групп 6 и 7 могут быть различные комбинации нулей и единиц, Вначале рассмотрим случай, когда на выходе какого-то одного элемента ИЛИ 6, например ИЛИ бь — единичный потенци ал. Тогда на выходах элементов ИЛИ-НЕ 24 и ИЛИ группы 8 — потенциал "О", кроме элемента ИЛИ 8ь единичный потенциал с, выхода которого поступает на второй вход . элемента И 9 и первый вход элемента И 11ь, поскольку на первом входе элемента И 9i—

; потенциал "О", то на выходах всех элемен. тов И группы 9 — потенциал "0", на выходе элемента ИЛИ-НŠ— потенциал "1"; который через элемент ИЛИ 10 проходит на второй вход элемента И 11ь Тем самым только на . выходе элемента И 11 появляется единич, ный потенциал, Рассуждая аналогично, по,лучаем, чта если единичный сигнал появля ется только на выходе одного элемента ИЛИ группы 7, например ИЛИ 7ь а на выходах остальных элементов ИЛИ групп 6 и 7— нули, то единичный сигнал появляется только на выходе одного элемента И 11ь

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

ИЛИ 27, работает таким образом, что потенциал "1" появляется только в том случае, когда число единиц на выходах элементов И группы 11 равно или больше двух, в противном случае (все нули или одна единица на выходах элементов И группы 11) на выходе элемента ИЛИ 27 — нулевой сигнал. При наличии потенциала "1" только на выходе

Элемента И 11 на выходе элемента ИЛИ 27—

" 0", на выходе элемента НЕ 23- "1", поэтому

Элементы И 15 открыты, и триггер 12 перебрасывается в единичное состояние. Единичный импульс с его выхода через элемент

ИЛИ 20(поступает на выход устройства как сигнал на выбор задания с номером один, а также, поступив на установочный вход регистра 1ь сбрасывает его в заданное (режимом

5 работы устройства) состояние ("0" или "1" во . всех разрядах), Через элемент ИЛИ 29 единичный потенциал с выхода триггера 12 проходит на второй вход элемента И вЂ” НЕ 32, на первый вход которого поступает "1" с

10 инверсного выхода переполнения счетчика

31; Появляющийся на выходе элемента ИН.Е 32 нулевой потенциал закрывает все элементы И групп 2 — 5 на время, когда после подачи сигнала на вход запуска генератор

15 30 осуществляет выдачу импульсов, счет которых ведет счетчик 31, а информация в регистрах группы 1 при поступлении каждого импульса на тактовый вход смещается на два разряда вправо и одновременно пере20 записывается, Когда счетчик 31 переполняется, сигнал с прямого выхода переполнения останавливает генератор 30, устанавливает счетчик 31 в исходное состояние, а также через элемент задержки сбра25 сывает в "О" триггеры 12. Начинается новый цикл устройства по выбору очередной задачи путем сравнения содержимого очередных разрядов весов задач, записанных в регистр группы 1 и поступа;ощих с соответ30 ству ащих выходов последнего и предпоследнего разрядов, кроме содержимого заблокированного (в данном случае — регистра 1 ) регистра группы 1. Конечно, при одной "1" в самом начале работы устройства

35 перезапись информации в регистры группы

1 путем запуска генератора 30 можно было и .e,ã=:.,àòü. Hî удобно это делать потому, чга такой вариант появления сигналов на выходах элементов И группы 11 может пра40 изойти в процессе работы устройства, и тогда такой режим перезаписи с блокировкой на это время элементов И групп 2 — 5 необходим, Для унификации работы устройства и сделала перезапись информации в начале

45 работы устройства при одной единице на

".üè0äýõ элементов И группы 11.

Если с выходов регистров группы 1 по:.:тупают од и .- ули, го на выходах всех элементов И группы 11 — нули, на выходах

50 элементов ИЛИ группы 20 — нули, и после подачи сигнала на вход запуска генератор

30 начинает выдачу импульсов, первый из которых, поступив на тактовые входы регистров группы 1, сдвигает записанные в них

55 коды на два разряда вправо(а два старших разряда перезаписываются в два первых разряда). Пусть теперь на выходах нескольких элементов ИЛИ группы 6, например

ИЛИ 61 и 61;потенциал "1", на выходе элементов ИЛИ 7i — г|отенциал "1", на выходах

1615721 остальных элементов ИЛИ группы 7 — "О", Тогда на выходе элемента ИЛИ-НЕ 24 — "О", на выходах элементов ИЛИ 8i и 8> — 1", на выходе элемента И 9i — "1", на выходах остальных элементов И группы 9 — "О"., на выходе элемента ИЛИ-НE 25 — "О", на выходе элемента И 11,— "1", на выходах остальных элементов И группы 11 — "О". Далее аналогично рассмотренному на выходе элемента

ИЛИ 20 появится импульс как сигнал на выбор задачи с номером один. Аналогично устройство работает и в случае, когда "1" присутствует на выходах элементов ИЛИ группы 7, но только на выходе какого-то одного элемента ИЛИ группы 6 присутствует "1".

Теперь рассмотрим случай, когда одинаковые коды снимаются с двух или более регистров группы 1. Пусть, например, "1" присутствует на выходах элементов ИЛИ 6 и бь а с выходов элементов ИЛИ 7i и 7 также поступает потенциал "1", Тогда на выходе элемента ИЛИ-НЕ 24 — "О", на выходах элементов ИЛИ 8 и 8> — "1", на обоих входах и выходах элементов И 9 и 9; — "1", на выходах элементов И 11 и 111 — "1", на выходах остальных элементов И группы 11 — "О", Аналогично и при "О" на обоих выходах элементов ИЛИ 7 и 7 только на выходах элементов И 11 и 11 — "1". С выходов элементов И 11 и 11> единичные сигналы поступают на входы элементов И 15, 15 и

16ь 161 и на функциональный узел из групп элементов И 19, ИЛИ 21 и ИЛИ 27, на выходе которого появляется "1", открывающая элементы И 16; и 16), поэтому триггеры 13 и

131 перебрасываются в единичное состояние. Появляющийся на выходе элемента

ИЛИ 28 единичный потенциал открывает элементы И группы 17, и тогда единичные сигналы с инверсных выходов остальных триггеров группы 13 проходят на единичные входы одноименных триггеров группы 14 и перебрасывают их в единичное состояние; нулевые потенциалы с их инверсных выхо-, дов закрывают соответствующие элементы

И групп 2 — 5 и блокируют выдачу информации из регистров группы 1 до конца данного цикла работы устройства по выбору очередной задачи, Сигналом с выхода элемента 33 задержки триггеры группы 13 возвращаются в нулевое состояние. Далее при выдаче генератором 30 следующего импульса и обусловленного этим сдвига записанной в регистрах группы 1 информации на два разряда вправо производится сравнение кодов выдаваемой регистрами группы 1 информации, но уже информация заблокированных регистров группы 1 в сравнении не участвует.

По мере работы устройства наступит момент, когда будет найден максимальный код, и импульс будет выдан с выхода соответствующего элемента ИЛИ группы 20. Однако возможен и случай, когда в двух или более регистрах группы 1 записаны максимальные веса, например в регистрах 1i и 11.

Тогда к моменту переполнения счетчика 31 лишь триггеры 14; и 141 останутся в состоянии "О", и потому лишь с их инверсных выходов единичные импульсы через элементы

И 18 и 18 и элементы ИЛИ 20 и 20) пройдут на соответствующие выходы устройства, когда сигнал переполнения с выхода счетчика 31 поступит на вторые входы элементов

И группы 18. Порядок выполнения задач не имеет знач ния — можно вначале выполнить первую, а можно и вторую.

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

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

ИЛИ первой и второй групп, выходы элементов ИЛИ первой группы соединены с первыми входами одноименных элементов

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

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

1615721. первыми входами одноименных элементов

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

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

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

1 ервой по четвертую группы, прямой выход

Переполнения счетчика соединен с входом рстанова генератора импульсов, установочНым входом счетчика и через первый элеМент задержки с нулевыми входами григгеров второй группы, инверсные выхо ды которых подключены к четвертым вхо. дам одноименнных элементов И с первой по четвертую группы и к вторым входам одноименных элементов И шестой группы, выход каждого регистра группы соединен с его йнформационным входом, первые и вторые 1ходы элементов И седьмой группы подключены к выходам одноименных элементов

ИЛИ соответственно третьей и четвертой групп, третьи входы элементов И седьмой группы объединены и соединены с выходом первого элемента ИЛИ, входы которого подключены к выходам элементов ИЛИ первой и второй групп, выходы элементов И седьмой группы подключены к первым входам одноименных элементов И восьмой, девятой и десятой групп, вторые входы элементов И десятой группы соединены с выходами одноименных элементов ИЛИ шестой группы, первый вход 1-го элемента И десятой группы (1=1, и, где n — число задач в пакете) соединен с входами j-x элементов

ИЛИ шестой группы ()=1,ï,1 |), выходы элементов И десятой группы подключены к входам второго элемента ИЛИ, выход которого соединен с входом второго элемента НЕ и вторыми входами элементов И девятой группы, выход второго элемента НЕ подключен к вторым входам элементов И восьмой группы, выходы которых соединены с единичными входами одноименных триггеров первой группы, выходы элементов ИЛИ пятой группы подключены к установочным входам одноименных регистров группы и являются выходами устройства, выходы элементов И девятой группы подключены к единичным входам одноименных триггеров третьей группы, прямые выходы которых соединены с входами третьего элемента ИЛИ, выход которого подключен к первым входам элементов И одиннадцатой группы и через второй элемент задержки к нулевым входам триггеров третьей группы, инверсные выходы которых соединены с вторыми входами одноименных элементов И одиннадцатой группы, выходы которых подключены к единичным входам одноименных триггеров второй группы, выходы элементов И шестой группы соединены с вторыми входами одноименных элементов ИЛИ пятой группы, инверсные выходы триггеров первой группы соединены с входами четвертого элемента

ИЛИ, выход которого соединен с вторым входом элемента И-НЕ, 1815721

Составитель Г.Пономарева

Редактор 0,Юрковецкая Техред M.Ìîðãåíòàë Корректор В.Гирняк

Заказ 3988 Тираж 570 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

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

Производственно-издательский комбинат "Патент", г, Ужгород, ул.Гагарина, 101