Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 7)

Архитектура кэш-памяти с прямым отображением (direct-mapped) характеризуется на­личием явной зависимости между адресами буферной и оперативной памяти, причем каждому адресу кэша соответствуют адреса оперативной памяти, кратные размеру кэш-памяти. Модель данного механизма такова. Пусть размер кэш-памяти равен размеру оперативной памяти. Тогда хэш-функция тривиальная: ключ - адрес строки кэша - совпадает с адресом строки ОЗУ. Затем добавим такой же блок оперативной памяти и сохраним правила размещения строк памяти в кэше (прямое отображение): первая строка кэша заполняется из первых строк блоков ОЗУ, вторая -из вторых и т.д. Соответственно к адресу строки ОЗУ добавляется старший разряд, уточняющий номер блока, который теперь не помещается в ключ. Для размещения старшего бита ОЗУ в каждой строке кэш-памяти отводится дополнительный, служебный разряд - тег, который заполняется при переписи строки кэша из ОЗУ. Тривиальная схема теперь усложняется, после считывания по ключу – по младшим разрядам адреса (без одного, старшего) ОЗУ строки кэша необходимо проверить значение разряда тега в выбранной строке. Кэш-попадание будет в случае, когда значение этого тега совпадает со старшим разрядом адреса, который не поместился в формат ключа. При кэш-промахе следует заменить строку кэша на строку с таким же номером из другого блока ОЗУ. Уже на таком примере виден главный недостаток данной схемы. Когда выбираются данные, размещенные по одинаковым адресам этих двух блоков ОЗУ, то происходит вытеснение ранее занесенных строк, несмотря на возможное наличие свободных строк в кэше. Обобщение этой схемы очевидно: ОЗУ размечается на блоки, кратные размеру кэш-памяти, и номера строк которых совпадают с номерами строк кэша. Номера этих блоков – теги - заносятся в строки кэша одновременно при заполнении кэша.

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

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

Частично-ассоциативная схема (n-way set associative) кэш памяти получается при размножении с заданным коэффициентом (n) кэш-памяти с прямым отображением. Продублируем кэш-память с прямым отображением, четыре раза (4-way). Теперь, при вызове кэш-строки ОЗУ в кэш-память она может быть размещена в одном из четырех блоков памяти данных. Соответственно, тег этой строки заносится в память тегов. И только при вызове пятой строки ОЗУ, претендующей на одно из четырех занятых строк, происходит кэш-трешинг, вытеснение одной из занятых строк при вызове претендента на это место. Частично-ассоциативная схема использует кэш-память более оптимально по сравнению с кэшем прямого отображения.

При ассоциативной организации кэша (полностью или частично) выбор строки для вытеснения определяется механизмом LPU (Least Recently Used). Однако, при увеличении размера кэша затраты на работу LRU также увеличиваются и в таких случаях более эффективно использовать простой механизм случайного выбора.

Для записи в кэш-память данного, измененного процессором, используются две стратегии обновления основной памяти (ОЗУ): стратегия сквозной записи и стратегия обратной записи. Кэш-память с немедленной (сквозной) запиcью в ОЗУ (write-through) при операции "запись" всегда записывает измененное данное как в кэш, так и в основную память, в ОЗУ. Кэш-память с отсроченной запиcью в ОЗУ (write-back) определяет другой порядок обновления оперативной памяти при изменении содержимого кэша. По этой схеме, при изменении строки кэша, её новое значение записывается только в кэш и не дублируется в ОЗУ. Обновление же содержимого оперативной памяти для кэшей с отсроченной записью производится автоматически:

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

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

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

Естественно, при первом способе записи кэш-эффект отсутствует, но реализация второй стратегии обновления ОЗУ дороже. Сквозной метод записи в ОЗУ оптимизируется схемой с буферизацией (buffered write through), в которой строка кэша сначала помещается в буфер, из которого перепись в ОЗУ производится при отсутствии к ней других запросов.

4. Глава 4

Конвейерные технологии

4.1. Параллелизм конвейерных работ

Обсуждение данной проблемы принято начинать с описания конвейера, изобретенного и внедренного Г. Фордом для сборки автомобилей. Этот механизм, используемый на автозаводах и по настоящее время, состоит из последовательности рабочих мест автосборщиков - постов, которые связаны непрерывной конвейерной лентой. На первый пост поступает шасси автомобиля, здесь к нему прикрепляются элементы подвески, и шасси по ленте передвигается на следующий пост, где к нему прикручивают колеса, на следующем посту – устанавливают мотор и т.д. Лента движется рывками, останавливаясь на одно и то же время – такт работы конвейера - и за это время каждый сборщик должен выполнить свою часть - этап работы. Работы на каждом посту организованы так, чтобы могли быть выполнены за время такта работы конвейера. Время, необходимое для сборки одного автомобиля, равно полному времени прохождения шасси авто от первого до последнего поста. Допустим, что число постов, длина конвейера, равно m, и пусть полное время сборки будет равно Т часов. Тогда при постоянном поступлении на первый пост очередного шасси (круглосуточная работа завода) новый автомобиль будет выходить с завода за каждый такт, равный времени выполнения работ на одном посту, то есть за время t = Т/m часов. Итак, несмотря на то, что полное время сборки одного автомобиля осталось равным Т, конвейерная организация работ обеспечивает сборку за это же время m автомобилей.

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

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

