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

/16 0 06 ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЭОБРЕТЕНИЯМ И ОТНРЬГГИЯМПРИ ГКНТ СССР АНИЕ ИЗОБРЕТЕН ВТОРСНОМУ СВИДЕТЕЛЬСТ(56) Патент США У 4096572кл. С Об Р 15/16, 1984Патент США У 3959775,б Г 15/16, 1983. ин ГОПРОЦЕССОРЕМА 1 ЧИСЛИТЕЛ к вычис быть исразличных в с общей ния - говшобретение относитс ой технике и может ано при построении оцессорных устроис алью. Цель изобрет ко ноас Фие, у кл. С О1(57) Илительпользомногопмагист шение производительности систеий наотдельных задачах, Многопроцессорнаявычислительная система содержит внешнюю память 1, операционную магистраль 2,М процессоров 3, каждый изкоторых включает операционный блок 4,внутреннюю оперативную память 5 икоммутаторв 6, шину запроса 7 магистрали, блок синхронизации 9. Введениев каждый процессор коммутатора соответствующей структуры позволяет гибко менять приоритеты процессоров всоответствии с приоритетами выполняемых ими задач й автоматически повы-шать приоритет процессоров,длительное время ожидавших предоставлениямагистрали, б ил.1589287 Составитель А,ИвановТехред А.Кравчук. едактор Л.Бандура Корректор С.йевкун кав 2542Тираж 5 б 7 ПодписноеНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СС113035, Москва, Ж, Раушская наб., д. 4/5 Производственно-издательский комбинат "Патент.", г, Ужгород, ул. Гагарина ЮфЧС РЮ 8 Ю/Щ 7Изобретение относится к вычисли".тельной технике и может быть использовано при построении различных многопроцессорных устройств с общей магистралью.Цель изобретения - повышение производительности за счет измененияприоритетов процессоров в соответствии с приоритетами задач и их увеличения в случае длительного ожидания вНа фиг.1 приведена функциональная схема многопроцессорной вычисли"тельной систеьи; на фиг, 2 - функциональная схема коммутатора: на фиг.З -вариант технической реализацж операционного блока; на фиг. 4 - функциональная схема блока. подключенияк операционной магистрали; на фиг.5 -вариант блока процессора.; на.фиг.б -функциональная схема блока отсчетавремени,.Многопроцессорная вычислительнаясистема содержит (фиг.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, элемент 1 НИ 36,Блок 31 подключения к магистралисодержит первый, второй и третий шинные формирователи 37 - 39, элемент40 задержки.Блок ЗО процессора содержит микропроцессор 41, формирователь 42,первыйи второй элементы НЕ 43, 44, триггер45.Блок 11 отсчета времени содержитпервый и второй элементы ИЛИ 46, 47,первый, второй и третий элементыНЕ 48 - 50, первый, второй и третийэлементы И 51-53, первый и второйтриггеры 54,55, первый и второй счетчики 56,57, элемент 58 задержки.Многопроцессорная вычислительнаясистема. работает следующим образом,Обработка информации в каждомпроцессоре 3 производится операционным блоком 4, работа которого синхронизируется тактовыми импульсамиблока 9, Обмен данными между процессором 3 и внешней памятью 1 осуществляется через операционную магистраль.2, по шинам которой в циклеобмена передаются адрес, данные иуправляющие сигналы,Рассмотрим взаимодействие операционного блока 4 с внешней памятью1 (фиг.1). По сигналу "Пуск",поступающему на вход запуска каждогооперационного блока 4, монитор,помещенный в локальную память каждого25 процессора 3, записывает в соответствующий ему коммутатор 6 код приоритета первой выполняемой задачи,При необходимости обращения к внешней памяти 1 и отсутствии сигнала3 "Предоставление магистрали" на входе признака операционного блока 4формируется на первом управляющемвыходе этого блока сигнал "Запросмагистрали" и блок 4 переходит в сос 35 тояние "ожидания",По сигналу "Запрос магистрали" вкоммутаторе 6 происходит определениепроцессора 3, имеющего наивысшийприоритет. В "соревновании" участву 40 ют только процессоры 3, выставившиесигнал "Запрос магистрали", Причем,если процессор долго находится всостоянии "ожидания", то блок 11отсчета времени автоматически повышаает его приоритет.Коммутатор 6, соответствующий наиболее приоритетному процессору, навыходе признака устанавливает сигнал11"Представление магистрали , поступивший на одноименный вход операционного блока 4, по которому он выходитиз состояния "ожидания" и осуществляет операцию обмена с внешней памятью1. Сигнал "Запрос магистрали" при55этом снимается и выставляется на втором управляющем выходе блока 4 сигнал Занятие магистрали".В случае автоматического,повышения процессором своего приоритета,5 158сигналом "Предоставление магистрали"восстанавливается первоначальный кодпр корит ет а.После завершения обмена с внешнейпамятью 1 операционный блок 4 снимает сигнал "Занятие магистрали" и приотсутствии запросов на обмен с внешней памятью 1 операционная магистраль 2 подключается к процессору 3,наибольшее время не обращавшемусяк внешней памяти,Передача магистрали происходитследующим образом. Коммутатор 6, вблоке 11 отсчета времени которогосодержится наибольший код,Формируетна выходе признака сигнал "Предоставление магистрали" уровнем логической"1", по которому операционная магистраль 2 подключается к соответствующему операционному блоку 4. При необходимости обмена с внешней памятью1 данный процессор 3 начинает обменбез сигнала запроса магистрали и перехода в режим ожидания, При появлении до начала обмена запросов от других процессоров, сигнал с шины 7 запросов магистрали на первом управляющем входе коммутатора 6 сбросит сигнал "Предоставление магистрали" иосвободит операционную магистраль.Рассмотрим разрешение конФликтовпри одновременном обращении к внешней памяти 1 нескольких процессоров.Если процессор 3 выставляет сигнал"Запрос магистрали" во время операции обмена с внешней памятью, сигнал"Предоставление магистрали не пройдет, так как он блокируется сигналомуровня "1" на втором управляющемвходе коммутатора 6 с шины 8 занятиямагистрали. При свободной операционной магистрали 2 и наличии нескольких запросов. магистраль будет предоставлена более приоритетному. процессору, который блокирует остальные, выставляя на втором. информационном выходе коммутатора 6 уровень "О". При равенстве приоритетов нескольких процессоров магистраль будет подключена к процессору с большим номером, который так же блокирует запросы от процессоров, имеющих номер меньше.Кроме того, часть процессоров системы может быть остановлена и выполнять команды "динамического останова", при выполнении которых 9287 бпроцессор может неопределенно долгоне обращаться к магистрали.Коммутатор (Фиг.2) работает следующим образом. Двоичный код приори"тета выполняемой задачи заносится втретий регистр 29 с входа заданиякода коммутатора 6 (код В), С этогоже входа поступают управляющие сигналы на селектор 10 адреса и на входвторого .элемента ИЛИ-НЕ 13, выходной сигнал которого записывает кодприоритета в третий регистр 29 и поистечении времени, которое определяется элементом 28 задержки, черезэлемент ИЛИ 27 в регистр 15.Сигнал "Запрос магистрали" с управляющего входа коммутатора 6 уровнем"1" открывает третий шинный Формиро ватель 18 и разрешает накоплениеимпульсов в блоке11 .отсчета времени, Параллельный код с выхода регистра 15 через третий шинный Формирователь 18 поступает на первые входы 25 первого шинного Формирователя 16 исхемы 23 сравнения, С первого инФормационного выхода коммутатора 6 х-гопроцессора параллельный код (код А)приходит на первый вход второго шин ного Формирователя 17 и второй входсхемы 23 сравнения +1-го процессора. В схеме 23 сравнения происходитсравнение кодов А и В. Если код Вменьше кода А, те. приоритет В вышеприоритета А, то на первом выходесхемы 23 сравнения и соответственнона выходе элемента ИЛИ 26 устанавливается уровень "1", который разрешает прохождение кода В на первый ин 4 б Формационный выход коммутатора 6.В противном случае на первом и втором выходах схемы 23 сравнения устанавливается уровень "О и на первыйинФормационный выход коммутатора 6поступает через второй шинный Формирователь 17 код А. На вторые входыэлемента И-НЕ 24 и элемента И 25 коммутатора 6 -го процессора подан, сигнал с второго инФормационного выл хода ког 1 утатора 6 +1-го процесса,причем на вторые входы элементаИ-НЕ 24 и элемента И 25 М-го процессора подан уровень "1", На первыеже входы элемента И-НЕ 24 и элемента И 25 поданы соответственно прямой и инвертированный выходные сигналы схемы 23 сравнения. Сигнал свыхода элемента И 25 поступает навторой инФормационный выход коммута1589287 татора 6 код В, т.е. сигнал "Предоставление магистрали" сформируется в процессоре, имеющем больший номер.При освобождении магистрали сигнал с шины 8 занятия магистрали уровнем "1" записывает код с выхода кода приоритета блока 11 отсчета времени в регистр 14. При отсутствии запросов от процессоров сигнал с шины 7 запроса магистрали через элемент НЕ 21 уровнем "1" разрешает прохождение кода с инверсного выхода регистра 14, через четвертый шинный формирователь 19 на первые входы первого шинного формирователя 16 и схемы 23 сравнения, Далее процедура формирования сигнала "Предоставление магистрали" аналогична описанной.Операционный блок, функциональная схема которого показана на фиг,З,ра - ботает следующим образом. На первый вход-выход блока и соответственно подаются шины адреса, данных и управляющие сигналы, необходимые для обмена с внешней памятью 1. Вторые входы-выходы блока 31 подключения к магистрали соединены с первыми входами-выходами блока 30 процессора и являются вторыми информапионными входами-выходами операционного блока 4. Работа блока 30 процессора тактируется импульсами, поступающими на тактовый вход операционного блока 4 и соответственно третий вход блока 30 процессора из блока 9 синхронизации.По импульсам с четвертого выхода блока 30 процессора производится переключение триггеров 32 и 33 запроса и занятия магистрали, и накопление кода в блоке 11 отсчета времени.При необходимости обмена с внешней памятью 1 на втором выходе блока 30 процессора .уровнем "1" устанавливается сигнал "Запрос магистрали"11 и блок .30 переходит в состояние ожидания", Сигнал запроса взводит триггер 33 запроса магистрали, единичный выход которого подается на третий управляющий выход операционного блока 4, Нулевой выход триггера 33 устанавливает через второй элемент НЕ 35 уровень "1" на первом управляющем выходе операционного блока 4 и соответственно вине 7 запроса магистратора 6 ь-го процессора и равен "1",если с второго информационного выхода коммутатора 6 +1 го процессора.поступил сигнал уровнем "1" и кодВ, хранящийся в регистре 15 1-гопроцессора больше кода А, полученного из -1"го процессора т.е. на выходе элемента И 25 формируется уровень "1", если меньший код хранится 10в регистре 15 процессора с меньшимномером, на выходе элемента И-НЕ 24при этом также формируется уровень11 1 11Если в регистре 1 5 хранится н аименьший код ( т . е . код высшего приорит ет а) , то сигнал уровнем " 1 " с и ерво го выхода схемы 2 3 сравнения черезэлемент ИЛИ 2 6 и второго и нформационного входа коммутатора 6 сфор мируе т 2 Он а выходе элемента И-НЕ 2 4 и , соо тв ет ст венно , на первом входе элемента ИЛИ-НЕ 12 уровень "0"При отсутствии обмена по операционной магистрали 2 (уровень "0" на шине о заня блока 31 подключения к магистралитии магистрали и на втором управляющем входе коммутатора б) на выходеэлемента ИЛИ-НЕ 12 и соответственновыходе. признака коммутатора 6 формируется сигнал "Предоставление магистрали" уровнем "1" При этом инвертированный сигнал с выхода элементаИЛИ 26 обеспечит уровень "0" на втором информационном выходе коммутатора 6, а также на втором информацион"ном входе коммутаторов 6, входящих.в процессоры с меньшимномером.Накопление кода в блоке 11 отсчета времени происходит по импульсамтактового генератора, поступающим 40на пятый управляющий вход коммутато-.ра 6. Если процессор долго находитсяв состоянии "ожидания" (т.е, не поступает сигнал "Занятие магистрали"на четвертый управляющий вход коммутатора 6), то по истечении определен 11 11ного времени сигнал уровнем 1 свыхода перемещения блока 1 1 отсчетавремени пр нход ит н а вы чит ающий входрегистра 1 5 , повьппая з тим приоритетсоот в ет ст вующего процессора ,Сигналом "Представление магистрали" через элемент ИЛИ 27 происходитвосстановление первоначального кодаприоритета процессора. 55При равенстве кодов А и В уровень"1" с второго выхода схемы 23 сравнения через элемент ИЛИ 26 пропуститна первьп ииформацвзнный выход криму 1589287 10ли. После соответствующих логических операций коммутатор б выставляет на . входе признака соответствующего операционного блока 4 сигнал "Предоставление магистрали" уровнем "1". Этот сигнал через элемент ИЛИ 36 взводит триггер 32 занятия магистрали,. Единичный выход триггера 32 устанавли" вает уровень "1" на четвертом управ ляющем выходе операционного блока 4. Сигнал с нулевого выхода через первый элемент НЕ 34 устанавливаютуровень "1" на втором управляющем выходе блока 4 и соответственно на 15 шине 8 занятия магистрали, а уровнем "0 подает команду на подключение блока 31 к операционной магистрали 2 и выдает сигнал "Предоставление магистрали в блок 30 процес сора. По этому сигналу блок 30 выходит из состояния "ожидания" и осуществляет операцио обмена с внешней памятью 1, снимая при этом сигнал "Запрос магистрали" и выставляя на первом входе элемента ИЛИ 36 сигнал Ма гистр аль з анят а.После снятия сигнала Запрос магистрали" триггер 44 запроса магист=. рали сбрасывается очередным тактирую щим импульсом, но состояние триггера 32 занятия магистрали поддерживается прежним, т.е, через элемент ИЛИ 36.Триггер 32 занятия магистрали сбрасывается очередным тактирующим импульсом, устанавливая на шине 8 занятия магистрали уровень "0",Ю Обмен с локальной памятью 5 осуществляется через второй информацион ный вход-. выход операционного блока 4 и не требует специальных сигналов.Техническая реализация блока 31 подключения к магистрали показана на фиг.4. Первые входы-выходы блока 31 45 подключены к операционной магистрали 2 и являются первыми входами-выходами первого шинного. формирователя 37, первыми входами второго шинного фор" мирователя 38 и входом третьего шинного формирователя 39, Вторые входы- выходы блока 31 подключения к магистрали соединены с первыми входами- выходами блока 30 процессора и являются вторыми входами-выходами перво, 55го шинного формирователя 37,входом второго шинного формирователя 38 и первым входом шинного формирователя39. Управление шинными формирователями 37 - 39 проиСходит следующим образомм.Включение и отключение шинных формирователей 37 - 39 осуществляется сигналом "Предоставление магистрали", поступающим на третий вход блока 31 подключения к магистрали. Уровень "0" при этом устанавливается на третьем и втщом входах соответственно первого и второго шинных формирователей 37, 38 и через элемент 40 задержки на втором входе третьего шинного формирователя 39. На третьих входах второго и третьего шинных формирователей 38, 39 установлены соответственно уровень "0" и "1". Такое подключение позволяет пропускать через второй шинный формирователь входные управляющие сигналы, а через третий шинный формирователь 39 выходные сигналы управления при обмене с внешней памятью 1Первый шиннный формирователь 37И управляется сигналом "к Ввод В,поступающим на его четвертый вход. При пассивном сигнале вторые входы первого шинного формирователя 37 подключены к первым его выходам, что позволяет осуществлять цикл Вывод",При цикле "Ввод" уровень "1" подключает первые входы первого шинного форми-рователя 37 к его вторым входам. Глок 30 процессора реализован на микропроцессоре К 1801 ВМ 2, сигнал БР 1 "Запрос окна" которогоявляется сигналом "Запрос магистрали", а на входной сигнал ЯР 2 "Предоставление окна" подан сигнал "Предоставление магистрали" (фиг,5). На первый вход- выход микропроцессора 41 подаются шины адреса, данных и управляющие сигналы, необходимые для обмена с памятью, Тактирование работы микропроцессора 41 осуществляется импульсами входного сигнала СЬС 1 с третьего входа блока 30 процессора.формирователь 42 формирует синхронизирующие импульсы сигнала СЬС по переднему и заднему фронту для повышения быстродействия процессора, Сигнал "Магистраль занята" организуется по сигналу ЯР 2 "Предоставление окна",ко-. торый взводит через элемент НЕ 43 триггер 45, по тактовому импульсу сигнала СЬС. После снятия сигнала1145 сбрасывается также очередным импульсом сигнала,Блок 11 отсчета времени .работаетследчощим образом (Фиг,6), При выставленин соответствующим процессорамсигнала "Запрос магистрали" уровень"1" с первого входа управления блока11 отсчета времени через первый элемент ИЛИ 46 поступает на первый вход 10первого счетчика 56, сбрасывая егосодержимое в "О". Одновременно черезпервый элемент НЕ 48. взводится первыйтриггер 54, прямой вход которого устанавливает на втором входе первого 15элемента И 51 уровень "1", разрешаянакопление в первом счетчике 56 кода,пропорционального времени с моментавыставления сигнала запроса. Код наращивается импульсами сигнала от блока 30 процессора, поступающим черезэлемент 58 задержки.При предоставлении процессору операционной магистрали 2 сигнал уровнем "1" с второго входа Формированияблока 11 отсчета времени через второй элемент ИЛИ 47 поступает на первый вход второго счетчика 57,сбрасывая его содержимое в "О". Одновременно через второй элемент НЕ 49 взводится второй триггер. 55 и сбрасывается первый триггер 54.Таким образом, уровень "1" на втором входе второго элемента И 52 разрешает накопление в втором счетчике57 кода, пропорционального временис момента последнего предоставленияпроцессору операционной магистрали,Уровень "О" на втором входе первогоэлемента И 51 запирает его до поступления очередного сигнала запросаот процессора.Некоторые процессоры системы могут находиться в состоянии так называемого динамического останова ,при 45котором процессор не выполняет никаких действий и не обращается к операционной магистрали неопределеннодолго до поступления сигнала прерывания. Таким процессорам нецелесообразно передавать магистраль при отсутствии от них сигнала "Запрос магистрали". Поэтому при достижении содержимым счетчика 57 значения Н, соответствующего времени выполнения наиболее длинной операции (например деление), на втором выходе этого счетчика Формируется сигнал, сбрасывающийвторой триггер 55 и через второй элемент ИЛИ 47 .содержимое второго счетчика 57. Сигнал уровнем "О" с выхода второго триггера 55 запирает второй элемент И 52 и препятствует накоплению во втором счетчике 57 кода времени до очередного захвата процессором операционной магистрали.Таким бразом, система позволяет. гибко менять приоритеты процессоров в соответствии с приоритетами выполняемых ими задач, а также имеет возможность автоматического повышенияприоритета процессоров, длительное время ожидавших предоставление магистрали, что не позволяет "оттеснять" высоко приоритетными процессорами низкоприоритетных.Формула изобретенияМногопроцессорная вычислительная система, содержащая внешнюю память, М процессоров, каждый из процессоров содержит операционный блок и локальную память, причем первые инФормационные входы (выходы операционного блока являются первыми инФормационными входами) выходами процессора и соединены через операционную магистраль с инФормационными входами-выходами внешней памяти, вторые инФормационные входы (выходы операционного блока соединены с инФормационными входами) выходами локальной памяти, о т л ич а ю щ а я с я тем, что, с целью повышения производительности за счет изменения приоритетов процессоров в соответствии с приоритетами задач и их увеличения в случае длительного ожидания, в нее введены шина запроса магистрали, шина занятия магистрали, блок синхронизации и в каждый процессор введен коммутатор, который содержит селектор адреса, блок отсчета времени, первый и второй элементы ИЛИ-НЕ, три регистра, четыре шинных Формирователя, три элемента НЕ,схему сравнения, элемент И-НЕ, элемент И, два элемента ИЛИ, элемент задержки, причем тактовый вход операционного блока каждого процессора соединен, с выходом блока синхронизации, вход пуска системы соединен с входом запуска операционного блока каждого процессора, первый инФормационный выход коммутатора -го процессора соединен с первым инФормационным входом коммутатора (1.+1)-го процессора (1 О 15 20 25 30 35 40 45 50 1, М), первый информационный вход коммутатора первого процессора соединен с входом задания максимального кода системы, второй информа" ционный вход коммутатора М-го процессора соединен с входом уровня логической единицы системы, второй информационный выход коммутатора К-го процессора соединен с вторым информационным вхоцом коммутатора (К)-го процессора (К = 2,М), первые управляющие выходы всех операционных блоков процессоров объединены и соединены через шину запроса магистрали с первыми управляющими входами коммутаторов всех процессоров, вторые управляющие выходы операционных блоков всех процессоров объединены и соединены через шину занятия магистрали с вторыми управляющими входами коммутаторов всех процессоров, выход признака коммутатора каждого процессора соединен с входом признака соответствующего операционного блока процессора, третий, четвертый и пятый управляющий выходы операционного блока в каждом процессоре соединены соответственно с третьим,чет, вертым и пятым управляющими входамикоммутатора процессора, вход задания кода коммутатора соединен с вторым информационным входом/выходом операционного блока, в коммутаторе каждого процессора первый информационный выход соединен с выходами первого и второго шинных формирователей, информационный вход первого шинного формирователя соединен с выходами третьего и четвертого шинных формирователей и первым входом схемы сравнения, второй вход которой соединен с информационным входом второго шинного формирователя и является первым информационным входом коммутатора, выходы "Меньше" и "Равно" схемы сравнения соединены с первым и вторым входами соответственно первого элемента ИЛИ, выход .которого соединен с входом управления первого шинного формирователя, первым входом элемента И-НЕ и через первый элемент НЕ - с.входом управления второго шинного формирователя и первым входомэлемента И, второй вход которогосоединен с вторым входом элементаИ"НЕ и является вторым информационным входом коммутатора, выход элемента И является вторым информационнымвыходом коммутатора, выход элементаИ-НЕ соединен с первым входом перво-го элемента ИЛИ-НЕ, выход которогосоединен с первым входом второго элемента ИЛИ и является выходом признака коммутатора, первый управляющийвход которого соединен через второйэлемент НЕ с входом управления четвертого шинного формирователя,информационный вход которого соединен синверсным выходом данных первого регистра, вход записи которого черезтретий элемент НЕ соединен с вторымвходом первого элемента ИЛИ-НЕ и является вторым управляющим входом коммутатора, третий управляющий входкоторого соединен с первым входомуправления блока отсчета времени ивходом управления третьего шинногоформирователя, информационный входкоторого соединен с выходом данныхвторого регистра, вход вычитания которого соединен с выходом переполнения блока отсчета времени, выход кода приоритета которого соединен с информационным входом первого регистра, второй и третий входы управления блока отсчета времени являютсячетвертым и пятым управляющими входами коммутатора соответственно, входзадания кода которого соединен свходом селектора адреса и инфармационным входом третьего регистра,один из разрядов информационного входа которого соединен с первым входомвторого элемента ИЛИ-НЕ, второй входкоторого соединен с выходом селектора адреса, выход второго элементаИЛИ-НЕ соединен с входом записитретьего регистра и через элемент за"держки с вторым входом второго элемента ИЛИ, выход которого соединен свходом записи второго регистра,информационный вход которого соединенс выходом третьего регистра.