Top | Bio | Research Interests | Publications | Reseach Project | Software Release | On-Line Tutorial | Conf. Organization | Talks | Teaching | Contact

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


Top | Bio | Research Interests | Publications | Reseach Project | Software Release | On-Line Tutorial | Conf. Organization | Talks | Teaching | Contact

Research Interests

Non-technical introduction

Overview and 2019 Perspective: Uzi Vishkin's research aspirations evolved over the years from that of a parallel algorithms theory specialist to more of a generalist. The deep question guiding his work has been whether it is feasible to align the theory of parallel algorithms, parallel programming and many-core hardware into a coherent computing stack for the processor of the future. Along with his research team, he developed the only current approach that enables that, while vendor-supported approaches have given up on their prior objective, as explained next.
Source programming (coding) is the programmer's input towards an executable program on target hardware. It is widely agreed that executables on many-core hardware must be multi-threaded. However, multi-threaded source programming is often too difficult, due to challenges such as race conditions and programming for locality. By 2019, (CPU and GPU) commercial vendors have apparently nearly abandoned all their prior expectations that application developers provide multi-threaded source code. To the extent that new performance executable are produced they are developed by in-house vendor programmers, often for the few specific routines that their marketing people identified as useful, e.g., for Python programmers.
In contrast, Vishkin's team has demonstrated that single-threaded programming for parallelism can: (i) directly harness the theory of parallel algorithms as-is for parallel programming, and (ii) achieve competitive many-core performance, as long as many-core hardware/software has been designed properly.

Still, a listing of technical areas and some elaboration follow:
  • Parallelism in computing
  • 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.

  • Machine learning as well as other potential "killer applications" for parallel computing.
  • 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.

Top | Bio | Research Interests | Publications | Reseach Project | Software Release | On-Line Tutorial | Conf. Organization | Talks | Teaching | Contact

Publications

Research Project

Software Release

Tutorial

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

Top | Bio | Research Interests | Publications | Reseach Project | Software Release | On-Line Tutorial | Conf. Organization | Talks | Teaching | Contact

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. ]

Interesting Teaching-Related Links

Personal Links

Statement Against Boycott

Where is the outrage over the bombardment of civilians in Israel?

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

Top | Bio | Research Interests | Publications | Reseach Project | Software Release | On-Line Tutorial | Conf. Organization | Talks | Teaching | Contact