Paul Krzyzanowski at Bell Labs
I spent a bit over a dozen years at Bell Labs, most of it
in the research area in building 2 in Murray Hill, New Jersey.
This page is a brief summary of some of my work at the labs.
You can get a feel for some of my work through my
publications - don't get too excited!
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.
A few of larger or more interesting projects I've worked on while at Bell Labs are:
- 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 (RFS)
and then on writing the administrative commands for distributed
file systems for system V release 4 (share, /etc/dfs, and all that
crud is my fault). After that, I developed an
intelligent consultant for system administration (no - nothing as
demeaning as the Microsoft paper clip!). I also played with
regular expression parsers and mail systems.
- 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.
- 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. It was a fun
experiment and forced me to build all the software components:
the assembler, disassembler, optimizing compiler, X-windows simulator,
libraries, .... Research along these lines is still being done
ten years later. It also led me to further research...
- Exploiting program parallelism - dynamically at the object level
-
Writing parallel programs is difficult. Having a compiler find
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.
call
- 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.
- 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. The nice thing is that many office phones
are essentially simple terminals. The user interface parts
(display, buttons, ringing) can be dissociated from the
signalling information (ISDN). What I did was to have a computer
snoop on the signalling information as well as the user
interfaces and hook them up or alter them when necessary.
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".
- 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, you can select pages to be preloaded into your
cache so they'll be there when you need them -- great for Dilbert).
- 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.
- 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.
Paul Krzyzanowski, pxk@cs.rutgers.edu