\documentclass[11pt]{article}
\usepackage{graphicx}
\usepackage{listings}
\usepackage{xcolor}
\usepackage{IEEEtrantools}

\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 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 set 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.

Numerically, this partition is
\begin{IEEEeqnarray*}{rl}
	C = \{ & \{ \{0, 1\}, \{2, 3\} \}, \\
	& \{ \{0, 2\}, \{1, 3\} \}, \\
	& \{ \{0, 3\}, \{1, 2\} \}, \\
	& \{ \{0, 4\} \}, \\
	& \{ \{1, 4\} \}, \\
	& \{ \{2, 4\} \}, \\
	& \{ \{3, 4\} \} \}
\end{IEEEeqnarray*}

Although $n=5$ only has two concurrent tasks per cell at most, the degree of concurrency increases rapidly with larger values of $n$.
$K_n$ has $n(n-1) / 2$ edges, so the number of edges increases in $O(n^2)$.
The size of a matching $M$ is at most $|M| = |V|/2$ (a perfect matching).
So, e.g., for $n=10$ the degree of concurrency is 5.
For $n=20$ the degree of concurrency is 10, etc.

Pseudocode for partitioning the collisions:
\begin{lstlisting}
struct Collision { Ball b1, b2; }
typedef [][]T Partition<T>
\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, a call to \texttt{animate()} loops through the cells of the partition and uses \texttt{parallel\_for()} to call \texttt{collideBall()} with each pair of balls in the cell.

\texttt{parallel\_for()} was also used to parallelize some other trivial loops with no dependences between iterations.

\end{document}
