Система доступа к памяти

 

1. СИСТЕМА ДОСТУПА К ПАМЯТИ, содержащая К мультиплексоров адреса , М мультиплексоров данных, К регистров адреса, К блоков памяти, причем группа адресных входов каждого мультиплексора данных и группа информационных входов каждого мультиплексора адреса подключена к соответствующей группе запросных входов системы, группа выходов каждого мультиплексора адреса подключена к группе информационных входов соответствующего регистра адреса, группа выходов которого соединена с группой адресных входов соответствующего блока памяти, группа выходов которого соединена с соответствующей группой информационных входов КЕ1ЖДОГО мультиплексора данных, отличающаяся тем, что, с целью повышения производительности , в нее введены К блоков индивидуального управления, М буферных регистров данных, К блоков обработки запросов, 1( мультиплексоров записываемых данных, причем установочный вход каждого i -го буферного регистра данных ( 1 ) подключен к выходу записи каждого -го блока индивидуального управления , исполнительный выход каждого блока индивидуального управления подключен к входу синхронизации соответствующего регистра адреса, входу записи соответствующего блока памяти и управляющему входу соответствующего блока обработки запросов , группа информационных входов каждого блока памяти подключена к группе выходов соответствующего мультиплексо ра записываемых данных, каждая ( -я группа информационных входов которого объединена с группой информационных входов системы и подключена к группе информационных (Л выходов соответствующего буферного с: регистра данных, выход поля занятости каждого буферного регистра данных подключен к -м входам занятости соответствующих блоков индивидуального управления, группы входов приема запросов которых подСП ключены к группам информационных выходов , соответствующих блоков обрасо ботки запросов, вход сброса занятости каждого буферного регистра данных подключен к соответствующему входу сброса системы, группа информационных входов каждого буферного регистра данных подключена к группе информационных выходов соответствующего мультиплексора данных, группа выходов J -го блока памяти подключена к j -и группе информационных входов ( 3 ) соответствующего мультиплексора данных, i -я группа запросных входов каждого блока обработки запросов подключена к

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИН (19) ((1) 4(5!) С 06 F 12/00

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМ У СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3673758/24-24 (22) 19.12.83 (46) 23.04.85. Бюл. N 15 (72) С.С.Букатин, В.А. Екимов, П.A. Чебатко, С.В.Яблонский и В.В. Ялик (53) 681.325(088.8) (56) 1. Патект США )1-. 4325116, кл. 364/200, опублик. 1982.

2. Патент США 4282572, кл. 362/200, опублик. 1981 (прототип), (54)(57) 1. СИСТЕМА ДОСТУПА К ПАИЯТИ, содержащая K мультиплексоров адреса, Ц мультиплексоров данных, К регистров адреса, К блоков памяти, причем группа адресных входов каждого мультиплексора данных и группа информационных входов .каждого мультиплексора адреса подключена к соответствующей группе запросных входов .системы, группа выходов каждого мультиплексора адреса подключена к группе информационных входов соответствующего регистра адреса, группа выходов которого соединена с группой адресных входов соответствующего блока памяти, группа выходов которого соединена с соответствующей группой информационных входов каждого мультиплексора данных, отличающаяся тем, что, с целью повышения производительности, в нее введены K блоков индивидуального управления, М буферных регистров данных, K блоков обработки запросов, K мультиплексоров записываемых данных> причем установочный вход каждого 1 -го буферного регистра данных { = 1 -Щ подключен к выходу записи каждого

i -го блока индивидуального управления., исполнительный выход каждого блока индивидуального управления подключен к входу синхронизации соответствующего регистра адреса, входу записи соответствующего блока памяти и управляющему входу соответствующего блока обработки запросов, группа информационных входов каждого блока памяти подключена к группе выходов соответствующего муль— типлексора записываемых данных, каждая (-я группа информационных входов которого объединена с группой информационных входов системы и подключена к группе информационных выходов соответствующего буферного регистра данных, выход поля занятости каждого буферного регистра данных подключен к -м входам занятости соответствующих блоков индивидуального управления, группы входов приема запросов которых подключены к группам информационных выходов, соответствующих блоков обработки запросов, вход сброса занятости каждого буферного регистра данных подключен к соответствующему входу сброса системы, группа .информационных входов каждого буферного регистра данных подключена к группе информационных выходов соответствующего мультиплексора данных, группа выходов -го блока памяти подключена к ) -й группе информационных входов (j = t-K) соответствующего мультиплексора данных, 1 -я группа запросных входов каждого блока обработки запросов подключена к

1151974 группе адресных входов соответствующего мультиплексора данных, группа выходов приоритетности запросов блока обработки запросов подключена к соответствующим группам управляющих входов мультиплексора адреса, мультиплексора записываемых данных и группе входов очередности выполнения запросов блока индивидуального управления, выход граничного адреса каждого блока памяти подключен к входу адреса соответствующего блока обработки запросов, причем блок индивидуального управления содержит ждущий генератор импульсов, элемент

ИЛИ, счетчик, дешифратор, триггер, коммутатор, группу из М элементов И, причем вход запуска ждущего генератора подключен к выходу элемента

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

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

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

2. Система по п. 1, о т л и— ч а ю щ а я с я тем, что блок обработки запросов содержит регистр, узел приоритета и М схем сравнения, причем первые входы схем сравнения подключены к входам запросов блока, вторые входы схем сравнения подключены к входам адреса блока, выходы схем сравнения подключены к информационным входам регистра, а также к группе информационных выходов блока, управляющий вход регистра подключен к управляющему входу блока, выходы регистра подключены к входам узла приоритета, выходы которого являются выходами приоритетности блока, более двух процессоров и снижению жизнеспособности системы.

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

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

20

3 115 f непроизвольному увеличению времени занятости отдельных сегментов памяти.

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

Все перечисленные недостатки приводят к сокращению производительности мультипроцессорной системы доступа к памяти.

Цель изобретения — повышение производительности системы доступа к памяти.

Поставленная цель достигается тем, что в систему доступа к памяти содержащую k мультиплексоров адреса, М мультиплексоров данных, К регистров адреса, К блоков памяти, причем группа адресных входов каждого муль- -25 типлексора данных и группа информационных входов каждого. мультиплексора адреса подключена к соответствующей группе запросных входов системы, группа выходов каждого мультиплексора адреса подключена к группе информационных входов соответствующего регистра адреса, группа выходов которого соединена с группой адресных входов соответствующего блока памя35 ти, группа выходов которого соединена с соответствующей группой информационных входов каждого мультиплексора данных, введены k .блоков индивидуального управления, М буфер- 40 ных регистров данных, K блоков обработки запросов, К мультиплексо-. ров записываемых данных, причем установочный вход каждого -го буферного регистра данных (1= 1 -М) под45 ключен к выходу записи каждого

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

55 каждого. блока памяти подключена к группе выходов соответствующего мультиплексора записываемых данных, 974 4 каждая 1 -я группа информационных входов которого объединена с группой информационных входов системы и подключена к группе информационных выходов соответствующего буферного регистра данных, выход поля занятости каждого буферного регистра данных подключен к -м входам занятости соответствующих блоков индивидуального управления, группы входов приема запросов которых подключены к группам информационных выходов соответствующих блоков обработки запросов, вход сброса занятости каждого буферного регистра данных подключен к соответствующему входу сброса системы, группа информационных входов каждого буферного регистра данных подключена к группе инфор— мационных выходов соответствующего мультиплексора данных, группа выходов j -го блока: памяти подключена к

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

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

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

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

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

Система доступа к памяти содержит

, М процессоров 1, K блоков 2 памяти, 40

lA мультип ексоров 3 данных, N буферных регистров 4 данных, К мультиплексоров 5 адреса, 1I регистров 6 адреса, k блоков 7 обработки запросов, 1 блоков 8 индивидуального управле- 45 ния и К мультиплексоров 9 записываемых данных.

Буферный регистр данных содержит регистр 10 и триггер !1.

Блок обработки запросов содержит регистр 12, узел 13 приоритета и И схем 14 сравнения.

Блок индивидуального управления содержит ждущий генератор 15 импульсов, элемент ИЛИ 16, счетчик 17, дешифратор 18, триггер 19, коммутатор 20, группу элементов И 21.

Кроме того, схема доступа к памяти содержит шину 22 считывания информации, шину 23 запросов процессоров, шину 24 данных мультиплексоров данных, шину 25 данных буферного регистра данных, шину 26 адреса мультиплексора адреса, шину 27 адреса регистра адреса, шину 28 управления, шину 29 данных мультиплексора записываемых данных, установочную шину 30, шину 31 состояния триггеров, шину 32 сброса, шину 33 адреса мультиплексоров данных, шину 34 граничных адресов блоков памяти и шину 35 сравнения.

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

Система доступа к памяти (фиг. 1) объединяет М процессоров 1, которые могут обращаться к общей для них памяти за информацией. Если общая память выполнена в виде запоминающего устройства требуемого объема, имеющего один вход и один выход, то неизбежно возникают конфликты по обращению к памяти от различных процессоров 1. Процессор 1, обращение от которого к памяти в данный момент реализуется, выполняет производительную работу, а все остальные процессоры 1, ожидающие приема их запросов на обработку, простаивают. Обращение процессоров 1 к общей памяти преследует в общем случае две цели: получение новой управляющей информации, выборка из памяти новой порции обрабатываемой информации или занесение в память промежуточных и конечных результатов.

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

В предлагаемой системе общая память разбивается на К блоков 2 памяти. С увеличением числа блоков

2 памяти увеличивается вероятность бесконфликтной работы системы, но увеличивается и оборудование.

Кроме того, информация, предназначенная для некоторого процесса 1, занимает какую-то локальную область

1151974 памяти и пересечение этих областей для различных процессоров незначительно (обычно это пересечение происходит на общесистемных организующих участках программы) . 5

Если объем блока 2 памяти выбран меньшим или равным минимальному. объему информации, требуемому для какого-либо процессора 1, а процессоры 1 характеризуются примерно оди"

10 иаковым быстродействием, то большая часть (или все) обращений от различных процессоров 1 осуществляется к различным блокам 2 памяти. Это объясняется тем, что в блоках пересечения, т.е. в блоках, содержащих окончание задачи для одного процессора 1 и начало для другого, обычно размещаются информация для обработки, промежуточные результаты одного процессора 1 и управляющая информация для другого..Кроме того, необходимо учитывать конкретные особенности алгоритмов различных задач.

Информация считывается из ) -го блока 2 памяти (шины 22) по запросу от q -го процессора 1 (шины 23} через i --й "мультиплексор 3 данных (шины 24) и l -й буферный регистр

4 данных (шины 25) s j -й процессор. 30

В системе имеется. М мультиплексоров

3 данных и буферных регистров 4 данных в соответствии с числом процессоров 1.

Адрес считываемых или записываемых,15 данных через 1 -й мультиплексор 5 адреса заносится по шине 26 на регистр

6 адреса, выход 27 которого соединен с адресными входами блока 2 памяти.

Включение j -го блока 2 памяти 40 в работу осуществляется после приема обращенного к нему запроса в 1 -й блок 7 обработки запросов и управляется сигналами„ формируемыми j -м устройством 8 индивидуального управ- 45 ления (шины 28).

Информация, записываемая из 1 -го процессора 1 в -й блок 2 памяти, по шинам .23 заносится через < -й мультиплексор 3 данных (шины 24) 50 на g- -й буферный регистр 4 данных и с выходных шин 25 буферного регистра 4 данных через j -й мультиплексор 9 записываемых данных по шинам 29 поступает на информационный вход j -го блока 2 памяти.

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

30 из блоков 8 индивидуального управ- . ления. Этим же импульсом производится прием информации с шин 24 на регистр 10. Выход триггера 11 (шина 31) сигнализирует о наличии в регистре

10 запрашиваемой информации. Установка в единичное состояние триггера l1 запрещает прием (с занятием какого-лнбо блока 2 памяти) запроса от процессора l которому соответствует установленный триггер 11.

Это позволяет обеспечить прием на обработку запроса от другого процессора 11 имеющего более низкий приоритет, в то время, когда более приоритетный процессор 1 занят на приеме ранее подготовленной информации и не готов к приему новой.

Сброс триггера 11 осуществляется сигналом, поступающим по шине 32 от соответствующего процессора по окончании в нем операций по приему информации с буферного регистра и данных, т.е. когда дальнейшее хранение информации в буферном регистре 4 данных не требуется.

Количество регистров 4 данных и мультиплексоров 3 данных в системе равно числу процессоров 1 и между ними установлено взаимооднозначное соответствие.

Мультиплексор 9 записываемых данных, число которых в системе равно числу блоков 2 памяти, представляет собой 6 М - входовых мультиплексоров с общей адресной частью, на которую по шинам 33 подается из соответствующего блока 7 обработки запросов адресная комбинация выбирающая источник записываемых данных. (Мультиплексоры 3 данных представляют собой совокупность иэ К входовых мультиплексоров с общими адресными входами.

Мультиплексоры 5 адреса представляют собой совокупность Й -входовых мультиплексоров с общими адресными входами, число которых соответстt 151974

10 вует числу разрядов в адресной информации для блока 2 памяти.

Регистр 10 является 3 -разрядным регистром с дизъюнктивно соединенными входами синхронизации, на которые по шинам 30 поступают исполнительные импульсы от того из блоков 8 индивидуального управления, который обрабатывает запрос, соответствующий рассматриваемому регист- 10 ру 4 данных. Эти же импульсы поступают одновременно на дизъюнктивно . соединенные входы установки в единицу (5) триггера 1 1, являющегося

AS -триггером, на вход 1 поступает импульс сброса от подключенного к шинам внешней связи (которыми являются шины 23, 25 и 32) процессора 1.

Блок 7 обработки запросов (фиг. 3) содержит регистр 12, на который по 20 шинам 23 от процессоров 1 помещаются соответствующие данному блоку 2 памяти запросы. Записью запросов в регистр 12 управляет блок 8 индивидуального управления по шинам 28. 25

Запросы проверяются на соответствие данному блоку 2 памяти на схемах

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

Выходные шины 35 схем 14 сравнения соединены с информационными входами регистра t2 а также с входами блока 8 индивидуального управления для запуска временной диаграммы об- 35 работки запросов.

Запросы, записанные в регистр 12, поступают на узел 13 приоритета, где определяется очередность выполнения запросов, и по шине 33 наиболее

40 приоритетный иэ имеющихся запросов поступает на соответствующие входы мультиплексора 5 адреса, мультиплексора 9 записываемых данных и блока 8 индивидуального управления. По окончании обработки запроса производится новый прием в регистр 12.

Таким образом, при одновременном поступлении нескольких обращений к одному блоку 2 памяти все запро- N сы принимаются на регистр 12, но через узел t3 приоритета проходит только один из них (наиболее приоритетный). После окончания обработки процессору 1 по шине 25 сообщается об этом и обработанный запрос снимается с шины 23. Осуществляется повторный прием на регистр 12 ожидавших обработки и вновь поступивших к этому моменту запросов, после чего процесс повторяется.

Все управление в системе доступа к памяти осуществляется блоками 8 индивидуального управления (фиг. 4).

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

16, собирающего запросы, поступающие по шинам 35 к соответствующему блоку 2 памяти.

С выхода ждущего генератора 15 импульсов импульсы поступают на счетчик 17 и с его выходов на дешифратор 18, на выходе 28 которого формируются исполнительные импульсы, управляющие работой системы. Триггер 19 сигнализирует о занятости данного блока 2 памяти обработкой какого-либо запроса. Он устанавливается в единичное состояние определенным импульсом по шине 28, при условии, что триггер

11, соответствующий процессору 1, от которого поступил запрос, находится в нулевом состоянии, что определяется схемой коммутатора 20. Число групп коммутации в этой схеме соответствует числу процессоров 1. Выход коммутатора (единичный уровень на нем) запрещает установку триггера

19. На нем коммутируются шины 31 (выходы триггеров 11) и. соответствующие им разряды шины 33 (выход узла

13 приоритета). Этим осуществляется выделение принятым на обработку запросом соответствующего ему триггера 11 и анализ его состояния.

Единичный уровень на выходе триг" гера 19 разрешает запись по определенному импульсу. но шине 28 в соответствующий принятому запросу регистр 4 данных. Импульс- записи вырабатывается на одной из шин 30 группой элементов И 21. В группу входят Ю трехвходовых элементов И, два входа которых соединены с шинами 28 и выходом триггера 19, а третьи входы соединены с соответствующими разрядами шин 33.

Кроме того, единичное состояние триггера t9 запрещает повторный запуск ждущего генератора и разрешает обнуление счетчика 17 импульсов, соответствующим окончанию обработки запроса.

Использование предлагаемой системы доступа к памяти обеспечивает

11.

1.151974

12 доступ от любого процессора к любому участку памяти, что позволяет создавать высокопроизводительные алгоритмы, не ограниченные заранее установленным объемом блока памяти, с использованием обобщенных банков данных и наборов. унифицированных процедур.

Увеличение числа процессоров не сокращает доступного отдельному процессору объема памяти.

5 Таким образом, предлагаемая система доступа к памяти позволяет достичь большей производительности, имеет повышенную шивучесть и надешность.

115I974

1 )51974

1151974 зом зо

31ß _#_

Фиа4

ФиМ щцрцф Заказ 2325/З8 Тираж 710 Нодписное адддад шш дпатадт, г.удгорол, ул.проекткаа, а