Difference between revisions 1227106 and 1227141 on hywiki

next diff >
Քեշ ալգորիթմ
{{|Ընդհանուր քեշ ալգորիթմները |մանրամասն ալգորիթմները հատուկ են թջավորմանը |Էջի փոխարինման ալգորիթմ |մանրամասն ալգորիթմները հատուկ են CPU և RAM միջև եղած քեշին |CPU քեշ}}

  [[հՀամակարգչային]], '''քեշ ալգորիթմներ''' (նաև կոչվում են''փոփոխվող ալգորիթմներ'' կամ ''փոփոխվող ծրագրեր'')  [[Օպտիմալացում (համակարգչային գիտության)|օպտիմալացնում]]են հրահանգների – [[ալգորիթմները]] – որը [[համակարգչային ծրագիրը]] կամ ամուր պահպանվող կառուցվածքը կարող է հետևել և կառավարել [[քեշ (համակարգչային)|քեշ]] տեղեկատվության պահպանմանը համակարգչում. Երբ քեշը լի է ,ալգորիթմը պետք է ընտրի, որը նյութեր է մերժում, որպեսզի տեղ ազատի  նորերի համար.

 Միջին հիշողության հղման ժամանակն է<ref name="ajsmith" />
: <math>T = m*T_m + T_h + E</math>
որտեղ
: <math>T</math> = միջին հիշողության տեղեկանքային ժամանակը
: <math>m</math> = բացթողման հարաբերակցություն = 1 - (զարկի հարաբերակցություն)
: <math>T_m</math> = այն ժամանակահատվածն է երբ կատարվում է հիմնական հիշողության մուտք զարկի առկայության դեպքում (կամ, բազմասանդղակային քեշ, կիրառվող հետագա ավելի ցածր քեշերի համար)
: <math>T_h</math>= թաքնված ընթացակարգ: ժամանակ , որ հղում է քեշը, երբ կա զարկ
: <math>E</math> = տարբեր երկրորդական ազդեցությունները, ինչպիսիք են հերթի հետեւանքները բազմագործոնային համակարգերում

  Կան քեշի հիմնավորման երկու հիմնական ցուցանիշները :
