otvety_na_bolshinstvo_biletov

18. Методы адресации. Непосредственная прямая и регистровая. Способ адресации — это способ

формирования исполнительного адреса операнда по адресному коду команды. Способ адресации

существенно влияет на параметры процесса обработки информации. Одни способы позволяют

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

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

Чтобы устройство управления вычислительной машины могло определить, какой именно способ

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

способам адресации соответствуют и разные коды операции. Другой подход — это добавление в состав

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

каждый адрес. Отметим, что возможен также вариант, когда в команде вообще отсутствует адресная

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

поскольку позволяет сократить длину команды.

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

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

19. Методы адресации. Косвенная и косвенная регистровая.

Косвенная регистровая -содержимое указанного регистра явл-ся адресом объектров памяти. Необходимый метод адресации-работа с массивами. Модификация команд считается в наст вр недопустимой.

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

20. Методы адресации. Адресация со смещением. Адресация со смещением. При адресации со смещением исполнительный адрес формируется в результате

суммирования содержимого адресного поля команды с содержимым одного или нескольких регистров

процессора.

Адресация со смещением предполагает, что адресная часть команды включает в себя как минимум одно поле (АК). В нем содержится константа, смысл которой в разных вариантах адресации со смещением может меняться. Константа может представлять собой некий базовый адрес, к которому добавляется хранящееся в регистре смещение. Допустим и прямо противоположный подход: базовый адрес находится в регистре процессора, а в поле АК указывается смещение относительно этого адреса. В некоторых процессорах для реализации определенных вариантов адресации со смещением предусмотрены специальные регистры, например базовый или индексный. Использование таких регистров предполагается по умолчанию, поэтому адресная часть команды содержит только поле АК. Если же составляющая адреса может располагаться в произвольном регистре общего назначения, то для указания конкретного регистра в команду включается дополнительное поле R (при составлении адреса более чем из двух составляющих в команде будет несколько таких полей). Еще одно поле R может появиться в командах, где смещение перед вычислением исполнительного адреса умножается на масштабный коэффициент. Такой коэффициент заносится в один из РОН, на который и указывает это дополнительное поле. В общем случае адресация со смещением подразумевает наличие двух адресных полей: АК и R.

21. Методы адресации. Относительная и базовая регистровая адресации. В случае базовой регистровой адресации (БРА) регистр, называемый базовым, содержит полноразрядный адрес, а подполе АС — смещение относительно этого адреса. Ссылка на базовый регистр может быть явной или неявной. В некоторых ВМ имеется специальный базовый регистр и его использование является неявным, то есть подполе R в команде отсутствует. Более типичен случай, когда в роли базового регистра выступает один из регистров общего назначения (РОН), тогда его номер явно указывается в подполе R команды.

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

22. Методы адресации. Индексная и постраничная. При индексной адресации (ИА) подполе АC содержит адрес ячейки памяти, а регистр (указанный явно или неявно) — смещение относительно этого адреса. Как видно, этот способ адресации похож на базовую регистровую адресацию. Поскольку при индексной адресации в поле АC находится полноразрядный адрес ячейки памяти, играющий роль базы, длина этого поля больше, чем при базовой регистровой адресации. Тем не менее вычисление исполнительного адреса операнда производится идентично. Индексная адресация предоставляет удобный механизм для организации итеративных вычислений. Пусть, например, имеется массив чисел, расположенных в памяти последовательно, начиная с адреса N, и мы хотим увеличить на единицу все элементы данного массива. Для этого требуется извлечь каждое число из памяти, прибавить к нему 1 и вернуть обратно, а последовательность исполнительных адресов будет следующей: N, N+ 1, N+ 2 и т. д., вплоть до последней ячейки, занимаемой рассматриваемым массивом. Значение N берется из подполя АC команды, а в выбранный регистр, называемый индексным регистром, сначала заносится 0. После каждой операции содержимое индексного регистра увеличивается на 1.

