Виртуалды жадқа арналған жылдам буфер (TLB)

Кіріспе

Компьютерлік компонент

Аудармалық іздеу буфері (TLB) – виртуалды жадты физикалық жадқа аудармалаудың соңғы нәтижелерін сақтайтын жад кэші. Ол пайдаланушы жадының мекенжайына қол жеткізу уақытын қысқарту үшін қолданылады. Оны адрестік аударма кэші деп те атауға болады. Бұл чиптің жадты басқару блогының (MMU) бір бөлігі. TLB процессор мен процессор кэші арасында, процессор кэші мен негізгі жад арасында немесе көп деңгейлі кэштің әртүрлі деңгейлері арасында орналасуы мүмкін. Көптеген үстел, ноутбук және сервер процессорлары жадты басқару аппараттарында бір немесе бірнеше TLB-ді қамтиды, және ол пайымдаулы немесе сегменттелген виртуалды жадты пайдаланатын кез келген процессорда дерлік кездеседі. TLB кейде мазмұндық адрестік жад (CAM) ретінде жүзеге асырылады. CAM іздеу кілті – виртуалды мекенжай, ал іздеу нәтижесі – физикалық мекенжай. Егер сұралған мекенжай TLB-де болса, CAM іздеуі жылдам сәйкестік береді және алынған физикалық мекенжай жадқа қол жеткізу үшін пайдаланылады. Бұл TLB-нің тиюі (hit) деп аталады. Егер сұралған мекенжай TLB-де болмаса, бұл сәтсіздік (miss) болып есептеледі, ал аударма беттік кестеге беттік іздеу (page walk) деп аталатын процесте қаралады. Беттік іздеу процессордың жылдамдығымен салыстырғанда көп уақыт алады, себебі ол бірнеше жад мекенжайларының мазмұнын оқуды және оларды физикалық мекенжайды есептеу үшін пайдалануды қамтиды. Физикалық мекенжай беттік іздеу арқылы анықталғаннан кейін, виртуалды мекенжай мен физикалық мекенжайдың сәйкестігі 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.

Орындаудың әсері

