Improving SUSP Simplification Algorithms In CUDA

This presentation introduces a new framework that boosts matrix multiplication efficiency using Uniquely Solvable Puzzles (USP) and a simpler subset called SUSP. We explain the basics of matrix multiplication and the theory behind USP and SUSP, then show through simulations how using SUSP can streamline computations by reducing overhead. Our work features a method for detecting large SUSP sizes and simplifying them, along with a search algorithm to pick the best SUSP candidates. To overcome the limitations of CPU processing, we also propose a GPU-accelerated approach, which our analysis shows significantly cuts processing time and improves scalability for large problems. Finally, we evaluate both CPU and GPU implementations, discussing performance, potential bottlenecks, and future research directions, including further algorithm optimizations, hybrid CPU-GPU architectures, and expanding the framework to more complex matrix operations.