Mandelbrot Set on Nachos
During the summer of 2003, I took an operating systems course as part of my undergraduate degree requirements. The course was CS354 and was renowned for requiring hundreds of hours designing and coding OS internals. The course was based on three assignments to add functionality to a pedagogical OS named NachOS. The first assignment was to implement several system calls, including exec. The second assignment was to implement virtual memory. The third assignment was to implement a file system. These assignments were done in groups and I had a great partner.
No user space programs were provided with NachOS to test out the functionality of the OS. It was up to each group to implement whatever user space programs they wanted to in order to convince the marker that the OS implementation was correct. For the first assignment (system calls), we wrote a small shell that could exec processes. For the second assignment (virtual memory), we extended our shell to have simple job control and spawn a lot of processes, thereby utilizing the virtual memory system.
Towards the end of the course as we were finishing up the third assignment (the filesystem), we really wanted to grandstand the robustness of our implementation. We figured we had a pretty rock-solid filesystem and a perfect virtual memory implementation and wanted an example that would hit both of these hard. I was also taking a fractals course that semester, so I figured I would write a Mandelbrot generator. The NachOS disk was small (approximately 100K), so I made the program output 320x240 images with a 256 colour index (so only 1 byte was needed for each pixel). One drawback of NachOS is that it didn't support floating point calculations, so I ported Softfloat. Below is a copy of a little explanation page I put together to explain to the marker what we did. We ended up getting perfect on the third assignment and 98% in the course.
The following are various output photos generated by the stack-mandelbrot program submitted as part of Group 9's CS354 A3 for the University of Waterloo.
The stack-mandelbrot program is compiled using make stack-mandelbrot.noff. The program needs to be copied to the NachOS disk to be run (./nachos -cp stack-mandelbrot.noff mand). After this, the program can be run from shell (which also needs to be loaded to the NachOS disk) with the following synopsis:
mand xstart xend ystart yend num_iterations
extractMand script. The Targa can be viewed in a program like the GIMP (v1.2 or more). There is also a tga2pdf script that will make a PDF document containing the output.
The reason that stack-mandelbrot takes so long is that it is doing all of the calculations in floating point. Since NachOS does not natively support floating point, the Softfloat library was ported to run on NachOS. Although SoftFloat is an excellent floating point implementation, the fact that it is software based inhibits speed greatly. In addition to this, the fact that SoftFloat is running on a simulated machine (as opposed to directly on hardware) also contributes to the slowness of the program. Nevertheless, although slow, stack-mandelbrot does perform the correct operations.
Here are sample pictures generated by stack-mandelbrot. The command line arguments used to create a particular picture are shown immediately below that picture.
-2.1 0.6 -1.2 1.2 40
-1.1624430 -1.1622430 0.292268 0.292468 200
-0.80183548 -0.79852452 -0.16964161 -0.16715839 300
0.4530446 0.4567774 -0.4047898 -0.4019902 75
0.2346763 0.3227257 -0.029728525 0.036308525 150If you've come this far, you get a bonus piece of information. The reason we chose a green based colour index was because The Matrix Reloaded had come out earlier in the semester and we were slightly obsessed. How cool were we?