Most recent comments
Liveblogg nyttårsaften 2017
Tor, 11 months, 2 weeks
Jogging og blogging
Are, 1 year, 11 months
Liveblogg nyttårsaften 2016
Are, 1 year, 11 months
Reading in dark times
Are, 2 years
Moldejazz 2016
Camilla, 2 years, 4 months
Dørskilt
Karoline, 2 years, 5 months
Halifax
Tor, 2 years, 5 months
Sony Smartwatch 3 review
Tor, 2 years, 6 months
Numerikk, takk
Tor, 2 years, 6 months
Topp tur
Camilla, 2 years, 8 months
50 book challenge
Camilla, 11 months, 2 weeks
Ten years ago
Kurs for brukere
Tor
Controls
Register

Minne

Hva som egentlig foregår inne i en datamaskin har jeg aldri tenkt så mye på. Jeg mener, jeg kan naturligvis sette sammen en datamaskin kjøpt i deler, og jeg vet jo i grove trekk hva harddisken gjør, hva prosessoren gjør og hva minnet gjør. Jeg har tilogmed hørt om cacheminne, og vet sånn omtrent hva som er poenget med det. Jeg har imidlertid aldri tenkt så mye på de tekniske detaljene i hvordan ting ligger lagret i minnet, hvordan prosessoren henter ting fra minnet, og alt mulig slikt. Det viser seg imidlertid at det kan lønne seg ganske heftig å tenke bittelitt på slike ting.

Vi skal se på et eksempel. Jeg har skrevet følgende program i fortran:
program memorytest
    real, dimension(15000,15000)    :: m
    real, dimension(2)             :: time
    m = 0
    
    total_time = etime(time)    
    do i = 1, size(m, 1)
        do j = 1, size(m, 2)
            k = m(j,i)
        end do
    end do
    total_time = etime(time) - total_time
    print*, total_time
    
    total_time = etime(time)    
    do i = 1, size(m, 1)
        do j = 1, size(m, 2)
            k = m(i,j)
        end do
    end do
    total_time = etime(time) - total_time
    print*, total_time
end program memorytest

For de som er så heldige at de ikke leser fortran kan jeg fortelle hva dette programmet gjør. Først lager det et kvadratisk array, med 15000 x 15000 tall, og setter alle disse tallene til 0. Dette arrayet tar opp ganske nøyaktig 900 MB i minnet. Deretter looper programmet over alle elementene i arrayet på to forskjellige måter. Først tar det for seg arrayet radvis, deretter kolonnevis. Det som viser seg når man kjører dette programmet er at det er ganske stor forskjell på hvor lang tid disse to måtene tar. På laptopen min tar den første 1,03 sekunder, den andre 20,3 sekunder. En forskjell på en faktor 20, bare ved å endre hvilken vei man går gjennom arrayet.

Grunnen til at det er slik er naturligvis at minnet ikke ser på et kvadratisk array som et kvadratisk array, men som en lang streng med tall. Den første operasjonen jeg gjør her passer med måten dataene ligger i minnet, slik at man bare kan dure gjennom tallene i rekkefølge, og her skjer det sikkert også noe smart med cachen. Den andre operasjonen passer derimot dårlig med minnet. Den begynner med å se på posisjon 1 i minnet, deretter ser den på posisjon 10001, deretter 20001, ogsåvidere, helt til den kommer til enden og begynner på nytt på posisjon 2, 10002, 20002, ogsåvidere. Det gjør at prosessoren må rote borti minnet mye oftere, da det ikke bare er å hente inn en blokk fra minnet til cachen, og dermed går det mye, mye tregere.

Såh. Det var den spennende historien om hvordan det faktisk kan lønne seg å vite litt om hva som foregår i bakgrunnen når man programmerer. I alle fall når man prøver å løse et ligningsystem der koeffisientmatrisen alene fyller flere gigabyte i minnet.

-Tor Nordam
Are, Eivind likes this

Comments

Knut,  08.11.10 16:23

vil du ikke se på posisjon 1, 15001, 30001, osv?
Tor,  08.11.10 17:43

Jo, du har naturligvis helt rett. Jeg hadde tenkt å gjøre arrayet 10000 x 10000, men så ombestemte jeg meg.

Are,  08.11.10 21:55

Cred! Det er farlig å kode for lavnivå. All den makten i programmererens hender!
Tor,  08.11.10 22:23

Det er sant. Og det er nok sikkert noe av grunnen til at Fortran 95 har slike nyskapende features som at man kan legge sammen et array og en float og få det resultatet man venter, uten å måtte skrive alle løkkene selv.
B,  10.11.10 21:35

http://www.visitusers.org/index.php?title=C_vs_Fortran_memory_order

Her er det en ganske fin wiki på akkurat dette temaet.

Har du ikke kjøpt deg et sint grafikkort og begynt å bruke CUDA eller lignende enda?
Tor,  10.11.10 22:54

Hvor mye minne får man på et grafikkort igjen? 1 GB eller noe slikt? Det er nok et par størrelsesordener for lite for det vi sysler med akkurat nå. Men jeg kunne definitivt tenke meg å lære CUDA.
Tor,  18.10.11 10:58

En dag i forrige uke kuttet jeg tiden det tar å sette opp ligningsystemet i simuleringskoden vår med 40% ved å huske poenget i denne artikkelen, nemlig at det spiller en rolle i hvilken rekkefølge du leser fra minnet.

Det var riktignok litt mer intrikat enn dette eksempelet, da det var snakk om et tredimensjonalt array som skrives på en måte og leses på en annen, men likevel. Pinlige greier.