Страничная адресация (СТА) предполагает разбиение адресного пространства на страницы. Страница определяется своим начальным адресом, выступающим в качестве базы. Старшая часть этого адреса хранится в специальном регистре — регистре адреса страницы (РАС). В адресном коде команды указывается смещение внутри страницы, рассматриваемое как младшая часть исполнительного адреса. Исполнительный адрес образуется конкатенацией (присоединением) АC к содержимому РАС, как показано на рис. 3.10. На рисунке символ || обозначает операцию конкатенации.

23. Цикл выполнения команд. Командные циклы – последовательность действий при реализации команд. Одна и таже команда при разной адресации может относится к разным командным циклам.

Командный цикл состоит из нескольких этапов:

1. Чтение кода команд из памяти . УУ передает адрес команды из СК в ОП (память). Память считывает соответствующую ячейку и возвращает код команды, который помещается в РК. Далее код декодируется.

2. Загрузка операнда из памяти в АЛУ.

УУ выделяет код А1 и формирует адрес операнда. После этого полученный адрес операнда передается в память и далее операнд передается в АЛУ.

3. Если операция двуместна, то аналогично производится третий этап В АЛУ.

4. Выполнение – формирует операции и флаги.

5. Запись результата в память.

УУ вычисляет адрес результата. Он передается в ОП, а в АЛУ подается приказ.

6. Формирование адреса следующих команд.

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

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

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

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

25. Структурные конфликты и способы их минимизации.

Совмещенный режим выполнения команд в общем случае требует конвейеризации функциональных устройств и дублирования ресурсов для разрешения всех возможных комбинаций команд в конвейере. Если какая-нибудь комбинация команд не может быть принята из-за конфликта по ресурсам, то говорят, что в машине имеется структурный конфликт. Наиболее типичным примером машин, в которых возможно появление структурных конфликтов, являются машины с не полностью конвейерными функциональными устройствами. Время работы такого устройства может составлять несколько тактов синхронизации конвейера. В этом случае последовательные команды, которые используют данное функциональное устройство, не могут поступать в него в каждом такте. Другая возможность появления структурных конфликтов связана с недостаточным дублированием некоторых ресурсов, что препятствует выполнению произвольной последовательности команд в конвейере без его приостановки. Структурные конфликты возникают, например, и в машинах, в которых имеется единственный конвейер памяти для команд и данных. В этом случае, когда одна команда содержит обращение к памяти за данными, оно будет конфликтовать с выборкой более поздней команды из памяти. Чтобы разрешить эту ситуацию, можно просто приостановить конвейер на один такт, когда происходит обращение к памяти за данными. Подобная приостановка часто называются "конвейерным пузырем" (pipeline bubble) или просто пузырем, поскольку пузырь проходит по конвейеру, занимая место, но не выполняя никакой полезной работы.

Машина без структурных конфликтов будет всегда иметь более низкий CPI (среднее число тактов на выдачу команды).

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

Как правило, можно разработать неконвейерное, или не полностью конвейерное устройство, имеющее меньшую общую задержку, чем полностью конвейерное.

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

Проблема может быть разрешена с помощью достаточно простой аппаратной техники, которая называется пересылкой или продвижением данных (data forwarding), обходом (data bypassing), иногда закороткой (short-circuiting). Эта аппаратура работает следующим образом. Результат операции АЛУ с его выходного регистра всегда снова подается назад на входы АЛУ. Если аппаратура обнаруживает, что предыдущая операция АЛУ записывает результат в регистр, соответствующий источнику операнда для следующей операции АЛУ, то логические схемы управления выбирают в качестве входа для АЛУ результат, поступающий по цепи "обхода" , а не значение, прочитанное из регистрового файла.

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

Или например, команда имеет задержку, которая не может быть устранена обычной "пересылкой". Вместо этого нам нужна дополнительная аппаратура, называемая аппаратурой внутренних блокировок конвейера (pipeline interlook), чтобы обеспечить корректное выполнение примера. Вообще такого рода аппаратура обнаруживает конфликты и приостанавливает конвейер до тех пор, пока существует конфликт. В этом случае эта аппаратура приостанавливает конвейер начиная с команды, которая хочет использовать данные в то время, когда предыдущая команда, результат которой является операндом для нашей, вырабатывает этот результат. Эта аппаратура вызывает приостановку конвейера или появление "пузыря" точно также, как и в случае структурных конфликтов.

