Archive for November, 2008


Game-Changing Advances from Computing Research — Followup

November 30th, 2008

In a November 4 post, we asked your help in identifying game-changing advances from computing research conducted in the past 20 years.  We primed the pump with four examples:

  • The Internet and the World Wide Web as we know them today
  • Search technology – Where once we filed, today we search
  • Cluster computing
  • The transformation of science via computation

In this post, we summarize just a sample of your additions (we have grabbed text from your posted comments, without a lot of editing, so this will be loose – “it’s the thoughts that count”) and invite your further comments – cleaning up these additions, or providing others.  Please let us hear from you!

Secure communication – the foundation of e-commerce

All of e-commerce relies on the results of computing research:  the Internet, the World Wide Web, cluster computing, parallel relational database systems, cryptography and algorithms for secure credit card transactions.  Here, we focus on the latter.  Without secure communication – for example, the ability to conduct a credit card transaction with an online merchant – there would be no e-commerce.  The complex of events (both theoretical advances and deployment of practical, useful software) that allow a user to type a credit card number into a web browser and be reasonably assured of its safety is a game-changer, making secure communication and secure commerce a reality for (potentially) all users of the Internet.  Without these artifacts, we would have no, no eBay, no thriving online pornography industry,

Mobile computing and communication

Twenty years ago, computing was a desktop experience.  “Portable computers” were the size of a briefcase.  Communication was via 9600 baud telephone modem.  Contrast that to today:  2 pound laptops that fit in a mailing envelope, mobile phones with Web browsers that fit in a shirt pocket, and ubiquitous WiFi and 3G cellular at many millions of bits per second.   Clearly, mobile computing and communication – the untethered lifestyle – is a game-changer.

Expert systems become ubiquitous

Thousands of routine decisions daily are made by computer systems that have specialized knowledge of a problem area. In the past, rule changes at a central office – e.g., the IRS, or the headquarters for a corporation – were incorporated slowly into practice. With expert systems, the people making the decisions have the benefit of codified knowledge bases that reflect current policy and practices.

Research on expert systems began in the 1970’s with support from DARPA, the National Institutes of Heath, and NSF. Expert systems have subsequently become an essential part of the IT toolkit for every major company. Help desks, credit checking and equipment troubleshooting are examples of systems that have been replicated many times over and are routinely saving money for business and public institutions.

Expert systems technology is a game-changer.

Robotics in everyday life

Twenty years ago, robots appeared in artificial intelligence laboratories, automated assembly lines, and science fiction movies.  In recent years, iRobot Corporation has sold roughly 1,000,000 Roomba robotic home vacuum cleaners annually, and multiple robotic automobiles have completed the DARPA Grand Challenge and Urban Challenge, autonomously navigating a 150-mile desert course and a 60-mile urban course.  Robots have entered the mainstream of society, integrating a wide variety of Artificial Intelligence technologies such as computer vision, sensing, and planning.  This is a game-changer, and the best clearly is yet to come.

Digital media

Today, almost no one thinks of photography in any form other than digital.  The means by which we capture, edit, and share digital images are the result of multiple breakthroughs in computer science.

Similarly, digital compact disc audio – a breakthrough when it entered the mainstream only two dozen years ago – is going the way of the dinosaur, replaced by MP3 audio on personal devices such as iPods.

Our video entertainment is in digital form too – whether on a DVD, a personal video device, streaming media, or a video game.

Digital media is revolutionizing entertainment and the entertainment industry – a game-changer.

GPS, mapping, and navigation

GPS – the ability to pinpoint your position nearly anywhere on earth – is a marvel.  But even more amazing are the algorithms that provide navigation – available on the Web, and in $200 self-contained portable devices from Garmin, TomTom, and others.  GPS, mapping, and navigation are game-changers.

Collaborative filtering and recommender systems

Collaborative filtering and recommender systems dramatically altered how we think about computing applications by introducing the idea that the actions and preferences of other people could be a useful resource in computations intended to support someone else’s activities.  This is easily appreciated by a broad audience – anyone who has used’s “people who bought this also bought…” or other social features; a somewhat narrower audience will also appreciate that a major improvement in search engine performance occurred when they started taking into account link structures and then click behaviors.

There’s a clear  tie to computing research, both in work on algorithms for using data from other people, and in interfaces for collecting it and presenting predictions or recommendations.  The idea was first articulated in CACM and in the ACM CSCW and CHI conferences, and there are now thousands of papers about it.

A few additional ideas that were suggested

