%page
%center
%fore "black"
%bgrad 0 0 100 0 0 "#9090ff" "#ffffff"

%fore "#000080"
%size 13
Distribuerede klynger
%size 6


http://jacob-sparre.dk/Jacob/foredrag/klynger/


%fore "black"
%size 8
Jacob Sparre Andersen
<sparre@nbi.dk>

%page
%fore "#000080"
%bgrad 0 0 100 0 0 "#9090ff" "#ffffff"
%center
%size 3


%size 10
Jacob Sparre Andersen
%left
%fore "black"
%size 6


  - eksperimentalfysiker
  - klyngeteoretiker (optimeringsalgoritmer)
  - doven (og dermed nødvendigvis Unix-bruger ;-)
  - Ada-programmør

  - medlem af SSLUG's bestyrelse
  - medstifter af Linux-áhugafelagið

%page
%fore "black"
%bgrad 0 0 100 0 0 "#9090ff" "#ffffff"
%center
%size 3


%size 10
%fore "#000080"
Oversigt
%left
%fore "black"
%size 6


  - Hvad er en klynge
  - Hvilke problemer løser en klynge
  - Eksempler på opgaver til klynger
  - Karakterisering af opgaverne
  - Hvilket isenkram kan man bruge i en klynge
  - Værktøjer

  - Opsummering

%page
%bgrad 0 0 100 0 0 "#9090ff" "#ffffff"
%center
%size 3


%size 10
%fore "#000080"
Hvad er en klynge
%left
%size 6
%fore "black"


  - En samling computere bundet sammen i
    et netværk.

  - Computerne vil typisk ikke have fælles
    hukommelse.

%page
%bgrad 0 0 100 0 0 "#9090ff" "#ffffff"
%center
%size 3


%size 10
%fore "#000080"
Hvilke problemer løser man med klynger
%left
%size 6
%fore "black"

  - Store opgaver der skal løses hurtigere.
%size 5

     Når man ikke har tid til at vente på at ens hurtigste
     computer regner færdigt.

%size 6
  - Udnytte ressourcer bedre til mange små
    opgaver.
%size 5

     Hvis man har regnekraft fordelt på mange maskiner og
     de enkelte brugere selv styrer fordelingen af opgaver
     bliver belastningen sjældent fordelt optimalt.
%size 6

%page
%bgrad 0 0 100 0 0 "#9090ff" "#ffffff"
%center
%size 3


%size 10
%fore "#000080"
Eksempler på opgaver til klynger
%left
%size 6
%fore "black"


  a) Computergenereret tegnefilm (ray-tracing)

  b) Proteinfoldning (eller optimering af
      distribuerede programmer)

  c) Vejrudsigter

%page
%bgrad 0 0 100 0 0 "#9090ff" "#ffffff"
%center
%size 3


%size 10
%fore "#000080"
Computergenereret tegnefilm
%left
%size 5
%fore "black"


  - Beskrivelse af den "verden" der skal tegnes.
  - Beskrivelse af hvor aktører og andre løsdele
    befinder sig til ethvert tidspunkt.

 Hvert billede i tegnefilmen laves så ved at computeren:
%size 4

    1) får et tidspunkt
    2) organiserer sin model af verden så den svarer til tidspunktet
    3) opbygger billedet ved at følge lysets vej til kameraet

%size 5
 Det sidste trin er meget tungt at regne på, men der er ikke
 noget i vejen for at uddelegere opgaverne så flere
 computere regner på hver deres del af filmen.

%page
%bgrad 0 0 100 0 0 "#9090ff" "#ffffff"
%center
%size 3


%size 10
%fore "#000080"
Proteinfoldning (1)
%left
%size 6
%fore "black"

   Proteiner består af aminosyrer, der kan være
   foldet mere eller mindre sammen på utallige
   måder (tilstande).

   Hvordan et protein er foldet sammen er
   afgørende for hvordan det virker.

   Da proteiner i "naturen" har det med enten at
   være foldede ud eller foldede sammen er man
   interesseret i at kunne modellere selve
   foldningsprocessen.

%page
%bgrad 0 0 100 0 0 "#9090ff" "#ffffff"
%center
%size 3


%size 10
%fore "#000080"
Proteinfoldning (2)
%left
%size 6
%fore "black"

   For at kunne modellere foldningsprocessen
   har man brug for at vide hvor mange former
   af proteinet der svarer til enhver energi
   (tilstandstæthed).

   Udforsker tilstandsrummet via Markov-kæder:

     + definerer "nabotilstande"

     + fastsætter sandsynligheder for at gå fra én
        tilstand til dens forskellige nabotilstande

%page
%bgrad 0 0 100 0 0 "#9090ff" "#ffffff"
%center
%size 3


%size 10
%fore "#000080"
Proteinfoldning (3)
%left
%size 6
%fore "black"

   Da tilstandstætheden i virkelige systemer gerne
   varierer med en faktor 10^30.000 risikerer vi at
   der er nogle energier vi aldrig kommer til at
   finde tilstande for.

   Hvis vi kender systemets tilstandstætheds-
   funktion kan vi løse problemet ved at lade
   sandsynligheden for at skifte tilstand være
   proportional med forholdet mellem de to
   tilstandes tilstandstætheder.

%page
%bgrad 0 0 100 0 0 "#9090ff" "#ffffff"
%center
%size 3


