VLSI CAD Research Group
Department of Computer Science
School of Engineering and Applied Science
University of Virginia
We address real-life practical problems from industry, while at the same time we strive to develop solutions of substantial theoretical significance. For example, in the early 1990s we predicted the increasing significance of performance-driven interconnect synthesis. This area indeed became very critical in recent years as semiconductor feature sizes continued to shrink, since faster transistor switching speeds and larger chip dimensions imply that interconnects now dominate logic gates as the determinants of circuit delay and overall system performance. Our early work in this area helped usher in a new-generation of tools for "ultra-deep submicron" design that address exactly these issues.
Our code distributions have been regularly requested by numerous research groups around the world, and have formed the basis of implementations in both academic and commercial settings. For example, the ISI Grapher tool that I developed for the pictorial display of graphs was marketed commercially by ExperTelligence, Inc., and enjoyed a large user base worldwide. The manual accompanying this commercial tool was based on one of my papers, and an 18-page chapter was devoted to describing this software tool in the book "Multicomputer Vision" (Academic Press, 204 pages). Additional examples of the impact of our research and codes are detailed below.
Our papers and results are now cited in every textbook in our area. For example, the basic VLSI CAD textbook "An Introduction to VLSI Physical Design" (McGraw Hill, 334 pages) devotes six pages to describing our bounded-radius bounded-cost routing methodology, and uses several additional pages to explain our Iterated 1-Steiner, clock routing, and Elmore-based methods. The textbook "Algorithms for VLSI Design Automation" (John Wiley & Sons, 326 pages) spends six pages on discussing our Iterated 1-Steiner routing algorithm, including our fast spanning-tree update technique; this textbook also discusses our algorithms for timing-driven routing, and refers to our original journal publication on this topic as "a key paper". The VLSI CAD textbook "Algorithms for VLSI Physical Design Automation" (Kluwer Academic Publishers, 538 pages) by Naveed Sherwani of Intel devotes three pages to discussing our matching-based techniques for clock routing. The textbook "VLSI Physical Design Automation" (IEEE Press, 426 pages) discusses our Iterated 1-Steiner algorithm, as well as our bounded-radius bounded-cost approach. The recent book "On Chip Inductance in High Speed Integrated Circuits" (Kluwer Academic Publishers, 303 pages) cites several of our papers on Elmore-based algorithms for high-performance routing. Our pattern-detection algorithms are described over the span of three pages in the recent textbook "Algorithms Sequential & Parallel" (Prentice Hall, 330 pages).
We developed new best-known provably-good results for most of the NP-complete (i.e., computationally intractable) problems listed above. For example, we showed that, surprisingly, previous published rectilinear Steiner tree heuristics perform quite poorly on certain pathological examples, despite published claims to the contrary. On the positive side, we have proposed the best-performing rectilinear Steiner tree heuristics to date. Our 1-Steiner -based algorithms produce solutions with average cost around 11% better than minimum spanning trees, and less than 0.25% away from optimal; moreover our algorithms actually find optimal solutions for about 90% of typical inputs. The definitive book on this topic, namely "The Steiner Tree Problem" (North Holland, 339 pages) authored researchers at Lucent / Bell Labs, George Mason University, and the University of Copenhagen, devotes two pages to discussing our techniques, and this book refers to the performance of our Steiner tree algorithms as "the best for any heuristic discussed so far." Our Iterated 1-Steiner technique is also described over several pages in the book "Steiner Minimal Trees" authored by Professor Dietmar Cieslik from Ernst-Moritz-Arndt University in Germany. Our Steiner tree codes and routing algorithms were incorporated into commercial tools such as the popular Timberwolf CAD system, marketed by InternetCAD.com and Timberwolf Systems Inc. Our Steiner tree codes were also used by groups at UC San Diego, UC Santa Cruz, University of Illinois, Cadence Design Systems, LSI Logic Corporation, and Emergent Information Technologies, Inc., among others.
For the more general (and even more difficult) group Steiner problem in graphs, where the objective is to interconnect groups of nodes (rather than individual nodes), we developed algorithms with new, best-known bounds. Whereas the best previous algorithm had a solution performance ratio of k times the optimal, where k is the number of groups, we proved that solutions produced by our new polynomial-time heuristics never cost more than k^e times the optimal in the worst case, for any user-fixed arbitrarily small e>0. This was a considerable improvement over the state-of-the-art and solved a long-standing open problem. We also proved an impossibility result, showing that it is not feasible to approximate the group Steiner problem in polynomial time to within less than a logarithmic factor. Aside from its theoretical significance, this algorithm found practical applications in industrial settings, e.g., in the routing of nets with multi-terminal ports (where each pin may contain multiple electically-equivalent terminals), and in placement (where modules may be rotated or flipped).
Our research on the Steiner problem has led us to discover other interesting results, such as bounds on the maximum degree of minimum spanning trees in arbitrary dimensions and under several metrics, resolving several long-standing open problems. For example, we have invented a perturbation-based proof technique to show that every pointset in the Manhattan plane has a minimum spanning tree with maximum degree of at most 4, and that every pointset in three-dimensional Manhattan space has a minimum spanning tree with maximum degree of at most 14 (the best previously known upper bounds were 6 and 26, respectively). We also showed how to compute such trees in polynomial time (previously to our work, this was assumed to be an intractable problem). Our perturbation-based proof techniques and minimum spanning tree bounds were the basis for follow-up research at e.g., Georgia Institute of Technology and Simplex Solutions, Inc. Our theorems and proofs regarding low-degree minimum spanning trees are now also described in books such as "Steiner Minimal Trees" (Kluwer Academic Publishers, 319 pages).
We addressed the problem of bounded-skew clock routing, which arises in performance-driven applications. We pioneered a recursive geometric matching-based approach, and applied it to both cell-based and building-block designs. Our methods achieve near-zero clock skew while maintaining reasonable total wirelength. Numerous research groups, both in academia and in industry (e.g., UCLA, UC San Diego, Cadence Design Systems), have since used our bottom-up recursive matching techniques as the basis of their research or implementations. The book "Clock Distribution Networks in VLSI Circuits and Systems" (IEEE Press, 525 pages) devotes 13 pages to reprinting our seminal paper on clock routing.
We proposed the first general formulation of performance-driven global routing for both general cell and block-based designs. Our algorithm smoothly trades off wirelength for tree radius based on a user-controlled parameter, and has a constant-factor worst-case performance ratio with respect to both tree cost and tree radius, simultaneously. This was the first such result in the CAD literature, and this work has opened the door for subsequent works in this area (e.g., the AHHK bounded-radius algorithm of Alpert et al.). Retrospectively, cost/radius tradeoffs were shown to reflect the evolution of an important parameter of the underlying VLSI process technology, namely the "resistance ratio" governing driver on-resistance and per-unit interconnect resistance. It is now an accepted precept that a routing construction must flexibly allow engineering tradeoffs of sink delay and routing cost (wiring area), and our work in this area has formed the basis of Ph.D. dissertations elsewhere (e.g., the Ph.D. thesis of Dr. Charles Chiang at Northwestern University).
One area of research strives to unify some of the above constructions in solving a minimum-density routing tree formulation; here, the objective is to reduce crosstalk in circuits by minimizing the maximum amount of routing resources used in any region of the layout. Our novel proof techniques yielded provably-good bounds as well as enabled an efficient algorithm that produces routings with average density within a constant factor of optimal. This work has also led to a general multi-objective minimization formulation.
We developed a new methodology for constructing Elmore-based high-performance interconnection topologies that accommodate sink priorities derived from static timing analysis. This approach successfully sidesteps delay modeling inaccuracies inherent in previous methods, and instead builds low delay trees by directly optimizing the relevant criterion (e.g., the Elmore delay formula). This methodology also extends to critical sink formulations, as well as other delay models. Extensive testing has shown that this new delay optimization scheme significantly outperforms all previous strategies, yielding up to 70% average reduction in delay for typical nets, depending on the technology parameters. We have also proved a decomposition theorem for optimal Elmore-based constructions, the first result of its kind in the CAD literature. We also generalized Hanan's classical Steiner tree characterization to Elmore delay-optimal trees. Our algorithms and codes have been benchmarked extensively by other researchers (e.g., a CAD group at the University of Illinois states in one of their papers that our high-performance routing algorithm "has produced some of the best delay figures reported in the literature.") This line of research has proved to be crucial in today's deep-submicron design methodologies. Indeed, our underlying ideas such as using a more accurate delay function like Elmore's formula, as well as exploiting its convexity in driving the routing process, have since been used by a number of other groups in industry (e.g., at the IBM Austin Research Laboratory, InternetCAD.com, and the LSI Logic Corporation), as well as in academia (e.g., UC San Diego, University of Washington, Professor Sachin Sapatnekar's group at the University of Minnesota, and the research group of Professor Ernest Kuh, former EECS Chair and former Dean of Engineering at UC Berkeley).
An implicit premise of previous routing methods is that the routing topology must correspond to a tree (i.e., it does not contain cycles). We investigated the consequences of abandoning this basic axiom and instead allowing routing topologies to correspond to arbitrary graphs (i.e., where cycles are allowed). We have shown that adding extra wires to an existing routing tree can often significantly improve signal propagation delay and skew, by exploiting a tradeoff between circuit capacitance and resistance. We developed a new routing algorithm based on this phenomenon, and explored the synergy inherent in combining this with other optimizations, such as wiresizing. Whereas previous wiresizing methods are static in that they wiresize a given fixed topology, we have used wiresizing considerations to drive the routing construction process itself. This enabled routings with improved delay as well as skew. Our non-tree routing methodology has been used at e.g., Berkeley and at the Hewlett-Packard Corporation, among others.
We have developed the first general architecture-independent framework for field-programmable gate array (FPGA) routing, where multiple competing objectives can be optimized simultaneously under a smooth designer-controlled tradeoff. Our approach is the first to unify the global and detailed routing phases in FPGA's, and significantly outperformed all previous routers on standard industry benchmarks. This method is based on a general multi-weighted graph formulation which we invented, a framework that proved to be of independent theoretical interest (e.g., researchers at Cadence Design Systems have built upon our ideas regarding multi-weighted graphs). Our multi-weighted graph methodology also has applications in many other combinatorial optimization problems, such as traveling salesman, graph matching, partitioning, and vehicle routing problems.
In the area of circuit testing, we investigated new problems that arise in multi-chip module packaging technology. We formulated the problem of multi-chip module substrate testing as a metric traveling salesman scheduling of an optimal set of tree "probes", and proposed an efficient provably-good heuristic. Our algorithm produces (in optimal time) the optimal number of probes necessary to completely test an MCM substrate. We also proved that in terms of scheduling these test probes, our solution to this NP-complete (i.e., computationally intractable) problem never exceeds the theoretically best possible by more than 50%. This methodology was adopted by the Alcoa Corporation in their manufacturing process.
We investigated new approaches to reduce VLSI manufacturing variation and improve performance predictability and yield, by making layouts uniform with respect to certain density criteria that arise during chemical-mechanical polishing (CMP). We developed several techniques for density analyses and control, including linear-programming, multi-level, and hierarchical based approaches. This line of research yielded the first realistic formulations of the layout filling problems that arise in optimization for manufacturability, and provided a new unification between manufacturing and physical design. Whereas previously only foundries and special mask data processing tools performed layout post-processing for density control, we enabled a convergence where performance verification flows can rely on such layout manipulations being embedded within the layout synthesis (place-and-route) flow. Our results in this area have been used by leading companies such as MicroUnity Systems Engineering, Inc. and Cadence Design Systems, as well as by startup companies (notably CMP Technology, Inc.). Actual production flows at Motorola Inc. have used our density control algorithms, and our approaches have formed the foundation for follow-up academic research in this area at UCLA and by Professor Martin Wong's lab at UT Austin.
On the multidisciplinary front, we have found that much of our expertise and techniques from VLSI CAD transfer to problem-solving in other, seemingly unrelated fields. Such excursions into other areas offer very fertile opportunities for "technology transfer"; for example, we have successfully explored such diverse research areas as landmine detection, motion planning, minimal surfaces, and computational biology, as described below.
We have proposed a simple optimal algorithm for determining all maximal equally-spaced collinear subsets of a pointset. Our algorithm generalizes to finding two-dimensional spatial regularities, as well as to inexact cases where a specified location drift can be accommodated in the patterns, as may be the case in real scenarios. There are many practical pattern-detection applications to this work, including finding rows of landmines in infrared images, and these results have drawn considerable interest from, e.g., the U.S. Army, which used our code for landmine detection at its Fort Belvoir research labs. Our pattern-detection algorithms have also served as the basis for several parallel implementations at the SUNY Buffalo's Center for Computational Research.
We have investigated robust motion planning, where we seek a minimum-cost path for a mobile agent subject to a minimum-width constraint. We used a network flow based transformation of this problem to obtain the first known polynomial-time algorithm for robust motion planning. We extended our motion planning formulation into a related result of independent interest: the first optimal algorithm for the discrete Plateau problem of minimum surfaces; our solution was published in the Proceedings of the National Academy of Sciences, and has attracted considerable attention from the national media (news articles about this work appeared in the Los Angeles Times, the Washington Post, the Boston Globe, and the San Diego Union-Tribune).
We also addressed important problems in computational biology, such as the construction of evolutionary trees over a given set of taxa (e.g., organisms, DNA molecules, etc.), where the optimization objective entails the best-fit of tree topologies under some criteria (e.g., least-squares). Another problem in computational biology that we investigated is the primer selection problem, which arises in polymerase chain reaction (PCR) experiments (i.e., DNA cloning). Here, given a set of DNA strands and a cost criterion, we seek to find a minimal covering set of compatible DNA subsequences (primers) with least cost. We have shown that this problem is NP-complete, and proposed several heuristics with provable near-optimal performance. Our algorithm has been used by biochemists to try to discover new proteins.
Additional problems we have researched include a new practical time-dependent variant of the classical Traveling Salesman Problem, called Moving-Target TSP. Here the objective is to span, using a tour, a given set of targets which move with constant velocities in arbitrary directions. In addition to pioneering this new formulation which directly generalizes TSP, we proved several interesting theorems regarding moving-target TSP tours, and we developed algorithms with the best-known performance bounds in terms of solution quality for this computationally difficult problem.
We have compiled some of our research in VLSI CAD into a book published by Kluwer Academic Publishers. Articles about our research have appeared in a number of national and international newspapers. The impact of our work has been substantial, in that it triggered or influenced many other research projects elsewhere in academia and in industry. Our work is described in textbooks, and is regularly cited by papers at major conferences and journals (e.g., the bibliographic search engine "Cite Seer" ranks me in the top one percent of all cited authors in that database).
My research efforts have been recognized with honors such as an invitation to become a member of the Defense Science Study Group in 1993, a National Science Foundation Young Investigator Award ($312K) in 1994, and a Packard Foundation Fellowship ($550K) in 1995, the latter being the first one at the University of Virginia, and still the only Packard Fellowship ever awarded to any researcher in my area. In 1996 I served as General Chair of the ACM/SIGDA Physical Design Workshop, and in 1997 I co-founded the ACM/SIGDA/IEEE International Symposium on Physical Design (ISPD), which has quickly evolved into the leading conference in the field of physical design. In 1997 I was awarded the Walter N. Munster Endowed Chair at UVa, and in 1998 I was invited to join the Army Science Board, the highest-level scientific advisory board to the U.S. Army. In 1999 I was asked by the U.S. National Academy of Engineering to co-organize the German-American Frontiers of Engineering Symposium, where top young engineers and scientists from the U.S. and Germany met in order to foster research collaborations. In 2000 I was asked to serve as Associate Editor of IEEE Transactions on Very Large Integration Systems, a flagship journal in our area. Over the years I was invited to serve as a member on a number of scientific boards and panels organized by the National Academy of Sciences (e.g., the 1997 Navy Future Study).
I plan to continue to pursue research that is both theoretically significant and practically relevant. I truly enjoy solving difficult problems and contributing to the state-of-the-art of scientific and engineering knowledge. I also derive genuine satisfaction from teaching, mentoring, and from seeing my students mature and succeed with respect to their own professional goals. In summary, I love research and academia, and I have no doubt whatsoever that this is indeed my life's calling.
Good teaching is essential to molding top-notch future scientists and engineers out of young, impressionable minds. Teaching should therefore not take a back-seat to research, especially at the undergraduate level. I strongly believe that teaching and research are not independent endeavors, but rather are synergetic processes: my experience has shown that teaching can lead to good research topics, and conversely, research often provides new ways of explaining and teaching. Moreover, in my view teachers are much more than information sources: they also serve as mentors and role models to their students. Indeed, a good teacher can have a tremendous long-term impact on a student's life. I therefore resolved very early in my career to try to excel not only as a researcher, but also as a teacher, as an educator, and as a role model.
The quality of undergraduate education at the University of Virginia is superb. I truly enjoy teaching our talented undergraduates, and I always try to challenge them with interesting problems. Aside from the traditional classroom-centered teaching setting, I have found that an excellent, albeit less traditional way to teach students about a field is to expose them to current research in that area. I therefore also actively involve bright undergraduates in research; for example, seven of my co-authors on refereed research papers over the years were undergraduates, and I am currently working with additional undergraduates. This not only enhances the students' undergraduate educational experience, but also better prepares them for a more productive graduate school or industry career. One of the undergraduates that I advised won the Louis T. Rader Award (given yearly to two UVa undergraduates for research excellence) and gave a presentation at the historical UVa Rotunda. Most of the undergraduates that I supervised went on to do Ph.D. work at top universities (e.g., UC Berkeley, UIUC, CMU, and Duke). Occasionally one of my former students returns to visit me and mentions how helpful their training with me was in their career and in their life in general: hearing these success stories always brings tremendous joy to my heart!
Another non-traditional teaching mechanism that I use to teach students practical skills is the Web Team, which I founded at UVa when the Web was born in 1994. The Web Team is a group of highly motivated undergraduates which help numerous faculty, departments, and offices around the University with all Web-related projects, including creating and maintaining Web sites, designing and implementing databases, programming and scripting, automating office work flow, operating digital cameras and video equipment, giving Web-based presentations and demos, designing and producing brochures, posters and newsletters, etc. In short, the Web Team is a highly effective, all-purpose group that is ready and eager to help any faculty or administrator with technical issues. Examples of Web sites created from scratch by the Web Team are those of the School of Engineering, the Office of the Vice Provost for Research, the Virginia Engineering Foundation, the Gateway Project, the Renaissance School, the Packard Foundation, among many other offices and organizations. Another major project undertaken by the Web Team is the creation of the CS department brochure, a comprehensive full-color publication which was mailed to thousands of faculty, deans, provosts, and companies around the world. This brochure has garnered much praise from universities around the world, and has helped enhance the image and reputation of our own Department and School.
The Web Team has proved to be a tremendously useful and effective teaching tool. The undergraduates that rotated through the Web Team have learned not only useful technical skills such as programming, scripting, writing, typesetting, Web site creation, image manipulation, networking principles, and system administration, but they also acquired very valuable "life skills" with respect to issues such as organization, prioritization, time management, public relations, user support, quality control, proofreading, presentation, responsibility, meeting deadlines, and team work. Students who spent time on the Web Team have been rapidly hired by technology companies at consistently high salaries. Thus, the Web Team provides a wonderful vehicle for students to learn very important skills in a "real life" setting, as well as offers an indispensable resource to faculty and administrators around our University, a true win-win situation. Former Web Team members often contact or visit me, and corroborate the above observations. For example, one former Web Team member, Daryoush Mansouri, who now works at a New York company called Grey Interactive, has sent me an unsolicited Email last April saying "it's amazing how much of what I do today I learned while working with the webteam... It's certainly paid off." I consider such feedback an excellent metric of teaching success.
Regarding the more traditional teaching mechanism, namely the classroom, over the years I have developed and taught numerous courses (both undergraduate and graduate) on topics such as VLSI CAD, algorithms, discrete mathematics, computational geometry, and theoretical computer science. I have also developed a seminar where students practiced the art of performing effective research, identifying important problems, and solving them successfully. Since 1993 I have organized and conducted a yearly "orientation" seminar (CS696) for all our incoming computer science graduate students, which rapidly brings our incoming students up to speed with respect to graduate school life, our computing infrastructure, and most importantly, instills in the students the motivation to quickly get involved in active research. I strongly believe that in addition to the traditional job of transmitting information to students, my responsibilities as an educator include enhancing the students' drive and motivation, encouraging them to excel, showing them how to become more productive, and helping them reach their full potential.
My teaching reviews have been consistently high, and my teaching efforts over the years have been recognized with several honors, including a Distinguished Teaching Award, an All-University Outstanding Teaching Award, and a University Teaching Fellowship. However, despite these successes, I feel that I will always have much left to learn about the art of teaching. I therefore regularly poll my students for feedback using mid-semester teaching evaluations. I also became heavily involved in the activities of the University of Virginia's Teaching Resource Center (TRC). I have regularly participated in teaching workshops and seminars given by world-renown educators, and I also actively encourage my colleagues to attend these meetings (e.g., announcement packets from the Teaching Resource Center regarding University Teaching Fellowships include a cover letter from me explaining the tremendous benefits of these programs; in fact, I was so impressed with the Teaching Resource Center that I took it upon myself to augment their meager budget with a significant amount of my own funds in order to help support their activities). I welcome such opportunities to meet with colleagues from other disciplines who share a genuine interest in teaching excellence. Such exciting interactions have broadened my horizons and afforded me many new and fresh perspectives on the art of teaching. In summary, I view excellence in teaching as a continually evolving process of constant improvement, rather than a fixed goal. I will continue to actively improve my effectiveness as an educator, and to encourage others to do the same. It is my hope that my efforts to improve the quality of education will one day have a substantial impact not only at UVa, but also at the national level as well.
For example, when the Web was born in 1994 I immediately realized that it would have a tremendous global impact on the world. I therefore created in that same year the CS Web Team, a group of top-notch motivated undergraduates that assisted all faculty and administrators with any Web-related tasks. Due to the creation of the Web Team, our department soon became the first at UVa to have a Web site, and our School of Engineering became one of the first in the country that could boast a Web presence. (Note: that a department or a school has a Web site is of course tautological these days, but back in 1994 when the Web was in its infancy, having a Web site was quite rare and novel). When funding for this enterprise was not always available, I often funded these activities out of my own grants (and indeed sometimes I financed Web Team operations out of my own pocket). However, I viewed this as an excellent investment in the future of our Department and our University, and indeed I was not disappointed: the Web Team has acted as an early catalyst to usher the rest of the University into the Information Age, and our collective efforts along these lines have been widely recognized. For example, in 2000 Yahoo!'s Internet Life magazine ranked the University of Virginia as number eight in the country in their annual rankings of "America's Most Wired Colleges". And due to our early web presence head-start, our Department's Web server now receives over one hundred thousand "hits" per day (i.e., more than a hit per second around the clock).
Another major service project which I personally spearheaded was the creation of our Department's brochure, a full-color glossy 64-page professional-looking publication which describes in detail our research activities, faculty backgrounds, funding track record, and our departmental environment and atmosphere. I then personally oversaw the mass-mailing of our brochure to every computer science faculty member in the country, as well as to all engineering deans, and to selected provosts and companies. We also targeted many foreign universities in addition to domestic institutions. Over five thousand copies of our brochure were mailed in all (in a time-staggered manner over a six-month period, in order to maximize the PR impact). This massive PR blitz has proved highly effective: aside from receiving kudos from many of our colleagues around the world (indeed some departments have even adopted our brochure format and style in their own brochures), a number of our incoming graduate students have named our brochure when asked what attracted them to apply to our department. In addition, the new brochure has been instrumental in our faculty recruiting efforts. In retrospect, the brochure's great success was well worth the (hundreds of hours of my) time that I invested in this project. Indeed, some other departments and universities have modeled their own brochures after ours in terms of style, format, and scope.
One service activity that I am particularly fond of is our Department's poster drive. After I received my Packard Fellowship in 1995, one of the first things I did was purchase a large-format (i.e., 3-foot wide continuous paper roll) full-color postscript poster printer. Shortly thereafter, I created a set of five large (3'x4') posters that describe in detail our Department's research projects, our faculty, and our accomplishments on various fronts. These posters still hang in our Department's hallways, and have received very positive comments from visitors, parents, and faculty candidates (a copy of this set of posters was displayed at Thornton Hall, and a third set of these posters was created in a portable format that can be displayed at conferences on easels). Next, I created research-related posters, first for my own research projects (in order to provide examples to others), and then for other research projects. Other faculty have quickly followed suit, and today our Department's hallways are full of large colorful posters that beautifully present our research to visitors. Indeed, other departments around the School (e.g., EE and MSE) who have seen our posters have followed suit and started to create their own hallway posters (in the same style and format as ours, and often using our poster printer for production - we are always very glad to assist). We have also placed copies of these posters on the Web and we received a number of inquiries about our posters from other universities.
Another project that I am proud of is our computer museum. I first got the idea for this museum when I noticed that some of the more senior faculty members had in their possession historic computer artifacts, taken from long-obsolete machines (e.g., the Burroughs B205, the Burroughs 5000, the IBM 704, the CDC6600, etc.). Such artifacts always fascinate computing practitioners, as they very vividly illustrate the rate of progress of our field (e.g., a four-bit accumulator from the Burroughs B205 is the size of a lunchbox!). However, having these artifacts sit on individual faculty office shelves was wasteful, since that severely limited public access to them. I therefore commissioned the construction and installation of several large hallway display cases, created appropriate captions, and today those historical computer artifacts are available for everyone to enjoy. A web version of our computer museum draws many hits each day from around the world. Indeed we often receive unsolicited offers for artifact donations into our museum from people around the world who have seen our computer museum on the Web and would like to contribute to our collection.
One final example of what I consider high-impact service is the Computer Science Department Lounge, which I created a few years ago, after noticing that our Department lacked a "social hub". I commandeered a spare room, and furnished it with comfortable furniture, plants, soft lighting, coffee and tea makers, a large commercial-style sliding-door refrigerator, microwave and toaster ovens, and other conveniences. The CS Lounge features a continuous service of gourmet coffees, flavored teas, and various snacks, available to all visitors, and the refrigerator is always well-stocked with a large variety of soft drinks and juices (see www.cs.virginia.edu/lounge). I also stocked the lounge with dozens of challenging games and mind-stimulating puzzles, as well as a wall display showcasing recently-published research papers co-authored by our students, in order to encourage our students to publish more papers. The CS Lounge has quickly become an established (and self-sustaining) departmental fixture and a social hub where people congregate over coffee and snacks for lively research discussions or a friendly board game. Indeed, visitors from other departments and universities often praise the CS Lounge, and some of them have created a similar enterprise in their our department or institution.
Each of the service projects discussed above was unusual in some ways, either because it was unprecedented, or because it did not fit the normal funding mechanisms (indeed I sometime had to resort to funding some of these service projects myself, a leadership role that I welcome when the outcome so obviously benefits such a large number of people). None of the projects listed above were dictated by any existing policy or convention; rather, I had to muster the leadership to identify a basic need, invent or define a solution mechanism from scratch, and then follow through and nurture the plan to a successful conclusion, despite any potential obstacles. I really do enjoy this process! With each of the service projects such as the ones detailed above, my goals were to improve our Department's culture and collegiality, to make our Department and our School even more conducive to research, and to improve our overall visibility and external image. I believe that we have achieved considerable success towards these goals, and I plan on continuing to perform such service in the years to come.