Space Exploration using Parallel Orbits: a Study in Parallel Symbolic Computing

Abstract. Orbit enumerations represent an important class of mathemat-ical algorithms which is widely used in computational discrete mathe-matics. In this paper, we present a new shared-memory implementation of a generic Orbit skeleton in the GAP computer algebra system [5,6]. By defining a skeleton, we are easily able to capture a wide variety of concrete Orbit enumerations that can exploit the same underlying par-allel implementation. We also propose a generic cost model for predict-ing the speedups that our Orbit skeleton will deliver for a given appli-cation on a given parallel system. We demonstrate the scalability of our implementation on a 64-core shared-memory machine. Our results show that we are able to obtain good speedups over sequential GAP programs (up to 36 on 64 cores)