From 6a18f738c8dd6e3fe9f21c27f70f7df201e54d24 Mon Sep 17 00:00:00 2001
From: Sam Anthony <sam@samanthony.xyz>
Date: Thu, 10 Oct 2024 17:58:30 -0400
Subject: move report to its own directory

---
 report.tex | 121 -------------------------------------------------------------
 1 file changed, 121 deletions(-)
 delete mode 100644 report.tex

(limited to 'report.tex')

diff --git a/report.tex b/report.tex
deleted file mode 100644
index a2d8409..0000000
--- a/report.tex
+++ /dev/null
@@ -1,121 +0,0 @@
-\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}
-- 
cgit v1.2.3