Устройство планирования вычислительного процесса в мультипроцессорной системе

(46) 30.10.88.Бюл. У 4 (71) Минский радиотехн кий инстииж, В.П.Пискун и В.А,Вишняко 25 (088.8) ское свидетель кл. С 06 Р 15/ ое свидетельст кл. С 06 Р 15/(72) А.В.Ч О.В.Герман (53) 6813 (56) Автор Кф 877553,Авторск У 940164,тво СССР О, 1981. о СССР О, 1982. ИРОВАНИЯ ВЫЧИСЛИ- МУЛЬТИПРОЦЕССОР(54) УСТРОЙСТВО ПЛАН ТЕЛЬНОГО ПРОЦЕССА В НОЙ СИСТЕМЕ(57) Устройство отно тельной технике и пр функционирования в с цессорной ЭВМ для ав выбора очередной зад тся к вычисли назначено для таве мультипро томатического ачи нз множес ОСУДАРСТ 8 ЕННЫЙ КОМИТЕТ СССРОДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ К АВТОРСКОМУ СВИДЕТЬ ва задач со структурой, заданной ацикличным ориентированным графом, и для автоматического синтеза расписаний работ, Целью изобретения являет" ся расширение функциональных возможностей устройства эа счет переназначения выполнения задач через фиксированные кванты времени. Устройство содержит матрицу триггеров, две группы элементов ИЛИ-НЕ, пять групп элементов И, три группы счетчиков, две груп" пы триггеров, регистр выбранных вершин, регистр приоритета, шифратор, блок управления, состоящий из генератора тактовых импульсов, элемента И, схемы начального пуска, элемента ИЛИ Я и триггера, регистр текущих обрабатываемых задач, элемент ИЛИ, счетчик . тактовых импульсов, регистр кванта, генератор тактовых импульсов, входы- выходы. 1 ил.Изобретение относится к вычислительной технике и предназначено дляФункционирования в составе мультипроцессорной ЭВМ для автоматическоговыбора очередной программы иэ множества программ со структурой, заданной ациклическим ориентированнымграфом, а также для автоматическогосинтеза расписаний работ. 1 ОЦелью изобретения является расширение функциональных возможностейустройства эа счет переназначения выполнения задач через Фиксированныекванты времени. 15На чертеже показана Функциональная схема устройства.Устройство содержит матрицу 1 триггеров 2, группу. элементов ИЛИ-НЕ 3,по числу строк матрицы, группу элементов И 4 по числу столбцов матрицы, группу счетчиков 5, группу триггеров 6, группу элементов И 7, группу счетчиков 8, группу триггеров 9,группу элементов И 10, регистр 11 выб раиных вершин, реализованно на триггерах 111, регистр 12 приоритета,группу элементов И 13, шифратор 14,блок управления, состоящий иэ генератора 15 тактовых импульсов, элемента И 16, схемы 17 начального пуска, элемента ИЛИ 18, триггера 19, вход 20 пуска устройства, вход 21 записи в регистр 11, информационный выход 22 устройства, блок 23 управления в сос" таве указанных схем 15 - 19, группу элементов И 24, группу счетчиков 25, группу элементов ИЛИ-НЕ 26, регистр 27 текущих обрабатываемых задач, элемент ИПИ 28, счетчик 29 тактовых импульсов, регистр 30 кванта, генератор 31 тактовых импульсов, вход 32 признака обрабатываемой задачи устройства, вход 33 записи в счетчик 29, пусковой вход 34 генератора 31 выходы 35, 36 запроса на прерывание устройства. Для записи в регистры 12, 27 используются соответственно вход 21 и один из входов 32. Шифратор 14 представляет комбинационную схему, обеспечивающую возбуждение одного или нескольких своих выходов, соответствующих максимальному коду, хра" нящемуся в одноименных счетчиках.8,Устройство работает следующим образом.Первоначально в матрицу 1 заносится информация о топологии моделируемого графа. При этом триггеры 2;1 (1,1,п), которые являются формирователями дуг, устанавливаются в единччные состояния, если есть информационная связь из х-й вершины в 1-ю.Соответствующий триггер 2; определяется пересечением х-й строки и1-го столбца. Другие триггеры 2;а также триггеры 6,9,19, счетчикй 8,регистры 11, 12, 27 находятся в нулевом состоянии (цепи установки в начальные состояния и записи в регистры и триггеры не показаны). В счетчики 5 и 25 соответствующих вершинграфа заносятся числа импульсов, дополняющие "веса" вершин до полнойемкости счетчиков, в регистр 30 заносится код, дополняющий квант временидо полной емкости счетчика 29.Послезанесения исходной информации навыходах элементов ИЛИ-НЕ 3, объединяющих выходы триггеров 2 в строках,соответствующих конечным вершинамграфабудут высокие потенциалы, поскольку принято, что граф ацикличени для конечных вершин соответствующие триггеры 2 обнулены. Первоначаль"но в устройстве происходит определение величин максимальных путей,связывающих данные вершины с конечными(формируются значения уровней вершин). При этом пусковой сигнал навходе 20 схемы 17 начального пусказапускает генератор 15, с выхода которого импульсы поступают на входыэлементов И 4 и 7, а далее на всесчетчики 8, так как в исходном состоянии все триггеры 6 находятся в нулевом состоянии, управляющие входыэлементов И 7 подключены к инверснымвыходам триггеров 6," Кроме того,счетные импульсы поступают через эле-,менты И 4 на те счетчики 5, для которых триггеры 2 одноименной строки матрицы 1 находятся в нулевом состоянии.Поэтому на.выходе соответствующихэлементов ИЛИ-НЕ 3 появляется высокийпотенциал, благодаря чему на управляемом входе одноименного элемента И 4будет высокий потенциал,Отсчитав число импульсов, пропорциональное "весу" моделируемой вершины, счетчик 5 переполняется, сигналпереполнения устанавливает в единичное состояние соответствующий триггер6, а все триггеры 2 в данном столбцематричной модели сети 1 - в нулевоесостояниеПереброс триггера 6 в единичное состояние обеспечивает прекобработки в текущем кванте задачам.С учетом состояния регистра 27 устанавливается нулевой уровень на выхо-.де тех элементов ИЛИ-НЕ 26 дополнительной группы, которые соответствуютобрабатываемым задачам, тем самымэти задачивременно исключаются" изполя зрения ЗВМ-диспетчера. Послетого как готовые задачи будут назначены на процессоры, ЭВМ-диспетчерзагружает в счетчик 29 дополнение ве"личины кванта времени до полной емкости счетчика из регистра 30 квантауправляющим сигналом, подаваемым навход 33 устройства, и запускает генератор 31 тактовых импульсов путем по"дачи импульса на вход 34 устройства.Сигналы с генератора 31 подаются навход счетчика 29, а также через элементы И 24 на входы тех счетчиков 25и вычитающие входы тех счетчиков 8,для которых соответствующие разрядырегистра 27 установлены в "1". Поокончании выделенного кванта времени(счетчик 29 переполняется) или позавершении выполнения одной или нескольких задач (переполняется соот"ветствующий счетчик 25) соответствующий сигнал переполнения через элементИЛИ 28 сбрасывает регистр 27 текущихобрабатываемых задач и генератор 31,а также поступает на выход 35 устройства и далее на вход запроса на пре"рывание ЗВИ-диспетчера, сигнализируяо необходимости выбора следующих задач. Далее производится новый цикл.назначения. Как только какая-либо из1задач будет выполнена полностью, происходит переполнение соответствующего счетчика 25, при этом сигналпереполнения устанавливает в единицусоответствующий разряд регистра выбранных вершин 11. В результате на выходе элемента И 13 будет высокий по"тенциал, по которому триггер 9 переходит в единичное состояние; подачакода уровня данной задачи со счетчика 8 на входы шифратора 14 прекращается и на регистре 12 записывается другой код, по которому ЭБИ-диспетчер выбирает нереализованные задачи55 Ф о р м у л а изобретения з1434451 ращение подачи счетных импульсов через элемент И 7 на вход регистрирующего счетчика 8, в котором фиксируется код максимального пути из данной5 вершины до конечной вершины интерпретирующего графа.Рассмотренные действия повторяются до тех пор, пока на выходах всех триггеров 6 не будут присутствовать низкие потенциалы. На выходе элемента ИЛИ 18 будет низкий потенциал, в результате чего прекращается подача счетных импульсов с выхода генератора 15 через элемент И 16 на инфор мационные входы элементовИ 4,7, Свыхода триггера 19 высокий потенциал подается на вход оповещения, ЭВМ и управляющий вход шифратора 14, который обеспечивает появление высокого 20 потенциала на одном или нескольких из и своих выходов, которые соответствуют максимальному коду, хранящемуся в одноименном счетчике 8 при условии, что на первый управляемый вход 25 элементов И 10 подается высокий потенциал с выходов элементов ИЛИ-НЕ 26. В результате в регистре 12 устанав- .ливается код, определяющий задачи, если таковые есть, которые могут вы полняться. Если в регистре 12 .имеется хотя бы одна единица, то это значит, что задача, определяемая номером данного единичного разряда, может назначаться на обработку. Информация из регистра 12 поступает на выход 22 и далее на вход ЭВИ-диспетчера, Если код в регистре 12 нулевой,сто при отсутствии текущих выполняемых задач это значит, что обработка 40 графа завершена (предполагается, что ЭВМ-диспетчер ведет информацию о текущих выполняемых задачах, что позволяет распознавать подобные ситуа" ции),Кроме того, при наличии несколь ких единиц в регистре 12 требуется последовательная выборка задач на обработку (например, первой выполняется задача с минимальным номером разряда в регистре 2), причем после того,бО как выбор текущей задачи сделан, ЭВМ- диспетчер по входам 32 устройства ус-. танавливает в регистре 27 текущих обрабатываемых задач код, наличие "1" в в 1-м разряде которого определяет, что 1-я задача обрабатывается. При этом установка такого кода не должна разрушать ранее установленных единиц, соответствующих выбранным для Устройство планирования вычислительного процесса в мультипроцессорной системе, содержащее матрицу (пхп)514344 триггеров, блок управления, группу элементов ИЛИ-НЕ, две группы счетчиков, две группы триггеров, регистр . выбранных вершин, регистр приоритета, четыре группы элементов И, шифратор5 причем управляющий выход блока управления соединен с входом стробирования шифратора и является первым выходом запроса на прерывание устройства, выход шифратора соединен с инФормационным входом регистра приоритета, выход которого является информационным выходом устройства, разряды выхода регистра приоритета соединены с первыми входами элементов И первой группы, вторые входы которых сое- динены с разрядами выхода регистра выбранных вершин, выходы элементов И первой группы соединены с входами установки нуля соответствующих тригге ров первой группы, вход разрешения записи регистра приоритета является входом подтверждения готовности ЭВМ устройства, выходы элементов И второй 25 группы соединены с информационными входами шифратора, выходы элементов И третьей группы соединены с информационными входами счетчиков первой группы, выходы которых соединены с первыми входами элементов И второй группы, входы элементов ИЛИ-НЕ груп пы соединены с выходами триггеров со" ответствующих строк матрицы, выходы элементов ИЛИ-НЕ группы соединены с первыми входами элементов И четвертой группы, выход синхронизации блока управления соединен с вторыми . входами элементов И четвертой группы и первыми входами элементов И треть ей группы, выходы элементов И четвертой группы соединены с информационными входами счетчиком второй груп" пы, выходы переполнения которых сое" динены с входами сброса триггеров матрицы и входами установки нуля триггеров второй группы, инверсные выходы которых соединены с вторыми входами элементов И третьей группы и входом останова блока управления, вход запуска которого является входом пуска устройства, о т л и ч а ющ е е. с я тем, что, с целью расшир ения функциональных возможностейза счет переназначения выполнения задач через фиксированные кванты времени, в него введены пятая группа элементов И, третья группа счетчиков, дополнительная группа элементов ИЛИНЕ, регистр текущих обрабатываемых задач, элемент ИЛИ, счетчик тактовых импульсов, регистр кванта, генератор тактовых импульсов, причем информационный вход регистра текущих обрабатываемых задач является входом признака обрабатываемой задачи устройства, разряды выхода регистра текущих обрабатываемых задач соединены с первыми входами элементов ИЛИ-НЕ дополнительной группы и первыми входами элементов И пятой группы, вторые вхоы элементов ИЛИ-НЕ дополнительнойруппы соединены с прямыми выходами триггеров первой группы, выходы элементов ИЛИ-НЕ дополнительной группы соединены с вторыми входами элементов И второй группы, выход генератора тактовых импульсов соединен с информационным входом счетчика тактовых импупьсов и вторымивходами элементов И пятой группы, выходы которых годключены к вычитающим входам счетчиков первой группы соответственно и счетным входам счетчиков третьей груп. пы соответственно, выходы переполнения счетчиков третьей группы соединены с разрядами информационного входа регистра выбранных вершин и соот,ветствующими входами элемента ИЛИ, выход переполнения счстчика тактовых импульсов соединен с соответствующим входом элемента ИЛИ, выход которого соединен с входом сброса генератора тактовых импульсов, входом сброса регистра текущих обрабатываемых задач и является вторым выходом запроса на прерывание устройства, вход начальной установки счетчика тактовых импульсов соединен с выходом регистра .кванта, вход пуска генератора тактовых импульсов соединен с входом ,пуска устройства, а вход управления занесением информации счетчика тактовых импульсов является одноименнымвходом устройства./5 5,ушская н риятие, г. Ужгород, ул ектна изводственно-полиграфическое Заказ 5557/52 Тираж 704 ВНИИПИ Госуда по делам и 113035, Москва, Подписное ого комитета ССС ний и открытий