POWER9 and Z14 have introduced ' vmsumudm' and 'vmslg' instructions
respectively for full 64-bit vector multiplication. This note demonstrates
implementing Poly1305 based on radix 2^44 for optimal architecture
utilization.
In radix B = 2^44 we have the state and key as follows
H = B^2 H_2 + B H_1 + H_0
R = B^2 R_2 + B R_1 + R_0
Where degrees of H_2 and R_2 are 42 and 36 respectively whereas other
coefficients are of degree 44
We have B^3 = 20 so we can pre-compute R_1' = 20 * R_1 and R_2' = 20 * R_2
Now to multiply H by R we can write
R H = B^2(R_2 H_0 + R_1 H_1 + R_0 H_2) + B(R_1 H_0 + R_0 H_1 + R_2' H_2)
\____________T2__________/
\____________T1__________/
+ R_0 H_0 + R_2' H_1 + R_1' H_2
\____________T0___________/
T_0 < 2^88 + 2^85 + 2^91 = 2^93
T_1 < 2^88 + 2^88 + 2^83 = 2^90
T_2 < 2^80 + 2^88 + 2^86 = 2^90
This is a good place to combine the interleaved multiplication state
products of next consecutive blocks (In this case we interleave four-block
multiplications by per-computing powers of key R) which rises up the degree
of product parts.
T_0 < 2^93 + 3*2^93 = 2^96
T_1 < 2^90 + 3*2^91 = 2^94
T_2 < 2^90 + 3*2^90 = 2^93
Now let's reduce this product to 2^130 divided to 2^44, 2^44, 2^42 for each
part.
T_0 ------------> T_1 ---------------> T_2 -------------------> T_0
---------------> T_1
(96-44) (94-44+1) (93-42+1+3)
(55-44+1)
This chain keeps the carry addition for the last part (2^44+2^12) less than
2^44+2^22.
Note the carry from T_2 would be multiplied by 5 before adding it to T_0
While the sequential carry addition achieves decent performance speed on
PowerPC arch, an interleaved carry handling would get more speed up for
s390x so let's figure an interleaved variant of carry addition.
*----------------------------------------------------------------------------------------------*
| Phase 1 | Phase 2 |
Phase 3 |
|------------------------------|---------------------------------|-------------------------------|
| T_1 ------------> T_2 | T_2 -----------------> T_0 | T_0
--------------> T_1 |
| (94-44) | (93-42+1+3) |
(55-44+1) |
|------------------------------|---------------------------------|-------------------------------|
| T_0 -------------> T_1 | T_1 --------------> T_2 |
|
| (96-44) | (52-44+1)
| |
*-----------------------------------------------------------------------------------------------*
This variant implies 3 sequential phases rather than four. Moreover, the
long carry path from T_2 -> T_0 would've executed in parallel with another
carry path.
Patches of implementation based on radix 2^44 for both architectures are
submitted to nettle with fat build support.
https://git.lysator.liu.se/nettle/nettle/-/merge_requests/39
https://git.lysator.liu.se/nettle/nettle/-/merge_requests/41
Benchmark the implementations on POWER9 and Z15
*---------------------------------------------------------------------------------------------*
| Arch | Nettle patch (radix 2^44) | OpenSSL (radix
2^26) |
|-------------------|--------------------------------------|-----------------------------------|
| PowerPC | 0.972 cycles/byte | 1.453 cycles/byte
|
|-------------------|--------------------------------------|-----------------------------------|
| IBMz | 0.840 cycles/byte | 0.936
cycles/byte |
*---------------------------------------------------------------------------------------------*
This note can also be applied on x86_64 arch with 'AVX512VL' and
'AVX512_IFMA' extension support by utilizing 'VPMADD52HUQ' and
'VPMADD52LUQ' instructions of full 52-bit multiplication.
regards,
Mamone
_______________________________________________
nettle-bugs mailing list
[email protected]
http://lists.lysator.liu.se/mailman/listinfo/nettle-bugs
