On 31/05/2021 03:01, hv90@xxxxxxxxxxxxxxxxxxxxxxx wrote: > From: Harishankar Vishwanathan <harishankar.vishwanathan@xxxxxxxxxxx> > > This patch introduces a new algorithm for multiplication of tristate > numbers (tnums) that is provably sound. It is faster and more precise when > compared to the existing method. > > Like the existing method, this new algorithm follows the long > multiplication algorithm. The idea is to generate partial products by > multiplying each bit in the multiplier (tnum a) with the multiplicand > (tnum b), and adding the partial products after appropriately bit-shifting > them. The new algorithm, however, uses just a single loop over the bits of > the multiplier (tnum a) and accumulates only the uncertain components of > the multiplicand (tnum b) into a mask-only tnum. The following paper > explains the algorithm in more detail: https://arxiv.org/abs/2105.05398. > > A natural way to construct the tnum product is by performing a tnum > addition on all the partial products. This algorithm presents another > method of doing this: decompose each partial product into two tnums, > consisting of the values and the masks separately. The mask-sum is > accumulated within the loop in acc_m. The value-sum tnum is generated > using a.value * b.value. The tnum constructed by tnum addition of the > value-sum and the mask-sum contains all possible summations of concrete > values drawn from the partial product tnums pairwise. We prove this result > in the paper. > > Our evaluations show that the new algorithm is overall more precise > (producing tnums with less uncertain components) than the existing method. > As an illustrative example, consider the input tnums A and B. The numbers > in the paranthesis correspond to (value;mask). > > A = 000000x1 (1;2) > B = 0010011x (38;1) > A * B (existing) = xxxxxxxx (0;255) > A * B (new) = 0x1xxxxx (32;95) > > Importantly, we present a proof of soundness of the new algorithm in the > aforementioned paper. Additionally, we show that this new algorithm is > empirically faster than the existing method. > > Co-developed-by: Matan Shachnai <m.shachnai@xxxxxxxxxxx> > Signed-off-by: Matan Shachnai <m.shachnai@xxxxxxxxxxx> > Co-developed-by: Srinivas Narayana <srinivas.narayana@xxxxxxxxxxx> > Signed-off-by: Srinivas Narayana <srinivas.narayana@xxxxxxxxxxx> > Co-developed-by: Santosh Nagarakatte <santosh.nagarakatte@xxxxxxxxxxx> > Signed-off-by: Santosh Nagarakatte <santosh.nagarakatte@xxxxxxxxxxx> > Signed-off-by: Harishankar Vishwanathan <harishankar.vishwanathan@xxxxxxxxxxx> Reviewed-by: Edward Cree <ecree.xilinx@xxxxxxxxx>
