Буферные ЗУ с ассоциативной адресацией

В ходе вычислительного процесса программа последовательно активизирует слова, хранимые в соответствующих ячейках ОП, и начинает с ними работать. В течение интервала времени лишь часть слов, из числа хранимых в ОП, является активной, и для повышения быстродействия ЭВМ целесообразно именно эти слова переместить в быстродействующую буферную память. Такое перемещение удобно трактовать как подмену активных ячеек ОП ячейками БЗУ. Процедура замены активных ячеек ОЗУ в процессе выполнения программы ячейками СОЗУ (БЗУ) реализуется с помощью ассоциативного ЗУ (АЗУ). Важно заметить, что любая ячейка СОЗУ может подменять любую ячейку А оперативной памяти с присвоением ячейке α адреса А.

АЗУ включается в качестве СОЗУ в соответствии со схемой рисунка 6.19 и состоит из (М+1) ячеек, которым присвоены адреса 0, 1, ..., М. АЗУ разделяются на три части: адресное поле АП, рабочее поле РП иуправляющее поле УП. В АП хранятся адреса А[0], …, A[M] слов P[0],…,P[M], размещаемых в РП.

В процессе обслуживания память, состоящая из АЗУ и ОП, выполняет следующие операции:

1. Чтение слова с адресом А;

2. Запись слова по адресу А.

Рисунок 6.19 – ЗУ с ассоциативной организацией

Операции инициируются управляющими сигналами ЗП и ЧТ и выполняются в соответствии с микропрограммой (рисунок 6.20).Выполнение операции начинается с проверки наличия в АЗУ слова с адресом А, которое поступает с шины А в адресное поле АЗУ (рис 6.19). В адресном поле значение А сопоставляется с адресами A[0],…A[M]. Если некоторой ячейке α АЗУ присвоить адрес A[α]=A, то ячейка α подменяет ячейку А ОП. Наличие в ОЗУ слова с адресом А отмечается осведомительным сигналом А АП. В АП определяется адрес α ячейки ОЗУ, к которой происходит обращение с целью записи или чтения слова Р, хранимого на итоговом регистре Р АУ (АЛУ). При записи выполняется передача P[α] = Pи при чтении Р: = P[α] (рис 6.20). Если слово с адресом А отсутствует в АЗУ, то сигнал А АП имеет нулевое значение. В этой ситуации необходимо освободить одну ячейку АЗУ для размещения в ней нового слова, активизируемого в данный момент времени. Освобождение некоторой ячейки α АЗУ выполняется путём передачи слова P[γ] в ячейку A[α] ОП. При записи результата слово Р помещается в ячейку γ АЗУ. При этом выполняются передачи A[γ]:=Aи P[γ]:=P. При чтении операндапроизводится обращение к ячейке А ОП. Выбранное слово передаётся на регистр Р и загружается в ячейку γ АЗУ. Адрес γ назначается управляющим полем АЗУ.

Рисунок 6.20 – Микропрограмма управления чтением и записью данных в АЗУ

Таким образом в АЗУ должны выполняться следующие действия:

1. Хранение адресов A[0], …, A[M] и слов P[0],…,P[M];

2. Сравнение адреса А с адресами A[0], …, A[M] с целью определения ячейки α, содержащей слово с адресом A[α] = A;

3.Формирование сигналаА АП, отмечающего наличие в АЗУ слова с адресом А;

4. Определение адреса γ ячейки, из которой с целью разгрузки АЗУ может быть удалено слово;

5. ПередачиA[γ]:=A, P[β]:=X, Y:=P[β], A:=A[γ], гдеβ=αилиγ, Xи Y – входная и выходная шины АЗУ.

Указанные функции реализуются схемой рис 6.21. При построении данной схемы предполагается, что (М+1)<K<n.

Рисунок 6.21 – Реализация функций чтения и записи данных в АЗУ

При построении данной схемы предполагается, что(М+1)<K<n. По этой причине управляющие сигналы, возбуждающие микрооперации передачи между регистрами A[β], P[β] и сигналами A, X, Y, воздействуют на цепи α и γ. Управляющее поле УП в любой момент времени присваивает единичное значение только одному сигналу γ₀,…,γ_M. Если γ_i= 1, то удалением в ОП послужит слово, хранимое в ячейке АЗУ. Значение сигнала А АП определяется временем γ₀vα1v ... vα_M.

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

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

Наиболее просто реализуется стратегия удаления слова наугад, т.е. случайный выбор, распространяющийся с одинаковой вероятностью 1/(M+1) на каждое слово 0, 1, ..., М независимо от интенсивности его использования. Реализация этой стратегии детерминированным способом сводится к последовательному удалению слов из ячеек 0, 1, ..., М АЗУ и выполняется с помощью регистра сдвига (рисунок 6.22а). Перед началом работы ЭВМ на регистр УП заносится унитарный код 100...0, и сигнал γ₀ принимает значение 1. После удаления из АЗУ очередного слова в УП посылается сигнал ПУ (признак удаления) по которому выполняется микрооперация циклического сдвига вправо. В этом случае единица из разряда γ УП переходит в разряд γ+1, чем назначается новый кандидат на удаление, причём единица из разряда М передаётся в разряд О. Таким образом, каждое слово пребывает в АЗУ в течение (1+М) периода, длительность которого определяется средним промежутком времени между моментами удаления слов. Очевидно, что удаление наугад часто приводит к промахам: может быть удалено активное слово и сохранено в АЗУ слово, потерявшее активность. В результате промахов возрастает интенсивность обращений к ОП и, следовательно, уменьшается производительность процессора.

В ряде случаев целесообразно применять более качественную стратегию: удалению подлежит слово, к которому не было ни одного обращения в течение некоторого промежутка времени. Эта стратегия реализуется схемой рис. 6.22б. Активность слов 0, 1, ..., М отмечается соответствующими разрядами регистра Т: если t_i=0, то словоiсчитается неактивным, если t_i=1, то слово активно. В начале работы регистр Т приводится в нулевое состояние. При обращении к i-й ячейке АЗУ формируется сигнал δ_i,который устанавливает t_i в состояние 1. Обращение к ячейке может происходить в следующих случаях:

1. При загрузке слова в ячейку iАЗУ;

2. При чтении словаi;

3. При записи словаi.

Рисунок 6.22 – Схема удаления слов из АЗУ в ОП

В каждом из этих случаевδ_i = 1.Таким образом, если в течение некоторого времени к ячейкам i, j, …, lпроизошло хотя бы одно обращение, то разряды i, j, …, l регистра будут приведены в состояние 1, а остальные разряды хранят 0. Кандидаты на удаление отмечаются разрядами с нулевыми состояниями. Если окажется, что все t_i=1, то формируется сигнал G = t₀, t₁,…,t_M,переключающий все триггеры в состояние 0. Среди слов, являющихся кандидатами на удаление, единственное слово выделяется избирательной схемой ИС. Эта схема среди множества слов, отмеченных сигналами t_i=0, выбирает слово с наименьшим номером. Конечно более корректным был бы случайный выбор слова среди кандидатов на удаление, но такое правило выбора значительно усложняет избирательную схему.

Наиболее выгодно использовать АЗУ емкостью 16-32 слова. Применение таких СОЗУ в настоящее время ограничено сложностью его технической реализации