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

(51)5 6 06 Р 9/4 ОСУДАРСТВЕННЫИ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯПРИ ГКНТ СССР ОПИСАНИЕ ИЗОБРЕТЕНИЯ АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(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 элементь 1 задержки.В исходном статическом состоянии обнулены триггеры групп 12 - 14, в счетчик 31 занесено число Е - С - 1,где Е - емкость счетП 1чика; С= -- 1; щ - разрядность кодов, которыми выражаются веса задач, причем при нечетном в число С округляется до ближайшего большего целого числа, Регистры группы 1 являются регистрами сдвига на два разряда в сторону старших разря. дов при поступлении каждого импульса на тактовый вход. Информация с их выходов переписывается снова в регистры, а съем информации производится с прямых и инверсных выходов двух старших (последнего и предпоследнего) разрядов, Единичный потенциал подается на вход элемента НЕ 22 для задания режима минимального времени реализации пакета за 1615721дач, нулевой потенциал -для задания режима минимального среднего времени ожидания задачи в пакете, это соответствует режимам распределения задач по процессорам вычислительной системы по критерию минимума (максимума) веса задач в пакете. Если на вход элемента НЕ 22 подан потенциал "1", то при подаче сигнала на установочные входы регистры группы 1 сбрасываются в "0", при подаче потенциала "0" сбрасываются в "1" (во всех разрядах).Работа устройства начинается после задания режима и занесения весов задач в регистры группы 1; тогда знаки ("1" или "0"), записанные в двух последних разрядах регистров группы 1, с прямых и ииверсных выходов этих разрядов выступают через открытые элементы И групп 2 (3) и 4(5) и элементы ИЛИ групп 6 и 7 на саответ-ствующие входы элементов ИЛИ групп 8 и 9 и ИЛИ-НЕ 24.На выходах элементов ИЛИ групп 6 и 7 могут быть различные комбинации нулей и единиц, Вначале рассмотрим случай, когда на выходе какого-то одного элемента ИЛИ6, например ИЛИ 6 ь - единичный потенци ал. Тогда на выходах элементов ИЛИ-НЕ 24и ИЛИ группы 8 - потенциал "0", кромеэлемента ИЛИ 8 ь единичный потенциал с , выхода которого поступает на второй вход элемента И 9 и первый вход элемента И 11 ь , поскольку на первом входе элемента И 9 - ; потенциал "О", то на выходах всех элементов И группы 9 - потенциал "О", на выходе элемента ИЛИ-НЕ - потенциал "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 работы устройства) состояние ("О" или "1" во. всех разрядах), Через элемент ИЛИ 29 единичный потенциал с выхода триггера 12 проходит на второй вход элемента И - НЕ 32, на первый вход которого поступает "1" с 10 инверсного выхода переполнения счетчика31; Появляющийся на выходе элемента ИНЕ 32 нулевой потенциал закрывает все элементы И групп 2 - 5 на время, когда после подачи сигнала на вход запуска генератор 15 ЗО осуществляет выдачу импульсов, счет которых ведет счетчик 31, а информация в регистрах группы 1 при поступлении каждого импульса на тактовый вход смещается на два разряда вправо и одновременно пере записывается, Когда счетчик 31 переполняется, сигнал с прямого выхода переполнения останавливает генератор 30, устанавливает счетчик 31 в исходное состояние, а также через элемент задержки сбра сывает в "0" триггеры 12. Начинается новыйцикл устройства по выбору очередной задачи путем сравнения содержимого очередных разрядов весов задач, записанных в регистр группы 1 и поступа;ощих с соответ ствуащих выходов последнего и предпоследнего разрядов, кроме содержимого заблокированного (в данном случае - регистра 1) регистра группы 1. Конечно, при одной "1" в самом начале работы устройства 35 перезапись информации в регистры группы1 путем запуска генератора 30 можно было и не,гзлать, но удобно это делать потому, гга такой вариант появления сигналов на выходах элементов И группы 11 может пра изойти в процессе работы устройства, и тогда такой режим перезаписи с блокировкой на эта время элементов И групп 2 - 5 необходим, Для унификации работы устройства и сделала перезапись информации в начале 45 работы устройства при одной единице навыходах элементов И группы 11.Если с выходов регистров группы 1 поступают одни нули, го на выходах всех элементов И группы 11 - нули, на выходах 50 элементов ИЛИ группы 20 - нули, и послеподачи сигнала на вход запуска генератор ЗО начинает выдачу импульсов, первый из которых, поступив на тактовые входы регистров группы 1, сдвигает записанные в них 55 коды на два разряда вправоа два старшихразряда перезаписываются в два первых разаяда), Пусть теперь на выходах нескольких элементов ИЛИ группы 6, например ИЛИ 6 и 61;потенциал "1", на выходе элементов ИЛИ 7 - готенциал "1", на выходахостальных элементов ИЛИ группы 7 - "0", Тогда на выходе элемента ИЛИ-НЕ 24 - "0", на выходах элементов ИЛИ 8 и 8 - "1", на выходе элемента И 9 - "1", на выходах остальных элементов И группы 9 - "0", на выходе элемента ИЛИ-НЕ 25 - "0", на выходе элемента И 11, - "1", на выходах остальных элементов И группы 11 - "0". Далее аналогично рассмотренному на выходе элемента ИЛИ 20 появится импульс как сигнал на выбор задачи с номером один. Аналогично устройство работает и в случае, когда "1" присутствует на выходах элементов ИЛИ группы 7, но только на выходе какого-то одного элемента ИЛИ группы б присутствует "1".Теперь рассмотрим случай, когда одинаковые коды снимаются с двух или более регистров группы 1. Пусть, например, "1" присутствует на выходах элементов ИЛИ б и бь а с выходов элементов ИЛИ 7 и 7 также поступает потенциал "1", Тогда на выходе элемента ИЛИ-НЕ 24 - "0", на выходах элементов ИЛИ 8; и 8; - "1", на обоих входах и выходах элементов И 9 и 9; - "1", на выходах элементов И 11 и 111 - "1", на выходах остальных элементов И группы 11 - "0", Аналогично и при "0" на обоих выходах элементов ИЛИ 7 и 7 только на выходах элементов И 111 и 11 - "1". С выходов элементов И 11.и 111 единичные сигналы поступают на входы элементов И 15 ь 15 и 16 ь 161 и на функциональный узел из групп элементов И 19, ИЛИ 21 и ИЛИ 27, на выходе которого появляется "1", открывающая элементы И 16 и 16, поэтому триггеры 131 и 131 перебрасываются в единичное состояние. Появляющийся на выходе элемента ИЛИ 28 единичный потенциал открывает элементы И группы 17, и тогда единичные сигналы с инверсных выходов остальных триггеров группы 13 проходят на единичные входы одноименных триггеров группы 14 и перебрасывают их в единичное состояние; нулевые потенциалы с их инверсных выхо-, дов закрывают соответствующие элементы И групп 2 - 5 и блокируют выдачу информации из регистров группы 1 до конца данного цикла работы устройства по выбору очередной задачи, Сигналом с выхода элемента 33 задержки триггеры группы 13 возвращаются в нулевое состояние. Далее при выдаче генератором 30 следующего импульса и обусловленного этим сдвига записанной в регистрах группы 1 информации на два разряда вправо производится сравнение кодов выдаваемой регистрами группы 1 информации, но уже информация заблокированных регистров группы 1 в сравнении не участвует,10 15 20 25 30 35 40 45 50 55 По мере работы устройства наступит момент, когда будет найден максимальный код, и импульс будет выдан с выхода соответствующего элемента ИЛИ группы 20. Однако возможен и случай, когда в двух или более регистрах группы 1 записаны максимальные веса, например в регистрах 1 и 11, Тогда к моменту переполнения счетчика 31 лишь триггеры 14; и 141 останутся в состоянии "0", и потому лишь с их инверсных выходов единичные импульсы через элементы И 18 и 18 и элементы ИЛИ 20 и 20 пройдут на соответствующие выходы устройства, когда сигнал переполнения с выхода счетчика 31 поступит на вторые входы элементов И группы 18. Порядок выполнения задач не имеет значения - можно вначале выполнить первую, а можно и вторую,Технико-экономический эффект предложенного устройства по сравнению с прототипом состоит в существенном повышении точности работы, что достигается перезаписью информации в регистрах группы 1 после каждой очередной задачи, в осуществлении зависимого процесса сравнения кодов, записанных в регистрах группы 1, путем блокировки тех из них, в которых оказываются записанные меньшие(большие) коды, а также путем устранения неверных связей выходов триггеров группы 12, Этим достигнут правильный выбор задач согласно назначенному критерию,Формула изобретения Устройство для распределения заданий процессорам, содержащее группу регистров, шесть групп элементов И, пять групп элементов ИЛИ, два элемента ИЛИ-НЕ, первый элемент задержки, первую группу триггеров, счетчик и генератор импульсов, причем прямые и инверсные выходы двух старших, разрядов каждого регистра группы соединены с первыми входами соответствующих элементов И соответственно первой,/второй, третьей и четвертой групп, выходы элементов И первой и третьей, второй и четвертой групп подключены соответственно к входам соответствующих элементов ИЛИ первой и второй групп, выходы элементов ИЛИ первой группы соединены с первыми входами одноименных элементов ИЛИ третьей группы и соответствующими входами первого элемента ИЛИ-НЕ, выход которого подключен к вторым входам элементов ИЛИ третьей группы, выходы элементов ИЛИ второй группы соединены с первыми входами одноименных элементов И пятой группы, к вторым входам которых подключены выходы соответствующих элементов ИЛИ третьей группы, выходы элементов И пятой группы соединены с5 10 15 20 25 30 35 40 45 первыми входами одноименных элементов : ИЛИ четвертой группы и входами второгоэлемента ИЛИ-НЕ, выход которого подключен к вторым входам элементов ИЛИ четвертой группы, инверсные выходы триггеров первой группы соединены с первыми входа, ми одноименных элементов ИЛИ пятойгруппы, выход первого элемента задержки соединен с инверсными входами триггеров первой группы, вход первого элемента задержки соединен с первыми входами элементов И шестой группы, о т л и ч а ю щ е - е с я тем, что, с целью повышения достоверности функционирования, в него дополнительно введены шестая группа элементов ИЛИ, вторая и третья группы триггеров, второй элемент задержки, с седьмой по одиннадцатую группы элементов И, элемент , И-НЕ, четыре элемента ИЛИ и два элемента ,НЕ, выход первого из которых соединен с , вторыми входами элементов И первой и второй групп, а вход соединен с вторыми входами элементов И третьей и четвертой групп и является входом задания режима работы устройства, пусковым входом устройства является вход запуска генератора импульсов, выход которого подключен к тактовым входам регистров группы и входу считывания счетчика, инверсный выход переполнения которого соединен с первым входом элемента И-НЕ, выход которого подключен к третьим входам элементов И с первой по четвертую группы, прямой выход переполнения счетчика соединен с входом рстанова генератора импульсов, установочНым входом счетчика и через первый элеМент задержки с нулевыми входами григгеров второй группы, инверсные выхо ды которых подключены к четвертым вхо. дам одноименнных элементов И с первой почетвертую группы и к вторым входам одноименных элементов И шестой группы, выход каждого регистра группы соединен с его йнформационным входом, первые и вторые Входы элементов И седьмой группы подключены к выходам одноименных элементов ИЛИ соответственно третьей и четвертой групп, третьи входы элементов И седьмой группы обьединены и соединены с выходом первого элемента ИЛИ, входы которого подключены к выходам элементов ИЛИ первой и второй групп, выходы элементов И седьмой группы подключены к первым входам одноименных элементов И восьмой, девятой и десятой групп, вторые входы элементов И десятой группы соединены с выходами одноименных элементов ИЛИ шестой группы, первый вход 1-го элемента И десятой группы (1=1, и, где и - число задач в пакете) соединен с входами )-х элементов ИЛИ шестой группы (/=1 и, Ф, выходы элементов И десятой группы подключены к входам второго элемента ИЛИ, выход которого соединен с входом второго элемента НЕ и вторыми входами элементов И девятой группы, выход второго элемента НЕ подключен к вторым входам элементов И восьмой группы, выходы которых соединены с единичными входами одноименных триггеров первой группы, выходы элементов ИЛИ пятой группы подключены к установочным входам одноименных регистров группы и являются выходами устройства, выходы элементов И девятой группы подключены к единичным входам одноименных триггеров третьей группы, прямые выходы которых соединены с входами третьего элемента ИЛИ, выход которого подключен к первым входам элементов И одиннадцатой группы и через второй элемент задержки к нулевым входам триггеров третьей группы, инверсные выходы которых соединены с вторыми входами одноименных элементов И одиннадцатой группы, выходы которых подключены к единичным входам одноименных триггеров второй группы, выходы элементов И шестой группы соединены с вторыми входами одноименных элементов ИЛИ пятой группы, инверсные выходы триггеров первой группы соединены с входами четвертого элемента ИЛИ, выход которого соединен с вторым входом элемента И-НЕ,1615721Составитель Г.Пономарева Редактор О,Юрковецкая Техред М.Моргентал Корректор В.Гирняк Заказ 3988 Тираж 570 Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР113035, Москва, Ж, Раушская наб., 45Производственно-издательский комбинат "Патент", г, Ужгород, ул.Гагарина, 101