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

GotoBLAS

Når man sysler med litt over middels krevende utregninger er det essensielt at ting går fort. En av de enkleste tingene man kan gjøre for å få ting til å gå fort er å ikke skrive sine egne rutiner. Noe må man naturligvis skrive selv, det er tross alt forskning vi driver med, men det er ingen grunn til å finne opp kruttet på nytt, som veilederen min liker å si. For eksempel, i problemet vi sysler med nå setter vi opp svære matriser, som vi så utfører operasjoner på. Vi må naturligvis sette opp matrisene våre selv, da dette er unikt for vårt problem, men det ville vært galskap om vi skulle skrive våre egne rutiner for matrisemultiplikasjon, for eksempel, da dette er en operasjon nesten alle som driver med numerikk må gjøre, og da det allerede er lagt ned utrolig mange årsverk i å skrive effektive rutiner.

BLAS (Basic Linear Algebra Subprograms) er en samling rutiner for å gjøre matrise- og vektoroperasjoner. Dette biblioteket kom ut første gang i 1979, og siden da har mange, mange mennesker lagt ned mange, mange timer i å optimere slike rutiner for ulike prosessorer. Grunnen til at det må optimeres for hver prosessor er at det å få disse tingene til å gå fort handler om at prosessoren må slippe å vente på minnet, og det igjen handler om å ha de riktige tingene i cachen til enhver tid. Hvis prosessoren må hente noe fra ram i stedet for fra cachen ryker nanosekundene fort, og selv nanosekunder blir mye når man har noen tusen milliarder av dem. Uansett, BLAS finnes, og med mindre du selger superdatamaskiner og dermed må lage din egen versjon, er det i grunnen ikke så mye å tenke på.

Kazushige Goto var imidlertid ikke fornøyd med å bare bruke noe noen andre hadde skrevet. I følge Paul Anton dreier det seg om en gal japaner som tenkte «Helvete! BLAS er så fordømt tregt! Det må da være mulig å gjøre dette bedre!», og som så satte seg ned og skrev tusenvis av linjer i assembly, og endte opp med noe som var vesentlig bedre enn vanlig BLAS for de fleste arkitekturer. Virkeligheten er bare marginalt mindre imponerende. Kazushige Goto jobbet på et patentkontor i Tokyo, og hadde BLAS-optimering som hobby. I seks år designet han rutiner med papir og blyant mens han satt på toget på vei til jobb, og programmerte på sine ni datamaskiner hjemme om kvelden. Så fikk han anledning til å ta et friår, noe man tydeligvis får som patentkontorarbeider i Japan, og da endte han opp på University of Texas at Austin, hvor han fikk snakke med andre datafolk og dessuten bruke all sin tid på dette. Resultatet ble GotoBLAS, som altså er bedre enn mange cpu-produsenters egen BLAS.

Uansett, moralen er at du bør ikke skrive dine egne rutiner for lineær algebra, da det er rimelig usannsynlig at du vil kunne gjøre det bedre enn en gal japaner som har hatt dette som hobby, og senere jobb, i over ti år.

-Tor Nordam
Matteus likes this

Comments

Sånn for fremtiden og slikt.
Tor,  11.02.11 23:04

Hvis du ikke husker dette blir du en slik person som i en vittig historie en dame som jobber med GPU-programmering på NTNU fortalte. Det var en student som kom til henne og lurte på om det var mulig å porte koden hans til å kjøre på en GPU, og så spurte hun hva slags biblioteker han brukte, og da sa han «Biblioteker?». Så byttet han fra å bruke sin egen FFT*, eller hva det nå var, til FFTW**, og så gikk plutselig koden 100 ganger fortere, og da var det ikke så farlig likevel.

*Fast Fourier Transform

**Fastest Fourier Transform in the West
Camilla,  11.02.11 23:06

hehe.

Camilla,  11.02.11 23:37

this reminds me of the time I was in Budapesht with Binky. We were trying to steal a goose from the casino.
Category
Technology
Tags
programmering
superdatamaskiner
numerikk
BLAS
GotoBLAS
assembly
Views
2475
Google hits
1
Last google search
numerikks driver