35861

Алгоритмы кэширования современных микропроцессоров

Контрольная

Информатика, кибернетика и программирование

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

Русский

2013-09-20

387.5 KB

10 чел.

1.1 Алгоритмы кэширования современных микропроцессоров

Рассмотрим память, как 2х уровневую структуру (верхнюю и нижнюю). Например, кэш 1го уровня и кэш 2го уровня.

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

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

Все алгоритмы делятся на 2 большие группы:

  1.  Физически не реализуемые (используют информацию о будущем обращении)
  2.  Физически реализуемые (используют историю процессора)

С помощью (1) можно оценить качество алгоритмов (2).

Физически не реализуемые

  1.  Алгоритм Михновского-Шора (сов. уч.): при каждом замещении удаляется строка, обращение к которой будет позже, чем к любой другой (реализуется минимально-возможная последовательность замещения) – МИН-алгоритм.
  2.  ОПТ (оптимальный) – известна вероятность обращения к строкам памяти. Замещается строка, вероятность обращения к которой не больше, чем к любой другой. Среднее число кэш промахов минимально.

Физически реализуемые

Алгоритмы выбора строки из кэш памяти.

  1.  Алгоритм случайного замещения (СЗ;Random)
  2.  Наиболее давно использованная (НДИ). Удаляется строка, к которой дольше всего не было обращения (LRU).
  3.  По времени первого появления (FIFO). Удаляется строка, появившаяся раньше всех.
  4.  LIFO (Last In First Out).

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

  1.  Карабкающаяся строка

Все строки в КЭШе образуют некоторую последовательность, которая пронумерована. При каждом общении последовательность изменяется следующим образом.

St: j1, j2,…, jm–1, jm,…, jr

qt – номер строки основной памяти.

Строка, к которой обращаются меньше всего постепенно съезжает в конец и при промахе заменяется.

Это разновидность НДИ алгоритма.

  1.  Рабочий комплект (РК)

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

- модифицированные строки

- не модифицированные строки

Алгоритм: «Первый вышел из РК, первый удаляется из кэша». Предпочтение отдается 2ой очереди.


1.2 Зависимость по данным и переименование регистров при параллельной обработке

Возможность выполнения программы в измененной последовательности ограничивается 2мя ограничителями:

  1.  зависимость по управлению (ЗПУ) – наличие команд условных переходов;
  2.  зависимость по данным (ЗПД) – ограниченность ресурсов.

Переименование регистров (ЗПД)

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

Существует 4 зависимости:

  1.  RAR – чтение после чтения
  2.  RAW – чтение после записи
  3.  WAR – запись после чтения
  4.  WAW – запись после записи

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

Пример.

Move  r3, r7

Lw  r8, (r3)

Add  r3, r3, 4

Lw  r9, (r3)

Некоторые зависимости являются несущественными, например, зависимость RAR.

Зависимости WAR и WAW могут быть устранены.

Существенной является только 1 зависимость – RAW.

Причины возникновения лишних зависимостей:

  1.  неоптимальный программный код;
  2.  ограниченность ресурсов.

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

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

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

Существует несколько подходов решения программы, представленной в примере.

Имеется логический файл (набор регистров) и физический файл. Физический больше логического и при необходимости переименования из файла берется свободный регистр и в него заносится значение из программы.

Move  r0, r7

Lw  r8, (r0)

Add  r1, r0, 4

 Lw  r9, (r1)


1.3 Принципы конвейеризации. Синхронный и асинхронный конвейер.

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

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

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

Существуют различные виды конвейеров.

Синхронный конвейер операций

Он работает в принудительном темпе и существует единое время выполнения каждого этапа (время такта).

Время такта = времени выполнения самой сложной операции.

, где ti – время операции.

Продолжительность выполнения 2х смежный операции должна быть больше времени такта.

    Этапы

1 2 3 4 5

  1 2 3 4 5

     1 2 3 4 5

        1 2 3 4 5

           1 2 3 4 5

1 2 3 4 5 6 7 8 9 10     такты

Рост производительности (теоретически) = количеству этапов (сколько этапов во столько раз возрастает)

Реальная производительность ниже. На это влияют 3 причины:

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

При выполнении условного перехода на 1 команду теряем 1 такт и т.д. При переходе на величину больше 5 команд получаем последовательную обработку.

Если устройство управления при выборе направления ветвления ожидает формирование признака результата предыдущей команды, то также происходит простой (в примере, формирование признака результата-6й такт, анализ признака-5й такт).

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

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

Асинхронный конвейер операций

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

I – выборка участка программы

II – распаковка

III – выборка операндов (tп – время паузы)

IV – операции в АЛУ

V – запись результата

Паузы возникают из-за неготовности блоков (источника или приемника).

Принципы конвейеризации

Первоначально с точки зрения конвейера процессоры были скалярными, т.е. имели 1 конвейер. Начиная с процессора Pentium(5е поколение), у процессоров стало 2 конвейера.

Эти 2 конвейера неравнозначны (U и V).

U – главный конвейер (команды идут всегда).

По второй ветви идут только целочисленные операции, согласованно с основным.

