Tutorium 8¶

Gruppen 2 und 4
Samuel Teuber
propa@teuber.dev
https://teuber.dev/propa

Übungsblätter¶

Fragen?
Probleme?
Zu schwierig?

Aufgabe 1 - Tester¶

even(0).
even(X) :- X>0, X1 is X-1, odd(X1).
odd(1).
odd(X) :- X>1, X1 is X-1, even(X1).

Was passiert, wenn man hier ?even(X) aufruft?

Aufgabe 1 - Generator¶

even(0).
even(X) :- odd(Y), X is Y+1, X>0.
odd(1).
odd(X) :- even(Y), X is Y+1, X>1.

Was passiert, wenn man hier ?odd(7) aufruft?
Wie unterscheidet sich das zu ?odd(8)?

Aufgabe 1 - Teil 2¶

Was passiert, wenn bei den Generatoren die Teilziele X>0 und X>1 weggelassen werden?

even(0).
even(X) :- odd(Y), X is Y+1, X>0.
odd(1).
odd(X) :- even(Y), X is Y+1, X>1.

X>1: Reerfüllung von odd(1) über even(0), damit auch even reerfüllbar
X>0: Überflüssig

Aufgabe 1 - Ausführungsbaum¶

Aufgabe 2 - Teil 1¶

del1([],_,[]).
del1([X|T1],X,L2) :- !, del1(T1,X,L2).
del1([Y|T1],X,[Y|T2]) :- del1(T1,X,T2).

del2([],_,[]).
del2([X|T1],X,L2) :- del2(T1,X,L2).
del2([Y|T1],X,[Y|T2]) :- del2(T1,X,T2), not(X=Y).

del3([X|L],X,L).
del3([Y|T1],X,[Y|T2]) :- del3(T1,X,T2).

Anfrage: deli([1,2,1],X,L).

del1 bricht nach erster erfüllbaren Belegung ab: X=1,L=[2]
del2 ist für X reerfüllbar: X=1,L=[2]; X=2,L=[1,1]
del3 ist reerfüllbar und löscht nur ein Vorkommen: X=1,L=[2,1]; X=2,L=[1,1]; X=1,L[1,2]

Aufgabe 2 - Teil 2¶

del1([],_,[]).
del1([X|T1],X,L2) :- !, del1(T1,X,L2).
del1([Y|T1],X,[Y|T2]) :- del1(T1,X,T2).

del2([],_,[]).
del2([X|T1],X,L2) :- del2(T1,X,L2).
del2([Y|T1],X,[Y|T2]) :- del2(T1,X,T2), not(X=Y).

del3([X|L],X,L).
del3([Y|T1],X,[Y|T2]) :- del3(T1,X,T2).

deli(L, 2, [1, 3]).: Nur 3

deli([1, 2, 3], X, [1, 3]).: Nur 2 und 3 (wegen Cut)

deli([1, 2, 3, 2], X, [1, 3]).: Nur 2

deli([1, 2, 3, 2], X, [1, 2, 3]).: Nur 3

deli([1|L], 1, X).: Alle

Aufgabe 2 - Freie Variablen¶

?fv(app(abs(x, abs(y, app(app(x,z), 17))), u), F).
F = [z,u]

Wir brauchen Regeln für jede mögliche Komponente:

Zahl
Atom
Abstraktion
Applikation

fv(X,[]) :- integer(X).
fv(X,[X]):- atom(X).
fv(abs(X,Y),R) :- fv(Y,L), del2(L,X,R).
fv(app(X,Y),R) :- fv(X,L1), fv(Y,L2), append(L1, L2, R).

Tutoren Rätsel¶

solution(S) :-
   % Lösung ist eine Liste mit Einträgen der Form [Name, Programmiersprache, Algorithmus]
   S = [[_,_,_],[_,_,_],[_,_,_],[_,_,_],[_,_,_]],
   clue1(S),
   clue2(S),
   clue3(S),
   clue4(S),
   clue5(S),
   clue6(S),
   clue7(S),
   clue8(S),
   clue9(S),
   clue10(S),
   clue11(S),
   clue12(S).

clue2(S)?
Der Tutor, der am liebsten in Java programmiert, steht direkt rechts von Lars.

clue2(Solution) :-
  indexOf(["Lars",_,_], Solution, N1),
  N2 is N1 + 1,
  indexOf([_,"Java",_], Solution, N2).

Name	Programmiersprache	Lieblingsalgorithmus
Samuel	Rust	Shear Sort
Paul	C	Shunting Yard
Moritz	C++	RAPTOR
Lars	Scala	Kruskal
Thomas	Java	Radix Sort

C/C++¶

