原创 CS gets with parallel program

Computer science is approaching a crisis that some CS experts say could fuel a renaissance of ideas.

Very soon, mainstream computers will need an easy-to-use parallel programming model to tap into performance gains from next-generation multicore processors. But that will require one or more breakthroughs, because top researchers worked unsuccessfully for more than a decade to develop such a model for high-end supercomputers.

In a sign that the issue is now on the radar screen of mainstream computing, Intel and Microsoft last week officially announced their plan to spend a total of $20 million over five years to fund work at new parallel computing labs at the University of California at Berkeley and the University of Illinois at Urbana-Champaign.

The news comes as a related group of researchers has nearly finished the design of an FPGA-based system intended to serve as a vehicle for exploring ideas in parallel computing.

Other companies and government research agencies need to attack the programming issue, which leaders at the new Berkeley lab are calling the biggest problem in the history of computer science.

"This architectural shift will change chips, systems and software, so it has the potential to radically change the industry," said Kurt Keutzer, a professor of computer science at Berkeley working in the new lab. "This shift will change how we write software for everything."

Charles Thacker is the computer pioneer and technical fellow overseeing the small systems architecture team at Microsoft Research that is helping to design the research computer. "What I am hoping is things like [the FPGA-based system] will revitalize research in computer architecture," said Thacker.

A handful of companies are stepping up to the challenge in various ways. Advanced Micro Devices, Hewlett-Packard, IBM and Nvidia are all gearing up new parallel computing initiatives.

One of AMD's chief technologists is now working full-time to drive a parallel computing initiative. HP started a multifaceted effort in its labs about a year ago.

Nvidia is rolling out chips and tools for running processing-intensive vertical applications in areas such as oil and gas exploration on its massively parallel graphics chips. And IBM has started a "cloud computing" initiative that includes work on parallel programming issues.

Others are still ignoring or unaware of the looming crisis. "I still don't see as much concern about this in the applications community, including sectors like CAD and EDA," said Keutzer, who was chief technology officer for Synopsys before joining Berkeley.

Among federal research agencies, the National Science Foundation and the Defense Advanced Research Projects Agency have let past efforts in parallelism for high-end systems go fallow, said Kathy Yelick, another professor of computer science at Berkeley working in the lab.

"It's impressive [that Intel and Microsoft] have a concerted effort. Now it's a question of whether federally funded agencies are putting enough attention here," Yelick said.

A daunting task

If researchers can successfully define a mainstream parallel programming model-- a daunting task in itself--an even bigger job is ahead: retraining today's software developers.

"We are talking about teaching a large number of people new programming techniques for all sorts of machines, from notebooks to servers," said Yelick.

The work is already starting in a small way. For instance, Intel started a program recently to help educate University of Illinois students in parallel programming.

"We believe that not only do we need to change graduate courses, but we also need to teach undergrads right now about this shift, even though we don't know what the new model is yet," said David Patterson, a veteran computer science professor and researcher at Berkeley who will head the new lab.

Freshman programming classes at Berkeley now include a segment on parallel techniques such as MapReduce, a novel algorithm developed by Google for taking a large number of data streams in parallel off disk and processing them. "It's one particular model that works for a wide class of problems," said Yelick.

Seeds of funding
Berkeley researchers first heard about the $10 million grant in February 2007 from Intel's head of research, Andrew Chien. He told them Microsoft and Intel would solicit proposals from 25 top U.S. universities for the so-called Universal Parallel Computer Research Center.

"That was music to our ears because we had spent nearly two years investigating this without any clear funding," said Keutzer.

A core group of researchers--including Keutzer, Patterson and Yelick--began holding regular meetings on the parallel software problem in early 2005. "It took a year just to get our terms clear," said Keutzer.

The group published a widely regarded paper on its initial thoughts in December 2006.

"We had spent a lot of time seriously thinking about this problem, and I think that showed in our proposal," said Keutzer.

The Berkeley proposal takes a top-down approach. Researchers have already started work on five prototype parallel applications in areas such as image retrieval, personal health analysis and music processing.

"One of the key elements of our proposal is we think there is really a small number of parallel computational patterns underlying diverse parallel apps, and we can build a software abstraction layer for them," said Keutzer.

The Intel and Microsoft request was "fairly broad" and open-ended, focusing mainly on programming issues. However, it also called for a secondary focus on ideas for hardware implementations that could ease the parallel programming task, Keutzer said.