Так /H.G. Cragon/ пишет, что идея сборочного конвейера зародилась у Г.Форда на мясоперерабатывающей фабрике в Чикаго при наблюдении процесса разделки коровьих туш. Форд будто бы заметил, что если что-то можно последовательно разбирать на части, то можно делать это и в обратном порядке.

4.2. Ускорение арифметических вычислений

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

Пусть работа АЛУ - Арифметического Логического Устройства - при сложении чисел вещественного типа выполняется за три такта вычислителя. Для конвейеризации этой работы разделим её на три этапа, а оборудование АЛУ на три последовательных блока (Р1-Р2-Р3), где Р1 - выравнивание порядков операндов, Р2 - собственно операция (сложение мантисс), Р3 - нормализация результата, причем блоки работают параллельно и каждый блок может выполнять свою работу за один такт вычислителя. И пусть на таком АЛУ выполняются следующие вычисления:

A1 = B1+C1

A2 = B2+C2

A3 = B3+C3

A4 = B4+C4

Тогда временная диаграмма работы конвейеризованного АЛУ имеет вид:

Этапы 1 такт 2 такт 3 такт 4 такт 5 такт 6 такт

P1 B1+C1 В2+C2 B3+C3 B4+C4 н/р н/р

P2 н/р В1+C1 B2+C2 B3+C3 B4+C4 н/р

P3 н/р н/р B1+C1 B2+C2 B3+C3 В4+С4

Здесь н/р – нет работы.

Вычисления А1-А4 выполнены за 6 тактов работы вычислителя, причем только во время двух тактов (3-4) работы оборудование загружено полностью. Однако не конвейеризованное АЛУ потратило бы на эти вычисления 12 тактов, то есть в два раза больше времени.

В общем случае работа операционного блока АЛУ разбивается на m последовательных частей (стадий, выполняемые за одинаковое время), на которых арифметические команды ЭВМ выполняются в конвейерном режиме. Тогда, если на выполнение одной команды блоку требуется время T, то на обработку n команд сложения потребуется время Tn = (n + m) * (Т / m). Следовательно, если m << n, то ускорение вычислений по сравнению с работой АЛУ без конвейерной организации (его время для той же работы равно Т*n) будет в m раз.

Фактором, снижающим производительность конвейеров АЛУ, может быть взаимозависимость выполняемых на конвейерном устройстве операций - конвейерный конфликт.

Так, программа:

Команды Комментарии

A1 = B1+C1

A2 = A1+C2 A2 = (B1+C1)+C2

A3 = B3+C3 A3 = B3+C3

A4 = B4+C4 A4 = B4+C4

будет выполняться на 3 этапном АЛУ на два такта дольше, чем предыдущая:

Этапы 1такт 2 такт 3 такт 4 такт 5 такт 6 такт 7 такт 8 такт

P1 B1+C1 н/р н/р A1+C2 B3+C3 B4+C4 н/р н/р

P2 н/р B1+C1 н/р н/р A1+C2 B3+C3 B4+C4 н/р

P3 н/р н/р B1+C1 н/р н/р A1+C2 B3+C3 В4+С4

На этой диаграмме видно, что количество холостых тактов работы оборудования “н/р” – “конвейерных пузырей “ (pipeline bubble) стало больше.

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

1. RAW – чтение после записи (ЧПЗ), реальная зависимость.

2. WAR – запись после чтения (ЗПЧ), антизависимость.

3. WAW – запись после записи (ЗПЗ), выходная зависимость.

Реальная зависимость - ”чтение после записи” (RAW конфликт) возникает, когда команде для её выполнения требуется результат работы предыдущей команды. Приведенный выше пример иллюстрирует конфликт данного вида и способ его разрешения. Реализация такой схемы производится с помощью аппаратуры внутренних блокировок конвейера (pipeline interlook). Другим аппаратным способом разрешения таких конфликтов является техника продвижения данных (data forwarding). Логика этой техники состоит в передаче результата операции непосредственно на вход конвейера параллельно с записью результата в память. При этом сокращается число пропущенных рабочих тактов, что повышает производительность вычислителя. В некоторых системах результат арифметических операций всегда записывается в один из буферов на входе в АЛУ сразу после его получения.

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

Пример данной коллизии /H.G. Cragon/. Пусть процессор умеет выдавать на исполнение команды вне очереди и он исполняет следующий фрагмент программы.

i А2 = А1 + А8

j А9 = А4 + А2

k А4 = А7 + А8

Между командами i и j имеет место взаимозависимость типа RAW по переменной А2 и выполнение команды j будет приостановлено. Команда k не имеет взаимозависимостей своих операндов и может быть выполнена вне очереди. Но она может завершиться и записать результат в А4 еще до того, как “старое ”значение А4 будет востребовано командой j, и тогда значение А9 будет некорректным – WAR конфликт.

Взаимозависимость можно предотвратить путем буферизации операндов-источников в регистрах.

А4 -> В1

i А2 = В2 = А1 + А8

j А9 = В1 + В2

k А4 = А7 + А8

Буферизация входных данных для команды j устраняет взаимозависимости, теперь команда k может свободно записывать в А4. Управление порядком записи/чтения в регистры производится при помощи управляющих битов. Такое использование буферов на входах АЛУ является частным случаем общего аппарата, называемого “переименование регистров”.

Характеристики

Список файлов книги