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

Фие.

код макс

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

Цель изобретения - повышение про- изводительности за счет изменения приоритетов процессоров н соответствии с пpиopитeтa и задач и их уве- личения в случае длительного ожидания.

На фиг.1 приведена функциональная схема многопроцессорной вычислительной системы; на фиг, 2 - функцио- нальная схема коммутатора; на фиг.З - вариант технической реализацж операционного блока; на фиг. 4 - функциональная схема блока подключения к операционной магистрали; на фиг.З - вариант блока процессора; на фиг.б - функциональная схема блока отсчета времени.

Многопроцессорная вычислительная сис тема содержит (фиг.1) внешнюю

память 1, операционную магистраль 2 и М процессоров 3, каждый из которых включает операционный блок 4,локальную память 5, коммутатор 6, шину 7 запроса магистрали и шшгу 8 занятия магистрали, блок 9 синхронизации.

На фиг.2 представлена функциональная схема коммутатора 6, содержащая селектор 10 адреса, блок 11 отсчета времени, первый и второй

элементы ИЛИ-НЕ 12,13, первый и второй регистры 14,15, первый, второй, третий и четвертый шинные формирователи 16 - 19, первый, второй и третий элементы НЕ 20-22, схему 23 срав нения, элемент 24, элемент И 25, первый и второй элементы ИШ 26, 27, элемент 28 задержки, треткй регистр 29.

Операционный блок 4 (фиг.З) со- держит блок 30 процессора, блок 31 подключения к магистрали, первый и - второй триггер 32,33 первый и второй элементы НЕ 34,35, элемент ИЛИ 36.

Блок 31 подключения к магистрали содержит первый, второй и третий шинные формирователи 37 - 39, элемент 40 задержки.

. Блок 30 процессора содержит микропроцессор 41, формирователь 42,первы и второй элементы НЕ 43, 44, триггер 45.

Блок 1 1 отсчета времени содерж;ят первый и второй элементы ИЛИ 46, 47,

первый, второй и третий элементы НЕ 48 - 50, первый, второй и третий элементы И 51-53, первый и второй триггеры 54,55, первый и второй счетчики 56,57, элемент 58 задержки.

Многопроцессорная вычислительная система работает следующим образом.

Обработка информации в каждом процессоре 3 производится операционным блоком 4, работа которого синхронизируется тактовыми импульсами блока 9. Обмен данными между процессором 3 и внешней памятью 1 осуществляется через операционную магистраль 2, по шинам которой в цикле обмена передаются адрес, данные и управляющие сигналы.

Рассмотрим взаимодействие операционного блока 4 с внешней памятью 1 (фиг,1). По сигналу Пуск,поступающему на вход запуска каждого операционного блока 4, монитор,помещенный в локальную память каждого процессора 3, записывает в соответствующий ему коммутатор 6 код приоритета первой выполняемой задачи. При необходимости обращения к внешней памяти 1.и отсутствии сигнала Предоставление магистрали на входе признака операционного блока 4 формируется на первом управляющем выходе этого блока сигнал Запрос магистрали и блок 4 переходит в состояние ожидания.

По сигналу Запрос магистрали в коммутаторе 6 происходит определение процессора 3, имеющего наивысший приоритет. В соревновании участвуют только процессоры 3, выставившие сигнал Запрос магистрали. Причем, если процессор долго находится в состоянии ожидания, то блок 1 отсчета времени автоматически повьшза ет его приоритет.

Коммутатор 6, соответствуюш 1Й наиболее приоритетному процессору, на выходе признака устанавливает сигнал представление магистрали , поступивший на одноименный вход операционного блока 4, по которому он выходит из состояния ожидания и осуществляет операцию обмена с внешней памятью 1. Сигнал Запрос магистрали при этом снимается и выставляется на втором управляющем выходе блока 4 сигнал Занятие магистрали.

В случае автоматического.повышения процессором своего приоритета.

сигналом Предоставление магистрали восстанавливается первоначальный код приоритета.

После завершения обмена с внешней памятью 1 операционный блок 4 снимает сигнал Занятие магистрали и при отсутствии запросов на обмен с внешней памятью 1 операционная магистраль 2 подключается к процессору 3, наибольшее время не обращавшемуся к внешней памяти.

Передача магистрали происходит следующим образом. Коммутатор 6, в блоке 11 отсчета времени которого содержится наибольший код,формирует на выходе признака сигнал Предоставление магистрали уровнем логической 1, по которому операционная магистраль 2 подключается к соответствующему операционному блоку 4. При необходимости обмена с внешней памятью 1 данный процессор 3 начинает обменбез сигнала запроса магистрали и перехода в режим ожидания. При появлении до начала обмена запросов от других процессоров, сигнал с шины 7 запросов магистрали на первом управляющем входе коммутатора 6 сбросит сигнал Предоставление магистрали и освободит операционную магистраль.

Рассмотрим разрешение конфликтов при одновременном обращении к внеш- ней памяти 1 нескольких процессоров. Если процессор 3 выставляет сигнал Запрос магистрали во время операции обмена с внешней памятью,си гнал Предоставление магистрали не прой- дет, так как он блокируется сигналом уровня 1 на втором управляющем входе коммутатора 6 с шины 8 занятия магистрали.

При свободной операционной магистрали 2 и наличии нескольких запросов магистраль будет предоставлена более приоритетному.процессору, который блокирует остальные, выставляя на втором.информационном выходе коммутатора 6 уровень О. При равенств приоритетов нескольких процессоров магистраль будет подключена к процессору с большим номером, который так же блокирует запросы от процессоров, имеющих номер меньше.

Кроме того, часть процессоров система может быть остановлена и выполнять команды динамического останова.

при выполнении которых

процессор может неопределенно долго не обращаться к магистрали. .

Ко 1мутатор (фиг. 2) работает следующим образом. Двоичный код приоритета выполняемой задачи заносится в третий регистр 29 с входа задания кода коммутатора 6 (код В). С этого же входа поступают упраапяюпще сигналы на селектор 10 адреса и на вход второго злемента ИЛИ-НЕ 13, выходной сигнал которого записывает код приоритета в третий регистр 29 и по истечении времени, которое определя- 5 ется элементом 28 задержки, через элем ент ИЛИ 27 в регистр 15.

Сигнал Запрос магистрали с управляющего входа коммутатора 6 -уровнем 1 открывает третий шинный формиро- 0 ватель 18 и разрешает, накопление импульсов в блоке 11 отсчета времени. Параллельный код с выхода регистра 15 через третий шинный формирователь 18 поступает на первые выходы 5 первого шинного формирователя 16 и схемы 23 сравнения. С первого информационного выхода коммутатора 6 i-ro процессора параллельный код (код А) приходит на первый вход второго шинного формирователя 17 и второй вход схемы 23 сравнения i+1-го процессора. В схеме 23 сравнения происходит сравнение кодов А и В. Если код В меньше кода А, т.е. пртюритет В выше приоритета А, то на первом выходе схемы 23 сравнения и соответственно на выходе элемента ИЛИ 26 устанавливается уровень 1, которьй разрешает прохождение кода В на первый 0 формационный выход коммутатора 6. . , В противном случае на первом и втором выходах схемы 23 сравнения устанавливается уровень О и на первый информационный выход коммутатора 6 45 поступает через второй шинный формирователь 17 код А. На вторые входы элемента И-НЕ 24 и элемента И 25 коммутатора 6 i-ro процессора подан .сигнал с второго информационного выхода коммутатора 6 i+1-го процесса, причем на вторые входы элемента И-НЕ 24 и элемента И 25 М-го процессора подан уровень 1. Па первые же входы элемента И-НЕ 24 и злемента И 25 поданы соответственно прямой и инвертированный выходные сигналы схемы 23 сравнения. Сигнал с выхода элемента И 25 поступает на второй информационный выход коммута0

5

50

55

ора ,6 i-го процессора и равен 1, сли с второго информацианного выхоа коммутатора 6 i+lTO процессора оступил сигнал уровнем 1 и код , хранящийся в регистре 15 i-ro роцессора больше кода А, полученного из i-1-го процессора,, т.е. на выоде элемента И 25 формируется уровень 1, если меньший код хранится ю в регистре 15 процессора с меньшим номером, на выходе элемента И-НЕ 24 при этом также формируется уровень

tt 1 П

i

Если В регистре 15 хранится наи- t5 меньший код (т.е. код высшего прио- . ритета), то сигнал уровнем 1 с первого выхода схемы 23 сравнения через элемент ИЛИ 26 и второго информационного входа коммутатора б сформирует 20 на выходе элемента И-НЕ 24 и, соответственно, на первом входе элемента ИЛИ-НЕ 12 уровень О. При отсутствии обмена по операционной магистрали 2 (уровень О на шине о эаня- 25 Тии магистрали и на втором управляющем входе коммут.атора 6) на выходе элемента ИЛИ-НЕ 12 и соответственно выходе-признака коммутатора 6 формируется сигнал Предоставление магист- 30 рали уровнем 1. При этом инвертированный сигнал с выхода элемента

