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

 

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

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

РЕСПУБЛИК (я)ю G 06 F 15/20, 15/419

ОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ЕДОМСТВО СССР

OCflATEHT СССР) .1..". МИ - и й%6йй

ЛИСАНИЕ ИЗОБ ЕТЕНИЯ.: "1QTF А

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (P1) 4923106/24 !

{ 2) 29.03.91

6) 30.08.93. Бюл. М 32

2) В.H. Торопов, П,Л. Прокопьев, В.П.Бубов, В.Ю. Волнянский и Р,Ф. Генерозова

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

037267, кл. С 06 F 15/20, 1983.

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

1427381, кл. С 06 F 15/20, 1988.

4) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ

АДАЧ В ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЕ

7) Устройство относится к вычислительной хнике., в частности к устройствам распрееления задач в вычислительной системе, и

Изобретение относится к вычислительой технике, в частности к устройствам для аспределения задач в вычислительной ситеме, Целью изобретения является увеличеие количества обслуженных задач за диективное время в вычислительной системе, оставленная цель достигается тем, что в стройство, содержащее матрицу АхА триг. еров (где n — число задач), первую и вторую руппы блоков элементов И, группу элеменов ИЛИ-НЕ, первую и вторую группу элеентов И„группу триггеров, первый и торой и третий элементы ИЛИ, элемент ¹ ервый элемент задержки, первую группу егистров, блок элементов ИЛИ, первый и торой блоки преобразования кодов, матриу элементов сравнения, причем P-й инфорационный вход устройства подключен к ходам установки в "1" триггеров P-й строки атрицы триггеров (Р=1, и, где n — число адач), К-й вход (К=1, п) номера задачи уст,, БЫ„„183731б А1 может быть использовано в управляющих вычислительных системах. Целью настоящего изобретения является увеличение количества обслужен ных задач за директивное время в вычислительной системе путем назначения для каждой задачи динамического приоритета, Поставленная цель достигается за счет введения в состав устройства третьей группы элементов И, второй и третьей групп регистров, регистра, блока элементов И, первой и второй групп элементов задержки, третьей группы блоков элементов И, группы вычитателей и соответствующих связей. 1 ил. ройства соединен с информационным входом Р-го регистра первой группы, вход запуска устройства соединен с первым входом первого элемента ИЛИ и входами установки в "0" триггеров группы, К-й вход сброса устройства соединен с входами установки в "0" триггеров К-й строки матрицы, выход KP-го триггера матрицы подключен к К-му входу

P-го элемента ИЛИ вЂ” НЕ группы, выход первого элемента ИЛИ соединен с первым входом элемента И, выходы элементов

ИЛИ вЂ” НЕ группы подключены к соответствующему входу второго элемента ИЛИ, первым входам элементов И первой группы, выходы которых соединены с входами установки в "1" триггеров группы и с вторыми входами блоков элементов И первой группы, выход М-го разряда Р-го регистра соединен с М-м входом соответственно P-го блока элементов И первой группы, выходы триггеров группы с (n+1)-ми входами элементов ИЛ И вЂ” Н Е группы, выход второго эле1837316 мента ИЛИ соединен с выходом "конец работы" устройства и с вторым входом элемента И, выход которого через элемент задержки соединен с (и+2)-м входом первого элемента ИЛИ, с первым входом блоков . элементов И второй группы и синхровыходом устройства, группа выходов блока элементов ИЛИ соединена с вторыми входами блоков элементов И второй группы, выходы которых соединены с соответствующим информационным выходом устройства, выход третьего элемента ИЛИ соединен с третьим входом элемента И, группа входов готовности устройства подключена к группе входов первого преобразователя кодов, группа выходов которого соединена с группой выходов готовности устройства, с третьими входами блоков элементов И второй группы и с группой входов третьего элемента ИЛИ, выход Р-го элемента И второй группы подключен к P-му входу второго блока преобразования кодов группы, группа выходов которого соединена с вторыми входами элементов И первой группы. В него дополнительно введены третья группа элементов И, вторая и третья группа регистров, регистр, блок элементов И, первая и вторая группа элементов задержки, третья группа блоков элементов И, группа вычитателей, причем выход Р-го элемента ИЛИ-НЕ группы подключен к первому входу Р:го элемента И третьей группы, второй вход которого соединен с выходом первого элемента ИЛИ, выход P-го элемента И третьей группы подключен к P-м элементам задержки первой и второй группы. и по вторым входам блоков элементов И третьей группы, К-й вход времени решения задачи устройства соединен с информационным входом P-го регистра второй группы, выход М-го разряда которого подключен к М-му разряду первой группы информационных входов P-го коммутатора, к -му разряду второй группы информационных входов всех коммутаторов подключен

