Uzi Vishkin

Professor
5216 Iribe Center
(301) 405-6763
Education: 
D.Sc., Technion - Israel Institute of Technology (Computer Science)
Special Awards/Honors: 
ACM Fellow
Biography: 

Uzi Vishkin is a professor of electrical and computer engineering with a permanent appointment in the University of Maryland Institute for Advanced Computer Studies.

His research focuses on parallelism in computing, design and analysis of algorithms, and synergy of algorithms.

He started his work on parallel computing in 1979 as a doctoral student at the Technion - Israel Institute of Technology. Vishkin's initial focus was on parallel algorithms and parallel algorithmic thinking. The 1982 Shiloach-Vishkin work-depth methodology for presenting parallel algorithms provided the presentation framework in several parallel algorithm (known as PRAM algorithms) texts, which also include a considerable number of parallel algorithms he co-authored.

This parallel algorithms theory provided the basis for his invention of the PRAM-On-Chip desktop supercomputer framework that scales beyond 1000 processors on chip. He later led its extensive hardware and software prototyping, including a 64-processor computer that has already been programmed by more than 100 middle school and high school students. He was named a Maryland Innovator of the Year for his PRAM-On-Chip venture, whose main patent has been widely cited in patents of the major vendors.

A follow-up proposal, entitled Center for Reinvention of Computing for Parallelism, ranked first among 49 proposals in a University System of Maryland (USM)-wide competition for Maryland Research Centers of Excellence.

In 1996, he was elected an 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 is also an ISI-Thompson Highly Cited Researcher.

Before coming to the University of Maryland, Vishkin was affiliated with Tel Aviv University between and 1984 and 1997, and was chair of its computer science department from 1987 to 1988. Vishkin also worked for IBM T.J. Watson and New York University.

He received his doctorate in computer science from Technion - Israel Institute of Technology in 1981.

Go here to view Vishkin's academic publications on Google Scholar.

Publications

2011


Horak MN, Nowick SM, Carlberg M, Vishkin U.  2011.  A Low-Overhead Asynchronous Interconnection Network for GALS Chip Multiprocessors. Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on. 30(4):494-507.

Caragea GC, Vishkin U.  2011.  Brief announcement: better speedups for parallel max-flow. Proceedings of the 23rd ACM symposium on Parallelism in algorithms and architectures.
:131-134.

Keceli F, Tzannes A, Caragea GC, Barua R, Vishkin U.  2011.  Toolchain for Programming, Simulating and Studying the XMT Many-Core Architecture. Parallel and Distributed Processing Workshops and Phd Forum (IPDPSW), 2011 IEEE International Symposium on.
:1282-1291.

2010


Caragea GC, Tzannes A, Keceli F, Barua R, Vishkin U.  2010.  Resource-Aware Compiler Prefetching for Many-Cores. Parallel and Distributed Computing (ISPDC), 2010 Ninth International Symposium on.
:133-140.

Tzannes A, Caragea GC, Barua R, Vishkin U.  2010.  Lazy binary-splitting: a run-time adaptive work-stealing scheduler. Proceedings of the 15th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming.
:179-190.

Torbert S, Vishkin U, Tzur R, Ellison DJ.  2010.  Is teaching parallel algorithmic thinking to high school students possible?: one teacher's experience Proceedings of the 41st ACM technical symposium on Computer science education.
:290-294.

Caragea GC, Keceli F, Tzannes A, Vishkin U.  2010.  General-purpose vs. gpu: Comparison of many-cores on irregular workloads. Proceedings of the Second Usenix Workshop on Hot Topics in Parallelism.
:14-15.

2009


Balkan AO, Qu G, Vishkin U.  2009.  Mesh-of-Trees and Alternative Interconnection Networks for Single-Chip Parallelism. Very Large Scale Integration (VLSI) Systems, IEEE Transactions on. 17(10):1419-1432.