Yelick said, "I've worked in parallel programming for a long time, and this is the first time I have seen hardware developers wanting to work closely with software developers to find out what they need in the hardware to help enable ease of programming. It's a very different state of affairs."

Wintel's short list

By July of last year, Berkeley researchers knew they had made Wintel's short list for the grant, and by December, they were informed they had won it.

Intel already funds a three-person lab focused on parallel computing issues just off the Berkeley campus. The team will add at least one researcher as it turns its attention to work with the new lab.

Microsoft has participated in Berkeley's retreats on the topic, but it is unclear whether it will dedicate any researchers to the local lab.

Keutzer and Patterson said they expect to demonstrate the first fruits of their work at a retreat in summer 2010. Work on image retrieval and parallel browser applications has already begun, making those projects the most likely to be the first demo vehicles.

"The different parallel apps will progress at different rates, but I think you will see some significant progress in the next couple of years," said Keutzer.

The lab aims to develop a set of low-level frameworks to help developers break down their applications into fundamental parallel tasks. It also wants to design a run-time environment that will schedule multiple program modules in a flexible way to make the best use of parallel hardware resources.

Patterson said all results will be made available through open source code using the BSD license. "Everyone seems to be happy with that," he said.

RAMPing up
The work will begin in earnest this spring when researchers complete the design for an FPGA-based computer. The so-called Berkeley Emulation Engine version 3 (BEE3) is intended to help researchers quickly prototype processors with hundreds or thousands of cores and explore new ways of programming them.

The latest version of the Berkeley-developed engine was designed as a commercially available system with significant help from Microsoft Research.

The system is the centerpiece of the Research Accelerator for Multiple Processors (RAMP) program among Berkeley, Microsoft, Intel and five other major U.S. universities, including MIT and Stanford. The effort is part of a broad search for new ways to build computers now that chip designers have determined they can no longer push raw data rates, because of power leakage.

"I was in computer science research for 25 years and found the work got to be pretty boring because it became very incremental, with a lot of papers reporting on 5 percent performance increases," said Thacker of Microsoft Research, who led the team at Xerox PARC that developed an early prototype of the personal computer.

Incredible amount of money

"That's not how it was 30 years ago, when the field was wide open and it was easy to do seminal work," Thacker said. "Today, if you want to do something competitive with Intel, you have to spend an incredible amount of money; but now with FPGAs, you can simulate what you want. It doesn't run as fast [as an Intel processor], but it runs fast enough."

Several universities built early versions of the BEE system for their own internal use. The latest version was designed with help from Microsoft and contract manufacturer Celestica, and was aimed at creating a general-purpose industrial computer for researchers.

Celestica is currently doing a final re-spin of the main printed-circuit board, and Berkeley researchers are wrapping up work on a peripheral control board. The design is being made available on a royalty-free basis.

"Fundamentally, FPGAs are now large enough and the tool suites good enough that a small number of people can build a fairly substantial system," said Thacker. "At the Berkeley wireless lab, they have already built a thousand-processor machine with an array of these systems racked up."

The latest version uses four Xilinx Virtex 5 LX110T FPGAs and up to 64 Gbytes of main memory. It has eight 10-Gbit/second CX4 Ethernet ports and four PCI Express slots.

"It could be useful across a wide range of apps given its flexibility and the substantial pile of RAM on the board," said Thacker, who describes BEE3 as the Swiss army knife of computer research tools.

Thacker would not say what parallel programming approaches Microsoft expects to try out on the system, other than jobs related to its published work on atomic transactions. "Many of our efforts will not be public for a while, and they are still very speculative," he said.

Asked what approaches he thinks are most promising, Thacker said, "I don't have a real good idea yet, I'm afraid. It's hard to predict the outline of the research or state milestones, but we will try many things and collaborate with universities."

In addition to the BEE3 work, Microsoft has been bolstering its ranks with supercomputing experts such as Burton Smith and Dan Reed.

Top computer science researchers have said the industry is at risk of hitting a wall if it cannot deliver a useful parallel programming model for next-generation multicore chips. Thacker had no comment on whether the industry as a whole is doing enough to tackle what is seen as an enormously difficult problem looming on the horizon.

"I don't know about the industry as a whole, but I think we do pretty well," he said, pointing to the work on the BEE3 design. "It is a lot of work, and we spent quite a bit of money on it."