blatt05.md 5.25 KB
Newer Older
Christoph Gerum's avatar
Christoph Gerum committed
1
Title: Blatt 4
2 3
status: hidden

Christoph Gerum's avatar
Christoph Gerum committed
4
# Superlinearer Speedup und Vektorbefehle 
Christoph Gerum's avatar
Christoph Gerum committed
5 6 7

Führen Sie vor dem Bearbeiten des Blattes wieder ein *git pull* durch.

Christoph Gerum's avatar
Christoph Gerum committed
8
## Aufgabe 1: Superlinearer Speedup (*Abgabe war verschoben von Blatt 04*)
Christoph Gerum's avatar
Christoph Gerum committed
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

Auf der englischen Wikipedia unter wird folgende Aussage zum Thema 
[superlinearer Speedup](https://en.wikipedia.org/wiki/Speedup#Super-linear_speedup)  bei
Parallelrechnerarchitekturen gemacht:

> Sometimes a speedup of more than $A$ when using $A$ processors is observed 
> in parallel computing, which is called ''super-linear speedup''. Super-linear 
> speedup rarely happens and often confuses beginners, who believe the t
> heoretical maximum speedup should be $A$ when $A$ processors are used.

Da Sie ja nicht zu den genannten "`Anfängern"' gehören  stiftet bei Ihnen
das Auftreten von superlinearem Speedup keine Verwirrung, so dass
Ihnen die folgenden Aufgaben auch keine Probleme bereiten dürften.

Schreiben Sie ein Benchmark-Programm, das ein von Ihnen definiertes
Problem löst und das bei  paralleler Bearbeitung auf einer gem5 Konfiguration mit mehreren Kernen einen superlinearen Speedup zeigt.

### Fragen 

-  Beschreiben Sie mindestens eine Ursache für das Zustandekommen von
   superlinearem Speedup bei der Verwendung eines Parallelrechners zur Lösung
   eines Problems.

- Erstellen sie wie in Aufgabe 1 ein Schaubild das den Verlauf des Speedups bei 
  einer schrittweisen Erhöhung der Anzahl der Rechenkerne zeigt.  Wo tritt superlinearer Speedup auf?

### Tips 

- Wenn Sie versuchen einen superlinearen Speedup durch Cacheeffekte zu erzielen
  kann es hilfreich sein den Speicher sehr langsam zu machen. Dazu können  
  Sie den DDR-RAM in der Beispielkonfiguration durch ein SimpleMemory ersetzen 
  und die Parameter latency und bandwidth setzen. 

Christoph Gerum's avatar
Christoph Gerum committed
42
- Unter umständen muss das Programm eine Zeit lang laufen um den gewünschten superlinearen Speedup zu zeigen.
Christoph Gerum's avatar
Christoph Gerum committed
43 44 45 46 47 48 49 50

### Abgabe
  
1.  der Quellcode des Programms und die verwendete gem5 konfiguration      
2.  die Antworten auf die Fragen  



Christoph Gerum's avatar
Christoph Gerum committed
51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116
## Aufgabe 2:  SIMD Parallelismus ARM-Neon

Sie haben in der Vorlesung bereits von
SIMD (Single Instruction Multiple Data) oder auch Vektor-Einheiten von
Prozessoren gehört. Dabei handelt es sich um Erweiterungen der eigentlichen
Prozessorarchitektur um eine Komponente, die eine Berechnung gleichzeitig auf
mehr als einem Datum ausführen kann (z.B. Vektoraddition).

*Neon* ist die SIMD-Erweiterung der ARM-Architektur. Aus
Programmierer-Sicht besteht die Neon-Erweiterung des ARM-Befehlssatzes aus einer
Menge spezieller Assembler-Befehle. Darüber hinaus existiert auch ein
High-Level Interface, welches es dem Programmierer auf
einfache Art und Weise erlaubt, aus Sprachen wie C oder C++ heraus die
Neon-Funktionalität zu benutzen.

In dem Programm *neon_convert.c* wurde eine Funktion zur Konvertierung
von Farbbildern in Graustufen einmal wie im folgenden in reinem C implementiert


    void reference_convert (uint8_t * __restrict dest, uint8_t * __restrict src, int n){
      int i;
      for (i=0; i<n; i++){
       int r = *src++; // load red
       int g = *src++; // load green
       int b = *src++; // load blue 

       // build weighted average:
       int y = (r*77)+(g*151)+(b*28);

       // undo the scale by 256 and write to memory:
       *dest++ = (y>>8);
      }
    }


Und einmal mit neon intrinsics implementiert. 




   void neon_convert (uint8_t * __restrict dest, uint8_t * __restrict src, int n){
     int i;
     uint8x8_t rfac = vdup_n_u8 (77);
     uint8x8_t gfac = vdup_n_u8 (151);
     uint8x8_t bfac = vdup_n_u8 (28);
     n/= 8;

     for (i=0; i<n; i++) {
       uint16x8_t  temp;
       uint8x8x3_t rgb  = vld3_u8 (src);
       uint8x8_t result;

       temp = vmull_u8 (rgb.val[0],      rfac);
       temp = vmlal_u8 (temp,rgb.val[1], gfac);
       temp = vmlal_u8 (temp,rgb.val[2], bfac);

       result = vshrn_n_u16 (temp, 8);
       vst1_u8 (dest, result);
       src  += 8*3;
       dest += 8;
     }
   }
 

Ihre Aufgabe ist es nun die beiden implementierungen miteinander zu vergleichen und den Effekt von Pipelinebreiten und Compileroptimierungen auf 
die Performance der implementierungen zu untersuchen. Übersetzen sie das Programm für den Simulator verwenden sie dazu die folgende Kommandozeile:
Christoph Gerum's avatar
Christoph Gerum committed
117 118


Christoph Gerum's avatar
Christoph Gerum committed
119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146
    arm-linux-gnueabihf-gcc -O$optlevel -march=armv7-a -marm -mfpu=neon -mfloat-abi=softfp -static neon_convert.c -o neon_convert

Ausführen lässt sich das Programm dann mittels: 

    ~/parallel_computer_architecture/gem5/build/ARM/gem5.fast  MCConfig.py  -c "neon_convert -r" -w $w

Für die referenzimplementierung und mittels:

     ~/parallel_computer_architecture/gem5/build/ARM/gem5.fast  MCConfig.py  -c "neon_convert" -w $w

Für die implementierung mit Neon intrinsics. "$w" steht in diesem Fall für die breite der Pipeline.

Führen Sie Messungen für Pipelinebreiten zwischen 1 und 8 und die Optimierungsstufen 1 und 3 durch. 


### Fragen 

- Die Neon Erweiterung erlaubt es im Beispiel die Berechnung auf Vektoren der Länge acht durchzuführen. Wie hoch wäre hier der von ihnen erwartete Speedup?

- Wie Sind die tatsächlichen Speedups. 

- Versuchen sie mögliche Unterschiede zu den erwarteten Werten zu erklären. 


### Abgabe
  
1.  die Ergebnisse der durchgeführten Messungen sowie die Erhaltenen fragen.      
2.  die Antworten auf die Fragen  
147