27. Классификация конфликтов по данным. Известны три возможных конфликта по данным в зависимости от порядка операций чтения и записи. Рассмотрим две команды i и j, при этом i предшествует j. Возможны следующие конфликты:

 RAW (чтение после записи) - j пытается прочитать операнд-источник данных прежде, чем i туда запишет. Таким образом, j может некорректно получить старое значение. Это наиболее общий тип конфликтов, способ их преодоления с помощью механизма обходов рассмотрен ранее.

 WAR (запись после чтения) - j пытается записать результат в приемник прежде, чем он считывается оттуда командой i, так что i может некорректно получить новое значение. Этот тип конфликтов как правило не возникает в системах с централизованным управлением потоком команд, обеспечивающих выполнение команд в порядке их поступления, так как последующая запись всегда выполняется позже, чем предшествующее считывание. Особенно часто конфликты такого рода могут возникать в системах, допускающих выполнение команд не в порядке их расположения в программном коде.

 WAW (запись после записи) - j пытается записать операнд прежде, чем будет записан результат команды i, т.е. записи заканчиваются в неверном порядке, оставляя в приемнике значение, записанное командой i, а не j. Этот тип конфликтов присутствует только в конвейерах, которые выполняют запись со многих ступеней (или позволяют команде выполняться даже в случае, когда предыдущая приостановлена).

28.Конфликты по данным приводящие к приостановке конвеера

К сожалению не все потенциальные конфликты по данным могут обрабатываться с помощью механизма "обходов". Рассмотрим следующую последовательность команд (рис. 5.9):

Рис. 5.9. Последовательность команд с приостановкой конвейера

Этот случай отличается от последовательности подряд идущих команд АЛУ. Команда загрузки (LW) регистра R1 из памяти имеет задержку, которая не может быть устранена обычной "пересылкой". Вместо этого нам нужна дополнительная аппаратура, называемая аппаратурой внутренних блокировок конвейера (pipeline interlook), чтобы обеспечить корректное выполнение примера. Вообще такого рода аппаратура обнаруживает конфликты и приостанавливает конвейер до тех пор, пока существует конфликт. В этом случае эта аппаратура приостанавливает конвейер начиная с команды, которая хочет использовать данные в то время, когда предыдущая команда, результат которой является операндом для нашей, вырабатывает этот результат. Эта аппаратура вызывает приостановку конвейера или появление "пузыря" точно также, как и в случае структурных конфликтов.

29.Планирование команд для улучшения производительности конвеера

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

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

30. Сокращение потерь на выполнение команд перехода и минимизация конфликтов по управлению.

Конфликты по управлению могут вызывать даже большие потери производительности конвейера,

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

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

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

перехода, то это может существенно отразиться на производительности машины. При частоте команд

условного перехода в программах, равной 30% и идеальном CPI, равным 1, машина с приостановками

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

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

вопросом. Число тактов, теряемых при приостановках из-за условных переходов, может быть уменьшено

двумя способами:

1. Обнаружением является ли условный переход выполняемым или невыполняемым на более

ранних ступенях конвейера.

2. Более ранним вычислением значения счетчика команд для выполняемого перехода (т.е.

вычислением целевого адреса перехода).

Реализация этих условий требует модернизации исходной схемы конвейера

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

замораживании или подавлении операций в конвейере, путем блокировки выполнения любой команды,

следующей за командой условного перехода, до тех пор, пока не станет известным направление

перехода. Привлекательность такого решения заключается в его простоте.

Метод возврата. Более хорошая и не на много более сложная схема состоит в том, чтобы

прогнозировать условный переход как невыполняемый. При этом аппаратура должна просто продолжать

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

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

станет окончательно известным. В некоторых машинах эта схема с невыполняемыми по прогнозу

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

был обычной командой. Поведение конвейера выглядит так, как будто ничего необычного не

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

конвейер от команд, выбранных вслед за командой условного перехода и заново повторить выборку

команд.

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

Четвертая схема, которая используется в некоторых машинах называется "задержанным переходом".

