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

,Г,Боровко оцессор е управлназнаназнач ОСУДАРСТВЕННЫЙ КОМИТЕТО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯРИ П(НТ СССР(56) Авторское свидетельство ССГР Р 629538, кл. С 06 Р 9/00, 1977,Авторское свидетельство СГСР И 1151965, кл, ( 06 Р 9/46, 1983, (54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ ЗАЯВОК ПО ПРОЦЕССОРАМ(57) Изобретение относится к вь;числительной технике и может быть использовано для распределения заявок ,по процессорам в мультипроцессорных системах. Целы изобретения является повышение надежности функционирования устройства зя счет обслуживания Изобретение относится к вычисли ельной технике и может быть испол овано для распределения заявок по в мультипроцессорных сисЦель. изобретения -повышение надежности функционирования устройства за счет обслуживания заявок при отказе двух и более процессоров, назначенных на их рещение, во время распределения текущей заявки,На фиг. 1 представлена структурсхема предлагаемого устройства; на фиг. 2 - структурная схема блокаения; на фиг. 3 - то же, блокчения; на фиг, 4 - то же, узел ения блока назначения. заявок при отклзс " ух и более процессоров, назнлче. ы х на их решение,но время распределения текущей за -явки, Устройство содержит группу регистров, регистр готовности, регистрпотребности, блок управления, блокназначения, элементы И, ИЛИ, элементызадержки. Устропстн осуществляетприем копов з: . т, ссдержящих кодномера ."лдлчи, о числя потребныхдля ее решения пр;1 плссорон. Блок нлзнячения за один такт работы произно -дит нл-.начение нл поступившую заявкусвобог. х процессорон, При отказахпроцессгрон но время выполнения злдач блок управлсния организует перезагрузку кодов злдяч, нл которые онибыли назначены, свободные процес -сорь, 1 з, и. ф-лы, -" ил,Устройство содержит группу входов 1 заявок устройстнл, группу регистров 2, регистр 3 потребности, ре - гистр 4 готовности, группу элементов И 5, пернуи, вторую и третью группы блоков элементов И 6-8, эле - мент ИЛИ 9, первую и вторую группы элементов ИЛИ 1 О и 11, блок 12 назняч ния, блок 13 управления, группу элементов 14 задержки, группу сигнальных входов 15 устройства, нход 16 запуска устройства, выход 17 прерывания устройства. группы выходов 18 устройства, группу сигнальных входов 19 устройства, группу выходов 20 блока 13, группу сигнальных входон 21 устройства, вход 22 блока 13, вы 1462314:элементы И 67 и 68, элементы ИЛИ 70и 71, элемент 69 запрета,Устройство работает следующим образом.В исходном состоянии регистры 2,регистр 3 потребности, регистр,33 отказов, регистр 34 маски и триггер 35"1" (все процессоры исправны и свободны), На выход 17 устройства с выхода. элемента НЕ 52 выдается единичный уровень, сигнализирующий о том,что устройство готово к приему новойзаявки.Планирующая система вырабатываетзаявки на р"ление задачи. которыепоступают на гругпу вхоцов 1 устройства, Заявка содержит код ном.раадачи, которую нужно решить и код потребности для ее решения числа про-.цессоров. Код числа процессоров позиционный (представляется в видесоответствующего числа разряцных едини т), Поступая на группу ьходов 1код заявки через группу выходов 20блока 13 управления поступает навход элемента ИЛИ 49 единичный сиг"нал с вихоца которого при этом поступает на первый вход элемента И 41На второй вход элемента И 41 с выхода элемента И 40 через элемент ИЛИ48 также подается единичный сигнал,так как на выходе элемента ИЛИ 46,а также элементов НЕ 52 и НЕ 53 висходном состоянии находится единичный потенциал. Поскольку в исходном состоянии на вход 16 устройства подается "0", элемент И 41 закрыт по третьему входу, и на выходе 23 блока 13 находится нулевой потенциал, закрывающий элементы И 5 группы по вто рым входам. На выходах 24 и 25 блока управления в исходном состоянии так а =а ь (с 1),а в каждой строке матрицы имеютсятри горизонтальныдвоичных каналас распространением сигнала слева на;траво, реализующие в каж,цом узле логические Аункции.поступающие с выходов регистра 4 передаются через открытие элементы И43 и элементы ИЛИ 51 на выходи группы выходов 26 блока 13 управления,открывая все блоки элементов И 6.10 Для включения устройства в работуна его вход 16 подается единичный потенциал, которнй сохраняется в течение последующей работы устройства.С поступлением этого потенпиала от 15 крывается элемент И 41 и с выхода 23блока 13 угравления на вторые входывсех элементов И 5 группы подаетсяединичный сигнал,Ввиду того, что на выходе всех20 элементов И 5 группь: присутствуетединичный потенциал, первая заявкапервоначально поступае на все регистры 2, а затем через блоки элементовИ 7 и элементы ИЛИ 11 код потребного25 числа процессоров поступает в регистр3 потребности, а код номера задачичерез открытые блоки элементов И б(на вход каждого из них подается единичный сигнал с соответствующего выЗО хода группы выходов 26 блока 13 управления) и элементы ИЛИ 10 первойгруппи подается на групповые входывсех блоков элементов И 8 третьейгруппы,С появлением единичного значенияи разрядах регистра 3 потребности начинается работа блока 12 назначениякоторый представляет ссоой двумернуюитеративную матрицу узлов 58 назначецГ. ния, Каждый узел 58 представляет собой конечный автомат без памяти. 3каждом столбце матрицы имеется верти.кальный двоичный капа.: (фиг, 3) сраспространением сигнала сверху вниз,реализующий в каждом узле логическуюФункцию10 20 25 58, Ь и Ь - на втором выходе 60 и выходе 64, с и с - на третьем выходе 61 и выходе 65, с 1 и й - на четвертом выходе 62 и выходе 66 узла 58,На выход 59 каждого узла граничной верхней строки матрипы через соответствующий вход группы входов 27 блока 12 назначения подается содержимое соответствующего разряда регистра 3 потребности, На выход 60 (на выход 62) каждого узла граничного левого столбца матрицы через соответствующий вход группы входов 28 (29) блока 12 назначекия,подается сигнал с прямого (инверсного) выхода соответствующего разряда регистра 4 готовности, На выход 6 всех узлв граничного левого столбца подается с входа 57 блока 12 назначения нулевая граничная константа (с,=О).В случае, если на выходе 59 какого-либо узла граничной верхней строки присутствует нулевой сигнал (а = =0), во всех узлах соответствующего данному узлу столбца в соответствии с (2) - (4):Ь =Ь с =с Й Ме При появлении позиционного кода 30числа потребных процессоров в регистр3 единичный сигнал с первого слеваединичного разряда распространяетсявниз по соответствующему стрлбцу до.того узла, в котором Ь=1 (д=О35с=с =0). На выходах этого узла в соответствии с (1)-(4) дюрмирунтсясигналы а =0; Ь =О; с =1, с 1 =О. Впоследующих узлах данного столбца(расположенных ниже) сигнал в вертикальном канале в соответствии с (1)измениться не может, и с выхода 63нижнего узла данного столбца нуле 1вой сигнал (а=О) подается через соответствующий выход группы выходоВ 4530 блока 12 назначения на.вход соответствующего разряда регистра 3потребности, сигнализируя о том, чтопотребность в одном из заказных процессоров удовлетворена. В последующих узлах данной строки, расположенных правее, сигналы в горизонтальныхканалах в соответствии. с (2)-(4)также изменйться не могут. С выхода.65 правого узла данной строки единичный сигнал подается через соответствующий выход группы выходов 32 блока12 назначения на вход соответствующего блока элементов И 8, разрешая передачу кода номера задачи для исполнения в свободный процессор (данный процессор был свободен, так какс регистра 4 готовности в новый узелсоответствующей строки матрицы блока12 назначения подавался сигнал Ь 1).Таким образом, осуществляется назначение процессора на выполнение задачи. С выхода б 4 правого узла даннойстроки нулевой сигнал подается черезсоответствующий выход"группы выходов31 блока 12 назначения на вход соответствующего разряда регистра 4, сигнализируя о том, что соответствующийданному разряду процессор уже назна -чен на вьнюлнение задачи, Аналогичнымобразом осуществляется назначениеоставшегося числа заказанных процессоров при наличии достаточного числасвободных процессоров,Одновременно с появлением единицпозиционного кода числа потребныхпроцессоров в регистре 3, на выходеэлемента ИЛИ 9 гоявляется единичныйсигнал, который подается на вход 22блока 13 управления, Этот сигнал проходит через открытый элемент И 36 напервый вход элемента И 42 и через эле.мент 55 задержки на второй вход элемента И 42, С выхода элемента И 42задержанный единичный сигнал черезвыход 25 блока 13 управления подается на тактовый вход регистров 3 и 4.Время задержки элемента 55 задержкивыбирается таким, чтобы этот сигналпоявлялся на входах регистров 3 и 4после завершения переходных процессоров в блоке 12 назначения.С поступлением единичного сигналана тактовые входы регистров 3 и 4хотя бы один из них сбрасывается внулевое состояние в первом случае,если число потребных для решения процессоров меньше числа свободных процессоров, обнуляется регистр 3, вовтором случае, если число потребныхпроцессоров больше числа свободных,регистр 4, в третьем случае, есличисло потребных равно числу свободных - регистр 3 и. регистр 4,В первом случае с выхода элементаИЛИ 9 на вход 22 блока 13 поступаетнулевой сигнал, на выходе элементаНЕ 52 при этом появляется единичныйсигнал, который поступает на выход17 устройства, сигнализируя планирующей системе о том, что устройствозакончило распределение текущей заяв7 146 231 ки и готово к приему следующей. 11 олу-, чив этот сигнал, планирующая система выдает на входы 1 устройства код сле-, дующей заявки, а в случае отсутствия в данный момент заявок, выставляет на входах 1 заявок нулевой код, При отсутствии отказов процессоров (на выходе элемента НЕ 53 присутствует единичный потенциал) единичный сигнал 10 с выхода элемента ИЛИ 46 проходит через открывшие элементы И 37, И 40 и элемент ИЛИ 48 на второй вход элемента И 41, При отсутствии новых заявок нулевой сигнал с выхода элемен та ИЛИ 49 удерживает элемент И 41 взакрытом состоянии и на выходе 23 блока 13 сохраняется нулевой потен циал, устройство переходит в режиможидания новых заявок. Если планирующая система выставила на вход 1 код новой заявки, элемент И 4 открывается и с выхода 23 блока 13 еди, ничный сигнал поступает на вторые входы элементов И 5 группы. При этом открываются те элементы И 5 группы, на первые входы которых поступают единичные сигналы с выходов регистра 4, и разрешают запись в соответствующие свободным процессорам регистры ЗО 2 кода новой заявки. Единичные сигналы с выходов элементов И 5, задержанные соответствующими элементами 14 задержки группы на время, достаточное дпя завершения переходных процессов в регистрах 2, открываютсоответствующие блоки элементов И 7,по первому входу (на второй входэтих блоков поступает единичный сигнал с выхода 17 блока 13 управления), 40разрешая запись в регистр 3 кода числа процессоров, потребных для решения данной задачи. Назначение процессоров на эту задачу производитсяаналогично рассмотренному, 45Во втором случае нулевой потенциал с выхода элемента ИЛИ 46 закрывает элемент И,36, 37 и 39. Единичныйсигнал с выхода элемента ИЛИ 9 подается на вход 22 блока 13. На выходах 5017, 23, 24 и 25 и группе выходов 26блока 13 управления присутствуют нулевые потенциалы, Устройство переходит в режим ожидания. свободных процессоров, При освобождении хотя быодного процессора на выходе элементаИЛИ 46 й на выходах группы выходов 26блока 13, соответствующих освободившимся процессорам, появляется единичный потенциал, так как при отсутствии отказов на выходе элемента НЕ 53присутствует единичный потенциал,При этом открывается элемент И 39,и передним фронтом единичного сигналас его выхода, поступающим на тактовыйвход триггера 35, триггер 35 переводится в единичное состояние, так какна его информационном входе единичный потенциал. Единичный сигнал с единичного выхода триггера 35, длительность которого определяется элементом 55 задержки, поступает через элемент ИЛИ 48 на второй вход элементаИ 41. На его первый вход поступаетединичный потенциал с выхода элемента ИЛИ 49; на вход которого поступаеткод заявки, распределение которой ещене закончено, так как единичный сигнал на выходе 17 блока 13 не вырабатывался, Сигнал с выхода 23 блока13 поступает на элементы И 5 группы, организуя запись в регистрах 2,соответствующих освободившимся процессорам кода заявки, Код числа потребных процессоров из этих регистровв регистр 3 не переписывается, таккак блоки элементов И 7 остаютея закрытыми нулевым потенциалом поступающим с выхода элмента НЕ 52. Дона- значение процессоров на данную задачу производится аналогично описанному.Если в ходе решения задачи откажет какой-либо из назначенных процессоров, на соответствующем входе группы входов 21 бло .а 13 появляется единичный потенциал, который поступает на первый вход соответствующего элемента И 45 группы; На второй вход этого элемента с соответствующего выхода группы инверсных выходов регистра 34 первоначально также поступает единичный потенциал., С выхода этого элемента единичный сигнал поступает на информационный вход соответствующего разряда регистра 33, С входа группы входов 21 единичный сигнал одновременно поступает через элемент ИЛИ 50 и элемент 56 задержки на тактовый вход регистра 33. Таким образом, в регистр 33 заносится информация об отказавших процессорах. С появле-нием единичного значения хотя би в одном разряде регистра 33 на выходе элемента ИЛИ 47 появляется единичный потенциал, а на выходе элемента НЕ 53 - нулевой потенциал, который завыхода отказавшего процессора навход группы сигнальных входов 21 устройства к этому моменту прекращается), единичный сигнал готовности свыхода восстановленного процессорапоступает на соответствующий входпервой группы сигнальных входов устройства, устанавливая в "1" соответствующий разряд регистра 4,Формул а и: о бр ет ения 1. Устройство для распределения заявок по процессорам, содержащее группу регистров, регистр готовности, группу элементов И, первую, вторую, третью группы блоков элементов И, элемент И 1 П 1, первую и вторую группы элементов ИЛИ, блок управления, содержащий первый, второй и третий элементы И, первую и вторую группы элементов И, первый и второй элементы ИЛИ, группу элементов. ИЛИ, первый и второй элементы НЕ, причем группы инАормационных входов регистров груп. пы объединены и являются группой входов заявок устройства, управляющий вход каждого регистра группы соединен с выходом одноименного элемента И группы, первая группа выходов каждого регистра группы соединена с группой входов одноименного блока элементов И первой группы,вторая группа выходов каждого регистра группы соединена с группой входов одноименного блока элементов И второй группы, группа выходов каждого блока элементов И первой группы соединена с группой входов одноименного элемента ИЛИ первой группы, группа выходов каждого блока элементов И второй группы соединена с группой входов одноименного элемента ИЛИ второй группы, выходы элементов ИЛИ первой группы соединены с группой входов каждого блока элементов И третьей группы, группа выходов которого является соответствующей группой выходов уст - ройства выход элемента ИЛИ соединен с входом первого элемента НЕ и с первым входом первого элемента И блока управления, первая группа сигнальных входов устройства соединена с группой информационных входов регистра готовности, каждый выход группы прямых выходов регистра готовности соединен с первым входом одноименного элемента И группы, с соответствующим 1 9 1462314 крывает элементы И 39,и 40 и элементы И 43 первой группы, В момент окончания распределения текущей заявки на выходе элемента НЕ 58 появляется единичный сигнал, который при наличии свободных процессоров проходит через элементы И 37 и 38 на выход 24 блока 13, Одновременно единичный сигнал с выхода элемента НЕ 53 поступает на первый вход каждого элемента И 44 группы, При этом открывается только один элемент И 44, соответствующий единичному разряду регистра 33, с минимальным юмЕром, поскольку нулевой 15 потецниал с его инверсного выхода закрывает элементы И 44, соответст:. вующие разрядам с большим номером. Единичный сигнал с выхода элемента . И 44 устанавливает в "1" соответствую щий разряд регистра 34 и через элемент ИЛИ 51 группы поступает на соответствуюший выход группы выходов 26 блока 13, открывая соответствующий отказавшему процессору блок элемен. - 25 тов И 6 группы. Единичный сигнал с выхода 24 блока 13 через первый элемент ИЛИ 11 группы записывает единицу в первый разряд регистра 3, После этого аналогично изложенному осуще ствляется назначение свободного процессора на задачу, кторую выполнял отказавший процессор. Единичный сигнал с выхода элемента И 38 через элемент ИЛИ 50 и элемент 56 задержки поступает также на вход синхронизации триггеров регистра 33, Так как элемент И 45, соответствующий отказавшему процессору, переназначение которого, уже состоялось (в соответст вующем разряде регистра 33 записана "1 ), закрыт нулевым сигналом с инверсного выхода соответствующего разряда регистра 34, соответствующий разряд регистра 33 обнуляется. Если 45 имеются еще необработанные отказы (имеются единичные разряды в регистре 33), процедура переназначения повторяется до тех пор, пока не будут обработаны все имеющиеся отказы, 50 ,Только после этого устройство перейдет к приему следующей новой заявки от планирующей системз. С восстановлением отказавшего процессора на соответствующий вход группы сигнальных входов 15 устройства подается единичный сигнал, который сбрасывает в "О" соответствующий разряд регистра 34 (подача единичного потенциала с14623входом первого элемента ИЛИ и с первым входом одноименного элемента Ипервой группы блока управления, выход второго элемента И блока управ 5ления соединен с вторыми входами элементов И группы, выход третьего элемента И блока управления соединен с,:входом первого элемента ИЛИ второй,:группы, в блоке управления выход пер;:вого элемента ИЛИ соединен с вторым:входом первого элемента И, выход пер"ваго элемента НЕ соединен с первымивходами элементов И второй группы;блока управления, выход второго эле,:мента ИЛИ блока управления соединенс входом второго элемента НЕ и спервым входом третьего элемента И., в:блоке управления выход второго зле;мента НЕ соединен с вторым входом 20каждого элемента И первой группы,;выход которого соединен с первым входом одноименного элемента ИЛИ груп:пы, второй вход которого соединен с,выходом одноименного элемента И вто.рой группы,. а выход каждого элемента ИЛИ группы блока управления соединен с управляющим входом одноименного блока элементов И первой группы,о т л и ч а ю щ е е с я тем, что с 30целью повышения надежности функционирования устройства за счет обслу"живания заявок при отказе двух и более процессоров, назначеиных на ихрешениево время распределения теку- Збщей заявки, в устройство введены регистр потребности, группа элементовзадержки, блок назначения, содержащийК групп узлов назначения (К - количество выходов регистра потребности),а в блок управления введены регистротказов, регистр маски, триггер,четвертый, пятый, шестой и седьмойэлементы И, третья группа элементовИ, третий, четвертый, и пятый элементы ИЛИ, первый, второй и третийэлементы задержки, причем каждый входгруппы информационных входов регистра потребности соединен с выходомсоответствующего элемента ИЛИ второйгруппы, каждый выход группы выходоврегистра потребности соединен с соответствующим входом элемента ИЛИ ис соответствующим входом первойгруппы входов блока назначения, вто"рая группа входов которого соединена с группой прямых выходов регистраготовности, третья группа входов бло 14 12ка назначения соединена с группой инверсных выходов регистра готовности. первая группа выходов блока назначения соединена с груплой установочных входов регистра потребности, каждый выход второй группы выходов блока назначения соединен с управляющим входом одноименного блока элементов И третьей группы, третья группа выходов блока назначения соединена с группой установочных входов регистра готовности, управляющий вход которого соединен с управляющим входом регистра потребности и с выходом четвертого элемента И блока управления, группа входов третьего элемента ИЛИ которого соединена с группой входов заявок устройства, первый управляющий вход каждого блока элементов И второй группы соединен с выходом одноименного элемента задержки группы, вход каждого из которых соединен с выходом одноименного элемента И группы, второй управляющий вход каждого блока элементов И второй группы соединен с выходом первого элемента НЕ блока управления, в блоке управления первый вход четвертого элемента И соединен с выходом первого элемента И, второй вход четвертого элемента И соединен через первый элемент задержки с выходом первого элемента И, выход пятого элемента И соединен с вторым входом третьего элемента И и с первым входом шестого элемента И, выход третьего элемента И соединен с первым входом четвертого элемента ИЛИ, первый вход пятого элемента ИЛИ соединен с единичным выходом триггера и через второй элемент задержкис входом сброса триггера, информационный вход которого соединен с первым входом первого элемента И блока управления, тактовый вход триггера соединен с выходом седьмого элемента И, группа входов четвертого элемента ИЛИ соединена с второй группой сигнальных входов устройства, выход четвертого элемента ИЛИ соединен через третий элемент задержки с управляющим входом регистра отказов, входы которого соединены с выходами элементов И третьей группы, первый вход каждого элемента И третьей груп-, .пы соединен с одноименным инверсным выходом регистра маски, второй вход каждого элемента И третьей группысоединен с одноименным входом второй13 группы сигнальных входов устройства,первый вход седьмого элемента И соединен с выходом первого элементаИЛИ, с вторым входом первого элемента И и с первым входом пятого элемента И, вторые входы щестого и седьмого элементов И соединены с выходомвторого элемента НЕ, выход седьмогоэлемента И соединен с тактовым входом 10триггера, второй вход пятого элемента ИЛИ соединен с выходом нестогоэлемента И, выход пятого элемента ИЛИсоединен с первым входом второго элемента И, второй вход которого соединен с выходом третьего элемента ИЛИ,второй управляющий вход каждого блокаэлементов И второй группы соединенс выходом первого элемента НЕ блокауправления, с вторым входом пятого 20элемента И блока управления и является выходом прерывания устройства,вход сброса каждого разряда регистрамаски соединен с одноименным входомтретьей группы сигнальных входов устройства, вход запуска которого соединен с вторым входомвторого элементаИ блока управления, единичнцй входкаждого разряда регистра маски соединен с выходом одноименного элемента 30И второй группы, прямой вход каждогоразряда регистра отказов соединен ссоответствующим входом одноименногоэлемента И второй группы, инверсныйвыход каждого разряда регистра отказов соединен с соответствующими входами всех последующих элементов Ивторой группы, прямые выходы регистра отказов соединены с входами второго элемента ИЛИ, причем в блоке назначения первые входы узлов назначения первой группы соединены с входомлогического нуля устройства, второйвход каждого -го узла назначенияпервой группы (=1 п, и - число узлов назначения в группе) соединен с-ым входом второй группы входов блока назначения, третий вход каждого-го узла назначения первой группысоединен с х"ым входом третьей груп 146231 Й 14пы входов блока назначения первый,второй и третий выходы х-го узла назначения каждой группы, кроме послед.ней, соединены соответственно с первым, вторым и третьим входами -гоузла назначения следующей группы,четвертый вход первого узла назначения каждой группы соединен с одноименным входом первой группы входовблока назначения, третьи выход узлов назначения последней группы неиспользуются, четвертый выход каждого узла назначения группы, кроме последнего .тала группы, соединен с четвертым входом следующего узла назначения данной группы, четвертые выходы последних узлов назначения каждойгруппы являются пе вой группой выходов блока назначения, первые викоды узлов назначения последней группы являются третьей группой выходовблока назначения, вторые выходы уз влов назначения последней , руппы являются второй группой выходов блоканазначения,2, Устройст " по и. 1, о т л ич а ю щ е е с: те , что узел назначения содержит два элемента И, дваэлемента ИЛИ и элемент запрета, причем первый вход узла соединен с первым входом первого элемента И и спрямым входом элемента залрета, выходкоторого является первым выходомузла, второй вход которого соединенс первыми входами первого и второгоэлементов ИЛИ, второй вход и выходпервого элемента ИЛИ соединены соответственно с выходом первого элементаИ и с вторым выходом узла, третийвход которого является его третьимвыходом и соединен с вторым входомвторого элемента ИЛИ, выход которогосоединен с первым входом второго элемента И, второй вход которого соединен с вторим входом первого элементаИ, с инверсным входом элемента запре.та и с четвертым входом узла, четвертый выход которого соединен с выходом второго элемента И.)инат "Патент", г, Ужгород, ул. Гагарина,ельск и иэв Составитель И, Купрящева Техред А. Кравчук 3/47 Тираж 667Государственного коыитета по изобр 113035, Москва, Ж, Рауш