2004-2005 Academic Year

Title: Can Parallel Computing Finally Impact Mainstream Computing?
Speaker: Uzi Vishkin, University of Maryland

Abstract:
The PRAM-On-Chip research project at UMD is reviewed.

The idea of upgrading performance and utility of computer systems
by incorporating parallel processing has been around since at least
the 1940s.  A significant investment in parallel processing in the
1980s and 1990s has led to an abundance of parallel architectures
that due to technical constraints at the time had to rely on multi-chip
multi-processing.  Unfortunately, their impact on mainstream
computing was quite limited. "Tribal lore" suggests the following
reason: while programming for parallelism tends to be easy, turning
this parallelism into the "coarse-grained" type, needed to optimize
performance for multi-chip multi-processing (with their high
coordination overhead), has been quite hard.  The mainstream
computing paradigm has always relied on serial code.  In spite of a
huge multi-decade effort in the relevant computer science academia
and industry to extract instruction level parallelism from serial
code, commercially successful processors are entering a second
decade of near stagnation in the maximum number of instructions they
can issue towards a single computational task in one clock.

The PRAM-On-Chip project at UMD is led by a fact, an old insight and
a new one.
(i) Billion transistor chips are here, up from less than 30,000 circa
1980.
(ii) Using a very simple parallel computation model, the parallel
random access model (PRAM), the parallel algorithms research
community has succeeded in developing a theory of parallel algorithms
and that theory appears to be second in magnitude only to serial
algorithmics. (Unfortunately,  this elegant algorithmic theory
remained in the ivory towers of theorists, since it did not offer an
effective abstraction for multi-chip multi-processors.)
(iii) The Billion transistor chip era allows for the first time  
low-overhead on-chip multi-processors so that the PRAM abstraction
becomes effective.

The PRAM-On-Chip team includes now a post-doc, 4 graduate, and 3
undergraduate
students. Current and future efforts are focused on several tracks.
1. Hardware and architecture research and prototyping.
2. Software systems research and prototyping.
3. Algorithms and performance programming research.
4. Application programming research.
A separate DARPA-funded programmer's productivity (development time) 
study is conducted by Dr. Basili's software eng. group.  For students,
the PRAM On Chip project offers significant opportunities for original
work (good for finishing your PhD...)and impact (helps finding a job
in academia and industry after you graduate),as well as being part of
an energetic team (fun while you are doing it).

The PRAM On Chip vision was first introduced in 1997. The following
recent highlights suggest that the world is getting much closer:
(i) SUN: new Niagara architecture with 32 CPUs on chip.
(ii) Intel: all future processor chips will have multiple CPUs on the
chip.
(iii) Burton Smith, Cray's Chief Scientist said: "...the uniprocessor
has pretty well run out of steam. Parallelism to date has been a nice
strategy for HPC users and an afterthought for microprocessor
vendors. Now, it is becoming a matter of business survival for all
processor vendors. Parallelism is going to be taken more seriously,  
starting with the idea of exploiting multi-threading and multiple
cores on a single problem. This is a major change. Imagine if
 Microsoft wanted to write Office in a parallel language. What would
that language be, and what would be the architecture to support it?  
We don't have good answers to these questions yet."PRAM On Chip
provides answers to these questions about language and architecture.