Scott Duckworth

During the Summer of 2002 I did a lot of reading at home on computer networking and played with it just as much on my Linux computer. I started working with iptables/netfilter, the firewall for Linux 2.4/2.6, but realized that the command line interface to these tools was not very friendly. So, like every other geek would, I started making scripts to make my life easier. One thing led to another, and before I knew it, I had created a bash shell script approximately 800 lines long. This script read a configuration file, processed it, and ran the appropriate commands to do what the config. file said.

I had also recently discovered SourceForge.net, so I had to get in on it. I gave my program a name - Linux Network Solution Kit - and registered it with SourceForge. To this day, the project still remains active (people still download it) although I have all but abandoned it. I believe this project had a lot to do with me getting a co-op at Cisco Systems in 2003.

At this point in my college career at Clemson University I was enrolled in the computer engineering program and I had already taken all of the computer science classes that I was required to take. Unfortunately, all of those classes were taught in Java, and I wanted to get some experience in C, so I decided to take CPSC 215. Little did I know that I would change my major and get my first publication because of it!

This was Dr. Geist's first time teaching this class in a while and he was trying something new - problem-based learning - basically he gave us a huge semester-long project and we had to learn C to do it. I was excited about the project because I had done some graphics stuff in the past (mostly CAD). I caught on to C fairly quickly and started working on things we hadn't even gone over in class. I had a lot of fun working on the project and creating images with my new toy.

I made some really cool images - Dr. Geist thought so, and apparently the Association for Computing Machinery (ACM) thought so as well. About two years after I had taken this class, Dr. Geist contacted me and told me my images made it into the November 2004 issue of Computer Graphics, a publication of ACM SIGGRAPH.

Two of my images are also featured on the Clemson University Department of Computer Science web page (the snowman and the one with floating objects in front of a setting sun).

This was my first compiler experience, and I went through it with Dr. Stevenson. Anybody who has ever gone through this with Dr. Stevenson will tell you that it is far from simple. His approach to this class is to not explicitly teach you anything, only give a very loose guidance. In other words, lectures were often more confusing than helpful. Anyway, I got through it and ended up enjoying it enough to go on and take a graduate compiler course.

The assignment given to us was to create a compiler for the Itty-Bitty Teaching Language (IBTL), a toy language closely modeled after LISP. Our target language was gforth, a stack-based language originally designed for printers (PostScript and PDF both use forth under the hood). This enabled us to focus more on the major parts of the compiler rather than the intracacies of code generation for general purpose register machines. The implementation language was left up to the student's preference - I chose C++ since at the time I did not have much experience in the language and wanted to learn more about it.

While working on this project, I developed a strong love/hate relationship for all three languages - C++, gforth, and IBTL. I did eventually get everything working, but only after I pretty much re-wrote the compiler a few times. That's par for (this) course.

The second compiler course I took during my undergraduate studies was optional - I took it because I was crazy! Although classified as both an undergraduate and graduate-level course, it was predominantly graduate students who took it (20+ graduate students and 2 undergraduate students).

Once again, we had a semester-long project - to write a compiler for a toy language similar to Fortran targeting a general-purpose register machine architechure. The implementation language was left up to the students. I chose to target the SPARC architechure although I had never done SPARC assembly (only Intel 8086), mostly because I heard it was easier to generate SPARC assembly. I had a hard time deciding on the language I would implement the compiler. I was comfortable with C/C++ and I had done a compiler with C++ in CPSC 428, but during that class Dr. Stevenson was able to convince me that there are better languages to use to make a compiler. He always mentioned O'Caml in class, and after playing with it some over the summer, I decided to give it a shot.

Unfortunately, since there was so much that the professor had to cover during the semester, he made a lot of design decisions for us. All of the other students were using C, C++, Python, or Java - all imperative languages - so naturally he presented his designs in an imperative style. Normally this would be okay, but since O'Caml is so different from imperative languages it proved to be difficult at times. I was able to translate the designs into something that would work in a functional style. As it turns out, many of the designs I came up with were simpler than their imperative equivalents because of the nature of the problem.

I completed my compiler before many of the graduate students did, and to my knowledge my program was one of the shorter ones. The professor even commented that it was faster than he was expecting. Ever since this project, I have been a strong advocate of O'Caml for most any kind of programming, particularly programs that do language processing.

In order to get a minor in mathematical sciences I needed to take a 400-level MTHSC course, so after asking around I decided on Linear Programming. In this class, we looked at one thing: linear optimization problems. That is, given a set of linear constraints and a linear objective function, find the minimum or maximum value of the function and the corresponding values of all of the variables. This class ended up being a lot more fun than I originally thought, and it ended up being closely related to my planned area of research.

There are many computer programs available which solve these types of programs. We worked with one particular program called LINDO. LINDO did it's job well, but I noticed one caveat - it did not accept rational numbers as input, nor did it do any computations rationally. All values were stored in a floating point number which any experienced computer scientist knows are inprecise.

Having recently learned the algorithm to solve such problems I decided to write a program that implements the algorithm and does so using rational numbers from start to finish to avoid any loss of precision (at the expense of speed of course). I completed my undertaking in about a week. I wrote the program from scratch using O'Caml and the rational number library. I made a parser for the input language (very similar to the subset of the LINDO language we had used, only it supported rational numbers). Although I did not use any of the known computational optimizations (I hadn't learned about them yet), it still worked fairly quickly, although nowhere near the performance of any industrial application.

Our first project was to create a video card driver for the 3DLabs Permedia2V graphics card for Linux 2.6 (specifically 2.6.12.3). This was my first introduction to real kernel programming, as it was for most other students in the class. The professor walked us through the first few steps then loosely guided us in the right direction. The main sources of information were the hardware and programmers reference manuals, the Linux Device Drivers book (our textbook), and examples found in the kernel source tree.

Since this is a graphics driver, and performance is always key in graphics, we aimed to get as much performance out of the drivers as possible. This meant using the DMA capabilities of the PCI graphics card, which therefore meant we had to write interrupt handlers and deal with concurrency issues. We also used a circular queue of DMA buffers which were memory mapped to user-space and handed off to the device when they were full or needed to be flushed.

My partner and I successfully completed our driver and received the highest grade in the class on the project. This was a really fun project, but then again, what project isn't fun when you get to draw pictures?!

Our last project was to create a disk scheduler for Linux 2.6 (specifically 2.6.12.3). The scheduler was to implement algorithms T and TBD, both of which attempt to minimize the mean wait time for disk requests. Although the professor walked us through the typical call path of a read() system call, very little information was given to us about the nature of the disk schedulers. In order to complete this project we had to dig through the kernel source code to understand the inner workings of various kernel functions and find examples of what we needed to do.

My four teammates and I successfully completed our scheduler within a month, and we achieved our objective of having a lower mean wait time than all of the other disk schedulers provided in the kernel (noop, anticipatory, deadline, and cfq). The final product was as very stable - it never crashed during our rigorous testing and performance analysis.