Caragea GC, Saybasili AB, Wen X, Vishkin U.  2009.  Brief announcement: performance potential of an easy-to-program PRAM-on-chip prototype versus state-of-the-art processor. Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures.
:163-165.

2008


Vishkin U.  2008.  Toward Realizing a PRAM-on-a-Chip Vision. Lecture Notes in Computer Science. 4854:5-6.

Balkan AO, Qu G, Vishkin U.  2008.  An area-efficient high-throughput hybrid interconnection network for single-chip parallel processing. Proceedings of the 45th annual Design Automation Conference.
:435-440.

Hochstein L, Basili VR, Vishkin U, Gilbert J.  2008.  A pilot study to compare programming effort for two parallel programming models. Journal of Systems and Software. 81(11):1920-1930.

Wen X, Vishkin U.  2008.  Fpga-based prototype of a pram-on-chip processor. Proceedings of the 5th conference on Computing frontiers.
:55-66.

2007


Balkan AO, Horak MN, Qu G, Vishkin U.  2007.  Layout-Accurate Design and Implementation of a High-Throughput Interconnection Network for Single-Chip Parallel Processing. High-Performance Interconnects, 2007. HOTI 2007. 15th Annual IEEE Symposium on.
:21-28.

Wen X, Vishkin U.  2007.  PRAM-on-chip: first commitment to silicon. Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures.
:301-302.

Vishkin U, Caragea GC, Lee B.  2007.  Models for advancing PRAM and other algorithms into parallel programs for a PRAM-On-Chip platform. IN HANDBOOK OF PARALLEL COMPUTING: MODELS, ALGORITHMS AND APPLICATIONS, EDITORS.

Vishkin U, Smolyaninov I, Davis C.  2007.  Plasmonics and the parallel programming problem. Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series. 6477:19-19.

Vishkin U.  2007.  Towards Realizing a PRAM-On-Chip Vision. Workshop on Highly Parallel Processing on a Chip (HPPC). 28

Peckerar M, Sander D, Srivastava A, Foli A, Vishkin U.  2007.  Electron beam and optical proximity effect reduction for nanolithography: New results. Journal of Vacuum Science & Technology B. 25(6):2288-2294.

2006


Milner S, Llorca J, Anibha A, Vishkin U.  2006.  A bootstrapping model for directional wireless networks. Communications Letters, IEEE. 10(12):840-842.

Liu F, Vishkin U, Milner S.  2006.  Bootstrapping free-space optical networks. Selected Areas in Communications, IEEE Journal on. 24(12):13-22.

Balkan AO, Vishkin U.  2006.  Programmer's Manual for XMTC Language, XMTC Compiler and XMT Simulator. Technical Reports from UMIACS, UMIACS-TR-2005-45.

2004


Balkan AO, Qu G, Vishkin U.  2004.  Arbitrate-and-move primitives for high throughput on-chip interconnection networks. Circuits and Systems, 2004. ISCAS '04. Proceedings of the 2004 International Symposium on. 2:II-441-4Vol.2-II-441-4Vol.2.

Llorca J, Desai A, Vishkin U, Davis CC, Milner SD.  2004.  Reconfigurable optical wireless sensor networks. Proceedings of SPIE. 5237(1):136-146.

Vishkin U.  2004.  PRAM-On-Chip: A Quest for Not-So-Obvious Non-obviousness. Mathematical Foundations of Computer Science 2004Mathematical Foundations of Computer Science 2004. 3153:104-105.

Vishkin U, Smolyaninov I.  2004.  Bending light for multi-chip virtual PRAMs? Proc. 3rd Workshop on Non-Slicon Computation, held in conjunction with the 31st International Symposium on Computer Architecture (ISCA 2004).
:19-23.

2003


Naishlos D, Nuzman J, Tseng CW, Vishkin U.  2003.  Towards a first vertical prototyping of an extremely fine-grained parallel programming approach. Theory of Computing Systems. 36(5):521-552.

Kutten S, Peleg D, Vishkin U.  2003.  Deterministic Resource Discovery in Distributed Networks. Theory of Computing Systems. 36(5):479-495.

