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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (st)s G 06 F 9/46

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4840446/24 (22) 18.16.90

{46) 15.08.92. Бюл. М 30 (71) Киевский политехнический институт им.

50-летия Великой Октябрьской социалистической революции (72) А, Г. Накалюжный, Ю. И. Сидоренко, B.

П. Тарасенко и E. M. Швец (56) Авторское свидетельство СССР

ЬЬ 1277108, кл. G 06 F 9/46, 1987.

Авторское свидетельство СССР

% 4643303, кл. G 06 F 9/46, 1990. (54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ

ЗАДАНИЙ МЕЖДУ ЭВМ (57) Изобретение относится к вычислительной технике и может быть использовано для построения вычислительных комплексов, многопроцессорных вычислительных устИзобретение относится к вычислительной технике и может быть использовано при построении вычислительных комплексов.

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

» Ж 1755280 Al ройств. Цель изобретения — расширение области применения устройства за счет минимизации времени обработки заданий вследствие учета времени ожидания задания, Устройство содержит шифратор приоритетов, дешифратор и K каналов (К вЂ” число

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

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

Наиболее близким к изобретению по технической сущности является устройство для распределения заданий между Э ВМ, содержащее К качалов, в каждом канале счетчик, блок элементов И, один на все устройство шифратор и один дешифратор, причем информационный вход устройства подключен к первым входам блоков элемен1755280 тов И всех каналов, выходы которых являются выходами устройства, К недостаткам прототипа относится отсутствие учета пройденного времени обработки задания нэ i-й "ÂÌ при распределении вновь поступившего зэдэния, что приводит к увеличению общего времени обработки пакета заданий и увеличение времени ожидания задания от времени поступления до времени обработки в ЭВМ.

Цель изобретения — расширение области применения устройства за счет минимизации времени обработки заданий вследствие учета времени ожидания задания, Поставленная цель достигается тем, что в устройство для распределения заданий между ЭВМ, содер>кащее шифратор приоритетов,дешифратор и К каналов(К вЂ” число

38M), причем каждый канал содер>кит счетчик и блок элементов И, информационный вход устройства соединен с первыми входами блоков элементов И и информационными входами счетчиков всех каналов ус:юйства, выходы блоков элементов И всех каналов образуют группу выходов устройства, выхоц признака переноса счетчика

I-го канала Ii = 1, К) соединен с i-м информационным входом шифратора приоритетов, выход признака запроса которого соединен с входом стробирования дешифраторэ, информационный выход шифратора приоритетов соединен с информационным входом дешифраторэ, i-й выход которого соединен с вторым входом блока элементов И и входом разрешения записи счетчика i-го канала, вход разрешения переноса которого является входом блокировки 1-ro канала устройства, введены в каждый канал устройства коммутатор, причем признака переноса счетчика I-гг канала соединен с первым управляющим входом коммутатора

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

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

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

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

Устройство для распределения заданий мeæäó ЭВМ содержит информационный вход ", который подключен к информэционным входам счетчиков 2 и первым входам

20 блоков элементов ИЗ. В ыход признака переноса!-го счетчикэ 2. 1 подведен к I-му входу шифрэторэ приоритетов 4, к входу разрешения счета i ãî счетчика 2. i и к первому управляющему входу коммутатора I-го кана25 ла 5.!, Выход признака зэпросэ шифратора приоритетов 4 связэн с 2-M упрэвляющим входом коммутаторов 5. ф = 1, К) всех каналов и с входом стробирования дешифратора б. Информационный выход шифратора приЗО оритетов 4 подведен к информационному входу дешифрэтора б, 1-й выход которого подключен к второму входу блока элементов

3 i и к входу разрешения записи счетчика i-го канала 2. I. Вход синхронизации I-го счетчи35 кэ 2.1 соединен с выходом коммутатора1-го канала 5. I, к первому, второму и третьему входэм которого подведены соответственно первый синхровход 7, второй сиихровход 8 и вход записи устройства 9. Вход записи 9

40 подключен к входу стробирования шифратора приоритетов б, Выход блока элементов

И 3 „ i образует информационный выход

10.i i-ro канала. Выход рэзрешения переносэ счетчика i-го канапэ 2.1образует вход блокировки этого канала 11.1.

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

И 3 могут быть использованы микросхемы

К58ОВА86, первым входом которых служат информационные входы элементов, э вторым входом является вход, управляющий передачей информации на выход: при "1" нэ упрэвляющем входе информация передается с входом нэ выход; при "О" выходы перевоцятся в высокоомное состояние. Счетчики

2 могут быть реализовэны на микросхемах

К531ИЕ17, которые позволяют строить счет1755280

/

20

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

Микросхема шифратора имеет восемь информационных входов, вход синхрониза- 1 ции, выход переноса и информационный вь,ход (для кодирования номера одного из восьми входов используются три вывода).

При нулевом сигнале на входе синхронизации шифратор формирует двоичный код наиболее приоритетной возбу>кденной входной шины и сигнал выхода переноса.

