Устройство для распределения заданий между ЭВМ Советский патент 1992 года по МПК G06F9/46 

Изобретение относится к вычислительной технике и может быть использовано при построении вычислительных комплексов.

Известны устройства для распределе- „ния заданий между ЭВМ содержащие три счетчика, три сумматора вычислителя, три элемента сравнения, три элемента ИЛИ, девять блоков элементов И, генератор импульсов; три канала, каждый из которых содержит два блока регистров, накапливающий сумматор, схему сравнения, группу схем сравнения, блок элементов И, первый и второй элементы И, элементы ИЛИ; три канала, в каждом канале счетчик, комбинационный сумматор, схема сравнения, блок

элементов И, первый и второй элементы И, элемент ИЛИ.

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

Наиболее близким к изобретению по технической сущности является устройство для распределения заданий между ЭВМ, содержащее К каналов, в каждом канале счет- чик, блок элементов И, один на все устройство шифратор и один дешифратор, причем информационный вход устройства подключен к первым входам блоков элеменГО

ов И всех каналов, выходы которых являютя выходами устройства.

К недостаткам прототипа относится отутствие учета пройденного времени обрз- отки задания на 1-й ЭВМ при аспределении вновь поступившего задаия, что приводит к увеличению общего вре- ени обработки пакета заданий и величение времени ожидания задания от времени поступления до времени обработки в ЭВМ. -

. Цель изобретения - расширение обла- ти применения устройства за счет минимизации времени обработки заданий вследствие учета времени ожидания задания.

Поставленная цель достигается тем, что в устройство для распределения заданий между ЭВМ, содержащее шифратор приоритетов, дешифратор и К каналов(К-число ЭВМ), причем каждый канал содержит счетчик и блок элементов И, информационный вход устройства соединен с первыми входами блоков.элементов И и информационными входами счетчиков всех каналов устройства, выходы блоков элементов И всех каналов образуют группу выходов устройства, выход признака переноса счетчика 1-го канала (I I, К) соединен с 1-м информационным входом шифратора приоритетов, выход признака запроса которого соединен с входом стробирования дешифратора, информационный выход шифратора приоритетов соединен с информационным входом дешифратора, i-й выход которого соединен с вторым входом блока элементов И и входом разрешения записи счетчика 1-го канала, вход разрешения переноса которого является входом блокировки 1-го канала устройства, введены в каждый кэнал устройства коммутатор, причем признака переноса счетчика 1-гг канала соединен с первым управляющим входом коммутатора 1:го канала, выход которого соединен С син- хровходом счетчика 1-го канала, выход признака запроса шифратора приоритета соединен вторыми управляющими входами коммутаторов всех каналов, первый, второй и третий информационные входы коммутаторов всех каналов соединены соответственно с первым и вторым синхровходами устройства и входом записи устройства, который соединён с входом стробирования шифратора приоритетов.

Сущность изобретения заключается в следующем.

Благодаря введению в каждый канал коммутатора и соответствующему изменению связей в устройство появилась возможность корректировать изменение текущего

времени обработки заданий во всех каналах загруженных ЭВМ, что позволяет определить минимально загруженную ЭВМ с учетом пройденного времени решения заданий

на всех ЭВМ и распределить вновь поступившее задание з канал с минимальной загрузкой. Так как эта возможность отсутствовала в устройстве прототипа, предлагаемое устройство позволяет сократить время обработки пакета заданий и время ожидания на обработку вновь поступившего задания.

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

Устройство для распределения заданий между ЭВМ содержит информационный вход 1, который подключен к информационным входам счетчиков 2 и первым входам

блоков элементов ИЗ, Выход признака переноса 1-го счетчика 2. I подведен к 1-му входу шифратора приоритетов 4, к входу разрешения счета 1-го счетчика 2. i и к первому управляющему входу коммутатора 1-го канала 5. i. Выход признака запроса шифратора приоритетов А связан с 2-м управляющим входом коммутаторов 5. f( 1, К) всех каналов и с входом стробиросания дешифратора 6. Информационный выход шифратора приоритетов 4 подведен к информационному входу дешифратора 6, 1-й выход которого подключен к второму входу блока элементов 3 i и к входу разрешения записи счетчика 1-го канала 2. i. Вход синхронизации 1-го счетчика 2 . i соединен с выходом коммутатора 1-го канала 5. 1, к первому, второму и третьему входам которого подведены соответственно первый синхровход 7, второй симхровход 8 и вход записи устройства 9. Вход записи 9

подключен к входу стробирования шифратора приоритетов 6. Выход блока элементов ИЗ образует информационный выход 10,1 i-го канала. Выход разрешения переноса счетчика i-ro канала 2 ,1 образует вход

блокировки этого канала 11.1.

Предлагаемое устройство распределения заданий может быть выполнено с использованием элементов различных серий. Так, например, в качестве группы элементов

