cachelokalointia

Cachelokalointi tarkoittaa sitä, miten ohjelman muistiviittaukset hyödyntävät prosessorin välimuistien rakennetta. Hyvä cachelokalointi parantaa suoritustehoa, koska välimuistin osumat pienentävät pääydinväliä ja megavälistä muistia kuormittavan liikenteen tarvetta.

Kaksi päätyyppiä on aikainen paikallisuus (temporal locality) ja tilallinen paikallisuus (spatial locality). Aikainen paikallisuus tarkoittaa sitä, että äskettäin käytetty data todennäköisesti palataan pian. Tilallinen paikallisuus tarkoittaa, että muistipaikkoja lähellä toisiaan käytetään todennäköisemmin peräkkäin.

Välimuistien hierarkiassa on L1-, L2- ja L3-välimuistit, jotka ovat pieniä mutta nopeita muistitasoja. Välimuistin rivin koko vaikuttaa siihen, kuinka monta muistipaikkaa siirretään kerralla. Välimuistin osumista käytetään sanaa osuma, ja jos dataa ei ole välimuistissa, syntyy missi. Missit jaetaan tyypillisesti pakkohauksiin (compulsory), kapasiteettihäviöihin (capacity) ja ristiriitatuloksiin (conflict).

Optimoitavaa löytyy ohjelmoinnissa ja tietorakenteissa. Suosi dataa, joka sijaitsee peräkkäin muistissa (contiguous), ja käy läpi dataa lineaarisesti. 2D-matriiseissa muistijärjestelmä vaikuttaa suuresti: C-kielessä muistialue on rivisuunnassa row-major, joten rivin sisäinen läpikäynti on hyvin localityä; kolumnin suuntaan kiertäminen voi heikentää sitä. Käytä tilaintia, kuten loop tiling/blocking ja data-Stridea, jolla tiedot lasketaan ja ladataan pienissä osissa.

Cachelokalointi vaikuttaa erityisesti suurille datajoukoille, iteratiivisille laskuille ja data-keskeisille ohjelmille. Oikea layout ja pääsykaavat voivat vähentää välimuistihäviöitä ja parantaa suorituskykyä merkittävästi.