From 6a18f738c8dd6e3fe9f21c27f70f7df201e54d24 Mon Sep 17 00:00:00 2001 From: Sam Anthony Date: Thu, 10 Oct 2024 17:58:30 -0400 Subject: move report to its own directory --- k5.gv | 9 ---- k5_1.gv | 18 -------- k5_2.gv | 18 -------- k5_3.gv | 18 -------- k5_4.gv | 18 -------- k5_5.gv | 18 -------- k5_6.gv | 18 -------- k5_7.gv | 18 -------- report.tex | 121 ---------------------------------------------------- report/k5.gv | 9 ++++ report/k5_1.gv | 18 ++++++++ report/k5_2.gv | 18 ++++++++ report/k5_3.gv | 18 ++++++++ report/k5_4.gv | 18 ++++++++ report/k5_5.gv | 18 ++++++++ report/k5_6.gv | 18 ++++++++ report/k5_7.gv | 18 ++++++++ report/report.tex | 124 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 18 files changed, 259 insertions(+), 256 deletions(-) delete mode 100644 k5.gv delete mode 100644 k5_1.gv delete mode 100644 k5_2.gv delete mode 100644 k5_3.gv delete mode 100644 k5_4.gv delete mode 100644 k5_5.gv delete mode 100644 k5_6.gv delete mode 100644 k5_7.gv delete mode 100644 report.tex create mode 100644 report/k5.gv create mode 100644 report/k5_1.gv create mode 100644 report/k5_2.gv create mode 100644 report/k5_3.gv create mode 100644 report/k5_4.gv create mode 100644 report/k5_5.gv create mode 100644 report/k5_6.gv create mode 100644 report/k5_7.gv create mode 100644 report/report.tex diff --git a/k5.gv b/k5.gv deleted file mode 100644 index 4bc4122..0000000 --- a/k5.gv +++ /dev/null @@ -1,9 +0,0 @@ -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 deleted file mode 100644 index 9baa68c..0000000 --- a/k5_1.gv +++ /dev/null @@ -1,18 +0,0 @@ -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 deleted file mode 100644 index 41f8c73..0000000 --- a/k5_2.gv +++ /dev/null @@ -1,18 +0,0 @@ -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 deleted file mode 100644 index 38899c1..0000000 --- a/k5_3.gv +++ /dev/null @@ -1,18 +0,0 @@ -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 deleted file mode 100644 index 6c900a6..0000000 --- a/k5_4.gv +++ /dev/null @@ -1,18 +0,0 @@ -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 deleted file mode 100644 index 99dd63c..0000000 --- a/k5_5.gv +++ /dev/null @@ -1,18 +0,0 @@ -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 deleted file mode 100644 index 1a5dc6f..0000000 --- a/k5_6.gv +++ /dev/null @@ -1,18 +0,0 @@ -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 deleted file mode 100644 index 3b88e7c..0000000 --- a/k5_7.gv +++ /dev/null @@ -1,18 +0,0 @@ -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 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 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} diff --git a/report/k5.gv b/report/k5.gv new file mode 100644 index 0000000..4bc4122 --- /dev/null +++ b/report/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/report/k5_1.gv b/report/k5_1.gv new file mode 100644 index 0000000..9baa68c --- /dev/null +++ b/report/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/report/k5_2.gv b/report/k5_2.gv new file mode 100644 index 0000000..41f8c73 --- /dev/null +++ b/report/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/report/k5_3.gv b/report/k5_3.gv new file mode 100644 index 0000000..38899c1 --- /dev/null +++ b/report/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/report/k5_4.gv b/report/k5_4.gv new file mode 100644 index 0000000..6c900a6 --- /dev/null +++ b/report/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/report/k5_5.gv b/report/k5_5.gv new file mode 100644 index 0000000..99dd63c --- /dev/null +++ b/report/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/report/k5_6.gv b/report/k5_6.gv new file mode 100644 index 0000000..1a5dc6f --- /dev/null +++ b/report/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/report/k5_7.gv b/report/k5_7.gv new file mode 100644 index 0000000..3b88e7c --- /dev/null +++ b/report/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/report.tex b/report/report.tex new file mode 100644 index 0000000..2003af2 --- /dev/null +++ b/report/report.tex @@ -0,0 +1,124 @@ +\documentclass[11pt]{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; } +typedef [][]T Partition +\end{lstlisting} +\begin{lstlisting} +Partition +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 depences between iterations. + +\end{document} -- cgit v1.2.3