These need fleshing out or weeding out!  Our comments in [blue brackets]

  • Something related to applications of machine learning – the applications within computing (e.g., NLP, vision, graphics), to other sciences (with big data), to finance (credit card fraud, and dare I say Wall Street) abound [for sure – needs fleshing out]
  • Something related to advances in software engineering, and the application of logic to analyzing both hardware and software designs and artifacts [the application of logic might work; we still have a “software crisis,” though, and “there (still) is no silver bullet,” so need to be careful with claims]
  • Something related to scientific computing and large-scale computational science, simulations, etc. [we meant this to be covered by one of our original topics – “the transformation of science via computation”]
  • Virtualization [can someone say “1960s”?]
  • Network coding [would need to be painted larger]
  • Compressed sampling/sensing [would need to be painted larger]
  • Quantum computing [premature]
  • Elliptic curve crypto [covered crypto under secure communication]
  • Molecular computing [come see us in 10 years!]
  • Randomized algorithms [would need to be painted larger – colored with applications]
  • Theory of distributed computing: impossibility results, Byzantine generals [we meant to feature this under our “cluster computing” topic, which relies integrally on these algorithms; cluster computing is not a hardware breakthrough, it’s a distributed algorithms breakthrough!]
  • Wearable/ubiquitous/mobile computing [covered under mobile computing and communication, a new topic above]
  • Sensor networks [tell me more]
  • Human computation (Captchas, the ESP game, etc.) [maybe …]
  • Computational microeconomics: ad placement, automated mechanism design [sounds good – say more!]

Again, we invite your comments!  Let us hear from you!

Ed Lazowska and Peter Lee

Multi-core and Parallel Programming: Is the Sky Falling?

November 17th, 2008

In previous posts on this blog, Berkeley’s David Patterson, Intel’s Andrew Chien, and Microsoft’s Dan Reed presented their views on why research advances are needed to overcome the problems posed by multicore processors. In this piece — the fourth (and possibly final) entry in the series -– Marc Snir from UIUC argues that there are major challenges facing us but yet, the sky is not falling.

The CCC blog has published a couple of articles on the multi-core challenge, all emphasizing the difficulty of making parallel programming prevalent and, hence, the difficulty of leveraging multi-core systems in mass markets. The challenge is, indeed, significant and requires important investments in research and development; but, at UPCRC Illinois, we do not believe that the sky is falling.

Parallel programming, as currently practiced, is hard: Programs, especially shared memory programs, are prone to subtle, hard-to-find synchronization bugs and parallel performance is elusive. One can reach two possible conclusions from this situation: It is possible that parallel programming is inherently hard, in which case, indeed the sky is falling. An alternative view is that, intrinsically, parallel programming is not significantly harder than sequential programming; rather, it is hampered by the lack of adequate languages, tools and architectures.  In this alternative view, different practices, supported by the right infrastructure, can make parallel programming prevalent.

This alternative, optimistic view is based on many years of experience with parallel programming. While some concurrent code, e.g., OS code, is often hard to write and debug, there are many forms of parallelism that are relatively easy to master: Many parallel scientific codes are written by scientists with limited CS education; the time spent handling parallelism is a small fraction of the time spent developing a large parallel scientific code. Parallelism can be hidden behind an SQL interface and exploited by programmers with little difficulty. Many programmers develop GUI’s that are, in effect, parallel programs, using specialized frameworks. Parallelism can be exposed using scripted object systems such as Squeak Etoys in ways that enable young children to write parallel programs. These examples seem to indicate that it is not parallelism per se that is hard to handle; rather it is the unstructured, unconstrained interaction between concurrent threads that result in code that is hard to understand both from a correctness and performance view, hence hard to debug and tune.

The state-of-the-art in parallel programming is what sequential computing was several decades ago. A major reason for this situation is that parallel programming has been an art exercised by a group of experts whose small population did not justify major investments in programming environments aimed at making their life easier. This reason disappears as parallelism becomes available on all platforms. Furthermore, we can make faster progress now because we understand well the principles it takes to make programming easier — principles such as safety, encapsulation, modularity, or separation of concerns; we also have more experience in developing sophisticated IDE’s.

What will it take to bring these principles of computer science to parallel programming? It will require a broad based attack across the system stack. As has been said in these blogs, we need research in languages, compilers, runtime, libraries, tools, hardware … What has not been said explicitly is that none of these areas are likely to produce the silver bullet on their own. The solution that will work eventually will be one that brings together technologies from all these areas to bear on each other. However, we do not have the luxury of doing this via incremental and reactive changes over decades. The research truly needs to be interdisciplinary and the idea of co-design needs to be internalized. Unfortunately, the mainstream systems community has all but abandoned this mode of research in the last several years. Language researchers are locked into mechanisms that will only be supported by commodity hardware and hardware researchers are locked into a mode that requires supporting the lowest common denominator software. It is imperative that we break out of these shells and get the research community into a mindset that we are truly looking to define a new age of computing — a mindset that nurtures research where a clean system slate is an acceptable starting point.