При переходе к процессорам следующего 6го поколения подход к конвейеру изменился.

BTB0

BTB1

IFU0

IFU1

IFU2

ID0

ID1

ROB RD

RAT

RS

P0

P1

P2

P3

P4

ROB WB

RRF

Увеличилось число ступеней с 5 до 13.

Весь конвейер можно условно разбить на 3 большие части:

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

BTB – блок предсказания ветвлений

IFU – блок выборки инструкции

ID – блок декодирования

ROB RD – переупорядочивающий буфер чтения

RAT – блок  выделения ресурсов и переименования регистров

RS – станция резервирования

P – порты используемых устройств

ROB WB – переупорядочивающий буфер записи

RRF – буфер регистров

Блок предсказания ветвлений содержит информацию о выполненных ранее командах условного перехода.

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

Блок дешифрации за каждый такт работы конвейера может декодировать до 3х инструкций. Причем команда на языке ассемблера переводится в простые микрооперации µ-ops (u-ops), причем в 2х потоках могут декодироваться команды, содержащие 1 микрооперацию, а в третьем – 4 µ-ops. Такой подход характерен для RISC-архитектуры.

Простые команды, содержащие 1 микрооперацию: команды типа «регистр-регистр».

2 микрооперации: запись и простые команды чтения.

4 микрооперации: чтение, модификация, запись.


1.4 Защищенный режим 32-разрядных процессоров

ПР – процессор

ФП – физическая память

УК – указатель

СЕЛ – селектор

СМ – смещение

СФА – сумматор физического адреса

РД – регистр дескриптора

ФА – физический адрес

С – сегмент

ТДС – таблица дескриптора сегмента

ДС – дескриптор сегмента

РС – размер сегмента

БАС – базовый адрес сегмента

АС – атрибуты сегмента

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

Процессор имеет несколько таблиц дескрипторов:

- локальная (Local Description Table (LTD));

- глобальная (GDT);

- таблица прерываний (IDT).

С каждой из таблиц связан соответствующий регистр процессора.

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

Обычно 4х уровневую систему привилегий рисуют с помощью коелц защиты.

PL – уровень привилегий:

0 – ядро ОС;

1 – системные сервисы;

2 – расширения ОС;

3 – приложения.

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

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

В регистре CS задается CPL – текущий уровень привилегий данной программы. Если CPL=0, то она может обращаться ко всем сегментам, описанным в глобальной таблице дескрипторов. Если он =3, то задача с самым низким уровнем привилегий.

Поле атрибутов сегмента содержит подполе DPL – поле привилегий дескриптора (все они занимают 2 бита (0-3)). Если DPL=0, то соответствующий дескриптор самый защищенный, к нему может обратиться задача с CPL=0. DPL=3 – обращаются все.

Привилегии селектора RPL – запрошенный уровень привилегии.

Существуют и другие уровни привилегий.

Переключение задач

Характерно для многозадачных систем.

Сохраняет состояние процессора и связь с предыдущей задачей и загружает состояние новой задачи.

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

Сегментация

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

Логический (виртуальный) состоит из селектора и эффективного адреса offset.

Линейный адрес образуется сложением базового адреса сегмента и смещения.

Физический получается из линейного после преобразования страничной переадресации.

ЭА – эффективный адрес

ЛОГ А – логический адрес

ЛА – линейный адрес

ФА – физический адрес

ВА – вычисление ЭА

СР – сегментный регистр

БС – блок сегментации

БСП – блок страничной переадресации

ФП – физическая память

ИДЛ (В) А – индекс дескриптора логического (виртуального) адреса

EA=Base+Index*Scale+Displ

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

Displ – смещение – число, включенное в команду

Base – содержимое базового регистра. Обычно используется для адресации начала массива.

Index – содержимое индексного регистра (для выбора элемента массива)

Scale – размер элемента массива (множитель, задаваемый кодом).

Некоторые слагаемые в формуле могут отсутствовать.

Страничное управление памятью

Базовый механизм страничного управления использует 2х уровневую табличную трансляцию линейного адреса в физический.

КСТР – каталог страниц, ТСТР – таблица страниц, СТР ФП – страница физической памяти, АН – адрес начала, DIR – смещение

Для каждой задачи имеется регистр CR3, он хранит физический адрес каталога страниц. К этому адресу добавляется полк DIR из линейного адреса и мы обращаемся к определенной строке. В ней хранится адрес начала таблицы страниц. Складывая его с  TABLE, получаем нужную строку таблицы, где находится базовый адрес страницы. Сложив его с offset выбираем нужную ячейку.

Недостаток – низкое быстродействие.

Обращение при каждой операции доступа к памяти к 2м таблицам, расположенным в памяти, существенно снижает производительность. Поэтому используется буфер ассоциативной трансляции (блок быстрой переадресации) (TLB). Он применяется для хранения интенсивно используемых строк таблицы. В первых 32х разрядных процессорах он хранил 32 строки. Он организован в виде 4х канальной наборно-ассоциативной кэш памяти. При этом получается коэффициент кэш попаданий 98%.

Режим виртуального 8086 (V86)

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

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


RAW

