Архитектура ЭВМ. Курс лекций Томск 2013 2 Оглавление
 Скачать 1.9 Mb.
|
|
С С Т Е К 40 Рис. 24. Модель стека, реализованная в оперативной памяти В качестве демонстрации приведем пример использования стека для вычисления арифметических выражений с использованием Польской Инверсной (бесскобочной) Записи (ПОЛИЗ). В ПОЛИЗе операция записывается не между операндами (Х+У), а после них (ХУ+). Подобные выражения можно вычислять по следующему алгоритму: 1) проанализировать каждый символ бесскобочной записи формулы, начиная с крайнего левого символа, до тех пор, пока не встретится знак операции; 2) взять ближайших два операнда (если операция двуместная) или один операнд (при унарной операции), расположенные слева от обнаруженного знака операции, выполнить операцию и результат поместить в формулу на место выделенных операндов и знака операции; 3) если после выполнения пункта 2) формула состоит из одного значения, это значение и есть результат, то есть алгоритм завершен, в противном случае перейти к пункту 1). Пример использования такого алгоритма для вычисления по формуле Y = (А+В−С)/(Е−D), преобразованной в формулу Y=АВС−+ЕD−/ (*) приведен в нижеследующей таблице. Для определенности в ней выбраны следующие числовые значения операндов: А=8, В=2, С=5, Е=6 и D=4. Шаг Формула, подлежащая расчету Левый знак операции Операнды Результат Новая формула после выполнения операции 1 82 5 − + 6 4 − / − 2 и 5 10 8 10 + 6 4 − / 2 810 + 6 4 − / + 8 и 10 18 18 6 4 − / 3 18 6 4 − / − 6 и 4 2 18 2 / 4 18 2 / / 18 и 2 9 9 Состояние стека после записи символов К, Е, и Т Указатель стека дно стека 770 Т Е К 770 774 1000 1004 В стек загружается символ С Указатель стека 764 764 770 774 1000 1004 С Т Е К Указатель стека Из стека извлекаются символы С и К 774 774 1000 1004 Е К 1004 Из стека извлекаются все символы. Стек пуст ! 1004 Указатель стека 41 На рис. 25. изображен расчет выражения (*) с использованием стека. Рис. 25. Пример использования стека для вычисления выражений Предполагается, что при работе со стеком на рис. 25. используются следующие команды: РUSH <ад.> - загрузка в стек содержимого ячейки с адресом <ад.>, РОР <ад.> - выгрузка из стека в память по адресу <ад.>, МUL - умножение содержимого двух верхних ячеек стека, АDD - сложение содержимого двух верхних ячеек стека, SUB - вычитание содержимого двух верхних ячеек стека, DIV - деление содержимого двух верхних ячеек стека. 6.2.4. Ассоциативные запоминающие устройства Ассоциативные запоминающие устройства (АЗУ) играют значительную роль в архитектуре современных ЭВМ для повышения производительности их работы. Описание назначения и сферы применения АЗУ требует специального рассмотрения, здесь ограничимся лишь изложением конструктивных особенностей данного типа памяти. АЗУ обеспечивает возможность поиска информации, хранящейся в ассоциативной памяти (АП), по содержимому ячеек (ассоциативному признаку, контексту), а не по адресам. Упрощенная схема использования АЗУ представлена на рис. 26. (предполагаются 8-разрядные ячейки памяти). Рис. 26. Упрощенная структура АЗУ Ассоциативная память состоит из сравнительно небольшого количества ячеек. В состав устройства управления такой памятью входят три специальных регистра: • регистр маски, • регистр контекста (или ассоциативного признака), • регистр совпадений. Биты 0 1 2 3 4 5 6 7 1 0 1 1 0 1 1 0 0 0 1 0 1 0 1 0 1 1 0 0 1 1 1 1 0 1 1 0 0 0 1 1 1 0 1 0 0 1 0 0 0 1 1 1 0 1 0 1 0 0 1 0 1 0 1 0 0 1 0 0 1 − регистр маски − регистр контекста регистр совпадений − ячейки Ассоциативной памяти А В А В×С А Е А+В×С Y С В А А+В×С F Е А+В×С E−F PUSH <ад.А> PUSH <ад.B> PUSH <ад.C> MUL ADD PUSH <ад.E> PUSH <ад.F> SUB DIV POP <ад.Y> 42 Размер регистров маски и контекста совпадает с размерностью ячеек ассоциативной памяти, а объем регистра совпадений равен количеству ячеек в ассоциативной памяти, причем каждый разряд регистра совпадений связан с соответствующей ячейкой ассоциативной памяти. Назовем маской упорядоченную совокупность номеров разрядов регистра маски, содержимое которых установлено в 1. На рис. 26. маску образует совокупность номеров 0,2,3,5,6. Назовем контекстом содержимое разрядов регистра контекста, номера которых совпадают с номерами разрядов маски. На рис. 26. контекст представлен следующей комбинацией битов: 0, 1,0,0, 1. Будем говорить, что i-й разряд ячейки замаскирован, если его номер совпадает с номером одного из разрядов маски. Ассоциативный поиск, осуществляемый в ячейках ассоциативной памяти, заключается в фиксации ячеек, для которых содержимое упорядоченной (по номеру разряда) совокупности замаскированных разрядов совпадает с контекстом. Фиксация выделенных ячеек осуществляется установкой в 1 содержимого соответствующих разрядов регистра совпадения. Важнейшим свойством АЗУ является то, что проверка содержимого проводится одновременно для всех ячеек ассоциативной памяти, что существенно ускоряет поиск по сравнению с последовательным адресным обращением к ячейкам ОЗУ. Следует, однако, отметить, что такое ускорение достигается за счет усложнения схемы управления памятью, поскольку для осуществления параллельного (одновременного) просмотра каждая ячейка должна снабжена локальным блоком управления, что резко повышает стоимость такой памяти. Именно поэтому объем ассоциативной памяти (по сравнению с объемом оперативной памяти) обычно невелик. В современных серийных моделях ЭВМ АЗУ нашли применение в некоторых архитектурах "сверхоперативных" запоминающих устройств, чаще называемых памятью типа Кэш. 6.2.5. Кэш-память Кэш (англ. cache, от фр. cacher «прятать», т.е. «скрытая» память) — промежуточный буфер с быстрым доступом, содержащий информацию, которая может быть запрошена с наибольшей вероятностью. Предназначен Кэш для ускорения обращения к данным, содержащимся постоянно в памяти с меньшей скоростью доступа. Таким образом, Кэш выступает в роли буфера, сглаживающего различие при взаимодействии в быстродействии высокоскоростного и медленного (в сравнении с высокоскоростным) устройств. Наличие такого буфера позволяет уменьшить время простоев (состояние ожидания) более быстрого устройства. В настоящее время кэширование применяется очень широко, здесь упомянем лишь два примера взаимодействия устройств с использованием Кэш: Структуру и принципы функционирования Кэш рассмотрим на примере основной взаимодействующей пары: ЦП – ОП. Центральный процессор Кэш Оперативная память Оперативная память Кэш Жесткий диск 43 Заметим, что в настоящее время соотношение скорости работы процессора и скорости работы оперативной памяти составляет приблизительно 1:1000, то есть, если данные, требуемые процессору для дальнейших вычислений, находятся в оперативной памяти (а не в Кэше), то процессор будет вынужден их ожидать, пропуская десятки и сотни операций. Если же данные находятся в Кэше, то они могут быть переданы процессору в ритме, необходимом для его безостановочной работы. Состав Кэш и принципы функционирования представлены на рис.27. Рис.27. Принципы использования кэш–памяти Кэш-контроллер управляет кэш-памятью: загружает в неё нужные данные из оперативной памяти и возвращает, когда нужно, модифицированные процессором данные в оперативную память. Когда процессор хочет прочесть (или записать) данные по какому-либо адресу оперативной памяти, он передает этот адрес в контроллер Кэш-памяти. Контроллер по некоторому алгоритму определяет, содержатся ли в кэш-памяти данные, соответствующие полученному от процессора адресу. Если данные найдены (это событие называется попаданием в кэш), то Кэш-контроллер выдает требуемые данные процессору (в случае чтения), либо перезаписывает их полученными от процессора данными (в случае записи). Если же данные не найдены (промах Кэша), то производится обращение к оперативной памяти, и процессор вынужден ждать. Замечание. Важно понимать, что кэш всегда «полон», так как оставлять часть кэш-памяти «пустой» было бы совершенно нерационально. Поэтому перед запуском приложения Кэш заранее заполняется, а новые данные попадают в кэш только путём вытеснения (замещения) каких-либо старых данных. Высокая степень попадания в кэш объясняется некоторыми объективными свойствами компьютерных данных: • Пространственная локальность. Если произошло обращение по некоторому адресу, то с высокой степенью вероятности в ближайшее время произойдет обращение к соседним адресам. Пространственная локальность позволяет надеяться, что имеет смысл копировать целый блок данных в кэш, так как, скорее всего, в ближайшее время обращение будет к данным из этого блока. • Временная локальность. Учет циклических участков программы. Если произошло обращение по некоторому адресу, то в ближайшее время с большой вероятностью произойдет обращение к этому же адресу. В ячейку Кэша загружается содержимое целого блока (последовательности) ячеек ОП вместе с адресом этого блока. Учитывая последовательную выборку команд и ПРОЦЕССОР Медленный ответ (кэш-промах) ОПЕРАТИВНАЯ ПАМЯТЬ Запрос Быстрый ответ (кэш-попадание) Кэш- контроллер Кэш-память Запись 44 последовательную работу с элементами массивов данных, расположенных в ОП, после удачного попадания (размещения нужной ячейки в блоке, загруженном в Кэш), обращения к ОП не происходит до «исчерпания» блока. Замечание. Очевидно, что последовательный процесс выполнения команд могут нарушить команды передачи управления. Если передача управления происходит на команду, расположенную в этом же блоке, проблем не возникает. В противном случае производится поиск требуемого нового блока, и при его отсутствии в Кэше фиксируется «промах», приводящий к необходимости его подкачки. Алгоритм работы Кэша представлен на рис.28. Рис.28. Алгоритм работы Кэш Эффективность Кэш. Эффективностью Кэша называется отношение числа попаданий к общему количеству обращений процессора. Эффективность, таким образом, — это число от 0 до 1. Нулевая эффективность означает, что кэш нисколько не ускорил работу системы; эффективность, равная единице, означает, что ускорение максимально, и время обращения к памяти определяется скоростью работы Кэша, а не скоростью работы оперативной памяти. Замечание. В настоящее время вероятность попадания в кэш составляет не менее 90%. Эффективность Кэша зависит от следующих факторов: 1) Объём. Чем больше объем Кэша, тем большую часть требуемых программе данных он может в себе содержать, тем реже будут происходить обращения к оперативной памяти. 2) Алгоритм функционирования. Зачастую объема Кэш-памяти недостаточно для того, чтобы вместить все необходимые для вычислений данные. В этом случае Кэш-контроллер должен «решить», какие именно данные следует держать в Кэше. Поэтому, кроме объема Кэша, важным является алгоритм его функционирования: кэш, оснащенный хорошим алгоритмом, будет гораздо эффективнее использовать свой объем, храня меньше ненужных данных. Запрос к памяти Копирование в Кэш Чтение из памяти Алгоритмы согласования Прямая запись в память Запрос выполнен нет нет нет да да да ? Кэш-попадание ? Кэш-попадан ие ? Запись 45 3) Выполняемая процессором программа. Кэш оказывается эффективным потому, что большинство компьютерных программ обращаются к памяти не случайным образом, а закономерно. Чем лучше Кэш-контроллер может «предсказать» обращения приложения к памяти, тем выше эффективность. Закономерность обращений программы к оперативной памяти обычно связана с рассмотренными выше свойствами временной и пространственной локальности. Используя эти предположения, кэш-контроллер прогнозирует обращения процессора к памяти, заранее загружая в кэш-память необходимые данные. Способы отображения оперативной памяти на Кэш-память. Содержание Кэш-памяти представляет собой совокупность записей обо всех блоках данных из основной памяти, загруженных в нее, включая их адреса (рис.29.). Адрес данных в ОП Блоки данных Управляющая информация Рис.29. Структура строки Кэш – памяти Рассмотрим механизм отображения блоков ОП в Кэш-память. Пример. Имеется ОП емкостью 256К байтов (256К = 2 18 ); для адресации такой памяти необходим 18-разрядный адрес. Пусть ОП разбивается на блоки по 16 байтов в каждом. Очевидно, что ОП удобно рассматривать как линейную последовательность из 16384=2 14 блоков. При такой организации 18-разрядный адрес можно условно разделить на две части: • младшие 4 разряда определяют адрес байта в пределах блока, • старшие 14 разрядов определяют номер одного из 16384 блоков. В дальнейшем старшие 14 разрядов адреса ОП будем называть адресом блока ОП. Пусть имеется Кэш-память емкостью 2К байтов (2К=2 11 ). Таким образом, для адресации Кэш-памяти необходим 11-разрядный адрес. В строку (ячейку) Кэш-памяти отображается блок ОП, следовательно, Кэш содержит 128=2 7 слов. 11-разрядный адрес слова в Кэш-памяти можно представить состоящим из двух частей: • адрес байта в строке (4 младших разряда), • адрес строки Кэш-памяти (7 старших разрядов). Так как расположение байтов в блоке ОП и строке Кэш одинаково, доступ к конкретному байту в строке Кэш-памяти определяется 4 младшими разрядами адреса ОП. Остается задача преобразования 14-разрядного адреса блока ОП в 7-разрядный адрес строки Кэш-памяти, то есть способа определения взаимного соответствия строки Кэш-памяти и области ОП. В этой связи различают три архитектуры Кэш-памяти: • Кэш прямого отображения, • полностью ассоциативный Кэш, • комбинация первых двух подходов - частично-ассоциативный Кэш. Для простоты ограничимся рассмотрением только архитектуру Кэш прямого отображения. Прямое отображение. При прямом отображении адрес i-й строки Кэш-памяти, на которую может быть отображен j-й блок ОП, однозначно определяется выражением i = j mod m, где m – общееколичество строк в Кэш-памяти. В примере i = j mod 128, где i может принимать значения от 0 до 127, а j – от 0 до 16383. Таким образом, на строку Кэш-памяти с номером i отображается каждый из 128 блоков ОП, начиная с номера i. (рис.30.). 46 Рис.30. Организация кэш-памяти с прямым отображением На рисунке ОП условно представлена в виде двухмерного массива блоков, в котором количество рядов равно количеству строк в Кэш-памяти, а в каждом ряду последовательно перечислены блоки, загружаемые на одну и ту же строку Кэш-памяти. При реализации такого отображения логика Кэш-памяти условно разбивает 14-разрядный адрес блока ОП на два поля: • 7-разрядное поле строки, • 7-разрядный тег. Поле строки указывает на одну из 128=2 7 строк Кэш-памяти, в которую может быть отображен блок с заданным адресом. Поле тега определяет, какой именно из списка блоков, закрепленных за данной строкой Кэш, будет отображен. Более точно, строка кэш-памяти прямого отображения может быть устроена следующим образом (рис. 31.). Рис.31. Строка Кэша с прямым отображением адресов В общем виде при прямом отображении работа кэш-контроллера представляется следующей последовательностью действий. Выполнение запроса процессора на чтение байта оперативной памяти: 1. разбивка адреса требуемого байта на части для определения тэга, номера строки́ Кэша и смещения в строке; 2. сверка тэга, записанного в нужной строке Кэша, с тэгом, выделенным из адреса; 3. если тэги не совпали (данные в Кэше отсутствуют), то выполняются следующие действия: a) если бит модификации строки не равен нулю, то он обнуляется, и содержимое строки сохраняется - записывается в оперативную память по адресу, определяемому хранящимся в строке тэгом и номером этой строки́ в Кэше; . . . 1 б ит Бит модификации 7 бит D0 D1 D2 D15 Тег Данные Строка 0 1 2 … 127 Память тегов 0 2 1 … 127 Блок 128 Блок 129 Блок 130 … Блок 255 Блок 256 Блок 257 Блок 258 … Блок 383 Блок 0 Блок 1 Блок 2 … Блок 127 … Блок 16383 0 1 2 127 Тег Строка 0 1 2 … 127 Кэш-память Основная память Блок 0 Блок 257 Блок 130 … Блок 16383 Память данных 47 b) в строку Кэша из оперативной памяти загружаются 16 байт, среди которых находится требуемый процессором байт памяти (адрес этой последовательности байт равен адресу требуемого байта, но с обнуленными последними четырьмя битами); c) тэг строки́ заменяется на тэг, выделенный из адреса требуемого байта; 4. теперь требуемые данные точно присутствуют в Кэше, и контроллер выдает байт процессору из строки Кэша в соответствии со смещением, выделенным из адреса. Выполнение запроса процессора на запись (модификацию) байта в оперативную память: 1. разбивка адреса требуемого байта на части для определения тэга, номера строки Кэша, и смещения в строке; 2. сверка тэга, записанного в нужной строке Кэша, с тэгом, выделенным из адреса; 3. если тэги не совпали (перезаписываемые данные не прокэшированы), то выполняются следующие действия: a) если бит модификации строки не равен нулю, то содержимое строки записывается на место оперативной памяти, определяемое хранящимся в строке тэгом и номером этой строки в Кэше; b) в строку Кэша из оперативной памяти загружаются 16 байт, среди которых находится перезаписываемый процессором байт памяти (адрес этой последовательности байт равен адресу требуемого байта, но с обнуленными последними четырьмя битами); c) тэг строки заменяется на тэг, выделенный из адреса требуемого байта; 4. теперь перезаписываемые данные точно присутствуют в Кэше, и контроллер модифицирует байт строки Кэша в соответствии со смещением, выделенным из адреса; 5. бит модификации строки устанавливается в 1. Кэш с прямым отображением адресов, будучи самым простым с точки зрения аппаратной реализации, исторически был первым распространенным видом Кэшей. |