32. Суперконвейерные процессоры. RISC (Reduced Instruction Set Command) с усеченным набором системы команд; □ VLIW (Very Length Instruction Word) со сверхбольшим командным словом; □ MISC (Minimum Instruction Set Command) с минимальным набором системы команд и весьма высоким быстродействием и т. д. Суперконвейерный подход - применение относительно длинных конвейеров с довольно большим числом коротких ступеней. Идеология суперконвейерного подхода эффективна, если выполнение потока команд в конвейере не нарушается командами перехода, когда конвейер приходится запускать вновь, что приводит к большим задержкам.

Микропроцессоры Pentium Pro, Pentium 4.

33. Суперскалярные процессоры. Суперскалярным (этот термин впервые был использован в 1987 году) называется центральный процессор (ЦП), который одновременно выполняет более чем одну скалярную команду. Это достигается за счет включения в состав ЦП нескольких самостоятельных функциональных (исполнительных) блоков, каждый из которых отвечает за свой класс операций и может присутствовать в процессоре в нескольких экземплярах. Так, в микропроцессоре Pentium III блоки целочисленной арифметики и операций с плавающей точкой дублированы, а в микропроцессорах Pentium 4 и Athlon — троированы. Структура типичного суперскалярного процессора показана на рис. 14.8. Процессор включает в себя шесть блоков: выборки команд, декодирования команд, диспетчеризации команд, распределения команд по функциональным блокам, блок исполнения и блок обновления состояния.

34. Процессоры с линейным конвейером. -

35. Структурные конфликты и конфликты по данным при конвейерной обработке. Причины структурных конфликтов: Не полностью конвейерная структура процессора, при которой некоторые ступени отдельных команд выполняются более одного такта. В этом случае в работе конвейера возникают так называемые "пузыри" (pIPelINe bubble) в обработке командi+2 и следующих за ней начиная с такта 6, которые снижают производительность процессора. Если какой-то блок конвейера вносит задержку, то тормозится работа всего конвейера. Образуемый при этом "пузырь" должен пройти от места своего возникновения до самого конца конвейера (если, например, возникла задержка на ступени считывания команды, то в следующем такте блок декодирования от него ничего не получит, а через 3 такта соответственно блок сохранения результатов ничего не получит от блока выполнения). Таким образом, скорость конвейера определяется скоростью самой медленной его ступени. Конфликты по данным возникают в том случае, когда применение конвейерной обработки может изменить порядок обращений за операндами так, что этот порядок будет отличаться от порядка, который наблюдается при последовательном выполнении команд на неконвейерной машине.

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

Каждая 7 команда-команда пустого перехода или вызова подпрограмм. Возникает проблема какую команду выполнять. Предсказание направления перехода, т.е. процессор получив команду перехода предсказывает ее исход и организует выполнение программы в соответствии с предсказанием. Но эти команды выпол-ся т.о. чтобы можно было безболезненно вернулься к началу обработки условных (предсказанных) команд. Результаты пишутся во временные регистры. Продолж-ся работа Если не угодали, то все команды начинаются сначала. Вопросы предсказания решает процессор. Анализируя алгоритм выдает предсказ. Наиболее вероятное направление перехода. Процессору найти цикл далеко от команд трудно. Далеко не все процессоры потдерживают это. При неправельном прогнозе происходит уточнение (добавление команд и т.д)Буфер содержит команды перехода с их аправлением (10-1000 емкость буфера). Спекулятивное выполнение команд закл-ся в том, что на исполнение необходимы программы по обоим направлениям. Процессор ищет 2 ветки и запускает их одновременно. При обнаружении истинной ветки выполнения команд, 2-я отбрас-ся. С аналогичными ситуац сталкиваемся при переходе на процедуры. Разное число тактов для выполия команд. Возникает столкновение по записи. За этим должна следить СУ конвейером. Обрабатывающие эл-ты на кристалле занимают маленькую часть. Если стадий > 15 гиперконвейер, если >7- суперконвейер. Вопрос выбора числа степеней зависит от мн-ва факторов не очень изученных. Чем > больше стадий, тем проще каждой из них и можно повышать тактовую частоту. При увелич-и стадий, задача существ-но упрощается, следов-но среди них < всего команд переходов.

