Partitioned Logical boolean operations

Links

• https://bugs.libre-soc.org/show_bug.cgi?id=176
• https://bugs.libre-soc.org/show_bug.cgi?id=549

These are not the same as bitwise logical operations equivalent to:

 for i in range(64):
     result[i] = a[i] xor b[i] # 2 operands

The above returns a 64 bit result for 64 bit inputs.

they are instead SIMD versions of:

 result = 0 # initial value (single bit)
 for i in range(64):
     result = result xor a[i] # one operand

Each of the logic ops, "some bool any all xor" are a single bit for scalar, but for Partitioned SIMD produce one bit per lane.

Requirements

Given a signal width (typically 64) and given an array of "Partition Points" (typically 7) that break the signal down into an arbitrary permutaion of 8 bit to 64 bit independent SIMD results, compute the following:

• xor of all bits in each partitioned group, regardless of the partitioning
• "are some bits set" in each partitioned group
• "are all bits set" in each partitioned group

note that "are some bits set" is equivalent to "is a != 0" whilst "are all bits set" is equivalent to "is a == all 1s" or "is (~a) == 0"

xor operator as an example

instead of the above single 64 bit xor result, dynamic partitioned SIMD must return a batch of results. if the subdivision is 2x32 it is:

 result[0] = 0 # initial value for low word
 result[1] = 0 # initial value for hi word
 for i in range(32):
     result[0] = result[0] xor a[i]
     result[1] = result[1] xor a[i+32]

and likewise by the time 8x8 is reached:

 for j in range(8):
     result[j] = 0 # initial value for each byte
     for i in range(8):
         result[j] = result[j] xor a[i+j*8]

now the question becomes: what to do when the Signal is dynamically partitionable? how do we merge all of the combinations, 1x64 2x32 4x16 8x8 into the same statically-allocated hardware?

the first thing is to define some conventions, that the answer (result) will always be 8 bit (not 1 bit) and that, rather than just one bit being set if some are set, all 8 bits are clear or all 8 bits are set.

 if result[0]:             # bit 0 true?
     result[1:7] = 1111111 # set the remaining 7

likewise, when configured as 2x32 the result is subdivided into two 4 bit halves: the first half is all zero if all the first 32 bits are zero, and all ones if any one bit in the first 32 bits are set.

 result[0] = 0 # initial value for low word
 result[4] = 0 # initial value for hi word
 for i in range(32):
     result[0] = result[0] xor a[i]
     result[4] = result[4] xor a[i+32]
 if result[0]:
     result[1:3] = 111
 if result[4]:
     result[5:7] = 111

Thus we have a convention where the result is also a partitioned signal, and can be reconfigured to return 1x xor yes/no, 2x xor yes/no, 4x xor yes/no or up to 8 independent yes/no boolean values.

The second observation then is that, actually, just like the other partitioned operations, it may be possible to "construct" the longer results from the 8x8 ones, based on whether the partition gates are open or closed. This is further explored below.

Boolean truth table for Partitioned XOR

Exactly the same as for eq, instead the "xor" operator for example is the amalgamation of 4 partial results, x0 to x3.

partition:     P    P    P     (3 partition bits)
a        : .... .... .... .... (32 input bits)
xor-a    : x0  P x1 P x2 P x3  (4+3 bits, P=1 "breaks")

the partial results x0-x3 are computed as follows:

x0 = input[0:7].xor()
x1 = input[8:15].xor()
x2 = input[16:23].xor()
x3 = input[24:31].xor()

here is the table showing how to combine x0-3 based on partitions p0-2, to produce results o0-3

Example:

when p2p1p0 == 101 this indicates

• that the output is to contain:
  • an XOR of the top 8 bits
  • the middle 16 bits
  • and the low 8 bits.
• this in a 4 bit result (o3o2o1o0) divided into o3, o2o1 and o0
  • the top bit o3 of the 4-bit answer contains x3
  • the middle 2 bits o2o1 contain the XOR of x1 and x2
  • the first bit o0 contains x0.
• therefore, the final result:
  • the top bit contains the XOR of the input bits 24 to 31
  • the middle 2 bits contains the XOR of bits 8 to 15
  • the lowest bit contains the XOR of bits 0 to 7.

A different partition creates a completely different SIMD subdivision. This is entirely dynamic.