Pointer¶

Deklaration: type *name = ...;
Adressoperator: &variable
Dereferenzierungsoperator: *variable

int myint = 10;
int *myptr = &myint;
int myint_again = myint;

Arrays¶

Initialisierung:
- type myarray[n];
- type myarray[] = {1,2,3};
- type myarray[n] = {1,2,3};
Arrayzugriff: myarray[i]

Mit Pointern¶

int array[] = {42, 24, 21, 12};
int *myptr = array;
int i1 = array[1];
int i2 = myptr[1];
int i3 = *(myptr + 1);

Annahme:

sizeof(int); // = 4
sizeof(char); // = 1

Auf was greift der folgende Code Snippet zu?

int i4 = *(((char*)myptr)+4);

Speicher¶

Variablen etc. in Funktion: Auf dem Stack
Für den Heap in C:
- malloc(size) allokiert size btyes auf dem Heap
- free(pointer) gibt den Speicherplatz an der Stelle pointer wieder frei
Für den Heap in C++:
- Mit new/delete Keywords Objekte erstellen/löschen

Übungsaufgabe¶

#include<stdio.h>

char p[] = "Hello_World!";
int i[] = {2,1,3,5,5};
int j = 4;

int main() {
    printf(&(p[*(i+j)+i[1]]));
}

Ausgabe? -> Umfrage

Raw Pointers in modernem C++¶

Vermeidet das in eurem eigenen (Nicht-ProPa) Code! Nutzt stattdessen lieber Smartpointers!
(Mögliche Stichwörter: std:unique_ptr, std:shared_ptr, std::weak_ptr)
Oder nutzt einfach gleich Rust ¯\(ツ)/¯

Flynn's Taxonomy¶

$$ \{\text{Single},\text{Multiple}\}\times\{\text{Instruction},\text{Data}\} $$

SISD: von Neumann
SIMD: e.g. vector processors, GPU,...
MISD: redundant architectures (maybe pipelines of modern processors)
MIMD: multi-core processors

Task Parallelism (MI)¶

Definierte Tasks laufen parallel

Data Parallelism (MD)¶

Aufteilung der Daten für ein und den selben Task

Amdahl's Law¶

Speedup¶

$$ S(n) = \frac{T(1)}{T(n)} $$

mit $T(n)$ Zeit bei Nutzung von $n$ Prozessoren

Amdahl's Law: Maximal Speedup¶

$$ S(n) = \frac{1}{(1-p)+\frac{p}{n}} < \frac{1}{1-p} $$

wobei $p$ der parallelisierbare Prozentsatz des Programms

MPI¶

Message Passing Interface

Praktische Hinweise¶

Kompilierung: mpicc INPUTFILES
Ausführung: mpirun -np N PROGRAM ARGUMENTS

Konzept¶

N Berechnungsprozesse
Kommunikation über Communiators
- Standardcommunicator: MPI_COMM_WORLD
Jeder Prozess: Eigenen Rank $0\leq R_j < N$
- Prozess mit Rank 0 wird oft als Master Control Program/root genutzt

Funktionen:

int my_rank;
int total_size;

MPI_Comm_size(MPI_COMM_WORLD,&total_size);
MPI_Comm_rank(MPI_COMM_WORLD,&my_rank);

Übungsaufgabe¶

#include<stdio.h>
#include<mpi.h> //Wichtig!
int main(int argc, char** args) {
    MPI_Init(&argc,&args);

    int size;
    int rank;
    MPI_Comm_size(MPI_COMM_WORLD,&size);
    MPI_Comm_rank(MPI_COMM_WORLD,&rank);
    printf("Rank %d of %d\n", rank, size);

    MPI_Finalize();
    return 0;
}

Message Exchange¶

int MPI_Send(void *buffer, int count, MPI_Datatype datatype, int dest, int tag, MPI_Comm comm)
- Parameter:
  - buffer: Der Buffer
  - count: Wie viele Elemente senden wir?
  - datatype: Der Datentyp der Buffer Elemente
  - dest: Ziel Rank
  - tag: "Kontext" der Nachricht
  - comm: Communicator
- Blockiert bis Buffer wiederverwendet werden kann
int MPI_Recv(void *buffer, int count, MPI_Datatype datatype, int source, int tag, MPI_Comm comm, MPI_Status *status)
- Parameter:
  - source: Rank der Quelle (kann auch MPI_ANY_SOURCE sein)
  - tag: kann auch MPI_ANY_TAG sein
  - status: Notwendig, kann Infos wie Tag, Quelle etc. enthalten
- Blockiert bis Nachricht vollständig im Buffer

Aufgabe¶

