Uzi Vishkin

Uzi Vishkin was born in Tel Aviv, Israel. He completed his B.Sc. (1974) and M.Sc. in Mathematics at the Hebrew University, before earning his D.Sc. in Computer Science at the Technion (1981). He then spent a year working at the IBM Thomas J. Watson Research Center in Yorktown Heights, New York. From 1982 to 1984, he worked at the department of computer science at New York University and remained affiliated with it till 1988. From 1984 until 1997 he worked in the computer science department of Tel Aviv University, serving as its chair from 1987 to 1988. Since 1988 he is with the University of Maryland, College Park.

{{BLP sources section|date=March 2009}}

A notable rudimentary abstraction—that any single instruction available for execution in a serial program executes immediately—made serial computing simple. A consequence of this abstraction is a step-by-step (inductive) explication of the instruction available next for execution.

The rudimentary parallel abstraction behind the PRAM-on-chip concept, dubbed Immediate Concurrent Execution (ICE) in {{harvtxt|Vishkin|2011}}, is that indefinitely many instructions available for concurrent execution execute immediately. A consequence of ICE is a step-by-step (inductive) explication (also known as lock-step) of the instructions available next for concurrent execution. Moving beyond the serial von Neumann computer (the only successful general purpose platform to date), the aspiration of the PRAM-on-chip concept is that computer science will again be able to augment

mathematical induction with a simple one-line computing abstraction. A chronological overview of the evolution of the PRAM-on-chip concept and its hardware and software prototyping follow.

In the 1980s and 1990s, Uzi Vishkin co-authored several articles that helped building a theory of parallel algorithms in a mathematical model called parallel random access machine (PRAM), which is a generalization for parallel computing of the standard serial computing model random-access machine (RAM). The parallel machines needed for implementing the PRAM model have not yet been built at the time, and quite a few challenged the ability to ever build such machines. Concluding in 1997Vishkin, Uzi. Spawn-join instruction set architecture for providing explicit multithreading. U.S. Patent 6,463,527. See also {{harvtxt|Vishkin|Dascal|Berkovich|Nuzman|1998}}. that the transistor count on chip as implied by Moore's Law will allow building a powerful parallel computer on a single silicon chip within a decade, he developed a PRAM-On-Chip vision that called for building a parallel computer on a single chip that allows programmers to develop their algorithms for the PRAM model. He went on to invent the explicit multi-threaded (XMT) computer architecture that enables implementation of this PRAM theory, and led his research team to completing in January 2007 a 64-processor computerUniversity of Maryland, press release, June 26, 2007: [http://www.newsdesk.umd.edu/scitech/release.cfm?ArticleID=1459 "Maryland Professor Creates Desktop Supercomputer"] {{Webarchive|url=https://web.archive.org/web/20091214195046/http://www.newsdesk.umd.edu/scitech/release.cfm?ArticleID=1459 |date=2009-12-14 }}. named Paraleap,University of Maryland, A. James Clark School of Engineering, press release, November 28, 2007: [http://www.eng.umd.edu/media/pressreleases/pr112707_superwinner.html "Next Big "Leap" in Computing Technology Gets a Name"]. that demonstrates the overall concept. The XMT concept was presented in {{harvtxt|Vishkin|Dascal|Berkovich|Nuzman|1998}}, {{harvtxt|Naishlos|Nuzman|Tseng|Vishkin|2003}}, the XMT 64-processor computer in {{harvtxt|Wen|Vishkin|2008}}, in {{harvtxt|Vishkin|2011}} and most recently in {{harvtxt|Ghanim|Vishkin|Barua|2018}}, where it was shown that lock-step parallel programming (using ICE) can achieve the same performance as the fastest hand-tuned multi-threaded code on XMT systems. Such inductive lock-step approach stands in contrast to multi-threaded programming approaches of other many core systems that are known for challenging programmers. The demonstration of XMT comprised several hardware and software components, as well as teaching PRAM algorithms in order to program the XMT Paraleap, using a language called XMTC. Since making parallel programming easy is one of the biggest challenges facing computer science today, the demonstration also sought to include teaching the basics of PRAM algorithms and XMTC programming to students ranging from high-school to graduate school.