The sky is not falling, but the ground is shifting rapidly. The multi-core challenge requires a concerted effort of academia and industry to generate new capabilities. We are confident that in the future, as in the past, new capabilities will breed new applications. Multi-core parallelism can be leveraged to develop human-centered consumer products that provide more intelligent and more intuitive interfaces through better graphics and vision, better speech and text processing and better modeling of the user and the environment.

The task of providing better performance is shifting from the hardware to the software. This is an exciting time for Computer Science.

Marc Snir
4323 Siebel Center, 201 N Goodwin, IL 61801
Tel (217) 244 6568

Computer Science Outside The Box

November 12th, 2008

One of the great things about computing research is that, despite our incredible track record of game-changing advances, we’re always looking for ways to make the field even more vibrant.  In this vein, on Monday I attended “Computer Science Outside The Box,” a workshop of 44 leaders from academia and industry (mostly department heads) convened by NSF CISE, CCC, and CRA.

The workshop vastly exceeded my expectations – 8 hours of brainstorming about strategies and best practices, in four areas:

·     “Go Outside Your Box” – what strategies can we adopt to increase collaboration across subfields and with other fields?

·     “The World Needs Us” – how to contribute to the solution of societal “Grand Challenge” problems while simultaneously driving computing research forward.

·     “Breaking the Cycle” – can we change the reward structure to decrease incrementalism, encouraging long-range thinking?

·     “Serving the Community” – how can we further increase the culture of service to the research community and to the nation?

I’m sure others will blog on various aspects, and teams have formed to write up specific strategies and best practices.  But here are a few things that really struck me:

Computer science:  the ever-expanding sphere

A model of how our field evolves can help us make smart decisions.  Think of computer science as an ever-expanding sphere (this analogy is due to Alfred Spector; all graphics are due to Peter Lee).  We transform other fields and we change the world.  We do this not just through the application of computation, but through the introduction of computational thinking.  When we transform these fields, we make new discoveries about our own field that enlarge our “bag of tricks” – our ability to transform other fields.  So we constantly reinvent ourselves by reinventing others.

We’ve transformed circuit design, publishing, photography, communication, mechanical CAD, certain fields of science, …  We’re in the process of transforming biology, transportation, …  And we’re always transforming ourselves.  Computer science truly is an endless frontier.

What this means is that even when working inside the sphere, we’ve got to be looking outward.  And at the edges of the sphere, we’ve got to be embracing others, because that’s how we reinvent ourselves.

Computer science lives in Pasteur’s Quadrant

The vast majority of work in our field is motivated both by concerns of use and by a desire to evolve principles of enduring value.  If anything, we may be too much in Pasteur’s Quadrant – we may place too little value on research without obvious utility, and we may be too reluctant to reject as “not computer science” work that’s focused on applications where it may not be obvious that our own field will be advanced.  (Jim Gray had the stature and courage to pioneer our move into data-intensive eScience – today, the transformations this has stimulated “within the sphere” are obvious.)

Lots of the action is at the interfaces

This is true fractally – it’s true of the interfaces between computer science and other fields (the edges of the sphere), and it’s true of the interfaces between subfields of computer science.

We’ve got to produce students who are comfortable at these interfaces.  It’s increasingly difficult.  Stuart Russell observed that “Bohr drives Pasteur” – we need strength at the core, and the core is ever-expanding.  At the same time, students need to be able to make connections.  I’m concerned we’re making the wrong tradeoffs these days.  Students enter graduate school with records that look like promotion cases a decade ago!  We decrease course requirements to get students engaged in our own research as quickly as possible.  Our colloquia are half-empty because everyone’s too busy beavering away to attend.  These factors decrease breadth and agility within the sphere.  We don’t require minors, which would expose students to other fields – this decreases the ability to work at the edge of the sphere.  As a field, we should tackle these issues head-on.

Visions, incremental progress, and random walks

A research project needs to be hard enough to be interesting, and easy enough to be doable.   There needs to be a vision – a sense of where you and your colleagues are headed over a five-year or ten-year period.  And it needs to be tackled in what Alfred Spector calls “factorizable pieces.”

If there’s a vision, then a “factorizable piece” may appear incremental, but it’s headed somewhere important.  Without a vision, it’s part of a random walk.  It’s important to differentiate these!  A goal of the CCC “visioning workshop” process is to articulate some of these visions for our field.

Bob Sproull pointed us to a wonderful paper by Ivan Sutherland on the conduct of research – “Technology and Courage.”  Read it!


