Optimize Point Coordinate Conversion and Scalar Decomposition in Metal MSM Implementation

[moven0831]

Related issue

• Optimize Metal MSM Implementation for Enhanced GPU Utilization #1

Problem

The current implementation of point coordinate conversion and scalar decomposition in the Metal version of the MSM algorithm can be further optimized to improve performance and memory usage.

Details

1. Convert elliptic curve points from Jacobian coordinates to Montgomery form using Barrett Reduction. This conversion enables more efficient arithmetic operations in the subsequent stages of the MSM algorithm.

2. Decompose scalars into chunks using the signed bucket index technique. This method reduces the number of buckets by half, enhancing parallel processing efficiency and balancing the workload across Metal's GPU threads.

3. Optimize memory access patterns and buffer handling in the Metal shaders to minimize data transfer overhead and maximize GPU utilization.

Acceptance Criteria

• Implement a Metal shader function to convert Jacobian coordinates to Montgomery form using Barrett Reduction.
• Modify the scalar decomposition logic in the Metal shader to use the signed bucket index technique, decomposing scalars into chunks with signed indices.
• Validate the correctness of the point coordinate conversion and scalar decomposition through comprehensive testing with various input sizes and distributions.

References

• Montgomery Arithmetic
• Barrett Reduction
• Signed Bucket Index Method
• cuZK Paper - Algorithm Adaptation
• ZPrize 2023 Prize 2, Tal Derei and Koh Wei Jie