NorthIs..⇡

Projects

Here are quick links to the projects I’ve completed and am still working on.

Graduate projects:
(I’ll write more on these when I have time, also I’ll post my sources)

Advanced Compliers

Writing the middle section of a compiler with the focus on code optimization. Over the semester I have been slowly adding features, first simple code generation, then simple control flow analysis, and finally redundancy elimination. Currently redundancies are only found on a local scope so I am adding global redundancy elimination now. This will be done using Dominator based Value Numbering. I have posted the source for my current version below, unfortunately there is a lot of environment setup required so it probably won’t compile for you.

Pervasive and Wireless computing
I have believed for a number of years now that the convergence device for computing is the cell phone. The phone is the perfect convergence device because everybody already has one, they carry it around with them, and they get a new one every two years. Now it may be a long while before phones actually replace conventional computers (if they ever do). But it will not be long before they will be able to do most of the things we want out of our home computers. The iPhone is an excellent example of a small device that is powerful enough to do such tasks. It can check my e-mail and browse the web (and I mean the real web, not the ‘mobile web’ which is severely crippled). The iPhone is, unfortunately, not a typical phone it is a super phone. A more typical phone is the RAZR from Motorolla. It is popular, small, and most importantly for this research has bluetooth capabilities. So for our project we will look at more commonplace phones. The only assumption we make is that the phone has bluetooth.

Specifically we are looking at how to use a centralized server and the internet to collect presence information from bluetooth enabled phones. When a computer detects a nearby bluetooth device it will send its id to the server, the server then record the location of the device and send the computer a variety of information.

Here are two examples of use:
1) Suppose I have a 9:00 meeting that has been changed to 8:30, and suppose its a large meeting (like a shareholders meeting) so it is not practical or possible to call everybody in attendance. The new time could be posted in vCal format to the server and as soon as I walk by a computer with bluetooth that computer would tell the server I just walked by and the server would respond with the vCal information. This could then be pushed to the phone using bluetooth’s OBEX protocol. My phone would beep and I would know the new meeting time.

2) Suppose a network of computers in an office, often it is useful to know about the network topology of the office, but what about the physical topology? If every computer comes equipped with bluetooth then we can use this system to have each computer detect its neighbors and we can make some assumptions about the physical topology.

After the framework is built there are many areas of interest:

What is the most efficient way to detect phones?

What about devices that aren’t mobile? ie. two desktops which continually report back to the server that they are next to each other, is this useful?

If computer A detects B but B does not detect A what does that mean?

How do you resolve conflicts when two computers can both detect the same phone?

Is this limited to only phones? clearly not! so what are other applications?

How do you ensure security? privacy? anonymity?

How do you handle devices with partial support for bluetooth?

We assume that phones are only receivers in this scheme, can a phone initiate contact?

What if we could put programs on the phones? Could we hook them into sensor networks?

If phones can push data to the server could this be used to track medical conditions? environmental conditions? safety conditions?

Advanced Operating Systems
-linux scheduler instrumentation and evaluation
In short, I instrumented the linux scheduler and benchmarked it on an SMP using 2, 4, and 8 processors against two benchmark suits. 1) a standard scheduler benchmark suite they normally use to stress test the linux kernel and 2) a suite designed to simulate “normal desktop behavior.” This included a download of a torrent, web browsing, and decoding an avi movie. While the kernel did a good job load balancing under the stress tests it did not do a very good job under the “normal desktop behavior.” Now, good job here is defined in terms of energy conservation. Where it kept a low load on some processors and a medium load on others it should have put no load on some and a higher load on others. This feature would pave the road for per-core power scaling which will be available in the next generation of processors (or sooner!).

Advanced Topics In Networking
-video teleconferencing QoS (Quality of Service)
We found this was very hard to achieve.

Real Life
My job consisted of programming a suite of applications in java for scientific computing. Using what I learned in my High Performance Computing class I improved the program’s runtime from minutes to instantaneous.

Undergraduate projects:

