PARALLEL SOLUTION TO LINEAR RECURRENCE (ARCHITECTURE)

In this thesis we present an optimal time parallel solution to the problem of first order linear recurrence. Given a system of n first order equations, the proposed parallel algorithm solves it in time O(n/p + logp) on a multiprocessor system with p processors. The multiprocessor system may be operating in synchronous or asynchronous mode. Our solution is not very restrictive in its requirement of processor interconnection. It requires only that certain processors be able to communicate with certain other processors as compared to some of the previous solutions which require a shared memory model of a parallel machine and require up to n simultaneous requests to memory to be serviced in 0(1) (constant) time. We map this algorithm on models of parallel machines such as the hypercube, a single bus connected system, a linear array of processors and a d-dimensional mesh