Кэш трансляции адресов (TLB): принцип работы и применение.

Введение

Компьютерный компонент

Буфер трансляции адресов (TLB) — это кэш памяти, хранящий недавние трансляции виртуальной памяти в физическую память. Он используется для уменьшения времени доступа к ячейке памяти пользователя. Его также можно назвать кэшем преобразования адресов. TLB является частью блока управления памятью (MMU) чипа. TLB может располагаться между ЦП и кэшем ЦП, между кэшем ЦП и основной памятью или между различными уровнями многоуровневого кэша. Большинство настольных, портативных и серверных процессоров включают один или несколько TLB в аппаратное обеспечение управления памятью, и он почти всегда присутствует в любом процессоре, использующем страничную или сегментированную виртуальную память. TLB иногда реализуется как ассоциативная память (CAM). Ключом поиска в CAM является виртуальный адрес, а результатом поиска — физический адрес. Если запрошенный адрес присутствует в TLB, поиск в CAM быстро дает совпадение, и полученный физический адрес может быть использован для доступа к памяти. Это называется попаданием в TLB. Если запрошенный адрес отсутствует в TLB, происходит промах, и трансляция продолжается путем поиска в таблице страниц в процессе, называемом обходом таблицы страниц. Обход таблицы страниц занимает значительное время по сравнению со скоростью процессора, поскольку включает в себя чтение содержимого нескольких ячеек памяти и использование их для вычисления физического адреса. После того, как физический адрес определен в результате обхода таблицы страниц, соответствие между виртуальным и физическим адресами заносится в TLB. Например, PowerPC 604 имеет двухпутевую ассоциативную TLB для загрузки и сохранения данных. Некоторые процессоры имеют отдельные TLB для адресов инструкций и данных.

Обзор

В TLB имеется фиксированное количество слотов, содержащих записи таблицы страниц и записи таблицы сегментов; записи таблицы страниц сопоставляют виртуальные адреса с физическими адресами и адресами промежуточных таблиц, а записи таблицы сегментов сопоставляют виртуальные адреса с адресами сегментов, адресами промежуточных таблиц и адресами таблицы страниц. Виртуальная память – это пространство памяти, видимое процессу; это пространство часто разделяется на страницы фиксированного размера (в страничной памяти) или, реже, на сегменты переменного размера (в сегментированной памяти). Таблица страниц, как правило, хранится в основной памяти и отслеживает, где виртуальные страницы хранятся в физической памяти. Для доступа к байту этот метод требует двух обращений к памяти (одно для записи в таблице страниц, другое – для самого байта). Сначала в таблице страниц выполняется поиск номера фрейма. Затем номер фрейма вместе со смещением страницы формируют фактический адрес. Таким образом, любая простая схема виртуальной памяти фактически удваивает время доступа к памяти. Следовательно, TLB используется для уменьшения времени, необходимого для доступа к ячейкам памяти при использовании метода таблицы страниц. TLB представляет собой кэш таблицы страниц, содержащий лишь подмножество ее содержимого. Обращаясь к адресам физической памяти, TLB может располагаться между ЦП и кэшем ЦП, между кэшем ЦП и основной памятью или между уровнями многоуровневого кэша. Его расположение определяет, использует ли кэш физическую или виртуальную адресацию. Если кэш использует виртуальную адресацию, запросы отправляются непосредственно от ЦП к кэшу, а к TLB обращаются только при промахе кэша. Если кэш использует физическую адресацию, ЦП выполняет поиск в TLB при каждой операции памяти, а полученный физический адрес отправляется в кэш. В архитектуре Гарварда или модифицированной архитектуре Гарварда может существовать отдельное виртуальное адресное пространство или аппаратное обеспечение доступа к памяти для инструкций и данных. Это может привести к наличию отдельных TLB для каждого типа доступа: буфера трансляции инструкций (ITLB) и буфера трансляции данных (DTLB). Различные преимущества отдельных TLB для данных и инструкций были продемонстрированы. TLB можно использовать как быстрый аппаратный кэш для поиска. На рисунке показана работа TLB. Каждая запись в TLB состоит из двух частей: тега и значения. Если тег входящего виртуального адреса совпадает с тегом в TLB, возвращается соответствующее значение. Поскольку поиск в TLB обычно является частью конвейера инструкций, он выполняется быстро и практически не влияет на производительность. Однако, чтобы поиск мог выполняться в конвейере инструкций, TLB должен быть небольшим. Распространенной оптимизацией для кэшей с физической адресацией является параллельное выполнение поиска в TLB и доступа к кэшу. При каждом обращении к виртуальной памяти аппаратное обеспечение проверяет TLB, чтобы узнать, содержится ли в нем номер страницы. Если да, то это попадание в TLB, и выполняется трансляция. Возвращается номер фрейма и используется для доступа к памяти. Если номер страницы отсутствует в TLB, необходимо проверить таблицу страниц. В зависимости от ЦП это может быть сделано автоматически с помощью аппаратных средств или с помощью прерывания операционной системы. После получения номера фрейма его можно использовать для доступа к памяти. Кроме того, номер страницы и номер фрейма добавляются в TLB, чтобы при следующем обращении их можно было быстро найти. Если TLB уже заполнен, необходимо выбрать подходящий блок для замены. Существуют различные методы замены, такие как наименее недавно использованный (LRU), первый пришел – первый ушел (FIFO) и т. д.; подробнее о виртуальной адресации в отношении кэшей и TLB см. в разделе «Трансляция адресов» в статье о кэше.

