Hoofdstuk 3: Arithmetic for computers Flashcards
SIMD
= 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.
Fraction VS exponent
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.
Figure 3.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.
Floating point addition
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)
Advanced vector extensions (AVX) in x86
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”)
ALU
= 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.
Figure 3.8
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
AVX subword parallel instructions
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)
Data level parallelism
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)
DGEMM
Double precision general matrix multiply (= wordt gebruikt om voordelen van bepaalde verbeteringen te tonen) → zie p 218 voor bevorderingen door subword parallelism via AVX
Faster division
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.
Figure 3.21
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.
Figure 3.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.
Floating point voorstelling
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
GigaFLOPS - FLOPS
floating point operations per second
Figure 3.11
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.
Guard bits (context: floating point)
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.
Figure 3.5
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).
IEEE 754 standaard
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^(𝐸−𝐵)
Normalized notation
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.
Overflow
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.
Point (in floating point)
getal voor komma?
Round bits (context: floating point)
De 2de bit van de 2 extra bits die tijdens floating-point bewerkingen rechts worden gehouden, ten voordele van de nauwkeurigheid van de afronding.
Rounding (context: floating point arithmetic)
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’)