При единичном сигнале на входе синхронизации входы блокируются, а на информационном выходе и выходе переноса будут 2 сохранены сигналы, зафиксированные ранее.

Устройство работает следующим образом, В исходном состоянии все 3ВМ свобод- 3 ны, находятся в работоспособном состоянии, по второму синхровходу 8 поступают импульсы, обеспечивающие быструю работу счетчиков 3, 1-3 . К в счетном режиме; по первому синхровходу 7 выдаются импуль- 3 сы, период поступления которых равен единичномуинтервалу времени,.принятомудля данной вычислительной системы.{ код времени решения любого задания определяется количеством этих интервалов); на вход записи 9 поступает нулевой сигнал; счетчики 2 . 1 — 2;К установлены в единичное

COCTOSIHMÇ (11...1), HB BCe входы 6JlQKMp08YM

11. 1 — 11. К подаются логические единицы, разрешающие работу соответствующих ка- 4 налов. При этом с выходов признака переноса всех счетчиков 2 .1 — 2. К логические единицы поступают на информационные входы шифратора приоритетоь 4. разрешает дешифрацию кода. Код представляет собой номер первого установленного в единичное состояние счетчика. В исходном состоянии будет номер первого счетчика 2.1, который поступает с информационнога выхода шифратора приоритетов.

В результате дешифрации единичный сигнал с первого выхода дешифратора подается на вход разрешения записи счетчика 2.1, устанавливая его в режим параллельной записи, и на второй вход блока элементов И вЂ” К 3,1, открывая его для обмена информации. Логические нули на остальных выходах дешифратора 5 запрещают передачу информации через соответствующие этим входам блоки элементов И (3.2 — 3 . К) и одновременно поступают на входы разрешения записи счетчиков 2.2 — 2, К и переводят из в режим счета-хранения, Единичный сигнал с выхода признака запроса; шифратора приоритетов поступает также на вторые управляющие входы acex K коммутаторов и тем самым отключает второй синхровход 8 от синхровхода всех счетчиков. В то >ке время сигнал с выхода признака переноса i-ãî (i = 1,K) счетчика поступает на вход разрешения счета этого же счетчика и на первый управляющий вход i-го коммутатора 5 ..i. При нулевом сигнале на входе разрешения записи нулевой сигнал на входе разрешения счета задает режим счета, а единичный задает режим хранения, В исходном состоянии с выходов признаков переноса счетчиков поступают единичные сигналы, следовательно, счетчики 2.2 — 2.К находятся в режиме хранения. Сигналы на первом и втором управляющих входах коммутаторов 6.1 — 6. К обеспечивают подключение к входам синхронизации счетчиков

2.1 — 2.К входа записи устройства 9.

Код задания и код времени решения с информационного входа 1 устройства поступает через открытый блок элементов И

3,1 на выход 10.1 первого канала и далее в соответствующую 3ВМ. Кроме того, код времени выполнения задания записывается в счетчик 2.1 по синхроимпульсу записи, поступающему через коммутатор 6.1 с входа записи устройства 9 (синхроимпульс записи поступает и на остальные счетчики

2.2-2. К, но при этом содержимое не меняется, так как они находятся в режиме хранения). В результате этого на выходе признака переноса счетчика 2.1 появится нулевой сигнал. Это изменение вызовет изменение выходного кода шифратора приоритетов 4 и соответствующее изменение кода на выходе дешифратора 6, В результате этого логическая единица появится на втором выходе

1755280

8 дешифратора 5, а на остальных выходах ус- редачу информации через блоки элементов тановятся логические нули.. И 3,1 — 3;К и переведут все счетчики 2;1—

Логическая единица на втором выходе 2=K в режим счета-хранения, При этом нуледешифратора 6 разрешает передачу инфор- вые сигналы с признаков переноса счетчимации через 3 2 элементов И, и одновре- 5 коп задают в счетчиках режим счета.

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

3,1,3,3,3.Киодновременнопереводятсчет- во все счетчики 2.1 — 2.К. При этом они чики2,1,2,3 — 2.,К врежимсчета-хранения.. декрементируют содержимое, если время

