Устройство для выбора замещаемого элемента Советский патент 1988 года по МПК G06F11/20 

со о: si

1 13

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

Цель изобретения - упрощение уст- ройства за счет уменьшения количества оборудования.

На фиг.1 представлена блок-схема устройства для выбора замещаемого элемента, у которого на фиг.2 - функциональная схема кодопреобразователя; на фиг.З - функциональная схема блока сравнения; на фиг.4 - функциональная схема блока управления; на фиг.5 - функциональ- ная схема счетчика; на фиг.6 - временные диаграммы работы устройства.

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

Блок 4 сравнения выполнен на схемах 22-25 сравнения и элементе ИЛИ 26, выход которого обозначен W.

Блок управления 5 содержит элементы И 27-30, элемент ИЛИ 31, выход ко- торого обозначен С, и два RS-тригге- ра 32 и 33, прямые выходы которых обозначены соответственно S, и S.

Второй ВХОД1 кодопреобразователя 1 соединен с информационным входом 7 устройства, а выход кодопреобразователя 1 - с вторым входом памяти 2, третий вход которого подключен к адресному входу 8 устройства, четвертый вход - к первому управляемому входу 11 устройства, а выход - к первому входу регистра 3, выход которого соединен с первым входом кодопреобразователя 1 и первым входом блока 5 управления j второй вход которого связан с вторым входом регистра 3, первым входом памяти 2 и входом 9 синхронизации устройства, третий вход блока 5 управления соединен с вторым управ

Q

5 0

5 о

0

5

5

72

ляющим входом 12 устройства, а выход- с первым входом счетчика 6, второй вход которого подсоединен к входу 10 случайного числа устройства, а выход- к второму входу блока 4 сравнения и выходу 13 устройства.

Кодопреобразователь 1 предназначен для формирования нового кода хронологии использования элементов в соответствии с кодом номера элемента по входу 7 устройства и текущим кодом хронологии с выхода регистра 3, причем вторые входы схем 14-16 сравнения соединены с информационным входом 7 устройства и первой группой выходов кодопреобразователя 1, а первые входы - соответственно с первой, второй и третьей группами выходов регистра 3. Первый выход схемы 14 сравнения подсоединен к второму входу группы элементов И-ИЛИ 19, третий вход которой соединен с вторым (инверсным) выходом схемы сравнения 14, первым входом элемента И 18 и первым входом элемента И 17, первый выход которого связан с вторым входом группы элементов И-ИЛИ 20,.третий вход . которой подключен к второму (инверсионному) выходу элемента И 17, вто- цой вход которого соединен с инверс- ным выходом схем 15 сравнения и с вторым входом элемента И 18, первый выход которого связан с вторым входом группы элементов И-ИЛИ 21, третий вход которой подключен к второму (инверсному) выходу элемента И 18, тре-. тий вход которого соединен с инверсным выходом схемы 16 сравнения. Первые входы групп элементов И-ШШ 19 и 20 соединены с второй группой выходов регистра 3, четвертый вход группы элементов И-ИЛИ 19 - с первой группой выходов.регистра 3, третья группы выходов которого связана с четвертым входом группы элементов И-ИЛИ 20 и первым входом группы элементов , И-ИЛИ 21 , четвертЕлй вход которой подсоединен к четвертой группе выходов регистра 3. Группа выходов кодопреобразователя 1 соединенная с входом 7 устройства, и грзшпы выходов групп элементов И-ИЛИ 19-21 соответственно соединены с вторым входом памяти 2.

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

313

ресу, поступающему с адресного входа 8 устройства, соединенного с третьим входом памяти 2, второй вход которой связан с группами выходов кодопреобразователя 1. Первьй вход памяти 2 , соединен с выходом СИ2 входа синхронизации 9 устройств, и является входом записи, четвертый вход памяти 2 подключен к первому управляющему входу 11 устройства и является входом разрешения записи, а выход памяти 2 со-, единен с первым входом регистра 3.

