Устройство для распределения заданий
Похожие патенты | МПК / Метки | Текст | Заявка | Код ссылки
Текст
Союз СоветскихСоциалистическихРеспублик ОРСКОМУ СВИДЕТЕЛЬСТВУ 61) Дополнительное х авт. св И. Кл.С 06 Г 9/О Заявлено 06. 02. 80 (21) 2913503/18-24 с присоединением заявхи М 3 Ьаударствавай каиитет СССР вв делам иафбретееий и вткрытнй(7) Заявитель 54 УСТРОЙСТВ АСПРЕДЕЛЕНИЯ ЗАДА% Изобретение относится к вычислительной технике, в частности к устройствам распределения заданий (задач) в вычислительной системе,Известно устройство обмена, которое содержит линейный блок, блокуправления поиском,и обменом, счетчик номера абонента, дешифратор поиска готовности, дешифратор управления обменом, регистр готовностейабонентов, сборку сигналов требова"10ний обмена, В устройстве анализируется готовность абонентов к обмену и организуется обмен выбранногоабонента с ЦВМ 1.1 Э .15Недостатками устройства являются низкое быстродействие и тот факт,что устройство,не позволяет организовать одновременный обмен с несколь -кими свободными абонентами.Цаиболее близким к предлагаемому потехнической сущности является устройство для распределения заданияпроцессорам, содержащее блок управления поиском и распределением к первому входу которого подключен выход элемента ИЛИ окончания распределения. Ко второму входу блокауправления поиском и распределением подсоединены выходы регистра готовностей процессоров, а к третьему входу - шины необходимого числапроцессоров. Первый выход блока управления подсоединен к входу, управляющему приемом кода из шин в регистр со сдвигом, второй выход подсоединен к входу, управляющему сдвигом в регистре со сдвигом. Третийвыход блока управления подсоединенк шине отказа от распределения задания. Выходы регистра со сдвигом подключены к входам элемента ИЛИ окончания распределения и к первым входам элементов И каждой из п (по числу процессоров) групп. Ко вторым входам каждой группы элементов И подключены соответствующие выходы регистра готовностей. К третьи:1 входамМежду заданиями 2 существуют информационные и управляющие связи, задаваемые матрицей смежности 2 2),О 0 О О 1 О О О 1О О О 22,2 Ра;) =Г и,) = Р1 ри распределении заданий извест 45 ным устройством вероятности правильного выполнения заданий 2 равныР) =(21)=РрР (25 )=Рр ) Ри (2)=Рр"Р)п) (2 ) Рр ) 1 (2 ) Рр )А достоверность выполнения задачи 2 равнаР(2):(-) Р (2):Р, .) д 1При распределении заданий 2 предлагаемым устройством, их выполнение пройзводится следующим образом: задание 2 выполняется на первом процессоре и одновременно на интервале Пусть для выполнения заданий 2и 2 необходимо времяа для выполнения заданий 25, 2 и 25 - время 2 с.15При существующих связях междузаданиями 22 известное устройствораспределяет их для выполнения следующим образом: задание 24 на первыйпроцессор на интервале (; ; заданиена второй процессор на интервалеС; задание 2 на первый процессорна интервале 7 + (,; задание 2 нап,п лвторой процессор на интервале (, +(.25задание 25 на третий процессор наинтервале ( + (.;Тогда, предполагая, что временной интервал (, намного больше времени распределения задания 21, получим,что достоверность выполнения заданий Р(2), характеризуемая вероятностью правильной реализации, равнаР(х) = П Р(7. 1,) 35где Р(2) - вероятность правильноговыполнения 1-го задания.Поскольку (, =(, =(, и все процессоры идентичны, а отказы в различ 40ных процессорах независимы друг отдруга, тона втором процессоре, заданиевыполняется на третьем процессогре и одновременно на интервае Г начетвертом процессоре; задание 2 выполняется на первом процессоре иодновременно на втором процессорена интервале , +(, ); задание 2 -на третьем процессоре на интервалегл и(1,+ (,); задание 2 - на четвртомпроцессоре на интервале (,+ С ),Предполагается, что выдача результатов производится через устройство выдачи, которое в смысле надежности является идеальным. В этомслучае вероятность правильной реализации каждого задания Р (2) равнаР 1) " Г (2. ) 1- (1- Р ),Р (У 1) = 1-(1- Р, ); Рй),) = Р(Х ) = РДостоверность Р(2) определяетсяследующим отношениемР) = П Р(Х 1) = Р, ( " Рр ) (-Рр1-)Тогда, выиГрыш в достоверностиравенР-Р и (и)ф = 100%Р (.)С 2 Р) (. Р ) 11 ИоПолагая Р =0,93, получаемЧ=)(2-0,93) (2-0,93 ) -,ОсЯ: =303,а при Ро =0,9Ч=. (2-0,9) (2-0,9 ) - 1100%=45%.Как показыват приведенные расчеты, разработанное устройство позволяет за счет использования естественной избыточности повысить достоверность выполнения заданий.Формула изобретения1. Устройство для распределения заданий, содержащее блок управления, регистр сдвига, первый элемент И 1 И, первую группу элементов ИЛИ, регистр готовностей, первую группу элементов И)первые входы элементов И первой группы соединены с соответствующими выходами регистра готовностей, входы которого подключены ко входам готовностей основных процессоров устройства, выходы регистра готовностей соединены со входами кода свободных процессоров блока управления, выход отказа которого подключен к выходу отказа устройства, входы кода числа необходимых процессо2. Устройство по п. 1, о т л ич а ю щ е е с я тем, что блок управления содержит два генератора одиночных импульсов, четыре триггера, первую, вторую, третью и четвертую группу элементов И, первую, вторую, третью и четвертую группу элементов задержки, первый и второй регистры, первый, второй, третий и четвертый счетчики, три схемы сравнения на больше, группу элементов сравнения на равенство, два элемента НЕ, семь элементов ИЛИ, девять элементов И, четыре элемента задержки, генератор импульсов, выход которого подключен ко второму входу седьмого элемента И и к первому входу восьмого элемента И, вы 21 90387 , ров которого соединены с информационными входами регистра сдвига и с входами кода числа необходимых процессоров блока управления, выходы регистра сдвига - со вторыми входами элементов И первой группы и с первой группой входов первого элемента ИЛИ, выход которого подключен ко входу окончания распределения блока управления, выход управления 10сдвигом которого подключен ко входу управления сдвигом регистра сдвига, входы сброса которого подключены к первым входам сброса регистра готовностей и к выходам элементов ИЛИ1 первой группы, входь 1 которых подключены к выходам соответствующих элементов И первой группы и к выходам номера основного задания устройства, третьи входы элементов И первой группы подключены ко входам кода номера задания устройства, о т л и - ч а ю щ е е с я тем, что, с целью, расиирения функциональных возможностей за счет использования естест- д венной избыточности для дублирования выполнения задания, в него введены регистр дублирования, вторая группа элементов ИЛИ, третья группа элементов ИЛИ, регистр съема, второй . элемент ИЗ И, третий элемент ИЛИ, четвертый элемент ИЛИ, дополнительный регистр сдвига, вторая группа элементов И, третья группа элементов И, выходы которых подключены к соответствующим входам элементов ИЛИ третьей группы и к соответствующим выходам номера снимаемого задания устройства, вход готовности дублирующих процессоров устройства соединен с информа-о ционным входом регистра дублирования, выходы которого соединены с первыми входами элементов И третьей группы и со входами кода процессоров, занятых дублированием блока управления, выход управления сдвигом регистра съема которого подключен ко входу управления сдвигом регистра съема, выходы которого соединены со вторыми входами элементов И третьей группы и со входами четвертого элемента ИЛИ, выход которого подключен ко входу окончания съема блока управления, выходы окончания формирования кода съема которого подключены к третьим входам элементов И третьей группы, четвертые входы которых подключены ко входам номера задания устройства, входам второго элемен 6 22та ИЛИ и к первым входам элементов И второй группы, вторые входы которых соединены с,выходами регистра готовностей, а третьи выходы - со вторыми входами второй группы входов первого элемента ИЛИ и со входами дополнительного регистра сдвига, информационные входы которого соединены с входами кода числа необходимых процессоров устройства, выходы элементов И второй группы подключены к выходам номера дублируемого задания устройства и ко входам второй группы элементов ИЛИ, выходы которых соединены со вторыми входами сброса регистра готовностей, со входами установки регистра дублирования и со входами сброса дополнительного регистра сдвига, вход управления ,приемом которого соединен с выходом управления приемом дополнительного регистра сдвига блока управления и первым входом третьего элемента ИЛИ, второй вход которого соединен с выходом управления приемом регистра сдвига, выход третьего элемента ИЛИ подключен к входу управления приемом регистра сдвига, вход управления сдвигом дополнительного регистра подключен к выходу управления сдвигом блока управления, вход номера задания которого соединен с выходом второго элемента ИЛИ, а выход последовательного ввода - со входом последовательного ввода регистра съема, входы сброса которого соединены со входами обнуления регистра дублирования, входами установки регистра готовностей и выходами третьей группы элементов ИЛИ.23 90387 ход которого соединен с выходом управления сдвигом блока и с нулевым входом третьего триггера, прямой выход которого соединен со вторым . входом девятого элемента И, первый вход которого соединен с выходом первого элемента НЕ и с нулевым входом второго триггера, прямой выход которого подключен к выходу окончания Формирования кода съема блэка 16: и к первому входу седьмого элемента И, выход которого соединен со вторым входом седьмого элемента ИЛИ, первый вход которого подключен ко входу второго элемента задержки и % .к выходу пятого элемента ИЛИ, входы которого соединены с выходами чет-, вертой группы элементов И, первый вход первого элемента И четвертойгруппы соединен с выходом второго 20 генератора одиночных импульсов исо входом первого элемента задержкичетвертой группы, выход каждого о-гоэлемента задержки четвертой группы (Я=1,2 1"1), где 1 - количество процессоров в блоке процессоров) соединен с первым входом с 1+1 элемента И четвертой группы и со входом с 1+1 элемента И задержки этой же группы, выход (-1)-го элемента задержки четвертой группы подключен ко входу первого элемента задержки, выход которого соединен с единичным входом третьего триггера и с единичным входом второго триггера, вторые входы четвертой группы элементов И подключены к выходам. группы элементов сравнения на равенство, первые входы которой соединены с выходами второго регистра, а вторые входы - с выходами первого регистра, инФормационные входы которого подключены к входам кода числа необходимых .процессоров блока управления и ко вторым входам первой группы элементов И, первый вход первого элемента. И первой группы подключен к выходу первого генератора одиночных импульсов, ко входу первого элемента задержки первой группы, ко входу первого элемента задержки второй группы и к первому входу первого .элемента И второй группы, выход каждого 1-го элемента задержки первой группы (1=1,2О, кром Я.-го, подключен к первому .входу 1,1+ 1)"го;.элемента Ипервой группы и ко входу (1+1)-го элемента задержки той же группы, выход -го элемента задержки первой группы сое 6 24динен с управляющим входом четвертого счетчика, выходы первой группы элементов И подключены ко входам первого элемента ИЛИ, выход которого соединен с входом установки четвертого счетчика, выходы которого подключены к первым входам второй схемы сравнения на больше, вторые входы которой соединены с вторыми входами третьей схемы сравнения на больше и выходами второго счетчика, вход установки которого подключен к выходу второго элемента ИЛИ, входу третьего элемента задержки, еди"ничному входу. второго регистра и вто.рому входу третьего элемента ИЛИ, входы которого подключены к выходам второй группы элементов И, первые входы этой группы соединены с входами кода числа свободных процессоров блока, выход каждого 1"го элемента задержки (=1,21"1) подключен ко входу (1+1)-го элемента задержки той же группы и ко второму входу (1+1)-го элемента И второй группы, выход( -1)-го элемента задержки второй группы соединен с первым входом первого элемента И третьей группы и с входом первого элемента задержки третьей группы, выходК-го эЛемента задержки третьей груп" пы (К=1,2, 2-1) соединен с первым входом каждого (К+1)-го элемента И третьей группы, вторые входы третьей группы элементов И подключены ко входам кода числа процессоров, занятых дублированием, а выходы - к первому входу третьего элемента ИЛИ, выход которого подключен ко входу установки третьего счетчика, выход (4/2-1)-го элемента задеркки третьей группы соединен со входом четвертого элемента задержки, выход которого соединен с единичным входом первого триггера, прямой выход которого подключен ко вторым входам первого и второго элементов И и к третьим входам третьего, четвертого, пятого и шестого элементов И, выход четвертого элемента ИЛИ подкчк ,н ко входу сброса первого, втогэгэ третьего и четвертого счетчик;в, первого, второго и третьего реги тр я и к нулевому входу первого триггера, первый вход четвертого элемента ИЛИ подключен к выходу отказа блока управления и к выходу первого элемента И, первый вход которого соединен с выходом первой25 90387 схемы сравнения на больше и с первым входом второго элемента И, выход которого соединен с первым входом третьего элемента И и первым входом четвертого элемента И, выход которого соединен со вторым входом восьмого элемента ИЛИ, выходом управления приемом дополнительного регистра сдвига блока и со вторым входом четвертого элемента ИЛИ, третий вход 10 которого подключен к выходу управления приемом регистра сдвига блока и с выходом шестого элемента ИЛИ, первый вход которого подключен к выходу пятого элемента И и входу вто рого генератора одиночных импульсов, второй вход шестого элемента ЮЯ соединен с первым входом восьмого элемента ИЛИ и с выходом шестого элемента И, первый вход которого подключен к выходу третьего элемента И, первому входу пятого элемента И и первому входу шестого элемента И, второй вход которого соединен со вторым входом пятого элемента И и 25 выходом третьей схемы сравнения на больше, первый вход которой подключен к выходу первого .счетчика и к первому входу первой схемы сравнения на больше, второй вход которой 30 соединен с выходом третьего счет 6 26чика, выход второй схемы сравнения на больше подключен ко второму входу третьего элемента И и второму входу четвертого элемента И, выход второго элемента задержки соединен с выходом последовательного ввода блока, вход первого элемента НЕ подключен ко входу окончания съема блока, вход второго элемента НЕ подключен ко входу окончания распреде-ления блока, а выход - к нулевому входу четвертого триггера, единичный вход которого соединен с выходом восьмого элемента ИЛИ, третий вход которого соединен с выходом девятого элемента И, прямой выход четвертого триггера соединен со вторым входом восьмого элемента И, выход седьмого элемента ИЛИ подключен к выходу управления сдвигом блока, вход первого генератора одиночных импульсов соединен с входом номера задания блока. Источники информации,принятые во внимание при экспертиэе1Авторское свидетельство СССРВ 468240, кл. 6 06 Г 9/00, 973.2. Авторское свидетельство СССРР 629538, кл. 6 06 Г 9/00, 978903876 Составитель П.ЧистобородовРедактор АД 1 ишкина ТехредМ. Надь орректорГ.Назаро Заказ 123/31ВНИИ 1 писное 4/ филиал 1 ПП 1 " Патент", г. Ужгород, ул. Проектная, 4 Тираж 731 1 И Государственного по делам изобретений 13035, Иосква, Ж, Ромитета ССС открытийушская наб.,.элементов И 5 подключены шины номера задания (задачи), К выходам каждой группы элементов И подключены входы соответствующих элементов ИЛИ, выходы которых подсоединены5 к нулевым входам соответствующих триггеров регистра со сдвигом и регистра готовностей. К входам процессоров подключены выходы соответствующих групп элементов И, а выходы про- О цессоров 7 подсоединены к единичным входам триггеров регистра готов" ностей 23.Недостатком устройства является невозможность использования естественной избыточности для дублированного выполнения заданий.Цель изобретения - расширение функциональных возможностей за счет использования естественной избыточности для дублирования выполнения заданий. Поставленная цель достигается .тем, что в устройство для распределения заданий, содержащее блок управления, регистр сдвига, первый элемент ИЛИ, первую группу элементов ИЛИ, регистр готовностей, первую группу элементов И, первые входы элеменЗО тов И первой группы соединены с соответствующими выходами регистра готонностей, входы которого подключены ко входам готовностей основных процессоров устройства, выходы регистра готовностей соединены со входами кода свободных процессоров блока управления, выход отказа которого подключен к выходу отказа устройства, входы коца числа необходимых прои40 цессоров Которого соединены с информд- О ционными входами регистра сдвига и с входами кода числа необходимых процессоров блока управления, выходы регистра сдвига, - со вторыми входами элементов И первой группы и с первой группой входов первого элемента ИЛИ, выход которого подключен ко входу окончания распределения блока управления, выход управления сдвигом которого подключен ко входу управления сдвигом регистра сдвига, входы сброса которого подключены к первым входам сброса регистра готов. ностей и.к выходам элементов ИЛИ первой группы, входы которых поцключены к .выходам соответствующих элементов И первой группы и к выходам номера основного задания устройства 4третьи входы элементов И первой группы подключены ко входам кода номера задания устройства, введены регистр дублирования, вторая группа элементов ИЛИ, третья группа элементов ИЛИ регистр съема, второй элемент ИЛИ, третий элемент ИЛИ, четвертый элемент ИЛИ, дополнительный регистр сдвига, вторая группа элементов И, третья группа элементов И выходы которых подключены к соответствующим входам элементов ИЛИ третьей группы и к соответствующим выходам номера снимаемого задания устройства, вход готовности дублирующих процессоров .устройства соединен с информационным входом регистра дублирования, выходы которого соединены с первыми входами элементов И третьей группы и со входами кода процессоров, занятых цублированием блока управления, выход управления сдвигом регистра съема которого подключен ко входу управления сдвигом регистра съема, выходы которого соединены со вторыми входами элементов И третьей группы и со входами четвертого элемента ИЛИ, выход которого подключен ко входу окончания съема блока управления, выходы окончания формирования кода съема которого подключены к третьим входам элементов И третьей группы, четвертые входы которых подключены ко входам номера задания устройства, входам второго элемента ИЛИ и к первым входам элементов И второй группы, вторые входы которых соединены с выходами регистра готовностей, а третьи выходы - со вторыми входами второй группы входов первого элемента ИЛИ и со входами дополнительного регистра сдвига, информационные входы которого соединены с входами кода числа необходимых процессоров устройства, выходы элементов И второи группы подключены к выходам номера дублируемого задания устройства и ко входам второй группы элементов ИЛИ, выходы которых, соединены со вторыми в",;:;.,ами сброса регистра готовност й. со входами установки регистра т.".лоования и со входами сброса дополнительного регистра сдвига, вход управления приемом которого соединен с выходом управления приемом дополнительного регистра сдвига блока управления и первым входом третьего элемента ИЛИ, второй входкоторого соединен с выходом управления приемом регистра сдвига, выход третьего элемента ИЛИ подключенко входу управления приемом регистра сдвига, вход управления сдвигом дополнительного регистра сдвигаподключен к выходу управления сдвигом блока управления, вход номеразадания которого соединен с выходом второго элемента ИЛИ, а выходпоследовательного ввода - со входомпоследовательного ввода регистрасъема, входы сброса которого соединены со входами обнуления регистрадублирования, входами установки регистра готовностей и выходами тре.тьей группы элементов ИЛИ. Кроме того, блок управления содержит два генератора одиночных импульсов, четыре триггера, первую, вторую, третью и четвертую группу элементов И, первую, вторую, третью и четвертую группу элементов задержки, первый и второй регистры, первый, второй, третий и четвертый счетчики, три схемы сравнения на больше, группу элементов сравнения на равенство, два элемента НЕ, семь элементов ЮМ, девять элементов И, четыре элемента задержки, генератор импульсов, выход которого подключен ко второму входу седьмого элемента И и к первому входу восьмого элемента И, выход которого соединен с выходом управления сдвигом блока и с нулевым входом третьего триггера, прямой выход которого соединен со вторым входом девятого элемента И, первый вход которого соединен с выходом первого элемента НЕ и с нулевым входом второго триггера, прямой выход которого подключен к выходу окончания формирования кода съема блока и к пер- . вому входу седьмого. элемента И, выход которого соединен со вторым входом седьмого элемента ИЛИ, первый вход которого подключен ко входу второго элемента задержки и к выходу пятого элемента ИЛИ, входы которого соединены с выходами четвертой группы элементов И, первый вход первого элемента И четвертой группы соединен с выходом второго генератора одиночных импульсов и входом первого элемента задержки четвертой группы, выход каждого с-го элемента задержки четвертой группы (с=1,2 6"1, где- количество процессоров1 О 15 вого элемента И первой группы подключен к выходу первого генератора одиночных импульсов, ко входу первого элемента задержки первой группы, ко входу первого элемента задержки второй группы и к первомувходу первого элемента И второй группы, выход каждого 1-го элемента задержки первой группы (1=1,2 кроме 1-го, подключен к первому входу (1+1)"го элемента И первой группы и ко входу (1+1)-го элемента задержки той же группы, выход,1,-го элемента задержки первой группы соединен с управляющим входом четвертого счетчика, выходы первой группы элементов И под. ключены ко входам первого элемента ИЛИ, выход которого соединен со входом установки четвертого счетчика, выходы которого подключены к первым входам второй схемы сравнения на больше, вторые входы которой соединены со вторыми входами третьей схемь 1 сравнения на больше и выходами второго счетчика, вход установки - которого подключен к выходу второго элемента ИЛИ, входу третьего элемента задержки, единичному входу второго регистра и второму входу третьего элемента ИЛИ, входы которого подключены к выходам второй группы элементов И, первые входы этой группы соединены с входами кода числа свободных процессоров блока, выход каждого 1-го элемента задержки второй группы (1=1,21-1) подключен ко входу (+1)-го элемента задержки той же группы и ко второму входу (+1)-го элемента И второй 25 ЭО 35 40 45 50 55 в блоке процессоров) соединен с первым входом ц+ элемента задержки этой же группы и с первым входом ц+1 элемента И четвертой группы, . выход (-1)-го элемента задержки четвертой группы подключен ко входу первого элемента задержки, выход,которого соединен с единичным входом третьего триггера и единичным входомвторого триггера, вторые входы четвертой группы элементов И подключены к выходам группы элементов сравнения на равенство, первые входы которой соединены с выходами второго регистра, а вторые входы - с выходами первого регистра, инФормационные входы которого подключены к входам кода числа необходимых процессоров блока управленияи ко вторым входам первой группы элементов И, первый вход пер03876 8 5 О 55 7 9 группы, выход (-1)-го элемента за" держки второй группы соединен с первым входом первого элемента И третьей группы и с входом первого элемента задержки третьей группы, выход каждого К;го элемента задержки третьей группы (К=1,21/2-1) соединен с первым входом каждого (К+1)-го элемента И третьей группы, вторые входы третьей группы элементов И подключены ко входам кода числа процессоров,.занятых дублированием, а выходы - к первому входу третьего элемента ИЛИ, выход которого подключен ко вхоцу установки третьеГо счетчика выход (Р 2"1) -го элемента задержки третьей группы соединен со входом четвертого элемента задержки, выход которого соединен с единичным входом первого триггера, прямой выход которого подключен ко вторым входам первого и второго элементов И и к третьим входам третьего, четвертого, пятого и шестого элементов И, выход четвертого элемента ИЛИ подключен ко входу сброса первого, второго, третьего и четвертого счетчиков, первого, второго и третьего регистров и к нулевому входу первого триггера, первый вход четвертого элемента ИЛИ под" ключен к выходу отказа блока управления и к выходу первого элемента И, первый вход которого соединен с выходом первой схемы сравнения на больше и с первым входом второго элемента И, выход которого соединен с первым входом третьего элемента И и первым входом четвертого элемента И, выход которого соединен со вторым входом. восьмого элемента ИЛИ, выходом управления приемом дополнительного регистра сдвига блока и со вторым входом четвертого элемента ИЛИ, третий вход которого подключен к выходу управления приемом регистра сдвига блока и с выходом шестого элемента И 1 П 1, первый вход которого подключен к выходу пятого элемента И и входу второго генератора одиночных импульсов, второй вход шестого элемента ИЛИ соединен с первым входом восьмого элемента ИЛИ и с выходом шестого элемента И, первый вход которого .подключен к выходу третьего элемента И, первому входу пятогоФэлемента И и первому входу шестого элемента И, второй вход которого соецинен со вторым входом пятого элемента И и выходом третьей схемы сравнения на больше, первый вход кото- н рои подключен к выходу первого счетчика и к первому входу первой схе мы сравнения на больше, второй вход которой соединен с выходом третьего счетчика, выход второй схемы сравнения на больше подключен ко второму входу третьего элемента И и второму1 О входу четвертого элемента И, выходвторого, элемента задержки соединенс выходом последовательного ввода блока, вход первого элемента НЕ подключен ко входу окончания съема бло 1 ка, вход второго элемента НЕ подключен ко входу окончания распределения блока, а выход - к нулевомувходу четвертого триггера, единич- н ныи вход которого соединен с выходом восьмого элемента ИЛИ, третий входкоторого соединен с выходом девятого элемента И, прямой выход четвертого триггера соединен со вторым вхохом восьмого элемента И, выход седьмого элемента ИЛИ подключен к выходу управления сдвигом блока, вход первого генератора одиночных импульсов соединен с входом номера задания блока.На фиг. 1 и 2 приведена структурная схема устройства. Устройство содержит блок 1 управления, регистр 2 готовностей, первый элемент ИЗБ 3 окончания распределения, регистр 4 сдвига, первую, вторую и третью группы элементов И 5, первую, вторую и третью группы элементов ИЛИ 6, процессоры 7, шины 8 необходимого числа процессо, ров, шины 9 номера задания, шину10 отказа, регистр 11 съема, ре" гистр 12 сдвига, регистр 13 дублирования, элементИЛИ 14 запуска, третий элемент ИЛИ 15 приема, четвер 4 тый элемент ИЛИ 16 окончания съема, ,счетчики 17-19, регистры 20 и 21,счетчик 22 с цепями сдвига, схемы23 сравнения на больше, группуодноразрядных схем 24 сравнения наравенство, триггеры 25-28, первую,вторую и третью группы элементовИ 29-31, элементы И 32-37, четвертую груйпу элементов И 38, элементы И 39 и 40, элементы ИЛИ 41-48, первый и второй элементы НЕ 49 , первую, вторую и третью группы элементов 50-52 задержки, элементы 53 и 54 задержки, четвертую группу элементов 55 задержки, элементы 56 и57 задержки, первый и второй генераторы.58 одиночных импульсов, генератор 59 импульсов, первый ЬО, второй 61 выходы блока 1 управления, первый 62 вход блока 1 управления, 5 третий 63, четвертый 64 выходы блокауправления, второй 65, третий 66, четвертый 67, пятый 68 входы блока ,1 управления, пятый 69, шестой 70, ,седьмой 71 выходы блока 1 управления 10 шестые 72 входы блока 1 управления,Предлагаемое устройство работает следующим образом. По шинам 9 номера задания код номера задания поступает на входы элемента ИЛИ 14 запуска, на выходе которого формируется сигнал, управляющий запуском первого генератора 58 одиночных импульсов, Одновременно по шинам 8 необходимого числа процессоров код необходимого для выполнения задания числа процессоров поступает на вторые входы группы элементов И 29 и на,единичные входы у 5 .регистра 20. Код количества свободных процессоров с регистра 2 готовностей поступает на вторые входы второй группы элементов И 30, а код количества процессоров занятых дублированием с регистра 13 дублирова" ния - на вторые входы элементов И 31. Импульс с выхода генератора 58, задержанный в первой группе элементов 50 задержки, разрешает последовательное прохождение единиц кода необходимого числа процессоров через элементы И 29, Каждая единица с вйхода соответствующих элементов И 29 третьей группы поступает через элемент ИЛИ 41 на вход счетчика 17 и на вход счетчика 22. В результате опроса импульсом с выхода генератора 581 всех элементов И 29 в счетчике 17 формируется двоичный код необходимого числа процессоров (и), в регистре 20 - принятый однопозиционный код необходимого числа процессоров, представляющий собой совокупность единиц последовательно расположенных в младших разрядах регистра 20, а в счетчике 22 с цепями сдвига - двоичный код.удвоенного необходимого числа процессоров (2 и). Удвоение количе 55 ства необходимого числа процессоров получается в результате сдвига содержимого счетчика 22 на один разряд влево по импульсу, поступающему с последнего элемента 50 задержкина сдвигающий вход счетчика 22.Импульс с выхода 1 генератора 58одиночных импульсов, задержанный на.элементах 51 задержки, также разрешает последовательное прохождениеединиц кода количества свободныхпроцессоров через группу элементовИ 30. Каждая единица с выхода соответствующей группы элементов И 30поступает через элемент ИЛИ 42 навход счетчика 18 и на вход, управляющий сдвигом регистра 21, производя сдвиг вправо содержимого регистра, что обеспечивает освобождение старшего разряда для приема очередной единицы кода количества свободных процессоров через элемент54 задержки,Кроме того, каждаяединица проходит через элемент ИЛИ 43 на входсчетчика 19. В результате этого всчетчиках 18 и 9 формируется двоичныйкод количества свободных процессоров (пс), а в регистре 2 - однопозиционный код, представляющий собойсовокупность единиц, количество которых равно количеству свободных про"цессоров.Импульс с выхода последнего элемента 51 задержки группы, задержанныйна элементах 52 задержки, группы разрешает последовательное прохождениеединиц кода количества процессоров,занятых дублированием, через элементы И 31.группы. Каждая единица с выхода соответствующего элемента И 3группы поступает через элемент ИЛИ 43на вход счетчика 19, формируя тем самым двоичный код суммы количествасвободных процессоров и количествопроцессоров, зайятых дублированием(п,+п) . Сигнал с выхода последнего элемента 52 задержки задерживается на элементе 53 задержки. Время задержки выбирается таким, чтобы импульс с выхода элемента 53 задержки переключал триггер 25 в единичное состояние только после того, когда на счетчиках 17-19, регистрах 20 и 21, счетчике 22 закончится процесс формирования кодов. Двоичный код необходимого числа процессоров, полученный на счетчике 17, поступает на первый вход первой схемы 231 сравнения на больше и наио 11 9 первый вход третьей схемы 23 сравне ния на больше. Двоичный код удвоен.ного необходимого числа процессоров, полученный на счетчике 22, поступает на первый вход второй схемы 23 сравнения на больше. Двоичный код количества свободных процессоров, полученный на счетчике 18, поступает на вторые входы второй и третьей схем 23 сравнения на больше. Двоичный код суммы количества свободных процессоров и количества процессоров, занятых дублированием, полу" ченный на счетчике 19, поступает на второй вход первой схемы 23 срав 1 нения на больше, Таким образом, первая схема 234 сравнения на боль-, ше, реализует неравенство 1 1"+ 1"И) вторая схема 23 сравнения на больше - неравенствои третья - неравенство тИ Р)Если количество процессоров, необходимых для выполнения задания (пи)больше суммы количеств свободных процессоров и процессоров, занятых дублированием (п+п), т.е, выполняется неравенство ( 1), то навыходе первой схемы 23 сравнения на больше Формируется единичный сигнал. Этот сигнал поступает на первый вход элемента И 32, на второй вход которого поступает единичный сигнал с триггера 25. В результате на выходе элемента И 32 появляется единичный потенциал, который поступает в шину 1 О отказа в качестве сигнала отказа от выполнения задания. Кроме того, этим. сигналом через элемент ИЛИ 44 производится обнуление счетчиков 17-19,и 22, регистров 20 и 21 и триггер 25 переключается в нулевое состояние, Вместе с тем, при выполнении неравенства (1), на выходе элемента И 33 Формируется нулевой сигнал, который ,блокирует выходы второй и третьей схем 23. сравнения на больше,Если неравенство (1) не выполняется, то на выходе элемента И 33Фпоявляется единичный потенциал, который разрешает прохождение сигнала с выхода второй схемы 23 срав 03876 12нения на больше через элементы И 34и 35, Тогда, если удвоенное количество процессоров (2 п), необходимых для выполнения, больше или, по"крайней мере, равно количеству свободных процессоров (и ), т.е. неравенство ( 2) не выполняется, то навыходе второи схемы 23 сравнения набольше единичный сигнал не появляется. Следовательно, нулевой сигналс выхода элемента И 34 блокируетвыход третьей схемы 235 сравнения,а на выходе элемента И 35 с появлением единичного потенциала с триггера 25 Формируется единичный сигнал,который через элемент ИЛИ 44 обнуляет счетчики 17-19.и 22, регистры 20 и 21 и переключает в нулевоесостояние триггер 25, Кроме того,этот сигнал поступает на вход, управляющий приемом в регистр 12 со сдвигом, и через элемент ИЛИ 15 приемана вход, управляющий приемом в ре.- гистр 4 сдвига, обеспечивая приемкода необходимого числа процессоровв регистры 12 и 4 сдвига.В случае совпадения единиц в разрядах регистра 4 сдвига и регистра2 готовностей соответствующие группы элементов И 5 разрешают прохождение кода номера задания, поступающего по шинам 9 номера задания, навход соответствующих процессоровдля выполнения, При появлении коданомера задания на выходах групп элементов И 5 появляютея сигналы на выходах соответствующих групп элементов ИЛИ 6, которые обнуляют соответствующие триггеры регистра 4 сдвигаи регистра 2 готовностей.Одновременно с этим, в случае совпадения единиц в разрядах регистра12 сдвига и регистра 2 готовностей,соответствующие группы элементов И 5 45 разрешают прохождение кода номеразадания на вход соответствующих процессоров для дублированного выпопкения. При появлении кода номера задания на выходах групп элементов 50И 5, появляются сигналы на выходахсоответствующих элементов ИЛИ 6,которые обнуляют соответствующиетриггеры регистра 12 сдвига, регистра 2 готовностей и переключают в единичное состояние соответствующие 55тоиггеры регистра 13 дублирования.К этому времени сигнал с выходаэлемента И 35, проходя через элемент ИЛИ 48, устанавливает в единич"14 45 55 13 9038 ное состояние триггер 27. Если количество триггеров регистров 4 и 12 сдвига, оставшихся в единичном состоянии, отлично от нуля, то на выходе элемента ИЗИ 3 окончания распре деления формируется единичный сигнал, который через второй элемент НЕ 49 проходит на нулевой вход триггера 27, не меняя его состояния. Потенциал с единичного выхода тригге- О ра 27 разрешает прохождение импульсов, формируемых генератором 59 импульсов через соответствующий элемент И 39 на входы, управляющие сдвигом, регистров 4 и 12 сдвига где происхо дит сдвиг кода необходимого числа процессоров; в регистре 4 сдвига в сторону возрастания номеров процессоров, а в регистре 12 сдвига- в сторону убывания этих номеров. При 20 совпадении единиц в соответствующих разрядах регистров 4 и 2 сдвига и регистра 2 готовностей происходит выцача кода номера задания через группу элементов И 5 на входы соот ветствующих процессоров для выполНения и дублирования, обнуление соОтветствующих триггеров регистров 4 и 12 сдвига, регистра 2 готовностей и г 1 ереключение в единичное состоя- ЗО ние соответствующих триггеров регистра 13 дублирования.Если все триггера регистров 4 и 12 сдвига обнулены, то на выходе элемента ИЗИ 3 окончания распределения появляется нулевой потенциал, который через второй элемент НЕ 49 поступает на нулевой вход триггера 27, переключая его в нулевое состояние. На единичном выходе триггера 40 формируется нулевой сигнал, который запрещает прохождение импульсов с выхода генератора 59 импульсов через олемент И 39. Если удвоенное количество йроцессоров, необходимых для выполнения задания (2 и), меньше количества свободных процессоров (и ), т,е, выполняется неравенство ( 2), то на выходе второй схемы 23 сравнения на больше формируется единичный сигнал, Этот сигнал поступает на второй вход элемента И 34, на первый вход которого поступает единичный потенциал с выхода элемента И 33, а на третий вход - единичный сигнал с триггера 25. В результате на выходе элемента И 34 появляется единичный потенциал, который разрешает прохождение сигнала с выхода третьей схемы 23 сравне 3 ния на больше через элементы И 36 и 37Тогда, если количество свободных процессоров (и ) больше или, по крайней мере, равно количеству процессоров, необходимых для выполнения задания (п), т,е. неравенство (31 не выполняется, то на выходе третьей схемы 235 сравнения на больше единичный сигнал не появ" ляется. Следовательно, на выходе элемента И 36 будет нулевой сигнал, а на выходе элемента И 37 с приходом единичного потенциала с триггера .25 появляется единичный сигнал, который через элементы ИЛИ 45 и 44 обнуляет счетчики 17-19 и 22, регистры 20 и 21 и переключает в нулевое состояние триггер 25. Кроме того, этот сигнал через элементы ИЗИ 45 и 5 поступает на вход, управляющий приемом в регистр 4 сдвига, обеспечивая прием кода необходимого числа процессоров в этот регистр.В случае совпадения единиц в разрядах регистра 4 сдвига и регистра 2 готовностей соответствующие группы элементов И 5 разрешают прохождение кода номера задания, поступающего по нинам 9 номера задания, на входы соответствующих процессоров для выполнения, При появлении кода номера задания на выходах групп элементов И 5, появляются сигналы на выходах соответствующих групп элементов ИЗБ 6, которые обнуляют соответствующие триггеры регистра 4 сдвига и регистра 2 готовностей. К этому времени сигнал с выхода элемента И 37, проходя через элемент ИЛИ 4 д, устанавливает в единичное состояние триггер 27. Если количество триггеров регистра 4 сдвига, оставшихся в единичном состоянии, отлично от нуля, на выходе элемента ИЗ 1 И 3 окончания распределения формируется единичный сигнал, которыи через второй элемент НЕ 49 проходит на нулевой вход триггера 27, не меняя его состояния, Потенциал с единичного выхода триггера 27 разрешает прохождение импульсов, формируемых генератором 59 импульсов на вход, управляющий сдвигом, регистра 4 сдвига, где происходит сдвиг кода необходимого числа процессоровОдновременно однопозиционный код количества свободных процессоров, находящийся в регистре 21, поступает на первые входы одноразрядных схем 24 сравнения на равенством на вторые выходы. которых поступают соответствующие разряды однопозиционного кода количества процессоров, необходимых для выполнения задания,Фнаходящегося в регистре 20, Если на входы одноразрядной схемы сравнения на равенство поданы одинаковые сигкалы (оба нули или оба единицы), тона выходе схемы появляется нулевой потенциал, если на входе присутствуют разные сигналы, то на выходе формируется единичный потенциал, Такимобразом, на выходах группы однораз" рядных схем 24 сравнения на равенство образуется однопозиционный код, представляющий собой совокупностьединиц количество которых равно разности между количеством процессоров, необходимых для выполнения задания, и количеством свободных процессоров (и-п) .Импульс с. выхода второго генера-тора 58, задержанный в группе элементов 55 задержки, разрешает последовательное прохождение единиц кода разности (и-пс) через группуэлементов И 38. Каждая единица с выхода соответствующей группы элементов И 38 поступает через элементы ИЛИ 46 и 47 на вход, управляющий сдвигом регистра 11 съема, производя сдвиг вправо содержимого регистра, что обеспечивает освобождениестаршего разряда для приема очередной единицы кода разности (и-и )через элемент 57 задержки. Сигналс выхода последнего элемента 55 за" держки группы задерживается на элементе 56 задержки ( время задержки выбирается таким, чтобы импульс с выхода элемента 56 задержки переключал триггера 26 и 28 в единичное состояние только после того, когда на регистре 11 съема закончится процесс формирования кода).40В случае совпадения единиц в разрядах регистра 1 съема и регистра 13 дублирования, при появлении единичного потенциала с триггера 26, соответствующие группы элементов И 5 45разрешают прохождение кода номера задания, поступающего по шинам номера задания, на вход соответствующих процессоров для их освобождения от дублирования, При появлении кода номера задания на выходах групп элементов И 5, появляются сигналы на входах соответствующих групп элементов ИЛИ б, которые обнуляют соответствующие триггеры регистра 13 дублирования и регистра 11 съема и переключают в единичное состояние соответствующие триггеры регистра 2 готовностей.В случае совпадения разрядов регистра 4 сдвйга и регистра готовностей 2 группы элементов И Ъ разрешают прохождение кода номера задания на входы соответствующих процессоров. При появлении кода номера задания на выходах . групп элементов И 5, появляется сигнал на выходах элементов И 31 И 6, которые обнуляют триггеры регистра 4 сдвига и ре 50 Если количество триггеров регист" ра 11 съема, оставшихся в единичном состоянии, отлично от нуля, то на выходе элемента И 31 И 16 окончания съема Формируется единичный сигнап, который через первый инвертор прохо" дит на нулевой вход триггера 27, не меняя его состояния. Потенциал с единичного выхода триггера 26 разрешает прохождение импульсов, Формио руемых генератором 59 импульсов, через соответствующий элемент И 39 и элемент И 31 И 47, на вход, управля" , ющий сдвигом регистра 11 съема, где происходит сдвиг кода разности (п" п,) в сторону убывания номеров процессоров. При совпадении единиц в соответствующих разрядах регистра11 съема и регистра 13 дублирования происходит выдача кода номера за О дания через группу элементов И 5 на входы соответствующих процессоров для их освобождения от дублированного выполнения заданий, обнуление соответствующих триггеров регистрасъема и регистра 13 дублирования и переключение в единичное состояние соответствующих триггеров регистра 2 готовностей.Если все триггера регистра 1 съе-Зо ма обнулены, то на выходе элемента И 31 И 16 окончания съема появляетсянулевой потенциал, который через первый элемент НЕ 49 поступает на нулевой вход триггера 26, переключая З 5 его в нулевое состояние, На единичном выходе триггера Формируется нулевой сигнал, который запрещает прохождение импульсов с выхода генератора 59 импульсов через соответствующий элемент И 39. Одновременно с этим единичный сигнал с выхода первого элемента НЕ 49 проходит через элемент И 40, на второй вход которо" го подается единичный потенциал с выхода триггера 28, и элемент И 31 И 48, устанавливая триггер 27 в единичное состояние. гистра готовностей. Если количест" во триггеров регистра 4 сдвига, .оставшихся в единичном состоянии, отлично от нуля, на выходе элемента ИЛИ 3 окончания распределения Формируется единичный сигнал, который через второй элемент НЕ 49 проходит на нулевой вход триггера 27, не меняя его состояния, Потенциал с единичного выхода триггера 27 разрешает прохождение импульсов, Формируемых генератором 59 импульсов, на вход, управляющий сдвигом регистра 4 сдвига, где происходит сдвиг кода необходимого числа процессо" ров в сторону возрастания номеров процессоров.При совпадении разрядов регистра 4 сдвига и регистра 2 готовностей происходит выдача кода номера задания через группу элементов И 5 на входы процессоров и обнуление разрядов регистра 4 сдвига и регистра 2 готовностей. Если все триггеры регистра 4 сдвига обнулены, то на выходе элемента ИЛИ 3 окончания распределения появляется нулевой потенциал, который через второй элемент НЕ 49 поступает на нулевой вход триггера 27, переключая его в нулевое состояние, На единичном выходе триггера формируется сигнал, который запрещает прохождение импульсов с выхода генератора 59 импульсов через элемент И 39.Таким образом, предлагаемое устройство позволяет повысить достоверность выполнения задач за счет использования естественной избыточности для дублированного выполнения заданий.Пусть в многопроцессорную вычис" лительную систему, содержащую четыре идентичных процессора, поступает на обработку задача 2, сводящая к выполнению заданий=03Каждый процессор может быть использован для выполнения любогозадания 2,.и вся совокупность эададаний 2 6 2 выполняется за время Т3 зТ , 61,с,к где Ь - -ыи временнои интервал
СмотретьЗаявка
2913503, 06.02.1980
ВОЕННАЯ ИНЖЕНЕРНАЯ РАДИОТЕХНИЧЕСКАЯ ОРДЕНОВ ОКТЯБРЬСКОЙ РЕВОЛЮЦИИ И ОТЕЧЕСТВЕННОЙ ВОЙНЫ АКАДЕМИЯ ПРОТИВОВОЗДУШНОЙ ОБОРОНЫ ИМ. МАРШАЛА СОВЕТСКОГО СОЮЗА ГОВОРОВА Л. А
ГАНИТУЛИН АНАТОЛИЙ ХАТЫНОВИЧ, ШМАТКОВ СЕРГЕЙ ИГОРЕВИЧ
МПК / Метки
МПК: G06F 9/00
Метки: заданий, распределения
Опубликовано: 07.02.1982
Код ссылки
<a href="https://patents.su/15-903876-ustrojjstvo-dlya-raspredeleniya-zadanijj.html" target="_blank" rel="follow" title="База патентов СССР">Устройство для распределения заданий</a>
Предыдущий патент: Цифровой интегратор
Следующий патент: Устройство микропрограммного управления
Случайный патент: Способ получения калийных удобрений