Uzi Vishkin

- Professor, Univ. of Md Institute for Advanced Computer Studies (UMIACS) and
Department of Electrical and Computer Engineering
- Affiliate Professor, Department of Computer Science. See, the Algorithms and Theory Group

Education

D.Sc., Computer Science, Technion - Israel Institute of Technology (Haifa, Israel), 1981
M.Sc., Mathematics, Hebrew University (Jerusalem, Israel), 1975
B.Sc., Mathematics, Hebrew University (Jerusalem, Israel), 1974

Organization

Fellow, Association for Computing Machinery (ACM), 1996. 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.
Highly Cited Researcher, Computer Science, Thompson ISI, 2003.

Research Interests

Non-technical introduction: The standard introduction of programming to Computer Science students teaches them to assume that any instruction in their program will be immediately executed by the computer. As computers keep executing an ever growing number of instructions in parallel, this introduction needs to be generalized for parallel execution of instructions. The generalization Uzi Vishkin has advocated since 1979 is: indefinitely many instructions that are available for concurrent execution execute immediately. This generalization is very powerful, as some parallelism can be observed in algorithms for practically every program. His work, along with the work of many colleagues, has demonstrated the utility of this generalization in algorithms and programs. His work also demonstrated feasibility of building the needed hardware. However, the unfortunate reality is that vendors are yet to provide hardware that supports effectively this simple generalization, forcing programmers instead to choose between giving up the performance benefits of parallelism, or work exceedingly hard to exploit these benefits. These much-too-difficult-to-program-than-necessary systems are the main reason for missing the grand opportunity of taking advantage of parallelism for achieving quantum leaps in information technology applications: 1. The investment needed for developing new parallel programs for current hardware is too high; and 2. Making a business case for the application innovations that the better-engineered hardware would bring about requires a leap of faith; namely, that applications will follow. However, normally applications tend to follow, rather than precede, availability of hardware.
Now that commodity computing has been greatly extended from desktops and laptops to tablets and smartphones, and competition among vendors is tighter, the conditions for advancing this generalization are improving: 1. Vendors will need to become far less risk averse to remain competitive. 2. Vendors have very few alternatives for differentiating their products, and this generalization provides a clear opportunity.
Listing of technical areas and some elaboration follow:

Parallelism in computing
- Parallel algorithmics
- The interplay between parallel computer systems (thread-level and processor-level parallelism) and algorithms (parallel and serial)
- Is PRAM algorithmics implementable? A PRAM-On-Chip Vision...
Design and analysis of algorithms.
Synergy of algorithms, programming and architecture for an easy-to-program general-purpose parallel computer platform.
The premise that inspired his work in the last few years on the PRAM-On-Chip framework has been: Were the architecture component of PRAM-On-Chip feasible in the 1990s, its parallel programming component would have become the mainstream standard.

In 1979 Uzi Vishkin identified the combined issue of parallel algorithms, parallel algorithmic thinking and programmability as the most critical component in developing a successful general-purpose parallel computer architecture. It simply did not look practical to proceed with building parallel computers before establishing a first satisfactory draft of its specifications. Such specifications had to include how to think about programming the computer to be built.
Many, including Uzi Vishkin, spent the next 15-20 years on parallel algorithmics. In fact, during the 1980s and the early 1990s, quite a few very talented computer science researchers worked on the following wider problem: Seek the "ultimate" parallel programming model that will allow easy expression of parallel algorithms and their programs in the model, as well as validation of the model by algorithmic paradigms and solutions for as many problems as possible. In this fierce "battle of ideas", the one approach that has beaten all its competitors by a truly wide margin was the PRAM approach. As early as 1988, standard algorithms textbooks started including significant chapters on PRAM algorithms, and as the above premise suggests, PRAM algorithms were on their way to become standard computer science know-how that every computer science graduate must command and the basis for standard parallel programming. However, multi-chip multi-processing architectures provided the only form of multi-processing available in the 1990s. They required high coordination overhead, which prevented PRAM algorithms from providing an effective abstraction for them. As a result, it became common wisdom that "PRAM algorithms are unrealistic", leading later editions of some textbooks to remove their PRAM chapters.
The good news are that the PRAM-On-Chip effort is finally establishing that it is becoming feasible to build a parallel computer that can be effectively programmed by a PRAM-like language.
From today's perspective, the prospects for making the PRAM approach a standard for parallel algorithms and programming look pretty good: (i) "Darwin has already spoken" - see the natural selection that already happened in what was called above the battle of ideas; (ii) The inclusion of significant PRAM chapters in standard textbooks, before concerns about implementability prevailed; but (iii) These concerns are becoming less and less relevant as the PRAM-On-Chip project, with its extensive hardware prototyping, continues its progress.
The optimistic tone above should not hide the fact that a significant research effort is still underway.
Pattern matching.
Theory of computing. In fact, the theory-driven PRAM-On-Chip effort aspires to provide a nice example where a forward looking theory-driven approach has practical impact.

Publications

Research Project

PRAM-On-Chip - A Desktop Supercomputer

Software Release

Link to public software release that allows you to use your own computer for programming on an XMT environment and experimenting with it

Tutorial

On-Line Tutorial . Our recent public software release allows you to use your computer for programming on an XMT environment