%size 10
%fore "#000080"
Proteinfoldning (4)
%left
%size 6
%fore "black"

 Vi kender ikke tilstandstæthedsfunktionen, så vi:

  1) Starter med at gætte.
  2) Bruger gættet til at følge en Markov-kæde
      et antal skridt og tæller hvor ofte vi lander i
      tilstande med forskellige energier.
  3) Benytter en formel der udfra en samling par
      af gættede tilstandstæthedsfunktioner og
      energitællinger kan give et bedre gæt på
      tilstandstæthedsfunktionen (Jesper Borgs idé).
  4) Hopper tilbage til punkt 2.

%page
%bgrad 0 0 100 0 0 "#9090ff" "#ffffff"
%center
%size 3


%size 10
%fore "#000080"
Proteinfoldning (5)
%left
%size 6
%fore "black"

 "... en samling par af ..."

 Hvorfor ikke lade flere computere tælle energier
 på hver deres tilfældige måde?

 Når de enkelte maskiner har tid kan de bare bede
 en central database om det seneste bud på
 tilstandstæthedsfunktionen. Den kan de så lave
 en energitælling udfra og sende tilbage sammen
 med den brugte tilstandstæthedsfunktion.

%page
%bgrad 0 0 100 0 0 "#9090ff" "#ffffff"
%center
%size 3


%size 10
%fore "#000080"
Vejrudsigter
%left
%size 6
%fore "black"

 Vejrmodeller bygger typisk på at man deler verden
 op i kasser og tiden op i diskrete tidsskridt.

 For hvert tidsskridt regner man så
 gennemsnitsvejret ud for hver enkelt kasse.

 Da kasserne ikke har ugennemtrængelige vægge
 har man brug for resultatet fra nabokasserne i det
 forrige tidsskridt, når man skal finde tilstanden i et
 nyt tidsskridt.

%page
%bgrad 0 0 100 0 0 "#9090ff" "#ffffff"
%center
%size 3


%size 10
%fore "#000080"
Karakterisering af opgaverne
%size 8
(synkronisering)
%left
%size 6
%fore "black"

 Et problem med parallelisering er synkronisering
 mellem programmets forskellige dele.

 Hver gang der er behov for en form for
 synkronisering risikerer man spildtid.

 Eksemplernes afhængighed af synkronisering:
%size 5
   a) Computergenereret tegnefilm	- ingen
   b) Proteinfoldning		- en smule
   c) Vejrudsigter			- tidsskridt for tidsskridt
%size 6

%page
%bgrad 0 0 100 0 0 "#9090ff" "#ffffff"
%center
%size 3


%size 10
%fore "#000080"
Karakterisering af opgaverne
%size 8
(dataudveksling og beregning)
%left
%size 6
%fore "black"

 Et andet problem med parallelisering er
 synkronisering forholdet mellem den tid der
 bruges på beregning og på dataudveksling.

 Dominerer beregning eller dataudveksling i
 eksemplerne:
%size 5
   a) Computergenereret tegnefilm	- beregning
   b) Proteinfoldning		- beregning
   c) Vejrudsigter			- dataudveksling
%size 6

%page
%bgrad 0 0 100 0 0 "#9090ff" "#ffffff"
%center
%size 3


%size 10
%fore "#000080"
Hvilket isenkram kan man bruge i en klynge
%left
%size 6
%fore "black"

 Eller:	Kan man bare sætte alt fra sin gamle
 	386'er til sin nyeste PIII'er i klyngen?

  - synkronisering	   svært at fordele opgaven
  - el-regning	   er en PIII'er ikke billigere end
 		   strømmen til en 386'er?
  - kompatibilitet	   det kan være bøvlet at
 		   udveksle data mellem
 		   forskellige arkitekturer

%page
%bgrad 0 0 100 0 0 "#9090ff" "#ffffff"
%center
%size 3


%size 10
%fore "#000080"
Værktøjer
%size 8
(distribuering af store opgaver)
%left 
%size 6
%fore "black"

  Listen her går fra det "håndkodede" over
  værktøjer der kræver en smule programmør-
  indblanding til praktisk taget usynlige værktøjer.

    1) HTTP+CGI (åbent for praktisk talt overalt)
    2) PVM/DSA/MPI (findes til de fleste Unixer)
    3) MOSIX (kun Linux/IA32?)

%page
%bgrad 0 0 100 0 0 "#9090ff" "#ffffff"
%center
%size 3


%size 10
%fore "#000080"
Værktøjer
%size 8
(belastningsfordeling med små opgaver)
%left
%size 6
%fore "black"

  Listen her går fra det "håndkodede" over
  værktøjer der kræver en smule programmør-
  indblanding til praktisk taget usynlige værktøjer.
 
    1) ruptime+ssh (findes til alle Unixer)
    2) Job-kø-systemer
    3) MOSIX (kun Linux/IA32?)

%page
%bgrad 0 0 100 0 0 "#9090ff" "#ffffff"
%center
%size 3


%size 10
%fore "#000080"
Opsummering
%left
%size 6
%fore "black"

  - Har præsenteret nogle eksempler på hvilke
    opgaver klynger kan bruges til at løse.
  - Har gennemgået hvad der karakteriserer
    opgaverne og hvilken betydning det har for
    hvordan man skal gribe dem an.
  - Har frarådet at man blander meget forskelligt
    isenkram i én klynge.
  - Har givet en oversigt over en del af de værktøjer
    der findes til at opbygge/administrere klynger.

%page
%bgrad 0 0 100 0 0 "#9090ff" "#ffffff"
%center
%size 3


%size 10
%fore "#000080"
Henvisninger
%left
%size 6
%fore "black"

    MOSIX:
%size 5
 	http://www.mosix.org/
%size 6
    Foredraget:
%size 5
 	http://jacob-sparre.dk/Jacob/foredrag/klynger/
%size 6