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

 

Изобретение относится к вычислительной технике , в частности, к устройствам управления памятью. Цель изобретения - повышение плотности записи в оперативную память за счет выделения оптимального по размеру массива оперативной памяти, а при отсутствии массива требуемого размера - за счет выделения совокупности из минимального числа массивов. Устройство содержит первую 1 и вторую 2 группы регистров, блок 3 сортировки, третью группу регистров 4, первый 5, второй 6 и третий 7 регистры, генератор импульсов 8, первый 9 и второй 10 счетчики, сумматор 11, первый 12 и второй 13 элементы сравнения, первый 14, второй 15, третий 16 и четвертый 17 триггеры, первый 18, второй 19, третий 20 и четвертый 21 элементы И. 1 з.п. ф-лы, 3 ил.

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

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

РЕСПУБЛИН (19) (11) (5D4 G06 F 12 00 р . о;лЯ ;,(Л -, j, (., В,, I33

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

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

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

1 (21) 4395481/24-24 (22) 21.03.88 (46) 23.09.89. Бюл. ¹ 35 (72) В.И.Бенкевич (53) 681.325(088.8) (56) Авторское свидетельство СССР № 1213484, кл. С 06 F 13/00, 1984 .

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

Р 1298754, кл. G 06 F 12/00, 1985 . (54) УСТРОЙСТВО РАСПРЕДЕЛЕНИЯ ОПЕРАТИВНОЙ ПАМЯТИ (57) Изобретение относится к вычислительной технике, в частности к устройствам управления памятью. Цель ,изобретения — ловы(пение плотности

Ъ

2 записи в оперативную память эа счет выделения оптимального по размеру массива оперативной памяти, а при отсутствии массива требуемого размераэа счет выделения совокупности иэ минимального числа массивов. Устройство содержит первую 1 и вторую 2 группы регистров, блок 3 сортировки, третью группу регистров 4, первый 5, второй 6 и третий 7 регистры, генератор импульсов 8, первый 9 и второй 10 счетчики, сумматор 11,первый 12 и второй 13 элементы сравнения, первый 14, .второй 15, третий 16 и четвертый 17 триггеры, первый 18, второй 19, тртетий 20 и четвертый

21 элементы.,1 з.п. ф-лы, 3 ил.

3 150990

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

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

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

Устройство содержит первую 1 и вторую 2 группы регистров, блок 3 сортировки, третью группу регистров

4, первый 5, второй 6 и третий 7 ре- 20 гистры, генератор 8 импульсов, первый

9 и второй 10 счетчики, сумматор 11, первый 12 и второй 13 элементы сравнения, первый 14, второй 15, третий

16 и четвертый 17 триггеры, первый

18, второй 19, третий 20 и четвертый (2i элементы И и имеют группу 22 вхо- дов размеров массивов памяти, группу 23 входов начальных адресов массивов памяти, вход 24 размера тре- 30 буемого массива памяти, вход 25 запуска, группу адресных выходов 26, выход 27 числа выделенных массивов памяти, выход 28. начального адреса выделеннога массива памяти, первый

29 и второй 30 сигнальные выходы и выход 31 готовности.

Блок сортировки содержит элемент

И 32, триггер 33, ключ 34, группу 35 ячеек коммутации, а в каждой ячейке 40 первый 36 и второй 37 элементы И, триггер 38, ключ 39, элемент 40 сравнения, первый 41 и второй 42 коммутаторы. Блок сортировки имеет первую

43 и вторую 44 группы входов, вход 45

45 синхронизации, первый 46 и второй

47 выходы, Элемент 12 сравнения, элемент

И 20., регистр 6 и триггер 15 представ.ляют собой группу элементов для выделения оптимального по размеру массива памяти, т.е. массива, длина ко ТОрог 0 Ьi LTp H L 1 где L — размер запрашиваемого мас- сива памяти Су матор 11 регистры i55

4 и 7, элемент 13 сравнения, счетчик . . 10, элементы И 19. 21 и триггер 17 представляют собой группу элементов для выделения минимального числа массивов памяти в соответствии с запросом. Обе группы элементов работают одновременно.

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

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

Если код размера поступившего массива больше либо равен требуемому, то соответствующий ему начальный адрес записывается в регистр 6, а триггер 15 устанавливается в единичное состояние, сигнализируя о выделении памяти одним массивом, По окончании работы устройства в регистре 6 находится начальный адрес оптимального по размеру массива памяти.

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

На вход сумматора 11 последовательно поступают коды размеров массивов памяти, начиная с наибольшего, на вход первого регистра третьей группы регистров 4 — соответствующие им начальные адреса. Если суммарная длина поступивших массивов памяти меньше требуемой, то из j-го регистра 4, (j = 1,п-1) информация переписывает- " ся в (j+1)-й регистр 4, а в первый регистр группы регистров 4 записыва- ется начальный адрес поступившего массива памяти. Одновременно в счетчике 10 подсчитывается число массивов. Как только суммарная длина массивов превысит размер требуемого массива, запись начальных адресов прекращается. По окончании работы устройства в счетчике 10 хранится, двоичный код числа выделенных массивов N, а в первых N регистрах 4— начальные адреса выделенных массивов., Устройство работает следующим образом.

В исходном состоянии регистр 7, счетчики 9, 10 триггеры 14-17 и 33, 38 блока сортировки обнулены (цепи . обнуления не показаны). В регистры 1 по входам 22 записаны коды размеров свободных массивов памяти, в регистры 2 по входам 23 — начальные адреса массивов памяти, причем если некото11(,рый массив памяти занят, то в соответствующий регистр 1 записывается нулевой код. В регистр 5 по входу 24 записан код размера требуемого массива памяти. В исходном состоянии с первого выхода блока сортировки на вход сумматора 11 и элемента 12 сравнения поступает код размера максимального свободного массива памяти, а с второго выхода блока сортировки на вход первого регистра 4 третьей группы и на вход регистра 6 поступает соответствующий ему начальный адрес. Если код числа по первому входу элемента сравнения больше, либо равен, кода по второму входу, то на выходе элемента сравнения логическая единица. C приходом по входу 25 импульса запуска триггер 14 переходит в единичное состояние, элемент И 18 открывается и импульсы с генератора

8 импульсов поступают на вход счетчика 9, увеличивая его состояние на единицу. Если код размера поступившего массива памяти больше, либо равен, требуемого, то на выходе элемента 12 сравнения логическая "1", элемент И 20 открыт и импульс с генератора 8 импульсов переводит триггер

15 в единичное состояние, в регистр

6 записывается начальный адрес массива. В противном случае элемент И 20 закрыт; запись информации в регистр

6 не происходит. В исходном состоянии регистр 7 обнулен, на выходе элемента сравнения логический "0", элемент

И 21 закрыт, элемент И 19 открыт.

Первый импульс с генератора 8 импульсов через элемент И 1.9 записывает суммарную длину массива памяти в регистр 7, в регистр 4 записывается на чальный адрес массива памяти, состоя Iíèå счетчика 10 увеличивается на еди.—

I 1 ницу. Кроме того, импульс с генератора импульсов поступает на вход синхронизации блока сортировок и через время ь,, определяемое особенностью работы блока сортировки, на

его первом и втором выходах появляется соответственно код размера и начальный адрес очередного массива па-. мяти. В том случае, если к приходу очередного импульса с генератора импульсов суммарная длина массивов памяти, хранящаяся в регистре 7,больше, либо равна требуемой, на выходе элемента 13 сравнения логическая "1", элемент И 19 закрыт, запись информа50 на входы коммутаторов 42 поступают начальные адреса массивов памяти. Выделение максимального кода размера и сбответствующего ему начального ад- реса памяти осуществляется следующим, образом.

В каждой 8-й ячейке коммУтации (S = 1,п-7) на элементе 40 сравнения сравнивается код размера (8+1)-ro массива памяти с наибольшим из предыдущих S массивов. Если код по первоiaa0q 6 ции в ре> ис.тры 4, 7, счетчики 10 не прои зводится .

С приходом (и+1)-го по счету импульса на выходе переполнения счетчика 9 появляется импульс, который устанавливает в нулевое состояние триггер 14 и, тем самым, отключает генератор импульсов. Триггер 16 устанавливается в единицу, что сигнализирует о готовности устройства выдать информацию. Кроме того, если к моменту окончания работы суммарная длина массива не меньше требуемой, то на выходе элемента 13 сравнения логическая "1", элемент И 21 открыт и сигнал переполнения с выхода счетчика 9 устанавливает в единичное состояние триггер 17, что сигнализи20 рует о выделении совокупности массивов памяти. Устройство завершает работу, Таким образом, по окончании работы на выходах 29(30) возможна следующая

25 комбинация двоичных сигналов: 1(1) память выделена одним массивом, 0(i) выделена совокупность массивов, 0(0) — память не выделена, В первом случае начальный адрес

3р выделенного массива находится в ре-. гистре 6, который выдается по вьгходу

28.

Во втором случае по выходу 27 из счетчика 10 выдается двоичный код N числа выделенных массивов, начальные

35 адреса которых из первых N регистров

4 выделяются по выходам 26.

Блок сортировки (фиг. 2) работает следующим образом.

40 В исходном состоянии триггеры 33 и 38 обнулены с их инверсных выходов снимается сигнал логической "1", который открывает ключи 34 и 39.

IIn первой группе входов 43 коды

45 размеров массивов памяти через открытые ключи 34 и 39 поступают на входы элементов 40 сравнения и коммутаторов 41, по второй группе входов 44

1509909 му входу элемента 40 сравнения больше, либо равен, кода по второму входу, то ца выходе элемента 40 сравне-! ния логическая "1", коммутаторы 41 и 42 открыты по первому информационному входу. В противном случае коммутаторы открыты по второму информационному входу. Таким образом, на выходе первого коммутатора 41 S-й ячейки 10 коммутации всегда присутствует код максимального из первых (S+1) массивов памяти, на выходе второго коммутатора 42 — соответствующий ему начальный адрес. В результате последо- 15 вательного сравнения и коммутации на выходе первого коммутаторы 41 (n-1)й ячейки коммутации появляется код размера максимального массива памяти, на выходе второго коммутато- 20 ра 42 — соответствующий ему начальный адрес.

Появление на выходе элемента сравнения S-й ячейки коммутации логической "1". говорит о том, что, возможно 25 код на (3+1)-м входе первой группы входов 43 является максимальным. Если на выходе элемента 40 сравнения

S-й ячейки коммутации сигнал Х - = 1, а сигнал = Х„= 0 (n 1h 2 - S) 30 то на (8+1)-м входе первой группы входов 43 присутствует максимальный код, который подлежит исключению из дальнейшего рассмотрения с приходом синхроимпульса по входу 45. Группа элементов И 32, 36, 37 обеспечивает определение и исключение максимального выделенного кода. Это осуществляется следующим образом.

С выхода элемента И 37 S-й ячейки коммутации на второй вход элемента

И 36 (S-1)-й ячейки коммутации поступает сигнал, определяемый логической функцией Й = Х Х,... Х„».,„, где 45

Х вЂ” инверсия сигнала на выходе элемента сравнения в S-й ячейке коммутации. ЕслиХз1 = 1 и f =1, то с приходом синхроимпульса с входа 45 через элемент И 36 (S-1)-й ячейки триггер 38 переходит в единичное состояние, потенциал логического "0" с его инверсного выхода закрывает ключ 39 и S-й массив памяти из дальнейшего рассмотрения исключается.

Через время c = (n-1) (Т . + Т,щ ), где Т,, Т щ щ — время пе ре ключения элемента сравнения и коммутатора соответственно, на выходе последней ячейки коммутации появляется код размера и начальный адрес максимального из оставшихся массивов памяти. (Если f = 1, то синхроимпульс через элемент И 32 устанавливает в единичное состояние триггер

33, ключ 34 закрывается).

Эпюры на фиг. 3 поясняют работу блока сортировки и устройства в целом, где I — момент поступления (обновления) информации на входах блока сортировки, II — момент появленйя кода размера и начального адреса массива памяти, на выходах блока сортировки; III — момент прихода синхроимпульса на синхровход блока сортировки.

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

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

1. Устройство распределения оперативной памяти, содержащее первую и вторую группы из и регистров (n— число анализируемых массивов оперативной памяти), три регистра, генератор импульсов, первый и второй триггеры, первый, второй и третий элементы И, два счетчика, два элемента сравнения, сумматор, причем информационные входы К-х регистров первой и второй группы (К = 1,n) являются соответственно входом размера и входом начального адреса К-. ro массива оперативной памяти устройства, вход размера требуемого массива устройства соединен с информационным входом первого регистра, выход которого соединен с первым входом первого элемента сравнения, вход запуска устройства соединен с входом установки в единичное состояние первого триггера, выход которого соединен с первым входом первого элемента И, второй вход которого соединен с выходом генератора импульсов, выход первого элемента И соединен со счетным входом первого счетчика, счетный вход второго счетчика соединен с выходом второго элемента И, выход первого элемента сравнения соединен с первым входом третьего элемента И, первый вход второго элемента сравнения сое1509909 динен с первым входом сумматора, вход установки в единичное состояние второго триггера соединен с входом записи второго регистра, о т л и ч а ю— щ е е с я тем, что, с целью повышения плотности записи в оперативную память за счет выделения оптимального триггера является выходом готовности устройства, выход начального адреса выделенного массива памяти которого соединен с выходом второго регистра,. выход данных второго счетчика является выходом числа выделенных массивов устройства.

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

15

20 входом третьего регистра, выход которого соединен с первым входом второго 25 элемента сравнения, второй вход которого соединен с выходом первого регистра, выход второго элемента сравнения соединен с первым входом чет1 . второго элемента И, выход которого соединен с входами записи третьего регистра и регистров третьей группы, выход М-го регистра третьей группы соединен с информационным входом (М+1)-го регистра третьей группы (Мпо

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

45 первого триггера, с входом установки

50 в единичное состояние третьего триггера и вторым входом четвертого элемента И, выход которого соединен с входом установки в единичное состояние четвертого триггера, выход кото55 рого является первым сигнальным выходом устройства, второй сигнальный выход которого соединен с выходом второго триггера, выход третьего вертого элемента И и инверсным входом 30

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

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

К-й ячейки коммутации (К = 1,п-2) соединен с вторым входом первого коммутатора (К+1)-й ячейки коммутации, выходы первого и второго коммутаторов (п-1)-й ячейки коммутации являются соответственно первым и вторым выходами блока сортировки, прямой вход второго элемента И К-й ячейки соединен с выходом, второго элемента И (К+1)-й ячейки коммутации причем прямой вход второго элемента

И (n-1)-й ячейки коммутации соединен с входом логической единицы, выход второго элемента И первой ячейки коммутации соединен с вторым входом

1509909

Составитель А.Иванов

Техред МвДидык

Корректор В. Кабаций

Редактор 0 ° Головач

Подписное

Заказ 5814/47 Тираж 668

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

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

Производственно-издательский комбинат "Патент", г.ужгород, ул. Гагарина, 101 элемента И, информационный вход ключа соединен с первым входом первой группы входов блока сортировки, информационный вход ключа j-й ячейки коммутации (j = 1,п-1) соединен с (j+1)"м входом первой группы входов блока сортировки, первый информационный вход второго коммутатора 1-й ячейки коммутации соединен с (j+1)-м входом второй группы входов блока сортировки, второй информационный вход второго коммутатора первой ячей5 ки коммутации соединен с первым входом второй группы входов блока сортировки, выход второго коммутатора

К-й ячейки коммутации (К = 1,п-2) соединен с вторым входом второго коммутатора (К+1)-й ячейки коммутации.