Взаимоотношения с памятью. Монопроцессор

За последние 10-15 лет в распоряжении программистов появился целый зоопарк различных языков программирования, каждый из которых ввёл целый ворох абстракций. Абстракции помогали писать программы быстрее, в то же время абстракции редко бывают бесплатными, и каждый новый язык накладывал свои расходы на исполняющую систему. Всё это нивелировалось тем, что железо развивалось стремительнее, чем программное обеспечение. Так как у нас появилась дешёвая память и быстрые процессоры многие просто перестали обращать внимание на то, насколько их программа оптимизирована. Это было с одной стороны, с другой стороны были(и есть) новички в индустрии, которые учились у “старых гуру”. В результате чего на форумах до сих пор можно встретить довольно молодых программистов, которые предлагают оптимизировать деление – битовым сдвигом, или же ратуют за использование “& 1” вместо “% 2” для проверки чётности числа.

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

Прямое взаимодействие

Типичная модель процессор-память выглядит следующим образом:

cpu_memory_connection

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

bus

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

  • 00 – Отсутствие активности
  • 01 – Прочитать байт из памяти
  • 10 – Записать байт в память
  • 11 – Память готова. Если процессор ждёт данные, то по этому сигналу их можно снимать. Если память ждёт данные(запись), то процессору нужно положить данные на шину.

Рассмотрим пример получения байта информация по вышеописанной шине. Предположим, что ЦП хочет получить находящийся по адресу 0x05 байт. В памяти, по этому адресу, лежит 0xAC:

  1. ЦП помещает адрес требуемого байта(0x05) на шину и “зажигает” контрольный сигнал(01).
  2. Память получив запрос, начинает его обработку. 
  3. Память, за N циклов, производит выборку из своих недр и выставляет данные на шину. После того, как данные помещены на шину, память выставляет контрольный сигнал(11). 
  4. Процессор, увидев выставленный сигнал, снимает данные с шины.

cpu_2_ram

ram_2_cpu

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

Именно в силу ограничения размера шины, процессор может передавать ограниченное количество данных за один сеанс передачи. Для 32 битных систем это 4 байта, поэтому только int(и всё что меньше его размером) является атомарным типом для x86-32, безо всяких синхронизирующих механизмов.

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

Внеочередное исполнение

Одним из способов не тратить драгоценное время процессора есть исполнения других инструкций во время ожидания памяти. Давайте рассмотрим простейший пример:

...
int x = 5;
int z = 30;
x++;
int y = z + 50;
x++;
...

Условимся, что процессор совершает арифметическую операцию за один цикл(такт), тогда как получение/запись данных из/в памяти занимает 5 тактов процессора. Вот как можно записать предыдущий код [ассемблерным] псевдокодом:

Загрузить x в регистр Р1
Инкрементировать Р1
Загрузить z в регистр Р2
Добавить 50 к Р2
Записать Р2 в y
Инкрементировать Р1

ordered_instructions

На рисунке выше изображён последовательный процесс исполнения команд, из которого видно, что общее количество тактов, которое необходимо затратить на исполнения данного кода равняется 18-и. Кроме того, из картинки можно увидеть, что у нас есть пустые такты, в которые процессор просто бездействует(для инициации записи/чтения из памяти требуется один такт, 4-е оставшихся это просто такты ожидания). Если же посмотреть на наш псевдокод то можно заметить, что x и z записываются в разные регистры, которые никак друг от друга не зависят. Почему бы нам тогда не изменить порядок исполнения инструкций, который позволит нам заполнить пустующие такты?

Загрузить x в регистр Р1
Загрузить z в регистр Р2
Инкрементировать Р1
Инкрементировать Р1
Добавить 50 к Р2
Записать Р2 в y

Этот код даст следующую картинку:

unordered_instructions

Из рисунка видно, что пустот стало меньше, а общее количество тактов, которые мы затратили на исполнение уменьшилось до 16. Почему процессор может позволить себе подобные вольности? Всё потому, что конечный пользователь переменных x и z в конечном итоге получит ожидаемый результат, вне зависимости от порядка исполнения, ведь мы изменили порядок только независимых частей. В этом лежит вся суть внеочередного исполнения – если есть свободные такты, нужно исполнить как можно больше инструкций, которые не зависят от результата “подвисших” инструкций.

