Hoofdstuk 3: Arithmetic for computers

Question 1

SIMD

Answer 1

= single instruction multiple data

Dit is een instructieset dat dataparallellisme kan uitvoeren op een vector. Bijvoorbeeld subword parallellisme. 1 instructie wordt parallel op meerdere datapunten uitgevoerd.

Een SIMD is een categorie van de parallel hardware. Het heeft een enkele instructiestroom en multiple datastreams. SIMD computers werken met vectoren van data of arrays van data. De SIMD computers werden niet meer gebruikt omdat ze te inflexibel waren. Het aantal belangrijke problemen kon deze stijl van multiprocessor niet gebruiken en de architectuur kon ook niet worden kleiner gemaakt. Een kleinere SIMD microprocessor kon geen voordeel halen uit de performance en de kost was ook groter.

Question 2

Fraction VS exponent

Answer 2

De fractie bij een floating point, bestaande uit 23 bits voor single precision en 52 bits voor double precision, geeft weer hoeveel getallen na de komma we kunnen weergeven. ( = mantissa)

De exponent bij een floating point, bestaande uit 8 bits voor single en 11 voor double, geeft het bereik weer van de getallen die we kunnen weergeven. (single: 2^+-38, double: 2^+-308)

Er is een compromis tussen de grootte van de fractie en exponent:

• door het groter maken van de fractie, verbetert de precisie
• door het groter maken van de exponent, vergroot het bereik.

Question 3

Figure 3.3

Answer 3

Voorstelling van de multiplicatie zoals wij het geleerd hebben in de lagere school, maar dan in hardware.

Deze is echter duur op vlak van clock cycli en we kunnen deze versnellen door de operaties in parallel te doen: multiplier en multiplicand shiften terwijl we multiplicand wordt opgeteld bij het product als de multiplier 1 bit is. Hierbij wordt de breedte van de adder en registers gehalveerd.

The multiplier bevindt zich in de 64-bit multiplier register en de 128-bit product register wordt geïnitialiseerd op 0. We moeten de multiplicand 1 cijfer naar links opschuiven in elke stap. Daarom hebben we dus een 128-bit multiplicand register nodig dat geïnitialiseerd wordt met de 64-bit multiplicand in de rechterhelft en nul in de linkerhelft. Dit register wordt dan telkens 1 bit naar links geschoven zodat het de multiplicand aligneert met de som die geaccumuleerd wordt in het 128-bit product register. De multiplier wordt in de tegengestelde richting geschoven na elke stap. De controle bepaalt wanneer het de Multiplicand en multiplier registers moet schiften en wanneer het nieuwe waarden in het product register moet schrijven.

Question 4

Floating point addition

Answer 4

1) Aligneren van het decimaal punt van het getal met de kleinste exponent om het getal met de grootste exponent te matchen. We moeten dus de significand van het kleinste nummer naar rechts schuiven totdat de exponent van dit nummer gelijk is aan de exponent van het grootste getal.
2) Tel de significanden op
3) Zet het om in genormaliseerde wetenschappelijke notatie door te schuiven en de exponent aan te passen. Check eveneens op underflow en overflow.
4) Rond de significand af zodat het past in de notatie (eventueel hernormaliseren)

Question 5

Advanced vector extensions (AVX) in x86

Answer 5

SIMD extensie van intel, waarbij een operatie nu 8 32-bit floating-point operaties kan doen (of dus 2 128-bit fp-operaties) (aangeduid door “v”)

Question 6

ALU

Answer 6

= arithmetic logical unit
De hardware dat verantwoordelijk is voor de aritmetische operaties en soms ook logische (and, or, ..) Aangezien vermenigvuldiging en deling enkel gebruikt maakt van shifts, additions en substractions zullen de enige aritmetische operaties optellen en aftrekken zijn.

Voor elke soort instructie zal er een andere bewerking moeten gebeuren. Hiervoor hebben we een opcode. De ALUop. Dit is 00 voor een LW (load word of store word, dus mem instruction), 01 voor een branch (een branch equal) en 10 voor een R instructie. De ALU controller geeft de opcodes door aan de ALU unit en zo weet die welke bewerking hij moet uitvoeren.