A TLB has a fixed number of slots containing page table entries and segment table entries; page table entries map virtual addresses to physical addresses and intermediate table addresses, while segment table entries map virtual addresses to segment addresses, intermediate table addresses and page table addresses. The virtual memory is the memory space as seen from a process; this space is often split into pages of a fixed size (in paged memory), or less commonly into segments of variable sizes (in segmented memory). The page table, generally stored in main memory, keeps track of where the virtual pages are stored in the physical memory. This method uses two memory accesses (one for the page table entry, one for the byte) to access a byte. First, the page table is looked up for the frame number. Second, the frame number with the page offset gives the actual address. Thus, any straightforward virtual memory scheme would have the effect of doubling the memory access time. Hence, the TLB is used to reduce the time taken to access the memory locations in the page table method. The TLB is a cache of the page table, representing only a subset of the page table contents. Referencing the physical memory addresses, a TLB may reside between the CPU and the CPU cache, between the CPU cache and primary storage memory, or between levels of a multi level cache. The placement determines whether the cache uses physical or virtual addressing. If the cache is virtually addressed, requests are sent directly from the CPU to the cache, and the TLB is accessed only on a cache miss. If the cache is physically addressed, the CPU does a TLB lookup on every memory operation, and the resulting physical address is sent to the cache. In a Harvard architecture or modified Harvard architecture, a separate virtual address space or memory access hardware may exist for instructions and data. This can lead to distinct TLBs for each access type, an instruction translation lookaside buffer (ITLB) and a data translation lookaside buffer (DTLB). Various benefits have been demonstrated with separate data and instruction TLBs. The TLB can be used as a fast lookup hardware cache. The figure shows the working of a TLB. Each entry in the TLB consists of two parts: a tag and a value. If the tag of the incoming virtual address matches the tag in the TLB, the corresponding value is returned. Since the TLB lookup is usually a part of the instruction pipeline, searches are fast and cause essentially no performance penalty. However, to be able to search within the instruction pipeline, the TLB has to be small. A common optimization for physically addressed caches is to perform the TLB lookup in parallel with the cache access. Upon each virtual memory reference, the hardware checks the TLB to see whether the page number is held therein. If yes, it is a TLB hit, and the translation is made. The frame number is returned and is used to access the memory. If the page number is not in the TLB, the page table must be checked. Depending on the CPU, this can be done automatically using a hardware or using an interrupt to the operating system. When the frame number is obtained, it can be used to access the memory. In addition, we add the page number and frame number to the TLB, so that they will be found quickly on the next reference. If the TLB is already full, a suitable block must be selected for replacement. There are different replacement methods like least recently used (LRU), first in, first out (FIFO) etc. ; see the address translation section in the cache article for more details about virtual addressing as it pertains to caches and TLBs.

Последствия для производительности

Процессор должен обращаться к основной памяти при промахе кэша инструкций, промахе кэша данных или промахе TLB. Третий случай (наиболее простой) – когда сама запрашиваемая информация фактически находится в кэше, но информация для преобразования виртуального адреса в физический отсутствует в TLB. Все эти ситуации приводят к замедлению работы из-за необходимости обращения к более медленному уровню иерархии памяти, поэтому эффективная работа TLB критически важна. Действительно, промах TLB может быть дороже, чем промах кэша инструкций или данных, поскольку требует не только загрузки из основной памяти, но и обхода таблицы страниц, что подразумевает несколько обращений к памяти. Приведенная схема иллюстрирует работу TLB. В случае промаха TLB процессор проверяет таблицу страниц на наличие записи для данной страницы. Если установлен бит присутствия, то страница находится в основной памяти, и процессор может извлечь номер фрейма из записи таблицы страниц для формирования физического адреса. Процессор также обновляет TLB, добавляя в него новую запись таблицы страниц. Если же бит присутствия не установлен, то запрашиваемая страница отсутствует в основной памяти, и генерируется ошибка страницы. Затем вызывается прерывание по ошибке страницы, которое выполняет подпрограмму обработки ошибки страницы. Если рабочий набор страниц не помещается в TLB, возникает явление, называемое "thrashing TLB" (переполнение TLB), при котором происходят частые промахи TLB, и каждая новая кэшированная страница вытесняет ту, которая вскоре потребуется снова, что приводит к снижению производительности аналогично переполнению кэша инструкций или данных. "Thrashing TLB" может возникать даже при отсутствии переполнения кэша инструкций или данных, поскольку они кэшируются в блоках разного размера. Инструкции и данные кэшируются небольшими блоками (строками кэша), а не целыми страницами, но поиск адресов осуществляется на уровне страниц. Таким образом, даже если рабочие наборы кода и данных помещаются в кэш, если они фрагментированы на множество страниц, рабочий набор виртуальных адресов может не поместиться в TLB, вызывая "thrashing TLB". Следовательно, для оптимального выбора размера TLB необходимо учитывать не только размер соответствующих кэшей инструкций и данных, но и степень их фрагментации на нескольких страницах.