И 3 могут быть использованы микросхемы К580ВА86, первым входом которых служат информационные входы элементов, а вторым входом является вход, управляющий передачей информации на выход: при 1 на

управляющем входе информация передается с входом на выход; при О выходы переводятся в высокоомное состояние. Счетчики 2 могут быть реализованы на микросхемах К531ЙЕ17, которые позволяют строить счетчики с разрядностью, кратной 4. Микросхема К531ИЕ17 имеет четырехразрядный информационный вход, вход разрешения счета, вход разрешения переноса, тактовый вход (в описании ему соответствует вход синхронизации), вход записи (вход разрешения записи), вход направления счета (для прямых кодов используется вычитание, для обратных кодов - суммирование) и выход переноса. В качестве шифратора приорите- тов 4, коммутаторов 5. 1 - 5 . К. дешифратора б могут быть выбраны соответственно микросхемы К500ИВ165, К155КП, К155ИД4. Микросхема шифратора имеет восемь информационных входов, вход синхрониза- ции, выход переноса и информационный выход (для кодирования номера одного из восьми входов используются три вывода). При нулевом сигнале на входе синхронизации шифратор формирует двоичный код на- иболее приоритетной возбужденной входной шипы и сигнал выхода переноса. При единичном сигнале на входе синхронизации входы блокируются, а на информационном выходе и выходе переноса будут сохранены сигналы, зафиксированные ранее.

Устройство работает следующим образом.

В исходном состоянии все ЭВМ свобод- ны, находятся в работоспособном состоянии, по второму синхровходу 8 поступают импульсы, обеспечивающие быструю работу счетчиков 3.1-3 , К в счетном режиме; по первому синхровходу 7 выдаются импуль- сы, период поступления которых равен единичному интервалу времени,принятому для данной вычислительной системы ( код времени решения любого задания определяется количеством этих интервалов); на вход записи 9 поступает нулевой сигнап; счетчики 2 .1 -2 ;К установлены в единичное состояние (11...1), на все входы блокировки 11. 1 - 11. К подаются логические единицы, разрешающие работу соответствующих ка- налов. При этом с выходов признака переноса всех счетчиков 2 .1 - 2. К логические единицы поступают на информационные входы шифратора приоритетов 4.

Работа шифратора приоритетов 4 разрешена нулевым сигналом, поступающим на его вход стробирования с синхровхода записи 9. При наличии хотя бы одной единицы на входах шифратора приоритетов 4, по- следний выдает единицу на выход признака запроса, которая поступает на вход строби- рования дешифратора 5. Единичный сигнал на входе стробирования дешифратора 5

разрешает дешифрацию кода. Код представляет собой номер первого установленного в единичное состояние счетчика. В исходном состоянии будет номер первого счетчика 2.1, который поступаете информационного выхода шифратора приоритетов. В результате дешифрации единичный сигнал с первого выхода дешифратора подается на вход разрешения записи счетчика 2.1, устанавливая его в режим параллельной записи, и на второй вход блока элементов И К 3,1, открывая его для обмена информации. Логические нули на остальных выходах дешифратора 5 запрещают передачу информации через соответствующие этим входам блоки элементов И (3.2 - 3 . К) и одновременно поступают на входы разрешения записи счетчиков 2.2-2 .К и переводят из в режим счета-хранения.

Единичный сигнал с выхода признака запроса1 шифратора приоритетов поступает также на вторые управляющие входы всех К коммутаторов и тем самым отключает второй синхровход 8 от синхровхода всех счетчиков, В то же время сипнал с выхода признака переноса 1-го (I 1,К) счетчика по- сгупает на вход разрешения счета этого же счетчика и на первый управляющий сход -го коммутатора 5 .4. При нулевом сигнале на входе разрешения записи нулевой сигнал на входе разрешения счета задает режим счета, а единичный задает режим хранения, В исходном состоянии с выходов признаков переноса счетчиков поступают единичные сигналы, следовательно, счетчики 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, В результате этого логическая единица появится на втором выходе

дешифратора 5, а на остальных выходах установятся логические нули.

Логическая единица на втором выходе дешифратора 6 разрешает передачу информации через 3t2 элементов И, и одновременно переведет счетчик 2,2 в режим параллельной записи кода с информационного входа 1. Логические нули на остальных выходах дешифратора 5 запрещают передачу информации через блоки элементов И 3,1,3.3,3. Ки одновременно переводят счетчики 2,1,213 - 2 К в режим счета-хранения. При этом с выходов признака счетчиков 2,3 - 2,К по прежнему поступают единичные сигналы. Поэтому эти счетчики будут находиться в режиме хранения, а с выхода признака переноса счетчика 2.1 нулевой сигнал поступает на вход разрешения счета этого же счетчика, задавая в нем режим счета. Сигналы на управляющих входах мультиплексоров обеспечивают подключение к счетчику первого синхровхода 7, а к счетчикам 2.2 -2. К входа записи устройства 9. При этом в счетчике 2И будет проис- хс ять коррекция суммарного времени решения задачи 1-го канала через каждый единичный интервал времени путем прибавления единицы к его содержимому.

