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

(72) Авторы изобретения В,А.Титов, Н,Н.Брянцев, А.В.Чугунов и В ХНИЧЕСЫАЯИЪЛВЮТЕКА Заявитель 4) УСТРОЙ ДЛЯ РАСПРЕДЕЛЕНИЯ ЗАДАНИЙРОЦЕ ССОРАМ герц и сх тц И, три 23.этого уст возможнос распредел м в мульт ной вцчис гистры, элеме мц сравненияНедостаток ключается в н ванин его для ний процессо или многом теме. йства эа и испол ния зад процессорно ительной си р ашиНаиболе является у бирательну ечых задач Изобретение относится к вычи" слительной технике и может быть использовано при органиэации вычислительного процесса по обработке пакета задач в многопроцессорной или в многомашинной вычислительной системе.Известно устройство для распределения заданий процессорам, содержащее блок управления, регистр, шифратор, блоки очередности, коммутаторы и элементы ИЛИ 1.Однако оно обеспечивает эффективную обработку только случайного потока задач без учета априорной ин формации о их параметрах на основе обслуживания запросов на решение в порядке поступления,близким к предлагаемому ройство, содержащее сосхему, по числу решапакете сдвигающие реЦель изобретения - расширение области применения и функциональных овозможностей устройства за счет обес печения выбора одной из,задач пакета при реализации его в многопроцессорной вычислительной системе.15 Поставленная цель достигается темчто в устройство для распределения заданий процессорам, содержащее элемент ИЛИ, и/2 каналов (и - число ре,шаемых задач в пакете), каждый из ко о торых содержит два сдвигающих регистра, два элемента И, две схемы сравнения и два триггера, причем выходы первого и второго сдвигающих регист3 96669ров каждого канала соединены соответственно с первыми выходами первогои второго сдвигающих регистров и соответствующих элементов И канала,выходы которых соединены с первымивходами соответственно первой и второй схем сравнения канала и с соответствующим входом элемента ИЛИ, выход которого соединен с вторыми входами первой и второй схем сравнения 1 Окаждого канала, выходы которых соединены соответственно с первыми входами первого и второго триггеров канала, выходы которых соединены соответственно с вторыми входами перво-,дго и второго элементов И,. первый ивторой синхронизирующие входы устройства соединены соответственно свторыми входами первого и второгосдвигающих регистров и первого и вто- орого триггеров -всех каналов, зведены инФормационный регистр, счетчик,блок элементов И, элемент ИЛИ-НЕ, ав каждый канал введены элементы ИЛИ,НЕ, ИЛИ-НЕ, причем вход и выходсчетчика соединены соответственно спервым синхронизирующии входом устройства и первым входом блока элементов И, выход которого соединен спервым входом инФормационного регистра, выход которого соединен с третьими входами первого и второго сдвигающих регистров каждого канала иявляется выходом устройства, выходэлемента ИЛИ-НЕ соединен с вторым входом блока элементов И, выход элемента ЗИДИ-НЕ каждого канала соединен с соответствующим входом блока элементовИ, первый вход элемента ИЛИ-НЕ каждого канала соединен через элемент НЕканала с первым входом элемента ИЛИ 40и выходом второготриггера своего канала, второй вход элемента ИЛИ-НЕ1-го канала соединен с вторым входомэлемента ИЛИ 1-го канала и с выходомэлемента ИЛИ (1+1) -го канала, первыйи второй входы элемента ИЛИ-НЕ соединены соответственно с выходами первого триггера и элемента ИЛИ первогоканала,Сущность изобретения заключается фв том, что, используя имеющиеся узлыизвестного устройства и введя дополнительные узлы с соответствующими связями, становится возможным по параметрам решаемых задач (например, требуемом времени для решения задачи) составить некоторое расписание порядкареализации набора задач, Такая дис 7 4циплина реализации пакета задач в мультипроцессорной вычислительной системе обеспечивает минимальное среднее время пребывания задач в системе;На чертеже представлена структурная схема устройства для распределения заданий процессором.Устройство содержит кольцевые сдвигающие регистры 1, 1.,1 , где2.фф иф и - число решаемцх задач в пакете, элементы И 2, 2 2, триггеры 3, 33, схемы сравнения 4, 42., 4, элементы НЕ 5 , 5 5элементы ИЛИ Ь, 66 элементы ИЛИ-НЕ 7 77 , инФормационный регистр 8, блок элементов И 9, элемент ИЛИ 10, счетчик 11 с коэФфициентом пересчета, равным числу л, где я- число разрядов в кольцевом сдвигающем регистре 1. Кроме того, на чертеже обозначены выход 12 устройства, синхронизирующие входы 13, 14 и 15 устройства.Устройство работает следующим образом.В регистрах 1 первоначально. находятся щ-разрядные коды, соответствующие длительностям решения задач в пакете, триггеры 3 находятся в единичном состоянии, а регистр 8 находится в нулевом состоянии, Поэтому на выходах триггеров 3 присутствует высокий потенциал, и сигнал с выхода триггерА старшего разряда (начертеже эти триггеры не показаны)регистр 1 (=1, и) через элемент И 2 поступает на 1-й вход элементаИЛИ 1 О, на выходе которого возникает сигнал, если в сравниваемыхразрядах хотя бы одного из кодов имеется единица. Этот сигнал поступаетна первые входы каждой схемы сравнения 4, на выходах ко 1 орцх возникаетсигнал сброса соответствующего триггера 3, в том случае, если информация в сравниваемом разряде данногосдвигающего регистра 1 совпадает снулем. С триггера 3 на элемент И2 поступает запрещающий (низкий)потенциал перед началом сравненияследующих разрядов чисел.1После процедуры сравнения старших разрядов кодов чисел происходит подача импульса сдвига на вход 13 уст" ройства, в результате чего в кольцевых сдвигающих регистрах 1 происходит сдвиг кодов на один разряд, и процесс сравнения очередных разрядов продолжается, и так далее до тех пор,5 966 пока число таких сдвигов и сравнений не будет равно числу в, о чем свидетельствует сигнал переполнения счетчика 11, Сигнал переполнения счетчика 11 поступает на первый вход блока элементов И 9, выходы которых подсоединены к входу регистра 8, К моменту появления сигнала переполнения на выходе счетчика 11, закончится процесс определения максимального кода 10 (или кодов, если их несколько), При одновременном единичном состоянии нескольких триггеров 3 на выходе 12 уст ройства (и на вторых входах групп элементов И 9) появляется единичный 5 сигнал только на одной 1-ой шине, причем 1 7 1, где 1=1,п; 1=1,п, т.е, пред- почтение отдается той задаче, порядковый номер которой наибольший среди задач, имеющих одинаковое требуемое время.для решения, Это достигается тем, что высокий потенциал с выхода триггера 3 подается через элементы ИЛИ 6 на первые входы предыдущих элементов ИЛИ-НЕ 7, вторые входы ко- и торых подсоединены к выходам одноименных элементов НЕ 5.Таким образом, позиционный код номера максимального числа получается уже на вторых входах элементов И 9, который далее фиксируется в регистре 8, подается на выход 12 устройства, а также обеспечивает сброс соответствующего регистра 1 в нулевое состояние. После назначения выбранной задачи (программы) для реализации в35 вычислительной системе по входу 15 подается сигнал сбрасывания регист" ра 8 в исходное нулевое состояние, по входу 14 - сигнал установки триггеров 3 в единичное состояние, а46 далее по входу 13 подается серия сигналов сдвига, в результате чего обеспечивается процесс определения номера очередной задачи из решаемого пакета для реализации в вычислительной 15 системе.Таким образом, применение данного устройства позволяет расширить область применения устройства и расши-. рить его функциональные возможности М за счет обеспечения выбора одной из задач пакета при реализации его в многопроцессорной вычислительной системе,формула изобретения 55 устройство для распределения за-.даний процессорам, содержащее элемент 697 6ИЛИ, и/2 каналов (и - число ренаемыхзадач в пакете), каждый из которых содержит два сдвигающих регистра, дваэлемента И, две схемы сравнения и два триггера, причем выходы первого и вто. рого сдвигаюн 1 их регистров каждого канала соединены соответственно с первыми входами первого и второго сдвигающих регистров и соответствующих элементов И этого же канала, выходы которых соединены с первыми входами соответственно первой и второй схем сравнения канала и с соответствующим входом элемента ИЛИ, выход которого соединен с вторыми входами первой ивторой схем сравнения каждого канала, выходы которых соединены соответствен- . но с первыми входами первого и второго триггеров канала, выходы которых соединены соответственно с вторы" ми входами первого и .второго элементов И, первый и второй синхронизирующие входы устройства соединены соответственно с вторыми входами первого и второго сдвигающих регистров и первого и второго триггеров всех каналов, отличающееся тем, что, с целью расширения области применения, в него введены информационный регистр, счетчик, блок элементов И, элемент ИЛИ-НЕ, а в каждый канал введены элементы ИЛИ, НЕ, ИЛИ-НЕ, причем вход и выход счетчика соедине" ны соответственно с первым синхронизирующим .входом устройства и первым входом блока элементов И, выход которого соединен с первым входом ин,формационного регистра, выход которого соединен с третьими входами первого и второго сдвигающих регистров каждого канала и является выходом устройства, выход элемента ИЛИ-НЕ соединен с вторым входом блока элементов И, выход элемента ИЛИ-НЕ каждого канала соединен с соответствующим входом блока элементов И, первый вход элемента ИЛИ-НЕ каждого канала соединен через элемент НЕ канала с первым входом элемента ИЛИ и выходом второго триггера своего канала, второй вход элемента ИЛИ-НЕ 1-го канала соединен с вторым входом элемента ИЛ 1 1-го канала и с выходом элемента ИЛИ (1+1)-го канала, первый и второй входы элемента ИЛИ-НЕ соединены соответственно с выходами первого триггера и элемента ИЛИ первого канала.966697 ,82. Авторское свидетельство СССРР 620976, кл, 6 06 Р 7/02, 1977(прототип),оставитель Г.Понома ехред И. Гергель каз,7 / Тираж 731 НИИПИ Государственного комитета СССР по делам изобретений и открытий 13035, Москва, Ж, Раушская наб., 4/5 илиал П тент , г, Ужгород, ул. Проек Источники информации,принятые во внимание при экспертизе 1. Авторское свидетельство СССР Н 548859, кл, 6 06 Р 8/46, 1974, актор Л,Авраменко 7