# Parallel prefix sum

committed 584f994

Analysis of final algorithm

# Files changed (2)

Add a comment to this file

# parallel prefix sum.pdf

Binary file modified.

# parallel prefix sum.tex

     \frametitle{Formal description}

     \begin{algorithm}[H]
-      \caption{Reduce operation}
+      \caption{Reduce operation \label{alg:reduce}}
       \begin{algorithmic}[1]

         \Require Array $x$ of length $n$
 \end{frame}


+\begin{frame}
+    \frametitle{Formal description}
+
+    \begin{algorithm}[H]
+      \caption{Down-sweep \label{alg:down-sweep}}
+      \begin{algorithmic}[1]
+
+        \Require Output of Algorithm \ref{alg:reduce} array $a$ of length $n$
+        \Ensure All-prefix-sums
+        \medskip
+        \State $a[n - 1] = 0$
+        \For{$\log_2 n - 1$ to $0$}
+            \For{$\forall i \le n - 1$ by $2^{d + 1}$ in parallel}
+                \State $t = a[i + 2^d - 1]$
+                \State $a[i + 2^d - 1] = a[i + 2^{d + 1} - 1]$
+                \State $a[i + 2^{d + 1} - 1] = t + a[i + 2^{d + 1} - 1]$
+            \EndFor
+        \EndFor
+      \end{algorithmic}
+    \end{algorithm}
+
+\end{frame}
+
+\begin{frame}
+    \frametitle{Work complexity}
+
+    \begin{theorem}
+        The Algorithm \ref{alg:down-sweep} performs:
+
+        \begin{align*}
+            \log n \cdot O(\dfrac{n}{\log n}) = O(n)
+        \end{align*}
+        operations.
+    \end{theorem}
+
+\end{frame}
+
 \end{document}
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.