Файл: Программа для эвм это упорядоченная последовательность команд, подлежащая обработке.docx

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

Типичная структура ассоциативного ЗУ (рис. 23) содержит запоминающий массив ЗМ, регистр ассоциативного признака РАП, регистр маски РМ, регистр информации РИ, блок сравнения БС, регистр совпадений РС и блок формирования результата ассоциативного обращения БР.
Рисунок 23 – Структура ассоциативного ЗУ

ЗМ содержит N (n+1)-разрядных ячеек. Для указания занятости ячейки используется служебный n-й разряд (0 – ячейка свободна, 1 – в ячейке записано слово).

По входной информационной шине ШИВХ в РАП поступает ассоциативный запрос (признак поиска), а в РМ – код маски поиска. Ассоциативный поиск производится только для тех разрядов РАП, которым соответствует 1 в РМ (незамаскированные разряды РАП). Блок сравнения БС состоит из N схем совпадения, которые используются для параллельного сравнения каждого бита всех хранимых слов с соответствующим битом признака поиска и выработки сигналов совпадения. В регистре совпадений РС каждой ячейке запоминающего массива соответствует один разряд. Для слов, в которых разряды совпадают с незамаскированными разрядами РАП, блок сравнения БС устанавливает 1 в соответствующих разрядах РС и 0 в остальных разрядах.

Блок формирования результата ассоциативного обращения БР формирует из слова, образовавшегося в РС, сигналы a0, a1, a2, соответствующие случаям:

• a₀ – отсутствие слов в ЗМ, удовлетворяющих ассоциативному признаку;

• a₁ – наличие одного слова в ЗМ, удовлетворяющего ассоциативному признаку;

• a₂ – наличие нескольких (более чем одного) слов в ЗМ, удовлетворяющих ассоциативному признаку.
Формирование содержимого РС и сигналов a0, a1, a2 по содержимому РАП, РМ и ЗМ называется операцией контроля ассоциации. Эта операция является составной частью операций чтения и записи.

При чтении:

---

• производится контроль ассоциации по признаку поиска в РАП;

• проверяются признаки a0, a1, a2. При a0 = 1 считывание не производится из-за отсутствия искомой информации, при a1 = 1 в РИ считывается найденное слово (слово, на которое указывает 1 в регистре совпадений), при a2 = 1 в РИ считывается слово из ячейки, имеющей наименьший номер среди ячеек, отмеченных 1 в РС. При этом соответствующий разряд в РС сбрасывается в 0. Повторяя эту операцию, можно последовательно считать все слова.
Запись производится в первую свободную ячейку. Для этого:

• отыскиваются свободные ячейки путем выполнения операции контроля ассоциации при РАП = ххх…х0 и РМ = 000…01. При этом свободные ячейки отмечаются 1 в РС;

• для записи выбирается ячейка с наименьшим номером;

• в выбранную ячейку записывается слово, поступившее в РИ с ШИВХ.
Для отыскания свободной ячейки могут использоваться служебные разряды, показывающие, как давно производилось обращение к данной ячейке. Свободной считается либо пустая ячейка, либо та, которая дольше всего не использовалась.

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

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

Главное преимущество ассоциативных ЗУ определяется тем, что время поиска информации зависит только от числа разрядов в признаке поиска и скорости опроса разрядов и не зависит от числа ячеек в запоминающем массиве.

Различают два вида поиска информации в ассоциативных ЗУ:

• простой поиск;

• сложный поиск.
При простом поиске требуется полное совпадение всех разрядов признака поиска с одноименными разрядами слов, хранящихся в запоминающем массиве.

---

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

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

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

---

18. Стековая память.

Стековая память является безадресной памятью с последовательным доступом.

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

В зависимости от того, как перемещаются слова в ЗМ, стековые ЗУ подразделяются на два основных типа:

• 
  память типа очереди или память типа FIFO (First In First Out – первым вошел, первым вышел);
  
• 
  память магазинного типа или стек.
  

Память типа очереди или память типа FIFO. В ЗУ этого типа слова перемещаются всегда в одном направлении от входа к выходу. Данные становятся доступными для считывания в том порядке, в котором производилась запись.

Возможно два варианта организации памяти типа FIFO. В первом случае информация записывается в ячейку в начале цепочки и считывается в ее конце. Запись и чтение информации производятся синхронно. ЗУ этого типа используются в качестве задержки на N тактов, где N – количество ячеек в памяти. Во втором случае информация записывается в первую свободную ячейку. Запись и чтение информации производятся асинхронно. ЗУ этого типа используются в качестве буферов с целью согласования различных скоростей информационных потоков двух компонентов микропроцессорной системы.

Стек. В ЗУ этого типа слова считываются в порядке, обратном порядку записи, т.е. по правилу LIFO (Last In First Out – последним вошел, первым вышел). Стек можно представить в виде вертикально расположенного массива ячеек. Доступ осуществляется всегда к верхней ячейке, которая называется вершиной стека. При записи в вершину стека все слова сдвигаются вниз на одну ячейку, а содержимое нижней ячейки теряется, т.е. стек опускается и происходит операция вталкивания в стек (PUSH). При чтении из вершины стека происходит обратное действие, т.е. стек поднимается и происходит операция выталкивания из стека (POP). При этом становится доступным слово из второй ячейки.

---

В универсальных МП стековая память организуется с использованием адресной памяти – памяти с произвольным доступом (моделируется на памяти с произвольным доступом). При этом в качестве стека используется часть основной памяти. Такой стек называется аппаратно-программным стеком. Это дает дополнительную гибкость, поскольку емкость стека может меняться при необходимости, и максимальный размер стека оказывается ограниченным только объемом основной памяти. Кроме того, перенос стека в память дает экономию аппаратуры.

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

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

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

19. Основная память: блочная, циклическая и блочно-циклическая схемы организации основной памяти.

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

---