Title: A PRAM Low Development-Time Roadmap for General-Purpose Parallel Computing

Date/Time: Thursday, March 23, 2006, 3:00 – 4:00 pm (MST)

Location: Building 980, Room 24 (Sandia NM)

Brief Abstract: How to upgrade performance and utility of computer systems by incorporating parallel processing? This question has led to significant investment over several decades. Still, the world is yet to see a high-productivity parallel computer system , where low development-time for applications make it a system of choice for a significant range users who are not guided by run-time alone. Replacing a previous concern regarding the slow rate in which parallel software is produced—the “parallel software crisis” of the 1990s—itself replacing a “parallel programmability” concern, the current focus is on productivity. However, my diagnosis, since joining the field in 1979, has not changed. The enabling technology that will once and for all put all these problems (or “symptoms”) on tract to solution is a proper parallel programming model. A key attribute of such a model must be that it will allow programmers to develop the concept of their program—their parallel algorithmic thinking—in a simple computation model and that the coding effort beyond the computation model will be minimal. A case for using a very simple parallel computation model, the parallel random access model (PRAM), will be made. (i) The parallel algorithms research community succeeded in developing a theory of parallel algorithms much richer than any competing approach and second in magnitude only to serial algorithmics. (ii) Were an architecture effectively supporting the feasible in the 1990s, the PRAM parallel programming would have become the mainstream standard; in 1988-90 standard algorithms textbooks chose to include significant PRAM chapters (some still have them). Arguably nothing could stand in the way of teaching them to every student at every computer science program. However, the fact is that PRAM theory has generally not reached out beyond the ivory towers. For example, the jury is still out on whether the PRAM can provide an effective abstraction for a proper design of a multi-chip multi-processors. The case for a lower hanging fruit, the PRAM-On-Chip research project at UMD, will be presented. Guided by the fact that the number of transistors on a chip already exceeds a Billion, up from less that 30, 000 circa 1980, and keeps growing, the main insight behind PRAM-On-Chip is as follows. The Billion transistor chip era allows for the first time low-overhead on-chip multi-processor thereby avoiding concerns regarding the higher overhead of multi-chip multiprocessors. It also allows an evolutionary path from serial computing. The drastic recent slow down in clock rate improvement for commodity processors is forcing leading vendors to shift all future performance growth, such as seeking growth to 100-core chips by 2015 and to programming for concurrency. If rushed to action, government can still affect the direction of high-end commodity processors and thereby the way they would render the multi-processor that government will purchase in the next decades as is at a much higher price than needed for a desired impact now. I expect industry investment to soon dwarf government means. A key milestone in our low-development-time roadmap is a complete system demonstration that the PRAM abstraction is effective. This would resolve the programming model enabling technology problem for a key family of parallel processors and will spearhead such resolution for other families.

CSRI POC: Sue Goudy, (505) 844-6083