Operating Systems
In my OS class we did more than most universities; we wrote our own operating system almost entirely from scratch. We used the Geek OS project which was quite an experience, as it is in the early stages of development itself (and not quite ready for educational use). When we did this project Geek OS was not very well documented so we, as new OS hackers, had quite an adventure exploring how exactly to complete each of the five projects.

The first project was simply to get user processes running in the user memory space. This involved researching the ELF header format and Intel documentation in great depth to determine exactly how to load a binary from disk into memory. Once in memory an inefficient Round-Robin scheduler would schedule processes and threads.

In project two we had to create a scheduling algorithm that would do better than FIFO or Round-Robin. We ended up using a Multi-Level Feedback Queue with four tiers that worked quite well.
In project three we implemented virtual memory so a process could have up to 4GB memory outside of the ~64KB we were emulating.

For project four we implemented a virtual file system that could work with both FAT and the file system we created called GOSFS.

For our fifth and final project we used our semaphores and virtual memory to create a shared memory region between (up to 16) processes. This project was especially interesting as it accompanied my studies in High Performance Computing where we were looking at SMP systems and other shared memory systems.

This class, along with High Performance Computing, ignited my interest in systems, which is what I am now looking at grad schools for.

I have put my OS projects in the downloads section for the time being. It will be taken down when the school year begins as it contains the solutions for GeekOS projects. If you wish to see it (and I have taken it down) e-mail me and I’ll send it to you (if you are not a student).

Networking

For my networking class we were assigned to write an IMAP client. We were told exactly that and where the RFC document was, everything else was up to us. I decided to make mine in cocoa and wow, was that an experience.

Never before have I used such an intuitive language! From semaphores and threads to the date it had everything one could ever want in a programing language. The only disappointment was that there was no awesome cocoa style BSDSockets support (we ended up using the NSFilehandle class which made all the network communication transparent to us as programers anyways; awesome!).

In short, I now know cocoa fairly well and have fallen completely in love with it.

High Performance Computing
In HPC we studied many kinds of multi processor systems and the strengths/weakness of each one with projects accompanying each kind of system. We covered using homogeneous and heterogeneous MPI systems using computer labs at my school as a multi processor system as well as machines at the Ohio Supercomputer Center that use a shared memory architecture. We studied the difference in performance between using MPI on our own lab, our 16 node Gigabit Beowulf cluster, and the clusters at OSC.

Our projects included integration of a curve using MPI, solving the n-body problem on MPI and OpenMP, and implementing various parallel image processing on OpenMP.

For our final project my group chose to generate large prime numbers using MPI and OpenMP. We originally planned to use a lab of Macintoshes with dual 1.25 G4 processors so we could use OpenMP on each machine as well as the AltiVec instruction set on each machine, then use MPI between all the machines. Unfortunately the generation of prime numbers lends itself best to OpenMP on a shared memory system, so we ended up using the 32 processor SGI Altix at OSC.

I have put my HPC projects in the downloads section.

Databases
In my databases class we spent the first few weeks solely on database theory, then we started on simple database projects. Ultimately each of us had to make a creative database (of sufficient complexity) that could be deployed in an enterprise scale. Whether or not any of us made “enterprise strength” databases I don’t know, but some of them were really cool.

Mine was called “A Novel Idea” and was a system for students to get better prices when selling textbooks at the end of the year by selling the to other students instead of the book store. It included a web interface using cgi scripts.

I have put my Database project in the downloads section.

Computer System Architecture
This class focused on how a computer works at a hardware level. We studied the pipeline within a processor and how to exploit it in assembly code. Our semester long project was to implement the entire IEEE floating point library in RISC assembly on an IRIX 64 bit workstation.

I have put my IEEE floating point project in the downloads section.

Class Name	Attachment	Size
Architecture	IEEE Floating Point Library.tgz	33.51 KB
High Performance	high_performance.tgz	611.48 KB
Networking	iMap.tgz	313.52 KB
Operating Systems	project5.tgz	146.35 KB
	project4.tgz	293.81 KB
	project3.tgz	240.79 KB
	project2.tgz	220.08 KB
	project1.tgz	187.93 KB
	project0.tgz	72.41 KB
Advanced Compilers	compilers project	70 KB