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

ОЮЗ СОВЕТСНИХ ОЦИАЛИСТИЧЕСНИРЕСПУБЛИН СССРНРЫТИЙ ОСУДАРСТВЕННЫЙ НОМИТ О ДЕЛАМ ИЗОБРЕТЕНИЙ И ПИСАНИЕ ИЗОБРЕТЕНИЯВТОРСКОМУ СВИДЕТЕЛЬСТВУ(56) Авторское свидетельство СССР У 620976, кл, С 06 Р 7/02, 1977.Авторское свидетельство СССР У 966697, кл. 6 06 Р Э/46, 1981. (54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ ЗАДАЧ ПРОЦЕССОРАИ.(57) Изобретение относится к вычислительной технике и может быть использовано в многопроцессорной или многомашинной вычислительной системе для равномерной по времени выполнения задач загрузки процессоров. Цель изобретения - расширение функциональ ных возможностей устройства за счет обеспечения равномерного по времени -распределения задач процессором.Устройство для распределения задач процессорам содержит элемент ИЛИ,.регистр, блок элементов И, первый счетчик, ш каналов; каждый из которых.зонаыг50 4 С 06 Г 9/46 содержит сдвигающий регистр, первый элемент И, первый триггер, схему сравнения, элементы ИЛИ-НЕ, первые элементы НЕ, ИЛИ и в него введены элемент НЕ, сдвигающий регистр, блок памяти, второй счетчик, дешифратор, блок регистров, а в каждый канал введены вторые элементы НЕ, элементы И и ИЛИ, вторые триггеры, Сущность изобретения состоит в использовании элементов НЕ на выходе кольцевых сдвигающих регистровкоторые формируют инверсные коды времени выполнения задач по сигналам с регистра управления таким образом, что в блок регистров устройства заносятся пози ю ционные коды номеров задач с минимальным и максимальным временем выполнения. Применение новых элементов позволяет организовать работу устройст-. ва в режиме поиска минимального и максимального кодов, группировать задачи по процессорам таким образом, чтобы общее вр мя выполнения всех задач было минимальным. 1 табл. 1 ил, 1425671Изобретение относится к вычислительной технике и может быть использовано при организации вычислительного процессора в многопроцессорной (МПС) или в многомашинной (ММС) вычислительной системе,Цель изобретения - расширение фун,кциональных возможностей устройства ;за счет обеспечения равномерного по времени распределения задач процессором.На чертеже изображено предлагаеое устройство.15Устройство содержит сдвигающие регистры 1, элементы НЕ 2, элементы3, элементы И 4,элементы ИЛИ 5, лементы И 6, триггеры 7, триггеры 8, лементы И 9, элементы И 10, элемен гы ИЛИ 11, схемы 12 сравнения, элеенты ИЛИ-НЕ 13, первые элементы НЕ ,14, элементы ИЛИ 15, элемент ИЛИ 16,егистр 17, блок элементов И 18, счетчик 19, элемент НЕ 20, сдвигающий 25 егистр 21, блок 22 памяти, счетчик 3, дешифратор 24, блок 25 регистров, синхронизирующие входы 26,27, 28 и 29 стройства, входы 30 кода управления стройства, вход 31 установки устрой 6 тва, выходы 32 устройства.Работа устройства начинается с приведения в исходное состояние элементов схемы.В блок 22 заблаговременно записываются коды управления: система диагностирования МПС (ММС) выставляет на входы 30 адрес чтения блока 22, который соответствует числу исправных Вроцессоров, в результате чего в регистр 21 записьвается рабочий код управления; с первого синхронизирую- щего входа 26 устанавливаются в нулевое состояние триггеры 8; с синхронизирующего входа 27 приводятся в нулевое состояние информационные разряды регистра 17; приводятся в исходное состояние (нулевое) счетчики 19 и 23; с входа 29 через элементы И 10 и ИЛИ устанавливаются в единичное50 состояние триггеры 7; с входа 29 подается сигнал на сдвиговый вход регистра 21 управления, в результате чего на его информационном выходе появляется первый разряд кода управ- . ления; с четвертого синхронизирующе 55 го входа 29 подается сигнал на счетчик 23, в результате чего с него считывается первое кодовое число, танавливается режим поис ного кода. При этом пода ный сигнал на третий эле разрешая тем самым прохож а максималь тся единичент И 4,дение прянт ИЛИ 5. а на первый эле ого Как указывалось, вид кода управления определяется количеством исправных процессоров в МПС (ММС) и при дешифрация которого приводит к возбуждению первой выходной шины дешифратора 24; с входа 31 в регистры 1заносятся коды, соответствующие длительности решения задач в МПС (ММС),таким образом, чтобы нумерация задачсоответствовала нумерации регистра 1,количество решаемых задач М,Работа устройства осуществляетсяв двух режимах: поиска минимальногокода времени выполнения. задачи и поиска максимального кода времени выполнения (далее по тексту соответственно минимальный и максимальный код).Количество разрядов кода управлениясоответствует числу выполняемых задач на МПС (ММС). Если МПС содержитН процессоров и Нс М, число кодовуправления равняется Н(случаи,когда Н=М и Н=1 не рассматриваются,так как при этом назначение однозначное и не возникает оптимизационнойзадачи), Таким образом, при фиксированном числе выполняемых на МПС задач, в случае отказов процессоров,возникает Нпроцедур оптимизациизагрузки процессоров по времени выполнения. И поэтому в блоке 22 записываются Нкодов, считывание которых происходит при подаче на вход 30устройства с системы диагностирования (СД) МПС адреса, соответствующего состоянию ПМС (по числу исправных процессоров), Рабочий ход управления записьвается в регистр 21 управления, При последовательном считывании с выхода регистра 21 разрядов кода управления устройство работает в режиме поиска минимальногокода или максимального. Если с регистра 21 считывается "0", то устанавливается режим поиска минимальногокода, При этом на выходе элементаНЕ 20 появляется единичный сигнал,разрешающий прохождение инверсногокода с регистра 1, через элемент НЕ 2и на второй вход второго элементаИ 3, и далее через второй элементИЛИ 5 на первый элемент И 6. Если срегистра 21 считьвается "1", то ус 1425671МЯ )ф М- )Н 229 О Я=2,35 45 его формировании рассматриваются.следующие соотношения между числомпроцессоров и количеством задач М: Для описания алгоритма формирования кодов управления рассмотрим информационное поле ПЗУ в виде таблицы,15 Значение каждого разряда строки ("О" и 1) соответствует одному из режимов работы устройства. Для поиска только максимального кода необходимо строку 3 заполнить всеми 20 единицами, Если необходимо работать только в режиме поиска минимального кода, строка 3 заполняется нулями, Для оптимального распределения задач на процессоры МПС (ММС) код управления 25 режимами работы необходимо формировать следующим образом:МСлучай 1. МН-сОпределяется номерпозиции 30 строки 3, начиная с которой записываются чередующиеся нуль и единица (в сторону уменьшения номеров задач): з. = М - (и - 3)2. Остальные позиции заполняются единицами. М2Определяется номер д позиции стро ки 3, начиная с которой записываются чередующиеся единица и нуль (в сторону уменьшения номеров задач): Остальные позиции заполняются нулями,Случай 3, Н = 2,Начиная со старшего номера задачи,в строке проставляются чередующиеся 50единица и нуль..По указанному алгоритму составляет ся таблица записей блока 22 для одного фиксированного числа задач. Таким же образом составляются таблицы и для55 различного числа решаемых на МПС задач, С учетом вышесказанного для считывания из блока 22 в регистр 21 рабочей строки адрес, подаваемый на вход 30 устройства, должен учитывать число решаемых задач (номер таблицы) . н число исправных процессоров.Устройство работает следующим образом.При считывании с регистра 21 первого разряда кода управления устанавливается режим поиска минимального или максимального кода путем разрешения прохождения инверсного кода с регистра 1 на первый элемент И 6 через элементы НЕ 2,. И 3, ИЛИ 5 (в случае нулевого первого разряда) или прямого кода через элементы И ч и ИЛИ 5 (в случае единичного первого разряда)Так как в исходном состоянии на выходах всех триггеров 7 присутствует высокий потенциал, то сигнал с выхода триггера старшего разряда (эти триггеры не показаны) регистра 1; (1 = 1,М) через первый элемент И 6 поступает на вход элемента ИЛИ 16, на выходе которого возникает сигнал, если в сравниваемых разрядах хотя бы одного из кодов имеется единица, Этот сигнал поступает на первые входы каждой схемы 12 сравнения, на выходах которых возникает сигнал сброса соответствующего триггера 7, в том случае, если информация в сравниваемом разряде совпадает с нулем. С триггера 7 на первый элемент И 6 поступает запрещающий (низкий) потенциал перед началом сравнения следу ющих разрядов кода (инверсного или прямого).После процедуры сравнения старших разрядов инверсного или прямого кодов происходит подача импульса сдвига на третий синхронизирующий вход 28 устройства в результате чего в сдвигающих регистрах 1 происходит сдвиг кодов на один разряд, и процесс сравнения очередных разрядов продолжается, и т,д. до тех пор, пока число таких сдвигов и сравнений не будет равно числу М, о чем свидетельствует сигнал переполнения счетчика 19, Сигнал переполнения счетчика 19 поступает на первый вход блока элементов И 18, выходы которого подсоединены к входам регистра 17, К моменту появления сигнала переполнения на выходе счетчика 19 заканчивается процесс определения максимального кода (или кодов, если их несколько)Фактически, если устройство работаетв режиме поиска минимального кода,данный, найденный инверсный максимальный код соответствует минималь.ному коду, записанному в соответствующем регистре 1; В режиме поиска,максимального кода это максимальныйкод, При одновременном, единичномсостоянии нескольких триггеров 7 в,регистре 17 и на его выходах появляется один единичный сигнал т,е.,предпочтение отдается той задаче,порядковый номер которой наибольшийсреди задач, имеющих одинаковое требуемое время для решения. Это достигается за счет наличия элементов13 - 15,Таким образом, позиционный кодномера минимального или максимального кода фиксируется в регистре 2 О,17 и подается на информационныевходы блока 25 регистров, а также,обеспечивает .сброс соответствующеговторого триггера 8 в нулевое состо,яние. 25При приведении устройства в исходное состояние на выходе счетчика 23,устанавливается код, обеспечивающийпосле дешифрации на дешифраторе 24подачу сигнала разрешения записи кода в первый регистр блока 25 регистров. В дальнейшем при каждой подачесигнала на вход 29 на выходе счетчика устанавливается такой код, который обеспечивает активизацию второго,третьего, , и т.д. выходов дешиф 35ратора 24. В результате чего после:дующие позиционные коды номеров задачсоответственно заносятся во второй,третий. , регистры блока 25 регистров,После занесения в регистр блока 25регистров позиционного кода номеравыбранной задачи по входу 27 подается сигнал сброса регистра 17 в исходное нулевое состояние, по входу29 сигнал установки тех триггеров 7в единичное состояние, в канал которых триггер 8 еще находится в единичном состоянии (не было выбора соответствующей задачи). С входа 29 син-.хронизирующим сигналом происходитсдвиг на один разряд кода управленияв регистре 21 (установка следующегорежима поиска) и установка на счетчике 23 следующего кода, в результатечего на выходе дешифратора 24 активизируется очередная шина, с которойпоступает сигнал разрешения записи в следующий регистр блока 25 регистров:Далее по входу 28 подается сериясигналов сдвига, в результате чегообеспечивается процесс определенияномера очередной задачи для записи вблок 25 регистров и последующего назначения, Так как триггер 7 канала,где произошел выбор задачи, сигналом с входа 29 переведен в нулевоесостояние (через элементы И 10 и ИЛИ11), то код задачи, записанный всоответствующем регистре 1, не участвует в дальнейшем процессе сравнения,Таким образом, в результате работыпредлагаемого устройства в блоке 25регистров записаны позиционные кодыномеров всех задач, предназначенныхдля выполнения на МПС, времена выполнения которых (минимальное или максимальное) чередуются в порядке следования нулей и единиц в коде управления, При выборе первого максимального кода, максимальным становится следующий за ним код, Аналогично и дляминимального кода, Зная порядок, вкотором записаны коды номеров задач,и имея ввиду, что они также записаныв блоке 25 регистров в виде удобномдля назначения, установим несложныйалгоритм распределения задач междупроцессорами, который может быть реализован процессором управления МПС.Считывание кодов номеров выбранныхзадач осуществляется с выходов 32устройства,Формула изобретения Устройство для распределения задач процессорам, содержащее элемент ИЛИ, регистр, блок элементов И, первый счетчик, ш каналов (ш - число решаемых задач), каждый из которых, кроме первого и ш-го каналов., содержит,. сдвиговый регистр, первый элемент И, первый триггер, схему сравнения, эле,мент ИЛИ-НЕ, первый элемент НЕ и первый элемент ИЛИ, первый канал содержит сдвигающий регистр, первый элемент И, первый триггер, схему сравнения и элемент ИЛИ-НЕ, а ш-й канал содержит сдвигающий регистр, первый элемент И, первый триггер и схему сравнения, причем информационные входы сдвигающих регистров каждого канала соединены со своими выходами, сдвиговые входы сдвигающих регистров всех каналов соединены с первым син 1425671хронизирующим входом устройства и счетным входом первого счетчика,прямой выход первого триггера каждого канала соединен с первым входом пер 5 ваго элемента И, выход которого соединен с первым входом схемы сравнения и через первый элемент НЕ - с первым входом элемента ИЛИ-НЕ этого же канала и с соответствующим входом элемента ИЛИ, выход которого соединен с вторыми входами схем сравнения каждого канала, первый вход первого элемента И каналов с второго до 1(тп)-го соединен с первым входом первого элемента ИЛИ своего канала, второй вход первого элемента ИЛИ и элемента ИЛИ-НЕ каждого канала,кроме (ш)-го, соединен с выходом первого элемента ИЛИ следующего канала, второй вход первого элемента ИЛИ и элемента ИЛИ-НЕ (ш)-го канала соединен с первым входом первого элемента И т-го канала и первым управ- . ляющим входом блока элементов И, ос тальные управляющие входы которого соединены с выходами элементов ИЛИ-НЕ, группа информационных входов блока элементов И соединена с выходами первого счетчика, выходы блока элемен ЗО тов И соединены с входами регистра, вход сброса которого соединен с вторым синхронизирующим входом .устройства, отличающееся тем, что, с целью расширения функциональных возможностей за счет равномерного времени распределеяия задач процессорами, в него введены элемент НЕ, сдвигающий регистр, блок памяти, второй счетчик, дешифратор, блок регистров, а в каждый канал введены второй элемент НЕ,. второй, третий, четвертый и пятый элементы И, второй и третий элементы ИЛИ, второй триггер, причем выход сдвигающего регистра каждого канала соединен с первым входом второго элемента И и через второй элемент НЕ - с первыми входами третьих элементов И каналов, вторые входы вторых элементов И каналов соединены с выходом сдвигающего регистра и входом элемента НЕ выход которого соединен с вторыми входами третьих элементов И каналов, выходы второго и третьего элементов И каждого канала, кроме первого, соединены соответствецно с первым и вторым входами второго элемента ИЛИ и в первом канале выходы второго и третьего элементов И соединены соответственна с первым и вторым входами первого элемента ИЛИ, выход которого и выходы вторых элементов ИЛИ остальных каналов соединены с. вторыми входами первых элементов И своих каналов, единичный вход первого триггера соединен с выходом четвертого элемента И своего канала, вход сброса первого триггера каналов, кроме первого, соединен с выходом третьего элемента ИЛИ своего канала, первый вход которого соединен с выходом пятого элемента И своего канала, второй вход второго элемента ИЛИ,первого и третьего эле)ментов ИЛИ остальных каналов соединены с выходом схемы сравнения, вход сброса второго триггера каждого канала соединен с одноименным разрядом регистра и с соответствующими информационными входами блока регистров, выходы которых являются выходами устройства, единичный вход второго триггера каждого канала соединен с третьим синхронизирующим входом устройства, прямой выход второго триггера соединен с первым входом четвертого элемента И своего канала, инверсный выход второго триггера соединен с первым входом пятого элемента И своего канала, вторые входы четвертого и пятого элементов И каналов соединены с четвертым синхронизирующим входом устройства, со сдвиговым входом сдвигающего регистра и счетным входом второго счетчика, информационные выходы которого соединены с входами дешифратора, выходы которого соединены с входами разрешения записи блока регистров, информационные входы сдвигающего регистра соединены с информационными выходами блока памяти, адресные входы которого соединены с входами кода управления устройства, параллельные входы записи информации сдвигающих регистров каждого канала соединены с. входом устацовки устройства, вход сброса первого триггера первого канала соединен с выходом второго элемента ИЛИ, вход которого соединен с выходом гятого элемента И своего канала.1425 б 71 10 Число процессоров 1 2 афе 1еп 3 ииЧ и-гд Ч Ь-К=2 Поле кодов управления Адресное поле П р и м е ч а н и е, 1 = 1, К - число исправных процессоров,ставитель М. Кудряшов хред Х.Кравчук дактор Г. Гер ректор А. Обручар каз 4771/47 ира одписн/5 Проектн Производственно-полиграФическое предприятие, г. Ужгород Т ВНИИПИ Госуда по делам из 035, Москва, Номера задачХ Х ) венного комитета етений и открыти 5, Раушская наб.