Թաքնված ընթացակարգը, և զարկի հարաբերությունը.
Կան նաև մի շարք երկրորդական գործոններ որոնք ազդում են քեշի կատարման վրա .<ref name="ajsmith" >
Alan Jay Smith.
"Design of CPU Cache Memories".
Proc. IEEE TENCON, 1987.
[http://www.eecs.berkeley.edu/Pubs/TechRpts/1987/CSD-87-357.pdf]
</ref>

  "Զարկի հարաբերությունը" թույլ է տալիս հասկանալ ինչպես գտնել փնտրվող տարրը.
  Առավել արդյունավետ է փոխարինման ծրագիրը չկորցնելով ավելի օգտակար տեղեկատվությունը բարելավվելու նպատակով զարկի մակարդակը(վերցնենք քեշի չափը ).

  "Թաքնված ընթացակարգը"  քեշը ներկայացնում է, թե որքան ժամանակ է պահանջվում , որպեսզի քեշը կարողանա  վերադառցնել այդ տարրը(երբ այնտեղ զարկ կա).
  Արագ փոխարինման ընթացակարգը, որպես կանոն, չկորցնում պակաս ինֆորմացիայի օգտագործումը  կամ, որոշ դեպքերում անմիջապես արտացոլում է քեշը,ոչ մի ինֆորմացիա,չի նվազում  անհրաժեշտ ինֆորմացիայի թարմացման ժամանակ .

  Յուրաքանչյուր փոխարինման ընթացակարգ փոխզիջում է զարկի հարաբերության և թաքնված ընթացակարգի միջև.

Չափումները "զարկի հարաբերության" սովորաբար իրականացվում է [[համակարգչային հատուկ ծրագրի (համակարգչային)|համակարգչային հատուկ ծրագրի]] ծրագրերով.
Փաստացի զարկի հարաբերակցությունը տատանվում է լայնորեն մեկ դիմումի համար.Զարկի հարաբերակցությունը մոտ է զրոյին, քանի որ յուրաքանչյուր քիչ տվյալների հոսք կարդում է միայն առաջին անգամ (պարտադիր բացթողման), որն օգտագործվում է, ապա երբեք չի կարդում կամ չի գրում . 
Նույնիսկ շատ վատ, քեշ ալգորիթմները (մասնավորապես, ՎԱԿ) թույլատրում են այս հոսքային տվյալները լրացնել քեշը , դուրս է մղում քեշ տեղեկատվությանը, որը պետք է օգտագործվի ավելի ուշ (քեշ աղտոտում).
<ref>
Paul V. Bolotoff.
[http://alasir.com/articles/cache_principles/ "Functional Principles of Cache Memory"].
2007.
</ref>

==Օրինակներ==
=== Բալադիի Ալգորիթմներ ===
  ''Շատ''արդյունավետ է քեշ ալգորիթմներից ամենաարդյունավետը տեղեկության դուրս բերման համար որի իրագործմանհամար երկար ժամանակ անհրաժեշտ չե . Սրա լավագույն արդյունքը կոչվում է [[ Բելադիի|Բելադիի]]' օպտիմալ ալգորիթմ կամ [[Էջի_անցման_ալգորիթմ# _Տեսական_օպտիմալ_էջի_անցման_ալգորիթմ| գուշակման ալգորիթմ]].Քանի որ, ընդհանուր առմամբ, կարելի է կանխատեսել, թե որքան հեռու են futlure տեղեկատվությունը անհրաժեշտ է, դա ընդհանուր առմամբ պետք չի իրագործել գործնականում .Գործնականում նվազագույնը կարող է հաշվարկվել միայն փորձերի քանակով, եւ կարելի է համեմատել արդյունավետությունը, ըստ էության, ընտրված քեշ ալգորիթմի .

=== Նվազագույն Վերջերս Օգտագործված ===
'''Նվազագույն Վերջերս Օգտագործված''' (ՆՎՕ): հեռացնում է ոչ վաղուց օգտագործված առաջին էլեմենտները. Այս ալգորիթմը պահանջում է պահել ու հետևել, թե ինչ էր, երբ, որը թանկ է, եթե մեկն ուզում է, որպեսզի համոզվենք, որ ալգորիթմը միշտ հեռացնում է ''որ''նվազագույն վերջերս օգտագործված  ենթակետ. Ընդհանուր իրականացման  տեխնիկան պահանջում է պահելու "չափային բիթերը"  քեշ-գծերի և հետևել "Նվազագույն Վերջերս Օգտագործված" քեշ-գծերի հիման վրա չափային-բիթեր. Նման ծրագրի իրականացման, ամեն անգամ երբ քեշ-գիծը օգտագործվում է, ամեն անգամ երբ Cache-line օգտագործվումամ է,այլ քեշ-գծերի չափային փոփողությունները . ՆՎՕ իրականում [[թջի_փոփոխման_ալգորիթմ#Տարբերակները_ _ՆՎՕի|իրականում քեշային ընտանիքի ալգորիթմ է ]] անդամների հետ, այդ թվում `: [http://www.vldb.org/conf/1994/P439.PDF 2Q]  Թեոդոր Յոնսոնի և Դենիս Սաշայի կողմից և ՆՎՕ/Կ  Փաթ Օ'Նելիի, Բեթի Օ'Նելիի և Ժեռառդ ՈՒեիքումի կողմից.

===Վերջերս Օգտագործված ===
'''Վերջերս Օգտագործված''' (ՎՕ): հեռացնում է , ի տարբերություն ՆՎՕ, առավել վերջերս օգտագործված նյութերից առաջինը. Այս արդյունքների ներկայացրել է VLDB 11 - րդ համաժողովին , Չոուն և Դեվիթը նշել են որ "Երբ ֆայլը բազմիցս սկանավորվել է [Հաջորդական Ցիկլ]տեղեկանք օրինակը , ՎՕ ամենալավ փոխարինման ալգորիթմն է."<ref>Հոնգ-Թայի Չոու և Դավիդ Ջ. Դեյվիթ. [http://www.vldb.org/conf/1985/P127.PDF An Evaluation of Buffer Management Strategies for Relational Database Systems.] VLDB, 1985.</ref> Հետագայում այլ հետազոտողներ ներկայացնելով, 22 - րդ VLDB ասուլիսում նշել են,որ պատահական մուտքի նշաններով ու կրկնվող նմանակներով ավելի մեծ հավաքածուների  (երբեմն հայտնի է որպես հրահանգների փուլային մուտք ) ՎՕ քեշ ալգորիթմները ավելի շատ զարկեր քան ՆՎՕ ի շնորհիվ իրենց միտումով պահպանել հին տվյալները.<ref>Սաուլ Դառ, Միշել Ջ. Ֆռանկլին, Բոռն Դոռ Ջոնսոն, Դիվես Սռիվաստավա, և Միշել Տան. [http://www.vldb.org/conf/1996/P330.PDF Semantic Data Caching and Replacement.] VLDB, 1996.</ref> ՎՕ ալգորիթմները կարող են առավել օգտակար իրավիճակներում, որտեղ շատ նյութ է,այնտեղ այնքան ավելի հավանական է, որ պետք է օգտվել.

=== Կեղծ-Նվազագույն Վերջերս Օգտագործված  ===
'''[[Pseudo-Նվազագույն Վերջերս Օգտագործված ]]''' (ԿՆՎՕ): [[CPU քեշից]] մեծ [[CPU քեշ#ասոցիատիվ|ասոցիատիվ]] (հիմնական >4 ճյուղ), իրականացման ծախսեր Նվազագույն Վերջերս Օգտագործված դառնում է արգելական.Շատ պրոցեսորների քեշեր, մի սխեմա է, որը գրեթե միշտ հեռացնում է մեկը գոնե վերջերս օգտագործված ապրանքներից . Այնպես որ շատ Պրոցեսորներ դիզայներներռեժիմ ընտրելը Կեղծ Նվազագույն Վերջերս Օգտագործված ալգորիթմ է, որը միայն պետք է մեկ փոքր - ինչ  քեշ կետի աշխատանքին .
ԿՆՎՕ սովորաբար ունի մի փոքր ավելի վատ բացթողման հարաբերակցությունը, ունի մի փոքր ավելի լավ թաքնված ւնթացակարգի, և օգտագործում է մի փոքր ավելի քիչ էներգիա քան Նվազագույն Վերջերս Օգտագործվածը.
[[Պատկեր:քեշ,ասոցիատիվ-լցնել-միասին.png|thumb|450px|Որ հիշողության վայրերում, կարող  են վերցված լինել  քեշից, որը քեշ տեղեր է]]

===Պատահական Փոփոխություն ===
'''Պատահական Փոփոխություն''' (ՊՓ):պատահականորեն ընտրել առաջարկվող ենթակետ,  մերժել այն դարձնել տեղ , երբ անհրաժեշտ է. Այս ալգորիթմը չի պահանջում պահելու որևէ տեղեկություն մուտքի պատմության մասին. Իր պարզությամբ, այն օգտագործվել է [[ARM ճարտարապետություն|ARM ճարտարապետություն]].<ref>[http://infocenter.arm.com/help/topic/com.arm.doc.set.cortexr/index.html ARM Cortex-R պրոցեսորների վերամշակման ձեռնարկ]</ref>Այն ընդունում է արդյունավետ ստոկաստիկ մոդելավորում .<ref>Արդյունավետ մոդելավորում ալգորիթմ համար պահոցն պատահական փոխարինող քաղաքականությունն է [http://www.springerlink.com/index/L324G2U075540681.pdf]</ref>

=== Հատվածային Նվազագույն Վերջերս Օգտագործված ===
''' Հատվածային Նվազագույն Վերջերս Օգտագործված''' (ՀՆՎՕ): Հատվածային Նվազագույն Վերջերս Օգտագործված քեշը բաժանված է երկու հատվածների.Փորձնական հատվածն ու պահպանվող հատված. Գծեր յուրաքանչյուր հատվածում  պատվիրված են ամենաշատն առնվազն վերջերս օգտվածն է.     Քեշի բացակա տվյալների ավելացումն է  և վերջիններս հասանելի են վերջում փորձնական հատվածին. Զարկեր են հանվել, որտեղ էլ որ նրանք ներկայումս գտնվում և հավելեց, որ վերջիններս հասանելի են  պահպանվող հատվածի ավարտին.Գծեր պահպանվող հատվածում են այսպիսով օգտագործվում են առնվազն երկու անգամ .Վերջավոր պաշտպանված հատվածն է  . որ միգրացիան մի տող է փորձնական հատվածում դեպի պաշտպանված հատվածում կարող է ստիպել միգրացիա  Նվազագույն Վերջերս Օգտագործված գիծը պահպանվող հատվածում առավել վերջերս օգտագործվածն է (Վերջերս Օգտագործված) ավարտվեց փորձնական հատվածին տալով այս տողում ևս մեկ հնարավորություն  մուտք գործել նախքան փոխարինվել.Չափը սահմանափակում է պահպանվող հատվածում  ՀՆՎՕ պարամետրը, որը տատանվում ըստ 1 / O ծանրաբեռնվածություն հրահանգների .Երբ տվյալները պետք է անտեսվեն  քեշը, տողեր է ձեռք բերել Նվազագույն Վերջերս Օգտագործված  փորձնական հատվածի վերջում.<ref>Ռամակռիշնա Կառեդլա, Ջ. Սփենսեռ Լովե, և Բռեդլի Գ. Ուեռռի.Քեշային սկավառակի համակարգ ստրատեգիա բարելավել  կատարումը .  [[Համակարգչային (ամսագիր)Համակարգչային|]], 1994.</ref>"

===Երկկողմանի Ասոցիատիվ Հավաքածու  ===
'''Երկկողմանի''' [[պրոցեսորային քեշ#Ասոցիատիվություն|ասոցիատիվ հավաքածու]]: բարձր արագություն [[պրոցեսորային քեշ]] որտեղ անգամ  Կեղծ-Նվազագույն Վերջերս Օգտագործված շատ դանդաղ. Հասցեն նոր կետում, որն օգտագործվում է հաշվարկել մեկը երկու հնարավոր քեշ տեղերում  ուր կարելի է գնալ.Նվազագույն Վերջերս Օգտագործված  որ երկուսը հեռացնի. Սա պահանջում է յուրաքանչյուր զույգ քեշ գծերից<!-- Ինչ վերաբերում է 2 - ճանապարհը խոտոր, ասոցիատիվ քեշորին? նրանք չեն , որոնք պահանջում են  յուրաքանչյուր տողում մեկ փոքր? -->,ցույց են տալիս, որ վերջերս օգտագործվածը գոնե երկուս էր   .

=== ՈՒղղորդված Քեշ ===
''' ՈՒղղորդված քեշ''': համար ամենաբարձր արագությամբ պրոցեսորներ քեշերը, որտեղ նույնիսկ 2 ճանապարհ սահմանված ասոցիատիվ քեշերը շատ դանդաղ են. Հասցեն նոր կետում օգտագործելու կարելի է  հաշվարկել մեկ վայրում ուր քեշը ուղարկի.Այն, ինչ կար մինչ այդ անտեսվեց .

=== Առավել Հաճախ Օգտագործվող ===
'''[[Առավել հաճախ օգտագործվող]]''' (ԱՀՕ): Առավել հաճախ օգտագործվողը հաշվում է որքան հաճախ է նյութը հարկավոր.Նրանք, որոնք օգտագործվում են հաճախ անտեսվում է.

=== Ցածր Ներկայացող Նորույթի Հավաքածու ===
'''[[Ցածր Ներկայացող Նորույթի Հավաքածու քեշքյին ալգորիթմը| Ցածր Ներկայացող Նորույթի Հավաքածու(ՑՆՆՀ) քեշային ալգորիթմ է ]]'''

===Հարմարվողական Փոփոխվող Քեշ ===
'''[[Հարմարվողական Փոփոխվող Քեշ]]''' (ՀՓՔ):<ref անուն=մեգիդդո>[[Նիմռոդ Մեգիդդո]] և Դառմենդս Ս. Մոդա. [http://www.usenix.org/events/fast03/tech/full_papers/megiddo/megiddo.pdf ARC: A Self-Tuning, Low Overhead Replacement Cache.] FAST, 2003.</ref> անընդհատ մնացորդները միջեւ ՆՎՕ եւ ԱՀԿ, բարելավել համակցված արդյունքը.
ՀՓՔ improves on ՀՆՎՕ օգտագործելով տեղեկատվություն վերջինս հեռացվի քեշի ապրանքներին դինամիկ հարմարեցնելով չափը պաշտպանված հատվածին և փորձնական հատվածին, ինչպես կատարել լավագույն օգտագործումը մատչելի քեշի տարածքում.

=== Ժամանակային Հարմարվողական Փոփոխություն ===
'''[[Ժամանակային Հարմարվողական Փոփոխություն]]''' (ԺՀՓ) համատեղում Հարմարվողական Փոփոխությոան քեշ (ՀՓՔ) և[[էջի_անցման_ալգորիթմ#Ժամանակային|Ժամանակային]]. ԺՀՓ ունի կատարումը համեմատելի է ՀՓՔ եւ էականորեն  թե ՆՎՕ ից եւ ժամանակայինից. Like ARC, ԺՀՓ ինքնուրույն-բարելավվում է, և չի պահանջում  օգտագործողի նշված հիանալի պարամետրերը.

=== Բազմակի Կապերով Քեշ Ալգորիթմ ===
'''[[ Բազմակի Կապերով(ԲԿ)Քեշ Ալգորիթմ ]]''':<ref անուն=Զոու>Յուանյուան Զոու, Ջեմս Փիլբին, և Կայ Լի. [http://static.usenix.org/event/usenix01/zhou.html The Multi-Queue Replacement Algorithm for Second Level Buffer Caches.] USENIX, 2002.</ref> (Յուանյուան Զոու, Ջեմս Փիլբին, և Կայ Լի կողմից ).

Քննարկման թեմաները:

* Տարբեր արժեքային տարրեր:պահպանիր տարրերը որոնք թանկ են ձեռք բերելու համար օրինակ այն տարրերը որոնք երկար ժամանակ են պահանջում .
* Ավելի շատ քեշ իրագործել: Եթե տարրերը տարբեր չափեր ունեն քեշը կարող է դուրս բերել մեծ տարրը ավելի փոքր տարրերի մասնատելու միջոցով.
* Տարրեր որոնք սպառվում են ժամանակին համընթաց: Որոշ քեշեր ինֆորմացիա են պարունակում (օրինակ  նորություն քեշերը, վեբ բրաուզերի քէշը,).Համակարգիչը կարող է մերժել տարրերը, քանի որ նրանք ժամկետանց են .Քեշի չափից կախված ալգորիթմի տարրերի բաց թողնումը կարող է լինել անհրաժեշտ.

Տարբեր ալգորիթմներ կա նաեւ պահպանելու [[քեշ coherency]]. Սա վերաբերում է միայն այն իրավիճակին, որտեղ ''բազմապատիկ'' անկախ քեշեր են օգտագործվում  ''նույն''տվյալների (օրինակ, բազմակի տվյալների բազաների սերվերների թարմացում մեկ ընդհանուր տվյալների ֆայլով ).

==Տես ամբողջը==
* [[Cache (computing)]]
* [[Cache-oblivious algorithm]]
* [[CPU cache]]
* [[Page replacement algorithm]]
* [[Locality of reference]]
* [[Distributed cache]]

==References==
<references/>

==Ինտերնետային կայքեր==
* [http://www.usenix.org/events/usenix01/full_papers/zhou/zhou_html/node3.html Definitions of various cache algorithms]
* [http://www.cs.umd.edu/class/spring2003/cmsc311/Notes/Memory/fully.html Fully associative cache]
* [http://www.cs.umd.edu/class/spring2003/cmsc311/Notes/Memory/set.html Set associative cache]
* [http://www.cs.umd.edu/class/spring2003/cmsc311/Notes/Memory/direct.html Direct mapped cache]

{{DEFAULTSORT:Cache Algorithms}}
[[Category:Cache (computing)]]
[[Category:Memory management algorithms]]

[[de:Cache-Algorithmus]]
[[fr:Algorithmes de remplacement des lignes de cache]]
[[id:Least Recently Used]]
[[ja:キャッシュアルゴリズム]]
[[ru:Алгоритмы кэширования]]
[[tr:Önbellek algoritmaları]]
[[zh:快取文件置換機制]]