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 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
extractMandscript. The Targa can be viewed in a program like the GIMP (v1.2 or more). There is also a
tga2pdfscript 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.
If 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?