Устройство для распределения заданий процессорам Советский патент 1989 года по МПК G06F9/50 

.1

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

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

На фиг. 1-3 дана схема предлагаемого устройства.

Устройство содержит группу триггеров 1, группы счетчиков 2 и 3, группу элементов ИЛИ-НЕ 4, группу

элементов И 5, блоки 6-9 памяти, группы кодовых входов 10 и 1I устройства, элементы ИЛИ 12-15, элементы И 16-19, приоритетные шифраторы 20 и 21, регистры 22-29, группу выходов 30 номера задания устройства, мультиплексоры 31-33, дешифраторы 34- 36, группы кодовых входов 37-41 устройства, вход 42 считывания устройства, группу кодовых входов 43 устройства, входы 44 сброса, вход 45 запуска устройства, триггеры 46-51, генератор 52 импульсов, элементы И-ИЛИ-НЕ 53 и 54, элементы И-НЕ 55-57, группу входов 58 готовности устройства, группу сигнальных выходов 59 устройства, группу выходов БО прерывания устрой 4

С35 1чЭ

со

ел

ства, выход 6 записи устройства, элемент 62 задержки, группу информационных выходов 63 устройства, элемент ИЛИ-НЕ 6А.

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

Перед началом работы устройства подачей импульсного сигнала на вход 44 все элементы памяти устройства, кроме блока 7 памяти; переводятся в исходное нулевое состояние. При это на группе выходов 63 устройства устновлены, единичные сигналы, а на выхдах 30, 59 и 60 устройства - нулевы Триггер 46 нулевым уровнем сигнала на прямом выходе запрещает работу гнератора импульсов.