Регистр 3 предназначен для хранения текущего состояния (кода) хронологии выбранной группы элементов, причем первый вход регистра 3 соединен с выходом памяти 2, второй вход - с выходом СИ1 входа 9 синхронизации устройства, а выход - с первым вхо- дом кодопреобразователя 1 и первым входом блока 4 сравнения, причем все разряды выхода регистра 3 разбиты на группы входов таким образом, что если в наборе из m элемейтов ведется хронология использования п элементов (), то число групп выходов регистра 3 равно п, а число разрядов в группе равно llogjmL и для случая m « 8 и п 4 имеются следовательно,

4группы выходов, по 3 разряда в каждой группе.

Блок 4 сравнения предназначен для сравнения содержимого счетчика 6 с кодами групп выходов регистра 3, причем первые входы схем 22-25 сравнения соединены соответственно с первой, второй, третьей и четвертой группами выходов регистра 3, вторые входы схем сравнения 22-25 подключены к выходу счетчика 6,а выходы схем 22-25 сравнения соединены соответственно с первым, вторым, третьим и четвертым входами элемента ИЛИ 26, выход которого соединен с первым входом блока

5управления.

Блок 5 управления предназначен для формирования сигналов синхронизации и управления работой счетчика 6, причем S-вход RS-трйггвра 33 соединен с- S-входом RS-триггера 31, вторым входом элемента ИЛИ 31, вторым управляющим входом 12 устройства, и вторыми (инверсными) входами элементов И 27 и 28, первые входы которых связаны соответственно с выходами СИ2 и СИ1 входа 9 синхронизации устройства, выход элемента И 28 соединен с R-входом RS-триггера 32, выход S1

0

5

0 5 0

5

0

5

О

5

которого подключен к соответствующему входу счетчика 6, вход S2 которого соединен с соответствующим выходом RS-триггера 33, R-вход которого связан с выходом элемента И 30, второй вход которого соединен с выходом элемента И 27 и входом элемента И 29, первый вход которого подсоединен к первому (инверсному) входу элемента И 30 и выходу W блока 4 (фиг.З), а выход элемента И 29 соединен с первым входом элемента ИЛИ 31, выход с которого соединен с соответствующим входом счетчика 6.

Счетчик 6 предназначен для получения номера замещаемого элемента и может быть реализован, например, на элементах 500ИЕ136, причем входы Д1, Д2 и ДЗ счетчика 6 соединены соответственно с разрядами входа IО случайного числа устройства, синхровход С счетчика 6 связан с соответствующим выходом блока 5 управления, выходы которого соединены с соответствующими входами счетчика 6, а выход L счетчика 6 подключен к соответствующему входу блока 4 сравнения и выходу 13 устройства.

Устройство для выбора замещаемого элемента может быть подключено к процессору ЭВМ, например, к его буферной (КЭШ) памяти для определения номера замещаемого блока в колонке при частично-ассоциативной организации буферной памяти или к буферу быстрой переадресации (TLB) для определения номера замещаемой записи буфера при страничном сбое в системе с виртуальной памятью. Поэтому все внешние управляющие сигналы, сигналы синхронизации, адреса памяти 2, номер используемого элемента с входа 7 поступают от процессора. Выход 13 устройства подается в процессор. Источником случайного числа, поступающего по входу 10 устройства, может служить группа разрядов некоторого регистра процессора, обновляющегося с достаточной частотой.

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

В устройстве ведется хронология использования группы из п (п т) наиболее часто используемых (активных) элементов набора из m элементов. Наименее активными (наиболее давно использовавшимися) считаются остальные т-п элементов данного набора и

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

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

2и регистром 3. Элементам набора присваиваются номера от О до т-1 . Двоичный код номера элемента имеет разрядов (для m 8 имеет

3разряда. Поскольку хронология ведется для п элементов,то разрядность слоба памяти 2, равная разрядности регистра 3, составляет п-Hog mГ разрядов и для m 8 и п 4 она равна 12 разрядам. Эти разряды разбиваются на 4 группы (п 4) по 3 разряда Glog 8Г) в каждой, причем код в разрядах первой группы определяет номер наиболее активного (последнего использовавшегося) элемента набора, код в разрядах второй группы - номер элемента, использовавшегося перед наиболее активным, и т.д.; наконец, код

в разрядах четвертой группы - номер наименее активного (наиболее давно использовавшегося) элемента в группе из четырех наиболее активных элементов данного набора. Соответственно разряды регистра 3 разбиты на 4 группы разрядов, причем код в разрядах первой группы определяет номер пос- . леднего использовавшегося элемента набора, а код в разрядах четвертой группы - номер наиболее давно использовавшегося элемента группы из четы рех элементов.