Question 7

Figure 3.8

Answer 7

Hardware hoe wij hebben geleerd om te delen. De 64-bit divisor start in de linkerhelft van het divisor register en wordt 1 bit naar rechts opgeschoven bij elke iteratie. De remainder is initieel gelijk aan de dividend. De controle beslist wanneer de divisor en quotient register geschoven moeten worden en wanneer er een nieuw cijfer in het remainder register moet geschreven worden.

Dit kan nog efficiënter gemaakt worden door het quotient en de teller en noemer tegelijk te shiften met de substractie → adder en register helft van de breedte

Question 8

AVX subword parallel instructions

Answer 8

AVX: advanced vector extensions.

instructies worden voorgegaan door “v”, om 4 16-bit floating-point operaties te doen bv. (3 address instructies in x86: vaddp %ymm0, %ymm1, %ymm4 addp %xmm0, %xmm4)

Question 9

Data level parallelism

Answer 9

subword parallelism = parallelism om operaties tegelijk uit te voeren op korte vectoren van 16 8-bit, 8 16-bit, 4 32-bit of 2 64-bit operanden. (gebruikt voor multimedia)

Question 10

DGEMM

Answer 10

Double precision general matrix multiply (= wordt gebruikt om voordelen van bepaalde verbeteringen te tonen) → zie p 218 voor bevorderingen door subword parallelism via AVX

Question 11

Faster division

Answer 11

Door de wet van Moore kunnen hardware ontwerpers nu veel snellere deling hardware maken. We kunnen niet zoals bij multiplicatie meer adders gebruiken doordat we het teken van het verschil van de rest en de deler moeten weten. Wat we echter wel kunnen doen is SRT deling: het voorspelt verscheidene quotiënt bits per stap via een tabel gebaseerd op de bovenste bits van het dividend en de remainder.

Question 12

Figure 3.21

Answer 12

Geoptimaliseerde code van DGEMM via AVX subword-parallelisme instructies voor x86

The declaration on line 6 of Figure 3.21 uses the __m256d data type, which tells the compiler the variable will hold four double-precision floating-point values. The intrinsic _mm256_load_pd() also on line 6 uses AVX instructions to load four double-precision floating-point numbers in parallel (_pd) from the matrix C into c0. The address calculation C+i+jn on line 6 represents element C[i+jn]. Symmetrically, the final step on line 11 uses the intrinsic _mm256_store_pd()
to store four double-precision floating-point numbers from c0 into the matrix C. As we’re going through four elements each iteration, the outer for loop on line 4
increments i by 4 instead of by 1 as on line 3 of Figure 3.19.

Inside the loops, on line 9 we first load four elements of A again using _mm256_load_pd(). To multiply these elements by one element of B, on line 10 we first use
the intrinsic _mm256_broadcast_sd(), which makes four identical copies of the scalar double precision number—in this case an element of B—in one of the YMM registers. We then use _mm256_mul_pd() on line 9 to multiply the four doubleprecision results in parallel. Finally, _mm256_add_pd() on line 8 adds the four products to the four sums in c0.

Question 13

Figure 3.13

Answer 13

Dit toont de IEEE 754 decodering van floating-point nummers. Een aparte sign bit bepaalt het teken. IEEE 754 heeft ook speciale symbolen om ongewone events voor te stellen.

Question 14

Floating point voorstelling

Answer 14

Dit geeft getallen weer waarin het binaire punt niet is vastgelegd. Het binair punt verplaatst zich afhankelijk van de grootte van het getal

(1.xxxxxx)two x 2^yyy

Single precision: 1 sign bit, 8 exponent bits, 23 fraction bits
Double precision: 1 sign bit, 11 exponent bits, 52 fraction bits

Question 15

GigaFLOPS - FLOPS

Answer 15

floating point operations per second

Question 16

Figure 3.11

Answer 16

