Uzi Vishkin

Uzi Vishkin started his work on parallel computing in 1979 as he began his doctoral research. Conjecturing then that transition to parallelism may turn into the only paradigm shift in core computing during his professional lifetime, Vishkin strategized his research career around three quests. Faced with what he considered a build-first-figure-out-how-to-program-later approach from the computer systems side and the dominance of NC (polynomial number of processors and polylogarithmic time) complexity theory, Vishkin went against the grain. His first quest was to crystalize the notion of parallel algorithmic thinking (i) to enable later system specification, (ii) yet challenge prominent theorists by favoring parallel algorithms whose total number of operations is as close as possible to that of the serial algorithms they seek to speed up. Parallel algorithms textbooks and survey adopted his work-depth (WD) methodology and incorporated tens of the PRAM algorithm he and colleagues invented, including: symmetry breaking techniques including , coin tossing (applied also in distributed computing), integer sorting (precursor to map-reduce) finding lowest comment ancestors, Euler tour technique, parallel graph algorithms for connectivity and  biconnectivity, original string matching techniques: witnesses and deterministic sampling, and 2-3 trees, and introduced their fit into an elegant structure---unusual for combinatorics or algorithms—including more advanced algorithms such as triconnectivity and maxflow.

His second quest was to invent the PRAM-On-Chip XMT architecture, have it prototyped including commitment to silicon and demonstration that as-is WD algorithms can be automatically implemented to achieve competitive results, refuting a broad presumption that PRAM is unrealistic. His 2005 hybrid memory for serial and parallel computing has been a precursor to CPU-integrated parallel accelerators, such as GPUs, in Billions of devices such as PCs and laptops since the early 2010s. The XMT ease of programming was demonstrated by over 1000 students in a single high school. His third, and current, quest is R&D of “killer apps” for the approach.

Education, appointments and honors B.Sc. and M.Sc. in Mathematics, Hebrew University. D.Sc., Computer Science, Technion, 1981. Post-doc, IBM Thomas J. Watson Research Center.1982 to 1984: department of computer science at New York University; remained affiliated till 1988. 1984 to 1997: Professor of computer science, Tel Aviv University. 1987 to 1988: CS Chair. 1988 and on: Professor of Electrical and Computer Engineering and permanent member of the University of Maryland Institute for Advanced Computer Studies (UMIACS). He is ACM Fellow for, among other things, having “played a leading role in forming and shaping what thinking in parallel has come to mean in the fundamental theory of Computer Science”. He was also an ISI-Thompson Highly Cited Researcher, is Fellow of the National Academy of Inventors (NAI), and winner of the ACM-SPAA Parallel Computing Award.