37. Иерархия памяти современных компьютеров. Основные понятия. Означает, что различные виды памяти образуют иерархию, на различных уровнях которой расположены памяти с отличающимися временем доступа, сложностью, стоимостью и объемом.  В большинстве современных ПК рассматривается следующая иерархия памяти:

1. Регистры процессора, организованные в регистровый файл — наиболее быстрый доступ (порядка 1 такта), но размером лишь в несколько сотен или, редко, тысяч байт.

2. Кэш процессора 1го уровня (L1) — время доступа порядка нескольких тактов, размером в десятки килобайт

3. Кэш процессора 2го уровня (L2) — большее время доступа (от 2 до 10 раз медленнее L1), около полумегабайта или более

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

5. ОЗУ системы — время доступа от сотен до, возможно, тысячи тактов, но огромные размеры в несколько гигабайт, вплоть до десятков. Время доступа к ОЗУ может варьироваться для разных его частей в случае комплексов класса NUMA (с неоднородным доступом в память)

6. Дисковое хранилище — многие миллионы тактов, если данные не были закэшированны или забуферизованны заранее, размеры до нескольких терабайт

7. Третичная память — задержки до нескольких секунд или минут, но практически неограниченные объемы (ленточные библиотеки).

38. Основные типы организации кэш-памяти. Ассоциативная кэш-память. Полностью ассоциативная: Организация КЭШ памяти определяется тем, каким образом достаточно большая оперативная память отображается на не сравнительно не большой КЭШ. Существует три разновидности отображения:

1. если каждая строка ОЗУ имеет фиксированное место расположения в КЭШ памяти, то КЭШ память называется КЭШем с прямым отображением. В этом случае адрес памяти определяет используемую строку КЭШа, а для адресации байта на строке используются младшие разряды адреса.

2. если некоторая строка оперативной памяти может располагаться на любом месте КЭШ памяти, то такая КЭШ память называется полностью ассоциативной.

3. если некоторая строка ОЗУ может располагаться на ограниченном множестве мест в КЭШ памяти, то КЭШ называется множественно-ассоциативной или частично-ассоциативной. Когда ЦП пытается

прочитать слово из основной памяти, сначала осуществляется поиск копии этого слова в кэше.

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

Полный адрес памяти делится на два поля. Младшие разряды это смещение в строке, а старшие – тег.

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

39. Основные типы организации кэш-памяти. Кэш-память прямого доступа. к ОЗУ.Самой простой организацией обладает КЭШ память с прямым отображением. В этом случае адрес памяти полностью определяет используемую строку КЭШ. Для КЭШ памяти с прямым отображением этот адрес разделяется на 3 части:

Младшая  часть байта определяет порядковый номер байта в строке КЭШа и является смещением.

Среднее поле позволяет однозначно выбрать одну строку КЭШа, это поле «номер строки». Оставшиеся старшие разряды несут информацию о признаке,  теге.

40. Множественно ассоциативная кэш-память.

Разумным компромиссом между двумя рассмотренными ранее архитектурами является частично ассоциативная организация КЭШ памяти. В этом случае несколько строк КЭШа объединяются в наборы, к которым происходит обращение с помощью средних бит адреса (поле набора).

Сравнение тегов КЭШа с тегом адреса происходит только для строк, входящих в выбранный набор. При совпадении тега адреса с одним из тегов набора происходит чтение байта из КЭШа (КЭШ попадание). Если такого совпадения нет (КЭШ промах), то происходит обращение к ОЗУ.

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

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

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

В алгоритме LRU удаляется из КЭШ памяти та строка, которая дольше всех не использовалась. Least – Recently Used (LRU) – это алгоритм, имеющий более сложную аппаратную реализацию, поскольку необходимо фиксировать все обращения к строкам для определения той строки, к которой дольше всех не было обращения.

При увеличении объема КЭШ памяти алгоритм LRU становится все более сложным и дорогим, а главное, не позволяет существенно снизить вероятность промахов по сравнению со случайным алгоритмом. Уже при объеме КЭШ памяти 256 кБ, алгоритм LRU практически не имеет преимуществ по сравнению со случайным алгоритмом, и поэтому при больших размерах КЭШа не используется, а используется случайный алгоритм.

