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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСНИ153 19) СПУБЛИН Р 94 НИЯ ТЕЛЬСТВУ ТОРСНО сныхаоэлемент кже менты о, содержит ого кода,5, элей в 18 оды 1 блок жит И 2 ы ИЛИентыода. ни вь ей ойство позволяет и орной информации о ния задач пакета о а времени уществлятьвыпол ОСУДАРСТВЕННЫЙ НОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМПРИ ГКНТ СССР АНИЕ ИЗОБ(56) Авторское свидетельство СССРКф 966697, кл, С 06 Р 9/46, 1980.Авторское свидетельство СССР9 964643, кл. С 06 Р 9/46, 1980.(54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯЗАДАНИЙ ПРОЦЕССОРАМ(57) Изобретение относится к вычилительной технике и предназначенодля использования в многопроцессоных или многомашинных вычислительсистемах, Цель изобретения - сокрщение объема оборудования, Устройство распределения заданий процесрам содержит каналы, каждый из ко Изобретение относится к вычислительной технике и может найти приме- нение в многопроцессорных или. многомашинных системах при распреде" ленин заданий процессорам.Цель изобретения - сокращение объема оборудования.На фиг.1 приведена структурная схема устройства; на фиг.2 - структурная схема блока выделения максимального кода.Устройство для распределения заданий процессорам содержит вход 1 запуска устройства, ответные входы 2 устройства, каналы К, каждый из которых содержит триггер 3 и группу элементов НЕ 4 элемент ИЛИ 5, элемент 6 задержки, входы 7 и 8 режима,устрых состоит из триггера, двух группэлементов И, группы элементов НЕ,группы элементов ИЛИ, общие для всехканалов блок выделения максимальногокода, элемент ИЛИ, элемент задержки,триггер, группу элементов ИЛИ, группу элементов ИЛИ-НЕ, элемент И.Распределение задач между процессорами осуществляется с учетом априорнойинформации о времени их выполнения,В зависимости от режима работы устройства первой для выполнения назначается задача, имеющая либо максимальное, либо минимальное время выполнения, Если среди задач пакета имеетсянесколько задач с одинаковым временемвыполнения, предпочтение отдаетсязадаче с большим порядковым номером.1 з,п, ф-лы, 2 ил. ройства, каналы содержатИ 9 и 10, Устройство содетриггер 11, каналы К - э12. Устройство, кроме тогблок 13 выделения максималэлементы ИЛИ 14, элементменты ИЛИ-НЕ 16, выходыства, группы кодовых входустройства, управляющиеблока 13, труппы входов13 и выходы 21 блока 13,Блок 13 (фиг.2) содет -НЕ 22, элементы ИЛм И 24 и 25, узлы 26назначение задач на выполнение либопо критерию минимального среднеговремени ожидания решения задач(т.е. первой назначается задача,имеющая минимальное время выполнения),5либо по критерию минимального времени реализации пакета (в этом случаепервой на выполнение назначается задача, имеющая максимальное время 10выполнения). Среди задач, иМеющихз.,одинаковое время выполнения, предпочтение отдается задачес большим порядковым номером.Устройство для распределениязаданий процессорам работает следующим образом.В исходном состоянии триггеры 3каналов и триггер 1 установлены внулевое состояние. На кодовые входы18 поданы двоичные коды времени выполнения, которые с входов8 поданы напервые входы элементов И 10 каждогоканала и через элементы НЕ 4 - на входы элементов И 9 каждого канала, Если устройство работает в режиме минимального времени реализации пакетазадач, на вход 7 подан единичный потенциал, если же устройство работаетв режиме минимального среднего времени ожидания решения задачи, то единичный потенциал подан на вход 8 устройства,Инициализация устройства производится подачейединичного импульса на вход 1 запуска устройства, который через элемент ИЛИ 5 поступает иа вход элемента 6 задержки. По переднему Фрон-. ту импульса устанавливаются в единичное. состояние триггеры 3 каждого канала, Единичные сигналы с прямых выходов этих триггеров поступают на входы 19 блока 3, на первые входй элементов И 9 и на первые входы элементов И 10.Предположим, что устройства рабо - тает в режиме минимального времени реализации пакета задач и на вход 7 устройства подан единичный потенциал-50 Этот потенциал присутствует на вторых входах всех элементов И 10 групп всех каналов, поэтому разрешена выдача всех кодов через эти элементы на вторые входы элементов ИЛИ 12 каналов и далее на соответствующие выходы55 20 каждого канала, Таким образом, на группы входов блока 13 подают коды времени выполнения заданий. Блок 13 работает следующим образом. Первые (старшие) разряды кодов времени выполнения задач подаются на первые входы 20 первых элементов И каждого узла 26, Аналогично остальные разряды кодов подаются на первые входы соответствующих элементов И 25 узлов 26. С входов 19 блока 13 единичные сигналы поступают на первые входы первых элементов И 24 и И 25 всех узлов 26.Алгоритм работы блока выделения максимума следующий. Анализируется содержимое первых (старших) разрядов всех кодов. Если эти разряды содержаттолько нули, то на следующем шаге анализируются вторые разряды всех кодов. Если же в первых разрядах имеются как нули, так и единицы, то на втором шаге анализируются только те коды, которые имеют в первом разделе единицы.На втором шаге аналогично просматриваются вторые разряды кодов, причем в работе принимают участие те узлы 26, в которых бып единичный сигнал переноса с предыдущего, в данном случае первого элемента ИЛИ 23 групАПЫу И ТедеНа последнем шаге анализируются последние разряды кодов, в результате чего появляется единичный сигнал на том выходе 21, который соответствует максимальному коду. С выхода элемента ИЛИ 5 единичный импульс поступает на вход элемента 6 задержки, а также на вход установки в нуль триггера 11,.не меняя его состояния. Через время, выбранное с учетом того, чтобы завершились переходные процессы в блоке 13; передним фронтом задержанного импульса триггер 11 устанавливается в единичное состояние, разрешая выдачу единичного сигнала на соответствующий выход 17, который указывает, что на выполнение назначена соответствующая задача,В общем случае, когда в пакете выявлено несколько задач с одинаковым временем выполнения, единичные сигналы возникают на соответствующих выходах 21 блока 13, а на выходах 17 устройства - единичный сигнал только на одном выходе, т.е, предпочтение отдается той задаче, порядковый номер которой наибольший среди задач с одинаковым требуемым временем для153977решения, Это достигается наличием цепи элементов 14 и 16.На этом первый этап назначения задач заканчивается,1 5Когда задача взята на выполнение,на соответствующий вход 2 подаетсяединичный импульс, который черезэлемент ИЛИ 5 поступает на элемент6 задержки, и, кроме того, переднийфронт этого импульса перебрасываеттриггер 11 в нулевое состояние. Врезультате этого прекращается выдача сигнала насоответствующий выход17 устройства. В то же время единичный импульс с входа 2 устанавливаеттриггер 3 соответствующего канала в. нулевое состояние. В результате этогозакрываются элементы И 9 и 1 О и выдача кода времени выполнения задачи на 20выходы 20 этого канала прекращается,Кроме того, с выхода этого триггерапоступает нулевой сигнал на соответствующий вход 19 блока 13, Так как насоответствующие входы 20 и на вход 2519 блока 13 подаются .нулевые сигналы,этот узел 26 не принимает участие вдальнейшей работе блока 13. Даннаязадача пакета исключается из рассмотрения. 30Далее работа устройства происходит аналогично описанному.Если устройство работает в режимеминимального среднего времени ожидания решения задачи то первой должнавыбираться на выполнение та задача,у которой время выполнения минимальное. В этом случае единичный управляющий сигнал подается ла вход 8 устройства. Этот сигнал открывает по второму входу элементы И 9 каждого канала,что в свою очередь разрешает выдачуобратных кодов времени выполнениязадач (через элементы НЕ 4, элементыИ 9 группы, элементы ИЛИ 12 группы) 45на выходы 20 каналов. В остальномработа устройства полностью аналогична описанному, но теперь первой выбирается задача, имеющая минимальноевремя выполнения, 50Формула изобретения1.Устройство для распределения заданий процессорам, содержащее каналы, блок выделения максимального кода, группу элементов ИЛИ и группу элементов ИЛИ-НЕ, выходы которых являются выходами устройства, первый и второй 8 6входы режима которого соединены с первым и вторым сигнальными входами всехканалов соответственно, каждый ответный вход устройства соединен с информационным входом одноименного канала, кодовые входы каждого из которыхсоединены с одноименной группой кодовых входов устройства, группа информационных выходов каждого канала соединена с одноименной группой входов блока выделения максимального кода, прямой выход каждого элемента ИЛИ группы, начиная с последнего элемента,соединен с первыми входами предьдущего элемента ИЛИ группы и предыдущегоэлемента ИЛИ-НЕ группы, о т л и -ч а ю щ е е с я тем, что, с цельюсокращения объема оборудования,устройство содержит элемент ИЛИ,триггер, элемент задержки и элементИ, причем ответные входы и вход запуска устройства соединены с входамиэлементами ИЛИ, вход запуска устройства соединен с входами запускавсех каналов, сигнальный выход каждо-.го канала соединен с одноименнымуправляющим входом блока выделениямаксимального кода, последний выходкоторого соединен с первым входомэлемента И и с первыми входамипоследних элементов ИЛИ и ИЛИ-НЕгрупп, каждый выход блока выделениямаксимального кода, начиная с предпоследнего, соединен с вторым входомсоответствующего элемента ИЛИ группы,начиная с последнего, инверсный выход каждого элемента ИЛИ. группы соединен с вторым входом одноименногоэлемента ИЛИ-НЕ группы, выход элемента И является соответствующим выходом устройства, третьи входы элементов ИЛИ-НЕ группы соединены с инверсным выходом триггера, прямой выход которого соединен с вторым входом элемента И, выход элемента ИЛИсоединен с входом сброса триггера ичерез элемент задержки - с единичным входом триггера,2,Устройство по п,1, о т л и ч а ю - щ е е с я ,тем, что блок выделения максимального кода содержит группу элементов ИЛИ-НЕ, узлы выделения кода, каждый из которых содержит две группы элементов И и группу элементов ИЛИ, причем д-й вход 1-й группы входов блока, где .=1п, и - раз-. рядность кода задания, 1=1,К, К -, 1539778количество заданий, соединен с первымвходом -го элемента И первой группы3-го узла вьщеления кода," выходы1.-х элементов И первой группы каждого узла выделения кода соединены свходами х-го элемента ИЛИ-НЕ группы,выход д-го элемента ИЛИ-НЕ группы соединен с первыми входами -х элементовИ второй группы всех узлов выделениякода, вторые входы первых элементовИ первой и второй групп 1 -го узлавыделения кода соединен с 1-м управляющим входом блока, выходы -хэлементов И первой и второй групп вкаждом узле вьщеления кода соединеныс входами .-го элемента ИЛИ группыданного узла выделения кода, выход1-го элемента ИЛИ группы в каждомузле вьщеления кода соединен с вторыми входами (д+1) -х элементов Ипервой и второй групп данного узлавьщеления кода, выходы последнихэлементов ИЛИ группы являются выходами блока,153978 оставитель М.Кудряшевехред М. Ходанич Корректор Л.11 ата Петр Редак ГКНТ ССС оизводственно-издательский комбинат "Патент", г, Ужгород, ул, Гагарина, 101 аказ 220 Тираж 557НИИПИ Государственного комитета по изобретенйя 113035, Москва, Ж, Раушская Подписноеи открытиямб., д. 4/5