Следующее (второе) задание через открытый блок элементов И распределится на второй информационный выход 10-2, а код времени решения этого задания запишется во агорой счетчик 2.-2. Выход переноса сметчика примет нулевое значение, что вызовет дальнейшее изменение кодов шифратора приоритетов 4 и дешифратора б, закрытие одних и открытие других блоков элементов И. Одновременно счетчик 2,2 перейдет в режим счета, а к его синхровходу через коммутатор 6-2 подключится первый синхровход 7, что обеспечит режим коррекции суммарного времени решения задач второго канала. Аналогичные действия будут происходить до распределения К-ro задания, т.е. когда код задания пройдет через К-й блок элементов И 3-К и код времени решения этого задания запишется в счетчик. При этом выход переноса счетчика 2. К примет нулевое значение и на входах шифратора приоритетов А может больше не оказаться единичных сигналов, т.е. содержимое всех счетчиков будет отличным от 11...1. Шифратор приоритетов А просигнализирует об этом путем выдачи нулевого сигнала на выход признака запроса и тем самым заблокирует работу дешифратора б по входу стробирования.

На всех выходах дешифратора 6 устаио- . вятся логические нули, которые запретят пеи

редачу информации через блоки элементов И 3,1 - 3,К и переведут вес счетчики 2 .1 - 2, К в режим счета-хранения. При этом нулевые сигналы с признаков переноса счетчи5 коп задают в счетчиках режим счета. Одновременно нулевой сигнал с выхода переноса шифратора приоритетов А поступит на первый управляющий вход всех мультиплексоров 6-1 - 6, К. В результате этого им10 пульсы с второго синхровхода 8 поступают во все счетчики 2.1 - 2. К. При этом они декрементируют содержимое, если время решения записано в прямом коде (или инк- реме: (тируют содержимое, если время ре15 шения записано в обратном коде). Режим счета (поиск наименее загруженной ЭВМ) будет продолжаться до тех пор, пока в каком-то счетчике не наступит переполнение. Как только в l-м счетчике 2.I наступит переполнение, то он будет сигнализировать об этом выдачей логической единицы на выход признака переноса, которая поступит на 1-й вход шифратора приоритетов 4. Это вызовет появление на выходе признака запроса шифратора приоритета 4 логической единицы, которая через первый управляющий вход мультиплексоров 6-1 - 6-К отключает второй синхровход 8 от синхровходов счетчиков, а также по входу стробирования разрешает работу дешифратора 5. Единичный сигнал с выхода признака переноса с етчи- ка 2 J через коммутатор 6.I подключит вход записи устройства 9 к синхровходу этого счетчикз.

Нулевые сигналы с выходов признака переноса остальных счетчиков через соответствующие коммутаторы подключат первый синхропход 7. В этих счетчиков будет продолжаться режим корректировки. В результате дешифрации кода с информационных выходов шифратора приоритетов 4 на i-м выходе дешифратора 5 появится логическая единица, которая, поступив на второй вход группы элементов И 3- ,разрешает передачу информации через 1-й канал, Одновременно логическая единица с 1-го выхода дешифратора 5 поступает на вход разрешения записи счетчика 2,1 и переводит его в режим параллельной записи. Следующее задание через открытый блок элементов И 3 Л распределится на 1-й информационный выход 10-1, а код времени решения этого задания запишется в 1-й счетчик 2,1. В итоге задание поступит в 1-ю ЭВМ, время выполнения заданий которой было минимальным.

Таким образом, режим коррекции суммарного времени решения задания в счетчике 1-го (I 1,К) канала начинается тогда,

20

25

30

35

40

45

50

55

когда з l-м счетчике будет записано число, отличное от кода 11...1 и в устройстве еще будет хотя бы один счетчик, содержимое которого равно 11...1, т.е. будет известен наименее загруженной канал

Режим коррекции в i-м счетчике приостанавливается при записи числэ, отличного от 11...1, в последний счетчик, содержимое которого было равным 11...1В, т.е. когда содержимое всех счетчиков становится отличным от 11...1. При этом все без исключения счетчики переводятся в счетный режим и к их входам синхронизации подключается второй синхровход 8. В устройстве идет поиск наименее загруженного канала. Режим счета прекращается при достижении хотя бы в одном из счетчиков кода 11...Г.

Если содержимое 1-го счетчика не стало равным 11...1, то режим коррекции в нем продолжается и после режима счета.

Режим коррекции в i-м счетчике прекращается при достижении им числа 11.„Г, т.е. когда суммарная загрузка i-го канала становится равной суммарной загрузке наименее загруженного канала.

На время действия синхроимпульса записи работа шифратора приоритетов 4 блокируется путем подачи этого импульса с входа записи устройства 9 на вход строби- рования шифратора приоритетов. При этом состояние выходов шифратора приоритетов остается неизменным до окончания действия импульса записи. Это необходимо для предотвращения переключения каналов устройства сзо время поступления кода задания с информационного входа 1 на выход 10 i-ro канала. Такое переключение могло бы возникнуть при достижении в результате коррекции j-м счетчиком () кода 11...1.

Во время работы устройства может появится необходимость во временном отключении одного или нескольких каналов, например, из-за неисправности ЭВМ. Для отключения i-й ЭВМ на вход блокировки 1.1 подается единица. При этом признак переноса счетчика 2.1 принимает значение логического нуля, вследствие чего блок элементов И 3 i будет закрыт. Устройство продолжает работу по распределению заданий с учетом отключенных каналов.

Пример. Рассмотрим для простоты в качестве примера 2-канальное устройство распределения заданий между ЭВМ. На вход устройства поступает поток заданий. Каждому заданию присвоим порядковый номер от 1 до М, момент поступления задания на вход устройства ti, время выполнения этого задания на любой из ЭВМ t j и время

ожидания TI от момента поступления до момента начала обработки.

Ниже представлен пример из 3-х заданий:

titi

Задание 1013

Задание 2 810

Задание 3 128

В устройстве-прототипе задание 1 рас0 пределяется в канал 1, задание 2 в канал 2 и задание 3 в канал 2, так как канал 2 имеет минимальную загрузку и не отслеживается текущее время выполнения задания 1 по каналу 1. Это приводит к увеличению време5 ни ожидания задания Тз и увеличению общего времени выполнения пакета заданий Т0.

В предлагаемом устройстве задание 1 распределится в канал 1, задание 2 - в канал

0 2 и задание 3 - в канал 1, так как вследствие отслеживания текущего времени минимальная загрузка в момент поступления задания 3 будет в канале 1. Это позволяет получить минимальное время ожидания задания на

5 обработку Т1з и общее время выполнения пакета заданий уменьшится до Т1о. Формула изобретения Устройство для распределения заданий между ЭВМ, содержащее шифратор при0 оритетов, дешифратор и К каналов (К-число ЭВМ), причем каждый канал содержит счетчик и блок элементов И, информационный вход устройства соединен с первыми входами блоков элементов И и информэционны5 ми входами счетчиков всех каналов устройства, выходы блоков элементов И всех каналов образуют группу выходов устройства, выход г физнака переноса счетчика i-ro канала (I 1, К) соединен с 1-м информа0 ционным входом шифратора приоритетов, выход признака запроса которого соединен с входом стробирования дешифратора, информационный выход шифратора приоритетов соединен с информационным входом

5 дешифратора, i-й выход которого соединен с вторым входом блока элементов И входом разрешения записи, счетчика 1-го канала, вход разрешения переноса которого является входом блокировки 1-го канала устройст0 ва, отличающееся тем, что, с целью расширения области применения устройства за счет минимизации времени обработки заданий вследствие учета времени ожидания задания, в каждый канал устройства

5 введен коммутатор, причем выход признака переноса счетчика 1-го канала соединен с первым управляющим входом коммутатора 1-го канала, выход которого соединен с син- хровходом счетчика 1-го канала, выход признака запроса шифратора приоритетов

соединен с вторыми управляющими входами коммутаторов всех каналов, первый, второй и третий информационные входы коммутаторов всех каналов соединены соответственно с первым и вторым синхровхо- дами устройства и входом записи устройства, который соединен с входом стробирования шифратора приоритетов.

Изобретение относится к вычислительной технике и может быть использовано для построения вычислительных комплексов, многопроцессорных вычислительных устройств. Цель изобретения - расширение области применения устройства за счет мини- мизацин времени обработки заданий вследствие учета времени ожидания задания. Устройство содержит шифратор приоритетов, дешифратор и К каналов (К- число ЭВМ). Каждый канал имеет счетчик суммарной загрузки канала, коммутатор и блок эле- ментов И, Устройство определяет минимально загруженную ЭВМ с учетом пройденного времени обработки ранее поступивших заданий и таким образом позволяет сократить время обработки заданий и время ожидания на обработку вновь поступившего задания. Выбор нужного канала осуществляется путем анализа состояний выходов признаков переносов сче тчиков всех незаблокированных каналов. 1 ил.

Редактор И.Касарда

Техред М.Моргентал

Заказ 2894ТиражПодписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж-35, Раушская наб., 4/5

Корректор С.Лисина