Uzi Vishkin
Uzi Vishkin | |
---|---|
Born | 1953 IBM Thomas J. Watson Research Center New York University Tel Aviv University University of Maryland, College Park |
Doctoral advisor | Yossi Shiloach |
Uzi Vishkin (born 1953) 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."[1]
Biography
Uzi Vishkin was born in Tel Aviv, Israel. He completed his B.Sc. (1974) and M.Sc. in Mathematics at the
PRAM-on-chip
This section of a poorly sourced must be removed immediately from the article and its talk page, especially if potentially libelous. )Find sources: "Uzi Vishkin" – news · newspapers · books · scholar · JSTOR (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 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 algorithms
In the field of parallel algorithms, Uzi Vishkin co-authored the paper 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 JaJa (1992) and Keller, Kessler & Traeff (2001), as well as in the class notes 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 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. 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
Other contributions by Uzi Vishkin and various co-authors include parallel algorithms for
Selected publications
- Shiloach, Yossi; Vishkin, Uzi (1982a), "An O(log n) parallel connectivity algorithm", Journal of Algorithms, 3: 57–67, .
- Shiloach, Yossi; Vishkin, Uzi (1982b), "An O(n2 log n) parallel max-flow algorithm", Journal of Algorithms, 3 (2): 128–146, .
- Mehlhorn, Kurt; Vishkin, Uzi (1984), "Randomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memories", Acta Informatica, 21 (4): 339–374, S2CID 29789494.
- Tarjan, Robert; Vishkin, Uzi (1985), "An efficient parallel biconnectivity algorithm", S2CID 7231609.
- Vishkin, Uzi (1985), "Optimal parallel pattern matching in strings", Information and Control, 67 (1–3): 91–113, .
- Cole, Richard; Vishkin, Uzi (1986), "Deterministic coin tossing with applications to optimal parallel list ranking", Information and Control, 70 (1): 32–53, .
- Vishkin, Uzi; Dascal, Shlomit; Berkovich, Efraim; Nuzman, Joseph (1998), "Explicit Multi-Threading (XMT) bridging models for instruction parallelism", Proc. 1998 ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 140–151.
- Naishlos, Dorit; Nuzman, Joseph; Tseng, Chau-Wen; Vishkin, Uzi (2003), "Towards a First Vertical Prototyping of an Extremely Fine-Grained Parallel Programming Approach" (PDF), Theory of Computing Systems, 36 (5): 551–552, S2CID 1929495.
- Wen, Xingzhi; Vishkin, Uzi (2008), "FPGA-based prototype of a PRAM-on-chip processor", Proc. 2008 ACM Conference on Computing Frontiers (Ischia, Italy) (PDF), pp. 55–66, S2CID 11557669.
- Vishkin, Uzi (January 2011), "Using simple abstraction to reinvent computing for parallelism", Communications of the ACM, 54 (1): 75–85, S2CID 10279904.
- Ghanim, Fady; Vishkin, Uzi; Barua, Rajeev (February 2018), "Easy PRAM-Based High-Performance Parallel Programming with ICE", IEEE Transactions on Parallel and Distributed Systems, 29 (2): 377–390, hdl:1903/18521.
Notes
- ^ ACM: Fellows Award / Uzi Vishkin.
- ^ Vishkin, Uzi. Spawn-join instruction set architecture for providing explicit multithreading. U.S. Patent 6,463,527. See also Vishkin et al. (1998).
- ^ University of Maryland, press release, June 26, 2007: "Maryland Professor Creates Desktop Supercomputer" Archived 2009-12-14 at the Wayback Machine.
- ^ University of Maryland, A. James Clark School of Engineering, press release, November 28, 2007: "Next Big "Leap" in Computing Technology Gets a Name".
- ^ 1st ed., Section 30.5.
- ^ See, e.g., Goldberg, Plotkin & Shannon (1988).
References
- Baase, Sara; Van Gelder, Allen (2000), ISBN 978-0-201-61244-8
- S2CID 16416106.
- ISBN 978-0-262-03141-7
This survey paper cites 16 papers co-authored by Vishkin
- doi:10.1137/0401044
- JaJa, Joseph (1992), ISBN 978-0-201-54856-3
Cites 36 papers co-authored by Vishkin
- Karp, Richard M.; Ramachandran, Vijaya (1988), "A Survey of Parallel Algorithms for Shared-Memory Machines", University of California, Berkeley, Department of EECS, Tech. Rep. UCB/CSD-88-408
This survey paper cites 20 papers co-authored by Vishkin
- Keller, Jorg; Kessler, Cristoph W.; Traeff, Jesper L. (2001), ISBN 978-0-471-35351-5
Cites 19 papers co-authored by Vishkin
- ISBN 978-0-201-12037-0
- Vishkin, Uzi (2009), Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques, 104 pages (PDF), Class notes of courses on parallel algorithms taught since 1992 at the University of Maryland, College Park, Tel Aviv University and the Technion
- Mathematics Genealogy Project: Uzi Vishkin.
- ISI Web of Knowledge, highly cited researchers: Uzi Vishkin.