Optimize Bucket Point Reduction

[FoodChain1028]

Problem

Current algorithm of bucket point reduction is not suitable for parallel computation. Instead, we should change this algorithm in a parallelized version.

Details

The pBPR (parallel Bucket Points Reduction) algorithm is originated from cuzk paper and we will take reference from zprize-2023 winner.

$$ \sum_{l=1}^{2^{s-1}} lB_l $$

This algorithm splits the buckets into multiple threads, computes the running sum of the points in each thread, multiplying each running sum by a required amount.

B7 +
B7 + B6 +
B7 + B6 + B5 + 
B7 + B6 + B5 + B4 +
B7 + B6 + B5 + B4 + B3 +
B7 + B6 + B5 + B4 + B3 + B2 +
B7 + B6 + B5 + B4 + B3 + B2 + B1 +
B7 + B6 + B5 + B4 + B3 + B2 + B1 + B0 =
/*
t0      | t1      | t2      | t3
*/
// Thread 0 computes:
B7 +
B7 + B6 +
(B7 + B6) * 6
// Thread 1 computes:
B5 +
B5 + B4 +
(B5 + B4) * 4
// Thread 2 computes:
B3 +
B3 + B2 +
(B3 + B2) * 2
// Thread 3 computes:
B1 +
B1 + B0

Acceptance criteria

1. writing bpr in rust (host side).
2. should use metal shader to generate the correct reduction result.

Next steps (optional)

This algorithm will be integrated in the future to make MSM work.