t-й выходной разряд регистра, информационные входы которого подключены к выходам блока элементов И, с первыми входами которого соединены входы установки текущего времени, выходы P-х элементов задержки первой и второй группы подключены соответственно к первому и второму управляющим входам Р-го коммутатора, М-й разряд информационного выхода P-го коммутатора соединен с М-м разрядом первой группы информационных входов Р-го вычитателя группы, г-й информационный выход которого подключен к первым входам

r-ro разряда РК-ых (P=1, (п-1), К=(Р+ 1), n) и ко вторым входам r-го разряда РК-ых элементов сравнения матрицы, выход признака

"Меньше" PK-ro элемента сравнения матрицы соединен с (К-1) входом, а выход признака "Больше" с К-ым входом P-го элемента И второй группы, К-й вход директивного времени окончания решения задачи устройства соединен с информационным входом P-го регистра третьей группы, выход М-го разряда которого соединен с М-м входом Р-го блока элементов третьей группы, выход t-го

10 разряда которого соединен с t ì разрядом второй группы информационных входов вычитателя группы, выход первого элемента

ИЛИ подключен к входам установки в "0" вычитателей устройства и ко вторым входам

15 блока элементов И. Схема устройства при-ведена на фиг. 1.

Устройство содержит матрицу 1 размером пхп (п — число задач) из триггеров 2, третью группу элементов И 3, вторую группу

20 регистров 4, регистр 5, блок элементов И 6, первый и второй блоки 7 преобразования кодов, содержащих блок элементов И-НЕ S, блок элементов ИЛИ-НЕ 9, первую группу элементов И 10, группу триггеров 11 ° первый элемент ИЛИ 12, элемент И 13, первый элемент 14 задержки, второй элемент ИЛИ

15, первую группу регистров 16, первую группу блоков элементов И 17, блок элементов ИЛИ 18, первую группу элементов 19

30 задержки, матрицу элементов 20 сравнения, вторую группу элементов И 21, вторую группу блоков элементов И 22, третий элемент ИЛИ 23, вторую группу элементов 24 задержки, третью группу регистров 25, 35 третью rpyony блоков элементов И 26, групп у 27 вычитател ей, группу 28 коммутаторов, выход 29 конца работы устройства, сигнальный выход 30 готовности устройства, группу информационных выходов 31 устройства, 40 выход 32 синхронизации устройства, группу входов установки в единицу устройства 33, группу входов 34 номера задачи устройства, вход 35 запуска устройства, группу входов

36 установки в ноль устройства, вход 37 ус45 тановки текущего времени, группу входов

38 времен решения задачи устройства, группу входов 39 директивного времени окончания решения задачи устройства, входы 40 готовности устройства. Увеличение количе50 ства обслуженных задач за директивное время в вычислительной системе достигается за счет назначения для каждой задачи динамического приоритета. Динамический приоритет (П ) задачи вычисляется по спе55 дующей формуле: и т-т -т, где Г-директивное время окончаниярешения задачи(время не позже которого задача должна быть решена);

Т вЂ” текущее время, t

1837316

T — время решения задачи (априорно звестно).

Устройство работает следующим обраом. В исходном состоянии триггеры 2, 11 и

ычитатели 27 обнулены. Первоначально в риггеры 2 по входам заносится информаия о топологии графа (вершины которого оответствуют задачам, а ветви информацинно-управляющим связям между ними). омер триггера, установленного в единичое состояние, определяется пересечением троки с номером, равным номеру начальой вершины ветви, и столбца с номером, авным номеру ее конечной вершины. В оответствующий регистр 4 по входу 38 заосится планируемое время решения задаи на ЭВМ, в соответствующий регистр 25 о входу 39 — директивное время выполнеия операции, в соответствующий регистр