CPU нұсқаулық кэшінің, дерек кэшінің немесе TLB кэшінің қатесі туындағанда негізгі жадқа жүгінуі қажет. Үшінші жағдай (ең қарапайымы) – ізделіп отырған ақпарат кэште бар, бірақ виртуалды адресті физикалық адреске аудармалау үшін қажетті мәлімет TLB-де жоқ. Мұның бәрі жад иерархиясының баяу деңгейіне қол жеткізу қажеттілігіне байланысты баяу болады, сондықтан тиімді жұмыс істейтін TLB маңызды. Шындығында, TLB қатесі нұсқаулық немесе дерек кэшінің қатесінен де қымбатқа түсуі мүмкін, себебі тек негізгі жадтан дерек алу ғана емес, сонымен қатар бірнеше жадқа кіруді талап ететін беттік іздеу (page walk) қажет болады. Ұсынылған блок-схема TLB-нің жұмыс істеу принципін түсіндіреді. Егер TLB қатесі болса, CPU беттік кестедегі жазбаны тексереді. Егер «қазіргі» биті (present bit) қойылған болса, онда бет негізгі жадта бар, ал процессор физикалық адресті құру үшін беттік кесте жазбасынан фрейм нөмірін алады. Процессор сондай-ақ TLB-ді жаңа беттік кесте жазбасымен жаңартады. Егер «қазіргі» биті қойылмаған болса, онда ізделіп отырған бет негізгі жадта жоқ, және беттік қате (page fault) туындайды. Содан кейін беттік қате үзілісі (page fault interrupt) шақырылады, ол беттік қатеге қатысты процедураны орындайды. Егер беттік жұмыс жиынтығы (page working set) TLB-ге сыймаса, TLB-де «үзіліс» (thrashing) пайда болады, яғни TLB қателері жиі туындайды, әрбір жаңа кэштелген бет жақын арада қайта қолданылатын бетті ығыстырады, бұл нұсқаулық немесе дерек кэшінің «үзілісі» сияқты өнімділікті төмендетеді. TLB-дегі «үзіліс» нұсқаулық немесе дерек кэшінде «үзіліс» болмаған жағдайда да пайда болуы мүмкін, себебі олар әртүрлі өлшем бірліктерінде кэштеледі. Нұсқаулар мен деректер кішкентай блоктарда (кэш жолдары – cache lines) кэштеледі, толық беттерде емес, бірақ мекенжайды іздеу беттік деңгейде жүзеге асырылады. Осылайша, код пен деректердің жұмыс жиынтықтары кэшке сыйса да, егер олар көптеген беттерге фрагменттелген болса, виртуалды мекенжайдың жұмыс жиынтығы TLB-ге сыймауы мүмкін, бұл 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-де бірнеше деңгей болуы мүмкін. CPU бірнеше TLB-мен (қазіргі кезде көбінесе) жасалуы мүмкін, мысалы, өте жылдам, кішкентай L1 TLB (толық ассоциативті болуы мүмкін) және сәл баяу үлкен L2 TLB. Егер нұсқаулық TLB (ITLB) және дерек TLB (DTLB) қолданылса, CPU үш (ITLB1, DTLB1, TLB2) немесе төрт TLB-ге ие болуы мүмкін. Мысалы, Intel Nehalem микроархитектурасында 4 КиБ беттер үшін 64 жазбасы және 2/4 МиБ беттер үшін 32 жазбасы бар, төрт жолды жиынтығы бар L1 DTLB, 4 КиБ беттер үшін 128 жазбасы және 2/4 МиБ беттер үшін 14 толық ассоциативті жазбасы бар L1 ITLB (ITLB-нің екі бөлігі де екі жіпке статикалық түрде бөлінген) және 4 КиБ беттер үшін бірыңғай 512 жазбасы бар L2 TLB, екеуі де төрт жолды ассоциативті. Кейбір TLB-лер кішкентай және үлкен беттер үшін бөлек бөлімдерге ие болуы мүмкін. Мысалы, Intel Skylake микроархитектурасы 1 ГиБ беттерге арналған TLB жазбаларын 4 КиБ/2 МиБ беттерге арналған TLB жазбаларынан ажыратады.

Виртуализация және x86 TLB

Серверлерді біріктіру үшін виртуализацияның енгізілуімен, x86 архитектурасын виртуализациялауды жеңілдетуге және x86 аппараттық құралдарындағы виртуалды машиналардың тиімді жұмысын қамтамасыз етуге көп күш жұмсалды. Әдетте, x86 TLB-дегі жазбалар нақты бір адрестік кеңістікпен байланыстырылмайды; олар ағымдағы адрестік кеңістікке тікелей сілтеме жасайды. Сондықтан, адрестік кеңістікте өзгеріс болған сайын, мысалы, контексттік ауысу кезінде, TLB-нің барлығын тазалау қажет. Бағдарламалық жасақтамада әрбір TLB жазбасын адрестік кеңістікпен байланыстыратын таңбаны сақтау және TLB іздеу және TLB тазалау кезінде осы таңбаны салыстыру өте қымбат, әсіресе x86 TLB өте төмен жауап беру уақытымен және толығымен аппараттық түрде жұмыс істеуге арналғандықтан. 2008 жылы Intel (Nehalem) және AMD (SVM) TLB жазбасының құрамына таңбаларды және іздеу кезінде таңбаны тексеруге арналған арнайы аппараттық құралдарды енгізді. Барлық операциялық жүйелер осы таңбаларды бірден толыққанды пайдаланбады, бірақ Linux 4.14 оларды жақында қолданылған адрестік кеңістіктерді анықтау үшін пайдалана бастады, себебі 12 биттік PCID (4095 түрлі мән) белгілі бір процессорда іске қосылатын барлық тапсырмалар үшін жеткіліксіз.