B. Л. Арлазаров, A. С Варпаховский, В. А. Ведешенков, А. Ф. Волков, Е, А. Диниц, Н, E. Емельянов, В. Д. Зенкин, А, В. Лебедев, . B. T. Лысиков, Г. К. Сорокин, А. В. Усков, И. A. Фараджев и И. Б. Чернышева (71) Заявитель

Ордена Ленина институт проблем управления (54) УСТРОЙСТВО ДЛЯ УПРАВЛЕНИЯ ПАМЯТЬЮ В МНОГОПРОЦЕССОРНОЙ

ВЫЧ ИСЛИТ ЕЛЬНОЙ СИСТЕМЕ

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

Известные устройства позволяют обрабатывать запросы, поступаюшие в виде физивЂ” ческих адресов блока хранения информации, что не дает возможности осушествлять вь.вЂ” борку требуемой информации из любой части памяти многопроцессорной системы лю° бой программой, реализуемой в данный момент. (1

В многопроцессорных вычислительных системах особый интерес представляет воп1рос коллективного пользования одними и

I теми >ке данными, храняшпмися в памяти.

Под коллективным пользованием данными понимается такой режим работы, когда

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

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

Независимо от способа органттзашти памяти системы (страничной пли сегментной) повЂ” лагаем, что всякое обрашенпе к памяти происходит по некоторому идентификатору, поз1к воляюшему определить адрес элемента данных. Тогда при многоуровневой системе памяти при всяком обрашении к памяти реавЂ” лизуемого в данный момент в системе процесса по идентификатору элемента данных (элемент сегмента, массива, слово страницы) блок, содержаший требуемый элемент, найденный на одном из более низких уровней памяти, будет передан в самьш верхвЂ” ний уровень для оперативной работы провЂ” рь цесса с элементами этого блока. При сме52 2501. .;о процосса, работающего с теми же элементами данных, ч î и предыдущий процесс, и обращающегося и памяти со своим идентификатором, по за теми же элементами (они находятся в верхнем уровне памяти), устанавливает- 5 ся соответствие между идентификаторами и второй процесс тем самым получает доступ к

; ем же элементам данных, что и предыдущий процесс. При этом каждый из процессов может работать в любом разрешенном ему рс- 10

-,ки;..е (чтенпе, запись).

Для системы с несколькими процессоравЂ” ми управление коллективным пользованием данцыми усложняется. Если в системе имевЂ” ется несколько процессоров, но с одной об- 1 шей оперативной памятью, то в каждый момент времени такую систему можно рассматривать как однопроцессорную с точки зревЂ” ния обращения к памяти, так как за каждый цикл памяти обслуживается лишь одно обра- 20 щение. Поэтому, если в оперативной памяти находятся данные, которыми пользуются два и более процессов в момент их реализации, вЂ”.о при одновременном обращении к памяти за одним и тем же элементом данных нескольких процессоров только один процессор, выделенный в результате разрешения конфликтной ситуации, получит право на использовавЂ” ние этого элемента. Затем этот элемент может быть использован другим выделенным 30 процессором, третьим и т. д. При этом возникает еще и дополнительная задача синхровЂ” низации процессов, но в смысле коллективвЂ” ного пользования такая система обеспечивЂ” вает этот режим. 35

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

Рассмотрим, например, двухпроцессорную <> систему, где каждому процессу выделен свой блок оперативной памяти и в данный момент реализуется два процесса, работающие с одними и теми же элементами данных в режимах чтения и записи соответственно. Тогда при обращении к одному и тому же элементу двух процессоров в оперативную память каждого процесса будет передан один и тот же блок данных и каждый процесс будет независимо от другого процесса работать с этим блоком данных, При этом каждый из процессов может в результате режима записи различным образом изменять элементы этого блока. В результате в двух блоках оперативной памяти будут получены два разных по содер>;;анпю блока данных, но имеющих один идентификатор. B памяти следующего более низкого уровня при этом хранится неизменвЂ” ная копия этого блока. Такое состояние, бло:-.а данных, имеющего один идентификатор, недопустимо, но оно не возникает в многопроцессорной системе с обшей оперативной памятью, Белью изобретения является повышение эффективности. работы устройства для управления памятью и, следовательно, быстродей- ствия системы в целом.

Для достижения поставленной цели в предлагаемое устройство введены блок классификации запросов, блок выдачи форматны запросов, блок сопряжения с каналом связи, блок замещения страницы, блок направления передачи информации и блок упаковки слова с соответствующими цепями связи между введенными и известными блоками. Это позволяет обеспечить необходимые условия режиму коллективного пользования двум и более процессам в многопроцессорной вычислительной системе и иерархической структурой памяти, в которой каждому процессу выделен свой блок памяти на самом верхнем ее уровне, а каждый процессор имеет непосредственную связь только со своим блоком памяти. Кроме того, все блоки памяти этого уровня связаны между собой общим каналом связи. Всякое обращение любого процесса к памяти происходит по идентификатору, в котором определен номер массива, номер первого байта требуемого элемента и длина элемента байтов. В идентификаторе имеется таквЂ” же признак, является ли массив с данным номером принадлежащим одному процессу или многим процессам.

Таким образом, устройство позволяет обрабатывать запросы, поступающие не в виде физических адресов блока хранения инвЂ” формации, а в виде идентификаторов массива и номера элемента в нем, что обеспечивает выборку этого элемента массива из любой части памяти многопроцессорной системы и любой программой, реализуемой в данный момент. IIpouecc перемещения инфор мации не связан с определением физических адресов месторасположения замещаемой или передаваемой информации, что позволяет аппаратно реализовать процесс динамического выделения требуемого объема памяти для обрабатываемой информации.

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

522501

4 замешения страницы, блок 5 поиска инвЂ” формации, блок 6 формирования признака совпадения, блок 7 хранения информации, блок 8 упаковки слова, блок 9 направления передачи, входы 10, 11 и 12 и выходы 13- 5

19.

Работа устройства рассматривается в составе многопроцессорной вычислительной сисмы, содержащей процессоры 20 -20, запоминаюшие устройства 21 -21, архивы мас10

1 к сивов 22 -22 и каналы обмена 23 и 24.

При поиске некоторым процессором эле мента массива на вход 10 одноименного устройства поступает запрос, содержаший 15 поле признака запроса П, поле номера массива N, поле номера байта Я, с коп торого начинается требуемый элемент массива, и поле длины элемента массива в байвЂ” тах 30

Признак запроса имеет два значения, первое из которых соответствует случаю, когда требуемый элемент содержится в массиве, который принадлежит только задаче, решаемой на зацрашиваюшем процессоре. Вто- 25 рое значение признака указывает на то, что требуемый элемент содержится в массиве, который принадлежит не только задаче, решаемой на запрашиваюшем процессоре, и, следовательно, принципиально может уже 30 находиться в запоминаюшем устройстве некоторого другого процессора, на котором решается некоторая другая задача.

Запрос поступает в блок 1 классификавЂ” ции запросов и в блок 2 выдачи форматных З5 запросов. В блоке классификашш запросов по признаку П определяется принадлежность искомого массива одной или несколькими задачам, реализуемым в данное время в многопроцессорной вычислительной системе. 40

Результат анализа признака П передается в блок форматных запросов, в блок сопряжения с каналом и в блок замешения страницы.

Рассмотрим работу устройства для слу- 45 чая, когда признак запроса П имеет первое значение. Так как требуемьш элемент массива может начинаться с любого байта машинного слова и число байтов в элементе может бьгть существенно большим, то, следователь- 50 но, требуемый элемент может быть расположен в одном, двух и более машинных словах. В связи с этим в блоке выдачи форматных запросов поступивший запрос либо остается без изменения, либо преобразуется в ряд запросов, соответствующих формату машинного слова.

Сформированный запрос из блока 2 вывЂ” дачи форматных запросов поступает в блок

5 поиска информации, устроенный по ассо-циативному принципу. Если требуемое мавЂ” шинное слово находитсч в блоке 7 хранения информации, то в блоке 5 поиска информавЂ” пии будет выработан признак совпадения, в соответствии с которым из блока хранения информации будет считано машинное слово, содержашее искомый элемент или его часть.

Блок 6 формирования признака совпадения определяет наличие хотя бы одного совгавЂ” дения между запросом и содержимым блока поиска информации, запрешая при этом дальнейшую работу блоков 3 и 4.

Считанное из блока 7 хранеш1я информации машинное слово поступает в блок 8 упаковки слова, куда из блока выдачи форматных запросов подается признак конца счивЂ” тывания элемента массива и признак расположения элемента массива или его части в считанном машинном слове. По второму признаку в блоке упаковке слова производится сдвиг элемента массива или его части в старшие разряды формата машинного слова.

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

При этом выход 15, 16 или 17 определяет признак, который поступает на вход блока 9 направления передачи, вырабатываюший управляющий признак, который подается йа вход блока 8 упаковки слова. С передачей информации на выход устройства из блока упаковки слова в блок выдачи форматных запросов поступает разрешение на обслуживание следуюшего запроса. Это же требование поступает в блок выдачи форматных запросов и в том случае, когда машинное слово не упаковано и считывание требуемого элемента еще не закончилось, т. е. когда элемент массива расположен не в одном машинном слове, и первая считанная его часть меньше машинного слова.

Предположим теперь, что признак запроса .

1 П в формате запроса имеет второе значение.

В этом случае возможны два варианта: массив с требуемым элементом находитвЂ” ся в одном из устройств (в том числе в устройстве, на которое поступил запрос); массива с требуемым элементом нет ни в одном устройстве.

Если массив с требуемым элементом оказался в устройстве, получившим запрос, то устройство работает, как было описано.

Если в устройстве, получившем запрос, массива с требуемым элементом не оказавЂ” лось, то блок формирования признака совпадения разрешает дальнейшую работу блоков

3 и 4. Блок 3 сопряжения с каналом перевЂ” дает признак захвата канала в блок 2 выда-522501 чи форматных запросов, KQTopbN через Bblход 14 выдаст в канал обмена 23 номер массива, нол ер байта, длину элемента в байтах и адрес запрашивающего процессора.

Если требуемый элемент содержится в ка-5 ком-либо другом блоке хранения информации, то этот элемент вместе с адресом запрашивающего процессора поступает через канал обмена 23 непосредственно в этот процесвЂ” сор. l0

Если требуемого элемента нет ни в одном блоке хранения информации, то блок 2 выдачи форматных запросов определяет, какую страницу в блоке хранения информации можно заменить, а блок 3 устанавливает у связь с архивами массивов 22 -22 через канал обмена 24. После определения замевЂ” шаемой страницы блок 4 замещения страницы определяет, производилась или нет завЂ”

20 пись информации в эту страницу на предыдущем этапе вычислений.

Если запись в замещаемую страницу не

I производилась, то после захвата канала из блока 3 в блок 2 выдачи форматных запро25 сов поступает признак на передачу запроса на выход 18 устройства, и одновременно запрос заносится в блок поиска информации на место замещаемой страницы. При поступлении на вход 12 устройства страницы, со30 держащей требуемый элемент массива, завЂ” пись этой страницы в блок хранения информации (запись содержит поле номера массива и поле номера байта) производит блок 9 направления передачи в соответствии с адресом, который поступает с выхода 12 устройства в блок направления передачи и далее в блок поиска информации.

Если же запись в замещаемую страницу производилась, то в этом случае необходимо передать замещаемую страницу в один из архивов массивов 22 -22, а затем уже на ее место записать страницу с тревЂ” буемым элементом массива, При этом по признаку захвата канала, поступающему из блока 3 в блок 4 замещения страницы, на выход 13 устройства передается запрос, содержащий Я Я (где N вЂ” номер первого элемента страницы) и номер запрашивающего процессора, В соответствии с переданHbM запросом на вход 10 устройства и далее в блок 9 направления передачи постувЂ” пает разрешение на передачу замещаемой страницы из блока хранения информации данного устройства через блок упаковки слова на выход 15. Agpec этой страницы постувЂ” пает из блока замещения страницы в блок выдачи форматных запросов. С концом певЂ” редачи страницы из блока направления передачи в блок выдачи форматных запросов

1 поступает признак разрешения передачи запроса пскомого элемента массива. По этому признаку необслуженпый запрос постувЂ” пает из блока 2 выдачи форматных запровЂ” сов па выход 13 устройства. Далее работа устройства сводится к случаю обслуживания запроса в отсутствие записи в замещаемую страницу, Ф ормула изобретения

Устройство для управления памятью в многопроцессорной вычислительной системе, содержащее блок поиска информации, первЂ” вый информационный вход которого соединен с первым информационным входом устройвЂ” ства, блок формирования признака совпадения и блок хранения информации, адресный вход которого соединен с адресным выходом блока поиска информации, о т л ивЂ” ч а ю ш е е с я тем, что. с целью повььшения быстродействия системы, в него введены блок классификации запросов, инфорвЂ” мационный вход которого подключен ко второму информационному входу устройства, блок выдачи форматных запросов, вход которого соединен с выходом блока классификации запросов, первый информационный вход подключен к первому информационному входу устройства, второй информационный входвЂ” ко второму информационному входу устройства, три информационных выхода подключены соответственно к первому и второму информационным выходам устройства п ко второму информационному входу блока поиска информации, блок сопряжения с каналом, два управляющих входа которого соединены соответственно с управляющим выходом блока классификации запросов и первым уп/ равляющим выходом блока форматных запросов, первый управляющий выход подклювЂ” чен к первому управляющему входу блока выдачи форматных запросов, два информационных выхода подключены соответственвЂ” но к третьему и четвертому информационвЂ” ным выходам устройства, блок замещения страницы, управляющий вход которого соединен с управляющим выходом блока класвЂ” сификации запросов, информационный входс первым информационным выходом блока поиска информации, вход признака подклювЂ” чен к одноименному выходу блока сопряжения с каналом, информационный выход соединен со вторым информационным выходом устройства, управляющий выход подключен ко второму управляющему входу блока вывЂ” дачи форматных запросов, вход блока форвЂ” мирования признака совпадения соединен со вторым информационным выходом блока поис-, 22501

"10

10 ка информации, выход подключен ко входам запрета блоков сопряжения с каналом и замешения страницы, блок упаковки слова, информационный вход которого соединен с выходом блока хранения информации, первый управляющий вход соединен со вторым управляющим выходом блока выдачи форматных запросов, управляюший выход подключен к третьему управляюшему входу блока выдавЂ” чи форматных запросов, три информационных )Q выхода подключены соответственно к пятому, шестому и седьмому информационным выходам устройства, и блок направления передачи, информационный вход которого соединен с третьим информационным входом .устройства, вход и вьход признака соединены соответственно с одноименными выховЂ” дом и входом блока выдачи форматных завЂ” просов, управляюший вь."ход подключен ко второму управляюшему входу блока упаковвЂ” ки слова, информационный выход соединен с информационным входом блока хранения информации и с третьим информационным входом блока поиска информации.

522501

Ф 4

Составитель Л. Жеренов

Редактор О. Кузнецова Техред М,Левицкая КорректорТ. Кравченко

Заказ 3978/343 Тираж 864 Подписное

11НИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушскаа наб., д. 4/5

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4