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