Poster Type: ACM SRC Posters
Author: Minh Phuc Nguyen (Union College)
Abstract: Simplifiable strong uniquely solvable puzzles (SUSPs) connect combinatorial search to upper bounds on the matrix-multiplication exponent. The process of evaluating each candidate requires expensive parallel workloads, which have been handled efficiently using GPUs. However, the existing search sent one candidate at a time to a GPU, so allocation, data transfer, and synchronization cost all the benefits of fast evaluation on a GPU. We redesigned the search by batching same-size candidates into one kernel launch. Besides that, we also optimized the workflow by decoupling GPU work from multi-threaded search expansion on the CPU. In our experiments, the single-GPU pipeline raised end-to-end throughput by 3.09–5.75 times, while the double-GPU pipeline could achieve over 11 times. With a new, better search program, we found a new (79, 10)-SUSP, improving on the best width-10 result reported by Anderson and Le.
Best Poster Finalist (BP): no
Poster: PDF
Poster Summary: PDF