Кешэнд ээлтэй програм бичих нь: 10 дахин хурдан програм бичих үү(Writing cache friendly program)

ulziikhishig

• 2025-03-26
• cache, faster_prgamming, locality, memory_hierarchy, кеш, код бичих, программчлал

Компьютерын системд тооцоолол маш хурдан явагддаг гэдгийг та мэдэх үү? Гэвч компьютер ихэнх цагаа өгөгдлөө зөөвөрлөх хуулах болон шилжүүлэхэд алддаг. Яг л Улаанбаатарын түгжрэлд хүмүүс ажлаа хийж биш ажил руугаа очих буцахдаа хамаг цагаа зарцуулдаг шиг.

Яагаад кэш чухал гэж?

Кеш гэх ойлголтыг тайлбарлахаас өмнө эхлээд энгийн нэгэн программ хэрхэн ажилладгийг авч үзье л дээ. Код бичдэг хүн бүрийн анхны код болсон “hello world” гэж хэвлэх программ бичсэн гэж бодъё. Та программаа ажиллуулахаар дуудах үед (жишээ нь: ./hello) командыг бичих үед shell программ дискээс таны компайлдсан exe кодыг secondary memory (disk) нээс main memory (RAM ) -руу зөөнө. Түүнчлэн процессор тухайн кодыг ажиллуулах үед instruction буюу таны бичсэн командууд дискээс cpu – руу зөөгдөнө. Мэдээж бидний бичсэн “hello world” текст маань хүртэл secondary memory-нд хадгалагдах тул бас л регистрүүд рүү зөөгдөнө. Бид компьютер яагаад ихэнх цагаа өгөгдлөө зөөвөрлөхөд алддагийг харлаа.

Тэгвэл энэхүү асуудлын шийдэл юу вэ?

Физикийн хуулийн дагуу хэрвээ та их хэмжээний хадгалах төхөөрөмж ашигламаар байвал удаан байна. Харин хурдан хадгалах төхөөрөмж нь бага өгөгдөл хадгална. Гэвч хүмүүсийн хүсэл бол хурдан бас их багтаамжтай төхөөрөмж. Тэгвэл том санах ой дунд жижиг санах ойг байршуулах гайхалтай санааг анх Maurice Wilkes гэх эрхэм 1965 онд хэрэгжүүлсэн.

Энэхүү санаа нь бидний бодит амьдралтай адилхан маш энгийн санаа юм. Яг л номын сан болон ширээний тавиуртай адилхан. Та номоос эшлэл харах болгондоо номын сангийн тавиур руу очиж харахын оронд хэрэгтэй номуудаа ширээн дээрээ авчирч тавиад харж болно шүү дээ. Кеш маань компьютерт ширээний тавиурын үүрэгтэй ажилладаг.

Кеш санах ойн түвшнүүд

Кеш санах ой нь ерөнхийдөө дараах гурван түвшинд ангилагдана:

1. L1 (Level 1) Кеш – Процессорт хамгийн ойр байрладаг бөгөөд хамгийн хурдан ажилладаг. Гэвч багтаамж багатай (ихэвчлэн 32KB-512KB).
2. L2 (Level 2) Кеш – L1 кешээс илүү том хэмжээтэй боловч арай удаан хурдтай. Энэ нь ихэвчлэн 256KB-8MB багтаамжтай байдаг.
3. L3 (Level 3) Кеш – L2 кешээс илүү том бөгөөд ихэвчлэн бүх процессорын цөмүүдийн хооронд хуваалцагддаг. Багтаамж нь 4MB-64MB хүрдэг.

Кеш хэрхэн ажилладаг вэ?

Кеш нь мэдээж санах ойгоос бага хэмжээтэй тиймээс CPU хүссэн мэдээлэл бүр нь кеш дотор байх нь боломжгүй зүйл юм. Тиймээс кеш дотор CPU -ний хүссэн мэдээлэл байхгүй бол санах ойгоос кэйш рүү зөөж эргүүлээд кэйшнээс CPU рүү зөөнө. Ингээд бодохоор бүр улам удаашруулж байгаа юм шиг санагдаж магадгүй. Гэхдээ та locality буюу нутагшилтыг ойлговол кешлэх нь ямар их үр ашгаа өгөхийг ойлгоно.

• Cache hit – CPU кешнээс хайсан өгөгдлөө олсон тохиолдолдлыг нэрлэдэг.
• Cache miss – CPU кешнээс хайсан өгөгдлөө олоогүй тохиолдлыг хэлнэ.

Locality буюу Нутагшил

Компьютерын системийн хамгийн чухал ойлголтуудын нэг юм. Хэрвээ та дээр дурдсан санах ойн шатлалыг ойлгосон бол сайн нутагшилтай программ бичиж чадна. Ер нь locality гэдэг нь маш энгийн ойлголт юм.

• 1. Нэг ашиглагдсан өгөгдөл ойрын хугацаанд дахин ашиглагддаг.
• 2. Тухайн ашиглагдсан өгөгдлийн хөрш өгөгдлүүд рүү CPU дараалан хандана.

Ихэнх программууд өөрөө цаанаасаа нутагшил сайтай байдаг. Жишээ нь та тоглоом тоглож байлаа гэж бодоход таны тоглоомын дүр нэг зураглалаас нөгөө рүү шилжихдээ гэнэт өөр болж хувирах үзэгдэл бага. Ихэвчлэн тухайн байрлалдаа байсаар эсвэл хажуу тийшээ жаахан хөдлөх гэх мэтчилэн ажилладаг.

Нутагшил сайтай програм бичих нь

Нутагшил сайтай программ бичсэнээр олон программын хурдыг хэд дахин сайжруулах боломжтой. Ингэхийн тулд та өөрийн ашиглаж буй кэшний хэмжээг тооцоолоход л хангалттай. Тэгээд та хэрхэн өгөгдлүүд рүүгээ хандвал кешэнд аль хэдийн байгаа өгөгдлүүдийг онох вэ? гэж бодож бичих хэрэгтэй гэсэн үг.

Дүгнэлт

Нутагшилт сайтай программ бичдэг программистууд тийм ч олон байдаггүй. Яахав бага хэмжээний өгөгдөл дээр энэ нь нэг их үр дүнгээ өгөхгүй нь үнэн. Гэхдээ энэхүү ойлголтын үргэлж бодолцож байх нь таны программын хурдыг хэд ч дахин ( өгөгдөл болон кэшний хэмжээнээс хамаарна. ) сайжруулах боломжтой.

Доорх бичлэгээс хэрхэн нутагшил сайтай программ бичихийг үзээрэй. Амжилт

Эх сурвалжууд 

Computer Systems: A Programmer’s Perspective, 3/E Randal E. Bryant and David R. O’Hallaron

https://www.geeksforgeeks.org/computer-organization-locality-and-cache-friendly-code

https://aws.amazon.com/caching

https://www.geeksforgeeks.org/cache-hits-in-memory-organization

нийтлэл бичсэн : М.Өлзийхишиг