Following his XMT related inventions, Uzi Vishkin was named 2024 Fellow of the National_Academy_of_Inventors (NAI). A University of Maryland announcement Maryland Today, December 10, 2024: [https://today.umd.edu/2-maryland-engineers-named-to-national-academy-of-inventors "2 Maryland Engineers Named to National Academy of Inventors: Tao, Vishkin Honored for ‘Creating Tangible Impacts’"].

noted: "Two of Vishkin's 2005 patents integrating parallel processing accelerators into the CPU, or "brain” of the computer, led computer design into a new era. The best-known example is CPUs coupled with integrated graphics processing units, present in well over a billion devices including desktop and laptop computers built since the 2010s".

In the field of parallel algorithms, Uzi Vishkin co-authored the paper {{harvtxt|Shiloach|Vishkin|1982b}} that contributed the work-time (WT) (sometimes called work-depth) framework for conceptualizing and describing parallel algorithms. The WT framework was adopted as the basic presentation framework in the parallel algorithms books {{harvtxt|JaJa|1992}} and {{harvtxt|Keller|Kessler|Traeff|2001}}, as well as in the class notes {{harvtxt|Vishkin|2009}}. In the WT framework, a parallel algorithm is first described in terms of parallel rounds. For each round, the operations to be performed are characterized, but several issues can be suppressed. For example, the number of operations at each round need not be clear, processors need not be mentioned and any information that may help with the assignment of processors to jobs need not be accounted for. Second, the suppressed information is provided. The inclusion of the suppressed information is, in fact, guided by the proof of a scheduling theorem due to {{harvtxt|Brent|1974}}. The WT framework is useful since while it can greatly simplify the initial description of a parallel algorithm, inserting the details suppressed by that initial description is often not very difficult. Similarly, first casting an algorithm in the WT framework can be very helpful for programming it in XMTC. {{harvtxt|Vishkin|2011}} explains the simple connection between the WT framework and the more rudimentary ICE abstraction noted above.

In the field of parallel and distributed algorithms, one of the seminal papers co-authored by Uzi Vishkin is {{harvtxt|Cole|Vishkin|1986}}. This work introduced an efficient parallel technique for graph coloring. The Cole–Vishkin algorithm finds a vertex colouring in an n-cycle in O(log^* n) synchronous communication rounds. This algorithm is nowadays presented in many textbooks, including Introduction to Algorithms by Cormen et al.,1st ed., Section 30.5. and it forms the basis of many other distributed algorithms for graph colouring.See, e.g., {{harvtxt|Goldberg|Plotkin|Shannon|1988}}.

Other contributions by Uzi Vishkin and various co-authors include parallel algorithms for list ranking, lowest common ancestor, spanning trees, and biconnected components.

• {{Citation

| last1 = Shiloach | first1 = Yossi

| last2 = Vishkin | first2 = Uzi

| year = 1982a

| title = An O(log n) parallel connectivity algorithm

| journal = Journal of Algorithms

| volume = 3

| issue =

| pages = 57–67

| doi =10.1016/0196-6774(82)90008-6

}}.

• {{Citation

| last1 = Shiloach | first1 = Yossi

| last2 = Vishkin | first2 = Uzi

| year = 1982b

| title = An O(n² log n) parallel max-flow algorithm

| journal = Journal of Algorithms

| volume = 3

| issue =2

| pages = 128–146

| doi =10.1016/0196-6774(82)90013-X

}}.

• {{Citation

| last1 = Mehlhorn | first1 = Kurt

| last2 = Vishkin | first2 = Uzi

| year = 1984

| title = Randomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memories

| journal = Acta Informatica

| volume = 21

| issue =4

| pages = 339–374

| doi =10.1007/BF00264615

| s2cid = 29789494

}}.

• {{Citation

| last1 = Tarjan | first1 = Robert

| last2 = Vishkin | first2 = Uzi

| year = 1985

| title = An efficient parallel biconnectivity algorithm

| journal = SIAM Journal on Computing

| volume = 14

| issue =4

| pages = 862–874

| doi =10.1137/0214061

| citeseerx = 10.1.1.465.8898

| s2cid = 7231609

}}.

• {{Citation

| last1 = Vishkin | first1 = Uzi

| year = 1985

| title = Optimal parallel pattern matching in strings

| journal = Information and Control

| volume = 67

| issue =1–3

| pages = 91–113

| doi =10.1016/S0019-9958(85)80028-0

| doi-access = free

}}.

• {{Citation

| last1 = Cole | first1 = Richard

| last2 = Vishkin | first2 = Uzi

| year = 1986

| title = Deterministic coin tossing with applications to optimal parallel list ranking

| journal = Information and Control

| volume = 70

| issue = 1

| pages = 32–53

| doi = 10.1016/S0019-9958(86)80023-7

| doi-access = free

}}.

• {{Citation

| last1=Vishkin | first1=Uzi

| last2=Dascal | first2=Shlomit

| last3=Berkovich | first3=Efraim

| last4=Nuzman | first4=Joseph

| title=Proc. 1998 ACM Symposium on Parallel Algorithms and Architectures (SPAA)

| contribution=Explicit Multi-Threading (XMT) bridging models for instruction parallelism

| pages=140–151

| year=1998

| doi=

| contribution-url=http://www.umiacs.umd.edu/users/vishkin/XMT/spaa98.ps

| title-link=Symposium on Parallel Algorithms and Architectures

}}.

• {{Citation

| last1 = Naishlos | first1 = Dorit

| last2 = Nuzman | first2 = Joseph

| last3 = Tseng | first3 = Chau-Wen

| last4 = Vishkin | first4 = Uzi

| year = 2003

| title = Towards a First Vertical Prototyping of an Extremely Fine-Grained Parallel Programming Approach

| journal = Theory of Computing Systems

| volume = 36

| issue =5

| pages = 551–552

| doi =10.1007/s00224-003-1086-6

| s2cid = 1929495

| url=http://www.umiacs.umd.edu/users/vishkin/XMT/spaa01-j-03.pdf

}}.

• {{Citation

| last1=Wen | first1=Xingzhi

| last2=Vishkin | first2=Uzi

| title=Proc. 2008 ACM Conference on Computing Frontiers (Ischia, Italy)

| contribution=FPGA-based prototype of a PRAM-on-chip processor

| pages=55–66

| year=2008

| doi=10.1145/1366230.1366240

| url=http://www.umiacs.umd.edu/users/vishkin/XMT/CompFrontiers08.pdf

| isbn=978-1-60558-077-7

| s2cid=11557669

}}.

• {{Citation

| last1=Vishkin | first1=Uzi

| journal=Communications of the ACM

| volume=54

| issue=1

| date=January 2011

| title=Using simple abstraction to reinvent computing for parallelism

| pages=75–85

| doi=10.1145/1866739.1866757

| doi-access=

| s2cid=10279904

}}.

• {{Citation

| last1=Ghanim | first1=Fady

| last2=Vishkin | first2=Uzi

| last3=Barua | first3=Rajeev

| journal= IEEE Transactions on Parallel and Distributed Systems

| volume=29

| issue=2

| date=February 2018

| title=Easy PRAM-Based High-Performance Parallel Programming with ICE

| pages=377–390

| doi=10.1109/TPDS.2017.2754376

| hdl=1903/18521

| doi-access=free

| hdl-access=free

}}.

{{Reflist|2}}

• {{Citation

| first = Sara

| last = Baase

|author2=Van Gelder, Allen

| title = Computer Algorithms Introduction to Design and Analysis

| edition = Third

| publisher = Addison-Wesley

| date = 2000

| isbn = 978-0-201-61244-8

| title-link = Computer Algorithms Introduction to Design and Analysis

}}

• {{Citation

| last1=Brent | first1=Richard P. | author1-link = Richard P. Brent

| title=The parallel evaluation of general arithmetic expressions

| journal=Journal of the ACM

| year=1974

| volume=21

| pages=201–208

| doi=10.1145/321812.321815

| issue=2 | s2cid=16416106 | doi-access=free

}}.

• {{Citation

| authorlink = Thomas H. Cormen

| first = Thomas H.

| last = Cormen

|author2=Leiserson, Charles E. | author3-link = Ronald L. Rivest

|author3=Rivest, Ronald L.

| title = Introduction to Algorithms

| edition = First

| publisher = MIT Press and McGraw-Hill

| date = 1990

| isbn = 978-0-262-03141-7

| title-link = Introduction to Algorithms

| author2-link = Charles E. Leiserson

}}

• {{Citation

| last1=Eppstein | first1=David | author1-link = David Eppstein

| last2=Galil | first2=Zvi | author2-link = Zvi Galil

| title=Parallel algorithmic techniques for combinatorial computation

| journal=Annu. Rev. Comput. Sci.

| year=1988

| volume=3

| pages=233–283

| number=

| doi=10.1146/annurev.cs.03.060188.001313

}}

This survey paper cites 16 papers co-authored by Vishkin

• {{Citation

| last1=Goldberg | first1=Andrew V. | author1-link = Andrew V. Goldberg

| last2=Plotkin | first2=Serge A.

| last3=Shannon | first3=Gregory E.

| title=Parallel symmetry-breaking in sparse graphs

| journal=SIAM Journal on Discrete Mathematics

| year=1988

| volume=1

| pages=434–446

| issue=4

| doi=10.1137/0401044

| citeseerx=10.1.1.39.269 }}

• {{Citation

| first = Joseph

| last = JaJa

| title = An Introduction to Parallel Algorithms

| edition =

| publisher = Addison-Wesley

| date = 1992

| isbn = 978-0-201-54856-3

| title-link = An Introduction to Parallel Algorithms

}}

Cites 36 papers co-authored by Vishkin

• {{Citation

| last1=Karp | first1=Richard M. | author1-link = Richard M. Karp

| last2=Ramachandran | first2=Vijaya

| title=A Survey of Parallel Algorithms for Shared-Memory Machines

| journal=University of California, Berkeley, Department of EECS, Tech. Rep. UCB/CSD-88-408

| year=1988

| volume=

| pages=

| number=

| doi=

}}

This survey paper cites 20 papers co-authored by Vishkin

• {{Citation

| first1 = Jorg

| last1 = Keller

| last2=Kessler

| first2=Cristoph W.

| last3=Traeff

| first3=Jesper L.

| title = Practical PRAM Programming

| edition =

| publisher = Wiley-Interscience

| date = 2001

| isbn = 978-0-471-35351-5

| title-link = Practical PRAM Programming

}}

Cites 19 papers co-authored by Vishkin

• {{Citation

| authorlink = Udi Manber

| first = Udi

| last = Manber

| title = Introduction to Algorithms A Creative Approach

| edition =

| publisher = Addison-Wesley

| date = 1989

| isbn = 978-0-201-12037-0

| title-link = Introduction to Algorithms A Creative Approach

}}

• {{Citation

| first = Uzi

| last = Vishkin

| title = Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques, 104 pages

| edition =

| publisher = Class notes of courses on parallel algorithms taught since 1992 at the University of Maryland, College Park, Tel Aviv University and the Technion

| date = 2009

| isbn =

| url=http://www.umiacs.umd.edu/users/vishkin/PUBLICATIONS/classnotes.pdf

}}

• Mathematics Genealogy Project: [http://genealogy.math.ndsu.nodak.edu/id.php?id=67362 Uzi Vishkin].
• ISI Web of Knowledge, highly cited researchers: [http://hcr3.isiknowledge.com/author.cgi?id=1225&cb=1689 Uzi Vishkin].

• [http://www.umiacs.umd.edu/~vishkin/index.shtml Home page of Uzi Vishkin].
• [http://www.umiacs.umd.edu/~vishkin/XMT/index.shtml Home page of the XMT project, with links to a software release, on-line tutorial and to material for teaching parallelism].
• [http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/v/Vishkin:Uzi.html Uzi Vishkin] in DBLP.

{{Authority control}}

{{DEFAULTSORT:Vishkin, Uzi}}

Category:American computer scientists

Category:Israeli computer scientists

Category:Theoretical computer scientists

Category:Researchers in distributed computing

Category:1996 fellows of the Association for Computing Machinery

Category:1953 births

Category:Living people