42. Алгоритмы согласования содержимого кэш-памяти и основной памяти.

Наиболее известны два способа аппаратурной реализации этого алгоритма.

В первом из них с каждой строкой кэш-памяти ассоциируют счетчик. К содержимому всех

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

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

всего не было обращений и эта строка — первый кандидат на замещение.

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

заносятся ссылки на эти строки. При каждом обращении к строке ссылка на нее перемещается в конец

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

было обращений. Именно эта строка прежде всего и заменяется.

Другой возможный алгоритм замещения — алгоритм, работающий по принципу "первый вошел,

первый вышел (FIFO — First In First Out). Здесь заменяется строка, дольше всего находившаяся в кэш-

памяти. Алгоритм легко реализуется с помощью рассмотренной ранее очереди, с той лишь разницей, что

после обращения к строке положение соответствующей ссылки в очереди не меняется.

Еще один алгоритм — замена наименее часто использовавшейся строки (LFU -Least Frequently

Used). Заменяется та строка в кэш-памяти, к которой было меньше всего обращений. Принцип можно

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

каждого обращения добавляется единица. Главным претендентом на замещение является строка, счетчик

которой содержит наименьшее число.

Простейший алгоритм — произвольный выбор строки для замены. Замещаемая строка выбирается

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

увеличивается на единицу с каждым тактовым импульсом, вне зависимости от того, имело место

попадание или промах. Значение в счетчике определяет заменяемую строку в полностью ассоциативной

кэш-памяти или строку в пределах модуля для множественно-ассоциативной кэш-памяти. Данный

алгоритм используется крайне редко.

Среди известных в настоящее время систем с кэш-памятью наиболее встречаемым является

алгоритм LRU.

43. Классификация систем параллельной обработки данных.