#include"mpi.h"
#include<stdio.h>
#include<string.h>

int main(int argc, char** argv) {
    char msg[20];
    int myrank, tag=42;
    MPI_Status status;
    MPI_Init(&argc, &argv);
    MPI_Comm_rank(MPI_COMM_WORLD, &myrank);
    if(myrank== 0) { // Root Prozess
        strcpy(msg, "Hello student!");
        char *msgPointer = "asdf";
        MPI_Send(msgPointer, strlen(msgPointer)+1, MPI_CHAR, 1, tag, MPI_COMM_WORLD);
    } else{
        MPI_Recv(msg, 20, MPI_CHAR, 0, MPI_ANY_TAG, MPI_COMM_WORLD, &status);
        printf("received \"%s\"\n", msg);
    }
    MPI_Finalize();
    return 0;
}

Kommunikationsmodi¶

Für Send:

Synchron: Aufeinander warten
Buffered: Explizite Buffer
Ready: Aufeinander warten, aber Receive muss bei Send schon initiiert sein
sonst undefined behaviour!
Standard: Implementation dependent

Recv matcht alle Send Modi gleichzeitig

(Non-)Blocking¶

Blocking: Warten bis Buffer freigegeben/voll beschrieben
Non-Blocking: Sofortiger Return, Buffer möglicherweise noch nicht voll beschrieben
- MPI_Isend(...,MPI_Request *request)
- MPI_Irecv(...,MPI_Request *request)

Kollektive Operationen¶

Broadcast
Scatter
Gather
Allgather
Alltoall
Reduce

Allreduce
Reduce-Scatter
Scan

Beispiel: Zahlen sehr ineffizient aufsummieren¶

int MPI_Scatter(void* sendbuf, int sendcount, MPI_Datatype sendtype, void* recvbuf, int recvcount, MPI_Datatype recvtype, int root, MPI_Comm comm);
int MPI_Reduce(void* sendbuf, void* recvbuf, int count, MPI_Datatype type, MPI_Op op, int root, MPI_Comm comm)

int main(int argc, char** argv) {
    int value;
    int myrank, size;
    MPI_Status status;
    MPI_Init(&argc, &argv);
    MPI_Comm_size(MPI_COMM_WORLD, &size);
    MPI_Comm_rank(MPI_COMM_WORLD, &myrank);
    if(myrank== 0) { // Root Prozess
        // Generiere Zahlen
        int generated_values[size];
        for(int i = 1; i<=size; i++) {
            generated_values[i-1]=i;
        }
        MPI_Scatter(&generated_values, 1, MPI_INT, &value, 1, MPI_INT, 0, MPI_COMM_WORLD);
    } else {
        MPI_Scatter(NULL, 1, MPI_INT, &value, 1, MPI_INT, 0, MPI_COMM_WORLD);
    }
    int result;
    MPI_Reduce(&value,&result,1,MPI_INT,MPI_SUM,0,MPI_COMM_WORLD);
    if(myrank==0){
        printf("Sum: %d",result);
    }
    MPI_Finalize();
    return 0;
}

Teil alter Klausuraufgabe (6 Punkte)¶

Konstruiere

MPI_Alltoall(void *sendbuf, 1, MPI_INT, void *recvbuf, 1, MPI_INT, MPI_COMM_WORLD)

aus anderen Operationen:

void myAllToAll(void *sendbuf, void *recvbuf, int rank, int size) {
    for (int i = 0; i<size; i++) {
        MPI_Gather(((int*)sendbuf)+i, 1, MPI_INT, recvbuf, 1, MPI_INT, i, MPI_COMM_WORLD);
    }
}

Kontext:

int main(int argc, char** argv) {
    int value;
    int rank, size;
    MPI_Status status;
    MPI_Init(&argc, &argv);
    MPI_Comm_size(MPI_COMM_WORLD, &size);
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    int *sendBuffer = malloc(size*sizeof(int));
    int*recvBuffer = malloc(size*sizeof(int));
    for(int i = 0; i < size; i++) {
        sendBuffer[i] = i + size*rank;
        printf("Rank %d, Position %d: %d\n", rank, i, sendBuffer[i]);
    }
    myAllToAll(sendBuffer, recvBuffer, rank, size);
    MPI_Barrier(MPI_COMM_WORLD);
    if (rank==0) {
        printf("\n\nALL TO ALL FINISHED\n\n");
    }
    MPI_Barrier(MPI_COMM_WORLD);
    for(int i = 0; i < size; i++) {
        sendBuffer[i] = i + size*rank;
        printf("Rank %d, Position %d: %d\n", rank, i, recvBuffer[i]);
    }
    MPI_Finalize();
    return 0;
}