2002


Vishkin U.  2002.  Two techniques for reconciling algorithm parallelism with memory constraints. Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures.
:95-98.

2001


Naishlos D, Nuzman J, Tseng CW, Vishkin U.  2001.  Evaluating the XMT parallel programming model. High-Level Parallel Programming Models and Supportive Environments.
:95-108.

2000


Vishkin U.  2000.  A no-busy-wait balanced tree parallel algorithmic paradigm. Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures.
:147-155.

Vishkin U.  2000.  PRAM-On-Chip Vision. String Processing and Information Retrieval, 2000. SPIRE 2000. Proceedings. Seventh International Symposium on.
:260-260.

Naishlos D, Nuzman J, Tseng CW, Vishkin U.  2000.  Evaluating multi-threading in the prototype XMT environment. Proc. 4th Workshop on Multi-Threaded Execution, Architecture and Compliation (MTEAC2000).

Cormode G, Paterson M, Sahinalp S C, Vishkin U.  2000.  Communication complexity of document exchange. Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms.
:197-206.

1999


Berkovich E, Nuzman J, Franklin M, Jacob B, Vishkin U.  1999.  XMT-M: A Scalable Decentralized Processor. UMIACS-TR-99-55

Mansour Y, Nisan N, Vishkin U.  1999.  Trade-offs between communication throughput and parallel time. Journal of Complexity. 15(1):148-166.

1998


Vishkin U, Dascal S, Berkovich E, Nuzman J.  1998.  Explicit Multi-Threading (XMT) bridging models for instruction parallelism (extended abstract). Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures.
:140-151.

1997


Vishkin U.  1997.  From algorithm parallelism to instruction-level parallelism: An encode-decode chain using prefix-sum. Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures.
:260-271.

1996


Sahinalp SC, Vishkin U.  1996.  Efficient approximate and dynamic matching of patterns using a labeling paradigm. Foundations of Computer Science, 1996. Proceedings., 37th Annual Symposium on.
:320-328.

Berkman O, Schieber B, Vishkin U.  1996.  A fast parallel algorithm for finding the convex hull of a sorted point set. International Journal of Computational Geometry and Applications. 6:231-242.

1995


Vishkin U.  1995.  On a technique for parsing a string. Combinatorial Pattern Matching.
:386-386.

Vishkin U.  1995.  On a Technique for Parsing a String (Invited Lecture). Lecture Notes in Computer Science. 937:386-386.

Sahinalp SC, Vishkin U.  1995.  Data compression using locally consistent parsing. TechnicM report, University of Maryland Department of Computer Science.

Raman R, Vishkin U.  1995.  Parallel algorithms for database operations and a database operation for parallel algorithms. Parallel Processing Symposium, 1995. Proceedings., 9th International.
:173-179.

Matias E, Vishkin U.  1995.  A note on reducing parallel model simulations to integer sorting. Parallel Processing Symposium, 1995. Proceedings., 9th International.
:208-212.

Berkman O, Vishkin U.  1995.  Almost fully-parallel parentheses matching. Discrete applied mathematics. 57(1):11-28.

1994


Landau GM, Vishkin U.  1994.  Pattern matching in a digitized image. Algorithmica. 12(4):375-408.

Goodrich MT, Matias Y, Vishkin U.  1994.  Optimal parallel approximation for prefix sums and integer sorting. Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms.
:241-250.

Cole R, Vishkin U.  1994.  On the detection of robust curves. CVGIP: Graphical Models and Image Processing. 56(3):189-204.

Berkman O, Vishkin U.  1994.  Finding level-ancestors in trees. Journal of Computer and System Sciences. 48(2):214-230.

Berkman O, JaJa JF, Krishnamurthy S, Thurimella R, Vishkin U.  1994.  Top-Bottom Routing around a Rectangle is as Easy as Computing Prefix Minima. SIAM Journal on Computing. 23(3):449-465.

Pages