Parallel term rewriting with PaReDuX. There are two major approaches to parallelizing software for symbolic computation. The first approach to parallelizing symbolic computation software relies on work parallelism (AND-parallelism), which spreads a given amount of work over a number of processors. If only work parallelism is used, then the parallel completion algorithm executes exactly the same strategy no matter how many processors it runs on, and therefore we also speak of a strategy compliant parallelization. Due to the high synchronization requirement of a single completion loop with a fixed strategy, and the fine grain of its parallel components, strategy compliant parallelization is typically only profitable on shared memory multiprocessors.par In a first part of this chapter we focus on this approach to parallelizing term rewriting systems. The second approach to parallelizing software for symbolic computation uses search parallelism (OR-parallelism). The goal of the second part of this chapter is twofold. Algorithmically, we want to show that the modular combination of search parallelism and work parallelism on an hierarchical memory processor can yield aggregate speed ups exceeding those of each isolated scheme and can overcome the limits that both approaches to parallel completion have. These limits are given by the facts that the speed-ups of search parallelism are limited by the number and relative quality of different selection strategies; work parallelism is limited by the amount of parallel work within each strategy and by the architectural constraints of today’s shared memory processors that allow at most a few dozen processors. Our second goal is to demonstrate that a uniform programming technique can be used for the network part and the shared memory part.

References in zbMATH (referenced in 1 article , 1 standard article )

Showing result 1 of 1.
Sorted by year (citations)

  1. Bündgen, Reinhard; Göbel, Manfred; Küchlin, Wolfgang; Weber, Andreas: Parallel term rewriting with PaReDuX (1998)