Ресурсные и информационные конфликты в конвейерных системах

Если  данные для некоторой команды, проходящей через некоторую ступень, находятся  в состоянии помехи типа RAW с какой-либо из более ранних команд, один из фиксаторов этой ступени загружается не данными, которых всё ещё нет, а индексом или тегом, указывающим на ту ступень, которая их выработает. Затем команда, ожидающая эти данные, задерживается на этой ступени до их поступления. Фиксаторы на входе в ступень позволяют другим командам проходить через неё, пока команда, зависящая от RAW, задержана. Когда ступень заканчивает вычисление, она проверяет все остальные фиксаторы ступеней на предмет того, нет ли в каком-нибудь из них тега, совпадающего с её идентификатором. Если такой тег имеется, то соответствующая ступень получает копию данных. Это позволяет возобновить выполнение задержанных команд и продолжить их продвижение по конвейеру^[2].

Организация памяти

 

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

Следующий метод – расслоение памяти. Хотя время доступа к одной команде  не уменьшается, но увеличивается число  доступов, находящихся в процессе их выполнения одновременно, и тем  самым увеличивается эффективная  скорость доступа к памяти.

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

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

В любой момент времени кэш-память содержит копии слов памяти, включая  разряды и фрагменты программ и данных. Доступ к этим копиям осуществляется в 3-10 раз быстрее, чем для основной памяти. Когда ЦП нужно сделать  запрос к памяти, он генерирует адрес  желаемого слова и затем ищет в кэш-памяти желаемую величину. Если эта величина находится в ней, то это попадание и копия нужного объекта передается ЦП без выполнения запроса к ОП и за значительно меньшее время. Если же желаемый объект не находится в кэш-памяти, то это промах (отсутствие нужных данных в КЭШ). Тогда адрес должен быть передан ОП для организации доступа к ней. Кроме того в кэш-памяти должно быть найдено место для запоминания копии желаемого слова и копии любых дополнительных слов, которые выдаются в силу расслоенной структуры памяти. Когда эти данные поступают, их копии запоминаются в кэш-памяти, а желаемый объект передается ЦП.

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

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

Важной  характеристикой такой кэш-памяти является отображение, связывающее  строки основной кэш-памяти. На протяжении определенного периода времени  каждая строка памяти может находиться в одной из нескольких различных строках кэш-памяти. Будем считать, что 2^N является числом строк основной памяти, а 2ⁿ – числом строк кэш-памяти.

Наиболее  общий, но и наиболее дорогой метод  отображения называется полностью ассоциативным. Любая строка памяти может находиться в любой строке кэш-памяти и входить при этом в любые комбинации. Каждая строка имеет свой компаратор. Если ЦП нужна строка, то он будет искать её среди 2ⁿ строк. Это может оказаться более дорогостоящим, если 2ⁿ имеет порядок сотен или тысяч. Далее, если имеется нехватка информации в кэш-памяти, то любая из её строк может быть загружена новой информацией.

Другой  крайний случай представляет структура  кэш-памяти с прямым отображением. Каждая строка кэш-памяти может содержать строку только из определенного подмножества строк ОП, а подмножества, соответствующие различным строкам кэш-памяти обычно не пересекаются. Поиск в этом случае состоит в определении, в какое из подмножеств попадает адрес строки, выработанный ЦП, затем в обращении к единственно существующей строке кэш-памяти и в единственном сравнении, устанавливающем, является ли эта строка желаемой. Поскольку реализация кэш-памяти является здесь простой, типичное прямое отображение использует разрядное отображение для выбора подмножеств памяти. Например, если в адресе строки памяти содержится N разрядов, то младшие n из них выбирают, в какую строку кэш-памяти она может копироваться. Таким образом, все строки памяти, имеющие одинаковые n разрядов в своей памяти копируются в одно и то же подмножество и могут появляться в одной строке кэш-памяти. Основным недостатком этого подхода является ограниченное число комбинаций строк, которые могут находиться в кэш-памяти.

Более общий метод, который включает в  себя как частные случаи, прямой и полностью ассоциативный методы, называется группо-ассоциативным. Здесь кэш-память делится на непересекающиеся подмножества строк. Каждая строка основной памяти может попадать в любую строку определенного подмножества строк кэш-памяти. Для поиска в кэш-памяти при прямом отображении используется адрес строки, выработанный центральным процессором для выбора подмножества строк кэш-памяти. Затем в результате полностью ассоциативного поиска внутри выбранного подмножества определяется, находится ли нужная строка в кэш-памяти. Как и раньше, прямое отображение реализуется обычно с помощью разрядного отображения. Если в кэш-памяти имеется 2ⁿ строк, разбитых на 2^s множеств, то  младшие s разрядов адреса строки, выработанного центральным процессором, показывают, в каком из подмножеств кэш-памяти должен вестись поиск. Старшие N-s разрядов этого адреса строки сравниваются затем с адресными тегами всех строк этого подмножества. На рисунке показан случай, когда s=1, т.е. когда в кэш-памяти имеются два подмножества.

