HP researchers among ACM's first Distinguished Members

By Jamie Beckett – Nov. 2006

Two HP researchers have been selected for a new Association for Computing Machinery (ACM) honor recognizing scientists whose contributions are "having lasting effects on the lives of citizens throughout the world."

The researchers, Hans Boehm and Rob Schreiber, are currently working in the area of highly parallel computing, but both have a long history of technical achievement in a range of disciplines.

Boehm is best known as the primary author of a widely used open source "garbage collector," a method of automated memory management in systems, and Schreiber is known for his leadership in the fields of high-performance computing languages, compilers, machine architecture, and algorithms. In addition, each has a strong record of contribution to the ACM.

The Distinguished Members award recognizes ACM members for their contributions to both the practical and theoretical aspects of computing and information technology. Boehm and Schreiber were among 49 selected for the new award recognizing the range of contributions computing professionals are making to everyday life.

The garbage collector

Boehm's garbage collector, also known as the Boehm-Demers-Weiser garbage collector, is a tool that allows developers to allocate memory that is no longer useful without explicitly de-allocating it. The collector automatically recycles memory when it determines that it can no longer be otherwise accessed.

The garbage collection library is used by a variety of systems either directly, or as a part of the language runtime system. It currently serves as the garbage collector for both GNU Java (gcj) and the Mono open source CLI implementation. In addition, it is used in the runtime systems for many research programming language implementations, including Bigloo Scheme, the Berkeley Titanium project, the Cyclone project, and others.

It also served as the basis of the commercial Great Circle garbage collector which, as a result of a chain of acquisitions, is now part of the Symantec Application Saver product.

Publications

Boehm has published numerous papers, many on garbage collection or concurrency, but also on topics such as exact real arithmetic, novel alternate character string implementations and undecidability of certain forms of type inference. One of his versions of the character string implementation (rope) is now distributed with the GNU Compiler Collection.

He has presented papers at many ACM Programming Language Design and Implementation (PLDI) and ACM Symposium on Principles of Programming Languages (POPL) events.

A 2005 paper won the PLDI 10-year retrospective Most Influential Paper Award. His 2005 PLDI paper reached the top downloaded papers list for the ACM digital library shortly after its publication, and provided much of the justification for his ongoing project to revise the C++ language standard to provide proper support for shared-memory concurrency.

ACM activities

Boehm has served (and continues to serve) on many program and conference steering committees. He has been general chair of the POPL, the International Symposium on Memory Management (ISMM), and Virtual Execution Environment (VEE) Symposia/Conferences. He was Program Chair for POPL 1994.

He was elected the ACM Special Interest Group on Programming Languages (SIGPLAN) Executive Committee in 1999, as its Chair in 2001, and to the SGB EC in 2003. He was instrumental in introducing SIGPLAN's electronic membership category, and thereby improving its non-conference finances when that became necessary.

He was recently given the 2006 SIGPLAN Distinguished Service Award.

Schreiber's contributions

Schreiber's work has spanned three decades, beginning in the late 1970s when, with famed numerical analyst and Caltech professor Herb Keller, he performed one of the first supercomputer simulations of fluid flow and wrote a groundbreaking paper in that field.

The efficient solution of systems of many equations and many unknowns is a core problem in computational science, arising in numerous settings from engineering to statistics to economics. Often these equations are “sparse,” meaning that most of the equations involve only a few of the unknowns.

In 1980, Schreiber discovered the elimination tree, a data structure that is central to the understanding of and the efficient implementation of solution methods for large sparse systems of equations. Because of their hierarchy of cache memory, modern computer architectures present significant challenges to the designers of high-performance software. Schreiber’s papers concerning cache-aware, block algorithms helped usher in efficient modern software (such as LAPACK, or Linear Algebra PACKage) for solving large systems of equations and finding the eigenvalues of matrices.

Schreiber is the author of the widely used NAS Conjugate Gradient Benchmark, which is used to evaluate the performance of highly parallel supercomputers. He was coauthor of a paper on the NAS Parallel Benchmarks that won the 1994 H. Julian Allen Award for the best paper at NASA Ames Research Center.

Work in high-performance computing

He contributed to work at NASA's Research Institute for Advanced Computer Science (RIACS) that led to efficient, highly parallel methods for large sparse systems of equations. In addition, he collaborated on work that explained the necessity of distributing both matrix dimensions to control the cost of data communication on highly parallel computers and that provided both an effective parallel load-balancing strategy and an out-of-core implementation for solving large sparse systems of equations.

Schreiber was also a leader in the development of the High Performance FORTRAN (HPF) language for parallel computing, and is a coauthor of the HPF Handbook.

With others, he developed an extensive and theoretically sound framework for the automatic mapping of array variables to distributed memory architectures, which preserves parallelism and reduces communication cost. In addition, he collaborated on the design and implementation of the sparse matrix extension of Matlab, which brought large-scale problems of computational engineering into the scope of what Matlab’s users can do with it.

Systems-on-chips technology

At HP Labs, Schreiber contributed to PICO (Program In, Chip Out) technology, which is designed to accelerate the design of systems-on-chips used for a wide range of electronic devices.

The PICO hardware synthesis system (now a product of Synfora, Inc.) starts from a high-language specification of function and builds an application-specific accelerator at the register-transfer level. Schreiber developed the parallelizing, optimizing source-to-source program transformation system that constitutes the front-end of the PICO system.

Schreiber has been widely published. Among these was a 1984 IEEE Transactions paper on efficient and numerically stable methods for solving the linear algebraic problems arising in beamforming, a signal processing technique, which is considered a key paper in that field. He has been granted 13 patents, with four others pending.

ACM contributions

Schreiber has long been active in ACM’s programs. He served as vice-chair of ACM's Special Interest Group on Numerical Mathematics (SIGNUM, now disbanded). He was the general chair of the 1977 Principles and Practice of Parallel Programming (PPoPP) Conference, and has served since then on its Steering Committee.

He has been a member of three Supercomputing Program Committees, and since 2005 he has been a member of the Supercomputing Steering Committee. In addition, he has served as Area Editor for scientific computing of the Journal of the ACM.