|
|
|
# The Parabix Transform
|
|
|
|
|
|
|
|
The Parabix Transform transposes ordinary character stream data into sets of bit-parallel data streams, each stream containing one bit per original character code unit position.
|
|
|
|
Most often, byte-oriented streams of data in representations such as ASCII, ISO Latin 1 or UTF-8 are transposed into sets of 8 parallel bit streams, one stream for each bit of the corresponding code units. However, the concept also applies for character data streams
|
|
|
|
using larger code units, such as those using the 16-bit code units of UTF-16 or the 32-bit code units of UTF-32. In each case, the transposed representation consists of one bit stream each for each bit position in the code units. In the case of UTF-32, however, implementations typically produce only 21 bit streams, as the high 11 bits of each 32-bit code unit are always zero.
|
|
|
|
|
|
|
|
Depending on the available processor architecture, there are many ways that the Parabix
|
|
|
|
Transform may be implemented. Although the transformation can be performed in a serial
|
|
|
|
fashion extracting one bit at a time from each byte, the overhead of the serial approach greatly limits its usefulness. In this section, we concentrate instead on parallel methods that impose a relatively small overhead on the processing of character data streams.
|
|
|
|
|
|
|
|
## Ideal Three-Stage Parallel Transposition for Byte Streams
|
|
|
|
|
|
|
|
The Parabix Transform to transform byte-oriented character stream data to bit-parallel data streams
|
|
|
|
can be implemented in a parallel fashion using the following
|
|
|
|
three-stage transposition strategy.
|
|
|
|
|
|
|
|
1. Transform the byte stream data into two parallel nybble streams, one for the high nybble of each byte, and one for the low nybble of each byte. (A nybble is one-half of a byte, i.e., 4 bits).
|
|
|
|
2. Transform each of the nybble streams into two parallel bit-pair streams. Each bit-pair stream consists of a stream of 2-bit units in one-to-one correspondence with the input byte stream. The bit-pairs in the first such stream consist of bits 0 and 1 of each byte, the bit-pairs in the second stream consist of bits 2 and 3 of each byte, the bit-pairs in the third stream consist of bits 4 and 5 of each byte and the bit-pairs in the fourth and final bit-pair stream consist of the bits 6 and 7 of each byte.
|
|
|
|
3. Transform each of the bit-pair streams into two individual bit streams.
|
|
|
|
|
|
|
|
|
|
|
|
### Ideal Implementation Using SIMD Packing
|
|
|
|
|
|
|
|
Given a processor architecture that supports binary SIMD operations on 2^k^-bit
|
|
|
|
registers, an ideal implementation of the Parabix Transposition can be based
|
|
|
|
on the availability of a family of horizontal packing operations. The operations
|
|
|
|
required each have the IDISA pattern `hsimd<{2,4,8}>::pack{h,l}(e1, e2)`,
|
|
|
|
in which `e1` and `e2` are 2^k^-bit input registers,
|
|
|
|
the field width of the fields processed is either 2, 4, or 8, and
|
|
|
|
the packing operation selects the bits comprising either the high (`h`) or low (`l`) half of each field. The result in each case is a single 2^k^-bit value
|
|
|
|
comprising the packed bits that are selected. For example,
|
|
|
|
`hsimd<2>::packh(e1, e2)` selects the high bit of each 2-bit field
|
|
|
|
in the concatenation of `e1` and `e2`, returning the packed set of
|
|
|
|
2^k^ bits as a single 2^k^-bit value.
|
|
|
|
The following example illustrates this operation working with 16-bit (k=4) registers.
|
|
|
|
|
|
|
|
| Expression | Field 1 | Field 2 |
|
|
|
|
| ---------- | ------- | ------- |
|
|
|
|
|`e1`|`AaBbCcDd`|`EeFfGgHh`|
|
|
|
|
|`e2`|`JjKkLlMm`|`NnPpQqRr`|
|
|
|
|
|`hsimd<2>::packh(e1, e2)`|`ABCDEFGH`|`JKLMNPQR`|
|
|
|
|
|
|
|
|
Similarly, `hsimd<8>::packl(e1, e2)`
|
|
|
|
selects the low 4-bits of each 8-bit field in the concatenation of `e1` and `e2`,
|
|
|
|
again returning the result as a single 2^k^-bit value, as illustrated by the following example.
|
|
|
|
|
|
|
|
| Expression | Field 1 | Field 2 |
|
|
|
|
| ---------- | ------- | ------- |
|
|
|
|
|`e1`|`AaBbCcDd`|`EeFfGgHh`|
|
|
|
|
|`e2`|`JjKkLlMm`|`NnPpQqRr`|
|
|
|
|
|`hsimd<8>::packl(e1, e2)`|`CdDdGgHh`|`LlMmQqRr`|
|
|
|
|
|
|
|
|
Using these operations it is possible to implement the ideal transposition
|
|
|
|
strategy in a
|
|
|
|
straightforward fashion. Given a 2^k^-byte sequence held consecutively
|
|
|
|
in 8 registers `s0`, `s1`, … `s7`, the following
|
|
|
|
3-step transformation process performs transposition to parallel bit streams.
|
|
|
|
|
|
|
|
```
|
|
|
|
// Transpose to 2 nybble streams
|
|
|
|
lo_nybble0 = hsimd::packl(s0, s1);
|
|
|
|
lo_nybble1 = hsimd::packl(s2, s3);
|
|
|
|
lo_nybble3 = hsimd::packl(s4, s5);
|
|
|
|
lo_nybble4 = hsimd::packl(s6, s7);
|
|
|
|
hi_nybble0 = hsimd::packh(s0, s1);
|
|
|
|
hi_nybble1 = hsimd::packh(s2, s3);
|
|
|
|
hi_nybble3 = hsimd::packh(s4, s5);
|
|
|
|
hi_nybble4 = hsimd::packh(s6, s7);
|
|
|
|
// Transpose 2 nybble streams to 4 bit-pair streams.
|
|
|
|
bit01pair_0 = hsimd::packl(lo_nybble0, lo_nybble1);
|
|
|
|
bit01pair_1 = hsimd::packl(lo_nybble2, lo_nybble3);
|
|
|
|
bit23pair_0 = hsimd::packh(lo_nybble0, lo_nybble1);
|
|
|
|
bit23pair_1 = hsimd::packh(lo_nybble2, lo_nybble3);
|
|
|
|
bit45pair_0 = hsimd::packl(hi_nybble0, hi_nybble1);
|
|
|
|
bit45pair_1 = hsimd::packl(hi_nybble2, hi_nybble3);
|
|
|
|
bit67pair_0 = hsimd::packh(hi_nybble0, hi_nybble1);
|
|
|
|
bit67pair_1 = hsimd::packh(hi_nybble2, hi_nybble3);
|
|
|
|
// Transpose 4 bit-pairs streams to 8 bit streams.
|
|
|
|
bit0 = hsimd::packl(bit01pair_0, bit01pair_1);
|
|
|
|
bit1 = hsimd::packh(bit01pair_0, bit01pair_1);
|
|
|
|
bit2 = hsimd::packl(bit23pair_0, bit23pair_1);
|
|
|
|
bit3 = hsimd::packh(bit23pair_0, bit23pair_1);
|
|
|
|
bit4 = hsimd::packl(bit45pair_0, bit45pair_1);
|
|
|
|
bit5 = hsimd::packh(bit45pair_0, bit45pair_1);
|
|
|
|
bit6 = hsimd::packl(bit67pair_0, bit67pair_1);
|
|
|
|
bit7 = hsimd::packh(bit67pair_0, bit67pair_1);
|
|
|
|
```
|
|
|
|
|
|
|
|
Overall, transposition requires 8 pack operations for each of the three transposition steps, for a total
|
|
|
|
of 24 operations for the entire process.
|
|
|
|
|
|
|
|
### Implementation of Ideal Packing Using Bit Shuffles
|
|
|
|
|
|
|
|
Unfortunately, the `hsimd<{2,4,8}>::pack{h,l}(e1, e2)` family of operations for
|
|
|
|
ideal transposition are not to be found within the SIMD instruction set of current
|
|
|
|
commodity processors. However, if ''bit shuffle'' operations are to be found instead,
|
|
|
|
then the pack operations can be expressed directly in terms of equivalent
|
|
|
|
bit shuffles. Bit shuffles can be found both at the intermediate representation
|
|
|
|
level with the LLVM `shufflevector` operation and at the processor ISA level
|
|
|
|
in terms of the Haswell new instruction `pext`.
|
|
|
|
|
|
|
|
The LLVM `shufflevector` operation allows a result vector to be populated
|
|
|
|
by directly selecting elements from a concatenated pair of input vectors.
|
|
|
|
A constant vector of `i32` selectors lets each vector element be selected
|
|
|
|
from any of the positions within either of the two input vectors. For example,
|
|
|
|
working with 8-bit input vectors (for simplicity of the example), the
|
|
|
|
`hsimd<2>::pack{h,l}(e1, e2)` operations may be translated directly into
|
|
|
|
`shufflevector` operations.
|
|
|
|
```
|
|
|
|
define <8 x i1> @hsimd_packh_2(<8 x i1> %x, <8 x i1> %y) {
|
|
|
|
%result = shufflevector <8 x i1> %x, <8 x i1> %y,
|
|
|
|
<8 x i32> <i32 1, i32 3, i32 5, i32 7, i32 9, i32 11, i32 13, i32 15>
|
|
|
|
return <8 x i1> result
|
|
|
|
}
|
|
|
|
define <8 x i1> @hsimd_packl_2(<8 x i1> %x, <8 x i1> %y) {
|
|
|
|
%result = shufflevector <8 x i1> %x, <8 x i1> %y,
|
|
|
|
<8 x i32> <i32 0, i32 2, i32 4, i32 6, i32 8, i32 10, i32 12, i32 14>
|
|
|
|
return <8 x i1> result
|
|
|
|
}
|
|
|
|
```
|
|
|
|
|
|
|
|
Similarly, it is straightforward to define the additional `hsimd<{4,8}>::pack{h,l}(e1, e2)`
|
|
|
|
operations on 8-bit registers as follows.
|
|
|
|
```
|
|
|
|
define <8 x i1> @hsimd_packh_4(<8 x i1> %x, <8 x i1> %y) {
|
|
|
|
%result = shufflevector <8 x i1> %x, <8 x i1> %y,
|
|
|
|
<8 x i32> <i32 2, i32 3, i32 6, i32 7, i32 10, i32 11, i32 14, i32 15>
|
|
|
|
return <8 x i1> result
|
|
|
|
}
|
|
|
|
define <8 x i1> @hsimd_packl_4(<8 x i1> %x, <8 x i1> %y) {
|
|
|
|
%result = shufflevector <8 x i1> %x, <8 x i1> %y,
|
|
|
|
<8 x i32> <i32 0, i32 1, i32 4, i32 5, i32 8, i32 9, i32 12, i32 13>
|
|
|
|
return <8 x i1> result
|
|
|
|
}
|
|
|
|
```
|
|
|
|
```
|
|
|
|
define <8 x i1> @hsimd_packh_8(<8 x i1> %x, <8 x i1> %y) {
|
|
|
|
%result = shufflevector <8 x i1> %x, <8 x i1> %y,
|
|
|
|
<8 x i32> <i32 4, i32 5, i32 6, i32 7, i32 12, i32 13, i32 14, i32 15>
|
|
|
|
return <8 x i1> result
|
|
|
|
}
|
|
|
|
define <8 x i1> @hsimd_packl_8(<8 x i1> %x, <8 x i1> %y) {
|
|
|
|
%result = shufflevector <8 x i1> %x, <8 x i1> %y,
|
|
|
|
<8 x i32> <i32 0, i32 1, i32 2, i32 3, i32 8, i32 9, i32 10, i32 11>
|
|
|
|
return <8 x i1> result
|
|
|
|
}
|
|
|
|
```
|
|
|
|
|
|
|
|
Alternatively, we may implement `hsimd<{4,8}>::pack{h,l}(e1, e2)` using
|
|
|
|
`shufflevector` with `i2` and `i4` vectors.
|
|
|
|
|
|
|
|
```
|
|
|
|
define <4 x i2> @hsimd_packh_4(<4 x i2> %x, <4 x i2> %y) {
|
|
|
|
%result = shufflevector <4 x i2> %x, <4 x i2> %y,
|
|
|
|
<4 x i32> <i32 1, i32 3, i32 5, i32 7>
|
|
|
|
return <4 x i2> result
|
|
|
|
}
|
|
|
|
define <4 x i2> @hsimd_packl_4(<4 x i2> %x, <4 x i2> %y) {
|
|
|
|
%result = shufflevector <4 x i2> %x, <4 x i2> %y,
|
|
|
|
<4 x i32> <i32 0, i32 2, i32 4, i32 6>
|
|
|
|
return <4 x i2> result
|
|
|
|
}
|
|
|
|
|
|
|
|
define <2 x i4> @hsimd_packh_8(<2 x i4> %x, <2 x i4> %y) {
|
|
|
|
%result = shufflevector <2 x i4> %x, <2 x i4> %y,
|
|
|
|
<2 x i32> <i32 1, i32 3>
|
|
|
|
return <2 x i4> result
|
|
|
|
}
|
|
|
|
define <2 x i4> @hsimd_packl_8(<2 x i4> %x, <2 x i4> %y) {
|
|
|
|
%result = shufflevector <2 x i4> %x, <2 x i4> %y,
|
|
|
|
<2 x i32> <i32 0, i32 2>
|
|
|
|
return <2 x i4> result
|
|
|
|
}
|
|
|
|
```
|
|
|
|
|
|
|
|
## Byte Pack Implementation of the Parabix Transform
|
|
|
|
|
|
|
|
Although SIMD units typically do not provide direct bit packing implementations,
|
|
|
|
''byte packing'' operations that extract bytes from 16-bit fields are common.
|
|
|
|
The `simd<16>::packh` and `simd<16>::packl` operations on 64-bit vectors
|
|
|
|
arranged into 16-bit fields are illustrated by the following examples.
|
|
|
|
|
|
|
|
| Expression | Field 1 | Field 2 | Field 3 | Field 4 |
|
|
|
|
| ---------- | ------- | ------- | ------- | ------- |
|
|
|
|
| s0 | 0x0123 | 0x4567 | 0x89AB | 0xCDEF |
|
|
|
|
| s1 | 0xaabb | 0xccdd | 0xeeff | 0x0011 |
|
|
|
|
| simd<16>::packh(s0, s1) | 0x0145 | 0x89CD | 0xaacc | 0xee00 ||
|
|
|
|
| simd<16>::packl(s0, s1) | 0x2367 | 0xABEF| 0xbbdd | 0xff11 ||
|
|
|
|
|
|
|
|
### Three-Stage Transposition Using Byte Packing ###
|
|
|
|
|
|
|
|
The following library code of the Parabix system implements three-stage
|
|
|
|
transposition using byte packing.
|
|
|
|
|
|
|
|
```
|
|
|
|
#define s2p_step(s0, s1, hi_mask, shift, p0, p1) \
|
|
|
|
do {\
|
|
|
|
BitBlock t0,t1;\
|
|
|
|
t0 = hsimd<16>::packh(s0, s1);\
|
|
|
|
t1 = hsimd<16>::packl(s0, s1);\
|
|
|
|
p0 = simd<1>::ifh(hi_mask, t0, simd<16>::srli<shift>(t1));\
|
|
|
|
p1 = simd<1>::ifh(hi_mask, simd<16>::slli<shift>(t0), t1);\
|
|
|
|
} while(0)
|
|
|
|
|
|
|
|
#define s2p_bytepack(s0, s1, s2, s3, s4, s5, s6, s7, p0, p1, p2, p3, p4, p5, p6, p7) \
|
|
|
|
do {\
|
|
|
|
BitBlock bit00224466_0,bit00224466_1,bit00224466_2,bit00224466_3;\
|
|
|
|
BitBlock bit11335577_0,bit11335577_1,bit11335577_2,bit11335577_3;\
|
|
|
|
BitBlock bit00004444_0,bit22226666_0,bit00004444_1,bit22226666_1;\
|
|
|
|
BitBlock bit11115555_0,bit33337777_0,bit11115555_1,bit33337777_1;\
|
|
|
|
s2p_step(s0,s1,simd<2>::himask(),1,bit00224466_0,bit11335577_0);\
|
|
|
|
s2p_step(s2,s3,simd<2>::himask(),1,bit00224466_1,bit11335577_1);\
|
|
|
|
s2p_step(s4,s5,simd<2>::himask(),1,bit00224466_2,bit11335577_2);\
|
|
|
|
s2p_step(s6,s7,simd<2>::himask(),1,bit00224466_3,bit11335577_3);\
|
|
|
|
s2p_step(bit00224466_0,bit00224466_1,simd<4>::himask(),2,bit00004444_0,bit22226666_0);\
|
|
|
|
s2p_step(bit00224466_2,bit00224466_3,simd<4>::himask(),2,bit00004444_1,bit22226666_1);\
|
|
|
|
s2p_step(bit11335577_0,bit11335577_1,simd<4>::himask(),2,bit11115555_0,bit33337777_0);\
|
|
|
|
s2p_step(bit11335577_2,bit11335577_3,simd<4>::himask(),2,bit11115555_1,bit33337777_1);\
|
|
|
|
s2p_step(bit00004444_0,bit00004444_1,simd<8>::himask(),4,p0,p4);\
|
|
|
|
s2p_step(bit11115555_0,bit11115555_1,simd<8>::himask(),4,p1,p5);\
|
|
|
|
s2p_step(bit22226666_0,bit22226666_1,simd<8>::himask(),4,p2,p6);\
|
|
|
|
s2p_step(bit33337777_0,bit33337777_1,simd<8>::himask(),4,p3,p7);\
|
|
|
|
} while(0)
|
|
|
|
```
|
|
|
|
|
|
|
|
|
|
|
|
### Byte Pack Using SSE2 `packuswb`
|
|
|
|
|
|
|
|
For example the SSE2 instruction `packuswb` packs 16-byte integers into
|
|
|
|
bytes using unsigned saturation. By clearing the high 8 bits of the 16-bit
|
|
|
|
field, this operation can be efficiently used to implement both the
|
|
|
|
`hsimd<16>::packh` and `hsimd<16>::packl` operations.
|
|
|
|
|
|
|
|
```
|
|
|
|
template <> bitblock_t hsimd<16>::packh(bitblock_t arg1, bitblock_t arg2)
|
|
|
|
{
|
|
|
|
return _mm_packus_epi16(_mm_srli_epi16(arg2, 8), _mm_srli_epi16(arg1, 8));
|
|
|
|
}
|
|
|
|
|
|
|
|
template <> bitblock_t hsimd<16>::packl(bitblock_t arg1, bitblock_t arg2)
|
|
|
|
{
|
|
|
|
const bitblock_t lomask = simd<16>::constant(0x00FF);
|
|
|
|
return _mm_packus_epi16(simd_and(arg2, lomask), simd_and(arg1, lomask));
|
|
|
|
}
|
|
|
|
```
|
|
|
|
|
|
|
|
### Byte Pack Using Byte Shuffling ###
|
|
|
|
|
|
|
|
Byte pack operations are also conveniently modeled as byte shuffle operations.
|
|
|
|
Thus, LLVM versions of pack are straightforward.
|
|
|
|
```
|
|
|
|
define <8 x i16> @hsimd_packh_16(<8 x i16> %x, <8 x i16> %y) {
|
|
|
|
%result = shufflevector <8 x i16> %x, <8 x i16> %y,
|
|
|
|
<8 x i32> <i32 1, i32 3, i32 5, i32 7, i32 9, i32 11, i32 13, i32 15>
|
|
|
|
return <8 x i16> result
|
|
|
|
}
|
|
|
|
define <8 x i16> @hsimd_packl_16(<8 x i16> %x, <8 x i16> %y) {
|
|
|
|
%result = shufflevector <8 x i16> %x, <8 x i16> %y,
|
|
|
|
<8 x i32> <i32 0, i32 2, i32 4, i32 6, i32 8, i32 10, i32 12, i32 14>
|
|
|
|
return <8 x i16> result
|
|
|
|
}
|
|
|
|
```
|
|
|
|
|
|
|
|
Given `shufflevector` operations satisfying the byte pack model,
|
|
|
|
an LLVM code generator can conceivably produce the SSE2-based implementations
|
|
|
|
shown previously, while an SSE3-based implementation might directly use
|
|
|
|
the byte shuffle operation `pshufb`.
|
|
|
|
|