SDU Supercomputer challenge - Øvet - Dag 2

09:00 - 11:45: Effektive algoritmer og datastrukturer

Langt den vigtigste ting man kan gøre for at finde en løsning til sit problem er at anvende effektive algoritmer.

Sortering

Til at motivere vigtigheden af at anvende en effektiv algoritme ser vi på sortering af heltal.

Fx hvordan kan man sortere 100 tal? Er nogle måder smartere end andre? Hvordan sorterer man spillekort?

• Insertion sort
• Merge sort

Opgaver

• Implementer insertion sort og/eller merge sort (eller en helt tredje)
• Lav en funktion til at generere en liste med fx 100, 1000, 10000 og 1000000 tal. Prøv både at lave en funktion med tilfældige tal, sorterede og omvendt sorterede. Brug random eller random i numpy (kan installeres med pip).
• Lav en lille timing test med insertion sort og/eller merge sort holdt op imod den indbyggede sorted i Python. Brug data set fra sidste opgave. Brug time, eksempel.

Stakke og køer

Implementeres som linked-list. Effektiv måde at indsætte og fjerne første eller sidste element.

Prioritetskøer

Mål: Find det største eller mindste element igen og igen.

Kan lægges i et array og laves meget effektivt.

Binære søgetræer

En populær version er et rød-sort træ som automatisk balancerer sig selv.

Grafer

Kan bruges til at beskrive vejnet og lignende.

Et godt bibliotek til grafer er networkx. Ud over en implementering af graf-datastrukturen, så findes der også implementeringer af de mest brugte algoritmer.

• DFS og BFS
• Korteste veje: Dijkstra

Opgaver

• Implementer en hjemmelavet prioritetskø som følger: Lav en liste hvor et nyt element tilføjes til enden af listen hvorefter listen sortes (brug sorted eller egen implementering af en sorteringsalgoritme).
  • Lav en lille timing test mellem ovenstående prioritetskø og heapq hvor 1000 eller 10000 tilfældige tal indsættes og dernæst tages ud igen.
• Implementer en knude i et binært søgetræ som en klasse TreeNode med data, et venstre og højre barn.
  • Hardcode et eksempel-træ eller brug dette. Prøv at tegne det.
  • Lav en funktion lookup der tager en TreeNode og noget data og leder ned igennem træet efter knuden med det data. Kan gøres rekursivt og iterativt (rekursivt er anbefalet). Returner None hvis det data ikke findes.
• Brug networkx (kan installeres via pip) eller lav egen graf implementering
  • Hardcode en eksempel-graf. Prøv at tegne den med funktioner i networkx.
  • En Euler sti er en vej igennem grafen, hvor hver kant besøges præcis en gang. Brug eulerian_circuit til at finde sådan en sti. Hvordan ser den ud?

12:00 - 14:00: Parallel programmering

Normalt bliver ens program kørt på én kerne. En supercomputer har ofte rigtig mange kerner som alle kan bearbejde en del af problemet parallelt. Målet er at udnytte alle kernerne så vidt muligt. Til dette kan man bruge forks, multiprocessing og threading.

Fork: I gamle dage da man ville udnytte flere kerner, lavede ens program et såkaldt fork (ikke noget der findes i Python). Det klonede programmet i to ens programmer, som så kunne fortsætte uafhængig af hinanden.

I Python kan man bruge threading og multiprocessing.

• En thread kan dele variabler med andre threads, hvilket både kan være godt og skidt. Det er ofte det der bruges til GUI.
• En process deler normalt ikke variabler med mindre dette gøres eksplicit

Bemærk: På grund af GIL (Global Interpreter Lock) i Python, så kan threads i realiteten ikke udnytte flere kerner til udregninger, se mere her. Derfor bør man bruge multiprocessing i en eller anden form.

Multiprocessing

Multiprocessing er et indbygget bibliotek i Python, der tillader en at styre adskillige processes, fx ved at kalde funktioner der skal køre på de specifikke processes.

1
2
3
4
5
6
7
8
from multiprocessing import Process

def f(name):
    print 'hello', name

p = Process(target=f, args=('bob',))
p.start()
p.join()

Parallel Python (pp)

Parallel Python er en abstraktion over multiprocessing. Det fungerer som en job server, hvor man sætter funktionskald i kø og disse bliver delt ud på forskellige kerner.

1
2
3
4
5
6
7
8
9
10
11
12
import pp

def f(name):
    print 'hello', name

job_server = pp.Server()

job1 = job_server.submit(f, ("bob",))

job1()

job_server.print_stats()

Link til Python 3 download her.

MPI

En ting er at udnytte alle kerner på én maskine, men en supercomputer har ofte mange individuelle nodes/maskiner, som arbejder sammen. For at disse maskiner kan fordele arbejdet mellem sig kan man bruge MPI (Message Passing Interface). Der er en Python udgave her. At udnytte flere nodes er dog mere avanceret, så vi vil ikke gå i dybden med det. Det vigtigste er at kunne anvende effektive algoritmer på flere kerner.

Parallel Python understøtter også anvendelsen af flere nodes vha. sin ppserver. Se mere her.

Start jobs på Abacus

1
2
3
4
5
6
#!/bin/bash
#SBATCH --account test00_gpu # account
#SBATCH --nodes 1            # number of nodes
#SBATCH --time 2:00:00       # max time (HH:MM:SS)
module add python/3.4.3      # Or python/2.7.5
python program.py

Kør dernæst ovenstående script

1
testuser@fe1:~$ sbatch myscript.sh

Mere info her.

Opgaver

• Lav en funktion, der tjekker om et tal er et primtal
  • Ret ovenstående funktion til også at tage et start-tal og et slut-tal. Tjek kun om tallet er deleligt med tal i dette interval.
  • Brug multiprocessing i Python til at tjekke om 484327 og 7978417 er primtal.
  • Lav en lignende løsning med Parallel Python.