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

(51)5 О 06 Р 9/46 ТЕН Б У КИ ельдля сов, устъМ тараи элементы И,а не позволяютчислом каналовает их функциоименеййя. ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИПРИ ГКНТ СССР ОПИСАНИЕ И ВТОРСКОУУ СВИДЕТЕЛЬ(71) Киевский политехнический институт им50-летия Великой Октябрьской социалистическай революции(56) Авторское свидетельство СССРй 1277108, кл, О 06 Р 9/46, 1987.Авторское свидетельство СССР(54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕ ЯЗАДАНИЙ МЕЖДУ ЭВМ(57) Изобретение относится к вычислитной технике и может быть использованопостроения вычислительных комплекмногопроцессорных вычислительных Изобретение относится к вычислительной технике и может быть использовано при построении вычислительных комплексов.Известны устройства для распределе.Ния заданий между ЭВМ содержащие три счетчика, три сумматора вычислителя, три элемента сравнения, три элемента ИЛИ, девять блоков элементов И, генератор импульсов; три канала, каждый из которых содержит два блока регистров, накапливающий сумматор, схему сравнения, группу схем сравнения., блок элементов И, первый и второй элементы И, элементы ИЛИ, три канала, в каждом канале счетчик, комбинационный сумматор, схема сравнения, блок ройств. Цель изобретения - расширение области применения устройства за счет минимизации времени обработки заданий вследствие учета времени ожидания задания, Устройство содержит шифратор приоритетов, дешифратор и К каналов (К - число Э ВМ). Каждый канал имеет счетчик суммарной загрузки канала, коммутатор и блок элементов И, Устройство определяет минимально загруженную ЭВМ с учетом пройденного времени обработки ранее поступивших заданий и таким образом позволяет сократить время обработки заданий и время ожидания на обработку вновь поступившего задания, Выбор нужного канала осуществляется путем-анализа состояний выходов признаков перейосов счетчиков всех незаблакированных каналов, 1 ил. элементов И, первыи и в элемент ИЛИ,Однако такие устройств обслуживать комплекс с больше трех, что ограничив нальные возможностий=пр Наиболее близким к изобретению по технической сущности является устройство для распределения заданий между Э ВМ, содержащее К качалов, в каждом канале счетчик, блок элементов И, один на все устройства шифратор и один дешифратор, причем информационный вход устройства подключен к первым входам блоков элементов И всех каналов, выходы которых являются выходами устройства,К недостаткам прототипа относится отсутствие учета пройденного времени обработки задания нз 1-й ЭВМ при распределении вновь поступившего зэдэния, что приводит к увеличению общего времени обработки пакета заданий и увеличение времени ожидания задания от времени поступления до времени обработки в ЭВМ.Цель изобретения - расширение областиприменения устройства за счет минимизации времени обработки заданий вследствие учета времени ожидания задания,Поставленная цель достигается тем, чта в устройство для распределения заданий между ЭВМ, содеркащее шифратор приоритетов,дешифрэтори К каналов(К-числа ЭВМ), причем каждый канал содеркит счетчик и блок элементов И, информационный вход устройства соединен с первыми входами блоков элементов И и информационными входами счетчиков всех каналов ус аайства, выходы блоков элементов И всех каналов образуют группу выходов устройства, выхоц признака переноса счетчика 1-го канала 1 = 3, К) соединен с 1-м информационным входом шифратора приоритетов, выход признака запроса которого соединен с входом стробирования дешифраторз, ин. фармэционнь,й выход шифрзторз приоритетов соединен с информзционным входом дешифраторэ, 1-й выход которого соединен с вторым входом блока элементов И и входом разрешения записи счетчика 3-го канала, вход разрешения переноса которага является входом блокировки 1-го канала устройства, введены в каждый канал устройства коммутатор, причем признака переноса счетчика 3-гг канала соединен с первым управляющим входом коммутатора 1-го канала, выход которога соединен с син- хровходом счетчика 1-го канала, выход признака запроса шифрэторэ приоритета соединен вторыми упрзвляюц 3 ими входэми коммутаторов всех каналов, первый, отарой и третий информационные входы коммутэторов всех каналов соединены соответственно с первым и вторым синхровходэми устройства и входом записи устройства, которь 3 й соединен с входом стробировэния шифратора приоритетов.Сущность изобретения заключается в следующем,Благодаря введению в каждый кэнэл коммутатора и соответствующему изменению связей в устройство паявилэсь возможность корректировать изменение текущего времени обработки заданий во всех каналах загруженных ЭВМ, что позволяет определить минимально зэгрукенную ЭВМ с учетом пройденного времени решения заданий 5 нэ всех ЭВМ и распределить вновь паступившее задание в канал с минимальной зэгрузкой. Тэк кэк эта возмокность отсутствовалэ в устройстве прототипа, предлагаемое устройство позволяет сокра тить время обработки пэкетэ заданий и время ожидания на обработку вновь поступившего задания.3-3 э чертеже изабрэженэ структурнзясхемл устройства для распределения зада нийУстроиства для распределения зэдзниимежду ЭВМ содержит информационный вход " который подключен к информационным входам счетчиков 2 и первым входам 20 блоков элементов ИЗ. В ыход признака переносэ 1-го счетчикэ 2, подведен к 1-му входу шифрэторэ приоритетов 4, к входу разрешения счета 1-га счетчика 2, 1 и к первому управляющему входу коммутатора 1-га кана ла 5, 1, Выход признака зэпросэ шифратораприоритетов 4 свяээн с 2-м упрэвляющим входам коммутаторов 5, ф = 1, К) всех каналов и с входом страбирования дешифратора б. Информационный выход шифратарз при- ЗО оритетов 4 подведен к информационномувходу дешифрзтора б, 1-й выход которого подключен к второму входу блока элементов 3 3 и к входу разрешения записи счетчика 1-га канала 2. 3. Вход синхронизации 3-га счетчи кэ 2. 3 соединен с выходом коммутатора 1-гоканала 5, 1, к первому, второму и третьему вхадэм которого подведены соответственно первый синхровход 7, второй сиихровход 8 и вход записи устройства 9. Вход записи 9 40 подключен к входу стробирования шифратора приоритетов б, Выход блока элементов И 33 образует информационный выход 10,1 1-го канада. Выход разрешения перенасэ счетчика 1-го канапэ 2,образует вход блокировки этого канала 11, 3.Предлагаемое устройство распределения заданий мажет быть выполнено с использованием элементов различных серий, Так., например, в качестве группы элементов И 3 могут быть использованы микросхемы К 58 ОВА 8 б, первым входом которых служат информационные входы элементов, з вторым входом является вход, упрэвляюьций передачей информации на выход: при "1" нэ упрэвляющем входе информация передается с входом нэ выход; паи "О" выходы перевоцятся в высокоомное состояние. Счетчики 2 могут быть реализованы на микросхемах К 531 ИЕ 17, которые позволяют строить счет/10 20 40 Работа шифратора приоритетов 4 разрешена нулевым сигналом, поступающим на его вход стробиронания с синхровхода записи 9. При наличии хотя бы одной единицы на входах шифратора приоритетов 4, последний выдает единицу на выход признака запроса, которая поступает на вход стробирования дешифратора 5, Единичный сигнал на входе страбирования дешифратора 5 чики с разрядностью, ратной 4, Микросхема К 531 ИЕ 17 имеет четырехразрядный информационный вход. вход разрешения счета, вход разрешения переноса, тактовый вход (в описании ему соответствует вход синхронизации), вход записи (вход разрешения записи), вход направления счета(для прямых кодов используется вычитание, для обратных кодов - суммирование) и выход переноса, В качестве шифратора приоритетов 4, коммутаторов 5, 1 - 5, К., дешифратора 6 могут быть выбраны соответственно микросхемы К 5 ООИВ 165, К 155 КП, К 155 ИД 4, Микросхема шифратора имеет восемь информационных входов, вход синхрониза ции, выход переноса и информационный вь,ход (для кодирования номера одного из восьми входов используются три вывода). При нулевом сигнале на входе синхронизации шифратор формирует двоичный код наиболее приоритетной возбужденной входной шины и сигнал выхода переноса, При единичном сигнале на входе синхронизации входы блокируются, а на информационном выходе и выходе переноса будут 2 сохранены сигналы, зафиксированные ранее.Устройство работает следующим образом,В исходном состоянии все ЭВМ свобод ны, находятся в работоспособном состоянии, по второму синхровходу 8 поступают импульсы, обеспечивающие быструю работу счетчиков 3, 1-3 . К в счетном режиме; по первому синхравхаду 7 выдаются импуль сы, период поступления которых равен единичнамуинтервалу времени,.принятомудля данной вычислительной системы.( код времени решения любого задания определяется количествомэтих интервалов); на вход записи 9 поступает нулевой сигнал; счетчики 2,1 - 2;К установлены в единичное состояние (111), на все входы блокировки 11, 1 - 11. К подаются логические единицы, разрешающие работу соответствующих ка налов. При этом с выходов признака переноса всех счетчиков 2 .1 - 2. К логические единицы поступают на информационные входы шифратора приоритетаь 4. разрешает дешифрацию кода. Код представляет собой номер первого установленного в единичное состояние счетчика. В исходном состоянии будет номер первого счетчика 2,1, который поступает с информацианнога выхода шифратора приоритетов. В результате дешифрации единичный сигнал с первого выхода дешифратора подается на вход разрешения записи счетчика 2,1, устанавливая ега в режим параллельной записи, и на второй вход блока элементов И - К 3,1, открывая его для обмена информации. Логические нули на остальных выходах дешифратора 5 запрещают передачу информации через соответствующие этим входамблоки элементов И (3,2 - 3 . К) и одновременно поступают на входы разрешения записи счетчиков 2.2 - 2, К и переводят из в режим счета-хранения,Единичный сигнал с выхода признаказапроса; шифратора приоритетов поступает также на вторые управляющие входы всех К коммутаторов и тем самым отключает второй синхровход 8 от синхравхода всех счетчиков. В то же время сигнал с выхода признака переноса 1-го ( = 1,К) счетчика поступает на вход разрешения счета этого же счетчика и на первый управляющий. вход 1-го коммутатора 5. . При нулевом сигнале навходе разрешения записи нулевой сигнал на входе разрешения счета задает режим счета, а единичный задает режим хранения, В исходном состоянии с выходов признаков переноса счетчиков поступают единичныесигналы, следовательно, счетчики 2.2 - 2,К находятся в режиме хранения, Сигналы на первом и втором управляющих входах коммутаторов 6.1 - 6.К обеспечивают подключение к входам синхронизации счетчиков2.1 - 2.К входа записи устройства 9. Код задания и кад времени решения с информационного входа 1 устройства поступает через открытый блок элементов И3,1 на выход 10,1 первого канала и далее в соответствующую ЗВМ. Кроме того, код времени выполнения задания записывается в счетчик 2.1 по синхроимпульсу записи, поступающему через коммутатор 6.1 с входа записи устройства 9 (синхроимпульс записи поступает и на остальные счетчики 2,2-2, К, но при этом содержимое не меняется, так как они находятся в режиме хранения). В результате этого на выходе признака переноса счетчика 2.1 появится нулевой сигнал. Эта изменение вызовет изменение выходного кода шифратора приоритетов 4 и соответствующее изменение када на выходе дешифратора 6, В результате этого логическая единица появится на втором выходе1755280 8дешифратора 5, а на остальных выходах ус- редачу информации через блоки элементов тановятся логические нули, . И 3, 1 - 3;К и переведут все счетчики 2 .1 -Логическая единица на втором выходе 2,Кв режим счета-хранения, При этом нуледешифратора 6 разрешает передачу инфор- вые сигналы с признаков переноса счетчимации через 3.2 элементов И, и одновре коп задают в счетчиках режим счета. менно переведет счетчик 2,2 в режим Одновременно нулевой сигнал с выхода пепараллельной записи кода с информацион- реноса шифратора приоритетов 4 поступит ного входа 1. Логические нули на остальных на первый Управляющий вход всех мульти- выходах дешифратора 5 запрещают переда- плексоров 6.1 - б, К. В результате этога имчу информации через блоки элементов И 10 пульсы с второго синхровхада 8 поступают 3,1,3,3,3.Киодновременнопереводятсчет- во все счетчики 2.1 - 2.К. При этом ани чики 2,1,2,3 - 2., К в режим счета-хранения,. декрементируют содержимое, если время При этом с выходов признака счетчиков 2.3 решения записано в прямом коде (или инк - 2,К по прежнему поступают единичные рементируот содержимое, если время ресигналы, Поэтому эти счетчики будут наха шения записано в обратном коде), Режим диться в режиме хранения, а с выхода при- счета (поиск наименее загруженной ЗВМ) знака переноса счетчика 2;1 нулевой сигнал будет продолжаться до тех пор, пака в капоступает на вход разрешения счета этого .кам-та счетчике не наступит переполнение. же счетчика, задавая в нем режим счета, Как только в 1-м счетчике 2.1 наступит пере- Сигналы на управляющих входах мульти полнение, та он будет сигнализировать об плексоров обеспечивают подключение к этом выдачей логической единицы на выход счетчику 2.1 первого синхравхода 7, а к признака переноса, которая поступит на 1-й счетчикам 22 - 2, К входа записи устрайст- вход шиФратора приоритетов 4. Эта вызова 9. При этом в счетчике 2,1 будет проис- . вет появление на выходе признака запроса ха "ить коррекция суммарного времени 25 шифратораприаритета 4 логической единирешения задачи 1-га канала через каждый цыкоторая через первый управляющий единичный интервал времени путем при- вход мультиплексоров 6.1 - б,К отключает бавления единицы к ега содержимому, второй синхровход 8 от синхровхадов счетСледующее (второе) задание через от- чиков, а также па входу стробиравания разкрытый блок элементов И 3.2 распределит решает работу дешифратора 5, Единичный ся на второй информационный выход 102, сигнал с выхода признака переноса счетчиа код времени решения этого задания запи- ка 2.1 через коммутатор 6,1 подклачит вход шетсявовторойсчетчик 2;2,Выхадперено- записи устройсгва 9 к синхровходу этого са счетчика 2.2 примет нулевое значение, счетчика.чта вызовет дальнейшее изменение кодов 35 Нулевые сигналы с выходов признака шифратора приоритетов 4 и дешифратора б, переноса остальных счетчиков через соотзакрытие одних и открытие других блоков ветствующие коммутаторы подключат перэлементов И. Одновременна счетчик 2,2 пе- вый синхровход 7. В этих счетчиков будет рейдет в режим счета, а к его синхровхаду продолжаться режим корректировки, В речерез коммутатор 6 2 подключится первый 40 зультате дешифрации кода с информационсинхровход 7, что обеспечит режим коррек- ных выходов шифратора приоритетов 4 на ции суммарного времени решения задач 1-м выходе дешифратара 5 появится логичевторого канала, Аналогичные действия бу- скал единица, которая, поступив на второй дут происходить до распределения К-го за- вход группы элементов И 3 1,разрешает дания, т.е, когда код задания пройдет через 45 передачу информации через 1-й канал, ОдК-й блок элементов И 3. К и код времени навременно логическая единица с 1-га выхорешения этого задания запишется в счет- да дешифратара 5 поступает на вход чик. При этом выход переноса счетчика 2, К разрешения записи счетчика 2,1 и перевопримет нулевое значение и на входах шиф- дит его в режим параллельной записи. Слератора приоритетов 4 можетбольше не ока дующее задание через открытый блок заться единичных сигналов, т.е, элементов И 3.1 распределится на 1-й инфарсодержимое всех счетчиков будет отличным мационный выход 10 1, а код времени решеат 111. Шифратор приоритетов 4 просиг- ния этого задания запишется в 1-й счетчик нализирует об этом путем выдачи нулевого 2,1. В итоге задание поступит в 1-ю ЭВМ, сигнала на выход признака запроса и темвремя выполнения заданий которой было самым заблокирует работу дешифратора 6минимальным.па входу стробирования. Таким образом, режим коррекции сумНа всехвыхадахдешифраторабустано- марного времени решения задания в счетвятсялогическиенули, которыезапретятпе- чике 1-га (1 =1,К) канала начинается тогда,становится равной суммарной загрузке на-.25 30 35 40 45 50 когда в 1-м счетчике будет записано число, отличное от кода "111" и в устройстве еще будет хотя бы один счетчик, содержимое которого равно "11,1", т,е. будет известен наименее загруженный канал.Режим коррекции в 1-м счетчике приостанавливается при записи числа, отличного от "111", в последний счетчик, содержимое которого было равным "111", т.е, когда содержимое всех счетчиков становится отличным от "11.1". При этом все без исклкчения счетчики переводятся в счетный режим и к их входам синхронизации подключается второй синхровход 8, В устройстве идет поиск наименее загруженного канала. Режим счета прекращается при достижении хотя бы в одном из счетчиков кода "111".Если содержимое 1-го счетчика не стало равным "11,1", то режим коррекции в нем продолжается и после режима счета.Режим коррекции в 1-м счетчике прекращается при достижении им числа "11.1", т,е, когда суммарная загрузка 1-го канала именее загруженного канала,На время действия синхроиМпульса записи работа шифратора приооитетов 4 блокируется путем подачи этого импульса с входа записи устройства 9 на вход стробирования шифратора приоритетов. При этом состояние выходов шифратора приоритетов остается неизменным до окончания дейст вия импульса записи, Это необходимо для предотвращения переключения каналов устройства во время поступления кода задания с информационного входа 1 на выход 10 1 1-го канала, Такое переключение могло бы возникнуть при достикении в результате коррекции )-м счетчиком (31) кода "111".Во время работы устройства может появится необходимость во временном отключении одного или нескольких каналов, например, из-за неисправности ЭВМ, Для отключения 1-й ЭВМ на вход блокировки 1,1 подается единица. При этом признак переноса счетчика 2принимает значение логического нуля, вследствие чего блок элементов И 3 1 будет закрыт. Устройство продолжает работу по распределению заданий с учетом отключенных каналов.П р и м е р. Рассмотрим для простоты в качестве примера 2-канальное устройство распределения заданий между ЭВМ, На вход устройства поступает поток заданий. Каждому заданию присвоим порядковый номер от 1 до М, момент поступления задания на входустройства ть время выполнения этого задания на любой из ЭВМ т и время 5 10 15 20 ожидания Т от момента поступления до момента начала обработки.Нике представлен пример из 3-х заданий:1 тЗадание 1 0 13Задание 2 8 10Задание 3 12 8В устройстве-прототипе задание 1 распределяется в канал 1, задание 2 в канал 2 и задание 3 в канал 2, так как канал 2 имеет минимальную загрузку и не отслеживается текущее время выполнеййя задания 1 по каналу 1, Это приводит к увеличению времени ожидания 3 задания Тз и увеличению общего времени выполнения пакета заданий То,В предлагаемом устройстве задание 1 распределится в канал 1, задание 2 - в канал 2 и задание 3 - в канал 1, так как вследствие отслеживания текущего времени минимальная загрузка в момент поступления задания 3 будет в канале 1, Это позволяет получить минимальное время ожидания задания на обработку Т 3 и общее время выполнения пакета заданий уменьшится до Т о,Формула изобретения Устройство для распределения заданий между ЭВМ, содержащее шифратор приоритетов, дешифратор и К каналов (К - число ЭВМ), причем каждый канал содержит счетчик и блок элементов И, информационный вход устройства соединен с первыми входами блоков элементов И и информационными входами счетчиков всех каналов устройства, выходы блоков элементов И всех каналов образуют группу выходов устройства, выход признака переноса счетчика 1-го канала (1 = 1, К) соединен с 1-м информационным входом шифратора приоритетов, выход признака запроса которого соединен с входом стробирования дешифрэтора, информационный выход шифратора приоритетов соединен с информационным входом дешифратора, 1-й выход которого соединен с вторым входом блока элементов И входом разрешения записи, счетчика 1-го канала, вход разрешения переноса которого является входом блокировки 1-го канала устройства, о т л и ч а ю щ е е с я тем, что, с целью расширения области применения устройства за счет минимизации времени обработки заданий вследствие учета времени ожидания заданияв каждый кайал устройства введен коммутатор, причем выход признака переноса счетчика 1-го канала соединен с первым управляющим входом коммутатора 1-го канала, выход которого соединен с синхровходом счетчика 1-го канала, выход признака запроса шифратора приоритетов1755280 12 едактор И.Касарда Техред У,Моргентал Корректор С.Лисин э 2894 Тираж ПодписноеВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб., 4/5 роизводственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 1 соединен с вторыми управляющими входами коммутаторов всех каналов, первый, второй и третий информационные входы коммутаторов всех каналов соединены соответственно с первым и вторым синхровходами устройства и входом записи устройства, который соединен с входом стробирования шифратора приоритетов.