Organizer and presenter, Tutorial on "How to Think Algorithmically in Parallel", Seattle, WA, Sunday, June 17, 2007, held in conjunction with the 21st ACM International Conference on Supercomputing (ICS).

Conference Organization

Organizer, Workshop on Theory and Many-Cores (T&MC): What Does Theory Have to Say About Many-Core Computing? to be held at the University of Maryland, May 29, 2009.
Organizer, Workshop on Parallelism in Algorithms and Architecture, May 12, 2006
Program Chair, ACM SPAA 2006
From the scope statement for SPAA 2006:
A renaissance of parallel computing research is on the horizon since: (i) chip multi-cores are the wave of the future for all major hardware vendors, (ii) since 2003 clock frequency of CPUs is hardly advancing any more, (iii) the 6-decade quest for an easy-to-program parallel architecture paradigm is yet to provide a competitive alternative to the serial paradigm. Contributed papers on algorithmics, software and/or hardware that address this emerging renaissance are particularly welcome for SPAA 2006.

Old Talks

For more talks see the PRAM-On-Chip home page

Teaching

[ This is a link to suggestions on teaching parallelism as a theory-type algorithms course coupled with programming assignments. We provide all the material needed for a course on parallel algorithms coupled with XMTC programming assignments: video-recorded lectures for the full semester, class notes, dry homework assignments, and programming assignments along with a complete software environment, based on our recent public software release. It allows students to use their private computers for programming on an XMT environment. Lance Fortnow's recent blog postings The Revenge of Parallelism and Teaching Parallelism provide a helpful discussion thread. ]

Fall 2012: ENEE641 Mathematical Foundations for Computer Engineering.
Spring 2012: ENEE759K/CMSC751 Parallel Algorithmics
Fall 2010: ENEE459P/ENEE699 Parallel Algorithms. Click for a brief flyer explaining the importance of this course . This course is offered as a joint inter niversity course on parallel computing with the University of Illinois. See ECE news story
Fall 2010: ENEE641 Mathematical Foundations for Computer Engineering.
Spring 2010: ENEE759K/CMSC751 Parallel Algorithmics
Spring 2009: ENEE159V Introduction to Parallel Algorithmic Thinking and Its Desktop Computing Context Flier for ENEE159V, Spring 2009
Spring 2009: ENEE759K/CMSC751 Parallel Algorithmics. Video-recorded lectures for the full semester are provided. Click for a comprehesive suggestion for what to teach and how that incorporates these lectures.
Spring 2008: HONR219A Towards a New Era of Desktop Supercomputing. Subtitle: How will computer programmers have to think by the time you graduate?
Spring 2008: ENEE459P/CMSC498V Parallel Algorithms.
Spring 2007: ENEE759K/CMSC751 Parallel Algorithmics.
Fall 2005: ENEE641 Mathematical Foundations for Computer Engineering.

Interesting Teaching-Related Links

Explaining parallel computing at Middle School: What Grown-Ups Do Not Understand About Parallel Programming - The Peanut Butter and Jelly Story.
Spring 2012: Composition of Parallel Algorithms (in Greek), University of Cyprus. You cannot imagine the satisfaction a person gets, after designing and analyzing algorithms on PRAM for more than 12 years, to finally be able to tell to students... "this can be easily turn to code and run on a real-world multi-core machine"!!!--Prof. Chryssis Georgiou on using the XMT platform in his University of Cyprus class.
Spring 2012: Parallel Computing Architectures, Electrical Engineering, Technion, Israel-Institute-of-Technology.
Spring 2011: Parallel Algorithms, University of California, Davis.
Spring 2011: Parallel Algorithms, University of California, San Diego.
Registration form for Middle School Computer Engineering Summer Camp at the John F. Kennedy High School, Silver Spring, Maryland, July 13-24, 2009, Montgomery County Public Schools: "Students will learn about computer programs for the 64-processor desktop-of-the-future computer built at UMCP and will explore relevant Computer Science and Mathematics concepts".
2009-10: Parallel Computing , Thomas Jefferson High School for Science and Technology, Alexandria, VA. Chapter on Explicit Multi-Threading (XMT) from 2008-9 course.
"Parallel Programming Comes to Ingenuity", The Ingenuity Spotlight, February 2009, The Ingenuity Project at the Baltimore Polytechnic Institute High School. Note the following comment in the story on page 2: ''The three classes in December were part of a study performed by UMCP Department of Computer Science to test these new teaching methods, and it turned out to be successful: in the questionnaires filled out by the students there was an equal split between people who said the material was the right level of difficulty and people who said it was too easy.'' (Bold face added, UV.)
Spring 2009: Algorithms and Programming in a Parallel Environment (syllabus in Hebrew) , The Academic College of Tel-Aviv Yaffo.
Resources for multicore programming education , webpage maintained by Nir Shavit, Tel Aviv University.

Personal Links

Home page of Immanuela Gruenberg, my wife.

Mailing Address:: Uzi Vishkin; University of Maryland Institute for Advanced Computer Studies (UMIACS); A.V. Williams Building. Room 2365; College Park, MD 20742-3251; Phone: (301) 405-6763; email: x at umd.edu, where x is the last name