Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456 Uzi Vishkin
Parallel computer architecture.
The premise that inspired his work in the last few years on the PRAM-On-Chip framework has been:
Were the architecture component of PRAM-On-Chip feasible in the 1990s, its parallel
programming component would have become the mainstream standard.
In 1979 Uzi Vishkin identified the issue of parallel algorithms/programmability as
the most critical component in developing a successful general-purpose parallel
computer architecture. It simply did not look practical to proceed with building
parallel computers before establishing a first satisfactory draft of its specifications.
Such "specs" had to include how to think about programming the computer to be built.
Many, including Uzi Vishkin, spent the next 15-20 years on parallel algorithmics.
In fact, during the 1980s and the early 1990s, quite a few very
talented computer science researchers worked on the following wider problem:
Seek the "ultimate" parallel programming model that will allow
easy expression of parallel algorithms and their programs in the model, as well as
validation of the model by algorithmic paradigms and solutions for as many problems as possible.
In this fierce "battle of ideas", the one approach that has beaten all its competitors by a truly wide margin was the PRAM approach.
As early as 1988, standard algorithms textbooks started including significant chapters on PRAM algorithms, and
as the above premise suggests,
PRAM algorithms were on their way to become standard computer science know-how that every computer science graduate
must command and the basis for standard parallel programming. However, multi-chip multi-processing architectures provided the only form of
multi-processing available in the 1990s. They required high coordination overhead, which prevented PRAM algorithms from
providing an effective abstraction for them. As a result,
it became common wisdom that "PRAM algorithms are unrealistics", leading later editions of some textbooks to remove their PRAM
chapters.
The good news are that the PRAM-On-Chip effort is finally establishing that it
is becoming feasible to build a parallel computer that can be effectively
programmed by a PRAM-like language.
From a 2005 perspective,
the prospects for making the PRAM approach a standard for parallel algorithms
and programming look pretty good: (i) "Darwin has already spoken" - see the
natural selection that already happened in what was called above the battle
of ideas, and (ii) The inclusion of significant PRAM chapters
in standard textbooks, before concerns about implementability prevailed; but
these concernes are becoming irrelevant as the PRAM-On-Chip progresses.
The optimistic tone above should not hide the fact that a significant research
effort is still underway.
Pattern matching.
Theory of computing. In fact, the theory-driven PRAM-On-Chip
effort aspires to provide a nice example where a forward looking
theory-driven approach has practical impact.
Program Chair, ACM SPAA 2006
From the scope statement for SPAA 2006:
A renaissance of parallel computing research is on the horizon since:
(i) chip multi-cores are the wave of the future for all major hardware vendors,
(ii) since 2003 clock frequency of CPUs is hardly advancing any more,
(iii) the 6-decade quest for an easy-to-program parallel architecture paradigm
is yet to provide a competitive alternative to the serial paradigm.
Contributed papers on algorithmics, software and/or hardware that address this
emerging renaissance are particularly welcome for SPAA 2006.