Over 158 papers published in conference proceedings and journals in 2002 were submitted by IBM Research authors worldwide for consideration as 2002 CS/EE/Math Best Papers. The following four were selected (in alphabetical order):
Cut-and-Paste Editing of Multiresolution Surfaces
Henning Biermann (NYU), Ioana Martin, Fausto Bernardini and Denis Zorin (NYU)
ACM SIGGRAPH
Paper Description
The paper describes a novel CAD modeling paradigm that allows designers to combine geometric surfaces with the same ease as one combines photographs using PhotoShop-like tools. For example, in the design of automobile parts, a designer can paste a logo obtained by 3D scanning onto a digitally-modeled surface, import features from a library of predefined shapes, or copy parts of a design from one project to another. These types of operations have not been available to the CAD modeling community until now, and this technology makes it not only possible, but also interactive. The underlying mesh representation used by this technique is the multiresolution subdivision surface, which provides a very compact representation for smooth surfaces and yet allows for highly efficient algorithms. Although subdivision surfaces have been used in these areas before, existing technology has made it difficult, if not impossible, to perform the design scenarios described.
This work has immediate impact for content creation in several industries including MCAD, Games, and Film. This new technology will be included as a module of Dassault Systemes' CAD package CATIA, which IBM markets as part of its Product Lifecycle Management product portfolio. CATIA is a market leader in the Automotive and Aerospace industries. With this technology, CATIA will be the first major CAD package to offer integrated car body styling tools. In addition to Dassault Systemes, many IBM PLM industrial partners as well as academic researchers have expressed interest in this work. It has recently become the starting point for several PhD projects at universities around the world.
Determinism versus Non-determinism for Linear-Time RAMs with Memory Restrictions
Miklos Ajtai
Journal of Computer and System Sciences
Paper Description
This paper solves a monumental problem in complexity theory that had been considered by many researchers over a 20 year period: how to show lower bounds for computing decision problems in completely general non-uniform models of computation. In particular, this paper shows that there are problems easily solvable in polynomial time but that require linear space to be solved using any linear time non-uniform algorithm. To give an indication about how much of a breakthrough this is, consider that it was not known previously how to show that more than O(log n) space was required by any linear time algorithm. It changes the landscape of what we can prove quite dramatically.
Ajtai won the 2003 Knuth Prize for what the Knuth Prize committee calls his "truly remarkable seminal contributions" to theoretical computer science, and this paper was one of the contributing factors.
Optimizing Pipelines for Power and Performance
Viji Srinivasan, David Brooks (now at Harvard), Michael Gschwind, Pradip Bose, Victor Zyuban, Philip Strenski, and Philip Emma
35th IEEE International Symposium on Microarchitecture (IEEE MICRO)
Paper Description
Previous theoretical work derived an "optimal" microprocessor pipeline depth based only on performance. This paper extends previous theory in two ways. (1) Power consumption is added to the model, as it is an increasingly important design factor -- the most important for some markets. In the new model, optimization can be done for any metric of power (raised to an exponent) vs performance. There is no single "right" exponent -- the value to use depends on a processor's market sector. (2) "Hardware intensity" (an input to modern synthesis tools) is used to measure the level of circuit tuning needed to achieve a given performance level. For a given hardware macro it is defined as the percentage power increase per percent performance increase. To speed up a machine, one can repipeline it to have more pipe stages, or one can increase hardware intensity via circuit tuning. The proposed model allows designers to achieve an optimal compromise between the two, subject to any specified power/performance metric. The model is validated by extensive detailed simulations, including detailed sensitivity analyses of the various parameters and assumptions.
The model is now being used by several teams in IBM to do design tradeoffs. This paper was rated the top paper by the conference program committee and a modified version has been submitted to IEEE Transactions on Computers.
The BLUE Active Queue Management Algorithms
Wu-Chang Feng (OGI School of Science and Engineering), Kang G. Shin (U. Michigan), Dilip D Kandlur and Debanjan Saha
IEEE/ACM Transactions on Networking
Paper Description
The paper proposes a novel way of managing congestion in the routers in the Internet. Active queue management schemes are used to manage the congestion, and stand for a class of schemes where packets can be dropped randomly even when there is sufficient buffer space at the router. The current standard active queue management scheme is RED, which drops packets randomly at a router if the length of the queues at router exceeds certain thresholds. RED is known to have several problems, including the inability of preventing higher loss rates. This paper proposes an alternative approach, called BLUE, which looks at packet loss data and link idle time to determine when packets ought to be preemptively dropped. The measurement and maintenance of state information at a router has been a traditional show-stopper for a practical deployment of the schemes like BLUE. The authors combine this approach with Bloom filters (a known approach that uses hashing to reduce state information), which reduces the state management task tremendously, and makes BLUE amenable to implementation in a practical system.
BLUE has been implemented and is available as standard feature in FreeBSD and OpenBSD shipments. It is implemented for Linux, and expected to be part of the standard shipment.This paper was awarded the IEEE Communication Society William R Bennet award for 2002, as being the best paper related to communications systems and theory in the year.