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

grafik.png

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

In [1]:
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.

In [2]:
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:

  1. Synchron: Aufeinander warten
  2. Buffered: Explizite Buffer
  3. Ready: Aufeinander warten, aber Receive muss bei Send schon initiiert sein
    sonst undefined behaviour!
  4. 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;
}
In [ ]: