NSWI109 - Konstrukce překladačů - domácí úkoly

Násobení matic (vnitřní cyklus)

Komentář: mp4 11min 10MB

Převeďte následující fragment kódu do vhodného mezikódu a pokuste se jej optimalizovat s cílem maximalizace rychlosti.

size_t m = ...;
size_t n = ...;
double * c = ...;
const double * a = ...;
const double * b = ...;
size_t i = ...;
size_t j = ...;
for (size_t k = 0; k < n; ++ k)
{
    c[m*i+j] += a[n*i+k] * b[n*k+j];
}

Úlohu řešte nejprve pro případ, že o hodnotách ukazatelů a,b,c není nic známo. Poté pokračujte dále s předpokladem, že výrazy c[...],a[...],b[...] nejsou aliasy, tj. pole, na která ukazatele a,b,c ukazují, se nepřekrývají. (To může být specifikováno např. použitím restrict v deklaracích a,b,c.)

Bucket-sort

Analyzujte tuto proceduru jazyka C:

void proc( 
  const int64_t * a, 
  const int64_t * b,
  int64_t * c,
  int64_t * d,
  int64_t n)
{
  int64_t i = 0;
  do {
    d[ c[ a[ i]]++] = b[ i];
  } while ( ++i < n );
}

Určete základní bloky, control-flow graf.

Přeložte tuto proceduru do 64-bitového cílového kódu (s virtuálními registry). Ukazatele i typ size_t jsou překládány jako 64-bitové; aritmetické instrukce odpovídají semantice typu int64_t a jsou použitelné i pro ukazatelovou aritmetiku.

Cílový kód obsahuje tyto instrukce:

MOV r1,r2r1 = r2
XLD r1,r2,cr1 = *(int64_t*)(r2+c)
XST r1,c,r2*(int64_t*)(r1+c) = r2
JEQ r1,r2,lif(r1==r2) goto l;
JGT r1,r2,lif(r1>r2) goto l;
podobně JNE,JGE,JLT,JLE
ADD r1,r2r1 += r2
podobně SUB,...
ADDC r1,cr1 += c
podobně SUBC,...

r1,r2 jsou 64-bitové celočíselné registry, c je konstanta.

Aritmetické instrukce mají latenci 1. Skokové instrukce mají latenci 1 (pro control-dependence). Latence instrukce XLD je 4. Latence mezi XST r1,c,r2 a XLD r3,r1,c (write-read přes paměť) je 1. Všechny antidependence mají latenci 0.

Analyzujte závislosti v základním bloku tvořícím smyčku, včetně závislostí mezi iteracemi. Určete kritickou smyčku a její délku.

Jak se situace změní, bude-li deklarována absence aliasů mezi poli a, b, c, d (např. pomocí restrict nebo #pragma ivdep)?

Zápočtový test

Analyzujte tuto proceduru jazyka C++:

struct S {
  S * n;
  int v;
};

void proc( S * * p, S * r)
{
  int w = r->v;
  S * q;
  for (;;)
  {
    q = * p;
    if ( q == 0 ) break;
    if ( q->v > w ) break;
    p = & q->n;
  }
  r->n = q;
  * p = r;
}

Určete základní bloky, control-flow graf a rozsah životnosti proměnných.

Přeložte tuto proceduru do 32-bitového cílového kódu (s virtuálními registry). Ukazatele i typ int jsou překládány jako 32-bitové; aritmetické instrukce odpovídají semantice typu int a jsou použitelné i pro ukazatelovou aritmetiku.

Cílový kód obsahuje tyto instrukce:

MOV r1,r2r1 = r2
XLD r1,r2,cr1 = *(r2+c)
XST r1,c,r2*(r1+c) = r2
JEQ r1,r2,lif(r1==r2) goto l;
JGT r1,r2,lif(r1>r2) goto l;
podobně JNE,JGE,JLT,JLE
JEQC r1,c,lif(r1==c) goto l;
podobně JGTC,JNEC,JGEC,JLTC,JLEC
ADD r1,r2r1 += r2
podobně SUB,...
ADDC r1,cr1 += c
podobně SUBC,...
r1,r2 jsou 32-bitové celočíselné registry, c je konstanta.

Na vytvořeném kódu určete závislosti (i přes hranice základních bloků).

Pokuste se kód optimalizovat změnou pořadí instrukcí (i přes hranice základních bloků, avšak bez úprav control-flow). Předpokládejte přitom cílový stroj s velkým stupněm paralelismu (tj. schopný spustit velký počet nezávislých instrukcí najednou), avšak bez out-of-order execution (tj. paralelně spouštěné instrukce musí být sousední).

Předpokládejte, že latence paměťových instrukcí (XLD, XST) je 4-násobkem latence ostatních instrukcí.