The CPU has to access main memory for an instruction cache miss, data cache miss, or TLB miss. The third case (the simplest one) is where the desired information itself actually is in a cache, but the information for virtual to physical translation is not in a TLB. These are all slow, due to the need to access a slower level of the memory hierarchy, so a well functioning TLB is important. Indeed, a TLB miss can be more expensive than an instruction or data cache miss, due to the need for not just a load from main memory, but a page walk, requiring several memory accesses. The flowchart provided explains the working of a TLB. If it is a TLB miss, then the CPU checks the page table for the page table entry. If the present bit is set, then the page is in main memory, and the processor can retrieve the frame number from the page table entry to form the physical address. The processor also updates the TLB to include the new page table entry. Finally, if the present bit is not set, then the desired page is not in the main memory, and a page fault is issued. Then a page fault interrupt is called, which executes the page fault handling routine. If the page working set does not fit into the TLB, then TLB thrashing occurs, where frequent TLB misses occur, with each newly cached page displacing one that will soon be used again, degrading performance in exactly the same way as thrashing of the instruction or data cache does. TLB thrashing can occur even if instruction cache or data cache thrashing are not occurring, because these are cached in different size units. Instructions and data are cached in small blocks (cache lines), not entire pages, but address lookup is done at the page level. Thus, even if the code and data working sets fit into cache, if the working sets are fragmented across many pages, the virtual address working set may not fit into TLB, causing TLB thrashing. Appropriate sizing of the TLB thus requires considering not only the size of the corresponding instruction and data caches, but also how these are fragmented across multiple pages.

Многократные TLB

Как и кэши, TLB могут иметь несколько уровней. Процессоры могут быть (и в настоящее время обычно и являются) построены с несколькими TLB, например, небольшой L1 TLB (потенциально полностью ассоциативный), который отличается чрезвычайно высокой скоростью, и больший L2 TLB, который несколько медленнее. При использовании TLB для инструкций (ITLB) и TLB для данных (DTLB) процессор может иметь три (ITLB1, DTLB1, TLB2) или четыре TLB. Например, микроархитектура Intel Nehalem имеет четырехпутевую ассоциативную L1 DTLB с 64 записями для страниц размером 4 КБ и 32 записями для страниц размером 2/4 МБ, L1 ITLB с 128 записями для страниц размером 4 КБ с четырехпутевой ассоциативностью и 14 полностью ассоциативных записей для страниц размером 2/4 МБ (обе части ITLB статически разделены между двумя потоками) и единую 512-записную L2 TLB для страниц размером 4 КБ, обе с четырехпутевой ассоциативностью. Некоторые TLB могут иметь отдельные секции для страниц малого и большого размера. Например, микроархитектура Intel Skylake разделяет записи TLB для страниц размером 1 ГБ от записей для страниц размером 4 КБ / 2 МБ.

Виртуализация и TLB x86

С появлением виртуализации для консолидации серверов, значительные усилия были направлены на упрощение виртуализации архитектуры x86 и повышение производительности виртуальных машин на x86-оборудовании. Как правило, записи в TLB x86 не привязаны к конкретному пространству адресов; они неявно относятся к текущему пространству адресов. Следовательно, при каждом изменении пространства адресов, например, при переключении контекста, весь TLB необходимо сбрасывать. Поддержание тега, связывающего каждую запись TLB с пространством адресов в программном обеспечении, и сравнение этого тега при поиске в TLB и его сбросе, является очень затратной операцией, особенно учитывая, что TLB x86 разработан для работы с минимальной задержкой и полностью аппаратно. В 2008 году Intel (Nehalem) и AMD (SVM) представили теги как часть записи TLB и специализированное аппаратное обеспечение для проверки тега при поиске. Не все операционные системы сразу же начали в полной мере использовать эти теги, но Linux 4.14 начал использовать их для идентификации недавно использовавшихся пространств адресов, поскольку 12-битных PCID (4095 различных значений) недостаточно для всех задач, выполняемых на данном процессоре.