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

) (1) бР 94 ГОСУДАРСТВЕННЫЙ НО ПО ДЕЛАМ ИЗОБРЕТЕН ТЕТ ССС И ОТНРЫ ИСАНИЕ ИЗОБРЕТЕНИЯ ПЕНИЯ вычислииспольа оченнописываизобрежности трат АВТОРСКОМУ СВИДЕТЕЛ 68993/24-240.07,4(54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЗАДАНИИ ПРОЦЕССОРАМ(57) Изобретение относится ктельной технике и может бытьзовано при автоматизации выбредной программы из информацсвязанного набора программ,емого графом без циклов. Цельютения является повышение надза счет снижения аппаратных1277106Устройство содержит матричную модельграфа, составленную из триггеров2 группу элеменгов ИЛИ 3, - 3группу элементов И1 - 4 , 8, - 8,12- 12 элементы И 1 ч . 1 7, 18,группу счетчиков 5 - 5, группу схем сравнения б. - б группы триггерон 7- 7, 9 - 9 , регистры,генератор 19 тактовых импульсов,счетчик 15 и блок 13 поиска максимального кода, состоящий из элементов И,элементов ИЛИ-НЕ и элементов ИЛИ.2 ил.Изобретение относится к вычислительной технике и может быть использовано при автоматизации выбора очередной программы из информационно-связанного набора программ, описываемого графом без циклов, для решенияего в многопроцессорной (многомашинной) вычислительной системе,Цель изобретения - повышение надежности за счет сокращения аппарат Оных затрат.На Фиг.1 изображена структурнаясхема устройства; на Фйг.2 - структурная схема блока поиска максимального кода 15Устройство содержит матричную модель 1 графа в составе пхп триггеров2, (1,3 6. 1,п) по числу столбцовматри 1.;и группу элементов ИЛИ 33, первую группу элементов И 47 Оглуппу счетчиков 5 ,5 групппу схем б .:, 6 сравнения, первую19 аае 9группу триггеров 7 , ,7 , третьюгруппу элементов И 8 8вторую.группу триггеров 9,9 регистр 2510 вь 1 бранных вершин, регистр 11 приоритета, вторую группу элементов И12 , , 12, блок 13 поиска максима 9 аЗльного кода, второй элемент И 14счетчик 15, триггер 16, третий 17 ипервый 18 элементы И, генератор 19тактовых импульсов, входы 20 и 21,выходы 22 и 23,Блок поиска максимального кода со-держит входные элементы И 21 элементы ИЛИ-НЕ 25,25 , (где 1 п - раз 35рядность сравниваемых кодов), группы26 -26, поразрядных узлов сравнения, состоящие из элементов ИПИ 27 иэлементов Ч 28, выходы 29 ,,29аеОи вхоцы 30 и.31,Устройство работает следующим образом.Первоначально в матричную модельграфа заносится информация о тополо-,гии моделируемого графа сети решаемыхзадач. Пои этом триггеры 2(,3 Е 1,1,1,и матричной модели графа, которые являются Формиоователями дуг,устанавливаются в единичное состояние, если есть информационная связьиз д-й вершины в 3-ю вершину. Соответствующий триггер 2определяетсяпересечением 1.-й строки и 1-го столбца, Триггеры 2;, вторая группа триггеров 9, триггер 16, группа счетчиков 5, счетчик 15, регистр 10 выбранных вершин и регистр 11 приоритетаустанавливаются в чулевое состояние.С появлением пускового сигнала повходу 20 импульсы с выхода генератора19 тактовых импульсов через открытыйпервый элемент И 18 (второи вход третьего элемента И 17 подсоединен к обратному выходу триггера 16) поступаютна вход счетчика 5 и через открытыеэлементы И 1 первой группы на входы4счетчиков 5группы, При этом импульсы не проходят через элементы И 6первой группы тех столбцов, все триггеры 2, которых находятся в нулевомсостоянии. Далее одержимое каждогосчетчика 5; группы в обратном кодепоступает на первый вход схемы 6..сравнения группы, на второй вход которой поступает ооратный код с выходасчетчика 15, а на третий - сигнал синверсного выхода первого элементаИ 18,При несовпадении показаний счетчика 5 группы и счетчика 15 в схеме6сравнения группы вырабатываетсящпульс несравнения, который далее перебрасывает в единичное состояниетриггер 7 первой группы,Высокий потенциал с выхода триггера 7, первои группы поступает на -йвход второго элемента И 1 ч и на установочные входы триггеров 2 1-й строки матричной модели 1 графа. После127 7106 4 элементы И 28 1-и группы 26, первого поразрядного узла сравнения. На выходе элементов И 28 формируются прямые коды чисел, начиная с второго этого с выхода генератора 19 тактовых импульсов на входы счетчиков 5 группы и счетчика 15 поступает очередной импульс и т.дВычислительный процесс продолжает-ся до тех пор, пока происходит сравнение в схемах 6 сравнения группы, т.е. до переброса всех триггеров 7 первой группы в единичное состояние. Это свидетельствует о том, что все О узлы моделируемого графа распределены по рангам. При этом высокий потенциал с выхода второго элемента И 14 поступает на синхронизирующий вход блока 13 поиска максимального кода, на выходы 5 23, сигнализируя о готовности устройства к выбору задачи, и вход триггера 16, который перебрасывается в единичное состояние, в результате чего прекращается подача импульсов с выхода .О генератора 19 тактовых импульсов через первый элемент И 18 на входы счетчиков 5группы и счетчика 15. Число импульсов, зафиксированноена счетчиках 5группы, соответствуетномеру ранга каждой вершины в графе(приоритету каждой задачи решаемогопакета задач в вычислительной системе).ОДалее начинается непосредственноеопределение и назначение очереднойзадачи для решения на освободившемсяпроцессоре (вычислительной машины).Для этого коды с выходов счетчиков5группы поступают через элементы 5И 8третьей группы на входы блока13 поиска максимального кода, Функционирование блока 13 поиска максимального кода начинается после появленияединичного сигнала на выходе второго 4 Оэлемента И 14 (вход 31 на фиг.2), Впервый момент анализируются старшиеразряды чисел в группе 26 поразряд-ных узлов сравнения, поступающие свыходов счетчиков 5группы. Еслихотя бы один из старших разрядов чисел (входы 30; , 3.Е 1п) равен"1", то на выходе элемента 25, ИЛИНЕ формируется "0":, который служитсигналом запрета для анализа осталь- Оных разрядов, При этом, если старшийразряд 1-го числа (1.Е(1, , п, пчисло сравниваемых кодов) равен "0",то все -е разряды не проходят черезэлементы И 28 1-и группы 26 поразрядного узла сравнения,Если старший разряд -го числа равен "1", то 1-е число проходит через по -й.Вторым элементом ИЛИ-НЕ 25 сова местно с элементом ИЛИ 27 группы 26 поразрядного узла сравнения анализируются вторые по старшинству разряды таким образом, как и старшие разряды и т,д, Позиционный код номера экспериментального числа получается путем совпадения всех сигналов запрета, сформированных в каждой -й группе 26 поразрядного узла сравнения. В результате на регистре 11 приоритета будет установлен код, содержащий набор нулей и одной или нескольких единиц, Этот код подается по выходным шинам 22 на супервизор вычислительной системы (не показан), который выбирает для реализации очередную программу, для которой в соответствующем разряде регистра 11 приоритета имеется единица. При наличии в регистре 11 приоритета одновременно нескольких единиц супервизор выбирает очередной ту программу, для которой номер разряда, содержащий единицу, наименьший.1После выбора одной из программ набора для реализации в вычислительной системе супервизор записывает в соответствующий номеру (например 16 1п) выбранной программы разряд регистра 10 выбранных вершин единицу, В результате на выходе элемента 12 И второй группы присутствует высокий потенциал, который перебрасывает триггер 9 второй группы в единичное состояние, после чего подача обратного кода с выхода счетчика 51 группы на входы блока 13 поиска максимального кода прекращается и на регистре 11 приоритета записывается другой код, по которому супервизор выбирает нереализованные программы. Работа устройства прекращается после. появления единичных сигналов на всех триггерахрегистра 10 выбранных вершин,Формула изобретения Устройство для распределения заданий процессорам, содержащее матричную модель графа размерностью п х и (где и - число вершин моделируемого гра-., фа), каждый узел которой содержит триггер, а также счетчик, блок поис 1277106ка максимального кода, регистр выбранных вершин регистр приоритета,первую группу элементов И, группусчетчиков, первую группу триггеров,вторую группу элементов И, вторуюгруппу триггеров, третью группу элементов И, генератор тактовых импульсов, выход которого соединен с первымвходом первого элемента И, первьйвыход которого подключен к первымвходам элементов И первой группы,выходы элементов И первой группы со 1 О единены соответственно с входами счетчиков группы, выход 1-го триггерапервой группы (б 1п) подключен 15к 1-му входу второго элемента Ч, выход которого соединен с входом триггера, входы регистра выбранных вершин являются группой входов устройства, выходы регистра выбранных вершин 20соединены с первыми входами соответствующих элементов И второй группь,вторые входы которых являются группойвыходов устройства и подключены квыходам регистра приоритета входыкоторого соединены с выходами блокапоиска максимального кода, инаормационные входы которого подключены квыходам элементов И третьей группы,первый вход х-го элемента И третьей .Огруппы соединен с вьгходом 1.-го триггера второй группы, вход -го триггера второй группы подключен к выходух-го элемента И второй групп ., о тл и ч а ю щ е е с я тем, что, с целью повьшения надежности за счет сокращения аппаратных затрат, в него введены Третий элемент И, группа элементов ИЛИ и группа схем сравнения, вход счетчика подключен к первому выходу первого элемента И, второй выход которого соединен со стробирующими входами схем сравнения группы, первые информационные входы которых подключены к выходу счетчика, выходы счетчиков группы соответственно соединены с вторыми информационными входами схем сравнения группы и вторыми входами элементов И третьей группы, выходы схем сравнения группы подключены к входам тригг ров первой группы, выход 1-го триггера первой группы соединен с входами триггеров ь-й строки матричной модели графа, выходы триггеров 1-го столбца матричной модели графа подключены к соответствующим входам д-го элемента ИЛИ группы, выходы элементов ИЛИ группы соединены соответственно с вторыми входами элементов И первой группы, выход триггера соединен с первым входом третьего элемента И, втсрой вход которого является входом пуска устройства, выход третьего элемента И подключен к второму входу первого элемента И , выход второго элемента И подключен к синхронизирующему входу блока поиска максимального кода и к выходу готовности ус- тройства1277106 ЛЪз л ЗОл Составитель И.ЗагорбининаТехред И.Попович Корректор М.щароши Редактор Е.Копча Заказ 6667/42 Тираж 671 ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж, Раушская наб., д. 4/5