Блок 7 памяти выполнен в виде ПЗ и реализует следующую группу функци Пусть Р - максимальное число параллельных программ, которые могут однвременно решаться в системе. Пусть регистре 23 записан код числа п, а в регистре 24 записан код числа т, где т, . Таким образом, из блка 7 памяти 7 выбирается п-я страница, а на ней ячейка с номером т, В ячейке m занесено 1-разрядное число (где 1 - число счетчиков 2 в устройстве и 1 кратно ,Р), имеющее в q(in-iTn)-oM (где , (l-n)/n и разряде единицу.

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

Далее для работы устройства необходимо занести на его элементы памяти следующую информацию. Пусть на оновании анализа поступающих на решение программ управляющий монитор выбирает п-программный режим работы устройства и заносит код числа п в регистр 23. Пусть также запускаемая программа будет решаться в системе под номером т. Для этого в регистр 24 заносится код числа т. Далее в счетчики 2 первой группы с номерами , где , (1-п)/п с входов 10 заносятся в прямом коде коды стё .пени захода соответствующих вершин графа программы. Соответствие вершины графа и счетчика 2 определяется весом верщины, представляюш 5м собой величину максимального пути из

0

5

5

0

0

5

0

5

0

5

данной верши1Ш до конечной вершины графа программы, имеюгиего в качестве веса дуг длительности решения задач. При этом п-ну счетчику 2 должна соответствовать вер1чина графа с наибольшим весом, (п-1тп)-му счетчи1су 2 - вторая по весу вершина графа и т.д. Последнему счетчику 2 распределенному т-й программе будет соответствовать конечная вершина графа, име- ющая нулевой вес. Такое соответствие вершин и счетчиков 2 позволяет минимизировать время решения параллельной программы, так как из некоторой совокупности запрашиваю1чих ре- . шений заданий ( представляющих программу) и для.решения которых имеется вся необходимая информация первым выбирается на решение задание, имеющее больший вес. При этом, если используются не все счетчики 2, распределенные т-й программе, то в них заносится произвольная ненулевая информация,

Далее в счетчик 3 с номером m заносится в дополнительном коде код. количества заданий в программе. По завершению каждого задания к содержимому счетчика добавляется единица и сигнал переполнения на сигнальном выходе счетчика свидетельствует о завершении выполнения одноименной про- гр аммы.

Для управления ходом выполнения программы m в блоки 6, 8 и 9 памяти заносится следут- щая информация, В блок 6 памяти заносится информация о топологии графа, описывающего набор информационно связанных заданий, представляющих параллельную прогр ам- му. По адресу, соответствующему коду завершенного задания, относящегося к программе га, в блок 6 памяти зане- сено числоJ имеющее в соответствующем q-M разряде единицу, если из j-й вершины графа исходит дуга, ведущая в q-тую вершину графа. По адресу, соответствующему конечной вершине графа, в блок 6 памяти занесен нуль.

В блок 8 памяти заносится информация, отражающая соответствие номера программы m и номера процессорного модуля системы, распределенного для его выполнения. По адресу, соответствующему номеру j некоторой вершины графа (счетчика 2 с номером j), в блок 8 памяти занесен код номера процессорного модуля, распределенного

для выполнения задания j, относяг(е- гося к программе тп.

В блок 9 памяти заносится информация, отражающая соответствие кода завершенного задания и «омера счетчика 3 второй группы, распределенного данной программе, для учета выполненных заданий. По адресу, соответствующему коду завершенного задания j, в блок 9 памяти занесено число , имеющее в соответствующем in-м разряде (где m - номер программы) единицу, если завершенное задание j, относится п программе т).

На тактах, предшествующих К-му, в регистр 29 заносится в унитарном коде код числа 3, а в регистр 26 заносится двоичный код числа 1. На К-м такте в регистр 25 заносится дво- ичньй код числа Р. На выходе элемента ИЛИ 13 появляется единичный сигнал, который создает условия для прохождения синхроимпульса на (К+1)-м такте через элементы И 17 и 18. Если на К-м такте не выполнялось условие готовности ни для одного из заданий, то на (К+1)-м такте триггер .48 останется в с-брошенном состоянии и единичном сигналом на инверсном выходе разрешит прохождение синхро-- импульса через элемент И 18. На (K+O-M такте синхроимпульс проходит через элемент И 18 и поступает на

синхровход . триггера 51, на информа- ционный ззход которого поступает единичный сигнал с выхода третьего разряда регистра 29. Одновременно с этим, если не поступало сигналов готовности от процессоров и триггер 47

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

- м

4623156

вход мультиплексора 31 и создает условия для прохождения кода адреса ячейки 1 с выходов регистра 26 на ад- f- ресный вход блока 8 памяти, на информационный вход которого поступает код из регистра 25. Синхроимпульс проходит через элемент И-НЕ 57 и формирует сигнал Запись, по которому 10 в ячейку 1 блока 8 памяти заносится код. Одновременно с этим через элемент ИЛИ 15 выдается сигнал высокого уровня на выход 61 устройства, который сигнализирует о том, что за- 15 пись кода в блок 8 памяти завершена и можно приступить к занесению следующего слова инфо.рмахдаи. Этот же сигнал через элемент 62 задержки сбрасывает регистры 25 и 26 и снимает 20 предпосылки дпя операции Запись. По синхроимпульсу триггер 51 сбрасывается и устройство возвращается в исходное состояние. В случае если на К-м такте возникнут предпосылки как 25 для выдачи готового к выполнению задания, так и для операции запись в блок 8 памяти, то на (К+1)-м такте по синхро.икпульсу триггер 48 перейдет в единичное состояние и запретит осу- 30 ществление операции запись. Таким образом, разрешается конфликт при обращении к блоку.8 памяти и отдается .приоритет операции выдачи задания на выполнение. Аналогичным образом осу- 35 ществляется модификация содержимого блоков 6 и 9 памяти. При этом приоритет отдается операции приема кода завершенного задания. Поскольку операция выдачи задания на выполнение 40 протекает при участии блока 8 памяти, . а в операции приема кода завершенного задания принимают участие блоки 6 и 9 памяти (как это будет описано ниже), то возможна параллельная мо

Изобретение относится к автоматике и вычислительной технике, а именно к приоритетным устройствам для распределения заданий процессорам, и предназначено для использования в выг сокопроизводительных многопроцессорных или многоматинных вычислительных и управляюрдах системах. Цель изобретения - расширение функциональных возможностей за счет адаптации устройства к качественному составу по- . ступающих заданий. Устройство содержит группы счетчиков, четыре блока памяти, четыре элемента ИЛИ, три элемента И-ИЕ, два элемента И-ИЛИ-НЕ, шесть триггеров5 три мультиплексора, два приоритетных шифратора, восемь регистров, три дешифратора, группу триггеров, генератор импульсов. Б устройство вводится новая дисциплина фракционирования - мультипроцессорное мультипрограммирование, состоящее в управлении решением нескольких параллельных программ в системе. 3 ил. «с

рого приходит нулевой сигнал с выхода 45 дификация содержимого блока 8 памя- разряда регистра- 29 (поскрльку соот- ти и прием кода завершенного задания.

ветствуювдш блок памяти не был выбран) .

По заднему фронту синхроимпульса триггер 51 переходит в единичное состояние. Сигнал высокого уровня на прямом выходе триггера 51 поступает на вход элемента И-НЕ 57 и создает условия для-прохождения синхроимпульа также параллельная выдача задания на выполнение и модификация содержимого блока 6 или 9 памяти. 50 После занесения всей необходимой дпя выпол1-1ения программы информации на вход 42 устройства подается единичный импульсный сигнал, который переводит в единичное состояние тригса,.а также поступает на вход элемен- 55 геры 1 группы, соответствующие про- та ИЛИ-НЕ 64 и формирует разрешение грамме т. Нулевые сигналы на инверс- доступа к блоку 8 памяти. При этом нулевой сигнал на прямом выходе триггера 48 поступает на управляющий

ных выходах выбранных триггеров разрешают прохождение нулевых сигналов с выходов счетчиков 2 первой группы.

а также параллельная выдача задания на выполнение и модификация содержимого блока 6 или 9 памяти. После занесения всей необходимой дпя выпол1-1ения программы информации на вход 42 устройства подается единичный импульсный сигнал, который переводит в единичное состояние триггеры 1 группы, соответствующие про- грамме т. Нулевые сигналы на инверс-

ных выходах выбранных триггеров разрешают прохождение нулевых сигналов с выходов счетчиков 2 первой группы.

714

Выдача готового к выполнению задания производится следующим образом. Поскольку начальная вершина графа программы представляет собой, согласно начальной разметке, готовое для выполнения задание, то в соответству- кяций ей счетчик 2 занесен нулевой код и на его выходе будет низкий уровень сигнала. В результате чего, на Быхсде одноименного элемента ИПИ-НЕ 4 сформируется единичный сигнал, который пройдет на выход элемента ШШ 12 и разрешит прохождение синхроимпульса через элемент И 16. По- скольку в устройстве может быть зафиксировано несколько готовых к выполнению заданий, то приоритетный шифратор 20 сформирует номер наиболее приоритетного задания, который по заднему фронту синхроим;пульса будет занесен в регистр 22. Одновременно с этим будет установлен триггер 48. Единичный сигнал с прямого выхода триггера 48 поступает на вход элемента И 19 и разрешает прохождение синхроимпульса, поступает на управляющий вход мультиплексора 31, а также поступает на. вход элемента ИЛИ-НЕ- 64 и формирует разрешение доступа к блоку В памяти. Код номера готового к выполнению задания с выходов регистра 22 поступает на информационный выход 30 устройства, а также через мультиплексор 31 поступает на адрес- ный вход блока 8 памяти, в результате чего на выход блока 8 памяти выдается код номера процессора, распределенного для выполнения- данного задания. По синхроимпульсу на выходе элемента И 19 сформируется единичный импульсный сигнал, который поступает на управляющий вход дешифратора 34 и разрешает формирование сигнала сброса триггера 1 .группы, соответствую- щего выдаваемому заданию, а также поступает на синхровход регистра 28 и отрицательным фронтом заносит в него код номера и.1бранного процессора с выхода блока 8 памяти.

По синхроимпульсу триггер 48 сбрасывается в исходное состояние, а на выходе дешифратора 35, соответствующему выбранному процессору, формируется импульсный сигнал, который поступает на выход 59 группы. По этой команде выбранный процессор принимает с системной магистрали код номера, готового к выполнению задания.

п 5 О п 5

0

5

58

По синхроимпульсу регистр 22 и 28 сбрасываются в исходное нулевое состояние.

Прием кода завершенного задания осуществляется следуюпщм образом. Процессор, завершивший выполнение задания, выставляет единичный сигнал на соответствующий вход 58 устройства. По очередному синхроимпульсу этот сигнал запоминается в регистре 27. В результате на выходе приоритетного шифратора 21 формируется двоичный код номера процессора, завершившего выполнение задания, а на выходе элемента ИЛИ 14 формируется единичный сигнал, который поступает на информационный вход триггера 47. Если в системе имеется не-сколько процессоров, завершивршх выполнение заданий, то приоритетный шифратор 21 формирует номер наиболее приоритетного из них.

По отрицательному фронту очередного синхроимпульса триггер 47 переводится в единичное состояние. Единичный сигнал с прямого выхода триггера 47 поступает на управляющие входа мультиплексоров 32 и 33 и разрешает прохождение на их выходы сигналов, поступает на входы элементов И-ИЛИ-НЕ 53 и 54 и разрешает прохождение синхроимпульса, а также поступает на управляющий вход дешифратора 36. На выходе дешифратора 36, соответствующем наиболее приоритетному процессору, формируется единичный сигнал, который, поступает на одноименный сигнальный выход 60 группы., Получив команду, выбранный процессор снимает сигнал готовности, выдает на системную магистраль код завершенного задания. С системной магистрали код завершенного задания поступает на информационные входы 43 устройства и далее через мультиплексог 32 и 33 на выходах элементов И-ИЛИ-НЕ 53 и 54 формируются нулевые импульсные сигналы, которые поступают на входы разрешения доступа блоков 6. и 9 памяти. В результате этого на выходах блока 6 памяти формируются единичные импульсные сигналы, которые поступают на вычитающие входы одноименных счетчиков 2 первой группы и корректируют готовность заданий. На выходе блока 9 памяти соответствующем программе, к которой относится завершенное задание, формируется единичный импульсиый сигнал, который поступает н счетный вход одноименного счетчика 3 и корректирует степень выполнения программы. По синхроимпульсу триггер 47 сбрасывается в исходное нулевое состояние.

Наличие в устройстве регистров 22 и 28 позволяет совместить в пределах одного такта операции по выдаче но- мера, готового к выполнению задания и приему кода завершенного задания.

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

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

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

Устройство для распределения заданий процессорам, содержащее первую группу счетчиков, первий блок памя- ти, первый элемент ШШ, четыре элемента И, группу элементов И, груп- .пу элементов ИЛИ-НЕ, причем первая группа кодовых входов устройства сое -динена с информационными входами и синхровходами одноименных счетчиков первой группы, выходы элементов ИЛИ-НЕ группь соединены с одноименными входами первого элемента ИЛИ, выхо которого, соединен с первым входом первого элемента И, отличающееся тем, что, с целью расширения функциональных возможностей за счет адаптации устройства к качественному составу поступшощих заданий, оно содержит вторую группу счетчиков, второй, третий и четвертый блоки памяти, второй, третий и четвертый элементы ИЖ, элемент ИЛИ-НЕ, первый, второй и третий элементы И-НЕ, .первый и второй элементы И-ШТИ-НЕ, шесть триггеров, три мультиплексора, первый и второй приоритетные шифраторы, восемь регистров, три дешифратора, группу триггеров, элемент задержки и генератор тактовых импульсов, причем каждый выход первого блока памяти соединен с вычитающим .входом одноименного.счетчика первой

групгш, сигнальный выход равенства нулю которого соединен с первым входом одноименного элемента ИЛИ-НЕ- группы, выходы элементов ИПИ-НЕ группы соединены с входами первого приоритетного шифратора, выходы которого соединены с группой информационных входов первого регистра, выходы первого регистра являются группой выходов номера задания устройства и соединены с группой информационных входов первого мультиплексора, а также с группой входов первого дешифратора каждай выход которого соединен с нулевым входом одноименного триггера группы, первая группа кодовых входов устройства соединена с группой информационных входов и синхровходом второго регистра, выходы которого соединены со Старшими разрядами адреса второго блока памяти, вторая группа кодовых входов устройства соединена с группой информационных входов и синхровходом третьего регистра, выходы которого соединены с младшими разрядами входа адреса второго блока памяти, каждый выход которого соединен с первым входом одноименного элемента И группы, вход считывания устройства соединен с вторыми входами элементов И группы, выходы которых соединены с единичными входами одноименных триггеров группы инверсные выходы триггеров rpynra i соединены с вторыми входами одноименных элементов ИЛИ-НЕ группы, третья группа кодовых входов устройства соединена с группой информационных входов и синхровходом четвертого регистра, выходы которого соединены с информационными входами первого, третьего и четвертого блоков памяти а также с входами второго элемента ИЛИ выход которого соединен с первыми входами второго и третьего элементов И, четвертая группа кодовых входов устройства соединена с группой информационных входов и синхровходом пятого регистра, выходы которого соединены с второй группой информационных входов первого и первыми информационными входами второго, третьего мультиплексоров, пятая группа кодовых входов устройства соединена с вторы- ми группами информационных входов второго и третьего мультиплексоров, вход сброса устройства соединен с нулевым входом первого триггера, вход запуск

устройства соединен с единичным входом первого триггера, прямой выход которого соединен с входом запуска генератор а. тактовых импульсов, первый йыход которого соединен с вторым вхо ;tOM первого элемента И и с синхровхо фм второго триггера, выход первого Цемента И соеданен с синхровходом первого регистра и с синхровходом тр тьегп триггера, второй выход генератора импульсов соединен с вторыми входами второго и третьего элементов И, с первым входом четвертого элемента И и с первыми входами первого и второго элементов И-ЙЛИ-НЕ, третий выход генератора тактовых импульсов соединен с синхровходом шестого регистра, с нулевыми входами второго и третьего триггеров, с первыми вхо- дами первого, второго и третьего элементов И-НЕ и с управляющим входом второго дешифратора, четвертый выход ггнератора тактовых импульсов соеди- нгн с входом сброса первого регист- ра, с нулевьаог входами четвертого, njToro и шестого триггеров и с входом сЗроса седьмого регистра, тестая группа кодовых входов устройства сое- с информационным входом и

синхровходом восьмого регистра, вы- хЬды разрядов которого соединены со- о -ветственно с информациониими входами четвертого, пятого и inecToro триггеров, группа сигнальных входов готовности устройства соединена с груп- пбй входов иестого регистра, выходы которого соединены с входами второго приоритетного шифратора, выхода вто- рбго приоритетного шифратора соеди- н«ш с информационными входами третьего дешифратора и с входами третьего элемента ИЛИ К)1ход которого соединён с информа1дионш,1м входом второго триггера, вход разрешения доступа Btoporo блока памяти соединен с вхог дами логического нуля устройства, вы- хдды третьего блока памяти соединетта с информационными входами седьмого регистра, выходы которого соединены с информацион1а,1ми входами второго дешифратора, и,1ходы которого являются Г1| уппой сигналый1х выходов устройства, прямой выход второго триггера соединен с управляющими входами второго и третьего мультиплексоров, с вторы™ мм входами первого и второго элементов И-ИЛИ-НЕ и с управляющим входом третьего дешифратора, выходы которо

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

42

У

-//

-xz;

Фиг.

29

Физ.