The Design of the PACLIB Kernel for Parallel Algebraic Computation

. This paper describes the runtime kernel of Paclib, a new system for parallel algebraic computation on shared memory computers. Paclib has been developed as a professional tool for the simple design and efficient implementation of parallel algorithms in computer algebra and related areas. It provides concurrency, shared memory communication, non-determinism, speculative parallelism, streams and a parallelized garbage collection. We explain the main design decisions as motivated by the special demands of algebraic computation and give several benchmarks that demonstrate the performance of the system. Paclib has been implemented on a Sequent Symmetry multiprocessor and is portable to other shared memory machines and workstations. 1 Introduction Computer algebra is that branch of computer science that aims to provide exact solutions of scientific problems. Research results of this area are e.g. algorithms for symbolic integration, polynomial factorization or the exact solution of algeb..