Geoptimaliseerde hardware voor de deling (t.ov. fig 3.8). Vergelijken met de eerste versie van de hardware zijn de ALU en divisor registers gehalveerd en wordt de remainder naar links geschift.

Deze versie is sneller want het schiften van de operanden en het quotient gebeurt tegelijk met de aftrekking. Hierdoor wordt de breedte van de adders en registers gehalveerd.

Question 17

Guard bits (context: floating point)

Answer 17

Om accuraat af te kunnen ronden moeten de hardware extra bits bevatten in de calculatie.
De guard is de eerste van de 2 extra bits rechts gehouden tijdens tussentijdse bewerkingen van floating points. Na de bewerking wordt deze gebruikt om de afrondingsnauwkeurigheid te verhogen.

Question 18

Figure 3.5

Answer 18

Dit is een geoptimaliseerde versie van de multiplicatie hardware. (zie figure 3.3)

We hebben het proces versneld door de operaties in parallel te doen: multiplier en multiplicand shiften terwijl we multiplicand wordt opgeteld bij het product als de multiplier 1 bit is. Hierbij wordt de breedte van de adder en registers gehalveerd.

Het mutliplicand register en ALU zijn gereduceerd tot 64 bits. En het product wordt nu naar rechts geschoven. Het aparte multiplier register is ook verdwenen. De multiplier is wordt nu in de rechterhelft van het product register geplaatst dat nu 129 bit heeft (ook bit voor carry-out van de adder).

Question 19

IEEE 754 standaard

Answer 19

Dit is de belangrijkste standaard voor het voorstellen van floating point nummers.

• gebruikt floating point format, maar fraction heeft 1 bit meer en wordt significand genoemd (→ leading 1 bit impliciet gemaakt)
• NaN = not a number = symbol voor het resultaat ongeldige bewerkingen
• Exponent voor significand → makkelijk te sorteren
• Bias voor exponent: 127 en 1023 → negatieve exponenten die klein zijn ook klein lijken voor sorteren.
  (−1)^𝑆 (1+𝐹) 2^(𝐸−𝐵)

Question 20

Normalized notation

Answer 20

Een nummer in scientific notation dat geen ‘leading’ nullen heeft (cijfer voor de komma mag niet nul zijn).

Om een genormaliseerde notatie te verkrijgen voor een binair nummer gebruiken we een basis 2 zodat we kunnen schuiven totdat we een niet-nul bit krijgen voor het decimaal punt.

Question 21

Overflow

Answer 21

Overflow komt voor bij integers en floating points wanneer het resultaat van een bewerking te groot wordt om voorgesteld te worden door de HW, bv. een 64-bit word. Dit komt doordat de exponent te groot is voor het exponentenveld van de floating-point representatie.

Bij de optelling kan dit fenomeen zich NIET voordoen als we getallen met een verschillende teken optellen. Bij aftrekking kan dit fenomeen zich NIET voordoen wanneer we getallen met hetzelfde teken aftrekken van elkaar.

Overflow is wel mogelijk bij het optellen van twee positieve (negatieve) getallen waarbij het resultaat negatief (positief) blijkt (bij de laatste overdracht van bit verandert het teken bit) of bij het aftrekken van een negatief (positief) getal van een positief (negatief) getal en waar het resultaat negatief (positief) blijkt. Bij vermenigvuldiging is overflow ook mogelijk, want het resultaat kan tot 128 bit lang zijn.

Wat men doet bij overflow hangt af van de taal. Sommige talen negeren overflow terwijl andere talen exception handlers voorzien.

Question 22

Point (in floating point)

Answer 22

getal voor komma?

Question 23

Round bits (context: floating point)

Answer 23

De 2de bit van de 2 extra bits die tijdens floating-point bewerkingen rechts worden gehouden, ten voordele van de nauwkeurigheid van de afronding.

Question 24

Rounding (context: floating point arithmetic)

Answer 24

Vaak gebruikt voor nummers die ze niet kunnen weegeven → afrondingen nodig (max 2^53 weergeven) → 2 bits nodig: guard en round