Если  в кэш-памяти имеется только одно подмножество (s=0), этот метод в точности сводится к полностью ассоциативному. Если в каждом подмножестве имеется только строка (n=s), то он сводится в точности к методу прямого отображения. Для промежуточных значений s он представляет собой комбинацию обоих методов, давая разработчику возможность выбирать между малой сложностью прямого отображения и большим числом комбинаций (значит, потенциально более высокой долей попаданий) полностью ассоциативного. Здесь, по сравнению с другими подходами, каждое подмножество из 2^n-s строк может содержать любую комбинацию из 2^N-s строк основной памяти, которые могут находиться в этом подмножестве. В целом имеется:

2^N-s !/ (2^N-s -2^n-s )!

комбинаций на подмножество или приблизительно ^{комбинаций по всем} 2^s подмножествам^[2].

 

Рис. 10 Группо-ассоциативное отображение кэш-памяти при n=2 и N=4.

Признаковый обмен и сквозная запись

 

Рассмотрим  дисциплину признакового обмена. Для  блока, подлежащего вытеснению, проверяется  бит изменения. В том случае, если бит изменения равен 1, т.е. это  означает, что содержимое блока было изменено, блок переписывается в ОП, а бит изменения сбрасывается в 0.

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

В группо-ассоциативном буфере, кроме признакового обмена, могут использоваться другие обменные дисциплины. При использовании сквозной записи данные в БП и ОП записываются параллельно. В связи с этим в группо-ассоциативном буфере не используются биты изменения. При сквозной записи в случае отсутствия адресуемого блока на место вытесняемого блока сразу же записывается адресуемый блок, а в адресную часть блока заносится номер адресуемого сегмента^[4].

Блоки GENERATE и TERMINATE

Блок GENERATE используется в программах в качестве источника транзактов, поступающих на вход следующего за ним блока. Операнды блока определяют режим работы генератора и атрибуты создаваемых транзактов. В полях А и В этого блока задается интервал системного времени между соседними моментами создания транзактов (интерпретация этих полей в блоках ADVANCE и GENERATE аналогична; к примеру, постоянный интервал времени между генерацией транзактов указывается в поле А, при этом поле В оставляется пустым), в поле С - момент выхода первого транзакта, и в поле D - число транзактов, которые должны быть созданы блоком. Если D - пусто, то блок генерирует транзакты до тех пор, пока не будет остановлено моделирование. Поля E, F, G служат для задания атрибутов генерируемых транзактов. Интерпретация полей указана в таблице 1.

 

Таблица 1. Интерпретация полей блока GENERATE

И Н Т Е Р П Р Е Т А Ц И Я
ПОЛЕ	ПОЛЕ   ЗАДАНО	ПОЛЕ   ОПУЩЕНО
Е	приоритет транзактов 0 - 127	0
F	число параметров (0 - 100)	12
G	Формат  параметров  F - слово,  Н – полуслово	Н

 

Пример:

                     A,B,C,   D,  E, F, G

      ­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­

       GENERATE     10,,150,10000,64,25,H

     

Данный  блок генерирует транзакты каждые 10 единиц времени, начиная с момента 150.  Всего будет создано 10000 транзактов, каждый из которых имеет приоритет 64 и 25 параметров формата в полуслово.

Замечания:

      1. После  создания  транзакта   все параметры имеют нулевое  значение. Обозначение параметров P1, P2, Р3 и т.д.

      2. Каждый  транзакт  имеет стандартный числовой атрибут - "отметка времени",  в которой блок GENERATE заносит время входа транзакта в систему.

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

      Для обеспечения выхода транзакта  из блока GENERATE за  ним помещают  блок ADVANCE 0 (пример 1). В этом случае  все транзакты при невозможности перемещаться далее по модели скапливаются в этом блоке. Кроме блока ADVANCE 0 возможно использование некоторых других блоков.

      Пример 1.

             . . .

            GENERATE  23,7

            ADVANCE   0

            SEIZE     WERK1

             . . .

 

Блок TERMINATE служит для удаления из модели попадающих на него транзактов. Если в поле А этого блока указано какое-либо число, то интерпретатор уменьшает на это число значение глобального "счетчика завершений", служащего для определения конца моделирования (пример 2). Моделирование прекращается, когда его значение станет равным 0. Начальное значение этого счетчика определяется операндом А блока START.

Пример 2.

. . .

GENERATE 4000

TERMINATE 1

START 1

 

Моделирование будет завершено по истечении 4000 тактов модельного времени. Блоком GENERATE в 4000-м такте сгенерируется транзакт, который далее поступит на блок TERMINATE с операндом А равным 1. В результате транзакт будет выведен из модели, а из счетчика завершений будет вычтена единица. Начальное значение счетчика завершений равно 1, т.к. операнд А блока START равен 1. После вычитания из него значения операнда А блока TERMINATE счетчик завершений примет нулевое значение и моделирование завершится.