Parallel sparse polynomial multiplication using heaps
Michael Monagan, Roman Pearce · International Symposium on Symbolic and Algebraic Computation · 2009
We present a high performance algorithm for multiplying sparse distributed polynomials using a multicore processor. Each core uses a heap of pointers to multiply parts of the polynomials using its local cache. Intermediate results are written to buffers in shared cache and the cores take turns combining them to form the result. A cooperative approach is used to balance the load and improve scalability, and the extra cache from each core produces a superlinear speedup in practice. We present benchmarks comparing our parallel routine to a sequential version and to the routines of other computer algebra systems.
Cited by 65 works. doi:10.1145/1576702.1576739
Authors
References
- The Magma Algebra System I: The User Language
- The cache performance and optimizations of blocked algorithms
- SINGULAR — A computer algebra system for polynomial computations
- Parallel Programming: Techniques and Applications Using Networked Workstations and Parallel Computers
- Synchronization with eventcounts and sequencers
- A class of compatible cache consistency protocols and their support by the IEEE futurebus
- Sparse polynomial arithmetic
- A simple load balancing scheme for task allocation in parallel machines
- Introduction to Parallel Algorithms
- The cache performance and optimizations of blocked algorithms