6 по входу 34 — код номера задания и исодные данные для его выполнения, В рабое устройства можно выделить три этапа. На ервом производится определение незавиимых заданий. На выходах соответствуюих элементов ИЛИ вЂ” НЕ 9 в столбцах, оторые соответствуют начальным вершиам информационно-управляющего графа, оявятся высокие потенциалы, т.к. начальые вершины не содержат входящих ветей, и триггеры 2 в этих. столбцах находятся нулевом состоянии. Импульс запуска по ходу 35 устройства устанавливают в нулеое состояние триггеры 11, и пройдя через лемент ИЛИ 12 поступает на следующие лементы: открывает элемент И 6 и по входу 37 в егистр 5 заносится значение текущего вреени из счетчика времени вычислительной истемы; открывает те элементы И 3, которые со1 тветствуют независимым заданиям, Сигналы с открытых элементов И 3: открывают соответствующие им эле енты И 26 и содержимое регистров 25 заносится в вычитатели 27; проходят через соответствующие элеенты 19 задержки и, поступив на первый правляющий вход коммутаторов 28, подключают выходы регистров 4, соответствуюих независимым заданиям ко входу

ычитателей 27; при этом, содержимое выитателей 27 уменьшается на величину соержимого соответствующих регистров 4; проходят через соответствующие элеенты 24 задержки и вторые управляющие ходы коммутаторов 28, при этом выходы егистра 5 подключаются к входам соответтвующих вычитателей 27, содержимое коорых уменьшается на величину регистра 5. локи элементов 19 и 24 задержки задержи5

55 вают сигнал, поступающий с элементов И 3 на время, необходимое для приема информации с регистров 25 в вычитатели 27 и на время приема информации с регистров 4 и вычитания в вычитателях 27 соответственно.

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

Таким образом, значения П соответствующих независимым заданиям, представленные в двоичных кодах с выхода вычитателей 27, подаются на матрицу 20 элементов сравнения. На выходе элементов

И 21 появляются единичные сигналы в том случае, если в соответствующих вершинах графа значение П вЂ” минимально.

Ъ

Второй блок 7 преобразования кода выбирает среди единичных сигналов с выхода элемента И 21 один, который вырабатывается на элементе И 21 с младшим номером, и подаст его на вход соответствующего элемента И 10, сигнал с выхода которого откроет соответствующий блок элементов И 17 и установит в единичное состояние триггер

11, На третьем этапе обеспечивается распределение независимых выбранных заданий по свободным ЭВМ, выдача ЭВМ вычислительной системы исходных данных для обслуживания заданий, установка в нулевое состояние триггеров 2 матрицы 1 тех строк, номера которых соответствуют кодам номеров задач, обслуженных Э В M и обнуление вычитателей, Выбранный блок элементов И 17 пропускает на вход блока элементов ИЛИ 18 код номера задания и исходных данных с выхода соответствующего регистра 16, По входам 40 устройства подаются сигналы готовности от процессоров комплекса на входы первого блока 7 преобразования кода, который выбирает среди них младший и оповещает его Ilo Goответствующему выходу 30 готовности устройства о том, что ему предстоит обслужить очередное задание. Сигнал с выхода элемента 14 задержки, необходимой для учета времени срабатывания устройства в совокупности с сигналом с соответствующего выхода первого блока 7 преобразования кода, открывает блок элементов И 22 и пропускает на его выход, т.е. на вход младшей свободной ЭВМ в вычислительной системе код номера выбранного задания и исходные данные для его выполнения. Момент выдачи определяется сигналом на синхровыходе 32 устройства.

1837316

8 том случае, если еще остались независимые задания (сигнал на выходе элемента

ИЛИ 15 имеет единичное значение) и в комплексе остались свободные процессоры, сигнал на выходе элемента ИЛИ 23 имеет единичное значение, устройство будет запущено вновь сигналом с выхода элемента И

13. При окончании обработки одного из заданий поступит сигнал по соответствующему входу 36 установки в ноль устройства, который установит в нулевое состояние триггеры соответствующей строки матрицы

1 и, пройдя через элемент ИЛИ 12, установит в "0" вычитатели устройства и далее при наличии независимых заданий и свободных

15 процессоров вновь запустит устройство.

Окончание обслуживания всех заданий сигнализируется нулевым значением на выходе 29 устройства.

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

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

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

30 вычислительной системе, содержащее матрицу пхп триггеров (где n — число задач), первую и вторую группы блоков элементов первый, второй и третий элементы ИЛИ, элемент И, первый элемент задержки, первую группу регистров, блок элементов ИЛИ, первый и второй блоки преобразования ко40. дов, матрицу элементов сравнения, причем

