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

(5) УСТРОЙСТВО для РАСПРЕДЕЛЕНИЯ ЗАДАНИЙ ПРОЦЕССОРАМ

1

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

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

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

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

Цель изобретения - расширение области применения и функциональных

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

Поставленная цель достигается тем,

15 что в устройство для распределения заданий процессорам, содержащее элемент ИЛИ, п/2 каналрв (п - число ре,шаемых задач в пакете), каждый из которых содержит два сдвигающих регистра, два элемента И, две схемы сравнения и два триггера, причем выходы первого и второго сдвигающих регистров каждого канала соединены соответ ственно с первыми выходами первого и второго сдвигающих регистров и соответствующих элементов И канала, выходы которых соединены с первыми входами соответственно первой и второй схем сравнения канала и с соответствующим входом элемента ИЛИ, выход которого соединен с вторыми входами первой и второй схем сравнения каждого канала, выходы которых соединены соответственно с первыми входами первого и второго триггеров канала , выходы которых соединены соответственно с вторыми входами перво го и второго элементов И,, первый и второй синхронизирующие входы устройства соединены соответственно с вторыми входами первого и второго сдвигающих регистров и первого и вто рого триггеров-всех каналов, зведены информационный регистр,счетчик, блок элементов И, элемент ИЛИ-НЕ, а в каждый канал введены элементы ИЛИ, НЕ,, ИЛИ-НЕ, причем щход и выход счетчика соединены соответственно с первым синхронизирующим входом устройства и первым входом блока элементов И, выход которого соединен с первым входом информационного регистра, выход которого соединен с третьими входами первого и второго сдвигающих регистров каждого канала и является выходом устройства, выход элемента ИЛИ-НЕ соединен с вторым вхо дом блока элементов И, выход элемента ИЛИ-НЕ каждого канала соединен с соответствующим входом блока элементов И, первый вход элемента ИЛИ-НЕ каждого канала соединен через элемент НЕ канала с первым входом элемента ИЛИ и выходом второго триггера своэго канала, второй вход элемента ИЛИ-НЕ -го канала соединен с вторым входом элемента ИЛИ i-го канала и с выходом элемента ИЛИ (i + l)-ro канала, первый и второй входы элемента ИЛИ-НЕ соединены соответственно с выходами первого триггера и элемента ИЛИ первого канала. CyutHOCTb изобретения заключается в том, что, используя имеющиеся узлы известного устройства и введя дополнительные узлы с соответствующими свя зями, становится возможным по парамет рам решаемых задач (например, требуемом времени для решения задачи) соелазить некоторое расписание порядка реализации набора задач. Такая дисциплина реализации пакета задач в мультипроцессорной вычислительной системе обеспечивает минимальное среднее время пребывания задач в системе; На чертеже представлена структурная схема устройства для распределения заданий процессором. Устройство содержит кольцевые сдвигающие регистры 1;,, l.,..., 1,, где п - число решаемых задач в пакете, элементы И 2, 2,... ,2у,, триггеры 3-t, З2.,...,3, схемы сравнения 4 , 4,...4v ,.,, элементы НЕ 5, 5,,. .,5,. элементы ИЛИ Ь, 6,... ,6,., элементы ИЛ И-НЕ 7 , 7i,... ,7., информационный регистр 8, блок элементов И 9, элемент ИЛИ 10, счетчик 11 с коэффициентом пересчета, равным числу т, где т - число разрядов в кольцевом сдвигающем регистре 1. Кроме того. на чертеже обозначены выход 12 устройства, синхронизирующие входы 13, 14 и 15 устройства. Устройство работает следующим образом. В регистрах 1 первоначально, находятся п-разрядные коды, соответствующие длительностям решения задач.в пакете, триггеры 3 находятся в единичном состоянии, а регистр 8 находится в нулевом состоянии. Поэтому на выходах триггеров 3 присутствует высокий потенциал, и сигнал с выхода триггера старшего разряда (на чертеже эти триггеры не показаны) регистр 1 (, п) через элемент И 2 поступает На I-и вход элемента ИЛИ 10, на выходе которого возникает сигнал, если в сравниваемых разрядах хотя бы одного из кодов имеется единица. Этот сигнал поступает на первые входы каждой схемы сравнения k- , на выходах которых возникает сигнал сброса соответствующего триггера 3, в том случае, если информация в сравниваемом разряде данного сдвигающего регистра 1 совпадает с нулем. С триггера на элемент И 2 поступает запрещающий (низкий) потенциал перед началом сравнения следующих разрядов чисел. I После процедуры сравнения старших разрядов кодов чисел происходит подача импульса сдвига на вход 13 устройства, в результате чего в кольцевых сдвигающих регистрах 1 происходит сдвиг кодов на один разряд, и процесс сравнения очередных разрядов продолжается, и так далее до тех пор, пока число таких сдвигов и сравнении не будет равно числу т, о чем свидетельствует сигнал переполнения счетчика 11 , Сигнал переполнения счетчика 11 поступает на первый вход блока элементов И 9 выходы которых подсоединены к входу регистра 8. К моме ту появления сигнала переполнения на выходе счетчика 11 закончится процесс определения максимального кода (или кодов, если их несколько). При одновременном единичном состоянии не скольких триггеров 3 на выходе 12 ус ройства (и на вторых входах групп элементов И 9) появляется единичный сигнал только на одной 1-дй шине, пр чем i 7 j , где ,n; ,n, т.е. пре почтение отдается той задаче, порядковый номер которой наибольший ср ди задач, имеющих одинаковое требуемое время .для решения. Это достигает ся тем, что высокий потенциал с выхо да триггера 3 подается через элемен ты ИЛИ 6 на первые входы предыдущих элементов ИЛИ-НЕ 7, вторые входы которых подсоединены к выходам одноиме ных элементов НЕ 5. Таким образом, позиционный код но мера максимального числа получается уже на вторых входах элементов И 9. который далее фиксируется в регистре 8, подается на выход 12 устройства, а также обеспечивает сброс соответствующего регистра 1 в нулевое сос тояние. После назначения выбранной .задачи (программы) для реализации в вычислительной системе по входу 15 подается сигнал сбрасывания регистра 8 в исходное нулевое состояние, по входу 14 - сигнал установки триггеров 3 в единичное состояние, а далее по входу 13 подается серия си|- налов сдвига, в результате чего обеспечивается процесс определения номера очередной задачи из решаемого пакета для реализации в вычислительной системе. Таким образом, применение данного устройства позволяет расширить область применения устройства и расширить его функциональные возможности за счет обеспечения выбора одной из задач пакета при реализации его в мно .гопроцессорной вычислительной системе Формула изобретения Устройство для распределения заданий процессорам, содержащее элемент ИЛИ, п/2 каналов (п - число решаемых задач в пакете), каждый из которых содержр т два сдвигающих регистра, два элемента И, две схемы сравнения и два триггера, причем выходы первого и второго сдвигающих регистров каждого канала соединены соответственно с первыми входами первого и второго сдвигающих регистров и соответствующих элементов И этого же канала, выходы которых соединены с первыми входами соответственно первой и второй схем сравнения канала и с соответствующим входом элемента ИЛИ, выход которого соединен с вторыми входами первой и второй схем сравнения каждого канала, выходы которых соединены соответственно с первыми входами первого и второго триггеров канала, выходы которых соединены соответственно с вторыми входами первого и второго элементов И, первый и второй синхронизирующие входы устройства соединены соответственно с вторыми входами первого и второго сдвигающих регистров и первого и второго триггеров всех каналов, отличающееся тем, что, с целью расширения области применения, в него введены информационный регистр, счетчик, блок элементов И, элемент ИЛИ-НЕ, а в каждый канал введены элементы ИЛИ, НЕ, ИЛИ-НЕ, причем вход и выход счетчика соединены соответственно с первым синхронизирующим входом устройства и первым входом блока элементов И, выход которого соединен с первым входом ин.формационного регистра, выход которого соединен с третьими входами первого и второго сдвигающих регистров каждого канала и является выходом устройства, выход элемента ИЛИ-НЕ соединен с вторым входом блока элементов И, выход элемента ИЛИ-НЕ каждого канала соединен с соответствующим входом блока элементов И, первый вход элемента ИЛИ-НЕ каждого канала соединен через элемент НЕ канала с пер.вым входом элемента ИЛИ и выходом второго триггера своего канала, второй вход элемента ИЛИ-НЕ i-ro канала соединен с вторым входом элемента ИЛ1 i-ro канала и с выходом элемена ИЛИ (|+1)-го канала, первый и втоой входы элемента ИЛИ-НЕ соединены соответственно с выходами первого риггера и элемента ИЛИ первого канала.

Источники информации,2, Авторское свидетельство СССР

принятые 80 внимание при экспертизе f 620976, кл. G Об F 7/02, 1977

К Авторское свидетельство СССР (прототип). Н- , кл. G Об F 8/Ц6. 197.