При этом с выходов признака счетчиков 2.3 решения записано в прямом коде (или инк— 2.К по прежнему поступают единичные реме.- тируют содержимое, если время ресигналы, Поэтому эти счетчики будут нахо- 15 шения записано в обратном коде), Режим диться в режиме хранения, а с выхода при- счета (поиск наименее загруженной 3BM) знака переноса счетчика 2;1 нулевой сигнал будет продолжаться до тех пор, пока в капоступает на вход разреления счета этого .ком-то счетчике не наступит переполнение. же счетчика, задавая в нем режим счета, Как только í I-м счетчике 2.1 наступит переСигналы на управляющих входах мульти- 20 полнение, то он будет сигнализировать об плексоров обеспечивают подключение к этом выдачей логической единицы на выход счетчику 2.1 первого синхровхода 7, а к признака переноса, которая поступит íà I-й счетчикам 2.2 — 2, K входа записи устройст- вход шифратора приоритетов 4. Это вызова 9. При этом в счетчике 2„1 будет проис- . вет появление на выходе признака запроса хс, - òü коррекция суммарного времени "-5 шифратора приоритета 4 логической единирешения задачи 1-го канала через каждый цы, которая через первый управляющий единичный интервал времени путем при- вход мультиплексоров 6.1 — 6,К отключает бавления единицы к его содержимому. второй синхровход 8 от синхровходов счетСледующее (второе) задание через от- чиков, а также по входу стробирования разкрытый блок элементов И 3.2 распределит- 0 решает ра" îòó дешифратора 5, Единичный ся на второй информационный выход 10 2, сигнал с выхода признака переноса счетчиа код времени решения этого задания запи- ка 2.1 через коммутатор 6,! подкл1очит вход шется во второй счетчик 2;2, Выход перено- записи устройс - a 9 к синхровходу этого са счетчика 2.2 примет нулевое значение, счетчика. что вызовет дальнейшее изменение кодов 35 Нулевые сигналы с выходов признака шифратора приоритетов 4 и дешифратора 6, переноса остальных счетчиков через соотзакрытие одних и открытие других блоков ветствующие коммутаторы подключат перэлементов И. Одновременно счетчик 2,2 пе- вый синхровход 7. В этих счетчиков будет рейдет в режим счета, а к его синхровходу продолжаться режим корректировки. В речерез коммутатор 6. 2 подключится первый 40 зультате дешифрации кода с информационсинхровход 7, что обеспечит режим коррек- ных выходов шифратора приоритетов 4 на ции суммарного времени решения задач I"M выходе дешифратора 5 появится логичевторого канала. Аналогичные действия бу- ская единица, которая, поступив на второй дут происходить до распределения К-ro за- вход группы элементов И 3 1, разрешает. дания, т.е, когда код задания пройдет через 45 передачу информации через I-й канал, ОдК-й блок элементов И 3. К и код времени новременно логическая единица с I-го выхорешения этого задания запишется в счет- да дешифратора 5 поступает на вход чик. При этом выход переноса счетчика 2,К разрешения записи счетчика 2,I и перевопримет нулевое значение и на входах шиф- дит его в режим параллельной записи. Слератора приоритетов 4можетбольше не ока- 50 дующее задание через открытый блок заться единичных сигналов, т.е, элементовИ3.1распределитсянаi-йинфорсодержимое всех счетчиков будет отличным мационный выход 10 I, а код времени решеот 11...1. Шифратор приоритетов 4 просиг- ния этого задания запишется в I-й счетчик нализирует об этом путем выдачи нулевого 2.I. В итоге задание поступит в I-e 3ВМ, сигнала на выход признака запроса и тем время выполнения заданий которой было самым заблокирует работу дешифратора 6 минимальным. по входу стробирования. Таким образом, режим коррекции сумНа всех выходах дешифратора бустано- марного времени Решения задания в счетвятсялогическиенули,которыезапретятпе- чике I-го (! =1,К) канала начинается тогда, 1755280

10 становится равной суммарной загрузке на-. 25

35

45

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

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

"11 ...1".

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

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

10 1 i-го канала. Такое перекл очение могло бы возникнуть при дости>кении в результате коррекции j-м счетчиком (J

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

Пример. Рассмотрим для простоты в качестве примера 2-канальное устройство распределения заданий между ЭВМ, На вход устройства поступает поток заданий.

Каждому заданию присвоим порядковый номер от 1 до М, момент поступления задания на вход устройства ti, время выполнения этого задания на любой из 3BM t и время

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

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

tj tl

Задание 1 0 13

Задание 2 8 10

Задание 3 12 8

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

2 и задание 3 — в канал 1, так как вследствие отслеживания текущего времени минимальная загрузка в момент поступления задания

3 будет в канале 1. Это позволяет получить минимальное время ожидания задания на обработку Т з и общее время выполнения

1 пакета заданий уменьшится до Т р, Формула изобретения

Устройство для распределения заданий между ЭВМ, содержащее шифратор приоритетов, дешифратор и К каналов (К вЂ” число

ЭВМ), причем каждый канал содержит счетчик и блок элементов И, информационный вход устройства соединен с первыми входами блоков элементов И и информационными входами счетчиков всех каналов устройства, выходы блоков элементов И всех каналов образуют группу выходов устройства, выход признака переноса счетчика

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

i-го канала, выход которого соединен с синхровходом счетчика 1-ro канала, выход признака запроса шифратора приоритетов

1755280

Редактор И.Касарда Техред M,Mîðãåíòàë Корректор С.Лисина

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

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., 4/5

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101 соединен с вторыми управляющими входами коммутаторов всех каналов, первый, второй и третий информационные входы коммутаторов всех каналов соединены соответственно с первым и вторым синхровходами устройства и входом записи устройства, который соединен с входом стробирования шифратора приоритетов.