Среди всех рассматриваемых систем классификации ВС наибольшее признание получила классификация , предложенная в 1966 году М. Флинном [99, 100J В ее основу положено понятие потока, под которым понимается последовательность элементов, команд или данных , обрабатываемая процессором. В зависимости от количества потоков команд и потоков данных Флинн выделяет четыре класса ар­хитектур: SISD, MISD, SIMD, MIMD.

SISD SISD (Single Instruction Stream/Single Data Stream) — одиночный поток команд и одиночный поток данных (рис. 25.5, а). Представителями этого класса являют­ся, прежде всего, классические фон-неймановские ВМ, где имеется только один поток команд, команды обрабатываются последовательно и каждая команда ини­циирует одну операцию с одним потоком данных. То, что для увеличения скорос­ти обработки команд и скорости выполнения арифметических операций может применяться конвейерная обработка, не имеет значения, поэтому в класс SISD од­новременно попадают как ВМ CDC 6600 со скалярными функциональными уст­ройствами, так и CDC 7600 с конвейерными. Некоторые специалисты считают, что к SISD-системам можно причислить и векторно-конвейерные ВС, если рассмат­ривать вектор как неделимый элемент данных для соответствующей команды.

MISD MISD (Multiple Instruction Stream/Single Data Stream) — множественный поток команд и одиночный поток данных (рис. 25.5, 6). Из определения следует, что в ар­хитектуре ВС присутствует множество процессоров, обрабатывающих один и тот же поток данных. Примером могла бы служить ВС, на процессоры которой пода­ется искаженный сигнал, а каждый из процессоров обрабатывает этот сигнал с по­мощью своего алгоритма фильтрации. Тем не менее ни Флинн, ни другие специа­листы в области архитектуры компьютеров до сих пор не сумели представить убедительный пример реально существующей вычислительной системы, постро­енной на данном принципе. Ряд исследователей относят к данному классу конвейерные системы, однако это не нашло окончательного признания. Отсюда принято считать, что пока данный класс пуст. Наличие пустого класса не следует считать недостатком классификации Флинна. Такие классы, по мнению некоторых исследователей, могут стать чрезвычайно полезными для раз­работки принципиально новых концепций в теории и практике построения вы­числительных систем.

SIMD SIMD (Single Instruction Stream/Multiple Data Stream) — одиночный поток команд и множественный поток данных (рис. 15.5, в). ВМ данной архитектуры позволяют выполнять одну арифметическую операцию сразу над многими данными — эле­ментами вектора. Бесспорными представителями класса SIMD считаются матрицы процессоров, где единое управляющее устройство контролирует множество про­цессорных элементов. Все процессорные элементы получают от устройства управ­ления одинаковую команду и выполняют ее над своими локальными данными. В принципе в этот класс можно включить и векторно-конвейерные ВС, если каж­дый элемент вектора рассматривать как отдельный элемент потока данных.

MIMD MIMD (Multiple Instruction Stream/Multiple Data Stream) — множественный по­ток команд и множественный поток данных (рис. 15.5, г). Класс предполагает на­личие в вычислительной системе множества устройств обработки команд, объе­диненных в единый комплекс и работающих каждое со своим потоком команд и данных. Класс MIMD чрезвычайно широк, поскольку включает в себя всевоз­можные мультипроцессорные системы. Кроме того, приобщение к классу MIMD зависит от трактовки. Так, ранее упоминавшиеся векторно-конвейерные ВС мож­но вполне отнести и к классу MIMD, если конвейерную обработку рассматривать как выполнение множества команд (операций ступеней конвейера) над множе­ственным скалярным потоком. Схема классификации Флинна вплоть до настоящего времени является наибо­лее распространенной при первоначальной оценке той или иной ВС, поскольку позволяет сразу оценить базовый принцип работы системы, чего часто бывает до­статочно. Однако у классификации Флинна имеются и очевидные недостатки, например неспособность однозначно отнести некоторые архитектуры к тому или иному классу. Другая слабость — это чрезмерная насыщенность класса MIMD. Все это породило множественные попытки либо модифицировать классификацию Флинна, либо предложить иную систему классификации.

44. Многопроцессорные системы с SIMD-процессорами-. ОКМД (SIMD) – выполняет одну и туже команду с разными данными. Эта структура работает не с любыми задачами. Выполняется над разными данными. Программа не зависит от числа элементов. Задачи поисков оптимизации вынуждают использовать перебор. Чем больше узлов, тем лучше. Подобные задачи хорошо масштабируются. Другое направление – составление уравнений частных производных. Аналогичные задачи возникают в метереологии.

45-46. MIMD-системы обла­дают большей гибкостью, в частности могут работать и как высокопроизводитель­ные однопользовательские системы, и как многопрограммные ВС, выполняющие множество задач параллельно. Кроме того, архитектура MIMD позволяет наибо­лее эффективно распорядиться всеми преимуществами современной микропро­цессорной технологии.

В MIMD-системе каждый процессорный элемент (ПЭ) выполняет свою про­грамму достаточно независимо от других ПЭ. В то же время ПЭ должны как-то взаимодействовать друг с другом. Различие в способе такого взаимодействия оп­ределяет условное деление MIMD-систем на ВС с общей памятью и системы с распределенной памятью. В системах с общей памятью, которые характеризуют как сильно связанные (tightly coupled), имеется общая память данных и команд, доступная всем процессорным элементам с помощью общей шины или сети соеди­нений. К этому типу, в частности, относятся симметричные мультипроцессоры (SMP, Symmetric Multiprocessor) и системы с неоднородным доступом к памяти (NUMA, Non-Uniform Memory Access).

В системах с распределенной памятью или слабо связанных (loosely coupled) многопроцессорных системах вся память распределена между процессорными эле­ментами, и каждый блок памяти доступен только «своему» процессору. Сеть со­единений связывает процессорные элементы друг с другом. Представителями этой группы могут служить системы с массовым параллелизмом (МРР, Massively Parallel Processing) и кластерные вычислительные системы.

Базовой моделью вычислений на MIMD-системе является совокупность неза­висимых процессов, эпизодически обращающихся к совместно используемым дан­ным. Существует множество вариантов этой модели. На одном конце спектра — распределенные вычисления, в рамках которых программа делится на доволь­но большое число параллельных задач, состоящих из множества подпрограмм.

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