Устройство для адресации памяти

 

Изобретение относится к области вычислительной техники, в частности к устройствам управления ЦВМ, и может быть использовано для построения устройств распределения памяти в вычислительных комплексах. Целью изобретения является расширение области использования за счет работы с блоками памяти, объем каждого из которых меньше требуемого. Устройство содержит группу 1 элементов сравнения, блок 2 элементов сравнения, дешифратор 3, регистр 4, шифратор 5, первый элемент И 6, элемент 7 задержки, элемент ИЛИ 8, блок 9 групп элементов И, второй элемент И 10, группу 11 элементов И, группу 12 блоков элементов И, группу 13 элементов ИЛИ, блок 14 объединения. Имеющийся в устройстве блок 14 объединения позволяет, выделить под запрос требуемый объем памяти путем объединения пары свободных массивов. 2 з.п. ф-лы, 3 ил. с J11dT92t 25Z6Z12m 6 И ШИП го 15 фиг.1

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

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

РЕа1УБЛИН (19) (11) (so 4 С 06 F 12/00

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

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

165с425862788 >1

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 4022164/24-24 (22) 14.02.86 (46) 07.08.87. Бюл. 9 29 (72) M.N. Зарецкий, В.В. Мазаник, С.В. Ефимов и В.Д, Костюченко (53) 681.3(088.8) (56) Авторское свидетельство СССР

У 1213484, кл. G 06 F 13/00, 1984.

Авторское свидетельство СССР .

У 1290335, кл. G 06 F 13/00, 1985. (54) УСТРОЙСТВО ДЛЯ АДРЕСАЦИИ ПАМЯТИ (57) Изобретение относится к области вычислительной техники, в частности к устройствам управления ЦВМ, и может быть использовано для построения устройств распределения памяти в вы числительных комплексах. Целью изобретения является расширение области использования за счет работы с блоками памяти, объем каждого из которых меньше требуемого. Устройство содержит группу 1 элементов сравнения, блок 2 элементов сравнения, дешифратор 3, регистр 4, шифратор 5, первый элемент И б,,элемент 7 задержки, элемент ИЛИ 8, блок 9 групп элементов

И, второй элемент И 10 группу 11 элементов И, группу 12 блоков элементов И, группу 13 элементов ИЛИ, блок

14 объединения. Имеющийся в устройстве блок 14 объединения позволяет,. выделить под запрос требуемый объем памяти путем объединения пары свобод- ных массивов. 2 з.п. ф-лы, 3 ил.

1 132

Изобретение относится к вычисли. тельной технике, в частности к устройствам управления ЦВМ.

Целью изобретения является расширение области использования за счет работы с блоками памяти, объем каждого из которых меньше требуемого.

На фиг.1 представлена структурная ,схема устройства, на фиг.2 — схема блока объединения; на фиг.3 — схема коммутатора.

Устройство содержит группу 1 элементов сравнения, блок 2 элементов сравнения, дешифратор 3, регистр 4, шифратор 5, первый элемент И 6, элемент 7 задержки, элемент ИЛИ 8, блок

9 групп элементов И, второй элемент

И 10, группу 11 элементов И, группу

12 блоков элементов И, группу 13 элементов ИЛИ, блок 14 объединения, вход 15 запроса, вход 16 требуемого размера массива, вход 17 признака освобождения, вход 18 размера освобождаемого массива, вход 19 адреса освобождаемого массива, выход 20 признака очистки, выходы признака наличия 21.и признака отсутствия 22 требуемого массива, выход 23 начального адреса выделяемого массива, входы начального адреса 24 и сдвига обращения к памяти 25, выходы модифи.цированного начального адреса 26 и сдвига модифицированного обращения к памяти 27.

Блок объединения содержит (фиг.2) коммутатор 28, с первого по третий сумматоры 29-31, первый элемент 32 сравнения, второй 33, первый 34, третий 35, четвертыи 36, пятый 37 регистры,с первого по третий элементы И-ИЛИ 38-40, первый 41, второй 42 элементы ИЛИ, первый элемент 43 задержки, триггер 44, второй элемент

45 сравнения, пятый 46, четвертый

47 сумматоры, третий элемент ИЛИ 48, четвертый, седьмой, шестой и пятый лементы И-ИЛИ 49-52, третий элемент

3 сравнения, второй 54,третий 55 элементы задержки; етвертый элемент

ИЛИ 56> элемент И 57, входы адресов

58 и объемов 59 свободных массивов, входы признаков отсутствия 60 и наличия 61 целого массива требуемого размера, вход 62 начального адреса целого массива требуемого размера, выходы признака наличия 21 признака отсутствия 22, начального адреса

23 B объема 63 выделяемого массива, 8820 2 признака выделения объема 64, началь,ного адреса 24 и сдвига обращения к памяти 25, модифицированных начального адреса 26 и сдвига обращения к

*амяти 27, входы признака освобождения 17, адреса 18 и объема 19 освобождаемого массива, выходы признака отказа 65, ацреса 66 и объема 67 освобождающегося массива.

Коммутатор содержит формирователь

68 импульсов (фиг.3), элемент 69 задержки, блок пар групп элементов И 70, первую 71, вторую 72 группы элементов ИЛИ, триггер 73, первую 74рвторую

75 группы элементов И, входы объемов

58 и адресов .59 свободных массивов, входы запуска 76, и останова 77,, выходы первого 78 и второго 79 свободных массивов, выход 80 отсутствия объединенного массива.

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

Регистр 4 хранит признаки занятост ". листов памяти, выделенных под ранее обслуженные запросы, шифратор 5 формирует коды начальных адресов и размеров свободных массивов памяти, а также выдает на выход 20 признак

З0 очистки памяти в случае, когда число свободных массивов превышает опреде1 ленный порог и, следовательно, они имеют малые размеры. На группе 1 элементов сравнения сравниваются размеры всех свободных массивов с требуемым размером, поступившим на вход 16 одновременно с признаком запроса на входе 15.

Результат этого сравнения и резуль4> тат сравнения свободных массивов между собой на блоке 2 поступают на блок 9, где формируются признаки выбора одного из каждой пары массивов под запрос. Эти признаки поступают на груп45 пу 11 элементов И, на выходе которой появляется сигнал выбора одного массива из всех свободных (в случае превьппения какого-либо размера массива над требуемым).

Адрес выбранного массива проходит через соответствующий блок группы 12 элементов И, группу 13 элементов ИЛИ на выход 62 блока 14 объединения.

Сигнал с прямого выхода элемента

ИЛИ 8 проходит через открытый задержанным на элементе 7 задержки сигналом запроса элемент И 10 на вход 61 блока 14. Этот сигнал означает наличие свободного массива нужного размез 13288 ра — иначе выдается сигнал с инверсного выхода элемента ИЛИ 8 на вход

60 блока 14.

Адрес выделенного массива и его размер проходят через блок 14 вместе

В с признаком выделения массива на дешифратор 3, который выдает сигналы занятия листов памяти на регистр 4.

При освобождении задачей ресурса памяти коды признака отказа 17, размера массива 18 и адреса 19 через блок

14 поступают на дешифратор 3, в котором вырабатываются сигналы освобождения листов памяти, поступающие на ре- 16 гистр 4.

Если не найдено требуемого массива (целого), то начинает работать собственно блок 14 объединения. На входы

58 и 59 коммутатора 28 поступают коды 20 объемов, адресов свободных массивов с выходов шифратора 5. Исходное положение триггера 44 единичное. Сигнал

60 отсутствия целого массива проходит через открытый элемент И 57 на вход 2б

76 коммутатора 28 и запускает его.

На первой и второй группе выходов комкоммутатора 28 по очереди появляются сочетания кодов адресов и объемов каждых двух свободных массивов. Сумма объемов с выхода сумматора 29 поступает на элемент 32 сравнения, где сравнивается с требуемым объемом с входа 16.

Одновременно вычисляются адрес

35 конца первого массива на сумматоре

30 и величина объема, которую надо выделить из второго массива под запрос, на вычитающем сумматоре 31.

Если сумма каких-то двух объемов не меньше требуемого, то элемент 32 сравнения выдает единичный сигнал, по которому триггер 44 переключается в "0", остановится перебор пар массивов на выходах коммутатора 28, что приводит к появлению на этих выходах нулевых кодов, нулевой суммы на выходе сумматора 29 и переключению выхода элемента 32 в "0" через определенное время, на регистры 33 и 37 принимаются коды адреса первого массива, адреса второго массива, объем первого массива, выделяемого числа листов из второго массива и адрес конца первого массива соответственно.

Кроме того, через элементы И-ИЛИ

38 и 39 на дешифратор 3 проходят коды адреса 23 и объема 63 первого

20 массива и признак выделения массива

64, а также выдается сигнал ответа устройства 21. Через время, необходимое для отработки кодов в дешифраторе 3, сигнал с выхода элемента 43 задержки выдает на выходы 23,63,64 коды адреса второго массива. Дешифратор 3 отрабатывает и эти коды, переключая соответствующие разряды регистра 4 в "0".

В случае отсутствия пары массивов с требуемым суммарным объемом по окончании переобора в коммутаторе 28 появляется сигнал на выходе 80, проходящий через элемент И-ИЛИ 40 на выход 22 устройства как признак отказа в запросе. Если при обслуживании других запросов появляется сигнал на входе 60, то, поскольку триггер 44 выключен, элемснт И 57 закрывается, а элемент И 40 по сигналам на третьем и четвертом входах выдает признак отказа.

При освобождении каждого массива поступивший адрес и хранящийся в регистре 33 адрес объединенного массива сравниваются на элементе 53 сравнения. При несовпадении адресов на выходах 66, 67 элементами И-ИЛИ 52 и 51 выдаются коды адреса и объема с входов 18 и 19 (а также признак освобождения с входа 17 через элемент ИЛИ 56 на выход 65) и далее на дешифратор 3. При совпадении адресов сначала выдаются коды объема и адреса первого массива, признака освобождения, а затем через время задержки на элементах 54 и 55 задержкикоды объема и адреса второго массива и признак освобождения. Кроме того, триггер 44 включается, что означает готовность устройства к выделению объединенного массива очередному запросу.

При обращении к памяти считается, что выделенный объем непрерывен.

Для модификации адреса обращения с целью обеспечения правильности обращения используются элементы 45-50.

На входы 24 и 25 поступают базовый адрес (номер первого листа массива) и сдвиг обращения (номер листа в массиве). Если идет обращение к объединенному массиву, то элемент 45 сравнения выдает нулевой сигнал.

Далее анализируют, в каком (первом или втором) массиве находится конкретный адрес обращения, который

5 13288 с выхода сумматора 46 поступает на вычитающий сумматор 47 вместе с адресом конца первого массива с регистра 37. Если адрес обращения находится в первом массиве, что определяется знаковым разрядом разности адресов, то выход элемента ИЛИ 48 пропускает через элементы И-ИЛИ 49 и 50 исходные коды адреса и сдвига (то же будет, если идет обращение не к объединенно- Ю му массиву) на выходы 26 и 27. Если адрес обращения находится во втором массиве из тех, которые выделены и объединены, то на выходе 27,26 выдяются коды начала второго массива 15 с регистра 34 .и сдвига во втором массиве с сумматора 47, равного разности полного адреса обращения и адреса конца первого массива.

Коммутатор 28 работает следующим 20 образом. Сигнал запуска потенциального вида на входе 76 поступает на формирователь 68, с выхода которого импульсный сигнал устанавливает триггер 73 в "1" и запускает элемент 69 задержки, выходные сигналы которого по очереди открывают пары групп элементов И 70 блока. Коды объемов и адресов двух выбранных свободных массивов с выхода одной из пар групп 30 элементов И 70 блока проходят через группы элементов KIH 71, 72 и И 73, 74 на выходы 78 и 79. Таким образом, на выходах 78 и 79 появляются коды пары массивов, на выходе 78 — первого 35 массива, на выходе 79 — с второго по

К-го массива, затем на выходе 78— второго, а на выходе 79 — с третьего по К-й и т.д., пока сигнал с входа

77 не переключит триггер 73 в "0", 40 который своим выходным сигналом закроет группы элементов И 74 и 75. После окончания перебора всех пар массивов с M+1-го выхода элемента 69 задержки выдается сигнал окончания 45 перебора.

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

1. Устройство для адресации памяти, содержащее группу элементов сравнения, блок элементов сравнения, дешифратор, шифратор, регистр„ элемент ИЛИ, элемент, задержки, первый, второй элементы И, блок групп элемен- 55 тов И, группу элементов И, группу блоков элементов И, группу элементов

ИЛИ, причем выход дешифратора через

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

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

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

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

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

ИЛИ, четвертым входом первого и третьим входом второго элементов И-ИЛИ, выход адреса второй группы выходов коммутатора соединен с информационным входом второго регистра и первым входом второго сумматора, выход объема памяти второй группы выходов коммутатора соединен с вторыми входами первого, второго сумматоров, первым входом третьего сумматора и информационным входом третьего регистра, третий вход второго сумматора соеди15

8 нен с шиной единичного потенциала устройства, шестой вход блока соединен с вторыми входами первого элемента сравнения и третьего сумматора и четвертым входом второго элемента И-ИЛИ, выходы третьего, второго сумматоров соединены с информационными входами четвертого, пятого регистров соответственно, выход первого регистра подключен к пятому входу первого элемента И-ИЛИ и первым входам четвертого, пятого элементов

И-ИЛИ, выход второго регистра соединен с шестым входом первого элемента И-ИЛИ, первым входом второго, третьего элементов сравнения и вторым входом пятого элемента И-ИЛИ, выход третьего регистра соединен с пятым входом второго элемента И-ИПИ и первым входом шестого элемента И-ИЛИ, выход четвертого регистра соединен с шестым входом второго элемента

И-ИЛИ и вторым входом шестого элемента И-ИЛИ, выход пятого регистра соединен с первым входом четвертого сумматора, вшходы модуля и знакового разряда которого соединены соответственно с первыми входами седьмого элемента И-ИПИ и третьего элемента

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

И- ИЛИ, десятый вход блока соединен с четвертым входом четвертого элемента И-ИЛИ, вторым входом второго элемента сравнения и первым входом пятого сумматора, одиннадцатый вход блока соединен с четвертым входом седьмого элемента И-ИЛИ и вторым входом пятого сумматора, выход которого соединен с вторым входом четвертого сумматора, выход первого элемента

ИЛИ соединен с вторым входом второго элемента ИЛИ, выходы блока с первого по десятый соединены соответственно с выходами четвертого, седьмого, третьего элементов И-ИЛИ, первого

9 13288 элемента ИЛИ, первого,, второго эле. ментов И-ИЛИ, второго элемента ИЛИ, четвертого элемента ИЛИ, шестого и пятого элементов И-ИЛИ, единичный выход триггера соединен с вторыми входами элемента И и третьего элемента И-ИЛИ, нулевой выход триггера соединен с третьим входом третьего элемента И-ИЛИ, четвертый 1о вход которого соединен с третьим выходом коммутатора, прямой выход третьего элемента сравнения соединен с единичным входом триггера, четвертыми входами пятого, шестого элемен- 1В тов И-ИЛИ и через третий элемент задержки с пятыми входами пятого, шестого элементов И-ИЛИ, инверсный выход третьего элемента сравнения соединен,с шестыми входами пятого, шестого элементов И-ИЛИ.

3. Устройство по п.1, о т л и ч а ю щ е е с-я тем, что коммутатор содержит формирователь импульсов, элемент задержки, блок пар групп эле- 25 ментов И, первую, вторую группу элементов ИЛИ, первую, вторую группы элементов И и триггер, причем третий вход коммутатора через формирователь импульсов подключен к входу элемента gp задержки и к единичному входу триггера, нулевой вход которого соединен

Я 58

20 с четвертым входом коммутатора, выход триггера соединен с первыми входами элементов И первой и второй групп, выходы элементов И первой, второй групп соединены соответственно с первой, второй группами выходов коммутатора, вторые входы элементов И первой, второй групп с.оединены соответственно с выходами элементов ИЛИ первой, второй групп, выходы с 1-го по М-й элемента задержки подключены к первым входам элементов И с 1-го по М-ю пар групп блока, выходы элементов И первых и вторых групп блока подключены к входам элементов ИЛИ первой, второй группы соответственно, P-e (Р=1,k) — максимально возможное число свободных объемов памяти), входы первой, второй групп входов коммутатора соединены с вторыми входами элементов И первых групп С-х пар блока (С = С С

P-(P

1 Яй

С„ (k i)+1, С,— - (k i)) и с вто =1 рыми входами элементов И вторых групп

В=х пар блока

9-1- Q

В =, (k i)+Âr, В, = 1,Р-1), 1

М+ 1-й выход элемента задержки М =

=,,(k-i) соединен с третьим выходом

1- r коммутатора.

6! 62

+ 7 б5

Составитель С. Бурухин

Редактор Н, Гунько Техред И.Попович Корректор И.Муска

Заказ 3489/51 Тираж 672 Подписное

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

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

-с .Производственно.-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4