Reducing Waiting Costs in User-Level Communication

Stefanos N. Damianakis, Yuqun Chen, and Edward W. Felten
Dept. of Computer Science, Princeton University

In this work we describe a mechanism for reducing the cost of waiting
for messages in architectures that allow user-level communication
libraries.  We reduce waiting costs in two ways: by reducing the cost
of servicing interrupts, and by carefully controlling when to use
interrupts and when to use polling.  We have implemented our mechanism
on the SHRIMP multicomputer and integrated it with our user-level
sockets library.

Many network interfaces can place incoming data directly in user
memory (for example, SHRIMP, Hamlyn, Myrinet).  This capability
enables the construction of very efficient network software since the
network interface can deliver a burst of packets without any software
intervention.  On such an architecture, communication can be handled
entirely in a user-level library.

The user-level library must either poll or be interrupted to find out
that new data has arrived.  This requires both a mechanism for
efficient blocking, and a policy for when to spin and when to block.
This paper considers the questions of which policy and which mechanism
to use.

In order to minimize the interrupt service time we keep the interrupt
path as simple as possible. Our mechanism does not execute a
user-level interrupt handler, since invoking such a handler requires
too much overhead. Further, we also require that there be a fast way
to enable and disable incoming data interrupts at page granularity.

We describe the tradeoffs between polling and blocking, drawing on
previous work on spinning vs. blocking tradeoffs in multiprocessor
locking.  There are three basic strategies, as well as several hybrid
strategies, each with adjustable parameters.  We discuss the tradeoffs
between the various strategies.  We present an implementation of these
strategies on the prototype SHRIMP multicomputer, and the results of
experiments comparing them, using our user-level sockets library, for
micro-benchmarks, larger benchmarks, and for a distributed file
system.