2019/01/09 by John P. Charlton, John Charlton, Steve Maddock +1 · 5 citations
Computer Science · Mathematics · #Algorithm #CUDA #Central processing unit #Computational science #Computer graphics (images) #Computer hardware #Computer science #Distributed and Parallel Computing Systems #Domain (mathematical analysis) #Graphics #Graphics processing unit #Linear programming #Mathematics #Operating system #Optimization and Search Problems #Parallel Computing and Optimization Techniques #Parallel computing #State (computer science) #Unit (ring theory) #Workload #cs.DC
paper · pdf · doi:10.1016/j.jpdc.2019.01.001
published in Journal of Parallel and Distributed Computing 126, 152-160 (Elsevier BV) · 22 pages, 11 figures, 1 listing
openalex publication_date 2019/01/09 · arxiv created 2019/02/13 · arxiv updated 2019/02/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
This paper presents a novel, high-performance, graphical processing unit-based algorithm for efficiently solving two-dimensional linear programs in batches. The domain of two-dimensional linear programs is particularly useful due to the prevalence of relevant geometric problems. Batch linear programming refers to solving numerous different linear programs within one operation. By solving many linear programs simultaneously and distributing workload evenly across threads, graphical processing unit utilization can be maximized. Speedups of over 22 times and 63 times are obtained against state-of-the-art graphics processing unit and CPU linear program solvers, respectively.