# Architektury systemów komputerowych - optymalizacja programów
## Zadania z 5. rozdziału CS:APP

### Zadanie 13
Załóżmy, że chcemy napisać procedure obliczającą iloczyn skalarny dwóch wektorów $u$ oraz $v$. Abstrakcyjna wersja tej funkcji ma współczynnik CPE 14-18 na architekturze x86-64 dla różnych typów liczb całkowitych oraz zmiennoprzecinkowych. Przekształcając program w taki sposób jak funkcje wcześniej opisane w rozdziale, otrzymaliśmy kod funkcji:

/* Inner product. Accumulate in temporary */
void inner4(vec_ptr u, vec_ptr v, data_t *dest)
{
    long i;
    long length = vec_length(u);
    data_t *udata = get_vec_start(u);
    data_t *vdata = get_vec_start(v);
    data_t sum = (data_t) 0;
    
    for (i = 0; i < length; i++) {
        sum = sum + udata[i] * vdata[i];
    }
    *dest = sum;
}

Pomiary wskazały, że ta funkcja ma CPE 1.50 dla liczb całkowitych oraz 3.00 dla zmiennoprzecinkowych. Dla typu `double` kod assemblera wewnętrznej pętli jest następujący:

.L15:                                     loop:
    vmovsd 0(%rbp,%rcx,8), %xmm1             Get udata[i]
    vmulsd (%rax,%rcx,8), %xmm1, %xmm1       Multiply by vdata[i]
    vaddsd %xmm1, %xmm0, %xmm0               Add to sum
    addq $1, %rcx                            Increment i
    cmpq %rbx, %rcx                          Compare i:limit
    jne .L15                                 If !=, goto loop

