wiki:ParabixTransform

Version 6 (modified by cameron, 4 years ago) (diff)

--

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.

Implementing the Parabix Transform

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 2k-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 2k-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 2k-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 2k bits as a single 2k-bit value. The following example illustrates this operation working with 16-bit (k=4) registers.

e1AaBbCcDdEeFfGgHh
e2JjKkLlMmNnPpQqRr
hsimd<2>::packh(e1, e2)ABCDEFGHJKLMNPQR

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 2k-bit value, as illustrated by the following example.

e1AaBbCcDdEeFfGgHh
e2JjKkLlMmNnPpQqRr
hsimd<8>::packh(e1, e2)CdDdGgHhLlMmQqRr

Using these operations it is possible to implement the ideal transposition strategy in a straightforward fashion. Given a 2k-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
}