Память 2 хранит состояние (коды) хронологии групп элементов нескольких наборов элементов. Хронология группы элементов требуемого набора элементов выбирается по номеру данного набора, поступающему с адресного входа 8 устройства на третий вход памяти 2. Выбранное слово памяти 2 заносится в регистр 3 по импульсу СИ1, поступающему с входа 9 синхронизации устройства на первый вход памяти 2.

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

0

15

0

30

25

0

45

35

50

55

вавшихся элементов набора из восьми элементов.

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

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

Пусть в группу, составленную из четырех наиболее активных элементов набора из восьми элементов с номерами от О до 7 входят элементы 0,2,3,6 и хронология их использования такова: 2; 6; 0; 3. При этом в такой записи номер самого активного элемента группы занимает крайнее левое место, номер следующего по активности элемента указан вторым слева и т.д., а номер самого неактивного элемента в группе указьшается в крайней правой позиции. Таким образом, наиболее активный элемент в группе - 2, наименее активный - 3. Слово памяти 2, определяющее хронологию использования данной группы элементов, принимается по импульсу СИ1 в регистр 3, разрядьг первой группы выходов которого содержат код 2, разряды второй группы, выходов - код 6, разряда третьей группы выходов - код О, разряды четвертой группь выходов В4 - код 3V

Пусть на второй код кодопреобразователя 1 (фиг.1) с информационного

входа 7 устройства поступает 3-разрядный код номера используемого элемента, равный 0. Тогда (фиг.2) три разряда первой группы выходов кодопреобразователя 1 содержат новый код наиболее активного элемента, равный О. На первом выходе, схемы 14 сравне ния имеется сигнал О, свидетельствующий о том, что пришедший код (О) не сравнился с кодом наиболее активного элемента в старой хронологии (2). Из этого следует, что активность элемента 2 в новой хронологии должна быть меньшей, чем в старой. На втором (инверсном) выходе схемы сравнения 14 имеется сигнал и на выходах группы элементов И-ИЛИ 19 оказьшаются разряды первой группы выходов регистра 3. Таким образом, код в трех разрядах второй группы выходов кодопреобразователя 1 становится равным 2. На вьпсоде (инверсном) схемы 15 сравнения имеется сигнал

Выходы элемента И 18 поступают на .входы группы элементов И-ИЛИ 21, и на ее четвертых выходах имеются разряды четвертой группы выходов регистра 3 т.е, код в разрядах четвертой группы выходов кодопреобразователя 1 равен 3. Таким образом, новая хронология имеет вид 0; 2; 6; 3.

Q Пусть на второй вход кодопреобразователя 1 с информационного входа 7 устройства поступает код номера используемого элемента, равный 5. Способом, описанным выше, на выходах

5 кодопреобразователя 1 при исходной хронологии 0; 2; 6; 3 оказьгоаются .соответственно коды 5; 0; 2; 6. Элемент с номером 3 переходит в группу из четырех наименее активных элемен0 тов.

Случайный выбор элемента для замещения среди группы из m-n наименее активных элементов набора из m элементов осуществляется блоком 4 срав

