deposit_your_work

PARALLEL SOLUTION TO LINEAR RECURRENCE (ARCHITECTURE)

Files in this item

Files Size Format View
1330918.PDF 1.618Mb application/pdf Thumbnail

Show full item record

Item Metadata

Title: PARALLEL SOLUTION TO LINEAR RECURRENCE (ARCHITECTURE)
Author: MITRA, KAMAL VEDPRAKASH
Degree: Master of Science thesis
Abstract: 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.
Citation: MITRA, KAMAL VEDPRAKASH. (1987) "PARALLEL SOLUTION TO LINEAR RECURRENCE (ARCHITECTURE)." Masters Thesis, Rice University. http://hdl.handle.net/1911/13242.
URI: http://hdl.handle.net/1911/13242
Date: 1987

This item appears in the following Collection(s)