I’m sure others will blog on various aspects of the workshop.  Look in the mirror – is there a field you’d rather be part of?

Ed Lazowska

Game-Changing Advances from Computing Research

November 4th, 2008

We’d like your help with a brainstorming exercise: Identify about a dozen game-changing advances from computing research conducted in the past 20 years. Here’s what we mean:

  • The advance needs to be “game changing,” in the sense of dramatically altering how we think about computing and its applications.
  • The importance of the advance needs to be obvious and easily appreciated by a wide audience.
  • There needs to be a clear tie to computing research (or to infrastructure initiatives that build upon research and were sponsored by computing research organizations).
  • We’re particularly interested in highlighting the impact of federally-funded university-based research.

We’re focusing on work carried out in the past 20 years or so, in part because of the upcoming 20-year celebrations for the CISE directorate at NSF. Of course, lots of great fundamental research can take more than 20 years before the impact becomes obvious, but even in such cases there is usually continuing influences on more recent research that can be cited here.

To get your juices flowing, here are four game-changers that we definitely think belong on the list. Use these to think about others that belong on the list, or feel free to argue with our choices.

The Internet and the World Wide Web as we know them today

In 1988 — 20 years ago — ARPANET became NSFNET. At the time, there were only about 50,000 hosts spread across only about 150 networks. In 1989, CNRI connected MCImail to the Internet — the first “commercial use.” In 1992, NCSA Mosaic triggered the explosive growth of the World Wide Web. In 1995, full commercialization of the Internet was achieved, with roughly 6,000,000 hosts spread across roughly 50,000 networks. Today, there are more than half a billion Internet hosts, and an estimated 1.5 billion Internet users.

While many of the underlying technologies (digital packet switching, ARPANET, TCP/IP) predate the 20-year window, the transition from the relatively closed ARPANET to the totally open Internet and World Wide Web as we know them today falls squarely within that window. NSF-supported contributions included CSnet, NSFNET, and NCSA Mosaic.

The Internet and the World Wide Web are game-changers.

Where once we filed, today we search

The vast majority of the world’s information is available online today, and we find what we need — whether across the continent or on our own personal computer — by searching, rather than by organizing the information for later retrieval.

Research on the retrieval of unstructured information is based on decades of fundamental research in both computer science theory and AI. But the paradigm shift that is web crawling and indexing and desktop search is much more recent. It traces its roots to university projects such as WebCrawler, MetaCrawler, Lycos, Excite, Inktomi, and the NSF Digital Libraries Initiative research which begat Google.

Search is a game-changer.

Cluster computing

At the risk of offending our many computer architect friends, we’re going to assert that cluster computing is the most significant advance in computer architecture in the past 20 years.

A decade ago, Jeff Bezos was featured in magazine advertisements for the DEC AlphaServer, because that’s what ran on — the biggest shared-memory multiprocessor that could be built. Similarly, the AltaVista search engine was designed to showcase the capabilities of big SMP’s with 64-bit addressing.

Today, this seems laughable. Companies such as Google and replicate and partition applications across clusters of tens of thousands of cheap commodity single-board computers, using a variety of software techniques to achieve reliability, availability, and scalability.

The notion of hardware “bricks” probably can be traced to Inktomi, a byproduct of the Berkeley Networks of Workstations project. The software techniques are drawn from several decades of research on distributed algorithms.

Cluster computing is a game-changer.

The transformation of science via computation

The traditional three legs of the scientific stool are theory, experimentation, and observation. In the past 20 years, computer simulation has joined these as a fundamental approach to science, driven largely by the NSF Supercomputer Centers and PACI programs. Entire branches of physics, chemistry, astronomy, and other fields have been transformed.

Today, a second transformation is underway — a transformation to data-centered eScience, which requires semi-automated discovery in enormous volumes of data using techniques such as data mining and machine learning, much of which is based on years of basic research in statistics, optimization theory, and algorithms.

Computational science is a game-changer.

Some non-inclusions

Quantum computing. There is huge potential here, but the impact hasn’t been felt yet.

Simultaneous multithreading. We claim that this, and many other important advances in computer architecture, are dominated by cluster computing. (Remember, we’re trying to be provocative here! Blame Dave Ditzel, who put this idea into Ed’s head.)

Your part goes here!

What’s your reaction to the four game-changers that we’ve identified? Do you agree that they belong on the list? If not, why not? If so, what do you think were the principal components of each — the key contributing research results?

Even more importantly, give us eight more! What are your nominees for game-changing advances from computing research conducted in the past 20 years?

Give us your thoughts!

Ed Lazowska and Peter Lee