2023/10/03 by Muhammed Fati̇h Balin, Xiaojing An, Balin, Muhammed Fatih +5
Computer Science · Engineering · #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Packing Problems #VLSI and FPGA Design Techniques
paper · pdf · doi:10.48550/arxiv.2310.02470
openalex publication_date 2023/10/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Partitioning for load balancing is a crucial first step to parallelize any type of computation. In this work, we propose SGORP, a new spatial partitioning method based on Subgradient Optimization, to solve the d-dimensional Rectilinear Partitioning Problem (RPP). Our proposed method allows the use of customizable objective functions as well as some user-specific constraints, such as symmetric partitioning on selected dimensions. Extensive experimental evaluation using over 600 test matrices shows that our algorithm achieves favorable performance against the state-of-the-art RPP and Symmetric RPP algorithms. Additionally, we show the effectiveness of our algorithm to do application-specific load balancing using two applications as motivation: Triangle Counting and Sparse Matrix Multiplication (SpGEMM), where we model their load-balancing problems as 3-dimensional RPPs.