Content deleted Content added
→top: General fixes, removed orphan tag |
|||
Line 25:
==== Runtime analysis ====
The main loop is executed <math>\lceil\log_2 p\rceil</math> times, the time needed for the part done in parallel is in <math>\mathcal{O}(m)</math> as a processing unit either combines two vectors or becomes inactive. Thus the parallel time <math>T(p,m)</math> for the PRAM is <math>T(p,m) = \mathcal{O}(\log(p) \cdot m)</math>. The strategy for handling read and write conflicts can be chosen as restrictive as an exclusive read and exclusive write (EREW). The efficiency <math>S(p,m)</math> of the algorithm is <math>S(p,m) \in \mathcal{O}(\frac{T_{seq}}{T(p,m)}) = \mathcal{O}(\frac{p}{\log(p)})</math> and therefore the efficiency is <math>E(p,m) \in \mathcal{O}(\frac{S(p,m)}{p}) = \mathcal{O}(\frac{1}{\log(p)})</math>. The efficiency suffers because of the fact that half of the active processing units become inactive after each step, so <math>\frac{p}{2^i}</math> units are active in step <math>i</math>.
=== Distributed memory algorithm ===
| |||