Stále pracujem na rutinách pre ľubovoľné dlhé celé čísla v C ++. Zatiaľ som implementoval sčítanie / odčítanie a násobenie pre 64-bitové procesory Intel.
Všetko funguje dobre, ale pýtal som sa, či to dokážemtrochu zrýchlite pomocou SSE. Prešiel som si zoznamy dokumentov SSE a inštrukcií procesorov, ale nenašiel som nič, o čom si myslím, že by som ich mohol použiť, a tu je dôvod, prečo:
SSE má niekoľko celočíselných pokynov, ale väčšina pokynov zvláda pohyblivú desatinu. Nevyzerá to, že bol navrhnutý na použitie s celými číslami (napr. Existuje celočíselné porovnanie za menej?)
Myšlienka SSE je SIMD (rovnaká inštrukcia, viacnásobná)údaje), takže poskytuje pokyny pre 2 alebo 4 nezávislé operácie. Na druhej strane by som chcel mať niečo ako 128-bitové celé číslo (128-bitový vstup a výstup). Zdá sa, že to neexistuje. (Možno? V AVX2 možno?)
Celočíselné prírastky a odčítania nezaoberajú vstupom ani výstupom. Je to veľmi ťažkopádne (a teda pomalé) robiť to ručne.
Moja otázka znie: Je moje hodnotenie správne alebo je niečo, čo som prehliadol? Môže mať SSE úžitok z dlhých celých rutín? Môžu mi pomôcť najmä pri písaní rýchlejšej pridanej, čiastkovej alebo viacnásobnej rutiny?
odpovede:
22 pre odpoveď č. 1V minulosti bola odpoveď na túto otázku jednoznačná, „nie“. Ale od roku 2017 sa situácia mení.
Ale predtým, ako budem pokračovať, je čas na terminológiu:
- Aritmetika celého slova
- Čiastočná aritmetika slova
Celoslovná aritmetika:
Toto je štandardné znázornenie, kde je číslo uložené v základni 232 alebo 264 pomocou poľa 32-bitových alebo 64-bitových celých čísel. Mnoho bignum knižníc a aplikácií (vrátane GMP) používa toto znázornenie.
V celoslovnom zastúpení má každé celé číslo jedinečné zastúpenie. Operácie ako porovnanie sú jednoduché. Ale veci ako pridávanie sú ťažšie z dôvodu potreby prenosu.
Je to toto šírenie pomocou prenosu, vďaka čomu je bignum aritmetické takmer nemožné vektorizovať.
Čiastková aritmetika
Toto je menej používané vyjadrenie, kde číslo používa základňu menšiu ako hardvérová veľkosť slova. Napríklad vloženie iba 60 bitov do každého 64-bitového slova. Alebo pomocou základne 1,000,000,000 s 32-bitovou veľkosťou slova pre desatinnú aritmetiku.
Autori GMP to nazývajú „nechty“, kde „necht“ predstavuje nepoužitú časť slova.
V minulosti bolo používanie čiastočnej slovnej aritmetikyväčšinou obmedzené na aplikácie pracujúce na nebinárnych základoch. Ale v dnešnej dobe je to čoraz dôležitejšie v tom, že umožňuje oneskorenie šírenia prenosu.
Problémy s celoslovnou aritmetikou:
Vektorizácia celoslovnej aritmetiky bola historicky stratenou príčinou:
- SSE / AVX2 nemá podporu pre šírenie prenosu.
- SSE / AVX2 nemá žiadny 128-bitový add / sub.
- SSE / AVX2 nemá žiadne 64 x 64-bitové celé číslo. *
* AVX512-DQ pridáva násobenie nižšej polovice 64 x 64 bitov. Stále však neexistuje žiadna inštrukcia pre hornú polovicu.
X86 / x64 má navyše veľa špecializovaných skalárne pokyny pre bignums:
- Doplnok:
adc,adcx,adox. - Dvojslovné násobenie: Jeden operand
mulamulx.
Z tohto dôvodu je pre SIMD ťažké poraziť skalárne na x64 tak bignum-add, ako aj bignum-multiply. Rozhodne nie s SSE alebo AVX.
S programom AVX2 je SIMD takmer konkurencieschopný so skalárnym násobením bignumu, ak usporiadaním údajov povolíte „vertikálnu vektorizáciu“ 4 rozdielny (a nezávislé) násobky rovnakej dĺžky v každom zo 4 pruhov SIMD.
AVX512 dá viac tipov na podporu SIMD za predpokladu vertikálnej vektorizácie.
Ale väčšinou „horizontálna vektorizácia“bignumov je do značnej miery stále stratenou príčinou, pokiaľ ich nemáte veľa (rovnakej veľkosti) a nemôžete si dovoliť náklady na ich transpozíciu, aby boli „vertikálne“.
Vektorizácia aritmetiky čiastkových slov
S aritmetikou čiastkových slov vám extra "nechty" umožňujú odložiť šírenie prenosu.
Pokiaľ slovo nepretekáte, je možné pridať / sub SIMD vykonať priamo. V mnohých implementáciách reprezentácia čiastočného slova používa celé čísla so znamienkom, aby slová mohli byť záporné.
Pretože nie je (zvyčajne) potrebné uskutočňovať prenos, je možné add / sub SIMD na čiastkových slovách vykonať rovnako efektívne na vertikálne aj horizontálne vektorizovaných bignumoch.
Prenos na horizontálne vektorizovaných bignumoch jestále lacné, pretože iba posúvate nechty cez ďalší pruh. Úplné prevedenie úplného vyčistenia nechtov a získania jedinečného zastúpenia zvyčajne nie je potrebné, pokiaľ nepotrebujete porovnanie dvoch čísel, ktoré sú takmer rovnaké.
Násobenie je s tým komplikovanejšiečiastočne slovná aritmetika, pretože si musíte poradiť s kúskami nechtov. Ale rovnako ako v prípade add / sub je možné to urobiť efektívne na horizontálne vektorizovaných bignumoch.
AVX512-IFMA (prichádza s procesormi Cannonlake)bude mať pokyny, ktoré dávajú plných 104 bitov 52 x 52-bitového násobenia (pravdepodobne pomocou hardvéru FPU). To sa bude veľmi dobre hrať s reprezentáciami čiastočných slov, ktoré používajú 52 bitov na slovo.
Veľké násobenie pomocou FFT
Pre skutočne veľké bignumy sa násobenie najefektívnejšie robí pomocou Rýchle Fourierove transformácie (FFT).
FFT sú úplne vektorizovateľné, pretože pracujú na nezávislých doubles. Je to možné, pretože v zásade ide o reprezentáciu, ktorú používajú FFT je
čiastočné slovné zastúpenie.
Ak to zhrnieme, je možná vektorizácia aritmetiky bignum. Musia sa však priniesť obete.
Ak očakávate, že SSE / AVX bude schopný urýchliť existujúci bignum kód bez zásadných zmien v reprezentácii a / alebo rozložení údajov, je nepravdepodobné, že by k tomu došlo.
Ale napriek tomu je možné vektorizovať bignum aritmetiku.
zverejnenie:
Ja som autorom y-cruncher čo robí veľké množstvo veľkých čísel arihmeticky.