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

(59 4 САНИЕ ИЗОБРЕТЕНИЯ ил,ОСУДАРСТВЕННЫИ КОМИТЕТ СССР ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ Н АВТОРСКОМУ СВИДЕТЕЯЬСТ(56) .Авторское свидетельство СССР В 664175, кл. С 06 Р 9/46, 1975.Авторское свидетельство СССР У 877553, кл. С 06 Г 9/46, 1979. (54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯЗАДАНИЙ ПРОЦЕССОРАМ(57) Изобретение относится к вычислительной технике и может быть использовано для распределения заданий процессорам мультипроцессорной системы. Устройство для распределения заданий процессорам содержит матрицу формирователей весов дуг, группу элементов запрета, группу счетчиков, группу блоков элементов ,И, блок сортировки информации, регистр приоритетов, регистр выбранных вершин, блок управления. В матрицу формирователей весов дуг заносится информация о топологии ориентированного графа и весах дуг, При поступлении входного сигнала в регистрирующих счетчиках накапливаются импульсы, число которых пропорционально времени максимального пути для соответствующей вершины графа. После того как будет сформирована необходимая информация в счетчиках, в соответствующий разряд регистра приоритетов с помощью блока сортировки информации будет записана логическая единица и на обслуживание выберется готовая вершина, для которой время максимального пути наибольшее. 31 13Изобретение относится к вычислительной технике и может быть использовано для распределения заданийпроцессорам мультипроцессорной системы.Цель изобретения - расширение области применения устройства за счетаппаратной реализации функций диспетчера вычислительной системы,На фиг. 1 показана структурнаясхема устройства (для И=З вершин);на фиг, 2 - блок сортировки информации на фиг. 3 - ячейка итеративнойсети,Устройство содержит матрицу 1 формирователей весов дуг, состоящую изформирователей 2, -2 весов дуг,каждый из которых состоит из счетчикй3, первого и второго триггеров 4 и5 и элементов И 6, - б, элемент 7задержки, генератор 8 тактовых импульсов, блока 9 управления, включающий элементы И 10 и 11, триггер12, элемент И 13, вход 14 пуска устройства, сигнальный выход 15 устройства, элементы 16, - 16 запрета,.регистрирующие счетчики 17, - 17 з,блоки элементов И 18, - 18, блок 19сортировки информации, группу входов20 и выходов 21 блока 19, группу вхо.дов 22 сброса счетчиков 17, регистр23 приоритета, регистр 24 выбранныхвершин, группу информационных выходов 25, - 25 э, первую и вторую группы информационных входов 26 - 26 и27, - 27 устройства, вход 28, ячейки 29, элементы НЕ 30, блок элементов И 31, входы 32-38, выходы 39-41,элементы И 42 и 44 и элементы НЕ 43и 45.Устройство работает следующим образом. В исходном состоянии регистры 23 и 24, счетчики 17 и 17 з находятся в нулевом состоянии, а триггер 12 в единичном состоянии, в счетчик 17, записано максимальное число, в матрицу 1 заносится информация о топологии ориентированного графа. При этом триггеры 4 и 5 формирователей 2, моделирующие ветви графа, устанавливаются в единичное состояние, Соответствующий формирователь 2 определяется пересечением строки с номером, равным номеру начального узла моделирующей ветви, и столбца с номером ее конечного узлаВ счетчике 3 соответствующих формировате 19031 5 10 15 20 25 ЗО 35 40 45 2лей 2 заносятся числа импульсов, дополняющие длительность ветвей до полной емкости счетчиков. После записи исходной информации на выходах элементов И 6, объединяющих выходы формирователей 2 в столбцах, соответствующих начальным узлам графа, устанавливаются высокие потенциалы, Это объясняется тем, что в однонаправленном графе без циклов и петелв начальные узлы не содержат входных ветвей, а следовательно, и триггеры 4 и 5, находящиесяв этом столбце, находятся в нулевом состоянииИсходный граф заносится в матрицу в инверсном порядке, т.е, матрица сличимости заносимого графа транспортирована относительно главной диагонали. Это позволяет для расчета максимальных путей в графе использовать процедуру динамического программирования.С появлением пускового сигнала на входе 14 срабатывает триггер 14 блока 9 управления и устанавливается в нулевое состояние, С инверсного выхода этого триггера поступает единичный потенциал и открывает элемент И 10, в результате чего импульсы с генератбра 8 через элемент И 10 поступают на входы всех элементов 16 16 запрета и на счетные входы счетчиков 3 всех формирователей 2. При этом начинают работать счетчики 3 тех формирователей 2, которые моделируют веса дуг, исходящих из началь. ного узла графа, за счет подачи высокого потенциала с выхода элемента И б на разрешающие входы счетчиков 3 формирователей 2 н - 2, . Импульсы от генератора 8 проходят на регистрирующие счетчики 17 всех вершин графа, кроме начальной, так как на выходе элемента И б, устанавливается высокий потенциал, следовательно, элемент 16 запрета не пропускает импульсы от генератора 8 на регистрирующий счетчик 17, . Отсчитав число импульсов, пропорциональное весу моделируемой дуги, счетчик 3 одного из формирователей 2 переполняется, устанавливается в нулевое состояние соответствующий триггер 4 и на вход соответствующего элемента И 6 поступает высокий потенциал с инверсного выхода этого триггера. Если на остальных входах этого элемента И б находится высокий31 3 13190 потенциал, единичный уровень поступает на соответствующий элемент 16 запрета и закрывает его. Это свидетельствует о том, что все веса дуг, входящих в узел графа, номер которого соответствует номеру столбца формирователей 2, объединенных этим элементом И 6, сформированы, При этом формируется разрешение работы счетчиков 3 формирователей 2, моделирующих 10 ветви графа, исходящие из формированного узла графа. На выходе счетчика 17 данного столбца фиксируется время максимального пути для данной вершины графа, 15Подсчитывание импульсов в счетчиках 17 продолжается до тех пор, пока на выходах всех элементов И 6 не присутствует высокий потенциал. Это свидетельствует о том, что все узлы 20 исследуемого графа сформированы. Все это время на выходах 2 1 блока сортировки информации 19 присутствуют нулевые потенциалы, так как он закрыт по управляющему входу 28. Одновремен ное наличие единичных потенциалов на входах элемента И 11 приводит к срабатыванию триггера 12 блока 9 управления. На вход элемента И 10 поступает нулевой потенциал, который пре кращает подачу импульсов генератора 8 в схему, В это же время сигналом с единичного выхода триггера 12 сбрасываются все триггеры 5, которые установлены в единичное состояние и информация записанная в них, переписывается в триггеры 4, так как триггеры 4 и 5 управляются передним фронтом импульса.40 Таким образом, в триггеры 4 всех формирователей 2 переписывается информация о топологии ориентированного графа. После этого единичный потенциал, задержавшись на линии 45 задержки 7 на время, необходимое для срабатывания элементов матрицы формирователей 1, поступает на управляющий вход 28 блока сортировки информации и открывает его. Так как 50 начальная вершина графа.не зависит ни от каких других, на всех входах элемента И 6 появляются единичные потенциалы, на его выходе появляется высокий потенциал, который, поступая на вход элемента И 18 разрешает подачу с выхода счетчика 17, кода на вход 20 блока 19 сортировки информации, который обеспечивает появление высокого потенциала на одном или нескольких выходах, которые соответствуют максимальному кодуподаваемому на его входы, Вследствие этого высокий потенциал с выхода 21, блока 19 сортировки информации записывается в первый разряд регистра 23 приоритетов, на выходе которого в первом разряде появляется высокий потенциал и поступает на выход 25 и далее к диспетчеру вычислительной системы, который выбирает на реализацию соответствующую программу. После выбора соответствующей программы для реализации ее в вычислительной системе диспетчер записывает единицу в соответствующий разряд регистра 24 выбранныхвершин, которая обнуляет соответствующий разряд регистра 23 и счетчик 17.До момента выполнения подпрограммы,выбранной на реализацию в устройстве, никаких изменений не происходит. После выполнения данной подпрограммы диспетчер посылает единичный сигнал на соответствующий вход 27, который обнуляет триггеры 4 соответствующей строки формирователей 2. После этого появляются единичные сигналы на выходе элемента И 6 одного или нескольких столбцов. Дальнейшая работа устройства происходит аналогичноописанному, При наличии в регистре 23 приоритетов нескольких единиц диспетчер выбирает очередной ту программу, для которой номер разряда, содержащего единицу, наименьший.Когда все программы взяты на обслуживание, во всех разрядах регистра 24 записаны единицы, которые откроют элемент И 13, с выхода которого единичный сигнал поступает на выход 15, сигнализируя о том, что работа устройства закончена, Этим же сигналом сбрасываются все разряды регистра 24, После восстановления исходного состояния схемы весь цикл можно повторить заново.Блок 10 сортировки информации содержит однородную структуру размером М х М (фиг. 2), где М - разрядность счетчика 17, И - количество столбцов . матрицы 1 (фиг1), блок элементов И 31 с управляющим входом 32, Таким образом, на каждую строку матрицы (входы 20, - 20) поступает одно число,а одноименные разряды всех чисел рас положены в одноименных столбцах матрицы (старшие разряды слева). Для(х =хетаг- вертикальные каналыу =у поиска максимума используется алгоритм поразрядного сравнения всех чи.сел, который состоит в следующем.1-й шаг. Просматриваются информационные входы 20, - 20 левого(первого) столбца, т.е. старшие разряды всех И чисел, Если все эти разряды содержат нули, на следующем шагепросматриваются вторые разряды всехИ чисел, Если же в первом разряде: 10имеются как нули, так и единицы, навтором шаге просматриваются толькочисла, которые имеют в первом разряде единицы,3-й шаг, Просматриваются информационные входы -го столбца в тех строках, которые выделены на (1-1)-м шаге, Если все эти разряды содержат нули, на следующем шаге просматриваются(3+1)-е разряды тех же строк, Если 20на просматриваемых информационныхвходах имеются как нули, так и единицы, на (3+)-м шаге просматриваютсятолько строки, соответствующие единицам, Выделенное на последнем (М-м)шаге подмножество строк содержит максимальное число.Данный алгоритм реализован с помощью двумерной интеративной сети сдвумя направлениями распространения ЗОмежэлементных сигналов.В горизонтальном направлении имеется цепь, просматривающая последовательно, слева направо, информационные входы и продолжающая этот просмотр, если на данном информационномвходе находится единица или если навсех просматриваемых информационныхвходах в данном столбце находятся нули,Эту работу выполняет двоичный канал, 40реализующий в каждой ячейке 29 (фиг,3)итеративной сети логическую функциюг =г (а у),где к - сигнал на боковом выходе 39ячейки 29;к - сигнал на боковом входе 38,а - информационный вход 37у - переменная, характеризующаясодержимое просматриваемых50ячеек данного столбца (вход36) : у = 1, если все.онисодержат нули и у = 0 - впротивном случае.На входе 38 (г) всех ячеек левого 55столбца матрицы поданы граничные константы к =1 (вход 34 блока 19 сортировки информации). Поэтому наличиесигнала ж =1 (на выходе 39) в гори 31 6зонтальном канале любой строки означает, что данная строка подлежит дальнейшему просмотру (в противном случае сигнал г принимает значение "0", которое в дальнейшем измениться не может).В каждом столбце организована вер тикальная цепь, проверяющая содержи- . мое всех просматриваемых ячеек и вырабатывающая переменную у. Эту работу выполняет двоичный канал, реализующий в каждой ячейке 29 логическую функцию где х - сигнал на нижнем выходе140 ячейки 29х - сигнал на верхнем входе 35ячейки 29.На входы х (вход 35) всех ячеек 29 верхней строки матрицы подаются граничные константы х= О. Поэтому межэлементный сигнал х (выход 40) принимает значение " 1" в первой же (начиная сверху) ячейке 29, которая подлежит просмотру (я 1), и содержит единицу (а = 1), причем х = 1 в дальнейшем измениться не может. Только в таком случае, если в проверяемом столбце нет ни одной такой ячейки, в вертикальном канале сохраняется х = 0 и на выходе 41 нижней (Я-й) ячейки столбца вырабаты(1вается х = О,Для правильной работы горизонтальных каналов организован еще один проходной вертикальный канал у (вход 36) и соединен в каждом столбце его вход с выходом х (выход 40) через инвертор 30. Вся система логических функций ячейки итеративной сети, реализующей поиск максимума, имеет следующий вид:1 =г(аиду) - горизонтальный канал у =х - вспомогательная функция.о йПосле подачи граничных сигналов г,=1, х =0 сигналы г =1 на правой границе матрицы установятся в строке или нескольких строках, которые содержат максимальные числа.Разрешающий сигнал поступает на вход 28 блока 19 сортировки информации и поступает на управляющий вход 32 блока элементов И 31, разрешая7 13 прохождение информации с выхода матрицы через блок элементов И 31 на выходы 21, - 21 ц блока 19 сортировки,Формула изобретенияУстройство для распределения заданий процессорам, содержащее матрицу формирователей весов дуг, а каждыйформирователь весов дуг содержит счет чик и первый триггер, а также группу из Я элементов И (0 - число вершин графа), генератор тактовых импульсов, блок управления, содержащий два элемента И и триггер, группу из Н счетчиков, группу из И блоков элементов И, регистр приоритетов, регистр выбранных вершин, блок сортировки, причем в каждом формирователе весов дуг матрицы выход переполнения счетчика соединен с К-входом первого триггера, нулевой выход первого триггера формирователей весов дуг -го (ь1,Ю) столбца матрицы соединен с соответствующими входами -го элемента И группы, выход которого соединен с входами запуска счетчиков формирователей весов дуг ь-й строки, К-вход триггера блока управления соединен с входом пуска устройства, первый вход первого элемента И блока управления соединен с выходом генератора тактовых импульсов, входы второго элемента И блока управления соединены с выходами элементов И группы, а выход второго элемента И блока управления подключен к Я-входу триггера блока управления, группа выходов ь-га счет чика группы соединена с группой входов -го блока элементов И группы блоков элементов И, группа выходов которого соединена с 1-й группой информационных входов блока сортировки информации, х-й выход которого соединен с входом установки 1-го разряда регистра приоритетов, выходы которого являются группой информационных выходов устройства, группа входов установки регистра выбранных вершин является первой группой ин19031 формационных входов устройства, о тл и ч а ю щ е е с я тем, что, с целью расширения области применения устройства, в каждый формирователь весов дуг введены матрицы формирователей, второй триггер, а в устройство введено М элементов запрета,элемент задержки, в блок управлениявве. ден третий элемент И, причем в каж дом формирователе весов дуг матрицы нулевой выход второго триггера соединен с 1-входом первого триггера, К-входы первых триггеров формирователей весов дуг х-й строки матрицы 15 соединены между собой и подключены к -му входу второй группы информационных входов устройства, прямые входы элементов запрета соединены с выходом первого элемента И блока уп авления, выход -го элемента запрета соединен со счетным входом д-го регистрирующего счетчика, группа вхо,дов третьего элемента И блока управления соединена с группой выходов регистра выбранных вершин, выход третьего элемента И блока управления соединен с сигнальным выходом устройства и с входами сброса всех разрядов регистра выбранных вершин, 30 выход -го разряда регистра выбранных вершин соединен с входом сброса, -го регистрирующего счетчика и с входом сброса 1-го разряда регистра приоритетов, выход -го элемента 35 И группы соединен с входом -го блока элементов И группы блоков элементов И и с инверсным входом -го элемента запрета того же столбца прямой выход триггера блока управления 40 соединен с К-входами вторых тригге- ров всех формирователей весов дуг матрицы и с входом элемента задерж.ки, выход которого соединен с управляющим входом блока сортировки инфор 45 мации, нулевой выход триггера блока управления соединен с вторым входом первого элемента И блока управления, выход которого соединен со счетными входами счетчиков всех формирователе 50 весов дуг матрицы.131 9031 го Х Зб Составитель М.Сорочангулич Техред М.Хаданич Редакто ешетни оррек Тираж 672Государственлам иэобретеосква, Ж,одписное ское предприятие, г. Ужгород, ул. Проектная, 4 роизводственно-поли Закаэ 2513/43 ВНИИПИ по д 113035, ого комитета СССРий и открытийРаушская наб д. 4