###### tags: `Assignment`, `Parallel Programming`

# 1. Parallel Prefix Algor. Proof

Given $n$ numbers $a_1, a_2, ..., a_{n}$,
denote the $i_{th}$ number at the $k_{th}$ stage by $a_i^k$.

We will prove by induction that,
for all $k \in [1,\ \log{n}]$

$(1)\\ a_i^k = a_{i} + a_{i-1} + ... + a_{i-2^k+1}\ \ \forall{i= 2^k+1, ...n}$

$a_j^k = a_j + a_{j-1} + ... + a_1\ \ \forall{j=1, ...2^k}$

Base case:

When $k = 1$, by the algorithm,
$a_1^1 = a_1$, and specified by the algorithm,
$a_i^1 = a_i + a_{i-1} = a_i + a_{i-2^1+1},\ \forall{i = 3...n}$,
hence $(1)$ is true for $k = 1$.

Induction step:

Let $q \in [1,\ \log{n}]$ be given and suppose $(1)$ is true for $k = q$,

Then when $k = q+1$:
specified by the algorithm, $\forall{i=2^{q+1}+1, ...n}$,
$a_i^{q+1} = a_i^q + a_{i-2^{q}}^q$

Since it's true at the $q$ stage, i.e.
$a_i^q = a_i + a_{i-1} + ...+a_{i-2^q+1}$
$a_{i-2^{q}}^q = a_{i-2^{q}} + a_{i-2^{q}-1} + ... + a_1$

We can derive:
$a_i^{q+1} = a_i + a_{i-1} + ...+a_{i-2^q+1} + a_{i-2^{q}} + a_{i-2^{q}-1} + ... + a_1$

Thus, $(1)$ holds for $k = q+1$, and the proof of the induction step is completed.

# 2. Asymptotically Optimality

We can model the prefix sum problem by building up a binary tree in a certain bottom-up manner, where its root is the prefix sum of the $n_{th}$ leaf.

Let $l$ be the actual nodes in a binary tree. Suppose such binary tree's height is $h$, so it can at most have $2^h$ nodes.

Since we have $n$ leaves, the nodes of the binary tree are limited by:
$n \le l \le 2^h$

then derive,
$h \ge \log{n} = \Omega{(\log{n})}$

The aymptotical lower bound of the parallel prefix sum problem is $\Omega{(\log{n})}$, hence the algorithm is asymptotically optimal.

# 3. Work Optimality

The work is not optimal, as it doesn't have the same work as a sequential algorithm:

$w_p = pT_p = nT_p$ (we have $n$ processors)
$= O(n\log{n}) > O(n) = w_s$