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

(54) УСТРОЙСТВО ДЛЯ РАСПгеДЕЛЕНИЯ ЗАДАНИЙ ПРОЦЕССОРАМ

I

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

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

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

to

Недостатком известных устройств является низкая надежность.

Цель изобретения - повышение надезк ности.

Указанная цель достигается тем, что

15 в устройство для распредшения заданяй процессорам, содержащее матричную модель сетпа, бпсж управления, первый выход которого подключен к управляющему входу шифратора, выходы которого сое20дивевы с входами регистра прторягегга, Екоды которого являются выходами уст|ройства и подключены к первым входам элемекгов И первой группы, вторые вхо- ды которых соединены с выходами регистра выбршаак вершин, входы которого являются входами устройства, выходы элементов И первой группы соединены с входами триггеров первой грутты, выходы кстгорых подключены к первым,выходам элементов И второй группы, выходы которых соединены с. информавзионными входами шифратора, первую грутшу счетчиков и третью группу элементов И, ВЫХОДЫ которых подключены к ккодам mtJ(r/ ErrVI 4V tT4 ТТ rfTfVrtf lff irr т rf .r - л« . счетчиков первой группы, выходы которых соединены с вторыми входами элеме ггов И второй груцпы, ЕЙЬедены вторая группа триггеров, вторая группа счетчиков, четвертая группа элементов И и группа элементов , входы которых соединены соответственно с выходами матричной модели-сети, выходы элементов ИЛИ-НЕ группы подключены к первым входам элементов И четвертой группы, вторые входы которых соединены с первыми входами элементов И третьей группы и подключены к второму выходу блока управления, выходы элементов И четвертой группы подключены к входам счетчиков второй группы, выходы которых соед1шены с входами матричной модели сети и с входами трштеров второй группы, выходы которых подключены к вторым входам элементов И тр:етьей группы и к входам блока управления. На чертеже показана структурная схема устройства дпя распределения заданий процессорам. Устройство содержит матричную модел 1 сети в составе триггеров 2, по числу строк матрицы группу элементов ИЛИ-НЕ 3, по числу столбцов матрицы четверпгую группу элементов И 4, взюрую группу счетчиков 5, вторую группу триггеров 6 третью группу элементов И 7, первую группу счетчиков 8, первую рруппу триггеров 9, вторую группу элементов И Ю регистр 11 выбранных вершин, регистр 12 приоритета, первую ipyjuiy элементов И 13, а также шифратор 14, генератор 15 тактовых импульсов, первый элемент И 16, схему 17 начального пуска, второй элемент И 18, дополнительный триггер 19, пусковой вход 20 устройства, информационные входы 21 устройства и выход 22 устройства. Блок 23 управления вкгаочает генератор 15, элементы И 16 и 18, схему 17 начального пуска, триг гер 19, входь 20 к 21 Vi выход 22. Устройство работает следующим образом. Первоначально в модель 1 заносится информация о топологии моделируемого гра. При этом триггеры (ij, 1;и ), которые являются формирова- тепятуш дуг; устанавливаются в едтогчное состошше, если есть информационная связь из 1 -ой вершины в j -ю вершину. Соответствукшшй триггер отгределлется пересечением -(-ой строки и -/ -го столбца. Другие триггеры 2.-; , а также трштеры 6, 9 и 19, счетчики 8 находят:-. .. . -4 ся в нулевом состоянии. В счетчики 5 соответствук1ших вершин графа заносятся . числа импульсов, дополняющие веса BejmmH до полной емкости счетчиков, После занесения исходной информации ка входах элементов ИЛИ-НЕ 3, объединяющих выходы триггеров 2 в строках, coc-i-ветствующим конечным вершинам графа, будут высокие потенциалы. Это объясняется тем, что в однонаправленном графе без циклов и петель конечные вершины не содержат выходящих ветвей, а следовательно, все триггеры 2 в этой строке будут в нулевом сосггоянии. Первоначально в устройстве происхощсг определение величзш максимальных путей из данной вершины до конечной вершины графа, описьшающего набор информашюнно-связанных задач. При этом с появлением пускового сигнала на входе 20 схемы 17 начального пуска импульсы с выхода генератора 15 поступают на входы элементов И 4 и 7, а далее на все счетчики 8, так как в исходном состоянии все триггеры 6 находятся в нулевом состоянии, а управляемые входы элементов И 7 подключены к нулевым выходам триггеров 6. Кроме того, счетные импульсы поступают через элементы И 4 на те счетчики 5, для которых трш геры 2 одноименной строки матрицы находятся в нулевом состоянии. Поэтому на выходе соответствуюншх элементов ИЛИ-НЕ 3 появляется высокий потенциал, благодаря чему на управляемом -входе одноименного элемента И 4 будет высокий потенциал. Отсчитав число импульсов, nponof даональное весу модегафуемой вершины, счетчик 5 переполняется, устанавливает в единичное состояние соответствук щий триггер 6, а все триггеры 2 в данном столбце матричной модели - в нулевое состо5шие. Переброс триггера 6 в единичное состояние обеспечивает пр&крашение подачи счетных импульсов через элемент И 7 па вход регистрирующего счетчика 8, на котором фвшсяруется код максимального пути вз данной вершины до конечной вераюшы графа информационно-связанного набора задач. Вычислительный щюцесс продолжается до тех пор, пока на выходах всех триггеров 6 не будут присутствовать низкие потенциалы. На выходе элемента ИЛИ 18 будет низкий потенциал, в результат чего прекращается подача счетных импул сов с выхода генератора 15 череэ элемент 16 совпадения на информационные входы элементов И 4 и 7. С выхода триггера 19 высокий потенциал подается и на управляемый вход пш4ратора 14, который обеспечивает noявление высокого потенциала на одном или нескозгьких из И своих выходов, коTojJbie соответствуют максимальному коду, хран5пцемуся на одноименном счетчв ке 8. На вход шифратора 14 коды со счетчиков 8 подаются через элементы И 10, на управляемые входы которых подается высокий потенциал с нулевых выходов триггеров 9. В результате на регистре 12 устанавливается код, содержащий набор нулей и одвоа или несколько единиц. Этот код подается через выходные шины 22 на супервизор вычислитель ной системы (не показан), который выбирает для реализации очередную ту программу, для которой в соответствующем разряде регистра 12 имеется единицей При наличии в регистре 12 одновременно нескольких единиц супервизор выбирает очередной ту программу, для которой номер разряда, содерлсащий единицу, наименьший.. После выбора одной из програмк- набора для реализагши в вычислительной системе супервизор записывает в соответствувжщй номеру (например, Л 1;и выбранной программы разряд регистра 11 единицу. В результате на выходе элемента 13i будет высокий потенциал,-по которому триггер 9 и переходит в единичное состояние, подача ко-да со счетчика Si на входы шифратора 14 прекрашается и на регистре 12 записыва Ьтся другой код, по которому супервизор выбирает нереализованные программы. Работа устройства прекрашается при появлении на регистре 12 нулевого кода. Таким образом, предлагаемое устройство за счет введения новых элементов с соответствуюшими связями обеспечивае распределение набора информац тонно-связанных задач по процессорам вычислительной системы, существе1шо сокращаются аппаратные затраты (приблизитепь- НО, с точностью до одного триггера, на (и - ) счетчиков, в которые заносятся числа импульсов, дополняющие веса вершин до полной емкости счетчиков) по сравнению с известным. Сокрашение аппаратных затрат в устройстве, выполняющем те же функции,привоциг к соответствующему увеличению надежности устройства, Ф ормула изобретения Устройство для распределения заданий процессорам, содержащее матричную модель сети, блок управления, первый вы- ход которого подключен к управляющему входу шифратора, выходы которого соединены с входами репаогра приоритета, выходы которого являются выходами ycJV ройства и подключены к первым входам элементов И первой группы, вторые входы которых соединены с шлходами регистра выбранных вершин, входы которого являоются входами устрюйства, выходы элементов И первой грутйпы соединены с входами триггеров цервой труппы, выходы которых подключены к первым входам элементов И второй группы, выходы которых соединены с информапиошвыми входами шифратора, первую группу счетчиков и трепгью группу элементов И, выходы которых подключены к входам счетчиков первой группы, выходы которых соединены с вторыми входами элементов И вто рой группы, отл-и чающееся тем, что, с целью повьш1ения надежности устройства, в него введены вторая группа тригГеров, вторая группа счетчиков, четвертая группа элементов И и группа элементов ИЛИ-НЕ, входы которых сое- цинены соответственно с выхода уй татрячной модели сети, выходы элементов ИЛИ-НЕ хфуппы подключены к первым входам элементов И четвертой группы, вторые входы которых соединены с первыми входами элементов И третьей груп- . пы и подключены к второму выходу блока угфавления, выходы элементов И четвертой грушп т подключены к входам счетчиков второй группы, выходы которых соединены с входами матричной модели сети и с входами триггеров второй группы, выходы которых подключены к вторым входам элементов И третьей группы и к входам блока управления. Источники информации, принятые во внимание при экспертизе 1.Авторское свидете)тьство № 664175, кл. Q06F 15/20, 1976.. 2.Авторское свидетельство СССР по заявке Me 2886510/18-24, клГ.ООе Р 15/20, 1979 (прототш)

22 м

/З/И//f

ilL

2/

М

///7

&40ie4

12i

12г

12

Жг

d lA Т

8i 9f

Sr

/; /г

HJ

V

HJ

(-Э

i