GirişAssosiativ keş. Assosiativ keş
· birbaşa xəritələşdirmə (yerləşdirmə) ilə keş;
· tam assosiativ keş;
· çoxsaylı assosiativ keş və ya qismən assosiativ.
Birbaşa Xəritəli Keş(yerləşdirmə) ən çox
sadə növü bufer. Yaddaş ünvanı sətri unikal şəkildə müəyyən edir
məlumat blokunun yerləşdiriləcəyi önbellek. Eyni zamanda, üstünlük verilir
Güman edilir ki, RAM bloklara və hər birinə bölünür
buferdə hansı bloka yalnız bir sətir ayrılır. Bu həyata keçirmək üçün sadə və ucuz ekran üsuludur. Onun əsas çatışmazlığı müəyyən OP bloklarına önbellekdə bir xəttin sərt təyin edilməsidir. Buna görə, bir proqram eyni keş xəttinə uyğunlaşdırılmış iki fərqli blokdan sözlərə alternativ olaraq daxil olarsa, bu xətt daim yenilənəcək və hit ehtimalı aşağı olacaq.
Tam xəritələnmiş önbellek istənilən OP blokunun istənilən keş xəttinə yüklənməsinə imkan verən birbaşa çatışmazlıqları aradan qaldırmağa imkan verir. İdarəetmə məntiqi OP ünvanında iki sahə ayırır: etiket sahəsi və söz sahəsi. Etiket sahəsi OP blokunun ünvanına uyğun gəlir. Blokun surətinin keşdə olduğunu yoxlamaq üçün keş idarəetmə məntiqi eyni vaxtda bütün sətirlərin teqlərini yoxlamalıdır ki, onların ünvan etiketi sahəsinə uyğun olub-olmasın. Assosiativ xəritələşdirmə yeni yazılmış blok üçün cərgənin seçilməsində çeviklik təmin edir. Bu metodun əsas çatışmazlığı bahalı assosiativ yaddaşdan istifadə ehtiyacıdır.
Çox assosiativ tip və ya qismən assosiativ xəritəçəkmə növü – Bu, birbaşa və assosiativ metodların üstünlüklərini birləşdirən mümkün kompromislərdən biridir. Keş yaddaşı (həm teqlər, həm də məlumatlar) bir sıra modullara bölünür. Modul və OP blokları arasındakı asılılıq birbaşa xəritələşdirmədə olduğu kimi ciddidir. Lakin modulun xətləri boyunca blokların yerləşdirilməsi ixtiyaridir və modul daxilində istədiyiniz xətti tapmaq üçün assosiativ prinsipdən istifadə olunur. Bu ekran üsulu müasir mikroprosessorlarda ən çox istifadə olunur.
Keş yaddaşında OP sektorlarının xəritələşdirilməsi.
Xəritəçəkmənin bu növü bütün müasir kompüterlərdə istifadə olunur və bütün OP-nin sabit sayda ardıcıl bloklardan ibarət sektorlara bölünməsindən ibarətdir. Keş yaddaşı da eyni sayda sətirdən ibarət sektorlara bölünür. OP sektorunda və keş sektorunda blokların yeri tamamilə eynidir. Sektorun keş yaddaşa uyğunlaşdırılması assosiativ şəkildə həyata keçirilir; OP-dən istənilən sektor keşin istənilən sektorunda yerləşdirilə bilər. Beləliklə, əməliyyat zamanı ALU növbəti əmri axtarmaq üçün OP-yə müraciət edir, nəticədə OP-dən məlumatın bütün sektoru keş- yaddaşa yüklənir (orada bu əmri ehtiva edən blok yoxdursa) və uyğun olaraq Yerlilik prinsipi, bunun sayəsində sistem performansını əhəmiyyətli dərəcədə artırır.
İyerarxik keş modeli
Tipik olaraq, keş yaddaş çox səviyyəli bir arxitekturaya malikdir. Məsələn, 32 KB daxili (prosessor nüvəsində) və 1 MB xarici (CPU korpusunda və ya ana platada) keş yaddaşı olan kompüterdə birinci səviyyə 1 (L1) keş, ikincisi isə səviyyəli hesab ediləcək. 2-ci səviyyə (L2). Müasir server sistemlərində keş səviyyələrinin sayı dördə qədər ola bilər, baxmayaraq ki, ən çox istifadə olunan iki və ya üç səviyyəli sxemdir.
Bəzi prosessor arxitekturalarında Səviyyə 1 önbelleği təlimat keşinə (InstructionCache, I-cache) və verilənlər keşinə (DataCache, D-cache) bölünür və eyni ölçüdə olması mütləq deyil. Dövrə dizaynı nöqteyi-nəzərindən, ayrıca I-cache və D-cache dizayn etmək daha asan və daha ucuzdur: əmrlərin alınması I-box tərəfindən həyata keçirilir və məlumatların seçilməsi E-box və F-box tərəfindən həyata keçirilir, baxmayaraq ki, hər iki halda A-box və C-box istifadə olunur. Bütün bu bloklar böyükdür və onlara eyni vaxtda və bir keşə sürətli girişin təmin edilməsi problemlidir. Bundan əlavə, bu, qaçılmaz olaraq giriş portlarının sayının artırılmasını tələb edəcəkdir ki, bu da dizayn tapşırığını çətinləşdirir.
I-cache və D-cache çox aşağı giriş gecikmələrini təmin etməli olduğundan (bu, istənilən L1 keşi üçün doğrudur), onlar öz ölçülərini qurban verməlidirlər – adətən 16-dan 32 KB-a qədərdir. Axı, keş ölçüsü nə qədər kiçik olsa, aşağı giriş gecikmələrinə nail olmaq bir o qədər asan olar.
Səviyyə 2 önbelleği adətən vahiddir, yəni həm təlimatları, həm də məlumatları ehtiva edə bilər. Əgər o, CPU nüvəsinə quraşdırılıbsa, onda S-cache (SecondaryCache, ikincil cache), əks halda B-cache (BackupCache, backup cache) haqqında danışırlar. Müasir server CPU-larında S-keşin ölçüsü birdən bir neçə meqabayta qədər, aB-keş isə 64 MB-a qədərdir. Əgər CPU dizaynı daxili Səviyyə 3 önbelleğini ehtiva edirsə, ona T-cache (TernaryCache) deyilir. Bir qayda olaraq, keş yaddaşının hər bir sonrakı səviyyəsi daha yavaşdır, lakin ölçüsü əvvəlkindən daha böyükdür. Sistemdə B-keş varsa (keş yaddaş modelinin son səviyyəsi kimi), o zaman həm CPU, həm də sistem məntiqi dəsti ilə idarə oluna bilər.
Müəyyən bir əmrin yerinə yetirilməsi zamanı registrlərdə bunun üçün heç bir məlumat yoxdursa, onlar ən yaxın keş yaddaş səviyyəsindən, yəni D-keşdən tələb olunacaq. Əgər onlar D-Cache-də deyillərsə, sorğu S-cache-ə göndərilir və s. Ən pis halda məlumatlar birbaşa yaddaşdan çatdırılacaq. Bununla belə, virtual yaddaş idarəetmə alt sistemi işlədikdə daha kədərli bir ssenari mümkündür əməliyyat sistemi(OS) onları dəyişdirmə faylına itələməyi bacarır sabit disk. -dən çatdırılma halında RAM lazımi məlumatları əldə etmək üçün vaxt itkisi onlarla prosessor dövrü ilə yüzlərlə arasında dəyişə bilər və əgər məlumatlar sabit diskdədirsə, biz artıq milyonlarla dövrə haqqında danışmaq olar.
Keş assosiativliyi
Kesh yaddaşın fundamental xüsusiyyətlərindən biri - assosiativlik səviyyəsi onun məntiqi seqmentasiyasını əks etdirir. Fakt budur ki, lazımi məlumatların axtarışında ardıcıl olaraq bütün keş xətləri arasında axtarış aparmaq onlarla saat dövrünü tələb edəcək və CPU-da quraşdırılmış yaddaşdan istifadənin bütün qazanclarını inkar edəcək. Buna görə də, RAM hüceyrələri keş xətləri ilə sıx bağlıdır (hər sətir sabit ünvanlar dəstindən məlumatları ehtiva edə bilər), bu da axtarış vaxtını əhəmiyyətli dərəcədə azaldır. Hər bir RAM yerinin onunla əlaqəli birdən çox keş xətti ola bilər: məsələn, n-waysetassociative o deməkdir ki, verilmiş RAM ünvanındakı məlumat n keş yerində saxlanıla bilər.
Yerin seçilməsi müxtəlif alqoritmlərdən istifadə etməklə həyata keçirilə bilər, bunlar arasında ən çox istifadə edilən dəyişdirmə prinsipləri LRU (LeastRecentlyUsed, ən son tələb olunan qeyd dəyişdirilir) və LFU (LeastFrequentlyUsed, ən az tələb olunan rekord), baxmayaraq ki, dəyişikliklər var. bu prinsiplərdən. Məsələn, RAM-da ixtiyari bir ünvanda yerləşən məlumatın ixtiyari bir xəttə yerləşdirilə biləcəyi tam assosiativ keş yaddaş. Başqa bir seçim, RAM-da ixtiyari bir ünvanda yerləşən məlumatın keş yaddaşında yalnız bir yerə yerləşdirilə biləcəyi birbaşa xəritələşdirmədir. Təbii ki, bu seçim ən yüksək performansı təmin edir, çünki məlumatın mövcudluğunu yoxlayarkən nəzarətçi yalnız bir keş xəttinə "baxmalı" olacaq, lakin o, həm də ən az effektivdir, çünki nəzarətçi "optimal" yeri seçməyəcəkdir. yazarkən. Eyni keş ölçüsünü nəzərə alaraq, tam assosiativ sxem ən az sürətli, lakin ən səmərəli olacaq.
Tamamilə assosiativ bir önbellek praktikada tapılır, lakin, bir qayda olaraq, çox kiçik bir ölçüyə malikdir. Məsələn, Cyrix 6x86 CPU vahid 16 və ya 64 KB L1 keşindən əvvəl bu təlimat keşinin 256 baytını istifadə etdi. Çox vaxt TLB-lərin (bunlar aşağıda müzakirə olunacaq), filial ünvan keşlərinin, oxu-yazma buferlərinin və s. layihələndirilərkən tam assosiativ sxemdən istifadə olunur. Bir qayda olaraq, I-cache və D-cache-nin assosiativlik səviyyələri kifayət qədər aşağıdır (yuxarı). dörd kanala) - onların artırılması qeyri-mümkündür, çünki bu, giriş gecikmələrinin artmasına gətirib çıxarır və nəticədə performansa mənfi təsir göstərir. Bəzi kompensasiya olaraq, S-keşin assosiativliyi artır (adətən 16 kanala qədər), çünki bu önbelleğe daxil olmaqda gecikmələr vacib deyil. Məsələn, tez-tez istifadə olunan tam problemlərin tədqiqatlarının nəticələrinə görə, Intel Pentium III 16 KB dördkanallı D-keş sorğuların təxminən 93%-ni, 16 KB dördkanallı I-keş isə sorğuların 99%-ni əhatə edir.
Keş xətti və etiket ölçüsü
Keş yaddaşının mühüm xüsusiyyəti xəttin ölçüsüdür. Tipik olaraq, hər bir sətirdə bir ünvan qeydi (teq adlanır) olur, bu da xəttin RAM-da hansı ünvana uyğun olduğunu göstərir. Aydındır ki, fərdi baytların nömrələnməsi qeyri-mümkündür, çünki bu halda keşdəki xidmət məlumatının həcmi məlumatın özündən bir neçə dəfə çox olacaqdır. Buna görə də, bir teq adətən bir sətirə əsaslanır ki, onun ölçüsü adətən 32 və ya 64 baytdır (faktiki maksimum 1024 baytdır) və dörd (bəzən səkkiz) FSB genişliyinə bərabərdir. Bundan əlavə, hər bir keş xətti xətaya dözümlülüyünü təmin etmək üçün bəzi məlumatlar ilə müşayiət olunur: bir və ya daha çox paritet biti və ya səkkiz və ya daha çox səhvin aşkarlanması və düzəldilməsi baytı (ECC, ErrorCheckingandCorrecting), baxmayaraq ki, kütləvi həllər çox vaxt digərindən istifadə etmir.
Keş etiketinin ölçüsü üç əsas amildən asılıdır: keşin ölçüsü, RAM-ın maksimum miqdarı və keşin assosiativliyi. Riyazi olaraq bu ölçü düsturla hesablanır:
Stag=log2(Smem*A/Scache),
burada Stag bir keş teqinin ölçüsüdür, bitlərlə; Smem - RAM-ın maksimum keşlənmiş miqdarı, baytlarda; Scache - keş yaddaşının ölçüsü, baytlarla; A - kanallarda cache assosiativliyi.
Bu o deməkdir ki, 1 GB RAM və 1 MB ikili yol assosiativ keşi olan sistem hər teq üçün 11 bit tələb edəcəkdir. Diqqətəlayiqdir ki, keş xəttinin ölçüsü özü heç bir şəkildə etiket ölçüsünə təsir etmir, lakin teqlərin sayına tərs təsir göstərir. Başa düşmək lazımdır ki, bir keş xəttinin ölçüsünü sistem məlumat avtobusunun enindən az etmək mənasızdır, lakin ölçüsünü dəfələrlə artırmaq, lazımsız məlumatlarla keş yaddaşının həddindən artıq tıxanmasına və həddindən artıq yüklənməyə səbəb olacaqdır. sistem avtobusu və yaddaş avtobusu. Bundan əlavə, önbelleğe alına bilən maksimum yaddaş miqdarı sistemdə quraşdırılmış maksimum mümkün RAM miqdarına uyğun olmamalıdır. Keşlənə biləndən daha çox RAM olduqda bir vəziyyət yaranarsa, keş yaddaşında yalnız RAM-ın aşağı seqmentindən məlumat olacaq. Socket7/Super7 platformasında vəziyyət məhz belə idi. Bu platforma üçün çipsetlər böyük həcmdə RAM-dan (256 MB-dan 1 GB-a qədər) istifadə etməyə imkan verdi, halbuki keşlənmiş həcm tez-tez ilk 64 MB ilə məhdudlaşırdı (söhbət ana platada yerləşən B-keşdən gedir) istifadə olunurdu. ucuz 8-bit etiketli SRAM çipləri (bunların 2 biti xəttin etibarlılığı və modifikasiyası göstəriciləri üçün ayrılmışdır). Bu, performansın nəzərəçarpacaq dərəcədə azalmasına səbəb oldu.
Niyə biz tək yivli proqramların performansında daimi artım görürük? IN hal-hazırda Biz mikroprosessor texnologiyalarının inkişafının o mərhələsindəyik ki, tək yivli proqramların sürətinin artması yalnız yaddaşdan asılıdır. Nüvələrin sayı artır, lakin tezlik 4 GHz-də sabitdir və heç bir performans artımı təmin etmir.
Yaddaş əməliyyatının sürəti və tezliyi "pulsuz tortumuzu" əldə etdiyimiz əsas şeydir (link). Məhz buna görə yaddaşdan bacardığımız qədər səmərəli və xüsusən də keş kimi sürətli istifadə etmək vacibdir. Müəyyən bir kompüter üçün proqramı optimallaşdırmaq üçün prosessor keşinin xüsusiyyətlərini bilmək faydalıdır: səviyyələrin sayı, ölçüsü, xəttin uzunluğu. Bu, xüsusilə yüksək performanslı kodlarda - sistem nüvələrində, riyazi kitabxanalarda vacibdir.
Avtomatik keşin xüsusiyyətlərini necə təyin etmək olar? (təbii ki, cpuinfo təhlil edilmiş hesab edilmir, yalnız ona görə ki, biz digər əməliyyat sistemlərində asanlıqla həyata keçirilə bilən alqoritm əldə etmək istəyirik. Rahatdır, elə deyilmi?) İndi edəcəyimiz şey budur.
Bir az nəzəriyyə
Hal-hazırda, geniş istifadə olunan üç növ keş yaddaş var: birbaşa xəritələnmiş keş, assosiativ keş və çox assosiativ keş.Birbaşa xəritəçəkmə önbelleği
- verilmiş RAM xətti tək bir keş xətti ilə əlaqələndirilə bilər, lakin bir çox mümkün RAM xətti hər bir keş xəttinə uyğunlaşdırıla bilər.Tam assosiativ keş
- hər hansı bir RAM xətti istənilən keş xəttinə uyğunlaşdırıla bilər.Çox assosiativ keş
- Keş yaddaşı bir neçə "banka" bölünür, onların hər biri birbaşa xəritələnmiş keş kimi fəaliyyət göstərir, beləliklə, RAM xətti bir mümkün keş girişinə deyil (birbaşa xəritələnmiş halda olduğu kimi) xəritələşdirilə bilər. ), lakin bir neçə bankdan birinə; Bank seçimi keşdə yerləşdirilmiş hər bir xətt üçün LRU və ya digər mexanizm əsasında həyata keçirilir.LRU - "ən uzun istifadə olunmayan" xəttin çıxarılması, yaddaş önbelleği.
İdeya
Keş səviyyələrinin sayını müəyyən etmək üçün keçidin aydın görünəcəyi yaddaşa daxil olma sırasını nəzərə almalısınız. Müxtəlif keş səviyyələri ilk növbədə yaddaşa cavab sürətində fərqlənir. Keş buraxılması halında, L1 önbelleği aşağıdakı yaddaş səviyyələrində məlumatları axtaracaq və məlumat ölçüsü L1-dən böyük və L2-dən azdırsa, yaddaşın cavab sürəti L2 cavab sürəti olacaqdır. Əvvəlki ifadə ümumi hallarda da doğrudur.Aydındır ki, önbellek buraxılışlarını aydın görəcəyimiz və müxtəlif məlumat ölçülərində sınaqdan keçirəcəyimiz bir test seçməliyik.
LRU alqoritmindən istifadə edərək işləyən dəst-assosiativ keşlərin məntiqini bilməklə, keşin "düşdüyü" bir alqoritm tapmaq çətin deyil, çətin bir şey yoxdur - xəttdən keçir. Effektivlik meyarı bir yaddaşa giriş vaxtı olacaqdır. Təbii ki, nəticəni orta hesabla almaq üçün onu dəfələrlə təkrarlayaraq xəttin bütün elementlərinə ardıcıl daxil olmaq lazımdır. Məsələn, bir xəttin önbelleğe sığdığı hallar ola bilər, lakin ilk keçid üçün xətti RAM-dən yükləyirik və buna görə də tamamilə qeyri-adekvat vaxt alırıq.
Mən addımlar kimi bir şey görmək istərdim, xətlər boyu gəzirəm müxtəlif uzunluqlar. Addımların xarakterini müəyyən etmək üçün birbaşa və assosiativ keş üçün xətt keçidinin nümunəsini nəzərdən keçirin.
Assosiativ keş
Məlumat ölçüsü keşin ölçüsünü aşdıqdan sonra,
Tam assosiativ keş hər yaddaşa girişi əldən verir.
Birbaşa önbellek
Müxtəlif xətt ölçülərinə baxaq. - növbəti dəfə xəttdən keçəndə prosessorun massiv elementlərinə daxil olmaq üçün sərf edəcəyi maksimum qaçırma sayını göstərir.
Gördüyünüz kimi, yaddaşa giriş vaxtı kəskin şəkildə deyil, məlumatların həcmi artdıqca artır. Məlumatın ölçüsü keş ölçüsünü aşdıqdan sonra, hər bir yaddaş girişində buraxılmış məlumatlar olacaq.
Buna görə də, assosiativ keş üçün addım şaquli olacaq, birbaşa keş üçün isə tədricən keş ölçüsünü iki dəfə artıracaq. Çox assosiativ önbellek, yalnız giriş vaxtı birbaşa olandan daha yaxşı ola bilmədiyi üçün orta bir vəziyyət, "qabar" olacaqdır.
Yaddaş haqqında danışırıqsa, onda ən sürətli keş yaddaşdır, ondan sonra əməliyyat yaddaşı, ən yavaşı dəyişdirmədir, gələcəkdə bu barədə danışmayacağıq. Öz növbəsində, müxtəlif keş səviyyələri (bir qayda olaraq, bu gün prosessorlarda 2-3 keş səviyyəsi var) fərqli sürət yaddaş reaksiyası: səviyyə nə qədər yüksəkdirsə, cavab sürəti bir o qədər yavaş olur. Və buna görə də, əgər bir xətt birinci səviyyəli önbelleğe yerləşdirilərsə (yeri gəlmişkən, bu, tamamilə assosiativdir), cavab müddəti birinci səviyyəli keşin ölçüsündən əhəmiyyətli dərəcədə böyük olan bir xətt üçün olduğundan daha az olacaqdır. Buna görə də, yaddaşın cavab vaxtının xətt ölçüsünə qarşı qrafikində bir neçə yayla olacaq - yaddaş cavabı yaylaları və müxtəlif keş səviyyələrinin səbəb olduğu yaylalar.
*Funksiya platosu - ( i:x, f(xi) - f(xi+1)< eps: eps → 0 }
Tətbiq etməyə başlayaq
Həyata keçirmək üçün biz C (ANSI C99) istifadə edəcəyik.Kod tez yazılmışdır, müxtəlif uzunluqlu, 10 MB-dan az olan xətlərdən adi keçid dəfələrlə yerinə yetirilmişdir. (Proqramın semantik yük daşıyan kiçik hissələrini təqdim edəcəyik).
Üçün (i = 0; i< 16; i++) { for (j = 0; j < L_STR; j++) A[j]++; }
Qrafikə baxırıq və böyük bir addım görürük. Ancaq nəzəri olaraq hər şey qaydasındadır. Buna görə də başa düşməlisiniz: niyə bu baş verir? Və bunu necə düzəltmək olar?
Aydındır ki, bu, iki səbəbə görə baş verə bilər: ya prosessorda yaddaş yaddaşı yoxdur, ya da prosessor yaddaşa girişləri çox yaxşı təxmin edir. Birinci seçim elmi fantastikaya daha yaxın olduğundan, hər şeyin səbəbi zənglərin yaxşı proqnozlaşdırılmasıdır.
Məsələ burasındadır ki, bu gün yüksək səviyyəli prosessorlar olmaqdan uzaq, məkanda yerləşmə prinsipinə əlavə olaraq, onlar da proqnozlaşdırırlar. arifmetik irəliləyiş yaddaşa daxil olmaq üçün. Buna görə də, yaddaş girişlərini təsadüfiləşdirmək lazımdır.
Təsadüfi massivin uzunluğu zənglərin böyük dənəvərliyindən xilas olmaq üçün əsas sətirin uzunluğu ilə müqayisə olunmalı və massivin uzunluğu ikinin gücü olmamalıdır, buna görə "üst-üstə düşmələr" baş verdi. - kənar göstəricilərlə nəticələnə bilər. Qranularlıq sabitini təyin etmək yaxşıdır, o cümlədən dənəvərlik əsas rəqəmdirsə, o zaman üst-üstə düşmələrin təsirindən qaça bilərsiniz. Və təsadüfi massivin uzunluğu sətrin uzunluğunun funksiyasıdır.
üçün (i = 0; i< j; i++) {
for (m = 0; m < L; m++) {
for (x = 0; x < M; x++){
v = A[ random[x] + m ];
}
}
}
Bundan sonra əvvəldən danışdığımız çoxdan gözlənilən “şəkil”i təəccübləndirdik.
Proqram 2 hissəyə bölünür - sınaq və məlumatların işlənməsi. Onu işə salmaq üçün 3 sətirdə bir skript yazmaq və ya əl ilə 2 dəfə işə salmaq sizə bağlıdır.
Linux-da size.file siyahısı
#daxildir
Windows-dan fayl ölçüsünün siyahısı
#daxildir
başqa k += 4*1024;
) 0 qaytarın; )
Ümumiyyətlə, düşünürəm ki, hər şey aydındır, amma bir neçə məqama aydınlıq gətirmək istərdim.
A massivi uçucu kimi elan edilir - bu direktiv bizə A massivinə həmişə daxil olacağına, yəni nə optimallaşdırıcı, nə də kompilyator tərəfindən “kəsilməməsinə” zəmanət verir. Onu da qeyd etmək lazımdır ki, bütün hesablama yükü vaxt ölçülməzdən əvvəl yerinə yetirilir ki, bu da fon təsirini azaltmağa imkan verir.
Fayl Ubuntu 12.04 və gcc 4.6 kompilyatorunda assemblerə tərcümə olunur - dövrlər saxlanılır.İkinci törəmənin sıfırdan böyük olduğu bütün nöqtələri tapırıq (bir az səhvlə, çünki ikinci törəmə ədədi olaraq hesablanmasından əlavə, çox səs-küylüdür). Funksiyanı keş ölçüsündə funksiyanın ikinci törəməsinin işarəsindən asılı olaraq təyin edirik. Funksiya ikinci törəmənin işarəsinin sıfırdan böyük olduğu nöqtələrdə 1 qiymətini, ikinci törəmənin işarəsi sıfırdan kiçik və ya sıfıra bərabər olduqda isə sıfır qiymətini alır.
“Uçuş” nöqtələri hər bir addımın başlanğıcıdır. Həmçinin, məlumatları emal etməzdən əvvəl, məlumatların mənasını dəyişdirməyən, lakin nəzərə çarpan səs-küy yaradan tək kənarları çıxarmaq lazımdır.
data_pr.c faylının siyahısı
#daxildir
başqa der_2[i] = 0;
// üçün daraq (i = 0; i
TestlərCPU/OS/kernel versiyası/kompilyator/kompilyasiya açarları hər bir test üçün göstəriləcək.
Intel Pentium CPU P6100 @2.00GHz / Ubuntu 12.04 / 3.2.0-27-generic / gcc -Wall -O3 size.c -lrt
L1 = 0,05 Mb- L2 = 0,2 Mb L3 = 2,7 Mb Hər şeyi sadalamayacağam
yaxşı testlər
, gəlin "Rake" haqqında danışaqGəlin "tırmık" haqqında danışaq
Dırmıq Intel Xeon 2.4/L2 = 512 kb/Windows Server 2008 server prosessorunda verilənləri emal edərkən aşkar edilib.
Problem, yaylaya çatma intervalına düşən nöqtələrin az olmasıdır, ikinci törəmədə sıçrayış görünməzdir və səs-küy kimi qəbul edilir;
Ən kiçik kvadratlar metodundan istifadə edərək bu problemi həll edə və ya yayla zonalarını müəyyən edərkən testlər keçirə bilərsiniz.
- Bu problemin həlli üçün təkliflərinizi eşitmək istərdim.
- İstinadlar
Makarov A.V. Kompüter arxitekturası və aşağı səviyyəli proqramlaşdırma.
Ulrich Drepper Yaddaş haqqında hər bir proqramçı nəyi bilməlidir
Keş tərtibatçıları böyük əsas yaddaşdakı potensial hər hansı bir hüceyrənin keşdə sona çata biləcəyi problemi ilə qarşılaşdılar. Əgər proqram tərəfindən istifadə edilən məlumatların işçi dəsti kifayət qədər böyükdürsə, bu o deməkdir ki, bir çox əsas yaddaş parçaları hər bir keş yeri üçün yarışacaq. Daha əvvəl bildirildiyi kimi, keş və əsas yaddaş arasında nisbətin 1-dən 1000-ə qədər olması qeyri-adi deyil. 3.3.1 Assosiativlik (Hər bir keş xəttinin istənilən yaddaş yerinin surətini saxlaya biləcəyi bir keşi həyata keçirmək mümkün olardı. Bu adlanır). Keş xəttinə daxil olmaq üçün prosessor nüvəsi hər bir keş xəttinin etiketlərini tələb olunan ünvanın etiketi ilə müqayisə etməlidir. Teq bütün ünvanı saxlamalı olacaq, ona keş xəttində ofset verilməyəcək (bu o deməkdir ki, 3.2-ci bölmədəki şəkildə göstərilən S dəyəri sıfır olacaq).
Bu şəkildə həyata keçirilən keşlər var, lakin hazırda istifadə olunan L2 keşlərinin ölçüsünə baxmaq bunun qeyri-mümkün olduğunu göstərir. Qeyd edək ki, 64B keş xətləri olan 4 MB keş 65,536 girişə malik olacaq. Adekvat performans əldə etmək üçün keş məntiqi bir neçə dövr ərzində bütün bu qeydlər arasından verilmiş etiketə uyğun olanı seçə bilməlidir. Belə bir sxemin həyata keçirilməsinin xərcləri çox böyük olardı.
Şəkil 3.5: Tam assosiativ keş yaddaşın sxematik təsviri
Hər bir keş xətti etiket müqayisəsini yerinə yetirmək üçün bir müqayisəçi tələb edir böyük ölçü(Qeyd edək ki, S sıfırdır). Hər bir əlaqənin yanındakı hərf bitlərdə əlaqənin enini göstərir. Heç bir şey göstərilməyibsə, əlaqə eni bir bitdir. Hər bir müqayisəçi hər biri T bit genişliyində olan iki dəyəri müqayisə etməlidir. Sonra, nəticəyə əsasən, müvafiq keş xəttinin məzmunu götürülməli və mövcud olmalıdır. Bunu etmək üçün, keş qutuları olduğu qədər O məlumat xətti dəstlərini birləşdirməlisiniz. Bir komparatorun həyata keçirilməsi üçün tələb olunan tranzistorların sayı çox olacaq, çünki komparator çox tez işləməlidir. İterativ müqayisəçi istifadə edilə bilməz. Müqayisə edənlərin sayına qənaət etməyin yeganə yolu iterativ etiket müqayisəsindən istifadə edərək onların sayını azaltmaqdır. Bu, iterativ müqayisələrin uyğun olmaması ilə eyni səbəbdən uyğun deyil: çox uzun çəkəcək.
Tam assosiativ keş kiçik keş ölçüləri üçün praktikdir (bəzilərində TLB keşi kimi). Intel prosessorları tam assosiativdir), lakin bu keş kiçik olmalıdır - həqiqətən kiçik. Söhbət maksimum bir neçə onlarla rekorddan gedir.
L1i cache, L1d cache və cache üçün daha çox yüksək səviyyədə fərqli yanaşma lazımdır. Edə biləcəyiniz tək şey axtarışınızı daraltmaqdır. Ən ekstremal halda, hər bir teq tam olaraq bir keş girişinə uyğunlaşdırılır. Hesablama sadədir: 65,536 girişi olan 4MB/64B keş üçün biz hər bir elementə birbaşa daxil ola bilərik və bunun üçün 6-dan 21-ə qədər ünvan bitlərindən (16 bit) istifadə edə bilərik. Aşağı 6 bit keş xətti indeksidir.
Şəkil 3.6: Birbaşa xəritələnmiş keşin sxematik təsviri
Şəkil 3.6-dan göründüyü kimi, belələrin həyata keçirilməsi birbaşa xəritələnmiş önbellek (birbaşa xəritələnmiş önbellek) tez və asan ola bilər. Bunun üçün yalnız bir komparator, bir multipleksor tələb olunur (teq və məlumatlar ayrıldığından bu diaqramda ikisi var, lakin bu, ciddi dizayn tələbi deyil) və bəziləri məntiqi dövrə etibarlı keş xətləri olan məzmunu seçmək üçün. Müqayisəli sürət tələblərinə görə mürəkkəbdir, lakin indi yalnız biri var; nəticədə, onu daha sürətli etmək üçün daha çox səy sərf edə bilərsiniz. Bu yanaşmanın əsl mürəkkəbliyi multipleksorlardadır. Sadə multipleksorda tranzistorların sayı O(log N) qanununa uyğun olaraq artır, burada N keş xətlərinin sayıdır. Bu məqbuldur, lakin bu, yavaş multipleksorla nəticələnə bilər, bu halda sürəti multipleksorlarda tranzistorlara investisiya qoymaqla və sürəti artırmaq üçün bəzi işləri paralelləşdirməklə sürəti artırmaq olar. Ümumi miqdar tranzistorlar keş ölçüsü ilə müqayisədə yavaş-yavaş böyüyəcək və bu, çox cəlbedici bir həlldir. Lakin bu yanaşmanın mənfi tərəfi var: o, yalnız proqramda istifadə olunan ünvanlar birbaşa xəritələşdirmə üçün istifadə olunan bitlərə nisbətən bərabər paylandıqda işləyir. Əgər belə deyilsə və adətən belədirsə, bəzi keş girişləri aktiv şəkildə istifadə olunur və buna görə də dəfələrlə boşaldılır, digərləri isə demək olar ki, istifadə olunmur və ya boş qalır.
Şəkil 3.7: Çox assosiativlik keşinin sxematik təsviri
Bu problem keş yaddaşdan istifadə etməklə həll edilə bilər çoxsaylı assosiativlik (assosiativ təyin edin). Çox assosiativlik keşi, bu həllərin çatışmazlıqlarının qarşısını almaq üçün tam assosiativlik keşinin və birbaşa xəritələnmiş keşin xüsusiyyətlərini birləşdirir. Şəkil 3.7 çox assosiativ keş dizaynını göstərir. Teqlər və məlumatlar üçün yaddaş dəstlərə bölünür, seçimi ünvana uyğun olaraq aparılır. Bu, birbaşa xəritələnmiş önbelleğe bənzəyir. Lakin çoxluqdakı hər bir dəyər üçün ayrıca elementdən istifadə etmək əvəzinə, eyni dəst az sayda dəyərləri keşləmək üçün istifadə olunur. Dəstin bütün elementləri üçün teqlər paralel olaraq müqayisə edilir ki, bu da tam assosiativ keşin işinə bənzəyir.
Nəticə, eyni vaxtda eyni təyin edilmiş nömrələrə malik ünvanların zəif və ya qəsdən seçilməsi səbəbindən qaçırılmalara kifayət qədər davamlı olan bir keşdir və keş ölçüsü paralel olaraq işləyə bilən müqayisəçilərin sayı ilə məhdudlaşmır. Keş yaddaşı artırsa (şəklə bax), o zaman satırların sayı deyil, yalnız sütunların sayı artır. Sətirlərin sayı yalnız keş assosiativliyi artdıqda artır. Bugünkü prosessorlar L2 önbelleği üçün 16-a qədər və daha yüksək assosiativlik səviyyələrindən istifadə edirlər. L1 önbelleği adətən 8-ci səviyyəyə təyin edilir.
Cədvəl 3.1: Keş ölçüsünün, assosiativliyin və keş xəttinin ölçüsünün təsiri
| Ölçü keş yaddaş L2 |
assosiativlik | |||||||
|---|---|---|---|---|---|---|---|---|
| Birbaşa ekran | 2 | 4 | 8 | |||||
| CL=32 | CL=64 | CL=32 | CL=64 | CL=32 | CL=64 | CL=32 | CL=64 | |
| 512 min | 27 794 595 | 20 422 527 | 25 222 611 | 18 303 581 | 24 096 510 | 17 356 121 | 23 666 929 | 17 029 334 |
| 1M | 19 007 315 | 13 903 854 | 16 566 738 | 12 127 174 | 15 537 500 | 11 436 705 | 15 162 895 | 11 233 896 |
| 2M | 12 230 962 | 8 801 403 | 9 081 881 | 6 491 011 | 7 878 601 | 5 675 181 | 7 391 389 | 5 382 064 |
| 4M | 7 749 986 | 5 427 836 | 4 736 187 | 3 159 507 | 3 788 122 | 2 418 898 | 3 430 713 | 2 125 103 |
| 8M | 4 731 904 | 3 209 693 | 2 690 498 | 1 602 957 | 2 207 655 | 1 228 190 | 2 111 075 | 1 155 847 |
| 16M | 2 620 587 | 1 528 592 | 1 958 293 | 1 089 580 | 1 704 878 | 883 530 | 1 671 541 | 862 324 |
Əgər bizim 4MB/64B keşimiz və 8 yollu assosiativliyimiz varsa, onda keşdə 8192 dəstimiz olacaq və keş dəstlərinə müraciət etmək üçün yalnız 13 teq biti tələb olunacaq. Keş dəstində hansı girişin (əgər varsa) ünvanlana bilən keş xəttini ehtiva etdiyini müəyyən etmək üçün 8 teq müqayisə edilməlidir. Bu çox şey üçün edilə bilər qısa müddət. Təcrübədən göründüyü kimi, bunun mənası var.
Cədvəl 3.1 bəzi proqramlar üçün L2 keş buraxılışlarının sayını göstərir (bu halda Linux nüvəsi tərtibatçıları tərəfindən ən vacib etalon hesab edilən gcc kompilyatoru) keş ölçüsü, keş xəttinin ölçüsü və çoxlu assosiativlik dəyəri kimi. Bölmə 7.2-də biz bu test üçün lazım olan keş yaddaşını simulyasiya etmək üçün alət təqdim edəcəyik.
Yalnız aydın deyilsə, bütün bu dəyərlər arasındakı əlaqə keş ölçüsünün bərabər olmasıdır.
keş xəttinin ölçüsü x assosiativlik x dəstlərin sayı
Ünvanların keş yaddaşa uyğunlaşdırılması kimi hesablanır
O = keş xəttinin ölçüsünün log2
S = dəstlərin sayının log2
3.2-ci bölmədəki rəqəmə uyğun olaraq.
Şəkil 3.8: Keş ölçüsü və assosiativlik səviyyəsi (CL=32)
düyü. 3.8 cədvəl məlumatlarını daha başa düşülən edir. Şəkil 32 bayta bərabər sabit ölçülü bir keş xətti üçün məlumatları göstərir. Müəyyən bir keş ölçüsü üçün rəqəmlərə baxsanız, görə bilərsiniz ki, assosiativlik əslində keş buraxılışlarını azaltmaqda uzun bir yol keçə bilər. 8MB keş üçün birbaşa xəritədən 2 tərəfli assosiativ keşə keçid keşin demək olar ki, 44%-nə qənaət edir. Çox assosiativlik keşindən istifadə edilərsə, prosessor birbaşa xəritələnmiş keş ilə müqayisədə daha böyük iş dəstini keş yaddaşında saxlaya bilər.
Ədəbiyyatda bəzən oxuya bilərsiniz ki, assosiativliyin tətbiqi keş ölçüsünü ikiqat artırmaqla eyni təsirə malikdir. Bu, 4 MB keşdən 8 MB önbelleğe keçid vəziyyətində göründüyü kimi, bəzi ekstremal hallarda doğrudur. Ancaq bu, əlbəttə ki, assosiativliyin sonrakı artması ilə doğru deyil. Məlumatlardan göründüyü kimi, assosiativliyin sonrakı artması əhəmiyyətli dərəcədə daha az qazanc verir. Bununla belə, biz bu faktı tamamilə nəzərdən qaçırmamalıyıq. Nümunə proqramımızda yaddaşın maksimum istifadəsi 5,6 MB-dır. Beləliklə, 8 MB keş ölçüsü ilə eyni keş dəstləri bir neçə dəfə (iki dəfədən çox) istifadə olunacaq. İş dəsti artdıqca, qənaət arta bilər, çünki gördüyümüz kimi, daha kiçik keş ölçüləri ilə assosiativlikdən istifadənin faydası daha çox olacaqdır.
Ümumiyyətlə, keş assosiativliyinin 8-dən yuxarı artması tək başlıq iş yüklərinə az təsir göstərir. Paylaşılan L2 önbelleğini istifadə edən çoxnüvəli prosessorların meydana çıxması ilə vəziyyət dəyişir. İndi, əsasən, eyni keşə daxil olan iki proqramınız var ki, bu da praktikada assosiativliyin faydasını ikiqat artırmalıdır (və ya dördnüvəli prosessorlar üçün dördqat). Beləliklə, nüvələrin sayı artdıqca, paylaşılan keşin assosiativliyinin də artacağını gözləmək olar. Bu qeyri-mümkün olduğu üçün (16-yollu assosiativliyi həyata keçirmək artıq çətindir), prosessor dizaynerləri paylaşılan L3 keşindən və ondan kənarda istifadə etməyə başlayacaqlar, L2 önbelleği isə potensial olaraq bəzi nüvə alt dəstləri tərəfindən paylaşılacaq.
Şəkil 3.8-də görə biləcəyimiz digər təsir keş ölçüsünün artırılmasının performansı necə yaxşılaşdırdığıdır. Bu məlumatlar işçi dəstinin ölçüsünü bilmədən şərh edilə bilməz. Aydındır ki, əsas yaddaş qədər böyük bir keş daha kiçik bir keşdən daha yaxşı nəticələr verməlidir, buna görə də ümumiyyətlə keş ölçüsünü artırmaq və əhəmiyyətli faydalar əldə etmək üçün heç bir məhdudiyyət yoxdur.
Yuxarıda qeyd edildiyi kimi, iş dəstinin maksimum ölçüsü 5,6 MB-dır. Bu dəyər maksimum fayda təmin edəcək yaddaşın ölçüsünü hesablamağa imkan vermir, lakin bu ölçüsü təxmin etməyə imkan verir. Problem ondadır ki, bütün yaddaş davamlı olaraq istifadə edilmir və buna görə də biz hətta 16M keş və 5.6M iş dəsti ilə mübahisə edirik (birbaşa ekran versiyası ilə müqayisədə 16MB 2 yollu keş-assosiativ keşin üstünlüyünü unutmayın). Ancaq əminliklə deyə bilərik ki, belə bir yükləmə ilə 32 MB önbelleğin üstünlüyü əhəmiyyətsiz olacaqdır. Ancaq kim dedi ki, işçi dəst dəyişməz qalmalıdır? Zamanla iş yükləri artdıqca, keş ölçüsü də artır. Maşın alarkən və nə qədər önbellek üçün ödəməyə qərar verərkən, iş dəstinin ölçüsünü ölçməyə dəyər. Bunun niyə vacib olduğunu Şəkildə görmək olar. 3.10.
Şəkil 3.9: Test zamanı istifadə olunan yaddaşın yerləşdirilməsi
İki növ test aparılır. Birinci sınaqda elementlər ardıcıllıqla işlənir. Test proqramı n göstəricisindən istifadə edir, lakin massiv elementləri bir-biri ilə əlaqəlidir ki, onlar yaddaşda göründükləri ardıcıllıqla keçsinlər. Bu seçim Şəkil 3.9-un aşağı hissəsində göstərilmişdir. Son elementdən gələn bir geri keçid var. İkinci sınaqda ( yuxarı hissəsiŞəkil) massiv elementləri təsadüfi ardıcıllıqla keçilir. Hər iki halda massiv elementləri tək-tək əlaqəli bir dövri siyahı təşkil edir.
Belə yaddaşda istənilən OP xətti keş yaddaşın istənilən yerində və digər xətlərlə istənilən kombinasiyada yerləşə bilər. CC1-CC4 kombinasiyalı müqayisə sxemləri (Şəkil 6.4) eyni vaxtda keşdə olan bütün sətir etiketlərini təhlil edir və onları prosessordan ünvan avtobusundan alınan ünvanla müqayisə edir. Keş hit baş verdikdə, xətt məlumat avtobusuna (DB) oxunur. Keş buraxılması halında, keş yaddaşındakı xətt OP-dən tələb olunan sətirlə əvəz olunur.
Bu yaddaşın üstünlüyü onun yüksək oxuma sürətidir. Dezavantaj hardware tətbiqinin mürəkkəbliyidir. Buna görə də, tam assosiativ keşlər ən çox az sayda sətir olan filial hədəf buferi kimi ixtisaslaşmış buferlərdə istifadə olunur.
3. Çox assosiativ yaddaş yaddaşı
Bu tip yaddaş yuxarıda müzakirə olunan ikisi arasında aralıqdır. O, birbaşa xəritələnmiş keşin sadəliyini assosiativ axtarış sürəti ilə birləşdirir.
Keş yaddaşı xətlərin ayrılmış alt çoxluqlarına (bloklarına) bölünür. Hər bir əsas yaddaş xətti yalnız bir keş alt dəstinə daxil ola bilər. Birbaşa xəritələmə blokları axtarmaq üçün istifadə olunur və tam assosiativ axtarış alt qrup daxilində axtarış üçün istifadə olunur. Keş alt dəstindəki sətirlərin sayı keşin özünün girişlərinin (portlarının) sayını müəyyən edir.
Əgər 2 n keş xətti 2 s ayrı-ayrı alt çoxluğa bölünürsə, onda RAM-in S aşağı dərəcəli bitləri assosiativ axtarışın hansı alt çoxluqda (indeksdə) aparılmalı olduğunu göstərir. Əsas yaddaş ünvanlarının ən əhəmiyyətli n-s bitləri etiketlərdir.
Əgər S=0 olarsa, onda tam assosiativ keş yaddaşına uyğun gələn bir alt çoxluq alırıq. Əgər S=n olarsa, onda biz 2 n alt çoxluq alırıq (yəni bir sətir - bir alt çoxluq). Bu birbaşa xəritələnmiş keş yaddaşdır. Əgər 1Sn-1 olarsa, onda bizdə set-assosiativ keş yaddaşımız var.
Şəkil 6.5-də S=1 olduğu keş nümunəsi göstərilir, yəni iki keş alt dəsti var. Prosessor tərəfindən yaradılan 0111 fiziki ünvan ən az əhəmiyyətli rəqəmə bərabər olan 1-ci indeksə və 011 teqinə bölünür. İndeksdən istifadə etməklə keş yaddaşında sətirlərin ikinci alt çoxluğu seçilir və sonra assosiativ axtarış aparılır. seçilmiş alt çoxluğun sətir teqləri. Tapılmış 7-ci sətir 011 etiketi ilə verilənlər avtobusuna (SD) ötürülür. Assosiativ axtarış bir həyata keçirilir 
CC1 və CC2 kombinasiyalı müqayisə sxemlərindən istifadə edərək müvəqqəti olaraq bütün teqlər üçün.
düyü. 6.5. Çox assosiativ önbellek
Müasir prosessorlar 4 və 8 girişli keş yaddaşdan istifadə edirlər. Onun daxilolmalarının sayının artması, etiketlər üçün assosiativ axtarışı təmin edən önbelleğin həmin hissəsinin aparat tətbiqinin mürəkkəbliyinin sürətlə artmasına səbəb olur.
Keş yaddaşda məlumatların qeyd edilməsi və dəyişdirilməsi xüsusiyyətləri. Keş uyğunluğu
Oxuma girişi həm önbelleğe, həm də RAM-a dərhal başlaya bilər. Daha sonra, məlumat önbellekten əskik olarsa, bu fakt müəyyən edildikdə, RAM giriş dövrünün bir hissəsi artıq tamamlanacaq və bu, performansı yaxşılaşdıra bilər. Məlumat önbellekdədirsə, RAM-a giriş dayandırıla bilər.
Yazma yolu ilə daxil olduqda iki üsuldan istifadə olunur: yazı yalnız keşdə və ya həm önbellekdə, həm də RAM-da eyni anda aparılır. Bu üsullara alqoritmlər deyilir tərs WB (Geriyə yaz) və vasitəsilə qeydlər WT (Write Through) müvafiq olaraq. Onlardan ikincisi daha sadədir, eyni zamanda daha yavaşdır, baxmayaraq ki, keş və RAM-da eyni məlumatın nüsxələrinin həmişə uyğun olmasına zəmanət verir. Ən erkən Intel prosessorları bu alqoritmdən istifadə edir.
DB-nin geri yazma alqoritmi daha sürətlidir. Məlumat RAM-a yalnız başqa OP səhifəsindən sətir verilmiş keş xəttinin yerinə köçürüldükdə və ya keşin məzmununu yeniləmək üçün əmr yerinə yetirildikdə ötürülür. Bu alqoritm daha diqqətli idarəetmə tələb edir, çünki eyni məlumatın nüsxələrinin keş və OP-də fərqli olduğu vaxtlar olur. Bundan əlavə, hər sətir keşdə olarkən dəyişmir. Heç bir dəyişiklik olmadıqda, sətri yenidən RAM-a yazmağa ehtiyac yoxdur. Adətən onlar etiket yaddaşında M (dəyişdirilmiş) bayrağından istifadə edirlər. Sətir ilkin olaraq keş yaddaşa yükləndikdə “0” vəziyyətinə, ona məlumat yazıldıqda isə “1”ə qoyulur. Keşdən sətir boşaldarkən, OP-yə yazmaq yalnız M bayrağı birə qoyulduqda yerinə yetirilir.
Yanlış baş verdikdə, keş nəzarətçisi əvəz etmək üçün bir xətt seçməlidir. Birbaşa ekran üçün aparat həlləri ən sadədir. Yalnız bir xətt vuruş üçün sınaqdan keçirilir və yalnız bu xətt dəyişdirilə bilər. Tam assosiativ və ya çox assosiativ keş təşkilatı ilə, buraxılmış halda namizədin seçilməli olduğu bir neçə sətir var. Bu problemi həll etmək üçün adlanan aşağıdakı xüsusi qaydalardan istifadə edin əvəzetmə alqoritmləri .
FIFO (First In First Out - ilk girən - birinci çıxar);
LRU (Ən Az İstifadə Edildi - digərlərinə nisbətən daha uzun müddət istifadə edilməmişdir);
LFU (Ən az istifadə olunur - daha az istifadə olunur);
Təsadüfi.
Birinci və sonuncu üsullar həyata keçirmək üçün ən sadədir, lakin onlar müəyyən bir keş xəttinin nə qədər tez-tez istifadə edildiyini nəzərə almırlar. Bu halda, çox yaxın gələcəkdə əldə ediləcək bir sıra silinə bilər. Bu üsullar üçün səhv ehtimalı ikinci və üçüncü ilə müqayisədə daha yüksəkdir.
FIFO alqoritmində keş yaddaşa ilk daxil olan xətt dəyişdirilmək üçün seçilir. Önbelleğe yeni yerləşdirilmiş hər bir sətir bu növbənin quyruğuna əlavə edilir. Alqoritm onun faktiki istifadəsini nəzərə almır. Məsələn, yüklənmiş ilk sətirlər bütün əməliyyat boyunca tələb olunan məlumatları ehtiva edə bilər. Bu, yenicə dəyişdirilmiş xəttə dərhal qayıtmağa səbəb olur.
LRU alqoritmi qeyd edir ki, ən uzun müddət istifadə olunmayan sətir silinmək üçün seçilməlidir. Hər dəfə cərgəyə daxil olanda onun vaxt damğası yenilənir. Bu, əhəmiyyətli xərclərlə nəticələnə bilər. Bununla belə, LRU alqoritmi praktikada ən çox istifadə olunur. Dezavantaj ondan ibarətdir ki, proqram bir çox sətirləri əhatə edən böyük bir döngədən keçirsə, ən uzun müddətə daxil olmayan sətir əslində növbəti istifadə olunan xətt ola bilər.
LRU-ya yaxın olan alqoritmlərdən biri LFU alqoritmidir ki, ona görə də ən az istifadə olunan sıra silinir. Bu halda, hər bir xəttə girişlərin sayını hesablamaq və ona nəzarət etmək lazımdır. Belə çıxa bilər ki, ən az intensiv istifadə olunan sətir keş yaddaşına yenicə yazılmış və yalnız bir dəfə daxil olan (digər xətlərə daha çox daxil olan) xəttdir. LFU alqoritminin dezavantajı olan çıxarıla bilər.
Keş yaddaşının məzmunu prosessorun nəzarəti altında dəyişir. Bu halda əsas yaddaş dəyişməz qala bilər. Digər tərəfdən, xarici qurğular birbaşa giriş rejimində OP-dəki məlumatları dəyişə bilər. Bu halda keş yaddaşı öz məlumatlarını dəyişmir. Daha çox vəziyyət daha mürəkkəbdirçoxprosessorlu sistemlərdə, bir neçə prosessor paylaşılan yaddaşa daxil olduqda. Problem yaranır uyğunluq keş yaddaş.
Hesablama sistemi var ardıcıl yaddaş əgər hər hansı bir cihaz tərəfindən yerinə yetirilən ünvanda hər oxunma əməliyyatı sonuncunu hansı cihazın yazdığından asılı olmayaraq həmin ünvandakı sonuncu nüsxənin dəyərini qaytarırsa. Ardıcıllıq problemi geri kopyalama sistemləri üçün ən vacibdir. Onlar xüsusi protokollardan istifadə edirlər və hər bir etiketə məlumatın dəyişdirilməsi və etibarlılığı bayraqları əlavə olunur. Bu bayraqlar məlumatlara girişə icazə verir və ya rədd edir.
Əsas yaddaşı keş yaddaşa uyğunlaşdırmaq üçün məlum variantları üç növə endirmək olar: birbaşa, tam assosiativdir Və qismən assosiativdir.
At birbaşa ekran xətt ünvanı i blokun uyğunlaşdırıla biləcəyi keş yaddaş j OP-dən, unikal şəkildə ifadə ilə müəyyən edilir: i = j mod m, Harada m– keş yaddaşındakı sətirlərin ümumi sayı, yəni hər keş sətir nömrəsinə görə i hər biri göstərilir m ci blok OP, əgər sayma nömrəsi olan blokdan başlayırsa i.
Birbaşa xəritəçəkmə həyata keçirmək üçün sadə və ucuz xəritəçəkmə üsuludur. Onun əsas çatışmazlığı müəyyən OP bloklarına önbellekdə bir xəttin sərt təyin edilməsidir. Buna görə də, proqram eyni keş xəttinə uyğunlaşdırılmış iki müxtəlif blokdan sözlərə alternativ olaraq daxil olarsa, bu xətt daim yenilənəcək və hit ehtimalı aşağı olacaq.
Tam assosiativ ekran istənilən OP blokunun istənilən keş xəttinə yüklənməsinə imkan verən birbaşa çatışmazlıqları aradan qaldırmağa imkan verir. Assosiativ xəritələşdirmə yeni yazılmış blok üçün cərgənin seçilməsində çeviklik təmin edir. Bu metodun əsas çatışmazlığı ondan ibarətdir ki, bütün keş xətlərinin yoxlanılmasını tələb edir.
Qismən assosiativ xəritəçəkmə birbaşa və assosiativ xəritəçəkmə üsullarının üstünlüklərini özündə birləşdirən və müəyyən dərəcədə onların mənfi cəhətlərindən azad olan mümkün kompromislərdən biridir. Keş yaddaşı bölünür v hər birində olan alt çoxluqlar (dəstlər). k simlər (bir dəstdə olduğunu söyləmək adətdir k girişlər). Dəst və OP blokları arasındakı asılılıq birbaşa xəritələşdirmə ilə eynidir: dəstdə olan xətlərdən i, əlaqəyə uyğun olaraq yalnız əsas yaddaşın dəqiq müəyyən edilmiş blokları xəritələşdirilə bilər i = j mod v, Harada j– OP blokunun ünvanı. Eyni zamanda, modulun xətləri boyunca blokların yerləşdirilməsi ixtiyaridir və modul daxilində istədiyiniz xətti tapmaq üçün assosiativ prinsipdən istifadə olunur.
Həddindən artıq hallarda, nə vaxt v = m, k= 1, dəst-assosiativ xəritələşdirmə birbaşa birinə endirilir və nə vaxt v = 1,k = m- assosiativə.
Keş xəttinin və əsas yaddaş blokunun qarşılıqlı uyğunluğunun müəyyən edilməsi metodundan asılı olaraq üç keş yaddaş arxitekturası fərqləndirilir:
· tam assosiativ keş;
Birbaşa xəritələnmiş keş
· set-assosiativ keş.
IN tam assosiativ önbellekəsas yaddaşın hər hansı bloku istənilən keş xəttində yerləşə bilər və ya hər hansı bir keş xətti əsas yaddaşın istənilən blokuna xəritə verə bilər. Bu zaman keşlənmiş verilənlərin ünvanının ən əhəmiyyətli bitləri, sətirdə (blokda) verilənlərin mövqeyini (ofsetini) müəyyən edən bitlər çıxılmaqla, kataloqa daxil edilir və teq kimi istifadə olunur. Belə bir arxitekturada müəyyən ünvanda keşdə verilənlərin olub-olmadığını müəyyən etmək üçün həmin ünvanın yüksək dərəcəli bitlərini keş kataloqundakı bütün sətirlərin teqləri ilə müqayisə etmək lazımdır. Əgər belə bir müqayisə ardıcıllıqla aparılarsa, bu, çox vaxt aparacaq və keş yaddaşı aşağı performans səbəbindən mənasını itirir. Buna görə də belə bir müqayisə bütün teqlər üçün paralel aparılmalıdır. Bu tələb mümkün olan ən yaxşı şəkildə Cavab assosiativ yaddaşdır, yəni teq keşin assosiativ teq yaddaşında saxlanmalıdır.
Keş yaddaşının bu cür təşkili yalnız kiçik həcmlər üçün həll edilə bilən mürəkkəb bir hardware problemidir, yəni tam assosiativ keş, mürəkkəbliyinə görə böyük həcmə malik ola bilməz və bir qayda olaraq, köməkçi məqsədlər üçün istifadə olunur. Məsələn, Intel prosessorları qurmaq üçün peyqinq blokunda tam assosiativ keşdən istifadə edirlər assosiativ tərcümə buferi Ağır istifadə olunan səhifələrə girişi sürətləndirmək üçün nəzərdə tutulmuş TLB (Tərcümə Buferə baxın).
Bunun əksi memarlıqdır birbaşa xəritə önbelleği. Birbaşa xəritələnmiş keşdə, əsas yaddaşın xüsusi bloku yalnız ciddi şəkildə müəyyən edilmiş keş xəttində yerləşə bilər. Əsas yaddaş şərti olaraq səhifələrə bölünür, onların ölçüsü keş yaddaşının ölçüsü ilə üst-üstə düşür. Birbaşa xəritələşdirmə arxitekturası o deməkdir ki, hər bir keş xətti istənilən əsas yaddaş səhifəsindən yalnız ona uyğun olan bloku xəritələyə bilər. Eyni səhifə nömrələri olan bloklar eyni keş xəttində sona çatır. Nəticə etibarilə, hər bir keş xətti səhifə daxilində eyni nömrələrə malik bir çox əsas yaddaş blokları tərəfindən tələb olunur. Hər dəfə bir sıra bu bloklardan yalnız birinin surətini ehtiva edə bilər. Teq, bloku müvafiq keş xəttini tutan səhifənin nömrəsidir. Belə bir arxitekturada müəyyən bir ünvanda keşdə verilənlərin olub-olmadığını müəyyən etmək üçün bu ünvanın aid olduğu səhifə nömrəsini səhifədəki bloka uyğun gələn keş kataloqunda həmin xəttin etiketi ilə müqayisə etmək lazımdır. verilmiş ünvanı ehtiva edir, yəni yalnız bir şeyi müqayisə etmək lazımdır.
Birbaşa xəritələnmiş keş ən sadə aparat tətbiqinə malikdir, çünki keş yaddaşı adi birbaşa ünvanlanan yaddaş strukturuna malikdir və yalnız bir müqayisə cihazı lazımdır. Buna görə də, belə bir önbellek böyük ola bilər.
Tam assosiativ keş ilə birbaşa xəritəçəkmə önbelleği arasında aralıqdır set-assosiativ keş, əsasən müasir mikroprosessorlarda istifadə olunur. Set-assosiativ keşdə, birbaşa xəritələnmiş keşdən fərqli olaraq, hər bir əsas yaddaş bloku dəstdə birləşdirilmiş bir neçə keş xəttindən birini tələb edə bilər. Bu, uğurlu müraciət ehtimalını artırır. Sadələşdirilmiş şəkildə hesab edə bilərik ki, çoxluq-assosiativ keş bir neçə paralel və əlaqələndirilmiş birbaşa xəritələşdirmə kanallarıdır, burada eyni nömrələri olan sətirlər uyğun bir çoxluq təşkil edir. Əsas yaddaşın tələb olunan blokunu təmsil edən təyin edilmiş xətt bütün keş kanallarında paralel olaraq yerinə yetirilən etiketlərin müqayisəsi (assosiativ keşdə olduğu kimi) ilə müəyyən edilir. Hər bir dəstdə keşin itirilməsi halında yeni blokla əvəz olunacaq dəstin xəttini təyin edən əlaqəli atribut var. Əvəz edilmək üçün namizəd adətən ən uzun müddətə daxil olmayan cərgədir (LRU alqoritmi - Ən az istifadə olunan). Daha sadə, lakin daha az səmərəli olan FIFO dəyişdirmə alqoritmini və ya hətta təsadüfi dəyişdirmə alqoritmini istifadə etmək də mümkündür.