My work

Paul Krzyzanowski’s projects

You can take a look at a list of my patents & publications. Please contain your excitement!

My reasearch interests are in operating systems, mobile computing (including wireless networking, and computing in disconnected and loosely connected environments), computer system architecture, and playing with cool and/or cute hardware and software.

These are a few of the larger or more interesting projects that I've worked on. Most were during my time at Bell Labs research:

Kernel-less operating systems
Operating systems take on quite a lot of work. Even microkernel systems take on quite a bit of responsibility in providing rudimentary I/O access, process scheduling, and resource management. Can we make things even simpler? This project created a "kernel" whose entire role is merely switching execution between protected spaces. Basically, each "process" requests a certain amount of memory and gets a protected address space and an interrupt table. The mechanism for switching between these spaces is by invoking the appropriate interrupt. Some spaces may have the privileges to operate in kernel mode or to access certain devices. All that the kernel does is accept the traps and perform this extended context switch to a new protected domain. It was sad to see how long the interrupt latency on an intel Pentium-class CPU was, largely due to the fact that the processor doesn't support tagged TLBs in its MMU.
Wireless ATM networking
We built a small circuit board that contains a wireless modem, microprocessor, and a bunch of memory and is interfaced via a PCMCIA interface. This system formed the basis of a wireless ATM network. The interesting part was getting quality-of-service reservations to work well. In the wireless world, we were faced with a bandwidth considerably lower than one typically gets in the wired world and, worse yet, periods of disconnection. We designed drivers to handle service reservation requests and provide the ability to interrupt applications to tell them if reservations can no longer be met. This allows for quality of service control and for applications to be self-adjusting to changes in operating conditionss.
TeleWeb - Web surfing anytime, anywhere
We like to web surf, but are not always connected to the Internet. Sometimes we could connect but it would be over a slow and/or expensive connection (e.g. dial-up modem or an airplane phone). TeleWeb runs as a local proxy that can make you aware (if you choose) of what is cached and what isn't by rewriting web pages on the fly. If you are not connected or connected over a costly link, TeleWeb will intercept access to non-cached pages and ask you whether you really want to load the page or if you'd like to put it in a queue that will be processed when you're on a better connection. Each page also gives you a small bar of buttons that enables you to turn a few TeleWeb options on or off, and schedule timed events via a VCR-style timer (great for precaching pages over a slow connection).
Programming your telephone
Telephones used to be simple. Now they're not. All too often you'll hear someone say "I'll try to transfer you but here's the number in case it doesn't work". We also want conferencing and call screening and possibly custom features. Many office phones are essentially simple terminals. The user interface parts (display, buttons, ringing) can be dissociated from the signalling information (ISDN or SIP). What I did was separate the signalling and the user interface and have a computer snoop on both and control the UI. You can now set up a call screening file which tells the computer what the phone (and the computer) should do for particular incoming calls. You can also write little scripts to do things like "keep dialing this number until someone answers" or "conference in a new user". Click to dial becomes really simple and does what you want — it dials the phone.
Personal mobile terminal
This research was putting a new spin on an old idea - the dumb terminal. This time the terminal is a Walkman-size handheld device containing a large LCD display, a few buttons, a microphone and a speaker, and a barcode reader. It has a radio interface and communicates with a nearby host. The personal mobile terminal (PMT) sends messages such as "here's some voice data", "button 2 was pressed", or "here's a barcode scan". It receives messages containing audio and display directives. The server is entirely responsible for the PMT's functionality as perceived by its user. For example, a user may go into a record store and use the barcode scanner to scan CD barcodes to be presented with a menu of preview choices. The same PMT may be taken to a warehouse and used for inventory control. It may be taked to a supermarket, allowing the customer to scan products for information and use the on-screen display to get information on sales. The same device can also be used for guided tours. Simple yet amazingly powerful.
High-definition TV
My contribution to this project was mininscule, but when the computer systems research lab committed to building an HDTV prototype (to compete for the FCC HDTV standard) many of us had to help out. Having lost most of my hardware design skills, I worked on writing software for the perceptual coder and the motion estimator. This was later used to validate the custom HDTV hardware. Perceptual coding deals with the realization that you can compress an image only so far by squeezing out redundancy. After that, you have to introduce noise into the system. The question is where to put the noise so that it is least perceived by the human viewer? Our system was based on taking a DCT (discrete cosine transform) and applying perceptual weights to the resulting matrix. The second component of HDTV was motion estimation. This involved splitting the image into a number of rectangular chunks and comparing each chunk with a previous frame. If a match is found, then the image in the chunk need not be sent and we only need to send the ID and a vector telling the receiver where that chunk is currently located. Motion estimation itself was a two-step process, with an initial search for big chunks (coarse) and a second search for small image chuncks (fine).
Intelligent memory
In the computer systems research laboratory, I worked on exploring the concept of intelligent memory. The bandwidth between memory and the CPU has not been increasing as rapidly as the two components it connects. Cache memory is a great solution, but it does not solve the problem completely. Sometimes large linked lists or other structures without spatial locality must be traversed or several CPUs need access to the same synchronous memory. The SWIM (Structured Wafer-based Intelligent Memory) project was our attempt at building a smarter memory chip. Instead of having a memory chip sit idle or serve a word of memory at a time, we augmented it with a small processor, optimized for memory-intensive operations. Now operations such as list traversals, pattern searches, and even disk I/O can be done by the memory without wasting bandwidth on the bus.
Exploiting program parallelism - dynamically at the object level
Writing parallel programs is difficult. Having a compiler discover parallelism is also difficult. This experiment focussed on exploiting object level parallelism. Suppose you have an environment where each object can be loaded on a different processor (in this case, intelligent memory was used). Executing a method now becomes analogous to a remote procedure call. However, if there is no immediate need for the return value, the program can continue running. Each method can do the same kind of aggressive scheduling. We run into problems when a method starts using future results. To handle this, all method invocations go to a commit manager which ensures serializability. No method will commit unless it gets an OK from the commit manager. We ensure serializability and achieve optimal object-level parallelism.
Parallel computing
We built a machine named SMOKE, optimized for parallel numeric processing. I wrote a C compiler for this system as well as other tools to enable applications to be written for this. The architecture was a grid topology (4-way communication) with half the address space of each processor being global shared memory and the other half local to a processor.
Unix
I spent the first several years of my Bell Labs career working in the Unix System lab. My work focussed on the initial development of remote file sharing and on writing the administrative commands for distributed file systems for system V release 4 (share, /etc/dfs, and all that crud). After that, I developed an intelligent consultant for system administration (no - nothing as demeaning as the Microsoft paper clip!). I also played with high-speed regular expression parsers and rule-based email systems.