WAW

WARW

RAR

II

III

IV

V

1

2

3

4

5

6

ДА

НЕТ

ПРЕПРОЦЕССОР

УПОРЯДОЧИВАЮЩЕЕ УСТРОЙСТВО

ЯДРО


 

А также другие работы, которые могут Вас заинтересовать

29899. Основные направления использования прибыли коммерческими организациями 16.08 KB
  Основные направления использования прибыли коммерческими организациями. Права и возможности в распределении и использовании прибыли имеют большое значение для любого хозяйствующего субъекта так как прибыль выступает основным источником финансового производственного и социального развития материального развития его работников. Система распределения и использования прибыли должна стимулировать дальнейшее развитие данного вида деятельности и освоение новых материально заинтересовывать в увеличении прибыли. Порядок распределения и...
29900. Государственные ценные бумаги как форма существования внутреннего и внешнего долга 21.03 KB
  Реальная курсовая цена облигаций займов и их привлекательность для заимодателей могут быть выяснены только при свободном обращении государственных ценных бумаг на фондовом рынке. Целями выпуска государственных ценных бумаг являются: ■ финансирование текущего бюджетного дефицита; ■ погашение ранее выпушенных размещенных займов; ■ обеспечение кассового исполнения государственного бюджета; ■ обеспечение равномерного поступления налоговых платежей в течение всего финансового года; ■ финансирование целевых...
29901. Краткосрочная финансовая политика РФ, её значение и задачи в современных условиях 16.29 KB
  Финансовая политика организации составная часть ее экономической политики. Успешность работы предприятия в краткосрочном периоде в решающей степени зависит от качества разработанной им краткосрочной финансовой политики под которой понимается система мер направленных на обеспечение бесперебойного финансирования его текущей деятельности. В рамках государственной деятельности целями краткосрочной финансовой политики являются: создание регулирование и контроль денежных потоков; установление сбалансированности текущих активных и пассивных...
29902. Операционный рычаг (производственный леверидж) как инструмент планирования прибыли 14.56 KB
  Эффект операционного производственного рычага заключается в том что любое изменение выручки от реализации всегда порождает более сильное изменение прибыли. Для расчета эффекта или силы воздействия рычага используется целый ряд показателей. Иными словами эффект производственного рычага показывает степень чувствительности прибыли от реализации к изменению выручки от реализации. Уровень или силу воздействия операционного рычага Degreeopertingleverge DOL рассчитываем по формуле: DOL = MP EBIT = pvQ pvQFC где MP маржинальная...
29903. Порог рентабельности, запас финансовой прочности. Практическая значимость, определяющие факторы 16.57 KB
  порог рентабельности запас финансовой прочности. Запас финансовой прочности показывает на сколько можно сократить реализацию производство продукции не неся при этом убытков. Превышение реального производства над порогом рентабельности есть запас финансовой прочности фирмы:Запас финансовой прочности = Выручка – Порог рентабельностиЗапас финансовой прочности предприятия выступает важнейшим показателем степени финансовой устойчивости. На практике возможны три ситуации которые поразному будут отражаться на величине прибыли и запасе...
29904. Кредитование физических лиц коммерческими банками: состояние и перспективы развития 20.56 KB
  Принцип возвратности банковского кредита означает что денежные средства полученные в виде ссуды служат для заемщика временным источником финансовых ресурсов и должны быть возвращены. Осуществление принципа платности банковского кредитования основывается на возмездном характере услуг оказываемых банками при предоставлении кредита. При обращении клиента в банк за получением кредита уполномоченный сотрудник банка разъясняет ему условия и порядок предоставления кредита выясняет у клиента цель на которую испрашивается кредит знакомит с...
29905. Цена капитала: источники информации и методика расчёта 45.31 KB
  В ходе процесса привлечения капитала предприятие использует различные собственные и заемные источники: эмиссию акций и облигаций кредиты банков займы у предприятий и т. Величина уставного капитала объявляется при регистрации предприятия. Его отсутствие или недостаточная величина рассматриваются как факторы дополнительного риска вложения капитала в предприятие.
29906. Особенности функционирования финансовых систем в экономически развитых странах 16.54 KB
  В финансовой системе выделяют государственные финансы финансы предприятий и финансы населения.; местные финансы – средства местного бюджета муниципальные ценные бумаги принадлежащие органам местного самоуправлениями другие финансовые средства; специальные внебюджетные фонды социальные и экономические; финансы государственных корпораций. Общая структура финансовых систем зарубежных стран: 1 государственные финансы; 2 корпоративные финансы; 3 финансы домохозяйств которые формируют и используют финансовые ресурсы централизованных...
29907. Роль Федерального бюджета в решении социальных проблем общества 17.21 KB
  Роль Федерального бюджета в решении социальных проблем общества. Роль государственного бюджета прежде всего состоит в том что бюджет создает финансовую базу необходимую для финансового обеспечения деятельности государственных органов и органов местного самоуправления. С помощью бюджета реализуются общегосударственные и региональные программы социальноэкономического характера. Роль государственного бюджета в социальноэкономическом развитии общества заключается в следующем: 1.