BRUCE MAGGS
Professor, Computer Science
www

My research area is networks for parallel and distributed computer systems. For the past few years my research has focused on how to build the communications system that underlies a parallel computer. My goal has been to develop mechanisms for moving data between processors (or between processors and memory) that are both practical and provably effective. To this end, I have designed, analyzed, and implemented algorithms for routing, sorting, and tolerating faults in parallel computers.

As an example of this type of work, Berthold Voecking and I have recently shown that an N-node AKS network can be embedded in a 3N/2-node degree-8 multibutterfly network with load 1, congestion 1, and dilation 2. The result has several implications, including the first deterministic algorithms for sorting n keys on an n-input multibutterfly in O(log n) time, and a three-dimensional VLSI layout for the n-input AKS network with volume O(n^(3/2)). These algorithms provide further evidence of the robustness of multibutterfly networks. We have also discovered a separate, and more practical, deterministic algorithm for routing h relations on an n-input multibutterfly in O(h+log n) time. Previously, only algorithms for solving h one-to-one routing problems were known.

Micah Adler and I have been studying asymmetric networks. An asymmetric network is one in which the link bandwidth or the link reliability between two points u and v differs according to the direction u - v or v - u. My interest in this subject was sparked by a hobby of mine. Over the past few years I have established a high-speed internet connection between campus and my home. The link is asymmetric because it uses 2 megabit/second wireless Ethernet in one direction and a 33.6 kilobit/sec telephone line in the other. (The reason for this asymmetry is that there is too much radio-frequency noise on campus for a signal to get through from off campus.) Despite the asymmetry, the link has proved capable of supporting a remote X terminal and a web browser, thus allowing me to work from home in a graphical environment comparable to that of the workstation in my office.

Micah and I have devised protocols for transmitting information across an asymmetric communication link in the ``wrong'' (or slow) direction. We assume that a client has an n-bit data item drawn from a distribution D to transmit to a server, and that the distribution is known to the server, but not to the client. This model is motivated by the scenario in which a server is collecting a single data sample from each of many clients. We have shown that using the asymmetric link in the fast direction, the server can guide the client through a transmission in which the client does nearly as well without knowing the distribution D as it could knowing D. In particular, we have devised a protocol in which the expected number of bits sent by the server is at most 3n, while the expected number of bits sent by the client is at most 1.71H(D), where H(D) is the entropy of the distribution D. Even knowing D, the client cannot expected to send fewer than H(D) bits. We have developed variations on this protocol in which the number of handshakes between the client and server is reduced, and also proved matching lower bounds and impossibility results concerning the total number of bits sent, the amount of computation performed by the server, and the number of handshakes.

My research now continues on a new front: parallel algorithms for scientific computing. Claudson Bornstein, Gary Miller, R. Ravi, and I have been studying the problem of solving linear systems using direct methods such as Gaussian elimination. We have focused on nested dissection. Viewing a system of equations as a graph, nested dissection can be summarized as follows. First find a set of ``separator'' vertices whose removal partitions the graph into two or more connected components. These vertices will be eliminated last. Order the individual components one after the other. (The separator prevents ``fill'' between the different components.) Within each component, order the vertices recursively.

We have analyzed the performance of a parallel variant of nested dissection that can be applied directly to interval graphs and chordal graphs. For general graphs, the algorithm can be used to parallelize the ordering produced by some other heuristic such as minimum degree. In this case, the algorithm is applied to the chordal completion that the heuristic generates from the input graph. The input to the algorithm is a chordal graph G with n nodes and m edges. The algorithm produces an ordering with height at most O(log 2 n) times optimal, fill at most O(m), and work at most O(W(G)), where W(G) is the minimum possible work over all elimination orderings for G. Experimental results show that when applied after some other heuristic, the increase in work and fill is usually small. In some instances the algorithm obtains an ordering that is actually better, in terms of work and fill, than the original one.

Claudson, Gary, and I have also analyzed a new sequential variant of nested dissection based on the following idea: once all but one of the components has been eliminated, the separator need not be eliminated last. We have developed a heuristic for determining when to eliminate the separator last, and when to merge it with the last component. In practice, our heuristic has been shown to outperform all of the publically available codes for nested dissection in terms of work and fill. The heuristic also has a theoretical motivation: unlike standard implementations of nested dissection, when applied to chordal graphs it produces a zero-fill elimination order.