Но почему тактов 16, а не 17, ведь как минимум один такт должен быть затрачен на инициацию загрузки z? Здесь всё просто, т.к. процессор использует разные сущности(память и АЛУ), то обе команды могут быть выполнены одновременно, т.е. в один и тот же такт. Поэтому инкрементирование Р1, на картинке, совмещено с началом загрузки z в Р2.

Можем ли мы еще улучшить наш код? К сожалению нет. Вышеозначенный код, по сути, имеет два независимых “потока” исполнения:

Загрузить x в регистр Р1

Инкрементировать Р1

Инкрементировать Р1

 

Загрузить z в регистр Р2

Инкрементировать Р2

Записать Р2 в y

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

В теории, внеочередное исполнение инструкций, могло бы позволить держать процессор занятым 100% времени, на практике же это не так. Большинство кода куда больше завязаны на ожидании памяти, чем на исполнении арифметических инструкций. Именно поэтому, даже если компилятор глуп и туп, то “оптимизация” по замене “% 2” на “& 1” практически всегда будет ничтожна – она не изменит ничего. В современном ПО, в первую очередь, нужно оптимизировать именно работу с памятью и лишь тот небольшой процент софта, который использует мощные математические вычисления нуждается в оптимизации в части арифметики. На моей же практике я видел только обратное, люди обеспокоены скорее тем, что используют деление, чем смотрят на то, как они взаимодействуют с памятью и как выглядят их структуры данных.

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

Кэш-память

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

cpu_memory_cache

В силу того, что кэш-память много меньше ОЗУ, она не может содержать все те данные, что может содержать ОЗУ. Более того, кэш-память не способна даже содержать достаточно данных, чтобы удовлетворить один мало-мальски серьёзный процесс. Поэтому дизайн кэш-памяти значительно отличается от дизайна ОЗУ. Простейшая кэш-память состоит из так называемых линий(lines). Каждая линия может быть различного размера, но типичными размерами являются 64 и 128 байтов. Типичный, опять же, кэш первого уровня(уровней может быть несколько, но в настоящей статье это не существенно) может содержать до 64 килобайтов данных. Это, безусловно, крайне мало, но и скорость обращения к нему составляет всего несколько циклов. На следующей картинке изображена простейшая модель кэш-памяти, где каждая строка является кэш-линией, а каждое пересечение столбца со строкой отвечает за один байт(картинка не в масштабе!):

cache_model

Т.к. кэш память много меньше и много быстрее ОЗУ, должно быть ясно, что в кэш-памяти стоит хранить лишь те данные, которые ЦП требуются в настоящий момент. Таким образом кэш состоит из данных которые либо требуются потоку, который в настоящий момент завладел ЦП, или же данных предыдущего потока, если текущему потоку какая-то часть кэша не нужна. Как вы заметили, кэш-память оперирует блоками данных существенно превышающими размеры машинного слова(линиями), в чём причина такого дизайна? Дело в том, что при запросе данных для текущей инструкции, есть довольно высокая вероятность, что для последующих инструкций ЦП понадобятся данные, лежащие по соседству. Это явление получило название пространственной локальности(spatial locality). Если посмотреть на код различных программ, то становится ясно, что этот вывод очевиден – мы часто оперируем переменными на стеке, которые лежат друг за другом в памяти; если это не стек, то это массивы в памяти, которые также представляют собой  непрерывные блоки данных. Конечно, не все данные располагаются друг за другом, но вероятность такого расположения весьма высока. Но всё это было бы бесполезно, если бы запрос одного блока, состоящего из N машинных слов, занимал бы столько же времени, сколько в совокупности занимают запросы N машинных слов, выполненные отдельно. К счастью это не так и современная память поддерживает так называемый пакетный режим(burst mode), при котором получение последовательного блока данных существенно быстрее, получения того же блока, выполненного несколькими запросами.

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

cache_memory_basic

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

Обратите внимания, что память как будто бы состоит из блоков идентичных кэш-памяти, т.е. N кэшей составляет всю память. Как вы можете видеть регион является разреженным, что позволяет эффективно позаботиться о пространственной локальности. Действительно, давайте представим, что вместо разреженных регионов мы бы имели последовательные – в этом случае соседние блоки региона соревновались бы за одну и ту же кэш линию, а так как мы знаем, что пространственная локальность встречается довольно часто, то это могло бы не просто аннулировать смысл кэша, а даже ухудшить производительность системы. Поэтому регион “размазан” по всей памяти и его блоки разделены между собой расстоянием равным размеру кэша.

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

