Uzi Vishkin
Encyclopedia
Uzi Vishkin is a computer scientist at the University of Maryland, College Park
, where he is Professor of Electrical and Computer Engineering at the University of Maryland Institute for Advanced Computer Studies (UMIACS). Uzi Vishkin is known for his work in the field of parallel computing
. In 1996, he was inducted as a Fellow
of the Association for Computing Machinery
, with the following citation: "One of the pioneers of parallel algorithms research, Dr. Vishkin's seminal contributions played a leading role in forming and shaping what thinking in parallel has come to mean in the fundamental theory of Computer Science."
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
.
The rudimentary parallel abstraction behind the PRAM-on-chip concept, dubbed Immediate Concurrent Execution (ICE) in , is that indefinitely many instructions available for concurrent execution execute immediately. A consequence of ICE is a step-by-step (inductive) explication 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 1997 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 computer named Paraleap, that demonstrates the overall concept. The XMT concept was presented in , , the XMT 64-processor computer in and most recently in . 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.
. 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 . 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., and it forms the basis of many other distributed algorithms for graph colouring.
Other contributions by Uzi Vishkin and various co-authors include parallel algorithms for list ranking, lowest common ancestor
, spanning trees
, and biconnected component
s.
University of Maryland, College Park
The University of Maryland, College Park is a top-ranked public research university located in the city of College Park in Prince George's County, Maryland, just outside Washington, D.C...
, where he is Professor of Electrical and Computer Engineering at the University of Maryland Institute for Advanced Computer Studies (UMIACS). Uzi Vishkin is known for his work in the field of parallel computing
Parallel computing
Parallel computing is a form of computation in which many calculations are carried out simultaneously, operating on the principle that large problems can often be divided into smaller ones, which are then solved concurrently . There are several different forms of parallel computing: bit-level,...
. In 1996, he was inducted as a Fellow
Fellow
A fellow in the broadest sense is someone who is an equal or a comrade. The term fellow is also used to describe a person, particularly by those in the upper social classes. It is most often used in an academic context: a fellow is often part of an elite group of learned people who are awarded...
of the Association for Computing Machinery
Association for Computing Machinery
The Association for Computing Machinery is a learned society for computing. It was founded in 1947 as the world's first scientific and educational computing society. Its membership is more than 92,000 as of 2009...
, with the following citation: "One of the pioneers of parallel algorithms research, Dr. Vishkin's seminal contributions played a leading role in forming and shaping what thinking in parallel has come to mean in the fundamental theory of Computer Science."
Biography
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 UniversityNew York University
New York University is a private, nonsectarian research university based in New York City. NYU's main campus is situated in the Greenwich Village section of Manhattan...
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
University of Maryland, College Park
The University of Maryland, College Park is a top-ranked public research university located in the city of College Park in Prince George's County, Maryland, just outside Washington, D.C...
.
PRAM-on-chip
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 , is that indefinitely many instructions available for concurrent execution execute immediately. A consequence of ICE is a step-by-step (inductive) explication 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
Software prototyping
*Software prototyping, refers to the activity of creating prototypes of software applications, i.e., incomplete versions of the software program being developed...
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
Parallel Random Access Machine
In computer science, Parallel Random Access Machine is a shared memory abstract machine. As its name indicates, the PRAM was intended as the parallel computing analogy to the 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 1997 that the transistor count
Transistor count
The transistor count of a device is the number of transistors in the device.Transistor count is the most common measure of integrated circuit complexity. According to Moore's Law, the transistor count of the integrated circuits doubles every two years...
on chip as implied by Moore's Law
Moore's Law
Moore's law describes a long-term trend in the history of computing hardware: the number of transistors that can be placed inexpensively on an integrated circuit doubles approximately every two years....
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
Explicit multi-threading
Explicit Multi-Threading is a computer science paradigm for building and programming parallel computers designed around the Parallel Random Access Machine parallel computational model...
(XMT) computer architecture that enables implementation of this PRAM theory, and led his research team to completing in January 2007 a 64-processor computer named Paraleap, that demonstrates the overall concept. The XMT concept was presented in , , the XMT 64-processor computer in and most recently in . 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
XMTC
XMTC is a shared-memory parallel programming language. It is an extension of the C programming language which strives to enable easy PRAM-like programming based on the explicit multi-threading paradigm. It is developed as part of the by a research team at the University of Maryland, College...
. 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.
Parallel algorithms
In the field of parallel algorithms, Uzi Vishkin co-authored the paper 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 and , as well as in the class notes . 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 . 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 XMTCXMTC
XMTC is a shared-memory parallel programming language. It is an extension of the C programming language which strives to enable easy PRAM-like programming based on the explicit multi-threading paradigm. It is developed as part of the by a research team at the University of Maryland, College...
. 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 . This work introduced an efficient parallel technique for graph coloring
Graph coloring
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the...
. The Cole–Vishkin algorithm finds a vertex colouring in an n-cycle
Cycle graph
In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices connected in a closed chain. The cycle graph with n vertices is called Cn...
in O(log* n) synchronous communication rounds. This algorithm is nowadays presented in many textbooks, including Introduction to Algorithms
Introduction to Algorithms
Introduction to Algorithms is a book by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. It is used as the textbook for algorithms courses at many universities. It is also one of the most commonly cited references for algorithms in published papers, with over 4600...
by Cormen et al., and it forms the basis of many other distributed algorithms for graph colouring.
Other contributions by Uzi Vishkin and various co-authors include parallel algorithms for list ranking, lowest common ancestor
Lowest common ancestor
The lowest common ancestor is a concept in graph theory and computer science. Let T be a rooted tree with n nodes. The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants .The LCA of v and w in T is the shared ancestor of v...
, spanning trees
Spanning tree (mathematics)
In the mathematical field of graph theory, a spanning tree T of a connected, undirected graph G is a tree composed of all the vertices and some of the edges of G. Informally, a spanning tree of G is a selection of edges of G that form a tree spanning every vertex...
, and biconnected component
Biconnected component
In graph theory, a biconnected component is a maximal biconnected subgraph. Any connected graph decomposes into a tree of biconnected components called the block tree of the graph. The blocks are attached to each other at shared vertices called cut vertices or articulation points...
s.
External links
- Home page of Uzi Vishkin.
- Home page of the XMT project, with links to a software release, on-line tutorial and to material for teaching parallelism.
- Uzi Vishkin in DBLPDBLPDBLP is a computer science bibliography website hosted at Universität Trier, in Germany. It was originally a database and logic programming bibliography site, and has existed at least since the 1980s. DBLP listed more than 1.3 million articles on computer science in January 2010...
.