Rounding is een methode om de tussentijdse floating-point te laten passen in het formaat, met het nieuwe nummer zo dicht mogelijk (de nauwkeurigheid wordt gemeten via ULP = unit in the last place = aantal bits in de ‘error zone’)

Question 25

Figure 3.7

Answer 25

Manier voor snellere multiplicatie: We voorzien 1 64-bit adder voor elke bit van de multiplier met als input: multiplicand AND’ed multiplier bit en output van een voorgaande adder.
Beste is in een parallelle boom (ipv. Rechte lijn) → wachten op 𝑙𝑜𝑔2(64) ipv. 64 64-bit add tijden. (kan zelfs sneller via carry save adders → pipelining, waardoor meerdere multiplicaties tegelijk ondersteund)

Question 26

Scientific notation

Answer 26

Notatie dat het grootste cijfer voor de komma zet en alle andere cijfers na de komma

Question 27

Sticky bits (context: floating point)

Answer 27

Een derde bit dat gebruikt wordt voor het afronden bovenop de guard en rounded bit wanneer er non-zero bits zijn, rechts van de round bit. (zodat de computer een verschil kan zien tussen 0.500000000000 en 0.5000000000001 tijdens het afronden.

Question 28

Subword parallelism

Answer 28

=data level parallelisme = SIMD
= parallelism om operaties tegelijk uit te voeren op korte vectoren van 16 8-bit, 8 16-bit, 4 32-bit of 2 64-bit operanden. (gebruikt voor multimedia)

Question 29

Figure 3.15

Answer 29

Blok diagram voor een optelling voor floating points. (zie uitleg optelling floating point, van boven naar onder: compare, shift smaller number, add, normalize, round)

First, the exponent of one operand is subtracted from the other using the small ALU to determine which is
larger and by how much. This difference controls the three multiplexors; from left to right, they select the larger exponent, the significand of the
smaller number, and the significand of the larger number. The smaller significand is shifted right, and then the significands are added together
using the big ALU. The normalization step then shifts the sum left or right and increments or decrements the exponent. Rounding then creates
the final result, which may require normalizing again to produce the actual final result.

Question 30

Faster multiplication

Answer 30

Door de wet van Moore kunnen hardware ontwerpers nu veel snellere vermenigvuldiging hardware maken. Of de multiplicand nu wel of erbij moet opgeteld worden is geweten aan het begin van de vermenigvuldiging door te kijken naar elke bit van de 64 multiplier bits. Snellere vermenigvuldigingen zijn mogelijk door een 1 64-bit adder for elke bit van de multiplier aan te bieden. De input is de multipland ANDed met een mutliplier bit en de andere is de output van de vorige adder.

De vermenigvuldiging gebeurt dus door 63 adders naast elkaar te zetten.

Question 31

Underflow

Answer 31

Undeflow treedt op wanneer een getal te klein is om voorgesteld te worden. Dus indien de negatieve exponent bij een floating-point notatie te groot is geworden voor het exponentenveld van de floating-point representatie

Question 32

Voordelen van standaard wetenschappelijk genormalisseerde notatie?

Answer 32

(opgeven wanneer over floating point voorstelling praat / normalized notation)

• vergemakkelijkt het uitwisselen van gegevens
• vergemakkelijkt bewerkingsalgoritmen
• verhoogt de precisie (want geen onnodige nullen)

Question 33

Hoe de kans op overflow en underflow verkleinen bij floating point getallen? +

Answer 33

Dit kan door i.p.v. een single precision format aan te bieden waar het floating point getal wordt voorgesteld door 32 bit, een double precision format te gebruiken. Hier wordt een floating point getal voorgesteld door 64 bit.

Question 34

Floating point multiplication

Answer 34

Floating point multiplication

1) Optellen van exponenten en dan aftrekken van 1 maal de bias
2) Vermenigvuldig de significanten
3) Normaliseer het product (schift fractie en pas exponent aan) en check op overflow of underflow
4) Rond de significand af zodat het past in de notatie (eventueel hernormaliseren)
5) Regel het teken van het product