Arabic Bulgarian Chinese Croatian Czech Danish Dutch English Estonian Finnish French German Greek Hebrew Hindi Hungarian Icelandic Indonesian Italian Japanese Korean Latvian Lithuanian Malagasy Norwegian Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swedish Thai Turkish Vietnamese
Arabic Bulgarian Chinese Croatian Czech Danish Dutch English Estonian Finnish French German Greek Hebrew Hindi Hungarian Icelandic Indonesian Italian Japanese Korean Latvian Lithuanian Malagasy Norwegian Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swedish Thai Turkish Vietnamese

definition - Uzi_Vishkin

definition of Wikipedia

   Advertizing ▼


Uzi Vishkin

From Wikipedia, the free encyclopedia

Jump to: navigation, search
Uzi Vishkin
Tel Aviv, Israel
Fieldsparallel algorithms
InstitutionsIBM Thomas J. Watson Research Center
New York University
Tel Aviv University
University of Maryland, College Park
Alma materHebrew University
Doctoral advisorYossi 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]



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


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[2] 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[3] named Paraleap,[4] that demonstrates the overall concept. The XMT concept was presented in Vishkin et al. (1998) and Naishlos et al. (2003) and the XMT 64-processor computer in Wen & Vishkin (2008). The demonstration 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.

Parallel algorithms

In the field of parallel algorithms, Uzi Vishkin co-authored the paper Shiloach & Vishkin (1982) 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.

In the field of parallel and distributed algorithms, one of the seminal papers co-authored by Uzi Vishkin is Cole & Vishkin (1986). 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.,[5] and it forms the basis of many other distributed algorithms for graph colouring.[6]

Other contributions by Uzi Vishkin and various co-authors include parallel algorithms for list ranking, lowest common ancestor, spanning trees, and biconnected components.

Selected publications


  1. ^ ACM: Fellows Award / Uzi Vishkin.
  2. ^ Vishkin, Uzi. Spawn-join instruction set architecture for providing explicit multithreading. U.S. Patent 6,463,527. See also Vishkin et al. (1998).
  3. ^ University of Maryland, press release, June 26, 2007: "Maryland Professor Creates Desktop Supercomputer".
  4. ^ University of Maryland, A. James Clark School of Engineering, press release, November 28, 2007: "Next Big "Leap" in Computing Technology Gets a Name".
  5. ^ 1st ed., Section 30.5.
  6. ^ See, e.g., Goldberg, Plotkin & Shannon (1988).


  • Baase, Sara; Van Gelder, Allen (2000). Computer Algorithms Introduction to Design and Analysis (Third ed.). Addison-Wesley. ISBN 0-201-61244-5. 
  • Brent, Richard P. (1974), [Expression error: Missing operand for > "The parallel evaluation of general arithmetic expressions"], Journal of the ACM 21: 201–208 .
  • Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990). Introduction to Algorithms (First ed.). MIT Press and McGraw-Hill. ISBN 978-0-262-03141-7. 
  • Eppstein, David; Galil, Zvi (1988), [Expression error: Missing operand for > "Parallel algorithmic techniques for combinatorial computation"], Ann. Rev. Comput. Sci 3: 233–283 

This survey paper cites 16 papers co-authored by Vishkin

  • Goldberg, Andrew V.; Plotkin, Serge A.; Shannon, Gregory E. (1988), [Expression error: Missing operand for > "Parallel symmetry-breaking in sparse graphs"], SIAM Journal on Discrete Mathematics 1 (4): 434–446, doi:10.1137/0401044 
  • JaJa, Joseph (1992). An Introduction to Parallel Algorithms. Addison-Wesley. ISBN 0-201-54856-9. 

Cites 36 papers co-authored by Vishkin

  • Karp, Richard M.; Ramachandran, Vijaya (1988), [Expression error: Missing operand for > "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). Practical PRAM Programming. Wiley-Interscience. ISBN 0-471-35351-5. 

Cites 19 papers co-authored by Vishkin

External links


All translations of Uzi_Vishkin

sensagent's content

  • definitions
  • synonyms
  • antonyms
  • encyclopedia

Dictionary and translator for handheld

⇨ New : sensagent is now available on your handheld

   Advertising ▼

sensagent's office

Shortkey or widget. Free.

Windows Shortkey: sensagent. Free.

Vista Widget : sensagent. Free.

Webmaster Solution


A windows (pop-into) of information (full-content of Sensagent) triggered by double-clicking any word on your webpage. Give contextual explanation and translation from your sites !

Try here  or   get the code


With a SensagentBox, visitors to your site can access reliable information on over 5 million pages provided by Sensagent.com. Choose the design that fits your site.

Business solution

Improve your site content

Add new content to your site from Sensagent by XML.

Crawl products or adds

Get XML access to reach the best products.

Index images and define metadata

Get XML access to fix the meaning of your metadata.

Please, email us to describe your idea.


The English word games are:
○   Anagrams
○   Wildcard, crossword
○   Lettris
○   Boggle.


Lettris is a curious tetris-clone game where all the bricks have the same square shape but different content. Each square carries a letter. To make squares disappear and save space for other squares you have to assemble English words (left, right, up, down) from the falling squares.


Boggle gives you 3 minutes to find as many words (3 letters or more) as you can in a grid of 16 letters. You can also try the grid of 16 letters. Letters must be adjacent and longer words score better. See if you can get into the grid Hall of Fame !

English dictionary
Main references

Most English definitions are provided by WordNet .
English thesaurus is mainly derived from The Integral Dictionary (TID).
English Encyclopedia is licensed by Wikipedia (GNU).


The wordgames anagrams, crossword, Lettris and Boggle are provided by Memodata.
The web service Alexandria is granted from Memodata for the Ebay search.
The SensagentBox are offered by sensAgent.


Change the target language to find translations.
Tips: browse the semantic fields (see From ideas to words) in two languages to learn more.

last searches on the dictionary :

2633 online visitors

computed in 0.062s

   Advertising ▼

I would like to report:
section :
a spelling or a grammatical mistake
an offensive content(racist, pornographic, injurious, etc.)
a copyright violation
an error
a missing statement
please precise:



Company informations

My account



   Advertising ▼