report draft

10 files changed, 259 insertions, 0 deletions

diff --git a/.gitignore b/.gitignore
index 1a94e9b..7615922 100644
--- a/.gitignore
+++ b/.gitignore
@@ -1,3 +1,6 @@
 *.o
 balls
 *.pdf
+*.png
+*.aux
+*.log
diff --git a/k5.gv b/k5.gv
new file mode 100644
index 0000000..4bc4122
--- /dev/null
+++ b/k5.gv
@@ -0,0 +1,9 @@
+graph "k5" {
+	layout=circo
+	node [ shape=circle ];
+
+	0 -- { 1, 2, 3, 4 }
+	1 -- { 2, 3, 4 }
+	2 -- { 3, 4 }
+	3 -- 4
+}
diff --git a/k5_1.gv b/k5_1.gv
new file mode 100644
index 0000000..9baa68c
--- /dev/null
+++ b/k5_1.gv
@@ -0,0 +1,18 @@
+graph "k5_1" {
+	layout=circo
+	node [ shape=circle ]
+
+	0 -- 1 [color=red]
+	0 -- 2
+	0 -- 3
+	0 -- 4
+
+	1 -- 2
+	1 -- 3
+	1 -- 4
+
+	2 -- 3 [color=red]
+	2 -- 4
+
+	3 -- 4
+}
diff --git a/k5_2.gv b/k5_2.gv
new file mode 100644
index 0000000..41f8c73
--- /dev/null
+++ b/k5_2.gv
@@ -0,0 +1,18 @@
+graph "k5_1" {
+	layout=circo
+	node [ shape=circle ]
+
+	0 -- 1
+	0 -- 2 [color=red]
+	0 -- 3
+	0 -- 4
+
+	1 -- 2
+	1 -- 3 [color=red]
+	1 -- 4
+
+	2 -- 3
+	2 -- 4
+
+	3 -- 4
+}
diff --git a/k5_3.gv b/k5_3.gv
new file mode 100644
index 0000000..38899c1
--- /dev/null
+++ b/k5_3.gv
@@ -0,0 +1,18 @@
+graph "k5_1" {
+	layout=circo
+	node [ shape=circle ]
+
+	0 -- 1
+	0 -- 2
+	0 -- 3 [color=red]
+	0 -- 4
+
+	1 -- 2 [color=red]
+	1 -- 3
+	1 -- 4
+
+	2 -- 3
+	2 -- 4
+
+	3 -- 4
+}
diff --git a/k5_4.gv b/k5_4.gv
new file mode 100644
index 0000000..6c900a6
--- /dev/null
+++ b/k5_4.gv
@@ -0,0 +1,18 @@
+graph "k5_1" {
+	layout=circo
+	node [ shape=circle ]
+
+	0 -- 1
+	0 -- 2
+	0 -- 3
+	0 -- 4 [color=red]
+
+	1 -- 2
+	1 -- 3
+	1 -- 4
+
+	2 -- 3
+	2 -- 4
+
+	3 -- 4
+}
diff --git a/k5_5.gv b/k5_5.gv
new file mode 100644
index 0000000..99dd63c
--- /dev/null
+++ b/k5_5.gv
@@ -0,0 +1,18 @@
+graph "k5_1" {
+	layout=circo
+	node [ shape=circle ]
+
+	0 -- 1
+	0 -- 2
+	0 -- 3
+	0 -- 4
+
+	1 -- 2
+	1 -- 3
+	1 -- 4 [color=red]
+
+	2 -- 3
+	2 -- 4
+
+	3 -- 4
+}
diff --git a/k5_6.gv b/k5_6.gv
new file mode 100644
index 0000000..1a5dc6f
--- /dev/null
+++ b/k5_6.gv
@@ -0,0 +1,18 @@
+graph "k5_1" {
+	layout=circo
+	node [ shape=circle ]
+
+	0 -- 1
+	0 -- 2
+	0 -- 3
+	0 -- 4
+
+	1 -- 2
+	1 -- 3
+	1 -- 4
+
+	2 -- 3
+	2 -- 4 [color=red]
+
+	3 -- 4
+}
diff --git a/k5_7.gv b/k5_7.gv
new file mode 100644
index 0000000..3b88e7c
--- /dev/null
+++ b/k5_7.gv
@@ -0,0 +1,18 @@
+graph "k5_1" {
+	layout=circo
+	node [ shape=circle ]
+
+	0 -- 1
+	0 -- 2
+	0 -- 3
+	0 -- 4
+
+	1 -- 2
+	1 -- 3
+	1 -- 4
+
+	2 -- 3
+	2 -- 4
+
+	3 -- 4 [color=red]
+}
diff --git a/report.tex b/report.tex
new file mode 100644
index 0000000..a2d8409
--- /dev/null
+++ b/report.tex
@@ -0,0 +1,121 @@
+\documentclass{article}
+\usepackage{graphicx}
+\usepackage{listings}
+\usepackage{xcolor}
+
+\definecolor{codegreen}{rgb}{0, 0.6, 0}
+\definecolor{codegray}{rgb}{0.5, 0.5, 0.5}
+\definecolor{backcolor}{rgb}{0.95, 0.95, 0.92}
+
+\lstdefinestyle{mystyle}{
+	backgroundcolor=\color{backcolor},
+%	commentstyle=\color{codegreen},
+%	keywordstyle=\color{magenta},
+%	basicstyle=\ttfamily,
+	tabsize=2,
+}
+\lstset{style=mystyle}
+\lstset{language=C}
+
+\title{2D Bouncing Balls Simulation with TBB\\
+\large COMP 426 Assignment 2}
+
+\author{Sam Anthony 40271987}
+
+\begin{document}
+
+\maketitle
+
+The program uses TBB to leverage data-level parallelism in the simulation.
+The brunt of the computational work is in simulating the collisions between balls.
+This was the main area of focus when parallelizing the program.
+
+Each frame, the program must test each pair of balls for a collision.
+If two balls are found to be colliding, their positions and velocities must react accordingly.
+The goal is to perform as many of these tests as possible in parallel.
+However, the outcome of one collision may affect the position and velocity of one or both of the colliding balls.
+Therefore, if two collision tests share at least one common ball, then they cannot happen concurrently.
+If they did, then they could both write the shared ball at once---a race condition.
+
+A potential solution is to lock each ball when it is being tested for collision, perhaps with a TBB concurrent container.
+While this would be effective, a more elegant solution is to partition the work such that there is no contention between tasks, obviating the need for an explicit lock.
+
+The lock-free solution works by partitioning the set of collision-tests so that no two collisions in a cell of the partition share any balls.
+Suppose there are $n$ balls labeled 0 through $n-1$.
+Let $B$ be the set of balls and $C$ be the set of all collision-tests.
+Each element of $C$ is a tuple of the form $(a, b)$ where $a,b \in B$.
+
+Each ball can be thought of as a vertex in a graph, and each collision-test as an edge in the graph.
+Let $G(B, C)$ be such a graph.
+Each ball must be tested against every other ball, so $G \equiv K_n$, the complete graph.
+
+The problem amounts to partitioning the edges of $K_n$ such that no two edges in a cell share an endpoint.
+A \emph{matching} is a set of edges without common vertices, so each cell of the partition is a matching on $K_n$.
+
+A concrete example will illustrate how this works.
+Consider the case of $n = 5$.
+$B = \{0, 1, 2, 3, 4\}$.
+Each ball has to be tested for collision with every other ball, so $C = \{(0, 1), (0, 2), (0, 3), (0, 4), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)\}$.
+This is what $G$ will look like:
+
+\includegraphics[width=0.25\textwidth]{"k5.png"}
+
+Here is one possible way to partition the graph:
+
+\includegraphics[width=0.25\textwidth]{"k5_1.png"}
+\includegraphics[width=0.25\textwidth]{"k5_2.png"}
+\includegraphics[width=0.25\textwidth]{"k5_3.png"}
+\includegraphics[width=0.25\textwidth]{"k5_4.png"}
+\includegraphics[width=0.25\textwidth]{"k5_5.png"}
+\includegraphics[width=0.25\textwidth]{"k5_6.png"}
+\includegraphics[width=0.25\textwidth]{"k5_7.png"}
+
+This partition has 7 cells.
+Red highlighting indicates that those edges are included in the cell.
+Note that no edges within a cell share an endpoint---they can be computed concurrently.
+
+Pseudocode for partitioning the collisions:
+\begin{lstlisting}
+struct Collision { Ball b1, b2; }
+\end{lstlisting}
+\begin{lstlisting}
+Partition<Collision> partitionCollisions([]Ball balls) {
+	G := complete graph on balls
+	P := empty partition
+
+	while !empty(G.edges) {
+		cell := matching(G.edges)
+		G.edges -= cell // remove edges in cell from graph
+		P.append(cell)
+	}
+
+	return P
+}
+\end{lstlisting}
+\begin{lstlisting}
+[]Edge matching([]Edge E) {
+	M := empty []Edge
+
+	for each Edge e in E {
+		for i in [0, len(M)) {
+			if hasCommonEndPoint(e, M[i]) {
+				break
+			}
+		}
+		if i >= len(M) { // no shared vertices
+			M.append(e)
+		}
+	}
+
+	return M
+}
+\end{lstlisting}
+
+The part of the program that constructs the partition can be found in \texttt{partition.cpp}.
+The program simply initializes the balls, and passes them to \texttt{partitionCollisions()} to construct the partition.
+Each frame it loops through the cells of the partition and uses \texttt{parallel\_for()} to call \texttt{collideBall()} with each pair of balls in the cell.
+This is performed by \texttt{animate()} in \texttt{balls.cpp}.
+
+\texttt{parallel\_for()} was also used to parallelize some other trivial loops with no depences between iterations.
+
+\end{document}