A paper by Danny Hillis and Guy Steele.
Parallel computers with tens of thousands of processors are typically programmed in a data parallel style, as opposed to the control parallel style used in multiprocessing. The success of data parallel algorithms - even on problems that at first glance seem inherently serial - suggests that this style of programming has much wider applicability than was previously thought.
An amazing tour of the data parallel programming style, as used in Connection Machine Lisp. The paper doesn't require any special background (no Lisp), and has a very nice puzzle-solving feel. They demonstrate logarithmic-time algorithms for a variety of problems, such as lexing and sorting, for Very Concurrent non von Neumann machines.
Posted to general by Luke Gorrie on 11/25/02; 5:21:20 AM