Изобретение относится к области вычислительной техники и предназначено для выбора из имеющегося набора элементов того, который должен быть замещен другим. При этом выбор замещаемого элемента из набора, состоящего из m элементов, производится случайньм образом из группы га-п наиболее давно использовавшихся элементов данного набора, для которых в отличие от группы из п наиболее часто исполь- зуемьпс элементов () не ведется хронологии их использования. Изобретение может быть использовано в ЭВМ и вычислительных системах, вычислительных устройствах и приборах цифровой автоматики. Цель изобретения - уменьшение количества оборудования. Устройство .содержит кодопреобразователь 1, память 2, регистр 3, счетчик 6, блок 5 управления и блок 4 сравнения. Устройство обеспечивает выбор замещаемого элемента среди тех m-n элементов, для которых не ведется . хронология их использования, и позволяет сократить число каскадов кодопреобразователя и разрядность слова памяти и регистра. 6 ил. с 5 (Л

М, свидетельствующий о несравнении 25 нения, блоком 5 управления и счетчипришедшего кода О с кодом 6 в разрядах второй группы выходов регистра 3 и, следовательно, на первом выходе элемента И 1 7 присутствует сигнал 1, а на втором (инверсном) выходе 30 шихся элементов данного набора, сосэлемента И 17 - сигнал О. Это означает, что КОД номера используемого элемента, который в новой хронологии самый активный, не Ьовпал ни с кодом номера первого, ни с кодом номера второго по активности элемента в старой хронологии, следовательно, активность элемента 6 должна быть понижена. Выходы элемента И 17 поступают на входы трёх элементов И-ИЛИ из группы 20, на выходах этой группы имеются разряды второй группы выходов регистра 3, т.е. код в разрядах третьей группы.выходов кодопреобразователя 1

станет равным 6. На выходе (инверс- 45 пульса СИ1 до переднего фронта сленом) схемы сравнения 16 присутствует дующего СИ1. По переднему фронту

сигнал О, который свидетельствует

о сравнении пришедшего по входу 7

устройства кода О с кодом О в

разрядах третьей группы выходов реги- gQ , т.е. код П приема информасигнала Е RS-триггеры 32 и 33 устанавливаются в единичное состояние и определяют состояния сигналов и

стра 3. Тогда на первом выходе элемента И 18 имеется сигнал О, а на втором (инверсном) выходе элемента И 18 - сигнал 1. Это означает, что код номера используемого элемента содержится среди имеющихся четырех наиболее активных элементов и, кроме того, активность оставшегося элемента (элементов) изменяться не должна.

ции в счетчик 6. Кроме того, сигнал Е через элемент ИЛИ 31 в виде сигнала С подается на синхровход счетчика 6 и по заднему фронту сигнала Е н eg счетчик заносится 3-разрядный код с входа 10 случайного числа устройст - ва. Пусть, например, это код 2. В этом же такте (т.е. в течение дейст.г ВИЯ сигнала Е) по адресному входу 8

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

0

тоящей из элементов с номерами 1, 4, 5, 7. В группу наиболее активных элементов, следовательно, входят элементы с номерами 0; 2; 3 и 6. Счетчик 6 (фиг.5) выполняет операции приема информации, прямого счета и хранения, задаваемое кодами 11, 01 и 00 соответственно, поступающими в виде сигналов S1 и S2 из блока управления 5 (фиг.4). При необходимости определения номера замещаемого элемента по второму управляющему входу 12 устройства подается сигнал Е, который длится от переднего фронта имсигнала Е RS-триггеры 32 и 33 устанавливаются в единичное состояние и определяют состояния сигналов и

gQ , т.е. код П приема информации в счетчик 6. Кроме того, сигнал Е через элемент ИЛИ 31 в виде сигнала С подается на синхровход счетчика 6 и по заднему фронту сигнала Е н eg счетчик заносится 3-разрядный код с входа 10 случайного числа устройст - ва. Пусть, например, это код 2. В этом же такте (т.е. в течение дейст.г ВИЯ сигнала Е) по адресному входу 8

у1

устройства на третий вход памяти 2 поступав : адрес того набора, один из элементов которого должен быть замещен. Этот адрес удерживается на входе 8 устройства до конца операции выбора замещаемого элемента. Выбранное слово памяти 2, содержащее номера четырех наиболее активньге элементов данного набора, по синхроимпульсу СИ1 запоминается в регистре 3.

В следующем такте после окончания действия сигнала Е по переднему фронту импульса СИ1 RS-триггер 32 сбрасы веется в нуль единичным сигналом на выходе элемента И 28. Таким образом, на выходе RS-триггера 32 имеется сигнал , а на выходе RS-триггера 33 остается сигнал , т.е. вырабатывается код 01, задающий режим прямого сче та счетчика 6.

Разряды выхода счетчика 6 поступают на второй вход блока 4 сравнения, на первый вход которого подается выход регистра 3. Разряды групп выходов регистра 3 определяют коды номеров четырех наиболее активных элементов набора. Пусть, например, разряды первой Группы содержат код 2, разряды второй группы - код 6, разряды третьей группы ВЗ - код О, раз- .ряды четвертой группы - код 3. Поскольку в счетчик 6 занесен случайньй ;код 2, на выходе схемы 22 сравнени присутствует сигнал 1,. который вы зывает на выходе элемента ИЛИ 26 состояние сигнала . В блоке 5 управления сигнал разрешает прохождение синхросигнала СИ2 с выхода элемента И 27 через элемент И 29 на вход элемента ИЛИ 31, выход которого в виде сигнала С заведен на синхровход счетчика 6. По заднему фронту импульса СМ2 содержимое счетчика 6 увели

чивается на единицу и становится рав- g мя как в предлагаемом устройстве ко- ным 3. Новый код, хранящийся в счет- допреобразователь содержит п-1 сту- чике 6, снова сравнивается в блоке 4 сравнения с кодами четырех наибопень. Разрядность одного слова памяти хронологий в устройстве-прототипе равна га-Hog тГ, а в предлагаемом

лее активных элементов набора, хранящихся в регистре 3. Так как в четвёр- gQ устройстве m-llog шГ разрядов. Если

ТОЙ Группе разрядов установлен код 3, то на выходе схемы 25 сравнения имеется сигнал 1, который вызывает на выходе элемента ИЛИ 26 состояние сигнала . В блоке 5 управления (фиг.4) по сигналу разрешается прохождение синхроимпульса СИ2 на выход с элемента ИЛИ 31 и далее на вход С счетчика 6. По заднему фронту имв памяти необходимо хранить хронологии использования N наборов элементов , то экономия емкости памяти в предлагаемом устройстве по сравнению gg с прототипом составляет N (m-n)llogm разрядов. Разрядность выходного регистра памяти в устройстве-прототипе и предлагаемом равна разрядности сло ва памяти. Следовательно, в предлага

10

пульса

СИ2 содержимое счетчика увеличивается на единицу и становится равным 4. Новый код, равный 4, поступает с выхода счетчика 6 снова на вход блока 4 сравнения, где сравнивается с содержимым регистра 3. На этот раз на выходах схем сравнения 22-25 находятся сигналы Д, следо- вательно, на выходе элемента ИЛИ 26 присутствует сигнал . Сигнал блокирует в блоке 5 управления прохождение синхроимпульса СИ2 через элемент И 29, следовательно, на выхо5 де элемента ИЛИ 31 имеется сигнал О, т.е. синхровход счетчика 6 заблокирован. Импульс СИ2 проходит через элемент И 30 и, поступив на R- вход R5-TpHrrepa 33, сбрасывает его

0 нуль. Тогда на выходах R5-TpHrre- ров 32 и 33 имеются сигналы и , задающие код 00, который определяет операцию хранения в счетчике 6. Таким образом, в счетчике 6

5 оказывается код 4, не совпадающий ни с одним из кодов номеров четырех наиболее активных элементов набора. Следовательно, в счетчике находится код номера замещаемого элемента. Этот код и передается на выход 13 устройства (фиг. 5) в качестве номера замещаемого элемента.

В предлагаемом устройстве достигается уменьшение количества оборудования за счет введения счетчика, блока сравнения и блока управления, которые осуществляют выбор замещаемого элемента среди тех m-n элементов набора из m элементов, для которых не ведется хронология их использования. Для ведения хронологии использования всех элементов набора в устройстве- прототипе используется (т-1) ступенчатый кодопреобразователь, в то вре0

5

0

мя как в предлагаемом устройстве ко- допреобразователь содержит п-1 сту-

пень. Разрядность одного слова памяти хронологий в устройстве-прототипе равна га-Hog тГ, а в предлагаемом

в памяти необходимо хранить хронологии использования N наборов элементов , то экономия емкости памяти в предлагаемом устройстве по сравнению gg с прототипом составляет N (m-n)llogmf разрядов. Разрядность выходного регистра памяти в устройстве-прототипе и предлагаемом равна разрядности слова памяти. Следовательно, в предлага1

емом устройстве регистр имеет на (т-п) Г разрядов меньше, чем регистр в прототипе,,а разрядность вводимого в предлагаемом устройстве счетчика всегда равна llog тГ. В результате уменьшения числа ступене кодопреобразователя, время срабатывания предлагаемого устройства незначительно превышает время срабатывания устройства-прототипа.

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

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

от УлЗ

367017

12

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

ftuf.3

от.

{ --,,

..

tpueS