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

/46 5 0 0 ННЫЙ КОМИТЕТ ИЯМ И ОТКРЫТ ОСУДАРСТВ О ИЗОБРЕТ РИ ГКНТ СС Е ИЗОБРЕТЕНИЯ ПИСА У. С В ИДЕТ ЕЛ Ь СТВУ ОРС Цель изобретения - расширение области применения устройства за счет учета времени выполнения заданий каждым процессором. Устройство для распределения заданий в неоднородной вычислительной среде содержит К блоков регистров (К - число процессоров), (К+ 2) группы блоков элементов И, К блоков элементов ИЛИ, формирователь импульсов, регистр, три триггера, два элемента задержки, два блока элементов И, дешифратор, группу сумматоров, группу счетчиков, генератор импульсов, элемент ИЛИ-НЕ, два элемента И, группу триггеров, элемент ИЛИ, Устройство позволяет распределять задания на процессоры, имеющие различную производительность. 1 ил..С,Скорытченк ство СССР46, 1984.ство СССР46, 1989.РАСПРЕДЕРОДНОЙ В ЕНИЯ 1 ЧИСтся к вычислитель- айти применение в темах для распреду процессорами. мента задержки, группу элементов И, блок регистров, дешифратор, блок элементов ИЛИ, группу сумматоров, генератор и пульсов, элементы И, ИЛИ, ИЛИ - НЕ, груп выходных триггеров. Устройство распре ляет задания процессорам с учетом вып нимости директивных сроков в однородн многопроцессорной системе.Недостатком данного устройства яв ется невозможность распределять задан в неоднородных вычислительных средах за отсутствия учета в нем времени выпал ния заданий каждым процессором.Цель изобретения - расширение области применения устройства за счет учета времени выполнения заданий каждым процессором. Изобретение относится к вычислительной технике и может найти применение в многопроцессорных системах для распределения нагрузки между процессорами.Известно устройство для распределения заданий процессорам, содержащее блок памяти, элемент И - НЕ, блок перебора перестановок, элементы памяти и дешифратор.Недостатком этого устройства является то, что оно не может динамически распределять запросы между процессорами с учетом их загруженности.Наиболее близким к изобретению является устройство для распределения заданий процессорам, содержащее формирователь импульсов, регистр, два триггера, два эле(21) 4802566/24(57) Изобретение относиной технике и может нмногопроцессорных сисделения нагрузки меж м(Л пу О деол- ( ) ой1 ия из- не 1725220На чертеже приведена структурная схема устройства.Устройство содержит сигнальный вход 1 устройства, группы информационных входов 2, вход 3 запроса устройства, входы 4 кода запрашиваемой функции, информационные входы 5, сигнальный выход 6 устройства, формирователь 7 импульсов, триггер 8, регистр 9, элемент 10 задержки, блок элементов И 11, группу блоков элементов И 12, блоков 13 регистров, дешифратор 14, К групп по п блоков элементов И 15, К блоков элементов ИЛИ 16, группу сумматоров 17, генератор 18 импульсов, второй элемент 19 задержки, элемент ИЛИ - Н Е 20, первый элемент И 21, группу блоков элементов И 22, элемент И 23, второй триггер 24, группу счетчиков 25, триггер 26, группу выходных триггеров 27, элемент ИЛИ 28, блок элементов И 29,Устройство работает следующим образом.В исходном состоянии все триггера, счетчики и сумматоры устройства и регистр 9 обнулены. В 1-м регистре 1-го блока 13 записано значение кода, соответствующего допустимому времени ожидания обслуживания заявки на 1-ю функцию при назначении ее на 1-й процессор, представленное в обратном коде рассчитывается заранее, какразность между допустимым временем ожидания и временем решения -й функции на -м процессоре),Запросы на обслуживание поступают от одного источника с минимальным допустимым интервалом между двумя соседними запросами, большим, чем максимально возможное время работы устройства (под временем работы устройства здесь понимается цикл выбора запроса от момента поступления сигнала запроса на вход 3 до момента поступления сигнала на вход 1, устанавливающий устройство в исходное состояние).Код запрашиваемой функции поступает по входам 4 в регистр 9. Одновременно на управляющем входе 3 появляется сигнал запроса на выполнение запрашиваемой функции, который устанавливает триггер 8 в единичное состояние и подается на формирователь 7 импульсов, на выходе которого появляется импульс, поступающий на элемент 10 задержки, Сигнал с единичного выхода триггера 8 открывает блок элементов И 11 и разрешает прохождение кода запрашиваемой функции с регистра 9 на дешифратор 14, На выходе дешифратора 14, соответствующем коду запрашиваемой функции, появится сигнал, открывающий соответствующие блоки элементов И 15, Коды допустимого времени ожидания запра 5 10 15 20 25 30 35 40 45 50 55 шиваемой функции через блоки элементов И 15 и блоки элементов ИЛИ 16 поступают на соответствующие входы сумматоров 17. По информационным входам 2 устройства через блоки элементов И 12, открываемые по второму входу задержанным управляющим сигналом устройства, с выхода элемента 10 задержки на соответствующие сумматоры 17.поступают коды суммарного времени дообслуживания всех заявок в соответствующих процессорах. Таким образом, в сумматорах 17 производится операция вычитания из кода обслуживания заявок на соответствующем процессоре кода допустимого времени ожидания запрашиваемой функции на соответствующем процессоре,Импульс, поступивший с элемента 10 задержки на элемент 19 задержки, задерживаясь в последнем, поступает на единичный вход триггера 24, на первый вход элемента И 23 и первые входы блоков элементов И 22. Результат операции вычитания, полученный в сумматоре 17, поступает на соответствующий счетчик 25 только в том случае, когда на знаковом выходе этого сумматора 17 присутствует единичный сигнал, открывающий соответствующий блок элементов И 22, при поступлении на него импульса с выхода элемента 19 задержки. Одновременно сигналы со знаковых выходов сумматоров 17 через элемент ИЛИ-НЕ 20 поступают на второй вход элемента И 23, При поступлении импульса с элемента 19 задержки на первый вход элемента И 23 на его выходе появится единичный сигнал только в случае, когда все знаковые разряды сумматоров 17 имеют нулевое значение, т.е. запрашиваемая функция ни на одном процессоре не может быть выполнена без нарушения директивного срока. Импульс с выхода элемента И 23, проходя через элемент ИЛИ 28, поступает на выход 6 устройства, а также устанавливаеттриггер 26 в единичное состояние, сигнал с инверсного выхода которого подается на вход элемента И 21, закрывая его и тем самым запрещая прохождение импульсов с генератора 18 на счетчики 25.Высокий потенциал с прямого выхода триггера 24 поступает на вход элемента И 21 и в случае, когда с инверсного выхода триггера 26 на вход элемента И 21 поступает единичный сигнал, разрешает поступление импульсов с генератора 18 на счетные выходы счетчиков 25, На выходе переполнения того счетчика 25 появится импульс, вход в котором максимален. Импульс переполнения устанавливает соответствующий триггер 27 в единицу ичерез элемент ИЛИ 28 поступает на сигнальный выход 6 устройст1725220 5 10 15 20 25 30 35 40 45 50 55 ва и устанавливает в нулевое состояние триггер 8, регистр 9, сумматоры 17, счетчики 25 и триггер 24. При наличии сигнала на выходе переполнения двух и более счетчиков устанавливается тот триггер 27, номер которого меньше, так как соответствующие элементы И 29 с большими номерами запираются сигналом с выхода счетчика 25 с наименьшим номером. Тем самым достигается однозначный выбор процессора для назначения.С выхода соответствующего триггера 27 на выход 5 устройства поступает единичный сигнал, определяющий процессор, которому назначается на обслуживание запрашиваемая функция. Если на выходе 6 устройства появится импульс, означающий окончание цикла выбора процессора, и ни на одном из выходов 5 устройства нет единичного сигнала, то запрос на выполнение запрашиваемой функции не принимается к обслуживанию, По окончании цикла выбора система посылает импульс по выходу 1 устройства, устанавливающий триггера 26, 27 в исходное состояние. Формула изобретения Устройство для распределения заданий в неоднородной вычислительной среде, содержащее формирователь импульсов, регистр, с первого по третий триггеры, два элемента задержки, два блока элементов И, с первой по третью группы блоков элементов И, блок регистров, дешифратор, блок элементов ИЛИ, группу сумматоров, группу счетчиков, генератор импульсов, элемент ИЛИ - НЕ, два элемента И, группутриггеров, элемент ИЛИ, выход которого соединен с входами сброса сумматоров группы, счетчиков группы, первого и второго триггеров и регистр, выход которого соединен с первым входом первого блока элементов И, второй вход и выход которого соединены с выходом первого триггера и входом дешифратора, запросный вход устройства соединен с единичным входом первого триггера и череЗ формирователь импульсов и первый элемент задержки с первыми входами блоков элементов И первой группы и входом второго элемента задержки, выход которого соединен с единичным входом второго триггера, первыми входами блоков элементов И второй группы, первым входом первого элемента И, выход которого соединен с единичным входом третьего триггера и первым входом элемента ИЛИ, информационный вход устройства соединен с вторыми входами блоков элементов И первой группы, выходы которых соединены с первыми информационными входами соответствующих сумматоров группы, информационные выходы которых соединены с вторыми входами соответствующих блоков элементов И второй группы, выходы которых соединены с информационными входами соответствующих счетчиков группы, выходы переполнения которых соединены с входами элемента ИЛИ и единичными входами триггеров группы,знаковые выходы сумматоров группы соединены с третьими входами соответствующих блоков элементов И второй группы и входами элемента ИЛИ-НЕ, выход генератора импульсов соединен с первым входом второго элемента И, второй вход которого соединен с выходом второго триггера, а выход соединен с суммирующими входами счетчиков группы, сигнальный вход устройства соединен с нулевым входом третьего триггера и нулевыми входами триггеров группы, выходы которых являются сигнальными выходами устройства, выход переполнения первого счетчика подключен к единичному входу первого триггера группы,выходы переполнения счетчиков группы соединены с входами второго блока элементов И, группа выходов которого соединена с единичными входами. соответствующих триггеров группы, выход третьего триггера соединен с третьим входом второго элемента И,отл ича ющееся тем,что,сцелью расширения области применения устройства за счет учета времени выполнения задания каждым процессором, в него дополнительно введены Кблоков регистров, (К - 1)-я группа блоков элементов И, К - 1 блоков элементов ИЛИ (К - число и роцессоров), причем выход М-го блока регистров(М =1,К) соединен с первыми входами М блоков элементов И М-й группы, вторые входы которых соединены с соответствующими выходами дешифратора, выходы блоков элементов И М-й группы соединены с входом М-го блока элементов ИЛИ, выход которого соединен с вторым информационным входом соответствующего сумматора группы.1725220 Составитель В.ЛясковскийТехред М,Моргентал Корректор Э,Лончаков В,Д аз 1177 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ ССС 113035, Москва, Ж, Раушская наб., 4/5 оизводственно-издательский комбинат "Патент", г, Ужгород, ул.Гагарина, 1