From a9760b31a2dfc672c72c4257a4e293fafb08c0b3 Mon Sep 17 00:00:00 2001 From: JP Appel Date: Mon, 29 Apr 2024 22:34:51 -0400 Subject: presentation sans figures --- .gitignore | 3 + makefile | 2 +- presentation/diagram.png | Bin 0 -> 139495 bytes presentation/presentation.md | 156 +++++++++++++++++++++++++++++++++++++++---- 4 files changed, 148 insertions(+), 13 deletions(-) create mode 100644 presentation/diagram.png diff --git a/.gitignore b/.gitignore index f26ec01..c93d064 100644 --- a/.gitignore +++ b/.gitignore @@ -9,6 +9,9 @@ build/* *.html !analysis/analysis.html +# IDE stuff +.vscode + # Prerequisites *.d diff --git a/makefile b/makefile index 2ca7100..c90bf85 100644 --- a/makefile +++ b/makefile @@ -68,7 +68,7 @@ tests/mandelbrot: examples/mandelbrot_serial.grid examples/mandelbrot_shared.gri # Presentation # ################## -presentation: presentation/presentation.html +presentation: presentation/presentation.html analysis/analysis.html presentation/presentation.html: presentation/presentation.md pandoc -t revealjs -so $@ $< diff --git a/presentation/diagram.png b/presentation/diagram.png new file mode 100644 index 0000000..ab1e372 Binary files /dev/null and b/presentation/diagram.png differ diff --git a/presentation/presentation.md b/presentation/presentation.md index 788dc8c..b3297c3 100644 --- a/presentation/presentation.md +++ b/presentation/presentation.md @@ -1,36 +1,168 @@ --- -title: "HPC Mandelbrot, Julia, and Multibot Sets" +title: "HPC Complex Fractal Generation" author: - "JP Appel" - "David Marrero" --- -![Mandelbrot Set]() - # Prerequisite Knowledge ## Complex Numbers +$$i^2 = -1$$ +$$z = x + iy$$ + +::: notes + +* complex numbers are an extension of real numbers, stemming from the square root of $-1$ +* a complex number is just a pair of two real numbers (x,y) with different ways to add and multiply +* in computer science we model real numbers with a single float or double, so we will need 2 floats or doubles to model a complex number + +::: + +. . . + +### Addition + +$$z_1 + z_2 = (x_1 + x_2) + i (y_1 + y_2)$$ + +::: notes + +* addition behaves as you expect +* multiplication involves multiplying then distributing, and using the fact that $i^2 = -1$ +* so adding two complex numbers is 2 float additions +* and multiplying them is 4 multiplications and 2 additions + +::: + +### Multiplication + +$$z_1z_2 = (x_1x_2 - y_1y_2) + i(x_1y_2 + x_2y_1)$$ + ## What is the Mandelbrot Set +. . . + +$$z_n = z^2_{n-1} + z_0$$ + + +::: notes + + +* this sequence is used to generate the mandelbrot set +* if for some complex number $z_0$ the sequence remains bounded as it $n$ approaches infinity then $z_0$ lies within the mandelbrot set +* there are many recursive sequences related to this, where you modify that happens with the recursive term + +::: + ## Fractals -## Handling Recursion +::::: {.columns} -# Implementations +:::: {.column width=40%} +* infinite self-similar geometric shape +* have "fractional dimension" +:::: -## Serial +:::: {.column width=60%} +![Sripenski Triangle](https://upload.wikimedia.org/wikipedia/commons/thumb/4/45/Sierpinski_triangle.svg/1920px-Sierpinski_triangle.svg.png){ width=80% } +:::: +::::: -## Serial Animation +. . . -## Shared +The Mandelbrot set is a fractal in the complex plane -## Shared Animation +::: notes + +* fractals are a infinite self-similar geometric shape +* so if you zoom in on any one part it will look like the entire object +* the Sripenski triangle is an example of a fractal +* the mandelbrot set forms a fractal in the complex plane + +::: + +## Fractal in Nature + +![Romanesco Cauliflower](https://www.rocketgardens.co.uk/wp-content/uploads/2016/02/Cauliflower20Romanesco.jpg){ width=50%} + +::: notes + +* fractals often show up in nature -## GPU +::: -## GPU Animation + +## Escape Time Algorithm + +::: incremental + +* Inputs + * Maximum Number of iterations + * Upper bound +1. Create a grid of points to sample +2. For each point in the sample space + 1. Compute the next term in the sequence + 2. if greater than the upper bound return the number of iterations + 3. else repeat until the maximum number of iterations and return + +::: + +::: notes + +* to compute the complex sets we used an escape time algorithm +* in general it takes in a maximum number of iterations, an initial value, and an upper bound +* the escape time algorithm is as follows (read of the slides) +* note that each sampled point is completely independent of any other point + * this hints to us that the problem will parallelize well +* for most of the sets we looked at, there is a proven bound + * ie if the sequence is ever larger than a value we know it diverges +::: + +# Implementation + +## Program Structure + +![](diagram.png) + +::: notes + +* the translation units are roughly as pictured here +* black ellipses are for serial code, color is for parallel +* each version of the program fills in an array with the number of iterations it took the sequence to grow too large +* that array along with some extra data is a grid object, which can be serialized and deserialized +* the main fractals unit handles cli argument parsing for the sampling resolution, fractal type etc +* a separate renderer program handles creating images from the `.grid` file +* the `.grid` file format is really simple, it's a magic number, the grid dimensions, the maximum number of iterations, the lower left and upper right most points of the region, and then the data + +::: + +## Mandelbrot + +::: notes + +* when mandelbrot initially tried to have this printed, the printers kept removing the "dust" thinking it was an error in their printing process + +::: + +## Tricorn + +## Burning Ship + +## Multibrot + +## Multicorn + +## Julia + +## Serial Animation + +## Shared Animation + +## CUDA Animation # Analysis -## Speedups +## + +[Interactive Plots](../analysis/analysis.html) -- cgit v1.2.3