| ||
| ||
| ||
How to Think Algorithmically in Parallel?Or, Parallel Programming through Parallel AlgorithmsFull-day TutorialDate and Venue:
| ||
AbstractThe abstract model used in standard undergraduate courses on algorithms and data-structures for serial computing is known as RAM, for random-access machine, or model. What should be the proper counterpart for parallel computing? Following a fierce "battle of ideas" during most of the 1980s regarding this very question, a clear winner emerged: The parallel random-access machine, or model, widely known as the PRAM (pronounced pee-RAM). The main assumption of the PRAM is that the latency for arbitrary number of memory accesses is the same as for one access. The PRAM has been the model of choice for the major theory-related communities. During 1988-90, a big PRAM chapter was included in at least 3 then-popular standard algorithms textbooks: Baase-88, Cormen-Leiserson-Rivest-90, 1st Edition, and Manber-89. In fact, in terms of magnitude and breadth the PRAM has no serious contender. One can say that the PRAM emerged as a clear winner in a natural selection process that took place during the 1980s. The PRAM did not fare as well with architecture communities in the early 1990s, when chip multiprocessing was not yet possible. The most relevant criticism argued correctly that there was no way to get sufficient bandwidth from multi-chip multiprocessors to allow the programmer to view the machine as a PRAM. A very small fraction of the instruction time is devoted to programming, as opposed to reasoning about algorithms. Programming is to be picked up from documents (e.g., programming tutorial and manual). This is a strength: (i) algorithm design is the idea part of a program and where the real thinking takes place, (ii) programming (including parallel programming), on the other hand, should be a skill that can be acquired. Indeed, in the serial computing example, programming is typically not taught beyond the Freshman year. However, algorithms and data structure are taught all the way to graduate school. The short time devoted to programming attests to the relative ease of parallel programming. It should be clear that easy parallel programming is the overriding objective of the overall approach. The (relatively short) architecture part of the tutorial will make the case that an on-chip parallel processor can provide sufficient bandwidth between processors and memories, and discuss the recent (FPGA) commitment to silicon of an explicit multi-threaded (XMT) architecture guided by a "PRAM-On-Chip" vision. | ||
| ||
Target audienceIn order to function in the new world of multi-core computer systems, some programming for parallelism cannot be avoided. Any one of the conference participants who recognizes that should find it helpful to understand the thinking process behind such programming. In fact, the short history of parallel computing provides many examples where parallel architectures were built only to find out that their designers expected that the thought process behind their programming will emerge after their machine are deployed. Unfortunately, build-first figure-out-how-to-think/program-later has its limits. The opportunity that the tutorial will provide for hands-on experience could have a special appeal for the general audience of the conference. | ||
| ||
What to expectThe key knowledge and ideas that participants can take away are:
| ||
| ||
Where is this tutorial coming from?Material for this tutorial is taken from a graduate course on Parallel Algorithms at the University of Maryland that is cross-listed between computer science and electrical and computer engineering. The course is a bit unique as it has its own computer, own compiler and own programming language. The tutorial provides coherent snapshots from this "UMD course planet". The core material is an updated shorter version of the course class notes. Documents featuring a tutorial and a manual of a modest extension to C (called XMT-C) used for programming will be provided. | ||
| ||
Organizer and presenter
Uzi Vishkin. BioUzi Vishkin is a permanent member of the University of Maryland Institute for Advanced Computer Science (UMIACS) and Professor of Electrical and Computer Engineering since 1988. He got his DSc in Computer Science from the Technion-Israel Institute of Technology and his MSc and BSc in Mathematics from the Hebrew University, Jerusalem, Israel. He was Professor of Computer Science at Tel Aviv University and the Technion, research faculty at the Courant Institute, NYU and a post-doc at IBM T.J Watson. He is Fellow of the ACM and an ISI-Thompson Highly-Cited Researcher. | ||
| ||
Relevant Publications
The more recent publication below are either already posted, or will be posted on http://www.umiacs.umd.edu/~vishkin/XMT
| ||
| ||
| ||
|