Устройство планирования вычислительного процесса в мультипроцессорной системе Советский патент 1988 года по МПК G06F15/163 

Изобретение относится к вычислительной технике и предназначено для функционирования в составе мультипроцессорной ЭВМ для автоматического выбора очередной программы из мно жества программ со структурой, задан™ ной ациклическим ориентированным графом, а также для автоматического синтеза расписаний работ.

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

На чертеже показана функциональная схема устройства.

Устройство содержит матрицу I триггеров 2, группу Элементов ИЛИ-НЕ 3, по числу строк матрицы, группу эле- ментов И 4 по числу столбцов матрицы, группу счетчиков 5, группу триггеров 6, группу элементов И 7, грзт- пу счетчиков 8, группу триггеров 9, группу элементов И 10, регистр 11 выб ранных вершин, реализованные на триггерах 1 If, регистр 12 приоритета, группу элементов И 13, шифратор 14, блок управления, состоящий из генера тора 15 тактовых импульсов, элемента И 16, схемы 17 начального nycKaj элемента ИЛИ 18, триггера 19, вход 20 пуска устройства, вход 21 записи в регистр 11, информационный выход 22 устройства, блок 23 управления в сое- таве указанных схем 15 - 19 группу элементов И 24, группу счетчиков 25, группу элементов ИПИ-НЕ 26, регистр 27 текущих обрабатываемых задач, элемент ИЛИ 28, счетчик 29 тактовых им- пульсов, регистр 30 кванта, генератор 31 тактовых импульсов, вход 52 признака обрабатьтаемой задачи устройства, вход 33 записи в счетчик 29, пусковой вход 34 генератора 31, вы- ходы 35, 36 запроса на прерывание устройства. Для записи в регистры 12, 27 используются соответственно вход 21 и один из входов 32. Шифратор 14 представляет комбинационную схему, обеспечивающую возбуждение одного или нескольких своих выходов, соот- ветствуюпдах максимальному коду, хранящемуся в одноименных счетчиках.8,

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

Первоначально в матрицу I заносится информация о топологии моделируемого графа. При этом триггеры 2; (i.

j - 1,n), которые являются формирователями дуг, устанавливаются в единичные состояния, если есть информационная связь из i-й вершины в jю Соответствующий триггер 2. определяется пересечением i-й строки и j-ro столбца. Другие триггеры 2 j: , , а также триггеры 6,9,19, счетчики 8, регистры 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 в единичное состояние обеспечивает прек

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

Рассмотренные действия повторяются до тех пор, пока на выходах всех триггеров 6 не будут присутствовать низкие потенциалы. На выходе элемента ИЛИ 18 будет низкий потенциал, в результате чего прекращается подача счетных импульсов с выхода генератора 15 через элемент И 16 на информационные входы элементов И 4,7, С выхода триггера 19 высокий потенциал подается на вход оповещения, ЭВМ и . управляющий вход шифратора I4, который обеспечивает появление высокого потенциала на одном или нескольких из п своих выходов, которые соответствуют максимальному коду, хранящемуся в одноименном счетчике 8 при условии, что на первый управляемый вход элементов И 10 подается высокий потенциал с выходов элементов ШШ-НЕ 26 В результате в регистре 12 устанавливается код, определяющий задачи, если таковые есть, которые могут выполняться. Если в регистре 12 .имеется хотя бы одна единица, то это значит, что задача, определяемая номером данного единичного разряда, может назначаться на обработку. Информация из регистра 12 поступает на выход 22 и далее на вход ЭВМ-диспетчера. Если код в регистре 12 нулевой, то при отсутствии текзпцих вьшолняе- мых задач это значит, что обработка графа завершена (предполагается, что ЭВМ-диспетчер ведет информацию о текущих вьшолняемых задачах, что позволяет распознавать подобные ситуа

ции).Кроме того, при наличии несколь- 45 ходе элемента И 13 будет высокий потенциал, по которому триггер 9 переходит в единичное состояние; подача кода уровня данной задачи со счетчика 8 на входы шифратора 14 прекраких единиц в регистре 12 требуется последовательная выборка задач на обработку (например, первой выполняется задача с минимальным номером разряда в регистре 12), причем после Toro,5Q щается и на регистре 12 записьшает- как выбор текущей задачи сделан, ЭВМ- ся другой код, по которому ЭВМ-дис- диспетчер по входам 32 устройства устанавливает в регистре 27 текущих об- рабатьшаемых задач код, наличие 1 в в i-M разряде которого определяет, gg что i-я задача обрабатывается. При этом установка такого кода не должна разрушать ранее установленных едипетчер выбирает нереализованные зад чи.

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

Устройство планирования вычислительного процесса з мультипроцессор ной системе, содержащее матрицу (пхп

ниц, соответств пощих выбранным для

0

5

0

5

обработки в текущем кванте задачам. С учетом состояния регистра 27 устанавливается нулевой уровень на выхо-. де тех элементов ИЛИ-НЕ 26 дополни- тельной группы, которые соответствуют обрабатьшаемым задачам, тем самым эти задачи временно исключаются из поля зрения ЭВМ-диспетчера, После того как готовые задачи будут назначены на процессоры, ЭВМ-диспетчер загружает в счетчик 29 дополнение величины кванта времени до полной емкости счетчика из регистра 30 кванта управляющим сигналом, подаваемым на вход 33 устройства, и запускает генератор 31 тактовых импульсов путем подачи импульса на вход 34 устройства. Сигналы с генератора 31 подаются на вход счетчика 29, а также через элементы И 24 на входы тех счетчиков 25 и вычитающие входы тех счетчиков 8, для которых соответствующие разряды регистра 27 установлены в 1, По окончании выделенного кванта времени (счетчик 29 переполняется) или по завершении выполнения одной или нескольких задач (переполняется соответствующий счетчик 25) соответствующий сигнал переполнения через элемент ИЛИ 28 сбрасывает регистр 27 текущих обрабатываемых задач и генератор 31, а также поступает на выход 35 устройства и далее на вход запроса на пре- 5 рьшание ЭВМ-диспатчера, сигнализируя о необходимости выбора следующих за- дач. Далее производится новый цикл ,назначения. Как только какая-либо из задач будет выполнена полностью, происходит переполнение соответствующего счетчика 25, при этом сигнал переполнения устанавливает в единицу соответствующий разряд регистра выбранных вершин 11. В результате на вы0

0

тенциал, по которому триггер 9 переходит в единичное состояние; подача кода уровня данной задачи со счетчика 8 на входы шифратора 14 прекращается и на регистре 12 записьшает- ся другой код, по которому ЭВМ-дис-

щается и на регистре 12 записьшает- ся другой код, по которому ЭВМ-дис-

петчер выбирает нереализованные задачи.

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

щается и на регистре 12 записьшает- ся другой код, по которому ЭВМ-дис-

Устройство планирования вычислительного процесса з мультипроцессорной системе, содержащее матрицу (пхп)

5

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

6

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

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

устройства, выходы элементов И второй 25 И второй группы, выход генератора

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

5

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

Q входом элемента ИЛИ, выход которого соединен с входом сброса генератора тактовых импульсов, входом сброса регистра текущи к обрабатываемых задач и является вторым выходом запроса на

g прерьюание устройства, вход начальной установки счетчика тактовых импульсов соединен с выходом регистра i-KBaHTa, вход пуска генератора тактовых импульсов соединен с входом пуска устройствas а вход управления - занесением информации счетчика тактовых импульсов является одноименным - входом устройства.

0