ABSTRACT AND-PARALLEL MACHINES

Abstract

Several abstract models of fine-grained parallelism, suited to symbolic programming languages, are suggested. The first, the  and-parallel Turing machine, can be viewed as a generalization of the deterministic Turing machine in which the infinite tape is replaced by an infinite tree-like tape on which processors work in parallel. With this model one can express in a very natural way communication between processors, suspension, and synchronization.  There are examples in which the processing time is polylogarithmic in the size of the input while for a nondeterministicTuring machine that looks at its input the time must be at least of the order of magnitude of the size of the input.  Then a stronger model, the  parallel rewriting machine, is introduced. Transitions are formulated as rewrite rules, resulting in a machine that is much easier to program.  This also adds a `pointer capability' to the previous machine.  Since this machine gets the program in a form that reflects its meaning, problems of synchronization are easily handled - rewrite rules just cannot be applied before arguments reach the right form. In both models a processor can launch other processors on subcomputations, but processing at a parent node must wait for answers from all of its "children''. One can introduce more powerful models that contain the possibility of an interrupt - if the answer from one child (or several children) is sufficient to continue the computation at the parent, the computation started by the other children can and should be interrupted.  These  interrupt machines are much more powerful than the previous two, but it does not seem to be much more difficult to implement them.  Although the machines considered are very powerful - the parallel rewriting  machine can compute the permanent in polynomial time and the and-parallel Turing machine with interrupt can simulate a nondeterministic Turing machine and an alternating Turing machine - they can be seen as models of realistic machines if time and space are suitably restricted.