«Особенности памяти»: Что общего у кэша процессора и офисного клерка

Мы в «ИТ-ГРАД ^[1]» рассказываем в своем блоге об интересных технологиях в области виртуализации, например, недавно мы говорили об облачных ERP-системах ^[2], а также о виртуальных GPU ^[3].

Сегодня мы углубимся в «железную тематику» и поговорим о кэше процессора.

^[4]

/ фото Isaac Bowen ^[5] CC ^[6]

Когда появились первые компьютеры, оперативная память стоила больших денег и была очень медленной, да и процессоры, по правде говоря, не блистали производительностью. Но в 80-х годах разница в скорости работы между CPU и DRAM начала резко возрастать: производительность процессоров взлетела, тогда как скорость доступа к памяти росла менее «оперативными» темпами. Чем больше становилась эта разница, тем становилось очевиднее, что устранить разрыв сможет лишь новый тип памяти.

Разница ^[7] в производительности CPU и DRAM

Основной показатель эффективности кэша — интенсивность попаданий (cache hit). Попаданием называется ситуация, когда в кэше есть запись с идентификатором, совпадающим с идентификатором запрошенного элемента данных. Большие кэши имеют более высокий процент попаданий, но и большую задержку.

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

Для простоты понимания Фабиан Гизен решил сравнить ^[8] кэш с офисной работой. Представьте клерка, который сидит за рабочим столом и просматривает документы в папках. Рабочий стол клерка – это кэш данных уровня L1. На нем находятся папки, с которыми он работает (строки кэша), просматривая каждую страницу (байт в строке кэша).

Шкаф, установленный в офисе, — кэш второго уровня L2. В нем хранятся папки, с которыми клерк завершил работу. Чтобы взять нужный файл из шкафа, к нему надо подойти и найти его в каталоге. Кроме того доступ к шкафу имеют и другие сотрудники, играющие роль ядер CPU. Очевидно, что работа с изъятием файлов из шкафа идет медленнее.

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

Так почему же нельзя оставить один уровень кэша? Допустим, весь кэш хранится на уровне L1, и доступ к нему имеют все ядра CPU. Тогда, следуя нашей аналогии, вместо того, чтобы выделить каждому клерку по отдельному рабочему месту, мы сажаем всех сотрудников за один стометровый стол. Представьте, насколько оперативной будет их работа.

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

Как «ускориться»

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

Немаловажный факт ^[9] состоит в том, что данные попадают в кэш двумя путями. Путь первый: данные запрашиваются в процессе работы и извлекаются из основной памяти, но с задержкой.

Второй путь предполагает предварительную загрузку данных до фактического обращения к ним, причем разработчик должен представлять, какие данные ему понадобятся в дальнейшем. Этот способ известен как предвыборка (prefetching) и позволяет резко сократить время на загрузку данных из RAM. Prefetching реализуется как программно, так и аппаратно — большинство современных CPU имеет специальные встроенные устройства (prefetcher).

Объем кэша, особенно на нижних уровнях, небольшой, поэтому для загрузки новых данных в кэш зачастую требуется освободить в нем место, вытеснив часть данных (по аналогии с офисом — отнести старые файлы в шкаф и положить новые на рабочий стол). Есть несколько алгоритмов вытеснения:

• Вытеснение первой/случайной ячейки. Самые простые в реализации, однако в некоторых случаях такой подход может снизить производительность кэша;
• FIFO (first in, first out): вытесняется первая попавшая ячейка. Несложная реализация, низкие накладные расходы на оборудование, однако периодически возникают задержки;
• LRU (least recently used): вытесняется самая «старая» ячейка — та, к которой давно не обращались, и предполагается, что к ней не будут обращаться в ближайшее время. Самый популярный способ, гарантирующий результат при относительно невысокой сложности реализации. Подробнее об LRU — в обсуждении ^[10] пользователей StackExchange.

Полезное решение предлагает пользователь социального сервиса Quora. Он рассказывает ^[11] о методе, который позволяет увеличить производительность кэша при написании программ.

Прием носит название loop blocking, или разбиение цикла на блоки. Его цель — уменьшить число промахов кэша и, таким образом, увеличить его производительность. Суть приема заключается в разбиении данных на меньшие блоки, способные целиком поместиться в кэше: в дальнейшем их можно неоднократно использовать. Подробный разбор примера приводится на сайте ^[12] компании Intel.

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

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

Помимо прочего, современные инженеры ищут все новые способы оптимизации структуры кэша. Первое, что приходит на ум в этом случае — это добавить новый уровень кэша. Как показывает практика, каждые 10 лет число уровней кэша увеличивается на один. Продолжая эту традицию, чипы Haswell и Broadwell от Intel уже снабжаются ^[13] кэшем четвертого уровня (L4).

Другие темы, о которых мы рассказываем в своем блоге о корпоративном IaaS ^[14]:

• Зарубежное или локальное размещение данных в облаке: подводные камни ^[15]
• Как справиться с пиковыми нагрузками при помощи IaaS ^[16]
• Технологии хранения в страховой сфере ^[17]
• SSD-кэширование в облаке VMWare ^[18]

Автор: ИТ-ГРАД

Источник ^[19]