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

.Г.Попо о СССР1977.СССР1981. ельств900,ьство9/46,7 тель зова тель повьпп Устро ности злеме тов И в уст тригг ра уэлем ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ ОПИСАНИЕ ИЗОБР К АВТОРСКОМУ СВИДЕТЕЛЬСТ(56) Авторское свидеУ 629938, кл, С 06 РАвторское свидетелУ 866560, кл. С 06 Р 54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕАДАНИЙ ПРОЦЕССОРАМ: Изобретение относится к вычислиой технике иможет быть исполь- о в многопроцессорных вычислиых системах. Цель изобретения - . ение быстродействия устройства. йство содержит регистр готовпроцессоров, элемент И, группу нтов И, группу блоков элеменгруппу элементов ИЛИ. Новым ройстве является использование ера запуска, четырех элементов ех элементов задержки, триггеравления, буферного регистра, ента ИЛИ-НЕ, генератора импульв, блока распределения, состоящео из регистра распределения, двух элементов задержки, группы элементов И, двух групп элементов ИЛИ, гру пы узлов распределения, выполненных, кроме первого, на двух группах элементов И, а первый - на одной группе элементов И. Устройство работает в два этапаНа первом этапе формируется очередь заявок, поступающих в первый регистр импульсов, перемещающихся по регистрам хранения груп пы. На втором этапе производится рас пределение свободных процессоров. При этом возможны два варианта работы устройства. В первом из них, когд число свободных процессоров больше либо равно требуемому для принятой заявки, производится их распределение, перемещение заявок в очереди и прием очередной заявки из последнего регистра хранения в буферный регистр Во втором варианте, когда число свободных процессоров меньше требуемых, заявка находится в буферном регистре пока ей не будет выделено требуемое число процессоров2 ил.Изобретение относится к вычисли;тельной технике и может быть использовано в многопроцессорных вычислительных системах.Цель изобретения - повышение быстродействия устройства,На фиг. 1 показана структурная схе,ма устройства; на фиг. 2 - структурная схема блока распределения процессоров. 1 ОУстройство (Фиг. 1) содержит группу регистров 1 хранения, триггер 2запуска, генератор 3 импульсов,элемент И 4, группу элементов И 5,элемент задержки 6, элемент задержки 7, элемент И 8, элемент И 9, элемент И 10, триггер 11 управленияэлемент задержки 12, элемент И 13,буферный регистр 14, элемент ИЛИ-НЕ15, блок 16 распределения процессоров, регистр 17 готовности процессоров группу блоков элементов И 18,группу элементов ИЛИ 19, вход 20 запуска устройства, вход 21 остановаустройства, вход 22 заявок устройства, группу информационных входов23 устройства, группу информационныхвыходов 24 блока 16, группу информационных входов 25 блока 16, управляющий вход 26 блока 16, выход 2 блока16, группу выходов 28 блока 16, группу выходов 29 блока 16, группу инФормационных выходов 30 устройства,Блок 16 распределения процессоров(фиг. 2) содержит регистр 31, элементы задержки 32 и 33, узлы 34. 1-34,Краспределения процессоров, группуэлементов И 35 первого узла 34.1 распределения.группы элементов И 36 и37 узлов 34 распределении, группу 4 Оэлементов ИЛИ 38, группу элементовИЛИ 39, группу элементов И 40.Рассмотрим принцип построения иработу устройства.Исходное состояние устройства 45характеризуется тем, что триггеры2 и 11, регистры 1, 14 и 31 установлены в нулевое состояние (не показано)Работа устройства начинается посигналу запуска,поступающему по входу 20 и устанавливающему триггер 2 запуска в состояние "1", и состоит из двух этапов еНа первом этапе Формируется очередь заявок, поступающих по входу 22 в первый регистр 1 хранения и по каждым тактовым импульсам перемещающихся по регистрам 1. Как только первая поступившая заявка окажется в последнем регистре 1, она передается в буферный регистр 14, определяя второй этап работы устройства,На втором этапе производится распределение свободных процессоров,сигналы готовности от которых поступают по входам 23 и фиксируются всоответствующих разрядах регистра готовности процессоров 17. При этомвозможны два варианта работы устройства. В первом варианте, когда числосвободных процессоров больше либоравно требуемому для принятой заявки в регистр 14, производится их распределение, перемещение заявок вочереди и прием очередной заявки изпоследнего регистра 1 в регистр 14.Во втором варианте, когда число свободных процессоров меньше требуемых,заявка находится в регистре 14, пока ей не будет выделено требуемоечисло процессоров а заявка на входе 22 сохраняется,Формирование очереди заявок производится следующим образом.Так как триггеры 11 и регистры1 и 14 установлены в состояние "0",то последний элемент И 5 открыт единичными сигналами с выхода элементаИЛИ-НЕ и с нулевого выхода триггера11. По тактовым импульсам, поступающим через открытые элементы И 4 и 5на управляющие входы регистров 1,заявки перемещаются по регистрам 1.Так как элемент И 10 закрыт поинверсному входу единичным сигналомс выхода элемента ИЛИ-НЕ 15, то импульсы генератора 3 не изменяют состояние триггера 11,Ввиду того, что элемент И 8 открыт единичным сигналом с выхода элемента ИЛИ-НЕ 15 и при перемещении за-явок по регистрам 1, пока первая изних не окажется в последнем регистре 1, на входах регистра 14 присутствует нулевая информация, по каждому импульсу генератора 3 нулевое состояние регистра 14 подтверждается.Когда по очередному импульсу генератора 3 первая заявка из последнего регистра 1 перемещается в регистр 14, единичный сигнал на выходе элемента ИЛИ-НЕ снимается. Через некоторое время, определяемое элементом задержки 7, нулевым сигналом свыхопа элемента ИЛИ-НК 15 по инверс ному входу открывается элемент И 10 и закрываются элементы И 5 и 9. Злемент задержки 7 обеспечивает прохождение импульса генератора 3 через элемент б без искажения за счетудержания в открьгтом состоянии последнего элемента И 5, при изменении состояния регистра,14. Кроме того элемент задержки 7 необходим цля соз дания условия надежного приема информации в регистр 14.Бремя задержки элемента б Определяется временем переходных процессов в элементе И 8, регистре 14 и элементе ИЛИ-НЕ и выбирается таким Образом, чтобы до перемещения заявок по регистрам 1 содержимое гОследнего регистра 1 принялось в регистр 14. Импульсом с выхода элемента задержки б происходит перемещение заявок в регистрах 1. Одновременно спередачей заявки в предпоследний регистр 1 происходит установка в " 1триггера 11 через открытый элементИ 10. При этом нулевым сигналом снулевого выхоца триггера 11 блокируется воздействие последующих импульсов генератора 3 на регистры 1 и14, а единичным сигналом с единичного его выхода открывается элементИ,13.По очередному импульсу генератора3 начинается второй этап работь уст 35ройс тва,Каждая заявка, принятая в регистр14, включает в себя код числа . ребуемыХ процессоров для решения задачии коц номера заявки. Код числа требуемых процессоров. указывается позиционным кодом. При этом максимальноечисло разрядов групп равно числу процессоров в вычислительной системе.Отсюда разрядность группы регистра .14, регистра 17 готовности процессоров и регистра 31 одинакова, Номер задачи указывается двоичным кодом вгруппе разрядов кода номера задачи врегистрах 1 и 14,50По импульсу генератора 3., проходящему через Открытый элемент И 13 по управляющему входу 26 блока 16 на синхронизирующий вход регистра 31,55 содержимое регистра 17 готовности процессоров на время одного цикла распределения передается в регистр 31 по входам 24. Потв ВЬ 1 чиг-;ИтЕЛЬНая СИСтЕМа СО- держит 4 ПГОцессоры и на момент распределения позиционный код числа свободных процессоров имеет в регистре 31 вид 0111. Для решения задачи требуется три процессора, при этом код числа требуемых процессоров в регистре 14 имеет ьид 1110.При данных условиях блок 16 рабо" тает следующим образом.Злементами И 35 в узле 34.1 производится выбор первой единицы из позиционного кода регистра 31,причем номер возбужденного элемента И 35 соответствует номеру свободного процессора а отсюда - номеру возбужденных элементов ИЛИ 39, И 40 ИЛИ 38 и .соОтветствующих выходов 28 и 29.В кажцом из узлов 34 посредством элемечтов И 37 производится определение оставшихся свободных процессоров для выделения одного из них очередному единичному сигналу в регистре 14. Затем с помощью элемента И 37 Обеспйчивается выбор крайней левойединицы. В каждом узле 34 элементы И 37 блокируются по инверсным входам единичными сигналами с выходов одноименФ ньх элементов И 35 первого узла 34 и элементов И 37 всех предыдущих узЛОВ.1По завершении переходных процессов в узлах 34, элементах ИЛИ 38 и 39 на выходе 27 блока 16 появляется сигнал, задержанный элементом задержки 32. По этому сигналу через соответствующие открытые блоки элементов И 18 сигналами с выходов 28 блока 16 в соответствующие выходные инФормационные шины 30 для выбранных процессоров перецается код номера задачи из группы разрядов регистра 14. Одновременно на ьыходах соответствующих элементов ИЛИ 19 формируются едиплп ничные сигналы, устанавливающие в соответствующие разряды регистра 17 готовности процессоров, переводя тем1 самым процессоры из состояния Свободен" в состояние "Занят".Через некоторое время, определяемое элементом задержки 33 устанавливается в "0" регистр 31 и через открытые соответствующие элементы И 40 возбужденньпы элементами ИЛИ 39 по выходам 29 - соответствующие разряды групг. регистра 14.13108 21 6группой информационных входов устройства первый элемент И, группу иэп (и - число заявок) элементов И,группу блоков элементов И, группу изп регистров хранения, группу элементов ИЛИ, выходы которых подключенык входам сброса соответствующих разрядов регистра готовности процессоров, выходы блоков элементов И группы являются информационными выходамиустройства и подключены к входам соответствующих элементов ИЛИ группы,группа информационных входов первогорегистра хранения группы являетсягруппой входов заявок устройства, управляющий вход каждого регистра хранения группы, кроме последнего, соединен с выходом соответствующегоэлемента И группы, группа информационных выходов каждого регистра хра"нения группы, кроме последнего, соединена с группой информационных входов последующего регистра хранениягруппы, первый вход элемента И группы, кроме первого и последнего, соединен с выходом предыдущего элемента И группы, о т л и ч а ю щ е е с ятем, что, с целью повышения быстродействия, в него введены триггер запуска, единичный и нулевой входы которого являются соответственно входа-.ми запуска и останова устройства,второй, третий, четвертый и пятыйэлементы И, три элемента задержки,триггер управления, буферный регистр,элемент ИЛИ-НЕ, блок распределенияпроцессоров и генератор импульсов,выход которого подключен к первомувходу первого элемента И, второйвход которого соединен с единичнымвыходом триггера запуска, .выход первого элемента И соединен с первымвходом последнего элемента И группы и с первым входом второго элемента И, второй вход которого подключенк единичному выходу триггера управления, нулевой выход которого соединен с первым входом первого и с вторыми входами остальных элементов Игруппы, выход элемента ИЛИ-НЕ черезпервый элемент задержки соединен спервыми входами третьего элемента ичетвертого элемента И, инверснымвходом пятого элемента И и с третьимвходом п-го элемента И группы, выходкоторого соединен с вторым входомтретьего элемента И и через второйэлемент задержки - с вторым входом Формула изобретения Устройство для распределения .зада ний процессорам, содержащее регистр готовности процессоров, группа информационных входов которого является Элемент задержки 33 необходим для выравнивания моментов формирования единичных сигналов установки в "О" разрядов регистров 17 и 14.Так как для рассматриваемого примера все разряды группы числа процессоров регистра 14 оказываются в нулевом состоянии, то на выходе элемента ИЛИ-НЕ 15 формируется единич;ный сигнал, которым по инверсному 10 входу закрывается элемент И 10, а открывается элемент И 9. Поэтому задержанным сигналом с выхода 27 блока 16 триггер устанавливается в "0".Время задержки элементом задержки 15 12 выбирается так, чтобы к моментупо- появления задержанного импульса на первом входе элемента И 9 на его втором входе по завершении переходных процессов в регистре 14, элементе 20 ИЛИ-НЕ 15 через элемент задержки 7 сформировался единичный уровень сигнала.После установки в "0" триггера 11 начинается первый этап работы устрой ства очередного цикла распределения процессоров для следующей в очереди заявки и в дальнейшем устройство функционирует аналогично рассмотренному,Если на втором этапе работы уст ройства по очередному импульсу генератора 3 в группе разрядов числа процессоров регистра 14 не все разряды обнулены, что означает недостаточное число процессоров для решения эа дачи, на выходе элемента. ИЛИ-НЕ 15 удерживается нулевой сигнал. Этим самым элемент И 9 остается в закрытом состоянии, поэтому триггер 11 сохраняет единичное состояние, Так 40 как нулевым сигналом с нулевого выхода триггера 11 последний элемент И 5 закрыт, а единичным сигналом с единичного выхода триггера 11 открыт элемент И 13, то по очередным им пульсам генератора 3 продолжается распределение процессоров задаче.При этом заявка в регистре 14 будет находиться до тех пор,пока задаче не будет выделено требуемое число процессоров.1 З 1 О 8 первого элемента И группы и с управляющим входом и-го регистра хранения группы, выходы которого подключены к соответствующим входам буферного регистра, выход пятого элемента Исоединен с единичным входом триггерауправления, нулевой вход которого подключен к выходу четвертого элементаИ, второй вход которого через второйэлемент задержки соединен с первыми 10управляющими входами блоков элементов И группы и с управляющим выходомблока распределения процессоров, первая группа информационных входов которого соединена с входами элемента 15ИЛИ-НЕ и с группой выходов кода числа процессоров буферного регистра,группа выходов кода номера задачикоторого подключена к информационнымвходам блоков элементов И группы, 20вторые управляющие входы которых подключены к первой группе выходов блока распределения процессоров, втораягруппа информационных входов которого соединена с выходами регистра готовности процессоров, входы сбросагруппы разрядов кода числа процессоров буферного регистра подключены квторой группе выходов блока распределения процессоров, управляющий вход З 0которого соединен с выходом второгоэлемента И, выход третьего элементаИ соединен с управляющим входом буферного регистра, выход предпоследнего элемента И группы подключен к пря мому входу пятого элемента И, причемблок распределения процессоров содержит два элемента задержки, регистр,группу элементов И, две группы элементов ИЛИ и группу узлов распределения, каждый из которых кроме первого, содержит две группы элементов И,а первый узел распределения. группысодержит группы элементов И, выходыкоторых являются выходами первого уз ла распределения группы, выходы элементов И второй группы каждого последующего узла распределения группы являются выходами этого узла,установочные входы регистра являются 50второй группой информационных входовблока распределения переносов процессоров, а вход сброса регистра соединен с первыми входами элементов Игруппы блока распределения процессоров и через первый элемент задержкис управляющим выходом блока распределения процессоров и с выходом вто 21 8рого элемента задержки, вход которого подключен к тактовому входу блокараспределения процессоров, прямой выход каждого разряда регистра соединен с первым входом одноименного элемента И группы первого узла,распределения группы и с прямым входом одноименного элемента И первой группывсех остальных узлов распределениягруппы, вторые входы элементов И груп-.пы первого узла распределения группы и первые прямые входы элементовИ второй группы остальных узлов распределения группы соединены с одноименными входами первой группы информационных входов блока распределения процессоров, выходы элементов Игруппы первого узла распределениягруппы и выходы элементов И первойгруппы остальных узлов распределениягруппы соединены с входами одноименных элементов ИЛИ первой группы блока распределения процессоров, выходыэлементов ИЛИ первой группы блокараспределения процессоров соединеныс вторыми входами одноименных элементов И группы распределения процессоров, выходы элементов И группы блокараспределения процессоров являютсявторой группой выходов блока распределения процессоров, инверсные выходырегистра соединены с соответствующими входами элементов И группы первого узла распределения группы, начинаяс второго элемента, выход каждогоэлемента И группы первого узла распределения группы соединен с соответствующим инверсным входом одноименного элемента И первой группы всех остальных узлрв распределения группы,выход каждого элемента И первой группы узлов распределения группы, начиная с второго, соединен с вторым прямым входом одноименного элемента Ивторой группы своего узла, выход каждого элемента И первой группы всехузлов распределения группы, начинаяс второго, соединен с соответствующим инверсным входом всех последующих элементов И второй группы своего узла, выход каждого элемента Ивторой группы всех узлов распределения группы, начиная с второго,соединен с соответствующим инверснымвходом одноименного элемента И первой группы следующего узла распределения группы, выход каждого элемента И второй группы последнего узла2350 Тираж 672 ВНИИПИ Государственногопо делам изобретений и 113035, Москва, Ж, Ра Зака Подписномитета СССРткрытий ская наб, д. 4/5 Производственно-полиграФическое предприятие, г. Ужгор Проектная,9 1310821 10 распределения группы соединен с пер- ных узлов соединены с входами одновым входом одноименного элемента ИЛИ именного элемента ИЛИ второй группы второй группы блока распределения блока распределения процессоров, выпроцессоров, выход каждого элемента ходы элементов ИЛИ второй группы бло- И группы первого узла распределения 5 ка распределения процессоров являются группы и выходы одноименных с ним эле- первой группой выходов блока распре- ментов И второй группы всех осталь- деления процессоров.