From 6e0903b459b339e404ad519467353ab0b526cfb5 Mon Sep 17 00:00:00 2001 From: Sam Anthony Date: Thu, 10 Oct 2024 17:41:27 -0400 Subject: report draft --- .gitignore | 3 ++ 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 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 10 files changed, 259 insertions(+) create mode 100644 k5.gv create mode 100644 k5_1.gv create mode 100644 k5_2.gv create mode 100644 k5_3.gv create mode 100644 k5_4.gv create mode 100644 k5_5.gv create mode 100644 k5_6.gv create mode 100644 k5_7.gv create mode 100644 report.tex 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 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