Concurrency in a System for Symbolic and Algebraic Computations

As miniaturization of computer components is approaching the limits of physics, researchers in computer architecture are looking for less conventional means to perpetuate Moore's law. Recent trends in hardware ve been adding more cores. Consequently multicore machines are now commodity. To help programmers benefit from Moore's dividend, researchers in programming techniques, tools and languages have been exploring several venues. A dominant theme is the design and implementation of parallel algorithms. Several programming models have been proposed, but none at the moment seem to be substantially better than others. While general parallel programming is a distinctively challenging task, we believe that scientific computation algorithms display algebraic structures, thanks to the rich mathematical objects they manipulate. The present work aims at exploring the extent to which algebraic properties displayed by computer algebra algorithms may be automatically exploited to take advantage of parallelism in the OpenAxiom scientific computation platform. We designed a runtime system that exploits the ubiquitous parallelism of modern CPUs; the system is also scaled to many-system clusters. By taking advantage of the existing InputForm domain in OpenAxiom and connecting of the standard input channel to sockets, we were able to minimize potentially hazardous modifications to the OpenAxiom source while still implementing desired functionality. Additionally, we designed and implemented FFI extensions to the OpenAxiom core to take advantage of SIMD instructions, particularly SSE2 (SIMD Streaming Extensions). The extension allowed us to nearly double the speed of common operations such as multiplying arrays of doubles. We also defined and implemented a foreign function interface for the OpenAxiom system. All of these additions were benchmarked using Berlekamp's algorithm for factorization of polynomials over integers. While much still remains to be done in parallelizing the algebra to work over many calculation nodes, mathematical annotations remain viable in unloading the burden of parallelizing code from the programmer by substituting a simpler activity