memory_with_data

Как вы можете видеть, часть пользовательских данных расположилось в первом блоке, другая же часть расположена в блоке номер 2. Принимая во внимания вышеописанную ситуацию, давайте представим, что сначала процессор запросил слово, по адресу A(из первого блока) – всё прошло гладко, и кусок данных был загружен в первую линию кэш. Сразу за этим процессор встретил команду, которая загружает слово по адресу B(из второго блока). Выполнив команду, процессор снова загрузил кусок данных в первую кэш линию(не забываем, что данные у нас находятся в одном регионе памяти!) . Эта ситуация может быть изображена следующим образом(слева состояние после выполнения первой команды, справа – после второй):

2data_on_1line_cache

 

Из картинки видно, что новые данные были загружены в первую линию, тогда как старые были просто отброшены. Что если сразу за этой операцией нам снова нужны данные, которые располагаются по адресу A? Потом снова по адресу B? Можно повторять до бесконечности, получая этакий пинг-понг. Подобная ситуация полностью убивает смысл кэша, т.к. он не то что не увеличивает производительность, он её ухудшает в силу того, что загрузка 64 байтов будет дольше загрузки 4 байтов(а ведь нам надо было только одно машинное слово!).

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

В ситуации описанной выше мы увидели в действии так называемую временную локальность(temporal locality). Временная локальность отражает тот факт, что при использование данных однажды, велика вероятность их повторного использования в весьма короткий срок. И это тоже можно легко проследить на примере практически любого куска кода – как правило, мы используем стековые объекты в функции более одного раза. Обе локальности весьма важны при проектирования модели кэш-памяти, но они являются достаточно высокоуровневыми, что делает их не очень удобными метриками для оценки жизнеспособности кэша. Для более точной оценки кэш-памяти рассмотрим алгоритм работы кэш – процессор и введём новые понятия.

  • При инициализации(старте компьютера, к примеру) все линии кэш-памяти пусты.
  • Декодируя команды, процессор встречает команду обращения к памяти и обращается к кэшу.
  • Т.к. кэш-память не содержит никаких данных мы получаем промах(cache miss) и, следовательно, должны пробросит запрос к памяти высшего порядка(в нашем случае ОЗУ)
  • Все последующие запросы процессором тех же данных(если они не были изгнаны другими данными) будут удовлетворены кэшем, т.е. будут т.н. попаданием(cache hit)

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

Современная модель

По существу, существует всего 2 модели кэш-памяти, находящиеся на полюсах. С одной стороны находится модель прямого отображения(direct mapped), при которой скорость доступа данных, при попадании, максимальна, но с промахами дела обстоят не лучшим образом(именно эту модель мы рассматривали в качестве развёрнутого примера ранее). С другой стороны лежит полностью ассоциативная модель(fully associative cache), при которой данные из памяти могут быть помещены в любую кэш-линию(эту модель мы также упоминали ранее); при этой модели мы будем иметь наименьшее число промахов, но скорость получения данных из кэша возрастёт.

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

true_cache_empty

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

В англоязычной литературе это называется N-way cache. Например кэш-память с зоной состоящей из 4-х кэш-линий будет называться 4-way set-associative cache.

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

true_cache_filled

Буфер записи

До сих пор мы говорили только о получении данных из памяти, сиречь чтении. Но работа с памятью состоит не только из чтения,- чтобы что-то прочитать, надо это сначала записать. Так как чтение всё же превалирует над записью, в количественном отношении, то и не мудрено, что кэш-память выполняет запрос на чтение быстрее, чем она может выполнить запрос на запись(это совсем не очевидно, но тем не менее это так; не в силу того, что сама запись сложнее, а в силу того, что запись может порождать дополнительные накладные расходы, которые мы не будем рассматривать в рамках данной статьи).

Поэтому для дальнейшего ускорения работы с кэш-памятью инженеры вводят новую сущность – буфер записи. Он находится там же где и кэш-память первого уровня(по сути являясь её частью). Схематично это можно изобразить следующим образом:

write_buffer

В англоязычно литературе можно встретить различное именования буфера записи: write buffer, store buffer, victim buffer

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

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

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

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

Итог

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

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