* Należy narysować diagram instrukcji ([polecam tą stronkę](https://app.diagrams.net/)) w sposób podobny do wcześniej wspominanego w bieżącym rozdziale i narysować jakieś zależności danych.
* Dla typu `double`, jaka jest dolna granica CPE determinowana przez ścieżkę krytyczną?
* Zakładając podobny ciąg instrukcji dla kodu z liczbami całkowitymi, jaka jest dolna granica CPE determinowana przez ścieżkę krytyczną?
* Wyjaśnij jak to możliwe, że wersje działające na liczbach zmiennoprzecinkowych mają CPE 3.00, pomimo że operacja mnożenia wymaga 5 cykli zegarowych.

Diagram 1:

Diagram 2 (ścieżka krytyczna - `%xmm0 -> add -> %xmm0`):

Dolna granica CPE dla `double` jest determinowana przez opóźnienie dodawania liczb zmiennoprzecinkowych, które jest równe 3.00, a w przypadku `int` opóźnienie dodawania wynosi 1.00.

Wersje działające na liczbach zmiennoprzecinkowych mają CPE na poziomie 3.00, ponieważ na ścieżce krytycznej znajduje się tylko jedna operacja dodawania.

### Zadanie 14
Napisać wersję procedury iloczynu skalarnego używającej odwijania pętli $6 \times 1$. Dla x86-64 pomiary odwiniętej pętli powinny dawać CPE 1.07 dla liczb całkowitych, a dla zmiennopozycyjnych powinien nadal zostać przy 3.01.
* Wyjaśnij, dlaczego żadna skalarna wersja iloczynu dwóch wektorów działająca na procesorze Intel Core i7 Haswell nie może osiągnąć CPE poniżej 1.00
* Wyjaśnij, dlaczego wydajność dla liczb zmiennopozycyjnych nie wzrosła pomimo odwijania pętli.

void inner6x1(vec_ptr u, vec_ptr v, data_t *dest) {
    long i;
    long length   = vec_length(u);
    data_t *udata = get_vec_start(u);
    data_t *vdata = get_vec_start(v);
    data_t sum    = (data_t) 0;

    // Liczymy 6 iloczynów jednocześnie, dodajemy je do akumulatora
    for (i = 0; i < length - 6; i += 6) {
        sum =  sum + 
               udata[i]   * vdata[i]   +
               udata[i+1] * vdata[i+1] +
               udata[i+2] * vdata[i+2] +
               udata[i+3] * vdata[i+3] +
               udata[i+4] * vdata[i+4] +
               udata[i+5] * vdata[i+5];
    }
    // Pozostałe <6 wartości wektorów mnożymy pojedynczo
    for(; i < length; i++) {
        sum = sum + udata[i] * vdata[i];
    }
    *dest = sum;
}

Diagram jak w zadaniu poprzednim (ścieżka krytyczna `sum -> add -> ... -> add -> sum`):

Nie można osiągnąć współczynnika CPE niższego niż 1.00, ponieważ każda wersja obliczająca iloczyn skalarny dwóch wektorów korzysta z operacji dodawania i mnożenia, a więc na ścieżce krytycznej nie będzie można osiągnąć niższego CPE dla żadnego z typów liczb. Spójrzmy na zasadę działania pętli: w każdej iteracji mamy $6$ elementów (oprócz ostatniej, którą bez straty ogólności możemy pominąć). Liczba iteracji wynosi $n/6$, a więc $6\cdot n/6 = 1.00$.

Dla liczb zmiennopozycyjnych odwijanie pętli $k \times 1$ nie poprawi wydajności ponad limit opóźnienia CPE (CS:APP, s. 563):
> We see here that there is still a critical path of n `mul` operations in this graph—there are half as many iterations, but each iteration has two multiplication operations in sequence. Since the critical path was the limiting factor for the performance of the code without loop unrolling, it remains so with $k \times 1$ loop unrolling.

### Zadanie 15
Należy przerobić funkcję z zadania 14. na funkcję używającą odwijania pętli $6 \times 6$. Pomiary na x86-64 dały rezultat CPE 1.06 dla liczb całkowitych i 1.01 dla liczb zmiennopozycyjnych.

void inner6x6(vec_ptr u, vec_ptr v, data_t *dest) {
    long i;
    long length   = vec_length(u); 
    data_t *udata = get_vec_start(u);
    data_t *vdata = get_vec_start(v);
    data_t sum0 = sum1 = sum2 = sum3 = sum4 = sum5 = (data_t) 0;

    // Liczymy 6 iloczynów w 6 akumulatorach
    for (i = 0; i < length - 6; i += 6) {
        sum0 = sum + udata[i]   * vdata[i];
        sum1 = sum + udata[i+1] * vdata[i+1];
        sum2 = sum + udata[i+2] * vdata[i+2];
        sum3 = sum + udata[i+3] * vdata[i+3];
        sum4 = sum + udata[i+4] * vdata[i+4];
        sum5 = sum + udata[i+5] * vdata[i+5];
    }
    // Pozostałe <6 wartości wektorów mnożymy pojedynczo
    for(; i < length; i++) {
        sum0 = sum0 + udata[i] * vdata[i];
    }
    // I dodajemy wszystkie akumulatory
    *dest = sum0 + sum1 + sum2 + sum3 + sum4 + sum5;
}

**TEGO NIE JESTEM PEWNY:** Używając zbyt dużego odwijania pętli możemy napotkać problem polegający na zbyt małej ilości dostępnych rejestrów, wtenczas kompilator zacznie "rozlewać" dane *(ang. spilling)*, przechowując część danych w pamięci, zwykle alokując miejsce na stosie run-time. Dla zbyt dużych wartości odwijania pętli może dojść nawet do utraty wydajności (więcej info w tabelce 5.11.1 CS:APP, s. 576).

### Zadanie 16
Należy przerobić funkcję z zadania 14. na funkcję używającą odwijania pętli $6 \times 1a$. Pomiary na x86-64 dały rezultat CPE 1.10 dla liczb całkowitych i 1.05 dla liczb zmiennopozycyjnych.

Główna różnica pomiędzy odwijaniem pętli $k \times 1$ a $k \times 1a$ polega na sposobie gromadzenia danych w akumulatorze - jest to transformacja polegająca na zmianie kolejności *(ang. reassociation transformation)*:

acc = (acc OP data[i]) OP data[i+1];

acc = acc OP (data[i] OP data[i+1]);

Dla dodawania czynnik CPE jest identyczny, jednak dla obliczania iloczynu zmniejsza się on dwukrotnie w przypadku odwijania $k \times 1a$. Przedstawia to poniższy kod:

void inner6x1a(vec_ptr u, vec_ptr v, data_t *dest) {
    long i;
    long length   = vec_length(u);
    data_t *udata = get_vec_start(u);
    data_t *vdata = get_vec_start(v);
    data_t sum    = (data_t) 0;

    // Wykonujemy najpierw mnożenia i dodawania wartości wektorów,
    // a następnie cały wynik dodajemy do akumulatora.
    for (i = 0; i < length - 6; i += 6) {
        sum = sum + 
              (udata[i]  * vdata[i]   +
              udata[i+1] * vdata[i+1] +
              udata[i+2] * vdata[i+2] +
              udata[i+3] * vdata[i+3] +
              udata[i+4] * vdata[i+4] +
              udata[i+5] * vdata[i+5]);
    }
    // Pozostałe <6 wartości wektorów mnożymy pojedynczo
    for(; i < length; i++) {
        sum = sum + udata[i] * vdata[i];
    }
    *dest = sum;
}