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

(61) Дополните (22) Заявлено 1 с присоедичени ое к авт. св М, Кл.аО 06 У 3.3 2.74.(21) 199590заявки-4 6 Г 15/1 Гасударственныи комитет Совета йинистрав СССР аа делам изобретений и аткрытий(71) Заявител Ордена Ленина инс тут проблем управ и МНОГОПРОБЕССОРНО НИЯ ПАМЯТ Й СИСТЕМЕ ль -м к вычиспримененх вычи носит я к одному В мультипро тчислительнойразными пр а данных р и тому же блоку граммной однопро системе режим и ограммами одног еализуется, но в р и. Пусть имеется с анньтх.ессорнои вь спользова о и того кел жиме ра некотор ния време д амяти, цессов 10 В многопроцесистемах особый льныхтяет во ссорных вычислт интерес предст о пользования о. данны, храняшпмися в ным пользованием акой режим работ сло процессов, р данным оллекти теми ж Подми понимается тдва и большее ч ализуе 4) УСТРОЙСТВО ДЛЯ УПРАВЛЕ ВЫЧИСЛИТЕЛЬНОИзобретение от ся литеной технике и может быть о присоздании многопроцессорнь слительныхсистем,Известны устройства для управления памятью, содержашие блок хранения информации, блок поиска информашти, включающийрегистры адресов, шифраторы, дешифраторы,логические схемы выбора, блок сравнения,Известные устройства позволяют обрабатывать запросы, поступаюшие в виде физи -ческих адресов блока хранения информации,что не дает возможности осушествлять вь. -борку требуемой информации из любой части памяти многопроцессорной системы любой программой, реализуемой в данный момент,А. Ведешенков, А. Ф. Волков нкин, А, В, Лебедев,сков, И. А. Фараджев данный момент в системе, обраша вычислительная система с одним процром и с иерархической структурой ив которой реализуется несколько проНезависимо от способа органттзашти памятисистемы (страничной пчи сегментной) по -лагаем, что всякое обращение к памяти происходит по некоторому идентификатору, позволяюшему определить адрес элемента данных. Тогда при многоуровневой системе памяти при всяком обрашении к памяти реа -лизуемого в данный момент в системе процесса по идентификатору элемента данных(элемент сегмента, массива, слово страницы) блок, содержаший требуемый элемент,найденный на одном из более низких уровней памяти, будет передан в самьш верх -ний уровень для оперативной работы про -цесса с элементами этого блока. При сме.;с процесса, работающего с теми же элементами данных, ч.о и предыдущий процесс, и обращающегося к памяти со своим идентификатором, по за теми же элементами (огггг находятся в верхнем уровне памяти), устанавливает ся соответствие между идентификаторами и второй процесс тем самым получает доступ к тем же элементам данных, что и предыдущий процесс. При этом каждый из процессов может работать в лгсбом разрешенном ему ре- О ;ни;е (чтенгге, запись).Для системы с несколькими процессора - мгг управление коллективным пользованием данными усложняется. Если в системе име - ется несколько процессоров, но с одной об шей оперативной памятью, то в каждый момент времени такую систему можно рассматривать как однопроцессорную с точки зре - ния обращения к памяти, так как за каждый цикл памяти обслуживается лишь одно обра шение. Поэтому, если в оперативной памяти находятся данные, которыми пользуются два и более процессов в момент их реализации, то при одновременном обращении к памяти за одним и тем же элементом данных нескольких процессоров только один процессор, выделенный в результате разрешения конфликтной ситуации, получит право на использова - ние этого элемента, Затем этот элемент может быть использован другим выделенным 30 процессором, третьим и т, д. При этом возникает еше и дополнительная задача синхронизации процессов, но в смысле коллектив - ного пользования такая система обеспечи - вает этот режим. 35Решением вопроса повышения эффектив - чости работы многопроцессорной системы было бы выделение каждому процессу некоторого объема оперативной памяти для исключения возможности возникновения конфликт ных ситуаций по обращению за элементами данных, но тогда исключалась бы возмож - ность коллективного пользования одними итеми же данными.Рассмотрим, например, двухпроцессорную 5 систему, где каждому процессу выделен свой блок оперативной памяти и в данный момент реализуется два процесса, работающие с одними и теми же элементами данных в режимах чтения и записи соответственно, Тогда при обращении к одному и тому же элементу двух процессоров в оперативную память каждого процесса будет передан один и тот же блок данных и каждый процесс будет независимо от другого процесса работать с этим 55 блоком данных, При этом каждый из процессов может в результате режима записи различным образом изменять элементы этого блока, В результате в двух блоках оперативной памяти будут получены два разных по 60 содержанию блока данных, но имеющих одинггдентггфикатор, В памяти следугсшего болеенизкого уровня при этом хранится неизмен -ная копия этого блока, Такое состояние;бдо:-.а данных, имеющего один идентификатор,недопустимо, но оно не возникает в многоггроцессорной системе с обшей оперативнойпамятью,Белью изобретения является повышениеэффективности. работы устройства для управления памятью и, следовательно, быстродей-ствия системы в целом.Ддя достижения поставленной цели в предлагаемое устройство введены блок классификации запросов, блок выдачи форматныхзапросов, блок сопряжения с каналом связи,блок замещения страницы, блок направленияпередачи информации и блок упаковки словас соответствуюшими цепями связи междувведенными и известными блоками. Это позволяет обеспечить необходимые условия режиму коллективного пользования двум и более процессам в многопроцессорной вычислительной системе и иерархической структуройпамяти, в которой каждому процессу выделен свой блок памяти на самом верхнем ееуровне, а каждый процессор имеет непосредственную связь только со своим блоком памяти. Кроме того, все блоки памяти этогоуровня связаны между собой общим каналомсвязи. Всякое обращение любого процесса к памяти происходит по идентификатору, в которомопределен номер массива, номер первогобайта требуемого элемента и длина элемента байтов, В идентификаторе имеется так -же признак, является ли массив с даннымномером принадлежащим одному процессуили многим процессам. Таким образом, устройство позволяет обрабатывать запросы, поступающие не в виде физических адресов блока хранения ин - формации, а в виде идентификаторов массива и номера элемента в нем, что обеспечивает выборку этого элемента массива из любой части памяти многопроцессорной системы и любой программой, реализуемой в данный момент. Процесс перемещения инфор мации не связан с определением физических адресов месторасположения замещаемой или передаваемой информации, что позволяет аппаратно реализовать процесс динамического выделения требуемого объема памяти дляобрабатываемой информацгги.На фиг. 1 изображена блок-схема предлагаемого устройства; на фиг, 2 - многопроцессорная вычислительная система,Устройство содержит блок 1 классификации запросов, блок 2 выдачи форматных запросов, блок 3 сопряжения с каналом, блок4 замещения страницы, блок 5 поиска ин -формации, блок 6 формирования признакасовпадения, блок 7 хранения информации,блок 8 упаковки слова, блок 9 направленияпередачи, входы 10, 11 и 12 и выходы 13- 519.Работа устройства рассматривается в составе многопроцессорной вычислительной сисмы, содержащей процессоры 20 -20, запоминающие устройства 21 -21, архивы мас 10к 1сивов 22 -22 и каналы обмена 23 и 24.При поиске некоторым процессором элемента массива на вход 10 одноименногоустройства поступает запрос, содержаший 15поле признака запроса П, поле номера массива Л, поле номера байта Я, с коюлторого начинается требуемый элемент массива, и поле длины элемента массива в бай -тах ЮПризнак запроса имеет два значения, первое из которых соответствует случаю, когда требуемый элемент содержится в массиве, который принадлежит только задаче, решаемой на запрашивающем процессоре. Второе значение признака указывает на то, чтотребуемый элемент содержится в массиве,который принадлежит не только задаче, решаемой на запрашивающем процессоре, и,следовательно, принципиально может уже 30находиться в запоминающем устройстве некоторого другого процессора, на которомрешается некоторая другая задача,Запрос поступает в блок 1 классифика -ции запросов и в блок 2 выдачи форматных 35запросов, В блоке классификашш запросовпо признаку П определяется принадлежностьискомого массива одной или несколькимизадачам, реализуемым в данное время вмногопроцессорной вычислительной системе, 40Результат анализа признака П передаетсяв блок форматных запросов, в блок сопряжения с каналом и в блок замещения страниРассмотрим работу устройства для случая, когда признак запроса П имеет первоезначение, Так как требуемьш элемент массива может начинаться с любого байта машинного слова и число байтов в элементе можетбьгть существенно большим, то, следовательно, требуемый элемент может быть расположен в одном, двух и более машинных словах, В связи с этим в блоке выдачи форматных запросов поступивший запрос либо остается без изменения, либо преобразуетсяв ряд запросов, соответствующих форматумашинного слова,Сформированный запрос из блока 2 вы -дачи форматных запросов поступает в блок5 поиска информации, устроенный по ассоциативному принципу, Если требуемое ма - шинное слово находитсч в блоке 7 хранения информации, то в блоке 5 поиска информа - пии будет выработан признак совпадения, в соответствии с которым из блока хранения информации будет считано машинное слово,Жсодержашее искомый элемент или его часть, Блок 6 формирования признака совпадения определяет наличие хотя бы одного совга - дения между запросом и содержимым блока поиска информации, запрешая при этом дальнейшую работу блоков 3 и 4. Считанное из блока 7 хранеш 1 я информации машинное слово поступает в блок 8 упаковки слова, куда из блока выдачи форматных запросов подается признак конца счи -тывания элемента массива и признак расположения элемента массива или его части всчитанном машинном слове. По второму признаку в блоке упаковке слова производитсясдвиг элемента массива или его части встаршие разряды формата машинного слова,Передача считанной информации на один извыходов устройства происходит в тех слу -чаях, когда требуемый элемент считан полностью или когда упаковано машинное слово.При этом выход 15, 16 или 17 определяетпризнак, который поступает на вход блока 9направления передачи, вырабатывающийуправляющий признак, который подается йавход блока 8 упаковки слова. С передачейинформации на выход устройства из блокаупаковки слова в блок выдачи форматных запросов поступает разрешение на обслуживаниеследуюшего запроса. Это же требование поступает в блок. выдачи форматных запросови в том случае, когда машинное слово неупаковано и считывание требуемого элемента еще не закончилось, т. е. когда элементмассива расположен не в одном машинномслове, и первая считанная его часть меньшемашинного слова,Предположим теперь, что признак запросаП в формате запроса имеет второе значение,В этом случае возможны два варианта;массив с требуемым элементом находит -ся в одном из устройств (в том числе в устройстве, на которое поступил запрос);массива с требуемым элементом нет нив одном устройстве,Если массив с требуемым элементом оказался в устройстве, получившим запрос, тоустройство работает, как было описано.Если в устройстве, получившем запрос,массива с требуемым элементом не оказа -лось, то блок формирования признака совпадения разрешает дальнейшую работу блоков3 и 4. Блок 3 сопряжения с каналом пере -дает. признак захвата канала в блок 2 выдачи форматных запросов, который через выход 14 выдаст в канал обмена 23 номер массива, нол ер байта, длину элемента в байтахи адрес запрациваюшего процессора,Если требуемый элемент содержится в ка ком-либо другом блоке хранения информации,то этот элемент вместе с адресом запрашивающего процессора поступает через каналобмена 23 непосредственно в этот процес -сор. ЮЕсли требуемого элемента нет ни в одном блоке хранения информации, то блок 2въдачи форматных запросов определяет, какую страницу в блоке хранения информацииможно заменить, а блок 3 устанавливает 15связь с архивами массивов 22 -22 черезканал обмена 24. После определения заме -шаемой страницы блок 4 замещения страницы определяет, производилась или нет за -20пись информации в эту страницу на предыдущем этапе вычислений,Если запись в замещаемую страницу непроизводилась, то после захвата канала изблока 3 в блок 2 выдачи форматных запро 25сов поступает признак на передачу запросана выход 18 устройства, и одновременнозапрос заносится в блок поиска информациина место замещаемой страницы. При поступлении на вход 12 устройства страницы, со 30держащей требуемый элемент массива, за -пись этой страницы в блок хранения информации (запись содержит поле номера массиваи поле номера байта) производит блок 9 направления передачи в соответствии с адре -сом, который поступает с выхода 12 устройства в блок направления передачи и далеев блок поиска информации.Если же запись в замещаемую страницупроизводилась, то в этом случае необходимо передать замещаемую страницу в одиниз архивов массивов 22 -22, а затемуже на ее место записать страницу с тре -буемым элементом массива, При этом попризнаку захвата канала, поступающему изблока 3 в блок 4 замещения страницы, навыход 13 устройства передается запрос, содержащий Я Я (где Я - номер первого элемента страницы) и номер запрашивающего процессора, В соответствии с переданным запросом на вход 10 устройства и далее в блок 9 направления передачи посту -пает разрешение на передачу замещаемойстраницы из блока хранения информации данного устройства через блок упаковки слована выход 15, Адрес этой страницы посту -пает из блока замещения страницы в блоквыдачи форматных запросов. С концом пе -редачи страницы из блока направления передачи в блок выдачи форматных запросов1 поступает признак разрешения передачи запроса пскомого элемента массива. По этому признаку необслуженпый запрос посту - пает из блока 2 выдачи форматных запро - сов па выход 13 устройства. Далее работа устройства сводится к случаю обслуживания запроса в отсутствие записи в замещаемую страницу.ф ормула изобретенияУстройство длч управления памятью в многопроцессорной вычислительной системе, содержащее блок поиска информации, пер - вый информационный вход которого соединен с первым информационным входом устрой - ства, блок формирования признака совпадения и блок хранения информации, адресный вход которого соединен с адресным выходом блока поиска информации, о т л и - ч а ю ш е е с я тем, что. с целью повььшения быстродействия системы, в него введены блок классификации запросов, инфор - мационный вход которого подключен ко второму информационному входу устройства, блок выдачи форматных запросов, вход которого соединен с выходом блока классификации запросов, первый информационный вход подключен к первому информационному входу устройства, второй информационный вход - ко второму информационному входу устройства, три информационных выхода подключены соответственно к первому и второму информационным выходам устройства п ко второму информационному входу блока поиска информации, блок сопряжения с каналом, два управляющих входа которого соединены соответственно с управляющим выходом блока классификации запросов и первым уп/ равляюшим выходом блока форматных запросов, первый управляющий выход подклю - чен к первому управляющему входу блока выдачи форматных запросов, два информационных выхода подключены соответствен - но к третьему и четвертому информацион - ным выходам устройства, блок замещения страницы, управляющий вход которого соединен с управляющим выходом блока клас - сификации запросов, информационный входс первым информационным выходом блока поиска информации, вход признака подклю - чен к одноименному выходу блока сопряжения с каналом, информационньш выход соединен со вторым информационным выходом устройства, управляющий выход подключен ко второму управляющему входу блока вы - дачи форматных запросов, вход блока фор - мирования признака совпадения соединен со вторым информационным выходом блока поис-,"10 70 ка информации, выход подключен ко входамзапрета блоков сопряжения с каналом и замещения страницы, блок упаковки слова,информационный вход которого соединен свыходом блока хранения информации, первый 5управляющий вход соединен со вторым управляющим выходом блока выдачи форматныхзапросов, управляюший выход подключен ктретьему управляющему входу блока вьда -чи форматных запросов, три информационных Овыхода подключены соответственно к пятому, шестому и седьмому информационным выходам устройства, и блок направления передачи, информационньш вход которого соединен с третьим информационным входомустройства, вход и вьход признака соединены соответственно с одноименными выхо -дом и входом блока выдачи форматных за -просов, управляющий вь,"ход подключен ковторому управляющему входу блока упаков -ки слова, информационный выход соединенс информационным входом блока храненияинформации и с третьим информационнымвходом блока поиска информации.ССРилиал ППП "Патент", г. Ужгород, ул, Проектная,Заказ 3978/343 Тираж 0 НИИПИ Государственног по делам113035, Москва, Ж, 864 Подписное комитета Совета Министро обретений и открытий Раушскаа наб., д. 4/5