P-й информационный вход устройства подключен к входам установки в "1" триггеров

Р-й строки матрицы триггеров (P=1, п, где и — число задач), К-й вход (К=1, n) номера задачи устройства соединен с информационным входом Р-ro регистра первой группы, вход запуска устройства соединен с первым

45 входом первого элемента ИЛИ и входами установки в "0" триггеров группы, К-й вход сброса устройства соединен с входами установки в "0" триггеров К-й строки матрицы, выход KP-го триггера матрицы подключен к

К-му входу Р-го элемента ИЛИ-НЕ группы, выход первого элемента ИЛИ соединен с первым входом элемента И, выходы элементов ИЛИ-НЕ группы подключень к соответствующему входу второго элемента ИЛИ, первым входам элементов И первой группы, выходы которых соединены с входами установки в "1" триггеров группы и с вторыми

И, группу элементов ИЛИ вЂ” Н Е, первую и вторую группы элементов И, группу триггеров, 35 входами блоков элементов И первой группы, выход М-го разряда P-го регистра соединен с М-м входом соответственно P-го блока элементов И первой группы. выходы триггеров группы с (n+1)-ми входами элементов ИЛИ вЂ” НЕ группы, выход второго элемента ИЛИ соединен с выходом "Конец работы" устройства и с вторым входом элемента И, выход которого через элемент задержки соединен с (и+2)-м входом первого элемента ИЛИ, с первым входом блоков элементов И второй группы и с синхровходом устройства, группа выходов блока элементов ИЛИ соединена с вторыми входами блоков элементов И второй группы, выходы которых соединены с соответствующим информационным выходом устройства, выход третьего элемента ИЛИ соединен с третьим входом элемента И, группа входов готовности устройства подключена к группе входов первого преобразователя кодов, группа выходов которого соединена с группой выходов готовности устройства, с третьими входами блоков элементов И второй группы и с группой входов третьего элемента ИЛИ, выход P-ro элемента И второй группы подключен к Р-му входу второго блока преобразования кодов группы, группа выходов которого соединена с вторыми входами элементов И первой группы, о т л и ч а ю щ е ес я тем, что. с целью увеличения количества обслуженных задач за директивное время в вычислительной системе, в него введены третья группа элементов И, вторая и третья группы регистров, регистр, блок элементов

И, первая и вторая группы элементов задержки, третья группа блоков элементов И, группа вычитателей, причем выход P-ro элемента ИЛИ вЂ” НЕ группы подключен к первому входу P-го элемента И третьей группы, второй вход которого соединен с выходом первого элемента ИЛИ, выход Р-го элемента И третьей группы подключен к P-м элементам задержки первой и второй групп и к вторым входам блоков элементов И третьей группы, К-й вход времени решения задачи устройства соединен с информационным входом P-ro регистра второй группы, выход

М-го разряда которого подключен к М-му разряду первой группы информационных входов Р-го коммутатора, к 1-му разряду второй группы информацйонных входов всех коммутаторов подключен t-й выходной разряд регистра, информационные входы которого подключены к выходам блока элементов И, с первыми входами которого соединены входы установки текущего времени, выходы Р-х элементов задержки первой и второй групп подключены соответственно к первому и второму управ1837316

М

38

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

Производственно-издательский комбинат "Патент", г. Ужгород. ул.Гагарина, 101

9 ! л ющим входам P-го коммутатора, М-й разр д информационного выхода P-го коммутат ра соединен с M-м разрядом первой г уппы информационных входов P-го вычит теля группы, r-й информационный выход к торого подключен к первым входам r-го р зряда PK-õ (P=1, (n — 1), К=(Р+1), и, и к втор м входам r ro разряда КР х элементов с авнения матрицы, выход признака "Менье" PK-го элемента сравнения матрицы сое инен с (К вЂ” 1)-м входом, а выход признака

" ольше" с К-м входом P-го элемента И второй группы, К-й вход директивного времени окончания решения задачи устройства соединен с информационным входом P-ro регистра третьей. группы, выход М-ro разряда

5 которого соединен с М-м входом P-го блока элементов И третьей группы, выходt-го разряда которого соединен с t-м разрядом второй группы информационных входов вычитателей группы, выход первого элемен10 та ИЛИ подключен к входам установки в "0" вычитателей группы устройства и к вторым входам блока элементов И.