Устройство для распределения задач в вычислительной системе Советский патент 1993 года по МПК G06F15/20 G06F15/419 

сл

с

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

| Целью изобретения является увеличение количества обслуженных задач за ди- р ективное время в вычислительной системе, Поставленная цель достигается тем, что в устройство, содержащее матрицу пхп триггеров (где п - число задач), первую и вторую пруппы блоков элементов И, группу элементов ИЛИ-НЕ, первую и вторую группу элементов И, группу триггеров, первый и Еторой и третий элементы ИЛИ. элемент И, г ервый элемент задержки, первую группу f егистров, блок элементов ИЛИ, первый и Е торой блоки преобразования кодов, матрицу элементов сравнения, причем Р-й инфор- ационный вход устройства подключен к ходам установки в 1 Tpj/итеров Р-й строки атрицы триггеров (, п, где п - число адач), К-й вход (, п) номера задачи устройства соединен с информационным входом Р-го регистра первой группы, вход запуска устройства соединен с первым входом первого элемента ИЛИ и входами установки в О триггеров группы, К-й вход сброса устройства соединен с входами установки в О триггеров К-й строки матрицы, выход КР-го триггера матрицы подключен к К-му входу Р-го элемента ИЛИ-НЕ группы, выход первого элемента ИЛИ соединен с первым входом элемента И, выходы элементов ИЛИ-НЕ группы подключены к соответствующему входу второго элемента ИЛИ, первым входам элементе И первой группы, выходы которых соединены с входами установки в 1 триггеров группы и с вторыми входами блоков элементов И первой группы, выход М-го разряда Р-го регистра соединен с.М-м входом соответственно Р-го блока элементов И первой группы, выходы триггеров группы с (п+1)-ми входами элементов ИЛ И-НЕ группы, выход второго эле00Сл ч|

со

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

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

0 разряда которого соединен с t-м разрядом второй группы информационных входов вычитателя группы, выход первого элемента ИЛИ подключен к входам установки в О вычитателей устройства и ко вторым входам

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

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

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

0 задержки, матрицу элементов 20 сравнения, вторую группу элементов И 21, вторую группу блоков элементов И 22, третий элемент ИЛИ 23, вторую группу элементов 24 задержки, третью группу регистров 25,

5 третью группу блоков элементов И 26, группу 27 вычитателей, группу 28 коммутаторов, выход 29 конца работы устройства, сигнальный выход 30 готовности устройства, группу информационных выходов 31 устройства,

0 выход 32 синхронизации устройства, группу входов установки в единицу устройства 33, группу входов 34 номера задачи устройства, вход 35 запуска устройства, группу входов 36 установки в ноль устройства, вход 37 ус5 тановки текущего времени, группу входов 38 времен решения задачи устройства, группу входов 39 директивного времени окончания решения задачи устройства, входы 40 готовности устройства. Увеличение количе0 ства обслуженных задач за директивное время в вычислительной системе достигается за счет назначения для каждой задачи динамического приоритета. Динамический приоритет (Гг) задачи вычисляется по сле5 дующей формуле:

П Г -Т -Тр,

где Т-директивное время окончания решения задачи (время не позже которого задача должна быть решена); Т1 - текущее время;

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

Устройство работает следующим образом. В исходном состоянии триггеры 2, 11 и вычитатели 27 обнулены. Первоначально в триггеры 2 по входам заносится информа- иия о топологии графа (вершины которого соответствуют задачам, а ветви информаци- с нно-управляющим связям между ними). Номер триггера, установленного в единич- ое состояние, определяется пересечением строки с номером, равным номеру начальной вершины ветви, и столбца с номером, равным номеру ее конечной вершины. В соответствующий регистр 4 по входу 38 за- к осится планируемое время решения задачи на ЭВМ, в соответствующий регистр 25 г о входу 39 - директивное время выполне- ия операции, в соответствующий регистр 6 по входу 34 - код номера задания и ис- одные данные для его выполнения, В работе устройства можно выделить три этапа. На г ервом производится определение независимых заданий. На выходах соответствую- цих элементов ИЛИ-НЕ 9 в столбцах, которые соответствуют начальным вершинам информационно-управляющего графа, Появятся высокие потенциалы, т.к. начальные вершины не содержат входящих вет- i ей, и триггеры 2 в этих столбцах находятся нулевом состоянии. Импульс запуска по ЕХОДУ 35 устройства устанавливают в нуле- toe состояние триггеры 11, и пройдя через элемент ИЛИ 12 поступает на следующие глементы:

открывает элемент И 6 и по входу 37 в регистр 5 заносится значение текущего времени из счетчика времени вычислительной (истемы;

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

Сигналы с открытых элементов И 3: открывают соответствующие им элеенты И 26 и содержимое регистров 25 за- йюсится в вычитатели 27;

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

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

локи элементов 19 и 24 задержки задержиt

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

вычитания в вычитателях 27 соответственно.

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

0 минимальный динамический приоритет. Значения П вычислены на первом этапе и находятся в вычитателях 27.

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

0 графа значение П - минимально.

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

5 подаст его на вход соответствующего элемента И 10, сигнал с выхода которого откроет соответствующий блок элементов И 17 и установит в единичное состояние триггер 11.

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

0 элементов ИЛИ 18 код номера задания и исходных данных с выхода соответствующего регистра 16. По входам 40 устройства подаются сигналы готовности от процессоров комплекса на входы первого блока 7

5 преобразования кода, который выбирает среди них младший и оповещает его по соответствующему выходу 30 готовности устройства о том, что ему предстоит обслужить очередное задание. Сигнал с выхода эле0 мента 14 задержки, необходимой для учета времени срабатывания устройства в совокупности с с.игналом с соответствующего выхода первого блока преобразования кода, открывает блок элементов И 22 и пропу5, екает на его выход, т.е. на вход младшей свободной ЭВМ в вычислительной системе код номера выбранного задания и исходные данные для его выполнения. Момент выдачи определяется сигналом на синхровыходе 32 устройства.

В том случае, если еще остались независимые задания (сигнал на выходе элемента ИЛИ 15 имеет единичное значение) и в комплексе остались свободные процессоры, сигнал на выходе элемента ИЛИ 23 имеет единичное значение, устройство будет запущено вновь сигналом с выхода элемента И 13. При окончании обработки одного из заданий поступит сигнал по соответствующему входу 36 установки в ноль устройства, который установит в нулевое состояние триггеры соответствующей строки матрицы 1 и, пройдя через элемент ИЛИ 12, установит в О вычитатели устройства и далее при наличии независимых заданий и свободных процессоров вновь запустит устройство. Окончание обслуживания всех заданий сигнализируется нулевым значением на выходе 29 устройства.

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

Ф о р м у л а и з о б р е т е н и я

Устройство для распределения задач в вычислительной системе, содержащее матрицу пхп триггеров (где п - число задач), первую и вторую группы блоков элементов И, группу элементов ИЛИ-НЕ, первую и вторую группы элементов И, группу триггеров, первый, второй и третий элементы ИЛИ, элемент И, первый элемент задержки, первую группу регистров, блок элементов ИЛИ, первый и второй блоки преобразования кодов, матрицу элементов сравнения, причем Р-й информационный вход устройства подключен к входам установки в Г| тр иггеров Р-й строки матрицы триггеров (, п, где п - число задач), К-й вход (, п) номера задачи устройства соединен с информационным входом Р-го регистра первой группы, вход запуска устройства соединен с первым входом первого элемента ИЛИ и входами установки в О триггеров группы, К-й вход сброса устройства соединен с входами установки в О триггеров К-й строки матрицы, выход КР-го триггера матрицы подключен к К-му входу Р-го элемента ИЛИ-НЕ группы, выход первого элемента ИЛИ соединен с первым входом элемента И, выходы элементов ИЛИ-НЕ группы подключены к соответствующему входу второго элемента ИЛИ, первым входам элементов И первой группы, выходы которых соединены с входами установки в 1 триггеров группы и с вторыми

входами блоков элементов И первой группы, выход М-ro разряда Р-го регистра соединен с М-м входом соответственно Р-го блока элементов И первой группы, выходы

5 триггеров группы с (п+1)-ми входами элементов ИЛИ-НЕ группы, выход второго элемента ИЛИ соединен с выходом Конец работы устройства и с вторым входом элемента И, выход которого через элемент за0 держки соединен с (п+2)-м входом первого элемента ИЛИ, с первым входом блоков элементов И второй группы и с синхровходом устройства, группа выходов блока элементов ИЛИ соединена с вторыми входами бло5 ков элементов И второй группы, выходы которых соединены с соответствующим информационным выходом устройства, выход третьего элемента ИЛИ соединен с третьим входом элемента И, группа входов готовно0 сти устройства подключена к группе входов первого преобразователя кодов, группа выходов которого соединена с группой выходов готовности устройства, с третьими входами блоков элементов И второй группы

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

5 группы регистров, регистр, блок элементов И, первая и вторая группы элементов задержки, третья группа блоков элементов И, группа вычитателей, причем выход Р-го элемента ИЛИ-НЕ группы подключен к перво0 му входу Р-го элемента И третьей группы, второй вход которого соединен с выходом первого элемента ИЛИ, выход Р-го элемента И третьей группы подключен к Р-м элементам задержки первой и второй групп и к

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

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

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

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