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?

Opgaver


Stakke og køer

Stack

Queue

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.

Binary heap

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

Binære søgetræer

Binary search tree

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

Grafer

Graph

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.

Opgaver


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.

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