ИЛИ 26 обеспечит уровень О на втором информационном выходе коммутатора 6, а- также на втором информацион- 35 ном входе коммутаторозз 6, входящих в процессоры с меньшим номером.

Накопление кода в блоке 11 отсчета времени происходит по импульсам тактового генератора , поступающим40

на пятый управляющий вход коммутато- ра 6. Если процессор долго находится в состоянии ожидания (т.е. не поступает сигнал Занятие магистрали на четвертый управляющий вход 45 татора 6), то по истечении опред(У1ен- ного времени сигнал уровнем 1 с

выхода перемещения блока 11 отсчета времени приходит на вычитающий вход регистра 15, повьш1ая этим приоритет jQ соответствующего процессора.

Сигналом Представление магистрали через элемент ИЛИ 27 происходат восстановление первоначального кода приоритета процессора.55

При равенстве кодов А и В уровень 1 с второго выхода схемы 23 сравнения через элемент HJM 26 пропустит на первьй информационный выхо рммутатора 6 код В, т.е. сигнал Предоставление магистрали сформируется в процессоре, имеющем больший номер.

При освобождении магистрали сиг- нап с шины 8 занятия магистрали уровнем 1 записывает код с выхода кода приоритета блока 11 отсчета времени в регистр 14. При отсутствии запросов от процессоров сигнал с шины 7 запроса магистрали через элемент НЕ 21 уровнем 1 разрешает прохождение кода с инверсного выхода регистра 14, через четвертый шинный формирователь 19 на первые вхо- ды первого шинного формирователя 16 и схемы 23 сравнения. Далее процедура формирования сигнала Предоставление магистрали аналогична описанной.

Операционный блок, функциональная схема которого показана на фиг.3,работает следующим образом. На первый вход-выход блока и соответственно блока 31 подключения к магистрали подаются шины адреса, данных и управляющие сигналы, необходимые для обмена с внешней памятью 1, Вторые входы-выходы блока 31 подключения к магистрали соединены с первыми входами-выходами блока 30 процессора и являются вторыми информапионны- ми входами-выходами операционного блока 4. Работа блока 30 процессора тактируется импульсами, поступающими, на тактовый вход операционного блока 4 и соответственно третий вход блока 30 процессора из блока 9 синхронизации.

По импульсам с четвертого выхода блока 30 процессора производится переключение триггеров 32 и 33 запроса и занятия магистрали, и накопление кода в -блоке 11 отсчета времени.

При необходимости обмена с внешней памятью 1 на втором выходе блока 30 процессора .уровнем 1 устанавливается сигнал Запрос магистрали и блок .30 переходит в состояние ожидания. Сигнал запроса взводит триггер 33 запроса магистрали, единичный - выход которого подается на третий управляющий выход операционного блока 4 . Нулевой выход триггера 33 устанавливает через второй элемент НЕ 35 уровень 1 на первом управляющем выходе операционного блока 4 и соответственно шине 7 запроса магистрали. После соответствующих логических операций коммутатор 6 выставляет на входе признака соответствующего операционного блока 4 сигнал Предоставление магистрали уровнем 1. Этот сигнал через элемент ИЛИ 36 взводит триггер 32 занятия магистрали,. Единичный выход триггера 32 устанавливает уровень 1 на четвертом управляющем выходе операционного блока 4. Сигнал с нулевого выхода через первый элемент НЕ 34 устанавливают уровень 1 на втором управляющем выходе блока 4 и соответственно на щине 8 занятия магистрали, а уровнем О подает команду на подключе- ние блока 31 к операционной магистрали 2 и выдает сигнал Предоставление магистрали в блок 30 процессора. По этому сигналу блок 30 выходит из состояния ожидания и осу

ществляет операцио обмена с внешней памятью 1, снимая при этом сигнал Запрос магистрали и выставляя на первом входе элемента ИЛИ 36 сигнал Магистраль занята.

После снятия сигнала Запрос магистрали триггер 44 запроса магист - рали сбрасыв.ается очередным тактирую щим импульсом, но состояние триггера 32 занятия магистрали поддерживается прежним, т.е. через элемент ИЛИ 36. Триггер 32 занятия магистрали сбрасывается очередным тактируюищм импуль- сом, устанавливая на шине 8 занятия магистрали уровень О.

Обмен с локальной памятью 5 осуществляется через второй информацион- ный входг-выход операционного блока 4 и не требует специальных сигналов.

Техническая реализация блока 31 подключения к магистрали показана на фиг,4. Первые входы-выходы блока 31 подключены к операционной магистрапи 2 и являются первыми входами-выходами первого шинного формирователя 37, первыми входами второго шинного формирователя 38 и входом третьего шин- ного формирователя 39. Вторые входы выходы блока 31 подключения к маги- страли соединены с первыми входами- выходами блока 30 процессора и являются вторыми входами-выходами перво- го шинного формирователя 37,входом второго шинного формирователя 38 и первым входом шинного формирователя 39.

5

0 5

О

45 0

Управление шинными формирователями 37 - 39 проиоходит следующим образом.

Включение и отключение щинных формирователей 37 - 39 осуществляет- ся сигналом Предоставление магистрали, поступающим на третий вход блока 31 подключения к магистрапи.

0 Уровень О при этом устанавливается на третьем и втором входах соответственно первого и второго шинных формирователей 37, 38 и через элемент 40 задержки на втором входе третьего

5 шинного формирователя 39. На третьих входах второго и третьего шинных формирователей 38, 39 установлены соответственно уровень . Такое подключенпе позволяет пропускать че0 рез второй шинньп формирователь входные управляющие сигналы, а через третий шинный формироват ель 39 выходные сигналы управления при обмене с внешней памятью 1.

Первый шиннный формирователь 37 управляется сигналом к Ввод В,поступающим на его четвертый вход. При пассивном сигнале вторые входы первого шинного формирователя 37 подключены к

первым его выходам, что позволяет осуществлять цикл Вывод.При цикле ВЕОД уровень 1 подключает первые входы первого шинного форми- роватёля 37 к его вторым входам.

Блок 30 процессора реализован на микропроцессоре К 1801 ВМ2, сигнал SP Запрос окна .которого является сигналом Запрос магистрали, а на входной сигнал SP2 Предоставление окна подан сигнал Предоставление магистрали (фиг.5), На первый вход- выход микропроцессора 41 подаются шины адреса, данных и управляющие сигналы, необходимые для обмена с памятью. Тактирование работы микропроцессора 41 осуществляется импульсами входного Сигнала CLCI с третьего входа блока 30 процессора,Формирователь 42 формирует синхронизирующие импульсы сигнала CLC по переднему и заднему фррнту для повьш1ения быстродействия процессора. Сигнал Магистраль занята организуется по сигналу SP2 Предоставление окна ко- торый взводит через элемент НЕ 43 триггер 45, по тактовому импульсу сигнала CLC. После снятия си гнала Предоставление магистрали триггер.

45 сбрасывается также очередным иг.(г пульсом сигнала, .

Блок 11 отсчета времени работает следующим обр аэом (фиг.б). При выстав лении соответствующим процессорам сигнала Запрос ма.гистрали уровень 1 с первого входа управления блока 11-отсчета времени через первьй эле- ; мент ИЛИ 46 поступает на первый вход

первого счетчика 56, сбрасывая его I содержимое в О, Одновременно через : первый элемент НЕ 48. взводится первый ; триггер 54, прямой вход которого ус- ; танавливает на втором входе первого ; элемента И 51 уровень 1, разрешая

накопление в первом счетчике 56 кода г пропорционального времени с момента I выставления сигнала запроса. Код на- ; ращивается импульсами сигнала от бло ; ка 30 процессора, поступающим через : элемент 58 задержки,

: При предоставлении процессору опе ; рационной магистрали 2 сигнал уров- : нем 1 с второго входа формирования

блока 11 отсч.ета времени через вто- : рой элемент ИЛИ 47 поступает на пер- : вый вход второго счетчика 57,сбрасы- : бая его содержимое в О. Одновремен но через второй элемент НЕ. 49 взводится второй триггер. 55 и сбрасывается первый триггер 54.

Таким образом, уровень 1 на втором входе второго элемента И 52 разрешает накопление в вторрм счетчике 57 кода, пропорционального времени

с момента последнего предоставления процессору операдио нной магистрали,

Уровень О на втором входе первого элемента И 51 запира ет его до поступления очередного сигнала запроса от процессора.

Некоторые процессоры системы могут находиться в состоянии так называемого динамического останова,при котором процессор не выполняет ника- . ких действий и не обращается к операционной магистрали неопределенно долго до поступления сигнала прерывания. Таким гфоцессорам нецелесообраз но передавать магистраль при отсутствии от них сигнаиа Запрос магистрали. Поэтому при достижении содерзки- мым счетчика 57 значения N, соответствующего времени выполнения наибо- лее длинной операции (например .деле- кие), на втором выходе этого счетчика формируется сигнал, сбрасывающей второй триггер 55 и через второй эле

0

5

мент ИЛИ 47 .содержимое второго счетчика 57, Сигнал уровнем О с выхода второго триггера 55 запирает второй элемент И 52 и препятствует накоплению во втором счетчике 57 кода времени до очередного захвата процессором операционной магистрали.

Таким образом, система позволяет гибко менять приоритеты процессоров в соответствии с приоритетами выполняемых ими задач, а также имеет возможность автоматического повышения приоритета процессоров, длительное время ожидавших

предоставление ,

магим

страли, что не позволяет оттеснять . высоко приоритетными процессорами низкоприоритетных.

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

Многопроцессорная вычислительная система, содержащая внешнюю, память, М процессоров, каждый из процессоров 5 содержит операционный блок и локальную память, причем первые информационные входы (выходы операционного блока являются первыми информационными входами) выходами процессора и соединены через операционную магистраль с информационными входами-выходами внешней памяти, вторые информационные входы (выходы операционного блока соединены с информационными входами) выходами локальной памяти, отличающаяся тем, что, с целью повьш ения производительности за счет изменения приоритетов процессоров в соответствии с приоритетами задач и их увеличения в случае длительного

5

0

ожидания, в нее введены шина запроса магистрали, шина занятия магистрали, блок синхронизации и в каждый процессор введен коммутатор, который содержит селектор адреса, блок отсчета времени, первый и второй элементы ИЛИ-НЕ, три регистра, четыре шинньпс формирователя, три элемента НЕ,схему сравнения, элемент И-НЕ, элемент И, два элемента ИЖ, элемент задержки, причем тактовый вход операционного блока каждого процессора соединен, с выходом блока синхронизации, вход пуска системы соединен с входом запуска операционного блока каждого процессора, первый информационный выход коммутатора i-ro процессора соединен с первым информационным входом коммутатора (1+1)-г о процессора (i

1, М-), первый информационный вход коммутатора первого процессора соединен с входом задания максимального кода системы, второй информационный вход коммутатора М-го процессора соединен с входом уровня логической единицы системы, второй информационный выход коммутатора К-го процессора соединен с вт-орым информационным входом коммутатора (К-)-го процессора (К 2,М), первые управляющие выходы всех операционных блоков процессоров объединены и соеди- нены через шину запроса магистрали с первыми управляющими входами коммутаторов всех процессоров, вторые управляющие выходы операционных блоков всех процессоров объединены и соединены через шину занятия магистрали с вторыми управляющими входами коммутаторов всех процессоров, выход признака коммутатора каждого процессора соединен с входом признака соответствующего операционного блока процессора, третий, четвертый и пя- тьш управляющий выходы, операционного блока в каждом процессоре соединены соотБСТственно с третьим,чет- вертым и пятым управляющими входами коммутатора процессора, вхйд задания кода KOMNryTHTOpa соединен с вторым информационным входом/выходом операционного блока, в коммутаторе каждого процессора первый информационный выход соединен с выходами первого и второго шинных формирователей, информационный вход первого тинного формирователя соединен с вы

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

5

0

5

0

5

0

0

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

P

50

т

31

k

:

Z)

Изобретение относится к вычислительной технике и может быть использовано при построении различных многопроцессорных устройств с общей магистралью. Цель изобретения - повышение производительности системы на отдельных задачах. Многопроцессорная вычислительная система содержит внешнюю память 1, операционную магистраль 2, M процессоров 3, каждый из которых включает операционный блок 4, внутреннюю оперативную память 5, и коммутатор 6, шину запроса 7 магистрали, шину занятия 8 магистрали, блок синхронизации 9. Введение в каждый процессор коммутатора соответствующей структуры позволяет гибко менять приоритеты процессоров в соответствии с приоритетами выполняемых ими задач и автоматически повышать приоритет процессоров, длительное время ожидавших предоставления магистрали. 6 ил.

Магистраль занята

0

Предостаёление .стралц

2

to

I Т-Г г г

. л

О

Занйтив /магистрали 54

J5i

Запрос /магистрали

О

-if

Фиг. 3

Й.

Запрос магистрали

iJTf

49

Магистраль занята

-I г Л1 1

CLC0

11

3

Фиг.б