After realizing implementing the PDP11 was infeasible for the time constraints of this project, we had a long conversation with Hunter and Bruce about how to approach the remaining 2.5 weeks. We were both interested in optimization and getting the most performance out of an FPGA and decided that building off of our lab 3 Mandelbrot set visualizer would be the perfect starting point. This would allow us to dive deep into optimization without having to worry about creating a baseline implementation within our reduced timeline. At the end of Lab 3, we were able to render the full Mandelbrot set, with top-left corner coordinates of (-2, -1) and bottom right corner coordinates of (1,1) in 203 milliseconds using 16 parallel solvers writing through a round-robin arbiter to shared memory. There are certainly optimizations that can lower the computation time and better utilize the FPGA resources.
For the sake of completeness, an explanation of the Mandelbrot set will be discussed here. The Mandelbrot set is a complex set which is infinitely rough, yet generated from a set of simple rules. These two rules are iteratively run until either some threshold condition is met or a maximum number of iterations are met. The number of iterations determines the color of that point. The specific equations used for computing the next iteration for the real and imaginary axes are:
Figure 1: The calculations used to find the real and imaginary parts of a point in the Mandelbrot Set (taken from the course website). Here, CR and Ci are the real and imaginary parts of a complex number which corresponds to our location in the set.
If the sum of squares of ZiN+1 and ZRN+1 exceeds 4, then the point is considered to have diverged. If not, then more iterations are calculated. Since this algorithm operates on coordinates independently of one another, it is highly suited towards parallelization on the DE1-SoC. The main constraints that the platform provides are that there are only 87 DSP blocks capable of performing 27x27 bit multiplications for our 4.23 fixed point data type. Since there are not enough resources to entirely parallelize the 307200 pixels on the VGA monitor, solver engines can be made which calculate the number of iterations before the conditions of the Mandelbrot equation diverge, bounded by an upper limit of 1000 for a set of pixels. Each solver is given an equal proportion of the pixels displayed on the screen based on a predetermined pattern, and we assume that the workload is distributed evenly among the solvers. Each solver is assigned an ID, and solves all of the pixels in every IDth vertical column.
On the HPS side, usability functionally was expanded upon to enhance zooming such that each zoom action was 99% of the previous frame, as opposed to 50%. An animation functionality was also added that would automatically manipulate PIO ports to simulate precise user input that zoomed into a specified point. The split between FPGA and HPS in this project is done to take advantage of the capabilities of each platform. The FPGA is ideal for high-performance computation and communicating with the VGA system, while the HPS is better suited for user input and more general processing. The combination of the two allows for an intuitive, high performance result.