Introduction

Most of the present algorithms are sequential.i.e., they specify sequence of steps in which each of the step consist of a single operation. However, the architectures in the market are going more and more towards the Parallel, from the start of multi-core systems. In contrast to a sequential algorithm, a Parallel algorithm will perform multiple operations in a single step. Consider the problem of computing sum of a sequence, $A$ of $n$ numbers. The standard sequential algorithm computes sum by making a single pass through the sequence, keeping a running sum of numbers seen so far. It is not difficult to device an algorithm to perform many operations in parallel. For example, each number of $A$ having an index $i$ paired with it, it is possible to pair $A[0]$ with $A[1]$, $A[2]$ with $A[3]$, and so on; the result is a new sequence $\lceil\frac{n}{2} \rceil$ numbers, whose sum is identical to earlier and will take half the steps. If this pairing is repeated, it would take only $\lceil \log_2 n\rceil$ steps for complete sum. Note that in $[\frac{n}{2}]$ steps there will be $[\frac{n}{2}]$ sums, next similarly, $[\frac{n}{4}]$, and so on.

The parallelism can result to improved performance. For example, in parallel architecture, operations in a single parallel algorithm can be executed simultaneously on different processors. The parallel algorithm can be executed even in a single processor system, using multiple functional units, for example, pipeline and array processors. A parallel algorithm will run at least as fast, as there are parallel processing units are existing in a computer. A good parallel algorithm is expected to run in both the parallel and sequential architecture.